Design Web Crawler
Published: 2023-11-25 22:32:07


## Задача. Сделать дизайн 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, только надо его запустить в паралель на большом числе серверов.

![](https://cdn-images-1.medium.com/max/2728/1*hQP23NsC0RZmfayjQuDYvg.png)

Компоненты:

 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, чтобы проверить, не сканировали ли мы раньше эту ссылку.

![](https://cdn-images-1.medium.com/max/3646/1*wFdJRCL9shyxBt9uGvh_Vw.png)

До этого мы вычислили, что размер 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](https://telegra.ph/Consistent-Hashing-05-22). Тогда обработку одного домена будет делать только один сервер/Fetcher. Это предотвратит ситуацию, когда один и тот же сайт сканируется множествами серверов одновременно.

![](https://cdn-images-1.medium.com/max/2000/1*4tmyLhWBcYkH7kqmi8ih0g.png)

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