Скачать презентацию
Идет загрузка презентации. Пожалуйста, подождите
Презентация была опубликована 11 лет назад пользователемashmanov.com
1 Архитектура краулера вертикального поиска Долинин Михаил Rambler 2010
2 Поисковая система: обзор Index Builder Найти | Краулер - компонент поисковой системы, ответственный за сбор и первичную обработку данных, из которых формируются индексы поисковой машины. WEB Crawler Search Engine Indexes
3 Вертикальный поиск Интерес представляют лишь сайты определённой тематики. Лишь часть страниц этих сайтов содержит интересующие данные. Объект обработки системы не HTML-данные, а документы с предопределённым набором свойств. Свойства необходимо самостоятельно извлекать из HTML-страниц. Все необходимые исходные параметры хранятся в наборе конфигурационных файлов. TITLE:Avatar YEAR:2010 HTML... Avatar 2010 Cameron... DIRECTOR:Cameron Document
4 Минимизация входящего трафика –желательно качать как можно меньше и как можно реже Минимизация объема выдачи –нужно выдавать лишь ту информацию, которая приводит к изменениям в индексах Масштабируемость процесса –Разделение процесса на подзадачи –Связность модулей должна быть минимальна. –Изменения системы для обработки новых сайтов, новых типов данных должны быть локализованы и минимальны –Алгоритмы должны позволять распараллеливание по данным. Компоненты краулера Особенности задачи при больших объёмах
5 Fetcher: получение данных из Web Качать только то, что необходимо для построения индексов Не DDOSить сайты –Качать в один поток –Делать паузы между запросами –Не превышать лимит запросов в единицу времени «Слушаться» robots.txt WEB Fetcher GET OK Cookies Robots.txt etc Unparsed Content (HTML) URL Last-Modified URL
6 Scheduler Scheduler: расписание запросов Качать можно одновременно с нескольких сайтов. Расписание запросов – циклическая очередь с приоритетами На входе – очередь заданий, на выходе – очередь результатов WEB Fetcher 1 Fetcher N … url1 url2 url3 url1 url2 url3 content1 content2 content3 Parser Site Configs
7 Извлечение интересующих параметров и выдача их на вход построителю индексов. –В случае, если документ скачан повторно, необходимо определить, следует ли его передавать в построитель индексов. 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
8 Извлечение из полученного HTML ссылок на другие страницы –Интересны лишь некоторые ссылки – какие именно, задаются конфигами –Полученные ссылки сортируются и сохраняются в списке вместе с адресом самого документа Parser: извлечение ссылок Parser Set of RegExps Sorted url list Unparsed Content (HTML) URL Site Config … url 1 url M URL … url 2
9 Каждый элемент списка содержит следующую информацию: –URL –Checksum (CRC32 от извлеченных параметров) –Время последнего скачивания –Промежуток времени до следующего скачивания Формат списка URLСhecksumRefetch DelayFetch Time… Для новых урлов, только что извлечённых из HTML: Checksum = 0 Fetch Time = 0 Refetch Delay = default из конфига Cписок может содержать также произвольные дополнительные данные, зависящие от специфики контента (Last-Modified, etc)
10 Все сформированные списки заносятся в очередь –Элементом очереди является не сам список, а имя файла, в котором он хранится Извлекает списки из очереди следующий модуль – 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
11 URL Merger: слияние списков Списки попарно извлекаются из очереди и объединяются в один список с помощью алгоритма сортировки слиянием. Полученный список: содержит только уникальные урлы возвращается в очередь Процесс продолжается до тех пор, пока не останется один список, содержащий все данные Merger Url lists queue List 1 List 2 List N … List N+1 List1 List N+1 = List 1 + List 2 List2
12 Url Merger: нюансы алгоритма Слияния списков можно производить параллельно: Создаём несколько процессов-мержеров Эффективнее сначала объединить все мелкие списки, затем более крупные и т.д: Очередь с приоритетами Приоритет списка = количество элементов в нём Парсер создаёт списки практически непрерывно, а процесс слияния более эффективен, если производить его, когда накопится достаточно много мелких списков. Q P = Q F * K где: Q P – суммарное количество элементов в необработанных списках Q F – количество элементов в очереди на закачку K – константа
13 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
14 Итоговый список периодически просматривается и часть урлов отправляются в очередь на закачку: –Все новые –На повторную закачку, т.е. те, у которых наступил момент 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 ?
15 Функционирование описанной кольцевой схемы поддерживается самостоятельно, и требуется лишь однократно её запустить. –При необходимости можно делать это периодически 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
16 Crawler: общая схема Index Builder FetcherN Merger1MergerM UpdaterSeeder Fetcher1 Scheduler … … Result list Parser Site configs Collector URL Lists WEB
17 Re-fetch: обновление документов Web-данные обновляются - индексы устаревают Как определить частоту обновлений? HTML URL Params URL ? Params Indexes WEB
18 Re-fetch: обновление документов #2 В идеале краулер должен скачивать страницу и обновлять индекс тогда и только тогда, когда источник изменился –В общем случае это невозможно – нас не оповещают Исходный период обновления страниц подбирается вручную для каждого сайта-источника и сохраняется в соответствующем конфиге. Cтраницы ведут очень индивидуально: некоторые не меняются годами, другие обновляются каждую минуту. –Поэтому равномерное скачивание всех страниц с одинаковой периодичностью нерационально –Универсального значения периода не существует –Как правило, страницы часто обновляются вскоре после создания, а со временем обновления становятся реже
19 Re-fetch: обновление документов #3 URLСhecksumRefetch DelayFetch Time… Для всех документов сайта значение Refetch Delay устанавливается в соответсвии с конфигом: –Документ повторно скачивается, как только наступает момент Fetch Time + Refetch Delay Далее, используя новые данные, можно попробовать адаптировать параметры, чтобы оптимизировать работу: –Если данные источника изменились – лучше сократить промежуток до следующего запроса. –Если изменений нет – срок до следующей попытки можно увеличить. +
20 Как определить, изменился ли документ? –Last-Modified пригоден только для статического контента. Полагаем, что документ изменился, если изменился хотя бы один из его параметров, значимых для нас Чтобы не хранить все значения свойств, создаём их отпечаток и сохраняем до следующего скачивания. –Если изменился отпечаток – изменился документ – необходимо обновлять индекс Checksum: выявление изменений = СRC32 Param1: Value1 URL ParamN: ValueN … Param1: Value1 ParamN: ValueN URL Param1: Value1 ParamN: ValueN ( ) Сhecksum
21 Определение периода повторного скачивания Модуль Parser, обрабатывая документ, каждый раз рассчитывает новый CheckSum и сравнивает с предыдущим. Если они не совпали – скачали эффективно: Подаём документ на вход Index Builder Уменьшаем срок до следующей выкачки: Refetch Delay /= K Если совпали – скачали вхолостую: Индексы не обновляем Увеличиваем срок до следующей выкачки: Refetch Delay *= K URLRefetch DelayFetch Time… Сhecksum K = 2
22 Поиск по видео: cоставные документы Для формирования документа поиска по видео ресурсам необходимо два компонента: –Страница HTML для извлечения параметров документа –Собственно видеофайл (FLV, 3GP, AVI) для генерации GIF-превью, поиска дубликатов и др. В таком случае скачивание документа происходит в два этапа. URL ChecksumLast-Modified HTML paramsVideo content
23 Fetcher Queue Поиск по видео: алгоритм #1 URL Fetcher URL HTML Parser URL params VideoURL После выяснения урла видео-контента Документ снова отправляется в очередь на выкачку
24 Fetcher Queue Поиск по видео: алгоритм #2 Fetcher Parser URL params VideoURL URL params VideoURL Video content Для более быстрого получения «полноценных» документов здесь можно реализовать очередь с приоритетами Index Builder
25 Язык реализации – Perl Каждый логический модуль работает в отдельном процессе –Возможно разнесение процессов по разным хостам –Возможна реализация параллельности по данным Процессы взаимодействуют 3 способами (с помощью IO::KQueue): –Пайпы –Сокеты –Файловые очереди Monitor – процесс, являющийся родителем для всех вышеописанных процессов, и выполняющий следующие функции: –Запуск и остановка модулей –Периодическая проверка их жизнеспособности (kill 0) и восстановление логической целостности при сбоях –Сбор статистики Seeder: запуск процессаТехнические детали текущей реализации
26 Спасибо за внимание ?
27 Дополнительно: реализация файловой очереди Алгоритм схож с алгоритмом реализации очереди с помощью двух стеков: Очередь представляет собой два изначально пустых файла – IN и OUT Операция PUSH добавляет элемент в конец файла IN Операция PULL извлекает текущий элемент из файла OUT, двигаясь от его начала к концу Если достигнут конец файла OUT, то всё содержимое файла IN переносится в OUT Элемент А INOUT Элемент B Элемент C Записываем Элемент А Элемент B Элемент C Переносим Считываем сверху вниз
Еще похожие презентации в нашем архиве:
© 2024 MyShared Inc.
All rights reserved.