title: Алекс Сюй, «System Design. Подготовка к сложному интервью» (Vol. 1, рус. изд.) — глава 9: Поисковый робот source: materials/System Design. Подготовка к сложному интервью.pdf, стр. 144–165 конспект: TASK-45.38, извлечено pymupdf 2026-09-17; ниже полный «грязный» текст главы + выжимка статус: выжимка и перенос в knowledge-base.md / methodology.md / classic-designs.md — см. _map.md

Глава 9. Поисковый робот

Выжимка

Хороший краулер: масштабируемость, устойчивость, вежливость, расширяемость. Оценки: 1 млрд страниц/мес ≈ 400 QPS (пик 800), 500 КБ/страница → 500 ТБ/мес, 5 лет ≈ 30 ПБ.

Компоненты: seed URL → граница сканирования (frontier) — очередь на загрузку → HTML-загрузчик (+DNS-резолвер) → анализатор контента → проверка «существующий контент?» (29 % страниц — дубликаты, сравнивать хеши, фильтр Блума) → извлекатель ссылок → фильтр URL (чёрные списки, расширения) → проверка «существующий URL?» → хранилище URL.

Frontier = BFS с доработками: обычный FIFO-BFS «невежлив» (все ссылки с одной страницы → один домен) и без приоритетов. Решение — две группы очередей: лицевые (front queues) — приоритет (PageRank, популярность, частота обновления); тыльные (back queues) — вежливость: домен → таблица связывания → своя FIFO → выделенный рабочий поток с задержкой между загрузками одного сервера.

Ещё: robots.txt (кэшировать, уважать Disallow); кэш DNS (10–200 мс — узкое место); гео-распределение краулеров; timeout; состояние в хранилище (рестарт после сбоя); ловушки-спайдертрапы (лимит длины URL, чёрные списки, ручное выявление по аномальному числу страниц); server-side рендеринг JS-страниц; модульность (плагины: PNG-загрузчик, веб-мониторинг).

Перенос: KB §14.4 (frontier/вежливость/robots.txt — блок «краулер»).

Полный текст (грязная выгрузка)

9 ПРОЕКТИРОВАНИЕ ПОИСКОВОГО РОБОТА В этой главе мы сосредоточимся на интересной классической задаче, которую можно встретить на интервью по проектировании ИТ-систем, — создании поискового робота. Поисковый робот еще называют веб-пауком или веб-краулером. Он широко используется в поисковых системах для обнаружения нового или обновленного контента в Сети. Это могут быть веб-страницы, изо­ бражения, видео, PDF-файлы и т. д. Сначала поисковый робот собирает несколько веб-страниц, а затем проходит по всем ссылкам, которые они содержат, чтобы собрать новый контент. Пример этого процесса показан на рис. 9.1. Поисковый робот применяется для множества разных задач.

Индексация в поисковой системе. Это самый распространенный сценарий использования. Робот собирает веб-страницы, чтобы создать локальный индекс для поисковой системы. Например, в поисковой системе Google эту роль играет Googlebot.

Веб-архивация. Это процесс сбора информации с веб-страниц для дальнейшего хранения и использования. Например, архивацией веб-сайтов занимаются многие национальные библиотеки. В каче­ стве известных примеров можно привести Библиотеку Конгресса США [1] и Веб-архив ЕС [2].

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

Проектирование поискового робота      145 www.a.com www.b.com www.c.com www.lime.com www.peach.com www.mango.com www.banana.com www.orange.com www.plum.com страница a.com страница b.com страница c.com страница lime.com страница peach.com страница mango.com страница banana.com страница orange.com страница plum.com Рис. 9.1

Веб-мониторинг. Поисковые роботы помогают отслеживать на­ рушения авторских прав и незаконное использование торговых марок в интернете. Например, Digimarc [3] таким образом ищет пиратские копии и отчеты. Сложность разработки поискового робота зависит от того, какой масштаб он должен поддерживать. Это может быть как скромный школьный про­ ект, который можно закончить за пару часов, так и гигантская система, требующая постоянного внимания со стороны целой команды инжене­ ров. Поэтому сначала нужно определиться с масштабом и функциями, которые должны поддерживаться.

