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

[olku]

Это просто праздник какой-то! Даешь неделю горизонтальных архитектур!

[danikin]

Это хорошо или плохо?

[olku]

Великолепно! Тут почтовые сервисы строят без поиска. В избранное — однозначно.

[danikin]

Какие, например?

[olku]

Альтернатива Google Apps

[madesst]

Огромное спасибо за материал, было очень интересно!
Я не очень понял вот такой момент:
— В конце токенизации письма мы получаем некий список (который далее станет словарем) первых форм слова.
— Поисковый запрос так же токенизируется и ищутся совпадения первых форм слов запроса по словарям писем.
— А как быть с поисковыми запросами для которых важно окончание и их нельзя приводить к первой форме, как в таком случае искать совпадения со словарем?

Возможно, я что-то упустил или неправильно понял.

[rvncerr]

В поиске по почте таких запросов нет. Обычно поисковый запрос представляет собой 1-2 слова, либо e-mail (или его часть). Максимум, чем мы рискуем, это большим количеством результатов, чем могло бы быть при «полном совпадении».

[Mystex]

Почему в индексе хранятся CRC32 слов, а не сами слова?

[rvncerr]

Важно, чтобы все записи в словаре имели одинаковую длину. Благодаря этому достаточно легко организовать бинарный поиск по нему.
Кроме того, существуют определенные требования к размеру индекса. Во-первых, таким образом экономится пространство на жестких дисках. Во-вторых, меньший по размеру словарь быстрее читается в память. А CRC32 меньше, чем средней длины слово.

[DjOnline]

Пишут что бывает коллизии у CRC32 на словах, и на русских и на английских.
В этом случае у вас просто подсвечивается другое слово вместо искомого, или ещё какая-то проверка идёт?
И ещё непонятный момент, почему именно CRC32 а не Primary Id леммы в таблице всех слов?

[rasstroen]

А как эта система шардится, если шардится? Или индекс размазывается по серверам?

[rvncerr]

Для каждого почтового ящика свой индекс. Никакого «общего» индекса нет.

[imater]

Обожаю, когда раскрученные сервисы приподнимают юбку и показывают то, что обычно скрыто.

[ef_end_y]

да сколько ж вас, обожателей майла, тут на хабре…

[imater]

Ну, положим, у Yandex юбку выше задирают.

[aeryaguzov]

Рассматривали ли Вы готовые решения(sphinx, solr, elastic) для реализации этого функционала?
Если да, то почему не устроило(неужели не уложились в рамки по мощностям?)?
Очень интересно было бы узнать объемы данных и инфу по машинам для таких рамок.
Если нет, то почему?

[danikin]

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

[dezconnect]

А чем всех не устраивает полнотекстовый поиск MySQL?

[danikin]

Суммарный размер наших поисковых индексов в Почте порядка 500Тб. MySQL такие нагрузки не тянет (ну разве что вы не поставите специально под это 5000 серверов с 96Гб памяти на каждом).

[dezconnect]

Ну и объемчики…

[antigona]

это хайлоад, детка :)

[dezconnect]

О да!. Научи меня хайлоаду, нежно. ;)

[socro]

Годная статья.

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

[rvncerr]

Время поиска по snapshot практически не зависит от размера ящика, а от количество слов в запросе зависит линейно.
Время поиска по xlog линейно зависит от его размера (а его максимально допустимый размер — от конкретных настроек демона).

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