Компания
1 079,53
рейтинг
29 января 2013 в 16:34

Разработка → Полнотекстовый поиск: как это делают в Почте Mail.Ru

Исторически в Почте Mail.Ru использовался механизм от «большого» Поиска (go.mail.ru); однако для задач поиска по почтовым ящикам такой вариант не был оптимальным ввиду большого потребления ресурсов и относительной сложности в обслуживании. Поиском по почте пользуются около 3% владельцев почтовых ящиков; однако, хотя эта цифра кажется относительно небольшой, ящики этих людей обычно достаточно объемны, и поиск им действительно необходим. Поэтому мы приняли решение написать специализированный поисковый демон, который будет заниматься именно поиском по почте. Основными требованиями к нему стали ограничения по потребляемым ресурсам (размер индекса — не более 3% от размера почтового ящика, среднее потребление оперативной памяти — не более 100 Мб, средняя утилизация CPU — не более 3%) и скорости исполнения запросов (среднее время — не более 200 мс). О том, как он был организован, я расскажу ниже.

Два основных процесса, выполняемых в рамках решения задачи поиска по почте, это индексация ящиков и исполнение поисковых запросов. В момент получения нового письма необходимо пополнить поисковый индекс, внеся в него это письмо. Очевидно, что данные в индексе должны быть упорядочены и максимально компактны; однако в таком случае наиболее вероятно, что потребуется вставка в середину файла, которая породит собой весьма «тяжелую» запись на диск. Учитывая, что приход нового письма происходит во много раз чаще, чем исполнение какого-либо поискового запроса, использование такой тяжелой операции для поддержания поискового индекса в актуальном состоянии сомнительно.

Мы приняли решение сделать индекс из двух файлов: snapshot, который содержит полнотекстовый индекс (отсортированные данные), и xlog, содержащий список последовательных транзакций, примененных к индексу. Любая операция над индексом (например, получение нового письма) вызывает одну запись на диск — это запись в конец файла xlog. В момент исполнения поискового запроса по факту происходит две операции поиска — бинарный поиск по snapshot и последовательный поиск по xlog — результаты которых объединяются. В тот момент, когда скорость поиска по xlog перестает нас удовлетворять, мы выполняем перестроение snapshot — вносим в него все изменения из xlog, а xlog начинаем копить заново. Данный момент определяется автоматически по одной из двух возможных политик: когда время исполнения очередного запроса превысит установленный порог, либо когда установленный порог будет превышен размером файла xlog.

Индексация нового письма начинается с токенизации. Токенизация — это разбиение письма на отдельные слова (полнотекстовый поиск работает с точностью до целого слова и не способен искать по произвольной подстроке). Стоит заметить, что токенизация является не самой тривиальной задачей. Возьмем, например, email-адрес

d.kalugin-balashov@corp.mail.ru

Очевидно, он является целым словом. Разумно сделать возможным поиск также и по слову d.kalugin (изучение поисковых запросов пользователей показало, что они часто пытаются искать по «части email»). Однако поддерживать все подстроки данного слова нельзя, так как это приведет к резкому росту размера индекса, и, как следствие, потере скорости исполнения запросов. Весьма разумно разбивать слово на подстроки только по знакам препинания. Соответственно, мы получаем следующие подслова:

d.kalugin-balashov@corp.mail.ru
d.kalugin-balashov@corp.mail
d.kalugin-balashov@corp
d.kalugin-balashov
d.kalugin
d
kalugin-balashov@corp.mail.ru
kalugin-balashov@corp.mail
kalugin-balashov@corp
kalugin-balashov
kalugin
balashov@corp.mail.ru
balashov@corp.mail
balashov@corp
balashov
corp.mail.ru
corp.mail
mail.ru
mail
ru


Все данные слова войдут в индекс.
Заметим, что такое рекурсивное разбиение на слова имеет некоторые проблемы. Например, системным администраторам часто приходят служебные письма, которые содержат в себе различные пути (/usr/local/something/libexec/libany.so), зачастую весьма длинные. Такие слова могут вызывать большую глубину рекурсии. Поэтому слова, которые имеют длину больше заданной в конфигурационном файле токенизатора, не разбиваются на токены рекурсивно, а разбиваются на подслова минимальной длины (само исходное слово, тем не менее, тоже попадает в индекс).
Например, возьмем слово:

/usr/local/something/libexec/libany.so

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

/usr/local/something/libexec/libany.so
usr
local
something
libexec
libany
so


Такое разбиение дает менее качественные результаты поиска, однако является компромиссным вариантом в плане соотношения качество/ресурсы.
Окончательным этапом токенизации является получение первой формы слова (для поиска всех словоформ используется лемматизатор от «большого поиска») и взятие от нее CRC32. Все слова в индексе являются именно этими 32-битными целыми числами.

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

