Средний

13 мин

185

Привет! Продолжаю разбирать классические задачи с System Design интервью на стримах (за анонсами можете следить тут), а это текстовая версия стрима. В прошлый раз была бесконечная лента, сегодня очередная классика жанра - веб-краулер. Условие звучит примерно так:

Спроектировать веб-краулер, который обходит интернет, вытаскивает со страниц текст и складывает его в хранилище. На этом тексте потом будут обучать LLM (условный ChatGPT). На весь обход даётся 5 дней - данные нужны быстро. Масштаб: ~10 млрд страниц, средняя страница весит ~2 МБ. В ресурсах мы не ограничены (в разумных пределах).

Сразу договоримся о границах. Обучение модели, токенизация и прочий ML - не наша забота. Наша работа заканчивается ровно в тот момент, когда текст лёг в хранилище, дальше его забирает ML-команда, и пусть у неё голова болит.

Этапы

Повторю мысль из прошлой статьи: в System Design нет единственно правильного ответа, и оценивают на интервью не финальную картинку, а то, как вы рассуждаете. Но чтобы не зависнуть перед пустым вайтбордом, полезно держать в голове скелет из этапов:

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

2. Сущности. Перечисляем, вокруг чего всё крутится. Полную схему БД рисовать рано - мы её на этом этапе обычно и не знаем, так что честно говорим интервьюеру, что вернёмся и допишем по ходу.

3. Интерфейс. В обычном продукте здесь были бы REST-ручки. Но краулер - не пользовательское приложение, API у него нет, поэтому просто фиксируем, что подаём на вход и что получаем на выходе.

4. Поток данных. Для пользовательских систем этот шаг я пропускаю, а вот для инфраструктурных штук вроде краулера он сильно выручает: расписываем по шагам, как данные идут через систему. Именно этот список потом ляжет в основу архитектуры.

5. Архитектура. Идём к вайтборду и собираем простейшую систему, которая закрывает функциональные требования. Не больше - на этом этапе схема должна быть максимально тупой и прямолинейной.

6. Доработка под нефункциональные требования. Самый интересный и долгий этап. Берём нашу простую схему и по одному прогоняем через неё нефункциональные требования - отказоустойчивость, вежливость, масштаб, эффективность, - пока система не начнёт удовлетворять им всем.

Сбор требований

Что вообще такое веб-краулер

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

Кстати, если на интервью вам говорят "спроектируй краулер", первый вопрос, который стоит задать, - а зачем он. Краулер для поискового индекса и краулер для разового сбора текста под LLM - это две очень разные системы, и дизайн будет разным.

Функциональные требования

Тут коротко:

• обойти весь веб, стартуя с набора seed URL (стартовых ссылок);

• извлечь со страниц текст;

• сложить его в хранилище.

Нефункциональные требования

А вот здесь начинается мясо. Прежде чем их выписывать, я бы уточнил у интервьюера масштаб: сколько всего страниц и сколько весит средняя. Допустим, нам ответили (или мы прикинули сами): 10 млрд страниц по ~2 МБ. Плюс жёсткий дедлайн - 5 дней на весь обход. Отсюда:

• Отказоустойчивость. Интернет - грязное место: сайты лежат, отдают 500-е, таймаутят. Сбои надо переживать, не теряя прогресс. Упасть на середине обхода и начать заново было бы обидно.

• Вежливость (politeness). Уважаем robots.txt и не дудосим чужие сайты. Это базовая гигиена, иначе нас просто забанят.

• Масштабируемость. 10 млрд страниц сами себя не обойдут.

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

И ещё одно, пока не ушли дальше. Во многих гайдах на этом месте советуют сразу садиться за back-of-the-envelope расчёты. Я обычно здесь их не делаю, и вот почему. Кандидат добросовестно перемножает RPS, объёмы и DAU, в конце говорит "ого, дофига" - и продолжает как ни в чём не бывало. Я как интервьюер из этого узнаю только то, что человек умеет умножать. А кандидат не узнаёт про свою систему вообще ничего нового: что она распределённая, было понятно и так. Считать имеет смысл тогда, когда расчёт реально влияет на решение. Дальше будет ровно такой момент - там и посчитаем.

