company_banner

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

  • Из RSS

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


.
Яндекс
Как мы делаем Яндекс

Comments 24

    –9
    Что же вы там такое пишете что падает dev build (12.0.725.0 dev) Хрома :)?
      +10
      Не нужно использовать dev билды для обычной работы и падать не будет. С какой стати dev билд не должен падать, кстати? Если б не падал, был бы не dev, а production. :)
        –7
        Я уже давно не видел чтобы хромовский девбилд падал просто на странице. Интересно а их собственная сборка тоже там падает? Хотел отписать багрепорт, да обнаружил что прямо сейчас разворачивается обновление. Подождем, проверим что прилетело и будет ли дальше падать.
          +2
          Я думаю, это не важно, видели ли вы или нет. Факт, что не нужно использовать девелоперские билды для серфинга интернета.

          Прошу прощения за резкий комментарий, но меня уже порядком достали пользователи, которые считают, что юзать на домашних компах dev-билды — это круто и прогрессивно, а потом заваливают техподдержки кучей воплей «не работает!»… Надеюсь, вы не из их числа.
            –4
            Давайте каждый сам решит — что именно юзать и для чего. Я не заваливаю техподдержку, я пишу баги в хром трекер.
            Это — баг. Не Яндекса, а хрома. Я просто поинтересовался — может быть Яндекс тим знает что именно валит хром у них на странице.

            PS и меня уже тоже порядком достали люди, пытающиеся учить жить окружающих по собственным канонам. Надеюсь вы не из их числа.
      +5
      Собирался написать негативный отзыв, т.к. до последнего времени (не включая 2-3 месяца) пользоваться поиском по письмам было решительно невозможно. Даже по точному запросу адресата сервер выдавал только какие-то архивные письма 5-летней давности (вместо кучи свежих). Сейчас перепроверил, вроде нет таких проблем. Значит хорошо работаете! =)
    • UFO just landed and posted this here
        +3
        Сейчас все должно быть все в порядке!
        +1
        Ну наконец то, не прошло и трёх лет, как у Яндекса появился поиск в почтовом ящике.
        Лучше поздно, чем никогда.
        Троекратное ура!
        0
        Планируется ли поиск по Яндекс.Подпискам?
          0
          Планируется! Но всему свое время.
          0
          Круто! Интересно было бы еще почитать про архитектуру Gmail ;)
            +6
            Когда узнаем, опубликуем :)
            +2
            ну вот, теперь осталось поиск в интернете сделать таким же нормальным ))
              +1
              Может я конечно не в тему, но жутко надоел зеленый банер навязывающий фаерфокс, если человек его закрыл, то наверное его это не интересует, так зачем заново показывать при следующем открытии страницы? :)
                0
                Раз уж такая возможность, у меня пожелание есть: сделать как-то возможным настроить поиск до поиска. Когда ищу слово, по которому много писем, то всё равно это происходит долго. А потом я нажимаю органичить область поиска и выбираю папку — и оно снова ищет. То есть первый раз ждал зря.

                А так, что ж, действительно, как писали выше, некоторе время назад поиска по почте тупо не было по факту, а сейчас даже (о чудо) клавиша Enter активирует поиск в Опере, я очень рад, спасибо!
                  0
                  Возможность органичить поиск до поиска будет и уже в разработке.
                  0
                  Скажите, а почему вы не сделали поиск основываясь на стандартном поисковом движке? То есть рассматривать поиск каждого отдельного пользователя как поиск по конкретному сайту.
                  site:http://www.lib.ru/PXESY/FILATOW
                  или как ваш поиск по каталогам
                  cat:11000051 где можно использовать вместо категории конкретного пользователя, и потом заточить его под поиск по письмам.
                  У вас есть отдельный продукт, который можно установить у пользователя на сервере и искать по серверу пользователя, в том числе по базам данных. Этот поисковик, за исключением стоп слов, индексирует все слова. Почему же он не подходит?
                    0
                    Возможно, это не следовало из описания, но мы взяли стандартное решение и заточили его под решение конкретной задачи.
                    Тут описывался не конкретный продукт, который умеет искать, а скорее серверная и технологическая архитектура его внедрения для решения задачи поиска по почте.
                    Т.е. если вы возьмете любой поисковый движок, который представлен на рынке, и проделаете с ним описанные нами модернизации, то избежите тех проблемам/ньюансов, с которыми мы уже столкнулись и о которых мы рассказали в этом посте.

                    Если вдруг ответил не достаточно конкретно, то готов что-нибудь уточнить.
                      0
                      Понятно.
                      А еще хотелось бы узнать подробнее насчет 3-го варианта решения. Вы пишите что данные пользователя всегда находятся в определенном сегменте. Значит ли это что индекс для одного пользователя ограничен 1 Гб?
                      И как происходит перераспределение пользовательских индексов по серверам в случае их разрастания?
                        0
                        Индекс пользователя всегда расположен в одном сегменте или шарде.
                        В сегменте может быть до 20-ти индексов.
                        Так что ограничение на индекс по письмам пользователя до 20-ти Гб, что в принципе практически нереально.

                        Это ж сколько надо написать и получить писем!
                          0
                          Понятно, спасибо!

                  Only users with full accounts can post comments. Log in, please.