146      ГЛАВА 9 ШАГ 1: ПОНЯТЬ ЗАДАЧУ И ОПРЕДЕЛИТЬ МАСШТАБ РЕШЕНИЯ Поисковый робот работает по простому принципу: 1. На вход подается список URL-адресов, после чего загружаются соответствующие веб-страницы. 2. Из веб-страниц извлекаются URL-адреса. 3. Новые URL-адреса добавляются в список для дальнейшей загрузки. Эти три шага повторяются заново. Ограничивается ли работа поискового робота этим простым алгоритмом? Не совсем. Спроектировать широкомасштабный поисковый робот очень сложно. Вряд ли кому-то удастся это сделать во время интервью. Прежде чем переходить к архитектуре, необходимо задать вопросы о требованиях и о масштабе системы. Кандидат: «Каково основное назначение поискового робота? Он ис­ пользуется для индексации в поисковой системе, сбора данных или для чего-то другого?» Интервьюер: «Для индексации в поисковой системе». Кандидат: «Сколько веб-страниц поисковый робот собирает в месяц?» Интервьюер: «1 миллиард страниц». Кандидат: «Какого рода контент мы ищем? Только HTML или другие ресурсы вроде PDF-файлов и изображений?» Интервьюер: «Только HTML». Кандидат: «Следует ли учитывать недавно добавленные или отредак­ тированные веб-страницы?» Интервьюер: «Да». Кандидат: «Нужно ли хранить собранные HTML-страницы?» Интервьюер: «Да. Срок хранения — 5 лет». Кандидат: «Что делать с веб-страницами, содержимое которых ду­ блируется?» Интервьюер: «Их следует игнорировать».

Проектирование поискового робота      147 Это лишь некоторые из тех вопросов, которые можно задать интервьюеру. Необходимо разобраться в требованиях и прояснить непонятные момен­ ты. Даже если вас попросят спроектировать такой простой продукт, как поисковый робот, у вас с интервьюером может быть разное понимание того, что он должен собой представлять. Помимо функциональности, которую нужно согласовать с интервьюером, необходимо учитывать следующие характеристики поискового робота.

Масштабируемость. Интернет огромен. В нем миллиарды веб- страниц. Поисковый робот должен быть чрезвычайно эффектив­ ным и использовать параллельные вычисления.

Устойчивость. Интернет полон ловушек. Вам постоянно будет встречаться некорректный HTML-код, неотзывчивые серверы, сбои, вредоносные ссылки и т. д. Поисковый робот должен справ­ ляться со всеми этими пограничными случаями.

Вежливость. Поисковый робот не должен отправлять веб-сайту слишком много запросов за короткий промежуток времени.

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

Предположим, что каждый месяц загружается 1 миллиард веб- страниц.

QPS: 1 000 000 000 / 30 дней / 24 часа / 3600 секунд = ~400 страниц в секунду.

Пиковый показатель QPS = 2 * QPS = 800.

Предположим, что средний размер веб-страницы составляет 500 Кб.

148      ГЛАВА 9

1 миллиард страниц * 500 Кб = 500 Тб в месяц для хранения. Если вы плохо ориентируетесь в единицах измерения данных, перечи­ тайте раздел «Степень двойки» в главе 2.

Если данные хранятся на протяжении пяти лет, 500 Тб * 12 меся­ цев * 5 лет = 30 Пб. Для контента, собранного за пять лет, нужно хранилище размером 30 Пб. ШАГ 2: ПРЕДЛОЖИТЬ ОБЩЕЕ РЕШЕНИЕ И ПОЛУЧИТЬ СОГЛАСИЕ Определившись с требованиями, мы переходим к общим архитектурным вопросам. На рис. 9.2 изображена предлагаемая архитектура, вдохновлен­ ная исследованиями [4] [5]. Исходные URL Загрузчик HTML Распознаватель DNS Анализатор контента Средство извле- чения ссылок Фильтр URL Граница сканирования Существующий URL? Хранилище контента Существующий контент? Хранилище URL Рис. 9.2 Сначала мы исследуем каждый компонент архитектуры, чтобы понять его функции, а затем шаг за шагом рассмотрим принцип работы поис­ кового робота.

