...

пятница, 24 октября 2014 г.

Распределенные вычисления для поиска жилья

Все слышали о distributed computing проектах, которые пытаются решать масштабные задачи, вроде поиска внеземной жизни, лекарств от СПИДа и рака, поиска простых чисел и уникальных решений для Судоку. Все это очень занимательно, но не более того, ведь практической пользы для человека, поделившегося ресурсами своего компьютера — никакой.

Сегодня я расскажу о распределенных вычислениях, решающих ваши проблемы. Ну не все конечно, а только некоторые, связанные с поиском жилья. Недавно я писал о проекте Sobnik, расширении для Chrome, которое обнаруживает посредников на досках объявлений. Две недели назад была запущена новая версия программы, в которой работа по сканированию и анализу объявлений распределяется по компьютерам пользователей. За прошедшее время было обработано около миллиона объявлений из более тысячи городов России, и это — только начало. Подробности, технические детали и еще немного цифр ждут вас под катом.


Зачем здесь распределенные вычисления?




Для того, чтобы выявить посредника, программе требуется загрузить объявление, распарсить его, проанализировать фотографии, сложить результаты в базу данных и выполнить несколько видов поиска, в частности — по номерам телефонов. Изначально пользователю требовалось открыть конкретное объявление, чтобы плагин выполнил этот анализ. Это неудобно, ведь объявлений сотни, и среди них почти все — посредники. От ручных операций нужно было избавляться, ведь компьютеры для того и существуют, чтобы действовать автоматически!

Первым планом стало создание централизованного сканера объявлений (далее — краулер). Берем PhantomJS, допиливаем под него JS-код плагина, и запускаем сканирование на сервере. Авито, конечно, будет сердиться на масштабное сканирование, и будет блокировать IP сервера, но на тот случай было решено накупить IP-адресов или использовать кучу прокси (Авито — единственная пока доска объявлений, с которой работает плагин). Но чем дольше я работал и думал в этом направлении, тем больше понимал — решение плохое:



  1. Сервера стоят денег, которые тратить не хотелось — проект ведь бесплатный, и я мечтаю его таковым оставить.

  2. Надежности никакой — соревноваться с Avito в поиске незабаненных прокси не было никакого желания.

  3. Масштабируемость такого решения упиралась в еще большие деньги, см. п.1.




Вскоре я пришел к выводу, что единственным решением, лишенным упомянутых недостатков, будет автоматический краулер, встроенный в плагин, и работающий в браузерах у пользователей даже тогда, когда они сами не заняты поиском жилья.

Распределенный краулер




Активно с Avito в каждый момент времени работает лишь небольшой процент пользователей, однако браузер с работающим плагином запущен почти весь день. Что если в браузере каждого пользователя сканировалось бы, скажем, одно объявление в минуту? Этих суммарных мощностей хватило бы, чтобы быстро сканировать объявления, с которыми в данный момент работают активные пользователи. И Авито бы не расстраивался, ведь перегрузок с определенных IP никогда бы не возникало. Да, вероятно не все захотят делиться мощностями своих компьютеров, однако мне верилось, что «сознательных граждан» будет все же достаточно. Идея выглядела очень заманчиво.

Углубившись в техническую часть нового подхода я осознал, что с возросшими нагрузками текущий сервер просто не справится. Обработка фотографий для обнаружения номеров телефонов и так уже жрала почти весь CPU, а если поток объявлений возрастет на порядок? Бесплатный виртуальный сервер от AWS Free Tier должен был справляться, иначе жизнь проекта была под угрозой. Так что первым шагом стал перенос работы с изображениями в масштабируемую часть системы — на клиента. Код плагина открыт, и конечно были опасения, что публикация алгоритма облегчит злым спамерам поиск слабых мест и путей для обмана. Однако, других вариантов для развития проекта я не видел, и решил — будь что будет.


Итак, теперь Sobnik открывает отдельную вкладку в вашем браузере. Периодически, примерно раз в минуту, он запрашивает с сервера задание — адрес объявления для сканирования, загружает это объявление в своей вкладке, парсит, обрабатывает изображения и отправляет результаты на сервер. Задания на сканирование создаются, когда кто-то из пользователей открывает список объявлений — заранее и «впрок» ничего не сканируется, объявления — продукт скоропортящийся.


Сознательных граждан, пожелавших поделиться мощностями своего ПК, пока не так уж много — порядка пары сотен. Однако, этого вполне достаточно, чтобы обрабатывать по 60 тысяч объявлений в день, обеспечивая нужды тысячи пользователей плагина. Открытый на Авито список из сотни объявлений обычно обрабатывается в пределах одной минуты.


