Книга «System Design. Подготовка к сложному интервью»

image Привет, Хаброжители! Мы решили начинать продавать элетронные книги до выхода бумажной книги. Начали с интервью по System Design (проектированию ИТ-систем), которые очень популярны у работодателей, на них легко проверить ваши навыки общения и оценить умение решать реальные задачи. Пройти такое собеседование непросто, поскольку в проектировании ИТ-систем не существует единственно правильных решений. Речь идет о самых разнообразных реальных системах, обладающих множеством особенностей. Вам могут предложить выбрать общую архитектуру, а потом пройтись по всем компонентам или, наоборот, сосредоточиться на каком-то одном аспекте. Но в любом случае вы должны продемонстрировать понимание и знание системных требований, ограничений и узких мест. Правильная стратегия и знания являются ключевыми факторами успешного прохождения интервью! Что внутри? — Инсайдерская информация: что на самом деле нужно интервьюерам — 4-х шаговый подход к решению любой задачи system design — 16 вопросов из реальных интервью с подробными решениями. — 188 диаграмм, наглядно объясняющих, как работают реальные системы.

Проектирование поискового робота

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

Поисковый робот еще называют веб-пауком или веб-краулером. Он широко используется в поисковых системах для обнаружения нового или обновленного контента в Сети. Это могут быть веб-страницы, изображения, видео, PDF-файлы и т. д. Сначала поисковый робот собирает несколько веб-страниц, а затем проходит по всем ссылкам, которые они содержат, чтобы собрать новый контент. Пример этого процесса показан на рис. 9.1.

image

Поисковый робот применяется для множества разных задач.

  • Индексация в поисковой системе. Это самый распространенный сценарий использования. Робот собирает веб-страницы, чтобы создать локальный индекс для поисковой системы. Например, в поисковой системе Google эту роль играет Googlebot.
  • Веб-архивация. Это процесс сбора информации с веб-страниц для дальнейшего хранения и использования. Например, архивацией веб-сайтов занимаются многие национальные библиотеки. В качестве известных примеров можно привести Библиотеку Конгресса США [1] и Веб-архив ЕС [2].
  • Извлечение веб-данных. Сверхбыстрое развитие интернета создает беспрецедентную возможность для сбора информации. Извлечение веб-данных помогает собирать в Сети ценные сведения. Например, ведущие финансовые фирмы используют поисковые роботы для загрузки стенограмм собраний акционеров и ежегодных отчетов для анализа ключевых инициатив компании.
  • Веб-мониторинг. Поисковые роботы помогают отслеживать нарушения авторских прав и незаконное использование торговых марок в интернете. Например, Digimarc [3] таким образом ищет пиратские копии и отчеты.

Сложность разработки поискового робота зависит от того, какой масштаб он должен поддерживать. Это может быть как скромный школьный проект, который можно закончить за пару часов, так и гигантская система, требующая постоянного внимания со стороны целой команды инженеров. Поэтому сначала нужно определиться с масштабом и функциями, которые должны поддерживаться.

Шаг 1: понять задачу и определить масштаб решения

Поисковый робот работает по простому принципу:

  1. На вход подается список URL-адресов, после чего загружаются соответствующие веб-страницы.
  2. Из веб-страниц извлекаются URL-адреса.
  3. Новые URL-адреса добавляются в список для дальнейшей загрузки. Эти три шага повторяются заново.

Ограничивается ли работа поискового робота этим простым алгоритмом? Не совсем.
Спроектировать широкомасштабный поисковый робот очень сложно. Вряд ли кому-то удастся это сделать во время интервью. Прежде чем переходить к архитектуре, необходимо задать вопросы о требованиях и о масштабе системы.

Кандидат: «Каково основное назначение поискового робота? Он используется для индексации в поисковой системе, сбора данных или для чего-то другого?»

Интервьюер: «Для индексации в поисковой системе».

Кандидат: «Сколько веб-страниц поисковый робот собирает в месяц?»

Интервьюер: «1 миллиард страниц».

Кандидат: «Какого рода контент мы ищем? Только HTML или другие ресурсы вроде PDF-файлов и изображений?»

Интервьюер: «Только HTML».

Кандидат: «Следует ли учитывать недавно добавленные или отредактированные веб-страницы?»

Интервьюер: «Да».

Кандидат: «Нужно ли хранить собранные HTML-страницы?»
Интервьюер: «Да. Срок хранения — 5 лет».

Кандидат: «Что делать с веб-страницами, содержимое которых дублируется?»

