Как найти девушку за 250 наносекунд

в 7:45, , рубрики: Блог компании Мамба, демоны, знакомства, социальные сети, метки: , ,

В отличие от Европы и Америки в России к сайтам знакомств преобладает осторожное отношение. Однако надежда нажать на волшебную кнопочку и найти себе любовь не гаснет в сердцах многих. И мы должны эту надежду оправдывать. Конечно, сразу найти идеально подходящую “половинку” мы не обещаем, но предложить десятки, сотни или в отдельных случаях тысячи вариантов, отвечающих именно вашим запросам, просто обязаны. Что и делаем, причем очень быстро.

Средний поиск по базе из 11 миллионов анкет, имеющих от 4 до 30 параметров каждая, занимает у нас в среднем 3.5 милисекунды. И при этом кроме поиска демон-серчер «Мамбы» выполняет следующие, в том числе не вполне традиционные задачи:

  • для каждой конкретной анкеты выдает ее место в поиске (каждый пользователь заходя в свою анкету видит сообщение «Вы находитесь на N месте в поиске)
  • выдает конкретную анкету из списка по первичному ключу
  • производит непосредственный поиск анкеты по заданным параметрам

Несмотря на то, что наш поиск с самого начала разрабатывался собственными силами, время от времени возникали мысли использовать что-то уже известное, обкатанное и гарантированно эффективное. Ну, а если мы задумываемся о поиске, первым в голову приходит Sphinx. В какой-то момент мы решили проверить, может ли он дать нам серьезные преимущества, и несколько удивились полученным результатам. На тестовой базе в 2 миллиона анкет Sphinx показал средний результат в 100-120 мс в в зависимости от запроса, при этом в индекс мы (поскольку это всё-таки тест) включили только часть полей. Наш поиск на этой же базе и на таком же оборудовании тратит от 0.2 до 1.1 мс на запрос.

Sphinx: source - mysql, индексировались только int поля через sql_attr_uint. Весь индекс в памяти.

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

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

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

  • анкеты разбиваются на блоки по 256 анкет в блоке
  • каждый блок кладётся в индекс: вначале 1-ый бит первого поля каждой анкеты, потом 2-ой бит от каждой анкеты, и т. д. Таким образом данные одного бита из поля всех анкет идут подряд

Что это означает для поиска? Например, у нас есть индекс по полям «пол» и «возраст», где пол может принимать значения «М» и «Ж», а возраст — от 18 до 21. Представим, что пользователь хочет найти девушку 20 лет (т. е. условиям удовлетворяют только по одному значению каждого поля).

Допустим, у нас есть такие анкеты (показан 1 блок, поскольку минимально допустимый возраст 18, то 18 лет кодируется как 0000, 19 как 0010, 20 как 0100, и так далее)

image

После обработки получается индекс следующего вида (жирным шрифтом выделен первый бит, до и после):

image

Для каких-то полей значение хранится некомпактно. Например, настоящее поле «возраст» принимает 64 значения. Можно хранить по 1 биту на возможное значение, то есть поле займёт 64 бита, но поиск будет занимать всего 1 операцию, а поиск по диапазону — 2 операции. Более традиционный вариант — хранить его как число, тогда это займёт log2(64) = 6 бит, но поиск конкретного возраста будет занимать 6 операций, а поиск по диапазону более 12 (точное значение зависит от длины записанного в виде ДНФ условия сравнения).

Сам процесс поиска происходит следующим образом:

  • демон принимает и распарсивает запрос
  • выделяется память под результаты (по биту на каждую анкету в индексе)
  • выделяется сегмент памяти под скомпилированный запрос, ему ставится флаг выполнения
  • в этот сегмент пишется:
    • код инициализации, заголовок цикла
    • для каждого поля, по которому нужно фильтровать результат, пишется код, который проверяет значение этого поля
    • окончание цикла, проверка границ, подсчёт кол-ва найденного
  • этот сегмент запускается на выполнение через обычный long jump

Самое интересное — это код проверки поля. В сегменте результатов каждой анкете соответствует 1 бит, который показывает, подходит ли анкета под запрос или нет.

Обработка запроса происходит так:

image

После этого остается только пройти по битовому массиву с результатом и посмотреть, у каких анкет выставлены 1.

В нашем примере результатом будет 00010, то есть запросу удовлетворяет только анкета номер 4.

Демон поиска “Мамбы” вызывается со значительной части всех страниц сайта. Думаю, стоит отметить, что вместе с несколькими другими “основными” демонами он использует протокол JSON-RPC и в целом создает “единое демоническое пространство”.

Реальная статистика поиска выглядит следующим образом:

Запросы на поиск по id анкеты
Рис. 1 Запросы на поиск по id анкеты (график с одного сервера)

Запросы на поиск по параметрам
Рис. 2 Запросы на поиск по параметрам (график с одного сервера)

Всего поиск работает на двух машинах, пиковая производительность одной — 20k операций поиска анкет по параметрам с полным подсчётом количества найденных анкет в секунду (это самая долгая операция, остальные работают значительно быстрее). Рабочая нагрузка — порядка 800 rps поиска + 1000 rps на получение места + 1500 rps на получение анкетных данных.

Вывод места анкеты в поисковой выдаче
Рис. 3 Вывод места анкеты в поисковой выдаче (график с одного сервера)

image
Распределение полного времени ответа (т. е. с учётом сетевого взаимодействия) от всех (двух) поисковых серверов. Среднее — 2.5 мс, медиана — 1.5 мс, 5% запросов занимают более 10 мс и 1% запросов занимает более 15 мс.

Автор: Julia_Gryzunova

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js