Сущности

Какие сущности крутятся в системе:

• текстовые данные - наш выход;

• URL и его метаданные - сам адрес плюс информация о том, скачали мы его или нет, где лежит сырой HTML и так далее;

• домен и его метаданные - потому что правила из robots.txt живут на уровне домена, а не отдельного URL.

Полную схему расписывать рано, но модель примерно такая (пишу на Go, по привычке):

type URLMeta struct {
    URL         string    `json:"url" db:"url"`                   // первичный ключ
    HTMLPath    string    `json:"html_path" db:"html_path"`       // ссылка на сырой HTML в S3
    ContentHash string    `json:"content_hash" db:"content_hash"` // хэш содержимого
    Depth       int       `json:"depth" db:"depth"`               // глубина обхода
    LastCrawled time.Time `json:"last_crawled" db:"last_crawled"`
}

type DomainMeta struct {
    Domain      string    `json:"domain" db:"domain"`
    LastCrawled time.Time `json:"last_crawled" db:"last_crawled"`
    Disallow    []string  `json:"disallow" db:"disallow"`       // запрещённые пути из robots.txt
    CrawlDelay  int       `json:"crawl_delay" db:"crawl_delay"` // задержка между запросами, сек
}

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

Интерфейс

Раз пользовательского API нет, просто фиксируем границы системы. На входе - набор seed URL с метаданными. На выходе - текст со всех обойдённых страниц, лежащий в хранилище. Этого достаточно, чтобы зафиксировать, что система ест и что отдаёт.

Поток данных

А вот это самая полезная часть подготовки. Распишем по шагам, что краулер вообще делает, начиная с одного seed URL:

1. Берём URL из frontier и резолвим его IP через DNS. (Frontier - это множество URL, которые ещё предстоит обойти. В самом начале это просто наши seed-урлы.)

2. Скачиваем HTML страницы.

3. Извлекаем из HTML текст.

4. Сохраняем текст в хранилище.

5. Вытаскиваем из страницы ссылки и добавляем их во frontier.

6. Повторяем шаги 1-5, пока frontier не опустеет.

Список нарочно высокоуровневый - это скелет, на который мы сейчас навесим архитектуру. Деталей станет в разы больше, когда полезем в нефункциональные требования, но именно этот простой список разблокирует нас и ведёт к вайтборду.

Архитектура

Берём поток данных и в лоб собираем под него систему.

Первым делом нужна очередь, назовём её frontier-очередью. Kafka это будет или SQS - решим чуть позже, пока непринципиально. В начале в ней лежат seed-урлы.

Дальше ставим воркер-краулер, который читает из этой очереди. Он забирает URL, идёт в DNS за IP, скачивает страницу, извлекает текст и ссылки. Текст кладёт в хранилище - и тут выбор очевидный: это статичные бинарные данные огромного объёма, берём объектное хранилище S3 (объёмы посчитаем ниже, но и без расчётов понятно, что 10 млрд страниц в реляционку мы пихать не будем). А извлечённые ссылки воркер просто возвращает обратно во frontier-очередь. И так по кругу. DNS и сами сайты - внешние для нас системы, всё остальное наше.

Базовая архитектура: frontier-очередь, воркер-краулер, поход в DNS и за HTML, запись в S3 и возврат ссылок в очередь.

Выглядит подозрительно просто, да? Так и должно быть. Эта схема закрывает функциональные требования, и на этом её роль заканчивается. Дальше начинается самое интересное - будем эволюционировать её под нефункциональные.

Расчеты