Проектирование поискового робота      149 Исходные URL-адреса В процессе поиска в качестве отправной точки используются исходные URL-адреса. Например, чтобы перебрать все веб-страницы на универ­ ситетском веб-сайте, нам, очевидно, следует начать с доменного имени университета. Для обхода всего интернета нам нужно творчески подойти к выбору ис­ ходных URL-адресов. Хороший исходный URL-адрес позволит перебрать как можно большее количество ссылок. Общая стратегия — разделить пространство адресов на отдельные части. Первый предложенный подход основан на местоположении, так как популярность тех или иных веб- сайтов может зависеть от страны. Исходные URL-адреса также можно выбирать по тематике. Например, адресное пространство можно разде­ лить на покупки, спорт, медицину и т. д. Выбор исходных URL-адресов зависит от разных факторов. От вас не ожидают идеального решения. Просто размышляйте вслух. Граница сканирования Большинство современных поисковых роботов делят контент на уже за­ груженный и ожидающий загрузки. Компонент, хранящий URL-адреса, предназначенные для загрузки, называется границей сканирования. Его можно считать очередью вида «первым пришел, первым ушел». Углубленную информацию об этом компоненте можно найти в разделе, посвященном углубленному проектированию. Загрузчик HTML Этот компонент загружает веб-страницы из интернета. URL-адреса этих веб-страниц предоставляются границей сканирования. Распознаватель DNS Чтобы загрузить веб-страницу, URL сначала нужно перевести в IP-адрес. Для этого загрузчик HTML может обратиться к распознавателю DNS. Например, по состоянию на 5.3.2019 URL www.wikipedia.org преобразуется в IP-адрес 198.35.26.96.

150      ГЛАВА 9 Анализатор контента После загрузки веб-страницы ее нужно проанализировать: вдруг у нее некорректный HTML-код, который вызовет проблемы и только займет место в хранилище? Если разместить анализатор контента на одном сер­ вере с поисковым роботом, это замедлит процесс сбора данных. В связи с этим он имеет вид отдельного компонента. Существующий контент? Как показывает онлайн-исследование [6], 29 % от всех веб-страниц являются дубликатами, что может привести к повторному сохранению одного и того же контента. Мы используем структуру данных «Существующий контент?», чтобы избежать дублирования информации и сократить время обработки. Она помогает обнаруживать новый контент, который система уже сохраняла. Но это медленный подход, занимающий много времени, особенно если речь идет о миллиардах веб-страниц. Для эффективного выполнения этой задачи следует сравнивать не сами веб-страницы, а их хеши [7]. Хранилище контента Это система хранения HTML. Ее выбор зависит от таких факторов, как тип и размер данных, частота доступа, время жизни и т. д. Используется как диск, так и память.

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

Востребованный контент хранится в памяти для снижения латент­ ности. Средство извлечения ссылок Этот компонент анализирует HTML-страницы и извлекает из них ссылки. Пример этого процесса показан на рис. 9.3. Относительные пути преоб­ разуются в абсолютные URL-адреса путем добавления префикса https:// en.wikipedia.org.

Проектирование поискового робота      151 Извлеченные ссылки: https://en.wikipedia.org/wiki/Cong_Weixi https://en.wikipedia.org/wiki/Kay_Hagan https://en.wikipedia.org/wiki/Vladimir_Bukovsky https://en.wikipedia.org/wiki/John_Conyers Рис. 9.3 Фильтр URL-адресов Фильтр URL-адресов отклоняет определенные типы контента, расшире­ ния файлов, ссылки на страницы с ошибками и URL-адреса, занесенные в черный список. Существующий URL-адрес? «Существующий URL-адрес?» — это структура данных, которая отсле­ живает URL-адреса, которые уже посещались или находятся в границе сканирования. Это помогает избежать повторного открытия одного и того же URL-адреса, которое чревато повышенной нагрузкой на сервер и по­ тенциальными бесконечными циклами. Для реализации этого компонента обычно применяют такие методики, как фильтр Блума и хеш-таблица. Мы не станем в них углубляться. Дополнительную информацию можно найти в справочных материалах [4] [8].

152      ГЛАВА 9 Хранилище URL-адресов Это хранилище уже посещенных URL-адресов. Итак, мы рассмотрели каждый отдельный компонент. Теперь мы соберем их воедино и обсудим принцип работы системы в целом. Принцип работы поискового робота Чтобы как следует объяснить каждый этап рабочего процесса, мы доба­ вили на диаграмму архитектуры порядковые номера (рис. 9.4). Исходные URL Загрузчик HTML Распознаватель DNS Анализатор контента Средство извле- чения ссылок Фильтр URL Граница сканирования Существующий URL? Существующий контент? 1 5 3 4 11 6 2 9 8 7 10 Хранилище контента Хранилище URL Рис. 9.4

Шаг 1. Добавляем исходные URL-адреса в границу сканирования.