Интервьюер: «Их следует игнорировать».

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

Помимо функциональности, которую нужно согласовать с интервьюером, необходимо учитывать следующие характеристики поискового робота.

  • Масштабируемость. Интернет огромен. В нем миллиарды веб-страниц. Поисковый робот должен быть чрезвычайно эффективным и использовать параллельные вычисления.
  • Устойчивость. Интернет полон ловушек. Вам постоянно будет встречаться некорректный HTML-код, неотзывчивые серверы, сбои, вредоносные ссылки и т. д. Поисковый робот должен справляться со всеми этими пограничными случаями.
  • Вежливость. Поисковый робот не должен отправлять веб-сайту слишком много запросов за короткий промежуток времени.
  • Расширяемость. Система должна быть гибкой, чтобы для поддержки новых видов контента не приходилось вносить масштабные изменения. Например, если в будущем нам понадобится собирать графические файлы, это не должно привести к переработке всей системы.

Приблизительные оценки

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

Предположим, что каждый месяц загружается 1 миллиард веб-страниц.
QPS: 1 000 000 000 / 30 дней / 24 часа / 3600 секунд = ~400 страниц в секунду.
Пиковый показатель QPS = 2 * QPS = 800.
Предположим, что средний размер веб-страницы составляет 500 Кб.
1 миллиард страниц * 500 Кб = 500 Тб в месяц для хранения. Если вы плохо ориентируетесь в единицах измерения данных, перечитайте раздел «Степень двойки» в главе 2.
Если данные хранятся на протяжении пяти лет, 500 Тб * 12 месяцев * 5 лет = 30 Пб. Для контента, собранного за пять лет, нужно хранилище размером 30 Пб.

Шаг 2: предложить общее решение и получить согласие

Определившись с требованиями, мы переходим к общим архитектурным вопросам. На рис. 9.2 изображена предлагаемая архитектура, вдохновленная исследованиями [4] [5].

image

Исходные URL-адреса

В процессе поиска в качестве отправной точки используются исходные URL-адреса. Например, чтобы перебрать все веб-страницы на университетском веб-сайте, нам, очевидно, следует начать с доменного имени университета.

Для обхода всего интернета нам нужно творчески подойти к выбору исходных URL-адресов. Хороший исходный URL-адрес позволит перебрать как можно большее количество ссылок. Общая стратегия — разделить пространство адресов на отдельные части. Первый предложенный подход основан на местоположении, так как популярность тех или иных веб-сайтов может зависеть от страны. Исходные URL-адреса также можно выбирать по тематике. Например, адресное пространство можно разделить на покупки, спорт, медицину и т. д. Выбор исходных URL-адресов зависит от разных факторов. От вас не ожидают идеального решения. Просто размышляйте вслух.

Граница сканирования

Большинство современных поисковых роботов делят контент на уже загруженный и ожидающий загрузки. Компонент, хранящий URL-адреса, предназначенные для загрузки, называется границей сканирования. Его можно считать очередью вида «первым пришел, первым ушел». Углубленную информацию об этом компоненте можно найти в разделе, посвященном углубленному проектированию.

Загрузчик HTML

Этот компонент загружает веб-страницы из интернета. URL-адреса этих веб-страниц предоставляются границей сканирования.

Распознаватель DNS

Чтобы загрузить веб-страницу, URL сначала нужно перевести в IP-адрес. Для этого загрузчик HTML может обратиться к распознавателю DNS. Например, по состоянию на 5.3.2019 URL www.wikipedia.org преобразуется в IP-адрес 198.35.26.96.

Анализатор контента

После загрузки веб-страницы ее нужно проанализировать: вдруг у нее некорректный HTML-код, который вызовет проблемы и только займет место в хранилище? Если разместить анализатор контента на одном сервере с поисковым роботом, это замедлит процесс сбора данных. В связи с этим он имеет вид отдельного компонента.

Существующий контент?

Как показывает онлайн-исследование [6], 29 % от всех веб-страниц являются дубликатами, что может привести к повторному сохранению одного и того же контента. Мы используем структуру данных «Существующий контент?», чтобы избежать дублирования информации и сократить время обработки. Она помогает обнаруживать новый контент, который система уже сохраняла. Но это медленный подход, занимающий много времени, особенно если речь идет о миллиардах веб-страниц. Для эффективного выполнения этой задачи следует сравнивать не сами веб-страницы, а их хеши [7].

Хранилище контента