Snapshot состоит из двух частей — словарь (список всех слов, встречающихся в письмах, и указатели (смещения)) и собственно списки документов (и зон), на которые ссылаются указатели из словаря. При поиске происходит чтение словаря, в котором находятся слова, содержащиеся в поисковом запросе, после чего читаются списки документов по указателям из словаря; результаты объединяются. В среднем поисковый запрос (с использованием только snapshot) по одному слову требует двух обращений к диску — для чтения словаря и чтения списка документов.



Xlog состоит из последовательно записанных транзакций. Целостность каждой транзакции гарантируется контрольной суммой (CRC32) ее содержимого. При чтении xlog все транзакции, для которых не сошлась контрольная сумма, пропускаются (однако процесс чтения не прерывается до тех пор, пока количество ошибок не превысит определенное число, установленное в конфигурационном файле). Транзакция, как правило, состоит из нескольких команд и описывает всегда ровно одно письмо. Главную роль играет команда, описывающая список слов, которые присутствуют в данном письме, и номера текстовых зон, в которых они встречаются. Исполнение поискового запроса над xlog требует чтения всего файла в память и анализа всех транзакций, поэтому размеры xlog сильно ограничены. Результаты исполнения запросов над xlog и snapshot объединяются в один общий результат.



После того как сформирован список писем, в которых встречаются слова из запроса, происходит получение значений всех числовых зон для них. Значения числовых зон хранятся в файле nzdata. Структура файла аналогична структуре snapshot — это словарь, содержащий все номера писем и указатели, ссылающиеся на список значений числовых зон данного письма. Однако данный файл читается в память целиком ввиду того, что число обращений к данным внутри него, в отличие от snapshot, велико, а сам файл имеет намного меньшие размеры. Отметим, что nzdata не содержит все актуальные значения числовых зон. Он, как и snapshot, содержит значения числовых зон на определенный момент, а все последующие их изменения содержатся в xlog. Перестроение nzdata производится в тот же момент, что и snapshot. После подгрузки всех числовых зон происходит второе чтение xlog и применение всех команд, которые описывают изменения числовых зон, к загруженным результатам. Также отметим, что поисковый демон, прежде чем обратиться к nzdata, пробует получить числовые зоны от демона, обеспечивающего работу с почтовыми индексами (которые кэшируются в памяти при активной работе с ящиком). Этот способ во много раз быстрее и обеспечивает консистентность данных. Получение числовых зон из nzdata происходит, по сути, только в аварийных ситуациях.



Получив числовые зоны, поисковый демон начинает применять фильтры, указанные в запросе. Фильтры — это ограничения числовых зон: «равно», «не равно», «больше», и т. д. Самые популярные фильтры — ограничение на дату («за вчера», «за неделю»), на папку («Входящие», «Отправленные», «не в Спаме»), на какой-либо флаг («Непрочитанное», «Отмеченное флажком», «С вложениями»). Фильтры применяются последовательно к каждому письму из списка результатов и исключают часть писем оттуда.



На этом же этапе применяются группировщики, которые подсчитывают «сколько бы было результатов, если бы был применен такой фильтр».



Следующим этапом является ранжирование. В случае поиска по почте, в отличие от других задач полнотекстового поиска, наиболее релевантная функция ранжирования очевидна и проста — это сортировка по дате письма. Заканчивается ранжирование отсечением писем, не попадающих в текущую страницу (аналог операции LIMIT в SQL).
Для формирования результата поиска одних числовых зон мало. Так как после ранжирования остается чаще всего не более 25 писем (стандартное количество писем, отображаемых на одной странице), тяжелые операции загрузки и обработки текстовых зон происходят именно на этом этапе. Каждая текстовая зона после загрузки разбивается на слова, среди которых выделяются присутствовавшие в поисковом запросе (с учетом словоформ и без учета регистра). Данные слова «подсвечиваются» тегами <b> и </b>, а сама текстовая зона обрезается слева и справа до определенного размера, в который гарантированно входит первое выделенное слово.





Индекс саджестов строится в момент перестройки xlog в snapshot. Математическое ожидание длины запроса — 6 символов.



В индексе саджестов хранятся слова, не приведенные к первой форме, в том регистре, в котором находятся в письме. Индекс саджестов состоит из двух частей:

1. Словарь, состоящий из префиксов слов (длиной до 6 символов). Для слов длиной свыше 6 символов в словаре хранятся ссылки на списки постфиксов.
2. Множество списков постфиксов (произвольной длины).



