Как устроен поиск по письмам в Яндекс.Почте

11 апреля 2011, 14:10

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

В первую очередь, Яндекс.Почта – это огромный объём данных. У нас хранится около 10 миллиардов писем – это почти столько же, сколько страниц в индексе веб-поиска Яндекса. При этом поисковых запросов примерно в 1000 раз меньше, чем запросов к поиску по интернету.

Зато в поиске по Почте очень важна полнота результатов: если поиск по интернету не найдёт один-единственный сайт из трёх миллионов по запросу «пластиковые стулья», этого никто (кроме, разумеется, вебмастера этого сайта) не заметит. Гораздо критичнее, если потеряется письмо с важным адресом или паролем.

По этим причинам в поиске по Почте существует ряд архитектурных и технологических особенностей.

Архитектурные особенности

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

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

Когда система работает в штатном режиме (все серверы функционируют, все дата-центры доступны), половина поисков отправляется на сервер в одном ДЦ, а вторая половина – на сервер в другом ДЦ. Благодаря этому поисковая производительность увеличивается в два раза.

Технологические особенности

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

Другой вариант – все пользователи в одном индексе. Однако этот вариант ненадёжен: если произойдёт сбой, то сразу миллионы пользователей останутся без поиска, а восстановление системы займёт значительное время.

1-й вариант решения: Индекс размером до 10 Гб
Мы попробовали промежуточный вариант: выбрали максимальный размер каждого индекса 10 Гб. Следовательно, на каждом сервере получилось по 50-100 индексов, которые создаются в порядке поступления писем, а данные пользователя, таким образом, могут находиться в любом из индексов. Но письма часто содержат большое количество однотипной информации («привет», «пока», «@yandex.ru»), которая подходит под 46% всех запросов к поиску по Почте. Получалось, что ответ на такой запрос требовал поднять около 20% всех писем, хранящихся на сервере — это занимало десятки секунд.

2-й вариант решения: Префиксный индекс
Мы оставили максимальный размер индекса равным 10Гб, но перед каждым словом добавили ID пользователя. В результате каждый поиск сразу ограничивался количеством и размером писем в почтовом ящике текущего пользователя. Это снизило объем находимых данных и на порядок ускорило поиск. Но когда на диске – сотни индексов, то из-за большого числа дисковых операций поиск занимает несколько секунд. Наша же цель – десятые доли секунд.

3-й вариант решения: Шардирование по пользователям
Все индексы на сервере были разделены на 1000 сегментов (шардов). В каждом из них – от пяти до двадцати индексов размером до 1 Гб, и данные конкретного пользователя всегда находятся в определённом сегменте. В результате число дисковых операций было снижено до 20 раз по сравнению со вторым вариантом. Скорость поиска также увеличилась в разы. Так мы получили поиск за доли секунд.

Онлайн-индексация
Для того чтобы все поступающие письма практически сразу появлялись в результатах поиска, мы разработали специальный инкрементальный индекс в памяти. Особенность индекса в том, что в него можно добавлять по одному документу, а после добавления документ сразу появляется в поиске.
Процесс индексации выглядит так:
Поступающие письма попадают в инкрементальный индекс в памяти. Когда в памяти накапливается определенное количество писем или занят определенный объем,  запускается процесс переноса данных из индекса в памяти в дисковый индекс.  В этот же момент прекращается индексация в памяти №1 и создается индекс в памяти №2.

Конечно, это – лишь часть того, что мы делаем для улучшения качества нашего поиска по Яндекс.Почте. Может быть, у вас есть какие-то вопросы? Мы с радостью на них ответим.


52 комментария
Все так легко... :)

Спасибо за интересное описание, поисковые алгоритмы по почте написаны на Perl или уже на чем то другом?

Честно говоря поисковые алгоритмы на Perl никогда не были написаны.
Почему Вы решили что они на Perl?

В интернете встречаются упоминания о Perl (в т.ч. вакансии в команду поиска с требованием по знанию перла)

А на чем, все таки, написан алгоритм поиска по почте?