Шаг 2. Загрузчик HTML берет список URL-адресов из границы сканирования.

Проектирование поискового робота      153

Шаг 3. Загрузчик HTML получает соответствующие IP-адреса от распознавателя DNS и начинает загрузку.

Шаг 4. Анализатор контента разбирает HTML-страницы и про­ веряет их корректность.

Шаг 5. После разбора и проверки контент передается компоненту «Существующий контент?».

Шаг 6. Компонент «Существующий контент?» проверяет, есть ли данная HTML-страница в хранилище: Š Š если есть, это означает, что этот контент находится по другому URL-адресу и мы его уже обработали. В этом случае HTML- страница отклоняется; Š Š если нет, система еще не обрабатывала этот контент, поэтому он передается средству извлечения ссылок.

Шаг 7. Из HTML-страниц извлекаются ссылки.

Шаг 8. Извлеченные ссылки передаются фильтру URL-адресов.

Шаг 9. После фильтрации ссылки передаются компоненту «Суще­ ствующий URL-адрес?».

Шаг 10. Компонент «Существующий URL-адрес?» проверяет, на­ ходится ли URL в хранилище. Если да, то он уже обрабатывался и больше ничего делать не нужно.

Шаг 11. Если URL-адрес еще не обрабатывался, он добавляется в границу сканирования. ШАГ 3: ПОДРОБНОЕ ПРОЕКТИРОВАНИЕ До сих пор мы обсуждали общие аспекты архитектуры. Теперь рассмо­ трим подробно самые важные составные компоненты и характеристики:

границу сканирования;

загрузчик HTML;

устойчивость;

расширяемость;

обнаружение и отклонение проблемного контента.

154      ГЛАВА 9 DFS и BFS Интернет можно считать направленным графом, вершинами которого являются веб-страницы, а ребрами — гиперссылки (URL-адреса). Про­ цесс поиска можно рассматривать как обход направленного графа, на­ чиная с корневой вершины. Для этого существует два распространенных алгоритма: поиск в глубину (deep-first search, DFS) и поиск в ширину (breadth-first search, BFS). При этом DFS обычно является не самым удачным вариантом, так как граф может быть очень глубоким. Поисковые роботы, как правило, используют алгоритм BFS, который реализуется с помощью очереди FIFO. URL-адреса достаются из очереди в том порядке, в котором они добавлялись. Но у этой реализации есть две проблемы.

Большинство ссылок, размещенных на одной веб-странице, ука­ зывают на один и тот же сетевой узел. На рис. 9.5 все ссылки на странице внутренние, из-за чего поисковый робот вынужден . . . wikipedia.com wikipedia.com/page1 wikipedia.com/page2 wikipedia.com/pageN wikipedia.com/page1/1 wikipedia.com/pageN/N wikipedia.com/pageN/1 wikipedia.com/page1/2 wikipedia.com/pageN/2 wikipedia.com/page2/1 wikipedia.com/page2/2 . . . Рис. 9.5

Проектирование поискового робота      155 обрабатывать URL-адреса в одном домене (wikipedia.com). Если он попытается загрузить веб-страницы параллельно, серверы Вики­ педии будут завалены запросами. Это «невежливо».

Стандартная версия BFS не учитывает приоритет URL-адреса. В интернете миллиарды веб-страниц, и не все они имеют одинако­ вый уровень качества и значимости. Поэтому приоритет обработки URL-адресов может зависеть от их рейтинга, популярности, часто­ ты обновления и т. д. Граница сканирования Эти проблемы помогает решить граница сканирования. Это структура данных, хранящая URL-адреса, которые нужно загрузить. Она играет важную роль в соблюдении вежливости, расстановке приоритетов и обеспечении актуальности страниц. Несколько исследований, по­ священных границе сканирования и заслуживающих вашего внимания, упоминается в справочных материалах [5][9]. Их результаты приво­ дятся ниже. Вежливость В целом поисковый робот не должен отправлять серверу слишком много запросов за короткий промежуток времени. Такое поведение считается невежливым и даже может быть воспринято как DoS-атака. Например, если не предусмотреть никаких ограничений, поисковый робот может отправлять одному и тому же веб-сайту тысячи запросов в секунду и тем самым перегрузит серверы. Основная идея соблюдения вежливости заключается в последовательной загрузке страниц с одного сервера. Между загрузками можно сделать задержку. Чтобы это реализовать, доменные имена веб-сайтов нужно привязывать к потокам (рабочим узлам) загрузки. У каждого потока-за­ грузчика есть отдельная очередь FIFO, и все URL-адреса он достает из нее. На рис. 9.6 показан механизм, который делает наш поисковый робот вежливым.