Звучит все это довольно просто, однако меня до сих пор завораживает возможность использовать сотни чужих компьютеров для решения общей задачи. Браузер — идеальная платформа для приложений такого рода:



  1. JavaScript нынче умеет почти всё.

  2. JS-код — кроссплатформенный (за исключением обращений к API браузера).

  3. Расширение устанавливается в один клик.

  4. Распространением обновлений ПО занимается Webstore.

  5. Браузер запущен большую часть дня.




Если вы задумали свои собственные SETI@HOME — присмотритесь, может вам пора изучать API любимого браузера. Об этом уже многие писали, но расцвета распределенных вычислений, решающих практические проблемы волонтеров, а не абстрактной человеческой цивилизации — пока не видно.

Стоит обратить внимание на один нюанс — людей очень напрягает, когда в браузере самостоятельно открываются вкладки. И если уж открывать их необходимо, стоит потратить достаточно усилий на то, чтобы такое поведение было ожидаемым для пользователей (инструкции, faq, понятные информационные сообщения). Пользуясь случаем, приношу извинения всем, кто был удивлен поведением плагина после выхода новой версии программы — мне следовало потратить больше времени на информирование вас о таких существенных нововведениях.


Эффективный сервер




Сервер, координирующий работу в распределенной вычислительной системе, должен быть очень эффективным, ведь его не так легко масштабировать. Сервер проекта Sobnik занимается не только координацией, но и решением прикладной задачи — поиском по базе данных, поэтому требования к нему еще выше. И если функциональность клиентской части была просто слегка расширена, сервер был переделан почти полностью (напомню, он написан на Go).

Изначально за хранение данных и выполнение поисков отвечала MongoDB, теперь все рабочие данные хранятся в ОЗУ. На сервере запущено два процесса — фронтенд и бекенд. Фронтенд взаимодействует с клиентами, ведет очередь заданий для распределенного краулера, очередь объявлений для передачи в бекенд, и небольшой кэш с информацией о статусе объявлений (посредник/собственник). Бекенд хранит данные в ОЗУ (выжимку из входящих объявлений), выполняет по ним поиски, асинхронно пишет входящие объявления в MongoDB, асинхронно выполняет запросы фронтенда. Взаимодействуют процессы с помощью ZeroMQ.


MongoDB используется в максимально эффективных режимах — для последовательной записи входящих объявлений, и для последовательного чтения при перезапуске бекенда, в один поток. При старте, бекенд читает из СУБД актуальные объявления, выполняет те же поиски и анализ, как и при штатном поступлении данных от клиентов, и наполняет свою базу в оперативной памяти. Такой подход позволяет легко модифицировать алгоритм выявления посредников, и применять его ко всей базе простым перезапуском бекенда.


Пока бекенд запускается, наполняя свою базу, фронтенд продолжает обслуживать клиентов — входящие объявления складывает в очередь, запросы статуса объявлений обслуживает из кэша, задания раздает из своей очереди.


В системе с почти десятком параллельных потоков (goroutine) нет ни одного мьютекса. Каждый поток имеет эксклюзивный доступ к своим данным, и обслуживает другие потоки через каналы (их наличие в Go просто несказанно радует).


Все межпроцессные и межпотоковые взаимодействия выполняются в неблокирующем режиме. Если принимающая сторона не успевает читать, данные либо складываются в очередь (входящие объявления на фронтенде), либо отбрасываются (прочие запросы). Все очереди и кэш имеют ограничение на размер, и при заполнении наиболее старые записи отбрасываются — клиентам Собника последняя информация более ценна. В случае невозможности выполнить запрос (канал с данными занят) клиенту отправляется соответствующий ответ, при этом клиент пробует снова, с возрастающим интервалом.


Такая архитектура создавалась с целью обеспечить максимальную надежность и доступность сервиса. И пока что она себя оправдывает — имея в базе почти миллион объявлений и обрабатывая до миллиона http-запросов в день, load_average на виртуальном сервере стабильно держится ниже 10%.


Ищем жилье по-новому!




Sobnik успешно пережил второе рождение — «распределился» и окреп. Месяц назад это была лишь интересная идея, прототип, который многие установили чтобы побаловаться. Теперь — это работающий инструмент, которым удобно пользоваться и который реально помогает фильтровать спам. Это стало возможным благодаря вам, Уважаемые Пользователи, ведь это ваши компьютеры решают общую задачу.

Конечно, система работает далеко не идеально, есть много вопросов к детектору для фотографий, и есть проблемы с анализом текста объявлений. Однако, теперь ясно — у Собника есть достаточно ресурсов для решения этих вопросов. Остается только подпитывать энтузиазм автора, чего Вы можете добиться критикой, предложениями и ценными комментариями.


This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.


Комментариев нет:

Отправить комментарий