Прежде чем лезть в deep dives, прикинем порядки. Главный расчёт - сколько нужно машин, чтобы уложиться в 5 дней, - я отложу до этапа масштабирования. Не из лени: систему мы ещё не достроили, и узкое место может оказаться вовсе не там, где кажется. Сначала собираем всё целиком, масштабируем в конце.

А вот объём хранилища посчитать можно прямо сейчас: сырой HTML - это 10 млрд × 2 МБ = 20 ПБ. Двадцать петабайт - это много, но для S3 это вообще не проблема: оно ровно для такого и сделано, масштабируется бесконечно, а за надёжность хранения уже подумал Безос. Текста после очистки от разметки останется в разы меньше, но и он будет измеряться петабайтами. Вывод один - только объектное хранилище, никаких баз.

Заметьте: этот расчёт сразу закрыл вопрос с типом хранилища. Ровно так математика и должна работать на интервью - не ради красивых чисел, а чтобы принять конкретное решение.

Доработка под нефункциональные требования

Дальше идём по требованиям по очереди. Небольшая ремарка про уровни: на мидле от вас ждут в основном ширину - нормально, если узкие места подсказывает интервьюер, а вы грамотно их закрываете. На стаффе наоборот: вы сами уверенно идёте по требованиям и в трёх-четырёх местах ныряете глубоко. Я по ходу буду отмечать, где именно эти места для глубины.

Отказоустойчивость

Посмотрим на наш воркер. Он делает слишком много всего сразу: читает из очереди, резолвит DNS, качает страницу, парсит текст, достаёт ссылки. Падает любой из шагов - теряем прогресс по всем остальным. Масштабировать эти задачи независимо тоже не получается, а наблюдаемость никакая: непонятно даже, на каком этапе мы находимся.

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

• Фаза 1 - Crawler. Только скачать HTML. Самый ненадёжный шаг во всём процессе - это поход на чужой сайт: он лежит, тормозит, рейт-лимитит. Вот пусть воркер и занимается только этим: скачал HTML, положил в S3, обновил метаданные - всё, тяжёлая часть позади.

• Фаза 2 - Parser. Из уже сохранённого HTML спокойно достаём текст и ссылки. Эту фазу можно ретраить сколько угодно, не дёргая чужие серверы.

Между фазами ставим вторую очередь - parsing-очередь.

Двухфазный пайплайн: Crawler складывает сырой HTML в S3 и кладёт указатель в parsing-очередь, Parser достаёт HTML, парсит текст и возвращает ссылки во frontier.

Тут возникает резонный вопрос: а почему бы не положить сам HTML прямо в очередь, чтобы парсер забирал его оттуда? Потому что очереди не для этого. Kafka по умолчанию держит сообщения до 1 МБ (настраивается, конечно, но наши страницы по 2 МБ), да и вообще payload в очереди принято минимизировать. Большие данные - работа для блоб-стораджа. Поэтому паттерн стандартный: в очередь кладём указатель на S3 (простенький JSON с URL и ссылкой на файл), а парсер по нему одним запросом достаёт HTML.

У разбиения на фазы есть и приятный бонус - устойчивость к смене требований. Представьте, приходит ML-команда: "текст отличный, но нам нужен ещё alt-текст у картинок и распознанный текст с изображений". Был бы у нас монолитный воркер - пришлось бы заново обходить весь интернет. А так просто перезаливаем все URL в parsing-очередь, обновляем логику парсера и прогоняем заново. Никакого повторного дорогого краулинга.

Теперь ретраи. Что делать, если страница не скачалась? Очевидный плохой вариант - поставить in-memory таймер в воркере и через 5-10 секунд попробовать снова. Плохой по двум причинам: упадёт воркер - таймер потеряем, да и лежащий сайт за 5 секунд вряд ли оживёт.