На C++
На Perl в данный момент формируется поисковая выдача. Это примерно так 1% от работы поиска, и как раз к этому моменту все алгоритмы уже отработали. Результаты в памяти и надо просто превратить их в html
критичнее, если потеряется письмо

Богдан, кажется, мое письмо к вам потерялось! Даже два. Что делать?

Думаю, что стоит попробовать отправить еще раз.
А когда Вы его отправляли?

Отправляла 31 марта в 17:27 и 8 апреля в 16:34 с alemanova@yuga.ru.

Да, Ваше письмо получал.
Мне его как раз сегодня прилала служба поддержки.
Сегодня же отвечу.

 

Поступающие письма попадают в инкрементальный индекс в памяти. Когда в памяти накапливается определенное количество писем или занят определенный объем,  запускается процесс переноса данных из индекса в памяти в дисковый индекс.  В этот же момент прекращается индексация в памяти №1 и создается индекс в памяти №2.

Т.е., в момент, когда индекс из памяти мержится с индексом на диске, то данные лочатся и поиск по этому сегменту не идет?

 

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

>На каждом сервере располагается индекс по письмам пяти миллионов пользователей.

далее


>Индекс размером до 10 Гб


>Следовательно, на каждом сервере получилось по 50-100 индексов


10*100=1Tb


> это занимало десятки секунд.



>сервере были разделены на 1000 сегментов (шардов). В каждом из них – от пяти до двадцати индексов размером до 1 Гб

20*1*1000 = 20Tb

>Так мы получили поиск за доли секунд.

А можно было бы написать в Выводах:

Расход дискового пространства увеличился в 20-раз, но при этом скорость поиска возросла ?????

ЗЫ:

Памяти Я так понимаю кушать стало больше?

wel aka wel.org.ua

Комментирую выводы:
1. Расход дискового пространства увеличился на 20% при введении префиксного индекса. Шардирование если и увеличило размер, то настолько незначительно, что мы этого не заметили( может быть максимум на 1%.)
2. Да, память нужна для кеширования, но поскольку поиском пользуются не каждый день все пользователи Яндекс.Почты, то памяти хватает.

>Расход дискового пространства увеличился на 20%

Было ожидаемо?Почему только на 20%?

Да, увеличение было ожидаемо, поскольку добавили префикс.
А на 20% потому, что увеличение затронуло только один индексный файл из 10-ти.
stanislav.grebenyukov
11 апреля 2011, 17:19

А алгоритмы индексации и кэширования собственные, или идеи позаимствованы из опенсорс СУБД?

Алгоритмы собственные, но подобные идеи скорее всего приходили не только нам в голову.

о наконец смог очистить папочки на 20 тыс писем ) видать обновили чего то

только этот пост не оправдывает кривости почты.

Если вы не умеете искать письма, то не называйте свой сервис поисковым

Подскажите, а у Вас Почта все еще что-то ненаходит?

Много чего не находит

вот к примеру:

Делай раз Обратите внимание сколько писем пришло от Буквоеда. Как минимум 5.

а теперь начинаем их искать..... Упппс 

Яндекс нашел всего одно :) 

Я написал вам как-то об этом письмо, но оно видимо потерялось в поиске счастья

Также не работает у меня и у товарища.

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

Сообщайте об этом в службу поддержки, пожалуйста.

Поступающие письма попадают в инкрементальный индекс в памяти. Когда в памяти накапливается определенное количество писем или занят определенный объем,  запускается процесс переноса данных из индекса в памяти в дисковый индекс.  В этот же момент прекращается индексация в памяти №1 и создается индекс в памяти №2.
Что будет с индексом в памяти, если до того, как он перенесётся в дисковый индекс, на сервере случится сбой?

 

С общим поисковым индексом все будет впорядке. 
Дело в том, что пока данные располагаются в индексе памяти, они продублированы в обычном текстовом файле на диске.
В момент, когда происходит сброс данных на дисковый индекс, происходит обычная индексация из файла.
Так что сбой здесь не страшен.

+ Раз в заданный период времени, происходит проверка: все ли письма в индексе или нет.
Если какие-то письма по любым причинам до поиска не доехали, то производится принудительная доиндексация.

