Полнотекстовый поиск в почте mail.ru

9 апреля в Международном информационно-выставочном центре «ИнфоПространство» прошел пятый Форум технологий Mail.Ru Group. Ведущим Форума выступил вице-президент и технический директор Mail.Ru Group Владимир Габриелян.

Полнотекстовый поиск в почте представил на Форуме программист Mail.Ru Group Дмитрий Калугин-Балашов.

Требования, предъявляемые к поиску по почте, отличаются от тех, которые обычно предъявляют к «большим» поисковым системам. Это становится причиной применения совершенно других, нестандартных технологических решений.

Для начала ― о целях, которые преследовались при создании поиска. До этого для поиска по письмам работал движок, переделанный из большого поиска Mail.Ru. Но, к сожалению, он не устраивал по нескольким параметрам: занимал слишком много памяти; из-за него часто выходили из строя жесткие диски, потому, что он слишком часто на них писал.

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

Во-вторых, нужно минимизировать размер индекса на жестком диске. Тут все просто: чем меньше там занято места, тем дешевле все обходится, и тем меньше нужно, собственно, жестких дисков.Также нужно минимизировать и количество обращений к жестким дискам, чтобы как можно меньше с них что-то читать.Нужно минимизировать и работу с ЦПУ.

И при всем при этом, поиск должен работать максимально быстро.

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

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

Поиск начинается с токенизации, то есть, с разбиения текстов на отдельные слова. Любой полнотекстовый поиск ищет с точностью до слова. Кроме поиска, еще строятся поисковые подсказки. Этим занимается отдельный демон, который запущен параллельно с поисковым демоном.

Обычно люди ищут с точностью до какого-то знака препинания. Если поиск ведется по электронному адресу ― то, например, от точки, либо до тире, либо до собачки. И решили разбивать слова на токены рекурсивным образом. То есть, вот такие слова попадут в индекс:

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

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

То есть, получается, что для того, чтобы осуществить поиск, нужно всего два чтения с диска: во-первых, чтение словаря, который в 99% случаев занимает не больше 1 Mb. В нем находится нужное слово. Во второй части файла читаем список документов, который также не больше 1 Mb. Даже если весь Snapshot очень большой, то он не грузится в память весь, а грузится всего лишь 2 Mb. Поэтому поиск осуществляется очень быстро, вне зависимости от объема.

Однако обнаружилось, что существуют ящики, в которых словари очень большие. Нашлись даже словари порядка 100 Mb. Таких ящиков меньше 0,1%, но они есть, и, что удивительно, пользователь таких ящиков чаще всего поиском и пользуется.

Поэтому мы ввели еще один словарь ― мета-словарь.

Тут будет показано, сколько у нас слов начинается на данный байт. От 0 до 255, и содержит 256 количеств этих слов. То есть, теперь, чтобы поискать по Snapshot, нам нужно три обращения к диску: сперва мы читаем мета-словарь, потом 1/256 часть словаря, и в третье обращение ― список документов. И признак конца словаря нам уже не нужен потому, что мы знаем его длину за счет мета-словаря.

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

Было решено дописывать данные в другой файл, XLog ― это бинарный лог, там записаны транзакции над поисковым индексом. Каждая транзакция применяется к одному документу. Чтобы искать по XLog, надо загрузить его в память целиком и провести обычный линейный поиск. Из-за этого ограничен размер XLog.

По Snapshot мы ищем бинарным поиском, по XLog ― линейным.

Результаты объединяются. Таким образом, получается список документов, список писем, которые содержат данные слова. Но одного списка писем мало, нужно отобразить целую страницу с результатами поиска. Помимо самих писем, у них есть какие-то текстовые и числовые значения ― дата, размер, имя отправителя, текст, тема, то есть, текстовые и числовые зоны.

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

Файл подобен Snapshot, только вместо словаря у него список документов, и список текстовых зон. Их всегда определенное количество, и они нумеруются. Только, в отличие от Snapshot, NZData грузится в память целиком. По размеру он небольшой, максимум, несколько десятков мегабайт.

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

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

И только после этого грузятся текстовые зоны.

Слова из запроса в ответе подсвечиваются.

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

Для выборки подсказок сперва загружается список префиксов для поиска нужного. Если запросу подходит несколько префиксов, то подгружаются все списки необходимых постфиксов. Получается список слов, который сортируется по частоте встречаемости. И выдаются первые n результатов.

Кэшировать нужно целиком список префиксов и те списки постфиксов, к которым уже обращались.

Длина средней подсказки ― в шесть символов. Индекс подсказки занимает минимальное место также при шесть символах. Однако и при других значениях разница не слишком велика, порядка 0,2%. Однако скорость поиска больше всего при длине подсказки в два символа.

Итак, получили поисковый движок, который тратит 50 Mb памяти ― для работы сервера на 300 человек. На жестком диске индексы занимают 3,5% от размера ящиков. И поиск происходит в границах от 3 до 30 обращений к диску. Расходуется примерно 3% ЦПУ. Среднее время исполнения запроса на текущий момент ― 70 милисекунд. Поисковый демон написан на С++, библиотека для записи XLog ― на С.