Опытным путем было установлено, что построение индекса саджестов с префиксами длиной именно в 6 символов минимизирует его размер. Индекс саджестов, в отличие от поискового индекса, имеет смысл кэшировать, но хранить в памяти относительно недолго, потому что пользователям свойственно вводить несколько букв подряд до тех пор, пока выдача саджестов их не устроит. Кэшируется список префиксов (полностью) и все прочитанные к настоящему моменту с диска списки постфиксов. Данные из xlog-а не используются при генерации саджеста, т. к. чтение xlog может занять достаточно большое время. Поэтому индекс саджестов всегда немного «отстает» от реального состояния ящика. Индекс саджестов пополняется данными из xlog во время очередного перестроения snapshot.

Если у вас есть вопросы по реализации или есть опыт решения подобной задачи — давайте делиться наработками.

Дмитрий Калугин-Балашов,
Программист команды Почты Mail.Ru
Автор: @rvncerr

Комментарии (24)

  • +10
    Это просто праздник какой-то! Даешь неделю горизонтальных архитектур!
    • 0
      Это хорошо или плохо?
      • +8
        Великолепно! Тут почтовые сервисы строят без поиска. В избранное — однозначно.
  • +6
    Огромное спасибо за материал, было очень интересно!
    Я не очень понял вот такой момент:
    — В конце токенизации письма мы получаем некий список (который далее станет словарем) первых форм слова.
    — Поисковый запрос так же токенизируется и ищутся совпадения первых форм слов запроса по словарям писем.
    — А как быть с поисковыми запросами для которых важно окончание и их нельзя приводить к первой форме, как в таком случае искать совпадения со словарем?

    Возможно, я что-то упустил или неправильно понял.
    • +4
      В поиске по почте таких запросов нет. Обычно поисковый запрос представляет собой 1-2 слова, либо e-mail (или его часть). Максимум, чем мы рискуем, это большим количеством результатов, чем могло бы быть при «полном совпадении».
  • +1
    Почему в индексе хранятся CRC32 слов, а не сами слова?
    • +7
      Важно, чтобы все записи в словаре имели одинаковую длину. Благодаря этому достаточно легко организовать бинарный поиск по нему.
      Кроме того, существуют определенные требования к размеру индекса. Во-первых, таким образом экономится пространство на жестких дисках. Во-вторых, меньший по размеру словарь быстрее читается в память. А CRC32 меньше, чем средней длины слово.
      • 0
        Пишут что бывает коллизии у CRC32 на словах, и на русских и на английских.
        В этом случае у вас просто подсвечивается другое слово вместо искомого, или ещё какая-то проверка идёт?
        И ещё непонятный момент, почему именно CRC32 а не Primary Id леммы в таблице всех слов?
  • 0
    А как эта система шардится, если шардится? Или индекс размазывается по серверам?
    • +3
      Для каждого почтового ящика свой индекс. Никакого «общего» индекса нет.
  • +12
    Обожаю, когда раскрученные сервисы приподнимают юбку и показывают то, что обычно скрыто.
    • –23
      да сколько ж вас, обожателей майла, тут на хабре…
      • +4
        Ну, положим, у Yandex юбку выше задирают.
  • +1
    Рассматривали ли Вы готовые решения(sphinx, solr, elastic) для реализации этого функционала?
    Если да, то почему не устроило(неужели не уложились в рамки по мощностям?)?
    Очень интересно было бы узнать объемы данных и инфу по машинам для таких рамок.
    Если нет, то почему?
    • +5
      У всех этих решений есть как минимум один общий недостаток — они сильно потребляют память. Это все из-за того, что вся верхушка индекса у них кэшируется. И это правильное решение для случая, когда у вас один большой индекс. А когда у вас много маленьких индексов (по одному на пользователя), то это решение не работает, ибо памяти столько не напасешься. В то же время, делать один большой индекс на всех пользователей, без жесткого экранирования пользователей друг от друга — это суперопасно для почты, ибо в случае бага в фильтрации результатов можно легко получить данные из чужого ящика.
  • –1
    А чем всех не устраивает полнотекстовый поиск MySQL?
    • +7
      Суммарный размер наших поисковых индексов в Почте порядка 500Тб. MySQL такие нагрузки не тянет (ну разве что вы не поставите специально под это 5000 серверов с 96Гб памяти на каждом).
      • +2
        Ну и объемчики…
        • +2
          это хайлоад, детка :)
          • +2
            О да!. Научи меня хайлоаду, нежно. ;)
  • +1
    Годная статья.

    Однако, хотелось бы немного замеров производительности. Какой-нибудь график время_поиска/размер_ящика (и еще как-нибудь туда приплести длину запроса).
    • 0
      Время поиска по snapshot практически не зависит от размера ящика, а от количество слов в запросе зависит линейно.
      Время поиска по xlog линейно зависит от его размера (а его максимально допустимый размер — от конкретных настроек демона).

      Математическое ожидание времени исполнения поискового запроса — 200мс (посчитано на живом сервере).
      Подробные графики покажем в ближайшее время (возможно, это тема для отдельного поста).

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.

Самое читаемое Разработка