Спроектируйте веб-краулер

Требования

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

Функциональные

• Стартовать с набора сидов URL и открывать достижимый веб, идя по ссылкам.
• Фетчить каждую страницу, извлекать ссылки и отдавать контент потребителям ниже (индексатор, архиватор).
• Уважать robots.txt и директивы crawl-delay — не обсуждается.
• Дедуплицировать: никогда не перефетчить URL без нужды и обнаруживать, когда два URL возвращают одинаковый контент.
• Перекраулить ради свежести: возвращаться к страницам, чтобы индекс не устаревал.

Нефункциональные

• Вежливость — жёсткое ограничение, а не любезность. Никогда не перегружать один хост; краулер, делающий DDoS сайтам, банится и плохой гражданин.
• Огромный масштаб. Миллиарды страниц, поэтому дизайн распределён по многим машинам с первого дня.
• Устойчивость. Веб враждебен — кривой HTML, циклы редиректов, бесконечные пространства URL, медленные серверы, ловушки-пауки. Краулер обязан пережить всё это, не зависая и не зацикливаясь.
• Расширяемость. Новые типы контента и потребители подключаются без переписывания.

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

Оценка

• Цель — 1 миллиард страниц/месяц. Это 10^9 / (30 × 10^5 с) ≈ ~400 страниц/с устойчиво — но реальное число выше, ведь большая часть времени фетча — это ожидание сети, так что темп задаёт конкурентность, а не CPU.
• Средняя страница ~100 КБ HTML → 10^9 × 100 КБ = ~100 ТБ/месяц сырого фетченного контента до дедупа. Доминируют хранение и пропускная способность, не вычисления.
• Бухгалтерия URL: чтобы обойти миллиард страниц, нужно помнить десятки миллиардов виденных URL, чтобы не перефетчить. По ~100 байт/URL точное множество seen из 10 миллиардов URL — это ~1 ТБ RAM — слишком дорого держать точно в памяти, что и есть вся мотивация bloom filter (несколько бит на URL вместо 100 байт).
• DNS: каждый фетч нуждается в разрешении имени хоста; при ~400 страниц/с без кеширования DNS становится синхронным узким местом — так что локальный резолвер/кеш обязателен, не опционален.

Число бухгалтерии и есть драйвер дизайна: нельзя позволить себе помнить каждый URL точно, поэтому дедуп вероятностный, и один этот факт формирует архитектуру.

Высокоуровневый дизайн

URL frontier держит URL для обхода, упорядоченные ради вежливости и приоритета. Воркеры тянут из frontier, разрешают DNS, фетчат страницу (после проверки robots.txt), проверяют контент на дублирование, хранят его, извлекают новые ссылки, фильтруют их против множества seen и подают выживших обратно в frontier.

Глубокое погружение

URL frontier и вежливость

Frontier — не простая FIFO-очередь, это движок вежливости, и ошибка в нём — то, что делает DDoS сайту. Настоящий frontier (дизайн Mercator) двухступенчатый:

• Передние очереди — приоритет. Входящие URL сортируются по очередям по приоритету (важность, нужда свежести), так что ценные страницы обходятся раньше. Приоритизатор выбирает, из какой передней очереди тянуть.
• Задние очереди — вежливость. Каждая задняя очередь привязана к ровно одному хосту, а роутер гарантирует, что две задние очереди не обслуживают один хост. Воркеру назначены задняя очередь и временная метка, когда он может снова стукнуться к этому хосту; он спит, пока не истёк crawl-delay хоста (из robots.txt или дефолт). Это и обеспечивает «не более одного запроса к хосту X каждые N секунд» независимо от того, сколько URL этого хоста ждут.

Так frontier одновременно говорит обходи важное первым (передние очереди) и никогда не задалбливай один хост (задние очереди) — две цели, которым одна очередь служить не может. Вежливость — на хост, а не на IP или на краулер, потому что один медленный сервер за одним именем хоста и есть то, что надо защитить.

Дедуп: bloom filter для URL, хеш контента для страниц

Есть две разные задачи дедупа, и им нужны два разных инструмента.

Видел ли я этот URL? При десятках миллиардов URL точное множество в памяти — это ~1 ТБ — неподъёмно. Bloom filter отвечает «видел ли я этот URL?» за несколько бит на URL без ложно-отрицательных (если говорит не видел — точно новый) и с настраиваемой долей ложно-положительных (изредка может сказать видел, когда нет, безвредно пропустив реально новый URL). Для краулера эта асимметрия идеальна: цена ложно-положительного — одна необойдённая страница из миллиардов; цена точного множества — терабайт RAM. (Пререквизит про bloom filter разбирает механику битового массива; здесь это трюк памяти, делающий дедуп веб-масштаба возможным.)

Видел ли я этот контент? Два разных URL часто возвращают одинаковые байты — http против https, трекинг-параметры ?utm=..., зеркала, версии для печати. Дедуп URL это не ловит, ведь URL различаются. Поэтому ты также хешируешь контент (например MD5/SHA нормализованного тела или SimHash для почти-дублей) и пропускаешь хранение страницы, чей хеш контента уже видел. Дедуп URL не даёт пере-фетчить; дедуп контента не даёт пере-хранить и пере-индексировать один текст, достижимый многими путями.

Ловушки, свежесть и перекраул

Ловушки — это календарь из хука: страницы, порождающие бесконечные постоянно меняющиеся URL (session ID в пути, ?page=1,2,3… до бесконечности, глубокие динамические фасеты). Наивный краулер считает каждую новой и зацикливается. Защиты: ограничить глубину обхода на хост, ограничить URL на хост, обнаруживать паттерны URL, что взрываются, и опираться на хеш контента (страницы ловушки часто почти идентичны, так что проверка хеша контента отсеивает их, даже когда URL различаются). Правила robots.txt Disallow тоже отгораживают многие склонные к ловушкам пути.

Свежесть — обратная задача: веб меняется, поэтому обход никогда не «завершён». Страницы надо перекраулить, но не равномерно — главная новостей меняется ежечасно, архивный PDF — никогда. Поэтому приоритет перекраула задаётся оценкой темпа изменений на страницу: отслеживай, как часто хеш контента страницы реально менялся в прошлых обходах, и планируй волатильные часто, а статичные редко. Это делает frontier непрерывной системой (URL добавляются обратно по графику свежести), а не одноразовым сливом.

Узкие места и компромиссы

• Масштаб и баланс frontier. При миллиардах URL frontier не влезает на одну машину; он партиционируется (часто по хешу хоста) по узлам — но тогда один гигантский хост (огромный сайт) может перегрузить свою партицию, пока другие простаивают. Балансировка назначения хост-к-партиции — реальная операционная проблема.
• DNS как скрытое узкое место. Синхронный DNS при сотнях запросов/с тормозит фетчеры; локальный кеширующий резолвер обязателен, и даже тогда наплыв новых хостов может его насытить.
• Вежливость против пропускной способности. Строгие лимиты на хост ограничивают, как быстро можно обходить один большой сайт — так что суммарная пропускная способность идёт от обхода многих хостов параллельно, а не одного быстро. Краулер, застрявший за несколькими мега-хостами, недорабатывает даже при запасе мощности.
• Ложно-положительные дедупа и нормализация контента. Bloom filter изредка отбрасывает реальный новый URL (настрой размер под приемлемую долю); хеш контента без нормализации считает страницы с ротирующим контентом бесконечно новыми, инвертируя дедуп в пустую работу — обе ручки корректность-против-цены, а не бесплатные победы.