Маршрутизатор очереди. Следит за тем, чтобы каждая очередь (b1, b2, … bn) содержала URL-адреса только с одним доменным именем.

Таблица связывания. Привязывает каждое доменное имя к очереди.

156      ГЛАВА 9 Таблица связывания Маршрутизатор очередей Селектор очередей . . . . . . b1 b2 bn Рабочий поток N Рабочий поток 2 Рабочий поток 1 Рис. 9.6 Таблица 9.1 Доменное имя Очередь wikipedia.com b1 apple.com b2 … … nike.com bn

Очереди FIFO b1, b2, …, bn. Каждая очередь содержит URL-адреса только с одним доменным именем.

Селектор очередей. Каждый рабочий поток привязан к очереди FIFO, и все URL-адреса загружает только из нее. За логику выбора подходящей очереди отвечает селектор очередей.

Проектирование поискового робота      157

Рабочие потоки от 1 до N. Рабочий поток последовательно загру­ жает веб-страницы из одного и того же сервера. Между загрузками можно предусмотреть задержку. Приоритет Случайное сообщение на форуме, посвященном продукции Apple, по своей значимости отличается от сообщений, опубликованных на офици­ альном сайте этой компании. Несмотря на общее для них ключевое слово Apple, поисковому роботу лучше начинать с последнего. Мы назначаем URL-адресам приоритеты в зависимости от их ценности. При этом можно учитывать PageRank [10], популярность веб-сайта, часто­ ту обновления и т. д. За это отвечает средство расстановки приоритетов. Более детальную информацию на эту тему можно найти в справочных материалах [5] [10]. Механизм, назначающий приоритеты URL-адресам, показан на рис. 9.7. f1 fn f2 Селектор очередей Средство расстановки приоритетов Входной URL Выходной URL . . . Рис. 9.7

158      ГЛАВА 9

Средство расстановки приоритетов. Принимает на вход URL- адреса и вычисляет их приоритеты.

Очереди с f1 по fn. Каждой очереди назначается приоритет. Чем выше приоритет, тем больше вероятность того, что очередь будет выбрана.

Селектор очередей. Выбирает произвольную очередь, отдавая пред­ почтение очередям с повышенным приоритетом. На рис. 9.8 показано, как устроена граница сканирования. Она состоит из двух модулей:

лицевые очереди: отвечают за расстановку приоритетов;

тыльные очереди: отвечают за соблюдение вежливости. Актуальность Веб-страницы постоянно добавляются, удаляются и редактируются. По­ исковый робот должен периодически проходиться по уже загруженным веб-страницам, чтобы поддерживать набор данных в актуальном состо­ янии. Для повторного перебора всех URL-адресов нужно много времени и ресурсов. Существует две стратегии оптимизации этого процесса:

учитывать историю обновлений веб-страниц;

назначать URL-адресам приоритеты, чтобы в первую очередь (и чаще) загружать важные страницы. Хранилище для границы сканирования В настоящих поисковых системах количество URL-адресов на границе сканирования может достигать сотен миллионов [4]. Хранение всего этого в памяти плохо сказывается как на надежности, так и на масштабируемо­ сти. На диске тоже лучше не хранить все подряд, так как он медленный и легко может стать узким местом поискового робота. Мы выбрали гибридный поход. Большая часть URL-адресов находится на диске, поэтому размер хранилища не составляет проблемы. Чтобы избежать накладных расходов, связанных с чтением и записью на диск, мы храним в памяти буфер для добавления/удаления данных из очереди. Содержимое буфера периодически сбрасывается на диск.

Проектирование поискового робота      159 f1 fn f2 Селектор лицевых очередей Средство расстановки приоритетов Входной URL Выходной URL Таблица связывания Маршрутизатор тыльных очередей b1 b2 bn . . . . . . Рабочий поток 1 Рабочий поток 2 Рабочий поток 3 . . . Селектор тыль- ных очередей Рис. 9.8

