How's that again?

Google

Кроулинг

Сначала делаем индексатор. Это сервис, который проходит по корпусу данных и представляет их в виде структуры данных, оптимизированной для чтения.

Индексатор состоит из 2 частей:

  • spider crawler: Проходит по данным методом паука и выдирает из них все ссылки, которые найдет.
  • indexer: Берет каждую ссылку, получает содержимое по ней и преобразует его в файл обратного индекса. Затем все маленькие файлы индексов объединяются в один большой индекс. Это можно сделать через джоб Map/Reduce. Этот этап может быть очень хорошо распараллелен в огромном дата-центре.

Что представляет из себя инвертированный индекс? Для каждого слова, найденного в процессе кроулинга, сохранен список пар DocumentId-PageRank. Этот список называется posting list.

Индексация

Теперь посмотрим, как документы преобразуются в индексные файлы.

Чтобы посчитать PageRank, нам понадобится еще один джоб Map/Reduce:

  • для каждого сайта считаем количество входящих ссылок
  • для каждой входящей ссылки смотрим, как она была оформлена (напр. ссылки в тэге <h1> получают больший вес, чем в тэге <h3>)
  • для каждой входящей ссылки смотрим количество исходящих ссылок с этого сайта
  • для каждой входящей ссылки смотрим, какие рядом используются слова и пытаемся определить предметную область, даем бОльший вес там сайтам, где предметная область совпадает с той, на которую ссылается.

Еще возможно много вариантов придумать, главное - помнить, что нам нужны масштабируемые способы анализа данных.

Поиск

Для каждого слова из запроса получаем список документов, в которых оно встречается, а затем находим пересечение этих списков. Результат сортируем по PageRank. Затем берем верхние 10 результатов, получаем соответствующие документы из хранилища документов и генерируем для них элементы выдачи, содержащие заголовок, фрагмент текста и его Url. Эти элементы и возвращаем юзеру.

Проблемы

Длинные постинг листы

Если запрос состоит только из популярных слов,то посчитать результат будет очень сложно из-за огромного количества документов, в которых они встречаются. Например, ищем "The Who":

  • The содержится в 50 млрд документов (это все индексированные документы гугла)
  • Who тоже содержится в 50 млрд документов

Если для каждого документа нам нужно хранить 8 байт, то получается что нужно прочитать с диска 2*50*8=800 ГБ данных и вычислить пересечение 1000 млрд строк за 0.2 секунды.

Параллельные запросы

Гугл обслуживает 300.000 запросов в секунду. То есть все, что описано в предыдущем пункте, нужно сделать еще и 300.000 раз за 1 секунду.

Варианты решения

  • Распределять каждый запрос между множеством серверов. Например, 1000 серверов, каждый хранит только свою часть индекса шардированого по документам. Все 1000 серверов выполняют запрос параллельно, потом результаты аггрегируются и возвращаются пользователю. Но эти 1000 серверов все 0.2 секунды будут заняты обслуживанием одного запроса. Чтобы они могли обслужить 300.000 запросов в секунду, понадобится около миллиона серверов.
  • Хранить индекс в памяти, а не на диске
  • Сжимать постинг листы Алгоритмы сжатия обратных индексов
  • Держать дополнительный биграммный индекс. Это индекс, который ищет не по отдельным словам, а по парам слов. В результате получаем намного более короткие постинг листы. Например, чтобы найти результаты запроса "to be or not to be", мы ищем по биграммному индексу результаты для: "to+be", "or+not", "to+be".

Google Docs

Речь здесь будет о предоставлении возможности совместного редактирования.

Google Docs для этого использует так называемое Операциональное Преобразование (Operational Transformation).

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

Наилучшая статья про это, которую мне удалось найти, даже с примером работы Перевод (в переводе ошибка на рисунке, где Васе второй раз применяется трансформированная операция - должно быть "получить Insert '!', @10" и "Применить Insert 'Habr', @5")

Еще хорошая серия статей:

Здесь хорошая визуализация: https://operational-transformation.github.io/visualization.html

А здесь описан другой алгоритм, Differential Synchronization: https://neil.fraser.name/writing/sync/

Реализация

При любом изменении документа в GoogleDocs на сервер шлется POST-запрос по ссылке типа: https://docs.google.com/document/u/0/d/___id_документа___/save?id=___id_документа___

В теле запроса (FormData) - 2 поля:

  • rev - новая версия документа, видимо вычисляется как текущая известная версия + 1
  • bundles - описание операции

Описание операции - json вида [{"commands":[{"ty":"is","ibi":13,"s":"k"}],"sid":"5671b339a5d349b6","reqId":5}]

Такая команда была послана при вставке символа k в позицию 13.

  • ty - тип команды. is - вставка, ds - удаление, mlti - мультикоманда.
  • ibi - индекс символа, на котором применена операция
  • s - вставляемый символ
  • reqId - версия, поверх которой проводились изменения

При удалении:

[{"commands":[{"ty":"ds","si":1,"ei":54}],"sid":"5671b339a5d349b6","reqId":11}]

  • si - индекс первого удаляемого символа
  • ei - индекс последнего удаляемого символа

При выделении и редактировании:

[{"commands":[{"ty":"mlti","mts":[{"ty":"ds","si":11,"ei":15},{"ty":"is","ibi":11,"s":"q"}]}],"sid":"5671b339a5d349b6","reqId":22}]

  • mts - перечисление команд мультикоманды

В ответ приходят json вида:

)]}'
{"additionalData":{},"revisionRanges":[[27,27]]}

При совместном редактировании наверно в additionalData должна быть инфа о том, как смержить документ.