Нужен нормальный exponential backoff, и здесь интересная развилка для глубины. В Kafka ретраев из коробки нет: пришлось бы городить отдельный топик для зафейленных URL и самим класть в сообщение время следующей попытки. Рабочее решение, но грязноватое. А в SQS ретраи с настраиваемым backoff есть из коробки - через visibility timeout, период, на который сообщение становится невидимым для других консьюмеров после того, как его кто-то забрал. По умолчанию это 30 секунд, и после каждой неудачной попытки он растёт экспоненциально: 30 секунд → 2 минуты → 5 минут → и так далее. Руками ничего реализовывать не надо, всё настраивается конфигом. За такую прагматичность я и люблю SQS, его в этом дизайне и берём.

Бесконечно ретраить тоже глупо: возможно, сайт умер насовсем. Ставим лимит попыток (в SQS это approximate receive count, например 5), после чего сообщение автоматически уезжает в Dead Letter Queue - специальную очередь для того, что обработать не удалось. Это почти наверняка мёртвые URL, и что с ними делать дальше - вопрос уже к продуктовой команде.

Знать разницу очередей на таком уровне для интервью не обязательно, но это ровно одно из мест, где можно блеснуть. Не знаете - достаточно сказать, что in-memory таймер не подойдёт и нужен exponential backoff, и предложить тот самый вариант с отдельным топиком. На любом уровне это нормальный ответ.

И ещё про падения. Что, если упадёт сам воркер? Поднимаем новый, ничего страшного: URL остаётся в очереди, пока мы не подтвердим, что HTML реально лёг в S3. Механика разная по очередям, и это тоже место для глубины. В Kafka каждое сообщение помечено offset'ом, а воркеры состоят в одной consumer group - это гарантирует, что сообщение прочитает только один из них. Обработал успешно - закоммитил offset, остальные за это сообщение уже не возьмутся (физически сообщения удаляются по retention policy, по умолчанию через 7 дней). В SQS сообщение лежит, пока его явно не удалят: воркер забрал - сработал visibility timeout, остальные его не видят; успел сохранить HTML - послал команду на удаление; упал - таймаут истёк, сообщение снова видимо, его подберёт другой воркер.

Вежливость

Начнём с примера. robots.txt - это файл на сервере сайта, который задаёт правила обхода по домену:

User-agent: *
Disallow: /private
Crawl-delay: 10

User-agent: * - правила для всех краулеров. Disallow - пути, которые трогать нельзя. Crawl-delay: 10 - между двумя запросами к этому домену надо ждать 10 секунд (это много, но бывает).

Значит, при первом обращении к домену тянем его robots.txt и складываем правила в DomainMeta, а дальше просто смотрим в эту таблицу. Алгоритм на каждый URL такой: сначала проверяем, разрешён ли путь вообще - если нет, подтверждаем сообщение и убираем его из очереди (в Kafka двигаем offset, в SQS явно удаляем). Потом смотрим на LastCrawled и CrawlDelay: если с прошлого захода прошло меньше, чем положено, нам ещё рано - возвращаем URL в очередь, выставив visibility timeout равным crawl-delay, и ждём положенное.

robots.txt со временем меняется, так что неплохо повесить на него TTL и периодически перечитывать, а сами правила закэшировать в Redis, чтобы не дёргать таблицу на каждый чих. Хотя, честно говоря, мы тут всё равно упёрты в скорость скачивания страниц, так что это скорее приятная мелочь.

Дальше - общий rate limiting. Даже если crawl-delay не задан (а его не задаёт почти никто), индустриальный стандарт - не больше одного запроса в секунду на домен. Ставим рейт-лимитер: тот же Redis со sliding window на каждый домен, считаем запросы за последнюю секунду и не превышаем. Не прошли по лимиту - возвращаем URL в очередь с visibility timeout.

Тут есть важная деталь - jitter, случайная добавка ко времени. Без неё легко словить такую картину: десять воркеров упёрлись в рейт-лимит одного домена, все вернули URL в очередь, все одновременно забрали их снова, опять упёрлись - и так по кругу. Добавляем рандом, и эта синхронность рассасывается.