160      ГЛАВА 9 Загрузчик HTML Этот компонент загружает веб-страницы из интернета по протоколу HTTP. Прежде чем его обсуждать, рассмотрим стандарт исключений для роботов. Robots.txt Файл robots.txt (так называемый стандарт исключений для роботов) позво­ ляет веб-сайтам взаимодействовать с поисковыми системами. В нем мож­ но указать страницы, которые позволено загружать поисковым роботам. Прежде чем начинать обход веб-сайта, поисковый робот должен сначала проверить соответствующий файл robots.txt и следовать его правилам. Чтобы не загружать robots.txt повторно, мы кэшируем его содержимое. Файл периодически загружается и сохраняется в кэш. Вот фрагмент, взятый из https://www.amazon.com/robots.txt. Некоторые директории, такие как creatorhub, закрыты для робота Google. User-agent: Googlebot Disallow: /creatorhub/ Disallow: /rss/people//reviews Disallow: /gp/pdp/rss/*/reviews Disallow: /gp/cdp/member-reviews/ Disallow: /gp/aw/c r/ Еще одним важным аспектом загрузчика HTML является оптимизация производительности, речь о которой пойдет дальше. Оптимизация производительности Ниже перечислены оптимизации загрузчика HTML. 1. Распределенный поиск. Для обеспечения высокой производи­ тельности процесс поиска должен быть распределен по разным серверам, каждый из которых работает в  несколько потоков. Адресное пространство делится на части, чтобы каждый загруз­ чик отвечал за отдельное подмножество URL-адресов. Пример распределенного поиска показан на рис. 9.9. 2. Кэширующий распознаватель DNS. Распознаватель DNS явля­ ется узким местом поискового робота, так как многие интерфейсы DNS синхронны по своей природе, и DNS-запросы могут занимать какое-то время. Время DNS-ответа варьируется от 10 мс до 200 мс. Когда поток поискового робота обращается к DNS-серверу, другие

Проектирование поискового робота      161 Граница сканирования ... распределение URL распределение URL распределение URL Загрузчики HTML Рис. 9.9 потоки блокируются, пока не завершится первый запрос. В качестве эффективного метода повышения скорости, который позволит из­ бежать частого обращения к DNS, можно использовать кэш DNS. Наш кэш хранит соответствия между доменными именами и IP- адресами и периодически обновляется с помощью заданий cron. 3. Локальность. Распределите серверы поискового робота географиче­ ски. Чем ближе они к серверам веб-сайта, тем короче время загрузки. Локальность относится к большинству компонентов системы: сер­ верам поискового робота, кэшу, очереди, хранилищу и т. д. 4. Короткое время ожидания. Некоторые серверы отвечают мед­ ленно или вовсе не отвечают. Чтобы не ждать их слишком долго, указывается максимальное время ожидания. Если сервер не ответит в отведенный промежуток времени, поисковый робот остановит задание и попробует загрузить какие-то другие страницы. Устойчивость Наряду с оптимизацией производительности важную роль играет устой­ чивость. Вот несколько подходов к улучшению устойчивости системы.

Согласованное хеширование. Оно помогает распределить нагруз­ ку между загрузчиками и позволяет добавлять и удалять серверы загрузки. Подробнее об этом — в главе 5 «Согласованное хеширо­ вание».

162      ГЛАВА 9

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

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

Проверка корректности данных. Это важная мера для предотвра­ щения системных ошибок. Расширяемость Почти всегда по мере развития системы разработчики стремятся сделать ее гибкой и обеспечить поддержку новых типов контента. Поисковый робот можно расширить за счет подключения новых модулей. На рис. 9.10 показано, как это делается. Исходные URL Загрузчик HTML Распознаватель DNS Анализатор контента Средство извле- чения ссылок Фильтр URL Граница сканирования Существующий URL? Существующий контент? Загрузчик PNG Веб- мониторинг Дополнительный модуль Хранилище контента Хранилище URL Рис. 9.10

Проектирование поискового робота      163

Загрузчик PNG — это подключаемый модуль для загрузки PNG- файлов.

