Как Google может быть таким быстрым?

Какие технологии и программные решения позволяют Google так быстро обрабатывать запросы?

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

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

Вот несколько замечательных ответов и указателей:

• Платформа Google
• Уменьшение карты
• Тщательно продуманные алгоритмы
• Оборудование - кластерные фермы и огромное количество дешевых компьютеров
• Кэширование и балансировка нагрузки
• Файловая система Google

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

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

Таким образом, возможная архитектура довольно проста: серверы переднего плана обрабатывают запрос, нормализуют его (возможно, удаляя стоп-слова и т. Д.), А затем распределяют его среди любого подмножества реплик, владеющего этой частью пространства запроса (альтернативная архитектура заключается в разделении данные с веб-страниц, так что для каждого запроса нужно обращаться к одной реплике из каждого набора). Возможно, будет запрошено очень много реплик, и самые быстрые ответы побеждают. Каждая реплика имеет запросы сопоставления индекса (или отдельные термины запроса) с документами, которые они могут использовать для очень быстрого поиска результатов в памяти. Если из разных источников возвращаются разные результаты, интерфейсный сервер может их ранжировать при выдаче HTML-кода.

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

Это многовато, чтобы выразить это одним ответом. http://en.wikipedia.org/wiki/Google_platform

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

Вначале биоинформатика столкнулась с проблемой быстрого поиска небольших текстов в гигантских строках. Для нас «гигантская струна» - это, конечно, ДНК. Часто не одна ДНК, а база данных из нескольких ДНК разных видов / людей. Маленькие тексты - это белки или их генетический аналог, ген. Большая часть первой работы компьютерных биологов была ограничена поиском гомологий между генами. Это делается для определения функции вновь обнаруженных генов путем выявления сходства с уже известными генами.

Теперь эти цепочки ДНК действительно становятся очень большими, и (с потерями!) Поиск должен выполняться чрезвычайно эффективно. Таким образом, большая часть современной теории поиска струн была разработана в контексте вычислительной биологии.

Однако некоторое время назад обычный текстовый поиск исчерпал себя. Требовался новый подход, который позволял искать большие строки в сублинейное время, то есть без просмотра каждого отдельного символа. Было обнаружено, что эту проблему можно решить, предварительно обработав большую строку и построив над ней специальную структуру данных индекса. Было предложено много различных таких структур данных. У каждого есть свои сильные и слабые стороны, но есть один, который особенно примечателен, потому что он позволяет выполнять поиск в постоянное время. Теперь, если судить по порядку величины, в котором работает Google, это уже не совсем так, потому что необходимо учитывать балансировку нагрузки между серверами, предварительную обработку и некоторые другие сложные вещи.

Но, по сути, так называемый индекс q-граммы позволяет выполнять поиск за постоянное время. Единственный недостаток: структура данных становится невероятно большой. По сути, для поиска строк, содержащих до q символов (отсюда и название), требуется таблица, в которой есть одно поле для каждой возможной комбинации из q букв (то есть q ^S , где S - размер алфавита , скажем, 36 (= 26 + 10)). Кроме того, должно быть одно поле для каждой позиции буквы в индексированной строке (или, в случае Google, для каждого веб-сайта).

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

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

Короче говоря, эти структуры данных индекса q -gram, возможно, являются самой центральной частью алгоритма поиска Google. К сожалению, нет хороших нетехнических статей, объясняющих, как работают индексы q -граммы. Единственная известная мне публикация, которая содержит описание того, как работает такой указатель, - это… увы, моя бакалаврская диссертация .

Вот несколько замечательных ответов и указателей:

• Платформа Google
• Уменьшение карты
• Тщательно продуманные алгоритмы
• Оборудование - кластерные фермы и огромное количество дешевых компьютеров
• Кэширование и балансировка нагрузки
• Файловая система Google

Они реализовали хорошие распределенные алгоритмы, работающие на огромном количестве оборудования.

Одна из самых важных задержек - веб-серверы - это получение вашего запроса на веб-сервер и получение ответа. Эта задержка ограничена скоростью света, которой должен подчиняться даже Google. Однако у них есть центры обработки данных по всему миру. В результате среднее расстояние до любого из них ниже. Это снижает задержку. Конечно, разница измеряется в миллисекундах, но имеет значение, если ответ должен прийти в течение 1000 миллисекунд.

Все знают, что это потому, что они , конечно же, используют голубей !

Ах да, это и Mapreduce.

У них в значительной степени есть локальная копия Интернета, кэшированная на тысячах ПК в пользовательских файловых системах.

Google нанимает лучших из лучших. В Google работают одни из самых умных людей в ИТ. У них практически бесконечные деньги, которые они могут потратить на оборудование и инженеров.

Они используют оптимизированные механизмы хранения для выполняемых задач.

У них есть географически расположенные серверные фермы.

Попытка составить обобщенный список (который не зависит от того, есть ли у вас доступ к внутренним инструментам Google):

1. Распределить запросы (например, разбить один запрос на меньшие наборы)
2. Асинхронный (сделать столько asynchronious , насколько это возможно, например , не будет блокировать запрос пользователя)
3. Память / кеш (дисковый ввод-вывод медленный, держите как можно больше в памяти)
4. Предварительные вычисления (выполните как можно больше работы заранее , не ждите, пока пользователь запросит данные / обработку)
5. Позаботьтесь о своем внешнем HTML (см. Ислоу и его друзья)

Вы можете найти на домашней странице Google Research несколько указателей на исследовательские работы, написанные некоторыми из сотрудников Google. Вы должны начать с объяснения файловой системы Google и алгоритма map / reduce, чтобы попытаться понять, что происходит за страницами Google.

Эта ссылка также очень информативна За кулисами запроса Google

Оборудование.

Много-много оборудования. В качестве своей серверной фермы они используют массивные кластеры обычных ПК.

TraumaPony права. Тонны серверов и интеллектуальная архитектура для балансировки нагрузки / кеширования, и вуаля, вы можете выполнить запрос менее чем за 1 секунду. В сети было много статей, описывающих архитектуру сервисов Google. Я уверен, что их можно найти в Google :)

Генри, вероятно, прав.

Map Reduce не играет роли для самого поиска, а используется только для индексации. Посмотрите это видео-интервью с изобретателями Map Reduce .

Дополнительная причина, по-видимому, заключается в том, что они обманывают алгоритм медленного запуска TCP.

http://blog.benstrong.com/2010/11/google-and-microsoft-cheat-on-slow.html

И алгоритмы, которые могут использовать эту аппаратную мощь. Например, mapreduce .

Если вас интересует более подробная информация о том, как работает кластер Google, я предлагаю эту реализацию их HDFS с открытым исходным кодом .

Он основан на Mapreduce от Google.

1. Многоступенчатое хранение, обработка и поиск данных

2. ЭФФЕКТИВНОЕ Распределение (100 из 1000 машин) вышеперечисленных задач

3. Хорошая структура для хранения необработанных данных и обработанных результатов

4. Хорошая структура для получения результатов

Как именно все это делается, показано по всем ссылкам, которые у вас есть в резюме вопроса.