Как Google может быть таким быстрым?
Какие технологии и программные решения позволяют Google так быстро обрабатывать запросы?
Каждый раз, когда я что-то ищу (один из нескольких раз в день), меня всегда поражает, как они выдают результаты примерно за 1 секунду или меньше. Какого рода конфигурация и алгоритмы могут быть у них для этого?
Примечание: Это своего рода подавляющая мысль, что даже если бы я установил настольное приложение и использовал его на своей машине, вероятно, он не был бы вдвое быстрее, чем Google. Продолжайте учиться, говорю я.
Вот некоторые из замечательных ответов и предоставленных указателей:
- Платформа Google
- Уменьшение карты
- Тщательно проработанные алгоритмы
- Оборудование - кластерные фермы и огромное количество дешевых компьютеров
- Кэширование и балансировка нагрузки
- Файловая система Google
Ответы 19
Аппаратное обеспечение.
Много-много оборудования. Они используют массивные кластеры обычных ПК в качестве своей серверной фермы.
Это многовато, чтобы выразить это одним ответом. http://en.wikipedia.org/wiki/Google_platform
TraumaPony права. Тонны серверов и умная архитектура для балансировки нагрузки / кеширования, и вуаля, вы можете запустить запрос менее чем за 1 секунду. В сети было много статей, описывающих архитектуру сервисов Google. Я уверен, что их можно найти в гугле :)
И алгоритмы, который может использовать эту аппаратную мощность. Например, как уменьшение карты.
MapReduce не используется для ответа на запросы.
MapReduce работает на большом кластере машин и обладает высокой масштабируемостью: типичное вычисление MapReduce обрабатывает многие терабайты данных на тысячах машин. Были внедрены сотни программ MapReduce, и ежедневно на кластерах Google выполняется более тысячи заданий MapReduce.
MapReduce почти наверняка используется для асинхронного индексирования данных поискового робота. Я был бы очень удивлен, если бы он оказался на критическом пути для поиска. Запуск задания MapReduce действительно убьет задержку.
Генри - они могли использовать его для прокладки маршрутов / карт. Но да, в общем случае. Вы не хотите, чтобы выполнялись какие-либо жесткие вычисления для ответа на обычный пользовательский запрос.
Они реализовали хорошие распределенные алгоритмы, работающие на огромном количестве оборудования.
У них в значительной степени есть локальная копия Интернета, кэшированная на тысячах ПК в пользовательских файловых системах.
Попадание в файловую систему на диске будет дорого стоить с точки зрения задержки (Amazon обнаружил это с Dynamo и ради этого пожертвовал некоторой устойчивостью); Я подозреваю, что все на критическом пути хранится в памяти.
Если вас интересуют более подробные сведения о том, как работает кластер Google, я предлагаю эту реализацию с открытым исходным кодом их HDFS.
Он основан на Уменьшение карты от Google.
HDFS - это распределенная файловая система. Клон mapreduce называется Hadoop и может работать как в HDFS, так и в вашей локальной файловой системе.
Google нанимает лучших из лучших. Некоторые из самых умных людей в ИТ работают в Google. У них практически бесконечные деньги, которые они могут потратить на оборудование и инженеров.
Они используют оптимизированные механизмы хранения для выполняемых задач.
У них есть географически расположенные серверные фермы.
Вы можете найти в домашняя страница Google Research некоторые указатели на исследовательские работы, написанные некоторыми из ребят из Google. Вам следует начать с объяснения файловая система Google и алгоритм сопоставления / сокращения, чтобы попытаться понять, что происходит за страницами Google.
Одна из самых важных задержек - веб-серверы - это получение вашего запроса на веб-сервер и получение ответа. Эта задержка ограничена скоростью света, которой должен подчиняться даже Google. Однако у них есть центры обработки данных по всему миру. В результате среднее расстояние до любого из них ниже. Это снижает задержку. Конечно, разница измеряется в миллисекундах, но имеет значение, если ответ должен прийти в течение 1000 миллисекунд.
Задержки убиваются из-за доступа к диску. Следовательно, разумно полагать, что все данные, используемые для ответов на запросы, хранятся в памяти. Это подразумевает тысячи серверов, каждый из которых реплицирует один из множества шардов. Поэтому критический путь для поиска вряд ли затронет какую-либо из их флагманских распределенных систем с технологиями GFS, MapReduce или BigTable. Они будут использоваться для грубой обработки результатов поискового робота.
Удобство поиска заключается в том, что нет необходимости иметь ни строго согласованные результаты, ни полностью обновленные данные, поэтому Google не мешает отвечать на запрос, потому что стали доступны более актуальные результаты поиска.
Таким образом, возможная архитектура довольно проста: серверы переднего плана обрабатывают запрос, нормализуют его (возможно, удаляя стоп-слова и т. д.), А затем распределяют его среди любого подмножества реплик, владеющего этой частью пространства запроса (альтернативная архитектура заключается в разделении данные с веб-страниц, так что для каждого запроса нужно обращаться к одной реплике из каждого набора). Вероятно, запрашивается очень много реплик, и самые быстрые ответы побеждают. Каждая реплика имеет запросы сопоставления индекса (или отдельные термины запроса) с документами, которые они могут использовать для очень быстрого поиска результатов в памяти. Если из разных источников возвращаются разные результаты, интерфейсный сервер может их ранжировать при выдаче html.
Обратите внимание, что это, вероятно, сильно отличается от того, что на самом деле делает Google - они спроектировали жизнь этой системы, поэтому может быть больше кешей в странных областях, странных индексов и какой-то забавной схемы балансировки нагрузки среди других возможных различий. .
Один факт, который я всегда находил забавным, заключается в том, что Google фактически управляется биоинформатикой (да ладно, мне это смешно, потому что я биоинф ... штука). Позволь мне объяснить.
Вначале биоинформатика столкнулась с проблемой быстрого поиска небольших текстов в гигантских строках. Для нас «гигантская нить» - это, конечно, ДНК. Часто это не одна ДНК, а база данных из нескольких ДНК разных видов / людей. Маленькие тексты - это белки или их генетический аналог, ген. Большая часть первых работ компьютерных биологов была ограничена поиском гомологий между генами. Это делается для того, чтобы установить функцию вновь обнаруженных генов, отмечая сходство с уже известными генами.
Теперь эти цепочки ДНК действительно становятся очень большими, и (с потерями!) Поиск должен выполняться чрезвычайно эффективно. Таким образом, большая часть современной теории поиска струн была разработана в контексте вычислительной биологии.
Однако некоторое время назад обычный текстовый поиск исчерпал себя. Требовался новый подход, который позволял искать большие строки за сублинейное время, то есть без просмотра каждого отдельного символа. Было обнаружено, что эту проблему можно решить, предварительно обработав большую строку и построив над ней специальную структуру данных индекса. Было предложено много различных таких структур данных. У каждого есть свои сильные и слабые стороны, но есть один, который особенно примечателен тем, что позволяет выполнять поиск в постоянное время. Теперь, если судить по порядку величин, в котором работает Google, это уже не совсем так, потому что необходимо учитывать балансировку нагрузки между серверами, предварительную обработку и некоторые другие сложные вещи.
Но по сути, так называемый q-граммовый индекс позволяет выполнять поиск за постоянное время. Единственный недостаток: структура данных становится невероятно большой. По сути, чтобы разрешить поиск строк с символами до q (отсюда и название), требуется таблица с одним полем для каждой возможной комбинации букв q (то есть qS, где S - размер алфавита, скажем, 36 (= 26 + 10)). Кроме того, должно быть одно поле для каждой позиции буквы в индексированной строке (или, в случае Google, для каждого веб-сайта).
Чтобы уменьшить явный размер, Google, вероятно, будет использовать несколько индексов (фактически, это делать, чтобы предлагать такие услуги, как исправление орфографии). Самые верхние работают не на уровне персонажа, а на уровне слов. Это уменьшает q, но делает S бесконечно больше, поэтому им придется использовать таблицы хеширования и коллизий, чтобы справиться с бесконечным количеством разных слов.
На следующем уровне эти хешированные слова будут указывать на другие структуры данных индекса, которые, в свою очередь, будут содержать хеш-символы, указывающие на веб-сайты.
Короче говоря, эти структуры данных индекса q-граммы, возможно, являются самой центральной частью алгоритма поиска Google. К сожалению, нет хороших нетехнических статей, объясняющих, как работают индексы q-граммы. Единственная известная мне публикация, которая содержит описание того, как работает такой указатель, - это… увы, моя диплом бакалавра.
Я был в биоинформатике 5 лет, а потом в поисковых системах - и q-граммы не так важны, как вы думаете. Фундаментальной структурой данных для поиска, который выполняет Google (на очень, очень базовом уровне), является инвертированный индекс.
Это кажется неправильным. Google работает или работал с инвертированным индексом. q-грамм будет полезен для фраз, но не в целом
@Stefan: Тот же комментарий уже был сделан SquareCog - и я не отрицаю, что инвертированные индексы играют большую (и, вероятно, намного большую, чем индексы n-граммов) роль. Я выбрал эту технологию, потому что n-граммы - это моя структура данных для домашних животных, и я думаю, что основная идея - Google работает быстро, потому что на самом деле ему не нужно «искать», он может выполнять более или менее прямой поиск - действительно зависит от такого индекса (nb: это, вероятно, выполняется с помощью хеширования, но это по-прежнему, n-граммовый индекс). То, что этот индекс также оказывается инвертированным, случайно с моей точки зрения (хотя, вероятно, не для Google ;-)).
Многоэтапное хранение, обработка и поиск данных
ЭФФЕКТИВНОЕ Распределение (100 из 1000 машин) вышеперечисленных задач
Хорошая структура для хранения необработанных данных и обработанных результатов
Хорошая структура для получения результатов
Как именно все это делается, резюмируют все ссылки, которые у вас есть в резюме вопроса.
Генри, вероятно, прав.
Map Reduce не играет роли для самого поиска, а используется только для индексации. Отметьте это видео-интервью с изобретателями Map Reduce.
Попытка составить обобщенный список (который не зависит от того, есть ли у вас доступ к внутренним инструментам Google):
- Parellelize запросы (например, разбить один запрос на меньшие наборы)
- Асинхронный (сделать как можно более асинхронным, например, не будет блокировать запрос пользователя)
- объем памяти / cache (Дисковый ввод-вывод медленный, держите как можно больше в памяти)
- Предварительно вычислить (Сделайте как можно больше работы заранее, не ждите, пока пользователь запросит данные / обработку)
- Заботьтесь о своем интерфейсный HTML (см. Yslow и друзья)
Все это знают, потому что, конечно же, они используют голубей!
Ах да, это и Mapreduce.
Если они заставят крыс работать и на них, два самых бесполезных и надоедливых существа получат работу ...
Я много смеюсь над этим, ха-ха
Эта ссылка также очень информативна За кулисами запроса google
Вот некоторые из замечательных ответов и предоставленных указателей:
- Платформа Google
- Уменьшение карты
- Тщательно проработанные алгоритмы
- Оборудование - кластерные фермы и огромное количество дешевых компьютеров
- Кэширование и балансировка нагрузки
- Файловая система Google
Дополнительная причина, по-видимому, заключается в том, что они обманывают алгоритм медленного запуска TCP.
http://blog.benstrong.com/2010/11/google-and-microsoft-cheat-on-slow.html
Просто чтобы уточнить «массивность»: сотни тысяч серверов. Думаю, никто за пределами Google не знает настоящего числа, и оно, должно быть, постоянно меняется.