И ещё одна проблема, потоньше. Когда парсим страницу, велик шанс, что куча ссылок на ней - с того же домена. Кидаем их в очередь, получаем бэклог из условных 200 URL одного домена, воркеры их разбирают, все упираются в crawl-delay, все возвращают обратно - такты жгутся впустую. Решение, которое любят приносить сеньоры и стаффы, - smart scheduler: вместо того чтобы кидать ссылки прямо в очередь, складываем их в метаданные, а отдельный планировщик периодически подбирает оттуда URL по какому-нибудь приоритетному алгоритму и раскладывает по очереди равномерно. В основную схему я его тащить не буду, штука довольно абстрактная, но как тема для глубокого разговора - отличная.

Масштаб и эффективность

Эти двое ходят парой: чтобы быть эффективным, надо уметь масштабироваться. И вот теперь тот самый отложенный расчёт.

Вопрос конкретный: сколько краулеров нужно, чтобы обойти 10 млрд страниц за 5 дней? Сразу скажу честно - оценка будет грубой. В реальной жизни тут запустили бы тест, замерили фактический throughput и умножили. На интервью теста нет, считаем на коленке:

• топовые network-optimized инстансы AWS тянут порядка 400 Гбит/с;

• 400 Гбит/с ÷ 8 = 50 ГБ/с = 50 000 МБ/с;

• при странице в 2 МБ это 50 000 ÷ 2 = 25 000 страниц/с - теоретический потолок одного инстанса.

Понятно, что 25 000 страниц в секунду - фантастика: сто процентов полосы не выжать никогда, мешают DNS, рейт-лимиты, crawl-delay, медленные сайты, ретраи. Реалистично заложим процентов 40:

• 25 000 × 0.4 ≈ 10 000 страниц/с;

• 10 млрд ÷ 10 000 = 10^6 секунд на одной машине;

• 10^6 ÷ 86 400 ≈ 11.5 дней.

Почти 12 дней на одной машине. Чтобы уложиться в 5, нужно минимум 3 (11.5 / 3 ≈ 3.8 дня), а с запасом на сбои и ошибки парсинга возьмём 4 таких инстанса под краулеры.

С парсером проще: он стоит после нашего узкого места (скачивания), так что ему достаточно успевать за входящим потоком. Пусть масштабируется динамически по длине parsing-очереди: бэклог растёт - поднимаем больше воркеров, EC2, Lambda, что угодно.

Про DNS забывают чаще всего, а это частое узкое место. У стороннего DNS-провайдера почти наверняка есть рейт-лимиты. Их можно поднять за деньги (а мы условились, что богатые), но есть ходы поизящнее. Первый - кэширование: у нас уже есть Redis под рейт-лимитер и кэш robots, пусть он же кэширует и резолвы. Один запрос на домен, дальше всё из кэша - нагрузка на провайдера падает в разы. Второй - несколько DNS-провайдеров с round-robin: размазываем нагрузку и заодно страхуемся от падения одного из них. Простое, но очень практичное решение - мне его как-то предложил кандидат на собеседовании, и идея понравилась: видно, что человек думает не книжными ответами, а как инженер, который реально упирался в DNS на проде.

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

Первый, простой - не краулить один и тот же URL дважды. Дубликатов будет полно: парсер достаёт ссылки, и многие из них мы уже видели. Решение - сделать URL первичным ключом в URLMeta и при добавлении проверять, есть ли он уже. Чтобы не плодить дубли ещё на входе, кладём URL в метаданные сразу при добавлении во frontier - с пустым LastCrawled, который заполнится после обхода. Записей будет 10 млрд, так что таблицу шардируем по первичному ключу; поиск остаётся быстрым, и это точно не наше узкое место.

Второй, потоньше - не парсить дубликат контента. Два разных URL (порой даже на разных доменах) могут вести на абсолютно одинаковый контент, и в интернете это случается чаще, чем кажется. Ловим так: краулер хэширует HTML и кладёт хэш в ContentHash, а перед отправкой страницы в parsing-очередь проверяем, не видели ли мы уже такой хэш. Весь вопрос - как сделать эту проверку быстрой:

