Архитектура краулера вертикального поиска Долинин Михаил Rambler 2010

Поисковая система: обзор Index Builder Найти | Краулер - компонент поисковой системы, ответственный за сбор и первичную обработку данных, из которых формируются индексы поисковой машины. WEB Crawler Search Engine Indexes

Вертикальный поиск Интерес представляют лишь сайты определённой тематики. Лишь часть страниц этих сайтов содержит интересующие данные. Объект обработки системы не HTML-данные, а документы с предопределённым набором свойств. Свойства необходимо самостоятельно извлекать из HTML-страниц. Все необходимые исходные параметры хранятся в наборе конфигурационных файлов. TITLE:Avatar YEAR:2010 HTML... Avatar 2010 Cameron... DIRECTOR:Cameron Document

Минимизация входящего трафика –желательно качать как можно меньше и как можно реже Минимизация объема выдачи –нужно выдавать лишь ту информацию, которая приводит к изменениям в индексах Масштабируемость процесса –Разделение процесса на подзадачи –Связность модулей должна быть минимальна. –Изменения системы для обработки новых сайтов, новых типов данных должны быть локализованы и минимальны –Алгоритмы должны позволять распараллеливание по данным. Компоненты краулера Особенности задачи при больших объёмах

Fetcher: получение данных из Web Качать только то, что необходимо для построения индексов Не DDOSить сайты –Качать в один поток –Делать паузы между запросами –Не превышать лимит запросов в единицу времени «Слушаться» robots.txt WEB Fetcher GET OK Cookies Robots.txt etc Unparsed Content (HTML) URL Last-Modified URL

Scheduler Scheduler: расписание запросов Качать можно одновременно с нескольких сайтов. Расписание запросов – циклическая очередь с приоритетами На входе – очередь заданий, на выходе – очередь результатов WEB Fetcher 1 Fetcher N … url1 url2 url3 url1 url2 url3 content1 content2 content3 Parser Site Configs

Извлечение интересующих параметров и выдача их на вход построителю индексов. –В случае, если документ скачан повторно, необходимо определить, следует ли его передавать в построитель индексов. Parser - обработка скачанного контентаParser: извлечение свойств документа Parser Set of RegExps Unparsed Content (HTML) URL Index Builder Param1: Value1 URL ParamN: ValueN … Param1: Value1 ParamN: ValueN URL Param1: Value1 ParamN: ValueN CheckSum Site Config

Извлечение из полученного HTML ссылок на другие страницы –Интересны лишь некоторые ссылки – какие именно, задаются конфигами –Полученные ссылки сортируются и сохраняются в списке вместе с адресом самого документа Parser: извлечение ссылок Parser Set of RegExps Sorted url list Unparsed Content (HTML) URL Site Config … url 1 url M URL … url 2

Каждый элемент списка содержит следующую информацию: –URL –Checksum (CRC32 от извлеченных параметров) –Время последнего скачивания –Промежуток времени до следующего скачивания Формат списка URLСhecksumRefetch DelayFetch Time… Для новых урлов, только что извлечённых из HTML: Checksum = 0 Fetch Time = 0 Refetch Delay = default из конфига Cписок может содержать также произвольные дополнительные данные, зависящие от специфики контента (Last-Modified, etc)

Все сформированные списки заносятся в очередь –Элементом очереди является не сам список, а имя файла, в котором он хранится Извлекает списки из очереди следующий модуль – Url Merger Очередь списков Parser List1 url M … url1 url2 url3 content1 content2 content3 Documents queue url 1 url N … url 1 url K … url 1 List2 List3 List1 List2 List3 Url lists queue

URL Merger: слияние списков Списки попарно извлекаются из очереди и объединяются в один список с помощью алгоритма сортировки слиянием. Полученный список: содержит только уникальные урлы возвращается в очередь Процесс продолжается до тех пор, пока не останется один список, содержащий все данные Merger Url lists queue List 1 List 2 List N … List N+1 List1 List N+1 = List 1 + List 2 List2

Url Merger: нюансы алгоритма Слияния списков можно производить параллельно: Создаём несколько процессов-мержеров Эффективнее сначала объединить все мелкие списки, затем более крупные и т.д: Очередь с приоритетами Приоритет списка = количество элементов в нём Парсер создаёт списки практически непрерывно, а процесс слияния более эффективен, если производить его, когда накопится достаточно много мелких списков. Q P = Q F * K где: Q P – суммарное количество элементов в необработанных списках Q F – количество элементов в очереди на закачку K – константа

Merger M Url Merger: адаптированный алгоритм Управление выносится в отдельный процесс – Collector Итоговый список, содержащий все урлы, выносится из очереди и подаётся на вход модулю Updater Merger 1 … Url list priority queue List 1 List … List N … List … … Result Url List Fetcher Queue Length Updater Collector

Итоговый список периодически просматривается и часть урлов отправляются в очередь на закачку: –Все новые –На повторную закачку, т.е. те, у которых наступил момент Fetch_date + refetch_delay Updater: отправка на скачивание url1 url2 url3 url N … Updater Result Url List Site1 url queue Site2 url queue SiteM url queue … Fetcher queue set Scheduler Time to (re)fetch ?