Блин, люди, Вам нечем больше занятся, Поставь нормальную почтовую прогу ( я юзаю Evolution + IMAP)

и радуйся жизни, тебе и контакты и всякие там дневнички. А главное если у Яндекса лагонули серваки, по каким либо причинам, или пров нэт отрубил - то нужную информацию в уже полученой почте всегда откопать можно))

А главное не приходится запариватся при поиске о задержках на  серверах и тд, у меня ящик с 3 тыс писем занимает порядка 150МБ, я думаю не нужно объяснять что 150 метров можно и без индексации перелопатить за пару сек, а прога всетаки енто хозяйство еще и индексирует))

Яндекс, когда же вы добавите нормальную работу с контактами в почте?

Или на это дело просто плюнули?

Работаем над этим.

С нетерпением жду. Думаю, не я один жду...

Как минимум, еще я )

Хотелось бы, конечно, еще и дожить до момента, когда Яндекс обновит работы с контактами... :-)

Если у вас так хорошо с поиском, то почему все так плохо с удалением писем. Очень долго  удаляются письма

Кто о чем, а вшивый о бане.

Когда заработает поиск, при котором 10к-0к результатов всё-таки покажутся?

Письма не новые, старые, поиск по одному слову, результатов должно быть много. Два или три (не помню точно) аджакс запроса отпадают по таймауту (каждый по 30с) и всё.

Саппорт обещает, что разбираются.

не надо писать группа куин ну и что что так читается а говорится квин весь мир говорит квин а вы куин морочите людям головы  и читаеся квин  квели куда вы потеряли букву v

Вы точно хотели это сюда написать? Как-то совсем мимо темы…

Ошиблась куда вы потеряли букву w ведь quelle и  queen одинаковые слова  а ведь не кувели а почему тогда кувин ? QUEEN  читаеся  qwin где букы q и e заменяются буквой w  которая вначале слов читается как русская в  примеров много 40 лет был квин .

"Скажем, поиск по интернету и по письмам очень сильно различаются. "

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

Если хотите поподробнее - можете связаться со мной,  я не знаю, где тут багрепорт =)

Тоже далеко не всегда доволен поиском

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

Лажает через раз, и именно тогда, когда уверен, что письмо есть. Приходится искать самостоятельно.

Понимаю, что сравнение с гм здесь не особо в тему, но там ищет намного лучше )

с потеряными AJAX запросами вроде в последнее время проблем особых нет

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

Можете написать багрепорт лично мне.
Почему то сегодня почта глючит. В предпросмотре видно, что текст в письме есть, а когда открываешь его пусто.:(
Есть ли возможность вернуться к классическому интерфейсу? Там таких багов не было.
А какже почистить почту!?
Раньше была такая возможность, сейчас её не стало!

Куда же она делась?

Не смешно! Как и всё остальное!
Отвечать нельзя, на комменты, если их уже больше 6!:-)0
Удалить и ответить, у фото поменялись местами!
Новшества-супер!
Но и понятна теперь причина этого!
Меньше отвечать пользователям,
ЯФ, не справляется со своми обязанностями!

Изменения в Яндекс.Почте никак не связаны с описанными Вами проблемами Яндекс.Фоток. Вам стоит написать в службу поддержки Фоток - они Вам помогут.

Так и почему не могу, удалить так, как делала всегда, комменты, не все, а те, которые хочу!?
где мой почтовый ящик?
olga-balakireva2015
16 апреля 2015, 01:57
где мой почтовый ящик,как найти????????????????????
Тимофей, служба поддержки
18 апреля 2015, 21:12
olga-balakireva2015,
Опишите, пожалуйста, подробнее, какие проблемы возникли с Вашим ящиком? О каком именно ящике идет речь?
Подскажите, как очистить историю поиска по письмам в яндекс.почте. В поиске сохранился список запросов и всегда высвечивается.
swetlana.mochalowa2011
14 октября 2016, 20:20
Помогите найти письмо в моей почте о собеседовании в американском консульстве ,примерно с 10 по15 апреля2015 года. Спасибо.