Это система хранения HTML. Ее выбор зависит от таких факторов, как тип и размер данных, частота доступа, время жизни и т. д. Используется как диск, так и память.
Большая часть контента хранится на диске, так как набор данных слишком большой и не умещается в памяти.

Востребованный контент хранится в памяти для снижения латентности.

Средство извлечения ссылок

Этот компонент анализирует HTML-страницы и извлекает из них ссылки. Пример этого процесса показан на рис. 9.3. Относительные пути преобразуются в абсолютные URL-адреса путем добавления префикса en.wikipedia.org.

image

Фильтр URL-адресов

Фильтр URL-адресов отклоняет определенные типы контента, расширения файлов, ссылки на страницы с ошибками и URL-адреса, занесенные в черный список.

Существующий URL-адрес?

«Существующий URL-адрес?» — это структура данных, которая отслеживает URL-адреса, которые уже посещались или находятся в границе сканирования. Это помогает избежать повторного открытия одного и того же URL-адреса, которое чревато повышенной нагрузкой на сервер и потенциальными бесконечными циклами.

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

Хранилище URL-адресов

Это хранилище уже посещенных URL-адресов.

Итак, мы рассмотрели каждый отдельный компонент. Теперь мы соберем их воедино и обсудим принцип работы системы в целом.

Принцип работы поискового робота

Чтобы как следует объяснить каждый этап рабочего процесса, мы добавили на диаграмму архитектуры порядковые номера (рис. 9.4).

image

Шаг 1. Добавляем исходные URL-адреса в границу сканирования.

Шаг 2. Загрузчик HTML берет список URL-адресов из границы сканирования.

Шаг 3. Загрузчик HTML получает соответствующие IP-адреса от распознавателя DNS и начинает загрузку.

Шаг 4. Анализатор контента разбирает HTML-страницы и проверяет их корректность.

Шаг 5. После разбора и проверки контент передается компоненту «Существующий контент?».

Шаг 6. Компонент «Существующий контент?» проверяет, есть ли данная HTML-страница в хранилище:

  • если есть, это означает, что этот контент находится по другому URL-адресу и мы его уже обработали. В этом случае HTML-страница отклоняется;
  • если нет, система еще не обрабатывала этот контент, поэтому он передается средству извлечения ссылок.

Шаг 7. Из HTML-страниц извлекаются ссылки.

Шаг 8. Извлеченные ссылки передаются фильтру URL-адресов.

Шаг 9. После фильтрации ссылки передаются компоненту «Существующий URL-адрес?».

Шаг 10. Компонент «Существующий URL-адрес?» проверяет, находится ли URL в хранилище. Если да, то он уже обрабатывался и больше ничего делать не нужно.

Шаг 11. Если URL-адрес еще не обрабатывался, он добавляется в границу сканирования.

Более подробно с книгой можно ознакомиться на сайте издательства

» Оглавление
» Отрывок

Оформить предзаказ бумажной книги по специальной цене можно на нашем сайте.

При покупке бумажной книги будет доступно чтение онлайн.

Читайте так же:

  • Как плохая репутация может подпортить бизнес Руководитель специалистов по поисковому продвижению SERM компании INGATE Репутация – одна из важнейших вещей для каждого бренда. Если пользователи читают негативные отзывы о компании, то вряд ли захотят покупать ее товары или пользоваться услугами. Поэтому важно регулярно […]
  • Наполнитель сайтов удаленноНаполнитель сайтов удаленно Это один из самых продолжительных дебатов в интернете, и я не знаю, как его разрешить. Но я хотел бы прожевать его как пример борьбы с высокими ставками из-за интернет-выражения. О котором большинство из нас не часто задумывается. Vice News недавно сообщила о нескольких случаях. Когда […]
  • Яндекс открыл прием заявок на ежегодную премию имени Ильи СегаловичаЯндекс открыл прием заявок на ежегодную премию имени Ильи Сегаловича Яндекс открыл прием заявок на научную премию имени Ильи Сегаловича. Она присуждается молодым исследователям и научным руководителям, которые занимаются компьютерными науками. В этом году премия пройдет уже в четвертый раз. Лауреаты получат денежную премию в размере 1 млн рублей и до 500 […]
  • Google представил обновленную версию PageSpeed InsightsGoogle представил обновленную версию PageSpeed Insights Google анонсировал предстоящий запуск обновленной версии инструмента PageSpeed Insights. Среди основных изменений – более четкое разграничение лабораторных и полевых данных, новый подраздел для оценки Core Web Vitals, дополнительная полезная информация и другие улучшения. Редизайн […]