
Условие
Полтора гигабита в секунду не проблема. Проблема в том, что с каждого сайта можно брать одну страницу в секунду, а почти все найденные ссылки ведут туда, где мы уже были.
Спроектируйте обходчик веб-страниц.
Система получает список стартовых адресов, скачивает страницы, извлекает из них ссылки, идёт по ним дальше и складывает содержимое для дальнейшей обработки. Со временем она возвращается к уже посещённым страницам, потому что они меняются.
Считайте, что:
- с одного хоста разрешено брать не чаще одной страницы в секунду;
robots.txtобязателен к соблюдению;- страница приходит в среднем за полторы секунды;
- JavaScript на странице не исполняется: берётся то, что пришло в ответе;
- обход идёт из одного региона.
Вне границ: поисковый индекс и ранжирование, разбор PDF и медиа, обход страниц за паролем. Система заканчивается там, где содержимое сложено в хранилище.
Требования
Функциональные 6
- Обход от списка стартовых адресов вглубь по найденным ссылкам
- Извлечение ссылок из скачанной страницы
- Сохранение содержимого страницы для дальнейшей обработки
- Соблюдение robots.txt для каждого хоста
- Повторный обход ранее посещённых страниц с частотой, зависящей от того, как часто страница меняется
- Адрес, найденный по ссылке и уже известный, повторно не ставится в очередь (к странице возвращаются только по расписанию), а содержимое, которое уже сохранено, повторно не сохраняется
Нефункциональные 5
- Не чаще одной страницы в секунду с одного хоста
- Темп обхода: ~386 страниц/с при цели 1 млрд страниц в месяц
- Отсев дублей: ~19 000 найденных ссылок/с проверяются на «уже видели»; из-за проверки пропущено не более 1% новых адресов
- Падение обходчика не теряет адреса: незавершённое задание возвращается в очередь не позже чем через 5 минут
- Хранение: ~500 ТБ содержимого в месяц до сжатия
Задачи того же уровня
СредняяWebhook Systemприём событий от внешних системПриём событий от внешних сервисов, где нагрузки почти нет, а вся трудность в семантике доставки: событие придёт дважды, придёт не по порядку и однажды не обработается вовсе.
СредняяБронирование мест и номеровПятьдесят тысяч человек приходят за пять тысяч мест в одну минуту. Ресурс именной и конечный: место 14 в ряду 7 существует в одном экземпляре и не заменяется соседним.
СредняяОнлайн-аукцион: ставки и закрытие лотаПятьсот ставок в секунду в один лот, и каждая обязана сравниться с текущим максимумом: такую конкуренцию не размазать, её выстраивают в очередь. И лот, который закрывается сам, ровно в объявленную секунду.
Решите задачу у доски
Интервьюер задаст вопросы по вашей схеме, проверка разберёт её по семи осям




