Как бы вы внедрили Google Search? [закрыто]

Предположим, вас спросили в интервью "Как бы вы внедрили Поиск Google?" Как бы вы ответили на такой вопрос? Там могут быть ресурсы, которые объясняют, как реализованы некоторые части в Google (BigTable, MapReduce, PageRank, ...), но это не совсем подходит для интервью.

Какую общую архитектуру вы бы использовали, и как бы вы объяснили это через 15-30 минут?

Я хотел бы начать с объяснения того, как создать поисковую систему, которая обрабатывает ~ 100 тыс. Документов, а затем расширить ее с помощью разделения до 50 млн. Документов, а затем, возможно, еще одним архитектурно-техническим скачком.

Это вид на 20000 футов. Мне бы хотелось узнать подробности - как бы вы ответили на это в интервью. Какие структуры данных вы бы использовали. Из каких сервисов / машин состоит ваша архитектура. Какой будет типичная задержка запроса? Что насчет проблем с отказом / расщеплением мозга? Так далее...

Рассмотрим мета-точку: что ищет интервьюер?

Громадный вопрос, подобный этому, не требует, чтобы вы тратили впустую время на тщательную реализацию алгоритма типа PageRank или на то, как выполнять распределенную индексацию. Вместо этого сфокусируйтесь на полной картине того, что нужно сделать. Похоже, вы уже знаете все большие части (BigTable, PageRank, Map / Reduce). Итак, вопрос в том, как вы на самом деле соединяете их вместе?

Вот мой удар.

Этап 1: Индексирование инфраструктуры (объяснение потратить 5 минут)

Первый этап внедрения Google (или любой поисковой системы) заключается в создании индексатора. Это часть программного обеспечения, которая сканирует совокупность данных и выдает результаты в структуре данных, которая более эффективна для чтения.

Чтобы реализовать это, рассмотрим две части: сканер и индексатор.

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

Во-вторых, индексатор будет работать как часть задания Map / Reduce. (Сопоставьте функцию с каждым элементом входных данных, а затем сведите результаты в одну «вещь».) Индексатор возьмет одну веб-ссылку, извлечет веб-сайт и преобразует его в индексный файл. (Обсуждается далее.) Шаг сокращения будет просто объединять все эти индексные файлы в одну единицу. (Вместо миллионов потерянных файлов.) Поскольку этапы индексирования могут выполняться параллельно, вы можете перенести эту задачу Map / Reduce в произвольно большой центр обработки данных.

Этап 2: Особенности алгоритмов индексации (потратить 10 минут на объяснение)

Как только вы заявите, как вы будете обрабатывать веб-страницы, в следующей части объясняется, как вы можете вычислить значимые результаты. Краткий ответ здесь «намного больше Map / Reduces», но рассмотрите виды вещей, которые вы можете сделать:

• Для каждого веб-сайта подсчитайте количество входящих ссылок. (Страницы с большим количеством ссылок должны быть «лучше».)
• Для каждого веб-сайта посмотрите, как была представлена ​​ссылка. (Ссылки в <h1> или <b> должны быть важнее, чем ссылки в <h3>.)
• Для каждого веб-сайта посмотрите количество исходящих ссылок. (Никто не любит спаммеров.)
• Для каждого веб-сайта обратите внимание на типы используемых слов. Например, «хэш» и «таблица», вероятно, означают, что веб-сайт связан с информатикой. С другой стороны, «хэш» и «пирожные» означают, что сайт был совсем другим.

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

Этап 3: Обслуживание результатов (объяснение потратить 10 минут)

Последний этап на самом деле служит результатам. Надеюсь, вы поделились некоторыми интересными идеями о том, как анализировать данные веб-страницы, но вопрос в том, как вы на самом деле делаете это? К счастью, 10% поисковых запросов Google каждый день никогда не видели. Это означает, что вы не можете кэшировать предыдущие результаты.

Вы не можете иметь ни одного «поиска» из своих веб-индексов, что бы вы попробовали? Как бы вы посмотрели на разные индексы? (Возможно объединение результатов - возможно, ключевое слово stackoverflow получило высокую оценку в нескольких индексах.)

Кроме того, как бы вы это посмотрели? Какие подходы вы можете использовать для быстрого считывания данных из огромного количества информации? (Не стесняйтесь называть свою любимую базу данных NoSQL здесь и / или узнать, что представляет собой BigTable Google.) Даже если у вас есть потрясающий высокоточный индекс, вам нужен способ быстрого нахождения данных в нем. (Например, найдите номер ранга для stackoverflow.com внутри файла объемом 200 ГБ.)

Случайные проблемы (оставшееся время)

После того, как вы покрыли «кости» своей поисковой системы, не стесняйтесь читать любые темы, по которым вы особенно хорошо осведомлены.

• Производительность веб-интерфейса
• Управление центром обработки данных для вашей карты / сокращение рабочих мест
• A / B тестирование улучшений поисковой системы
• Интеграция предыдущего объема поиска / тенденций в индексацию. (Например, ожидая, что нагрузка на внешний сервер увеличится до 9-5 и умрет в начале утра.)

Здесь, очевидно, более 15 минут материала для обсуждения, но, надеюсь, этого достаточно, чтобы вы начали.

Пост на Quora давала оригинальную статью , опубликованную Сергей Брин и Ларри Пейдж. Кажется, это отличная ссылка на этот тип вопросов.