Модуль веб-мониторинга подключается для отслеживания и пре­ дотвращения нарушений авторских прав и незаконного использо­ вания товарных знаков в интернете. Обнаружение и отклонение проблемного контента В этом разделе обсуждается обнаружение и предотвращение загрузки лишнего, бессмысленного или вредоносного контента. 1. Лишний контент. Как говорилось выше, около 30 % всех страниц являются дубликатами. Для их обнаружения можно использовать хеши или контрольные суммы [11]. 2. Ловушки. Речь идет о веб-страницах, которые заставляют поиско­ вого робота входить в бесконечный цикл. Например, вот ссылка на бесконечно глубокую структуру директорий: www.spidertrapexample. com/foo/bar/foo/bar/foo/bar/…. Таких ловушек можно избежать, если установить максимальную длину URL-адресов. Но вообще, для их обнаружения не существует какого-то универсального метода. Веб-сайты с ловушками можно легко определить по необычно большому количеству страниц, которые они содержат. Сложно написать алгоритм, который будет автоматически избегать таких ловушек; это можно сделать вруч­ ную, а затем либо занести соответствующие веб-сайты в черный список, либо применить собственные фильтры для URL-адресов. 3. Бессмысленные данные. Некоторый контент несет в себе мало смысла, а порой его нет вообще. Это относится к рекламе, листингам кода, спаму и т. д. Такой контент бесполезен для поисковых роботов, и его по возможности следует отклонять. ШАГ 4: ПОДВЕДЕНИЕ ИТОГОВ Мы начали эту главу с обсуждения характеристик хорошего поискового робота — масштабируемости, вежливости, расширяемости и устойчи­ вости. Затем мы предложили вариант архитектуры и рассмотрели ее

164      ГЛАВА 9 ключевые компоненты. Создание масштабируемого поискового робота — нетривиальная задача, ведь интернет огромен и полон ловушек. И хотя нам удалось охватить множество аспектов, без внимания осталось еще много важного.

Генерация страниц на стороне сервера. Многие веб-сайты гене­ рируют ссылки на лету, используя JavaScript, AJAX и т. д. Если мы будем загружать и разбирать веб-страницы напрямую, нам не удастся извлечь динамически сгенерированные ссылки. Чтобы решить эту проблему, перед разбором веб-страницы мы генерируем ее на сервере [12].

Фильтрация нежелательных страниц. Поскольку емкость храни­ лища и ресурсы поискового робота ограничены, будет полезно использовать компонент для борьбы со спамом, который будет фильтровать низкокачественные и рекламные страницы [13] [14].

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

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

Доступность, согласованность и надежность. Это ключевые харак­ теристики успеха любой крупной системы. Мы подробно обсудили их в главе 1.

Аналитика. Сбор и анализ данных — важная часть системы и клю­ чевой элемент ее оптимизации. Поздравляем, вы проделали длинный путь и можете гордиться собой. Отличная работа! СПРАВОЧНЫЕ МАТЕРИАЛЫ [1]  Библиотека Конгресса США: https://www.loc.gov/websites/ [2]  Веб-архив ЕС: http://data.europa.eu/webarchive [3]  Digimarc: https://www.digimarc.com/products/digimarc-services/piracy- intelligence

Проектирование поискового робота      165 [4]  Heydon A., Najork M. Mercator: A scalable, extensible web crawler World Wide Web, 2 (4) (1999), pp. 219-229 [5]  By Christopher Olston, Marc Najork: Web Crawling. http://infolab.stanford. edu/~olston/publications/crawling_survey.pdf [6]  29% Of Sites Face Duplicate Content Issues: https://tinyurl.com/y6tmh55y [7]  Rabin M.O., et al. Fingerprinting by random polynomials Center for Research in Computing Techn., Aiken Computation Laboratory, Univ. (1981) [8]  B. H. Bloom, “Space/time trade-offs in hash coding with allowable errors,” Communications of the ACM, vol. 13, no. 7, pp. 422–426, 1970. [9]  Donald J. Patterson, Web Crawling: https://www.ics.uci.edu/~lopes/teaching/ cs221W12/slides/Lecture05.pdf [10]  L. Page, S. Brin, R. Motwani, and T. Winograd, “The PageRank citation ranking: Bringing order to the web,” Technical Report, Stanford University, 1998. [11]  Burton Bloom. Space/time trade-offs in hash coding with allowable errors. Communications of the ACM, 13(7), pages 422–426, July 1970. [12]  Google Dynamic Rendering: https://developers.google.com/search/docs/ guides/dynamic-rendering [13]  T. Urvoy, T. Lavergne, and P. Filoche, “Tracking web spam with hidden style similarity,” in Proceedings of the 2nd International Workshop on Adversarial Information Retrieval on the Web, 2006. [14]  H.-T. Lee, D. Leonard, X. Wang, and D. Loguinov, “IRLbot: Scaling to 6 billion pages and beyond,” in Proceedings of the 17th International World Wide Web Conference, 2008.