Исторически Почта Mail.Ru использовала механизм от «большого» Поиска (go.mail.ru); однако для задач поиска почтовых ящиков этот вариант не был оптимальным из-за большого потребления ресурсов и относительной сложности обслуживания.
Около 3% владельцев почтовых ящиков используют поиск по почте; однако, хотя эта цифра кажется сравнительно небольшой, почтовые ящики этих людей обычно довольно велики, и их действительно нужно искать.
Поэтому мы решили написать специализированный поисковый демон, который будет искать именно по почте.
Основными требованиями к нему были ограничения на потребление ресурсов (размер индекса — не более 3% от размера почтового ящика, среднее потребление оперативной памяти — не более 100 МБ, средняя загрузка ЦП — не более 3%) и скорость выполнения запросов (средняя время – не более 200 мс).
Ниже расскажу, как это было организовано.
Два основных процесса, выполняемых для решения проблемы поиска почты, — это индексирование почтовых ящиков и выполнение поисковых запросов.
При получении нового письма вам необходимо пополнить поисковый индекс, добавив в него это письмо.
Очевидно, что данные в индексе должны быть упорядочены и максимально компактны; однако в этом случае, скорее всего, потребуется вставка в середину файла, что вызовет очень «тяжелую» запись на диск.
Учитывая, что приход нового письма происходит во много раз чаще, чем выполнение любого поискового запроса, использование столь тяжелой операции для поддержания поискового индекса в актуальном состоянии сомнительно.
Мы решили сделать индекс из двух файлов: снапшота, который содержит полнотекстовый индекс (отсортированные данные), и xlog, который содержит список последовательных транзакций, примененных к индексу.
Любая операция над индексом (например, получение новой буквы) вызывает одну запись на диск — это запись в конец файла xlog.
В момент выполнения поискового запроса фактически происходят две поисковые операции — бинарный поиск с использованием снапшота и последовательный поиск с использованием xlog — результаты которых объединяются.
В тот момент, когда скорость поиска xlog нас перестает удовлетворять, мы перестраиваем снапшот — вносим в него все изменения из xlog и начинаем накапливать xlog заново.
Этот момент определяется автоматически по одной из двух возможных политик: когда время выполнения очередного запроса превышает установленный порог или когда установленный порог превышается размером файла xlog. Индексирование нового сообщения начинается с токенизации.
Токенизация — это разбиение буквы на отдельные слова (полнотекстовый поиск работает с точностью до всего слова и не способен искать по произвольной подстроке).
Стоит отметить, что токенизация — не самая тривиальная задача.
Возьмем, к примеру, адрес электронной почты [email protected] Очевидно, это целое слово.
Разумно было бы сделать возможность поиска и по слову д.калугин (исследование поисковых запросов пользователей показало, что они часто пытаются искать по «части письма»).
Однако невозможно поддерживать все подстроки данного слова, так как это приведет к резкому увеличению размера индекса и, как следствие, к потере скорости выполнения запроса.
Весьма разумно разбивать слово на подстроки, используя только знаки препинания.
Соответственно, мы получаем следующие подслова: [email protected]
[email protected]
d.kalugin-balashov@corp
д.калугин-балашов
д.калугин
д
[email protected]
[email protected]
kalugin-balashov@corp
Калугин-Балашов
Калугин
[email protected]
[email protected]
balashov@corp
Балашов
corp.mail.ru
корпоративная почта
Mail.ru
почта
RU
Все эти слова будут включены в индекс.
Обратите внимание, что это рекурсивное разделение слов имеет некоторые проблемы.
Например, системные администраторы часто получают служебные письма, содержащие различные пути (/usr/local/something/libexec/libany.so), часто очень длинные.
Такие слова могут вызвать большую глубину рекурсии.
Поэтому слова, длина которых превышает указанную в файле конфигурации токенизатора, не делятся на токены рекурсивно, а разбиваются на подслова минимальной длины (само исходное слово, однако, тоже попадает в индекс).
Например, возьмем слово: /usr/local/something/libexec/libany.so При условии, что его длина превышает длину, разрешенную для рекурсивной токенизации, оно разбивается на следующие подслова: /usr/local/something/libexec/libany.so usr местный что-нибудь libexec Либания так Это разделение дает результаты поиска более низкого качества, но является компромиссом с точки зрения соотношения качество/ресурсы.
Завершающий этап токенизации — получить первую форму слова (лемматизатор из «большого поиска» используется для нахождения всех словоформ) и взять из нее CRC32. Все слова в индексе представляют собой именно эти 32-битные целые числа.
Письмо имеет определенный набор числовых (папка, дата, размер, флаг, наличие вложений и т. д.) и текстовых (тема, отправитель, текст и т. д.) зон.
Список зон настраивается в специальном файле и может дополняться в процессе работы поисковой системы.
Снимок состоит из двух частей — словаря (списка всех слов, встречающихся в буквах, и указателей (смещениях)) и собственно списков документов (и зон), на которые ссылаются указатели из словаря.
При поиске считывается словарь, содержащий слова, содержащиеся в поисковом запросе, после чего считываются списки документов по индексам из словаря; результаты суммируются.
В среднем поисковый запрос (с использованием только снимка) по одному слову требует двух обращений к диску — для чтения словаря и для чтения списка документов.
Xlog состоит из последовательно записываемых транзакций.
Целостность каждой транзакции гарантируется контрольной суммой (CRC32) ее содержимого.
При чтении xlog все транзакции, у которых не совпадает контрольная сумма, пропускаются (однако процесс чтения не прерывается до тех пор, пока количество ошибок не превысит определенное число, установленное в файле конфигурации).
Транзакция, как правило, состоит из нескольких команд и всегда описывает ровно одну букву.
Основную роль играет команда, описывающая список слов, присутствующих в данной букве, и номера текстовых зон, в которых они встречаются.
Выполнение поискового запроса через xlog требует чтения всего файла в память и анализа всех транзакций, поэтому размер xlog сильно ограничен.
Результаты выполнения запросов к xlog и снапшоту объединяются в один общий результат.
После того, как сформирован список букв, в которых встречаются слова из запроса, получаются значения всех числовых зон для них.
Числовые значения зон хранятся в файле nzdata. Структура файла аналогична структуре снимка — это словарь, содержащий все номера букв и указатели, которые ссылаются на список значений числовых зон данной буквы.
Однако этот файл считывается в память целиком из-за того, что количество обращений к данным внутри него, в отличие от снимка, велико, а сам файл имеет гораздо меньший размер.
Обратите внимание, что nzdata не содержит все текущие значения числовых зон.
Он, как и снапшот, содержит значения числовых зон на определённый момент, а все последующие изменения содержатся в xlog. Перестроение nzdata происходит одновременно с созданием моментального снимка.
После загрузки всех числовых зон xlog считывается второй раз и все команды, описывающие изменения в числовых зонах, применяются к загруженным результатам.
Также обратите внимание, что демон поиска перед обращением к nzdata пытается получить числовые зоны от демона, обеспечивающего работу с почтовыми индексами (которые кэшируются в памяти при активной работе с почтовым ящиком).
Этот метод во много раз быстрее и обеспечивает согласованность данных.
Получение числовых зон из nzdata происходит, по сути, только в экстренных ситуациях.
Получив числовые зоны, демон поиска начинает применять указанные в запросе фильтры.
Фильтры представляют собой ограничения по числовым зонам: «равно», «не равно», «больше» и т. д. Наиболее популярные фильтры — ограничения по дате («за вчера», «за неделю»), по папке ( «Входящие», «Отправлено», «Нет в спаме»), к любому флажку («Непрочитано», «Помечено», «С вложениями»).
Фильтры применяются последовательно к каждому письму из списка результатов и исключают оттуда некоторые письма.
На этом же этапе используются групперы, которые вычисляют, «сколько было бы результатов, если бы был применен такой фильтр».
Следующий шаг – ранжирование.
В случае поиска по электронной почте, в отличие от других задач полнотекстового поиска, наиболее актуальная функция ранжирования очевидна и проста — сортировка по дате электронного письма.
Ранжирование заканчивается обрезкой букв, не попадающих на текущую страницу (аналог операции LIMIT в SQL).
Для формирования результата поиска одних числовых зон недостаточно.
Поскольку после ранжирования чаще всего остается не более 25 букв (стандартное количество букв, отображаемых на одной странице), именно на этом этапе происходят тяжелые операции по загрузке и обработке текстовых зон.
После загрузки каждая текстовая зона разбивается на слова, среди которых выделяются те, которые присутствуют в поисковом запросе (с учетом словоформ и без учета регистра).
Эти слова «выделены» значком и теги, а сама текстовая область обрезается слева и справа до определенного размера, в который гарантированно входит первое выделенное слово.
Самый печальный индекс строится в момент пересборки xlog в снапшот. Математическое ожидание длины запроса — 6 символов.
Самый печальный индекс хранит слова, не приведенные к первой форме в том регистре, в котором они встречаются в букве.
Индекс Сагеста состоит из двух частей: 1. Словарь, состоящий из префиксов слов (длиной до 6 символов).
Для слов длиной более 6 символов в словаре сохраняются ссылки на списки постфиксов.
2. Множество списков постфиксов (произвольной длины).
Экспериментально было установлено, что построение самого печального индекса с префиксами длиной ровно 6 символов минимизирует его размер.
Самый грустный индекс, в отличие от индекса поиска, имеет смысл кэшировать, но хранить его в памяти относительно недолгое время, поскольку пользователи склонны вводить несколько букв подряд, пока не будут удовлетворены выводом грустных.
Список префиксов (полностью) и все списки постфиксов, считанные с диска, кэшируются.
Данные из xlog не используются при формировании сообщения, так как чтение xlog может занять довольно продолжительное время.
Поэтому самый печальный показатель всегда немного отстает от фактического состояния коробки.
Индекс дайджеста обновляется данными из xlog во время следующей перестройки снимка.
Если у вас есть вопросы по внедрению или есть опыт решения подобной задачи, давайте поделимся лучшими практиками.
Дмитрий Калугин-Балашов, Программист команды Почты Mail.Ru Теги: #mail.ru #Поисковые технологии #поиск
-
Как Удалить Ms-Office 2013?
19 Dec, 24 -
Васм Или Не Васм?
19 Dec, 24 -
Gnome 3.0 Глазами Пользователя
19 Dec, 24 -
Вот Как Выглядит Эффективная Работа Техлида
19 Dec, 24 -
Redmineup — Платформа Для Продуктовых Команд
19 Dec, 24 -
Myspace Стал Крупнейшим Сайтом В Мире
19 Dec, 24