Функционирование описанной кольцевой схемы поддерживается самостоятельно, и требуется лишь однократно её запустить. –При необходимости можно делать это периодически Seeder - процесс, «сеящий зерно», т.е. записывающий исходные урлы в изначально пустую очередь на скачивание –Количество таких точек входа может быть любым Seeder: инициализация процесса Seeder SiteM entry url Site configs Site1 url queue Site2 url queue SiteM url queue … Fetch queue set Site2 entry url Site1 entry url

Crawler: общая схема Index Builder FetcherN Merger1MergerM UpdaterSeeder Fetcher1 Scheduler … … Result list Parser Site configs Collector URL Lists WEB

Re-fetch: обновление документов Web-данные обновляются - индексы устаревают Как определить частоту обновлений? HTML URL Params URL ? Params Indexes WEB

Re-fetch: обновление документов #2 В идеале краулер должен скачивать страницу и обновлять индекс тогда и только тогда, когда источник изменился –В общем случае это невозможно – нас не оповещают Исходный период обновления страниц подбирается вручную для каждого сайта-источника и сохраняется в соответствующем конфиге. Cтраницы ведут очень индивидуально: некоторые не меняются годами, другие обновляются каждую минуту. –Поэтому равномерное скачивание всех страниц с одинаковой периодичностью нерационально –Универсального значения периода не существует –Как правило, страницы часто обновляются вскоре после создания, а со временем обновления становятся реже

Re-fetch: обновление документов #3 URLСhecksumRefetch DelayFetch Time… Для всех документов сайта значение Refetch Delay устанавливается в соответсвии с конфигом: –Документ повторно скачивается, как только наступает момент Fetch Time + Refetch Delay Далее, используя новые данные, можно попробовать адаптировать параметры, чтобы оптимизировать работу: –Если данные источника изменились – лучше сократить промежуток до следующего запроса. –Если изменений нет – срок до следующей попытки можно увеличить. +

Как определить, изменился ли документ? –Last-Modified пригоден только для статического контента. Полагаем, что документ изменился, если изменился хотя бы один из его параметров, значимых для нас Чтобы не хранить все значения свойств, создаём их отпечаток и сохраняем до следующего скачивания. –Если изменился отпечаток – изменился документ – необходимо обновлять индекс Checksum: выявление изменений = СRC32 Param1: Value1 URL ParamN: ValueN … Param1: Value1 ParamN: ValueN URL Param1: Value1 ParamN: ValueN ( ) Сhecksum

Определение периода повторного скачивания Модуль Parser, обрабатывая документ, каждый раз рассчитывает новый CheckSum и сравнивает с предыдущим. Если они не совпали – скачали эффективно: Подаём документ на вход Index Builder Уменьшаем срок до следующей выкачки: Refetch Delay /= K Если совпали – скачали вхолостую: Индексы не обновляем Увеличиваем срок до следующей выкачки: Refetch Delay *= K URLRefetch DelayFetch Time… Сhecksum K = 2

Поиск по видео: cоставные документы Для формирования документа поиска по видео ресурсам необходимо два компонента: –Страница HTML для извлечения параметров документа –Собственно видеофайл (FLV, 3GP, AVI) для генерации GIF-превью, поиска дубликатов и др. В таком случае скачивание документа происходит в два этапа. URL ChecksumLast-Modified HTML paramsVideo content

Fetcher Queue Поиск по видео: алгоритм #1 URL Fetcher URL HTML Parser URL params VideoURL После выяснения урла видео-контента Документ снова отправляется в очередь на выкачку

Fetcher Queue Поиск по видео: алгоритм #2 Fetcher Parser URL params VideoURL URL params VideoURL Video content Для более быстрого получения «полноценных» документов здесь можно реализовать очередь с приоритетами Index Builder

Язык реализации – Perl Каждый логический модуль работает в отдельном процессе –Возможно разнесение процессов по разным хостам –Возможна реализация параллельности по данным Процессы взаимодействуют 3 способами (с помощью IO::KQueue): –Пайпы –Сокеты –Файловые очереди Monitor – процесс, являющийся родителем для всех вышеописанных процессов, и выполняющий следующие функции: –Запуск и остановка модулей –Периодическая проверка их жизнеспособности (kill 0) и восстановление логической целостности при сбоях –Сбор статистики Seeder: запуск процессаТехнические детали текущей реализации

Спасибо за внимание ?

Дополнительно: реализация файловой очереди Алгоритм схож с алгоритмом реализации очереди с помощью двух стеков: Очередь представляет собой два изначально пустых файла – IN и OUT Операция PUSH добавляет элемент в конец файла IN Операция PULL извлекает текущий элемент из файла OUT, двигаясь от его начала к концу Если достигнут конец файла OUT, то всё содержимое файла IN переносится в OUT Элемент А INOUT Элемент B Элемент C Записываем Элемент А Элемент B Элемент C Переносим Считываем сверху вниз