Как запрос к огромной базе данных возвращается с незначительной задержкой?

Question

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

Я понимаю, что Google сортирует и индексирует страницы с помощью алгоритмов и т.д., Но я полагаю, что индексировать результаты каждого отдельного возможного запроса невозможно (а результаты персонализированы, что делает это еще более неосуществимым)?

Более того, разве аппаратная задержка в аппаратных средствах Google не была бы огромной?Даже если бы все данные в Google хранились на твердотельных накопителях емкостью ТБ / с, я полагаю, что аппаратная задержка была бы огромной, учитывая огромный объем обрабатываемых данных.

Помогает ли MapReduce решить эту проблему?

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

Answer 1

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

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

Учитывая это, давайте попробуем ответить на ваши вопросы:

но я полагаю, что индексировать результаты каждого отдельного возможного запроса невозможно

Да, было бы и на самом деле невозможно получить результаты для каждый отдельный возможный запрос.В мире существует бесконечное количество терминов (даже если вы предполагаете, что будут введены только термины с правильным написанием), и существует экспоненциальное количество запросов к ним n -> inf условия (2^n).Итак, что же делается?Кэширование.Но если запросов / результатов так много, какие из них кэшировать?Политики кэширования.Наиболее частые / популярные / релевантные для пользователя запросы - это те, которые находятся в кэше.

разве аппаратная задержка в аппаратных средствах Google не была бы огромной?Даже если все данные в Google хранились на твердотельных накопителях емкостью ТБ / с.

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

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

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

Помогает ли MapReduce решить эту проблему?

Хотя я не думаю, что использование MapReduce или нет является ограниченной информацией внутри Google, я не разбираюсь в этом вопросе.Однако реализация Google MapReduce (которая, несомненно, нет Hadoop) должен иметь множество оптимизаций, многие из которых включают аспекты, рассмотренные выше.Таким образом, архитектура MapReduce, вероятно, помогает определить, как физически распределяются вычисления, но есть много других моментов, которые следует учитывать, чтобы оправдать такую скорость выполнения запросов.

Итак, я понимаю, что популярные поисковые запросы могут быть кэшированы в памяти.Но как насчет непопулярных поисковых запросов?

На графике ниже представлена кривая того, как виды возникает множество запросов.Вы можете видеть, что существует три основных вида поиска, на каждый из которых приходится примерно 1/3 объема запросов (область под кривой).График показывает степенной закон и подтверждает тот факт, что наиболее популярными являются небольшие запросы.Вторую треть запросов все еще можно обработать, поскольку в них содержится мало слов.Но множество так называемых непонятные запросы, которые обычно состоят из запросов неопытных пользователей, не являются незначительной частью запросов.

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

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

Answer 2

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

Ответ на низкую задержку состоит в том, чтобы сохранить предварительные индексы в памяти. Все, что касается диска, трудно сделать быстро и масштабировать. Вот как новое поколение Hadoop на основе SQL-двигателей, таких как Импала Получите так много скорости по сравнению с инфраструктурой на основе MapReduce Улей, Например.

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

Поиск также разделен на серверы. Таким образом, одна машина может делегировать до 100, чтобы получить часть результата, а затем объединить их.

Вы также можете уйти с некоторой степени приближения. Google буквально не образует тысячи страниц результатов поиска; Это просто должно получить первую страницу о правой.

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

Answer 3

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

Поиск в Google будет работать в основном так же, как в Lucene и Elastic Search, за исключением множества тонко настроенных дополнительных весов и оптимизаций.Но в самой основе своей они будут использовать ту или иную форму перевернутый индекс.Другими словами, они делают нет выполняйте поиск на несколько терабайт при вводе поискового запроса (даже если он не кэширован).Скорее всего, они вообще не смотрят на настоящие документы.Но они используют таблицу подстановки, в которой перечислены документы, соответствующие вашему термину запроса (с вытекающими, орфографическими ошибками, синонимами и т.д.все предварительно обработано).Они, вероятно, извлекают Список из 10000 лучших документов для каждого слова (10 тысяч целых чисел - всего несколько кб!) и вычислите из них наилучшие совпадения.Только если в этих списках нет хороших совпадений, они расширяются до следующих таких блоков и т.д.

Запросы на общеупотребительные слова можно легко кэшировать;и с помощью предварительной обработки вы можете создать список из 10 тысяч лучших результатов, а затем повторно ранжировать их в соответствии с профилем пользователя.Вычисляя "точный" ответ, тоже ничего не добьешься.Вероятно, достаточно взглянуть на топ-10 тысяч результатов;правильного ответа нет;и если будет пропущен лучший результат где-нибудь в позиции 10001, никто не узнает и не заметит (или не обратит внимания).Вероятно, он уже был ранжирован при предварительной обработке и не попал бы в топ-10, который представлен пользователю в конце (или в топ-3, на которые пользователь действительно смотрит)

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

Я рекомендую прочитать эту статью:

Анатомия крупномасштабной гипертекстовой поисковой системы в Интернете
Сергей Брин и Лоуренс Пейдж
Факультет компьютерных наук, Стэнфордский университет, Стэнфорд, КАЛИФОРНИЯ 94305
http://infolab.stanford.edu /~backrub/google.html

И да, это написали основатели Google.Это не последнее состояние, но оно уже будет работать в довольно больших масштабах.