• Global Secondary Index по хэшу в DynamoDB. На мой взгляд, лучший вариант: проверка за log n, всё лежит рядом с остальными данными, а узкое место у нас всё равно в скачивании - этого хватает с запасом.

• Redis-сет хэшей. Проверка за O(1). Прикинем объём: 10^10 страниц × 20 байт на хэш = 200 ГБ - один инстанс на 256 ГБ вытянет. Минусы: лишнее железо плюс отдельная головная боль с отказоустойчивостью и персистентностью, если Redis ляжет. Зато всё в памяти, десятки миллисекунд.

И отдельно про bloom-фильтр, потому что на этом месте его называет каждый второй кандидат - и обычно зря. Bloom-фильтр - это компактная вероятностная структура для проверки на вхождение в множество. Ключевое слово - вероятностная: вы меняете точность на экономию памяти. Возможны ложноположительные срабатывания (а ложноотрицательные невозможны). Для нас это значит вот что: фильтр иногда скажет "этот контент уже парсили", хотя на самом деле нет, - и мы потеряем страницу. На 10 млрд URL таких потерь немного, и, может, на них плевать. А может, нам критично собрать вообще весь текст - тогда размен плохой.

Так вот, при наших вводных (память не ограничена) я бы bloom-фильтр даже не рассматривал. И приношу его сюда только потому, что его постоянно называют - и часто это скорее плохой сигнал. Кандидат не ставит задачу ("у меня ограничена память в Redis, поэтому..."), не сравнивает с GSI или обычным сетом, а сразу выпаливает "возьму bloom-фильтр", потому что он на слуху из книжек. Структура-то классная, просто применяйте её там, где она правда нужна.

Ловушки для краулеров

Последний штрих к эффективности - crawler traps. Это страницы, специально сделанные так, чтобы держать краулер на сайте вечно: страница ссылается сама на себя или на сотни тысяч пустых страниц того же домена. Без подстраховки можно бесконечно крутиться на одном домене без всякой пользы.

Лечится просто: вводим максимальную глубину обхода (Depth, например 20). Парсер достал новую ссылку - поставил ей глубину родителя плюс один. Превысили порог - не кладём URL обратно в очередь. Вот и всё.

Что ещё можно обсудить

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

• Динамический контент. Куча сайтов сегодня на React и Angular, и контент там не в HTML, а догружается JavaScript'ом. Чтобы такое забирать, нужен headless-браузер (Puppeteer и компания), который отрендерит JS перед парсингом. Это заметно медленнее, дороже и капризнее - вопрос, который лучше прояснить с интервьюером сразу.

• Мониторинг. Datadog, New Relic и прочее: смотреть, сколько URL на каждой фазе пайплайна и какие основные ошибки. Разбиение на фазы тут очень кстати.

• Большие страницы. Некоторые страницы огромны и портят жизнь. По заголовку Content-Length слишком большие файлы можно просто скипать.

• Постоянное обновление. Если краулер нужен не разово, а как у поисковика (или модель переобучают раз в пару месяцев), он должен крутиться непрерывно. Тут и пригодится тот самый URL scheduler: периодически смотрит в метаданные, по LastCrawled решает, что пора перекраулить, и кладёт URL обратно в очередь.

Финальная архитектура: frontier-очередь → краулеры → S3 с сырым HTML, метаданные в DynamoDB, parsing-очередь → парсеры → текст в S3, Redis под рейт-лимит и DNS-кэш, DLQ для мёртвых URL.

На этом всё. Из тупой схемы с одной очередью и одним воркером мы дошли до краулера, который переживает сбои, не дудосит чужие сайты и обходит 10 млрд страниц за 5 дней. Попадётся задача на интервью - будет с чем выходить к вайтборду. А как решали бы вы - пишите в комментариях, всегда интересно почитать.