Design Web Crawler

Задача. Сделать дизайн Web Crawler’а.

Решение.

Web Crawler это бот, который сканирует интернет и сохраняет контент, например в виде индекса поиска. Этот индекс может быть использован для реализации поиска, например, как google.

Уточняем требования.

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

1. Crawler должен просканировать интернет начиная с заданных начальных ссылок (seed URLs)**. Эти ссылки могут быть выбраны разными способами. Например, выбраны по популярности и качеству. Скажем, для википедии это может быть рутовая страница. Мы с нее можем перейти на дочернии, с дочерних на страницы, на которые они ссылаются и т.д.

2. Система должна уметь вытаскивать контент со страниц и сохранять его.

3. Процесс должен быть периодическим. Система должна периодически перезапуск процесса сканирования.

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

1. Scalability(масштабируемость). Система должна быть масштабируемой, т.к. мы хотим просканировать и сохранить контент гигантского числа веб страниц.

2. Extensibility(Расширяемость). Сейчас требуется только вытаскивать контент используя протокол HTTP(s). В будущем потребуется возможность расширить на другие протоколы( например FTP). Также сейчас мы ограничимся только сохранением текста. Возможность сохранять картинки и видео сейчас не требуется, но может потребоваться в будущем.

3. Consistency(Консистентность). Т.к. система должна быть масштабируемой,нам потребуется большое число процессов, потоков, машин, которые будут работать с данными (Workers). Нам нужно обеспечить консистентность этих данных в системе. Все такие Worker’ы должны подчиняться некоторым правилам, когда сканируют и сохраняют данные.

4. Performance (Производительность). Система должна быть достаточно умна, чтобы ограничивать время, которое она тратит на один домен/сайт. Например, ограничивая время затраченное на сканирование одного ресурса, числа URL посещенных для одного домена и т.д. Это называется self-throttling. Обычно сайты содержат файлы robot.txt, который описывает ограничения для данного домена, которым должен следовать crawler.

5. Система должна иметь возможность запускать crawling не только по расписанию, но и по требованию администратора.

Оценим необходимые ресурсы для такой системы.

Допущения, которые мы используем для оценки:

1. Всего нужно отсканировать около 5 миллиардов страниц(ну или любое другое, которое вы обсудите с интервьюером).

2. Размер одной страницы (только текста) ~2MB

3. Объем метаданных для одной страницы (название и описание) ~0.5KB

4. Время на сканирование одной страницы пусть будет 60 ms

5. Мы хотим отсканировать все страницы за один день.

Для хранения отсканированных данных в виде blob нам потребуется:

5 B * (2MB + 0.5 KB) ~ 10 PB (петабайт)

Оценка числа серверов для сканирования:

5 B * 0.06s / (24 * 3600 s) = 3472 сервера

Необходимая пропускная способность сети:

10 PB / (24 * 3600 s) ~ 120 GB/s (гигабайт в секунду) ~ 960 Gb/s (гигабит в секунду).

Или на один сервер:

960 Gb/s / 3472 сервера ~ 277 Mb/s (мегабит в секунду для одной машины).

Дизайн.

High Level Design:

1. Получить еще не посещенный URL

2. Определить его IP Address

3. Установить соединение

4. Распарсить страницу, вытащить ссылки из страницы (URLs) и текст самой страницы.

5. Добавить полученные ссылки в очередь к еще не посещенным.

6. Сохранить текст страницы в blob хранилище или индексе.

7. Перейти к шагу 1.

Вообще, алгоритм похож на BFS, только надо его запустить в паралель на большом числе серверов.

Компоненты:

1. URL Frontier: хранит ссылки, которые нужно посетить(аналог очереди в BFS). Они приоритезированы и каждой приписана, частота с которой нужно ее сканировать. Это необходимо, т.к. некоторые страницы нужно сканировать чаще других. Например, новостные сайты нужно сканировать чаще, чем другие ресурсы.

2. HTML Fetcher. Берет URL из URL Frontier. Резолвит IP address. Устанавливает соединение. Выкачивает HTML.

3. Duplicate Remover. Позволяет определить, не сканировали ли мы уже эту страницу. Т.к. процесс распараллелен и разные страницы могут ссылаться на одни и те же страницы, то нужно исключить страницы, которые мы уже сканировали до этого. Или страница не изменилась, с момента предыдущего сканирования.

4. Extractor. Из полученного HTML вытаскивает ссылки и текст страницы. Текст сохраняет в хранилище (Storage). Непосещенные ссылки сохраняет в URL Frontier.

Более детальный дизайн.

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

Между Fetcher и Extractor добавим DIS (Document Input Stream). Он будет хранить документ в кэше и его можно будет прочитать при помощи нескольких разных модулей одновременно. В качестве DIS можно использовать, например, Redis.

Первый модуль, которые будет читать из DIS — Document De-dup. Он будет вычислять checksum нашего документа, чтобы определить не сохраняли ли мы раньше такой документ и изменился ли он с момента предыдущего скана. Если нет — то он сохранит его в Storage.

Второй модуль будет вытаскивать ссылки из документа и передавать их URL Filter. Который отфильтрует только нужные нам ссылки. Например, по типу протокола ссылки (если мы хотим игнорировать все, кроме HTTP(s)).

Отфильтрованные ссылки будут переданы URL De-dup, который вычислит checksum URL, чтобы проверить, не сканировали ли мы раньше эту ссылку.

До этого мы вычислили, что размер Storage ~10 PB.

Но в процессе дизайна, мы использовали еще несколько хранилищ. Например, URL Set. Он будет хранить checksum уже посещенных ссылок. Какого он должен быть размера? 5B ссылок. Пусть checksum для одной ссылки 8 байт. То размер URL Set 40 GB. Впринципе, такой объем помещается в оперативной памяти современного сервера. Т.е. можно использовать in-memory cache. Если же размер больше, то можно хранить в базе, но с кешем поверх, т.к. нужен быстрый доступ.

Document Checksum Set устроен по тому же принципу и имеет такой же размер.

Как реализовать требования, чтобы наш Crawler, не перегружал сайты свои запросами?

Для этого сделаем для каждого HTML Fetcher отдельную sub-queue. В нее будем помещать ссылки, которые должен зафетчить, конкретный Fetcher. Туда помещать ссылки вычисляя hash(URL) -> Fetcher number. Т.е. на основе ссылки/домена вычислим hash-функцию, на основе этого значения вычислим Fetcher, в очередь которого нужно поместить URL для сканирования. Более того эти сервера можно организовать в hash кольцо. Смотри мою статью consistent hasing: https://telegra.ph/Consistent-Hashing-05-22. Тогда обработку одного домена будет делать только один сервер/Fetcher. Это предотвратит ситуацию, когда один и тот же сайт сканируется множествами серверов одновременно.

Что нужно сделать, чтобы расширить данное решение на другие протоколы? Скажем на FTP? для этого нужно расширить Fetcher. Чтобы он мог устанавливать соединение не только по HTTP(s), но и по FTP. Для расширения для других типов документов, нужно чтобы Document De-dup также умел работать с картинками и видео.