Привет! Меня зовут Николай Смирнов, я ML-инженер в команде поиска Яндекс Лавки. В этой статье я расскажу немного о закулисье: 

• Как наша команда шаг за шагом строила поисковый сервис, начиная с алгоритма Ахо — Корасик, SaaS-решений и Маркета, и дошла до собственной архитектуры на C++ с userver и многослойным «бургером» из ML-моделей. 

• Зачем поиску Лавки понадобилось сразу несколько технологий — BM25, DSSM, BERT и CatBoost — и чем полезна каждая из них. 

• Как наш поиск собирает данные о вас и о товарах и почему ML-модели приходится дообучать. 

А ещё вместе «сломаем» прод — посмотрим, что произойдёт, если выключить какую-нибудь из моделей, и почему даже самые продвинутые нейросети не являются серебряной пулей.

В общем, будет немного истории, самое интересное из архитектуры, инженерные находки и живые примеры того, как поиск в Лавке принимает решения. Если интересно, как на самом деле работает поиск, — погнали!

Хроники поиска истинного пути

Начнём с небольшого экскурса в историю. Поиск в Лавке начинался с алгоритма Ахо — Корасик в 2020 году. Он был модифицирован под нужды товарного поиска — искал по названию, категориям и синонимам, учитывая с бóльшим весом, конечно, название. Обрабатывал некоторые несложные опечатки, но не умел, например, понять, что «вожв» — это на самом деле две опечатки в слове из четырёх букв «вода».

Следующим этапом развития сервиса поиска в 2021 году стал переезд на SaaS (Search as a Service) — общеяндексовый универсальный сервис для поиска по произвольным документам. Он не учитывал специфику Лавки, но в целом выглядел неплохо. Более того, мы продолжаем использовать его как бейзлайн при замере интегральных улучшений в качестве поисковых моделей.

Затем в том же 2021 году команда поиска успешно выполнила проект в сотрудничестве с командой поискового портала и переключилась на движок Яндекс Маркета. В его основе лежал инвертированный индекс и ранжирующая модель CatBoost. Для этого были построены пайплайны поставки данных о товарах в поисковый индекс и написан сервис, проксирующий вызов поиска в контур Маркета.

Маркет отлично умеет искать товары, учитывая множество факторов, в том числе CTR-ность и покупаемость. Казалось, что он идеально покрывал потребности Лавки. Тем более что DevOps и общая культура разработки в большой команде Маркета позволяли обучать и встраивать кастомные лавочные ML-модели и выкатывать их почти независимо от других команд. Кроме того, инфра Маркета давала широкие возможности для масштабирования. Но в итоге мы плавно перешли к решению на собственных рельсах, о котором я расскажу в статье.

Для интересующихся историей оставлю ссылку на более подробное описание эволюции поиска в Лавке, сделанное Ваней Ходором.

Сервис поиска с высоты птичьего полёта

Верхнеуровневое описание архитектуры сервиса поиска Лавки похоже на типичный сервис с машинным обучением под капотом. У него есть три важные части:

1. Рантайм, где применяются ML-модели и пользователи получают релевантную поисковую выдачу.

2. Система сбора и поставки данных для обучения ML-моделей.

3. Процесс обучения моделей, которые затем едут в рантайм.

Схематично это можно представить так:

Перед погружением в архитектуру сервиса, как это делают в интервью по System Design, давайте выясним важные детали решаемой задачи:

Q: Какова дневная аудитория поиска в Яндекс Лавке? Какой RPS на сервис ожидается?

A: Сотни тысяч покупателей в сутки, которые генерируют в пике порядка нескольких сотен запросов в секунду.

Q: Какие данные храним о пользователях? 

A: История заказов, эмбеддинги и несколько десятков счётчиков типа среднего чека. Занимаемое пространство — порядка 10 КБ на пользователя.

Q: Сколько документов, по которым необходимо осуществлять поиск?

A: 100К товаров. Метаданные о товаре: название, описание, состав, цена и некоторые другие.

Q: Как в поиске обрабатываем факт отсутствия товара на складе: игнорируем или удаляем такой товар из выдачи? Сколько складов всего? Какой средний ассортимент склада?

A: Отсутствующие товары не показываем на выдаче. Складов порядка 1К, и на каждом примерно 5К товаров в наличии при ассортименте в 20К.

Ещё важные уточнения по функциональности:

• Нужно искать по неполному запросу: например, на «моло» должны находить «молоко».

• Поиск должен быть персонализированным: например, на широких запросах типа «сметана» в топе должна быть сметана, которую купите именно вы.

Пользовательский запрос с фронта (мобильные приложения Лавка, Еда, Go, Маркет и другие либо web-клиент) поступает на client-api. Это крупногранулярный сервис, отвечающий за получение товаров из каталога и поиска. В нём определяется идентификатор склада, из которого будет происходить заказ, и выполняется запрос в сервис search, возвращающий список идентификаторов товаров, релевантных поисковому запросу. Под капотом у поискового сервиса:

1. Сбор данных о пользователе из kv-user-storage.

2. Предобработка поискового запроса: например, вычисление эмбеддингов и нормализация текста.

3. Генерация товаров-кандидатов с помощью ML-моделей.

4. Фильтрация кандидатов по наличию на складе.

5. Вычисление фичей (признаков), необходимых для инференса модели ранжирования.

6. Применение бизнес-правил и формирование списка идентификаторов товаров конечной поисковой выдачи.

Отдельно стоит сказать про фильтрацию товаров по наличию. Этот этап максимально приближен к кандидатогенерации, и вот почему: как правило, в наличии на складе находится ¼ товаров от полного ассортимента, и было бы слишком расточительно для ¾ поисковой выдачи вычислять тяжеловесные фичи, необходимые ранжирующей модели. Поэтому в сервисе search мы храним асинхронно обновляемый кеш: для каждого склада подготавливается Quotient filter (альтернатива фильтру Блума). У фильтра есть операции:

• добавления идентификатора товара, который есть в наличии на складе;

• проверки факта наличия ID товара в фильтре.

Quotient filter — вероятностная структура, которая гарантирует отсутствие false-negative срабатываний. То есть если товар добавлялся в фильтр, то он точно будет в выдаче, и с некоторой вероятностью (у нас в прыжке — 0,99) фильтр может выдавать false-positive (товара нет на складе, но фильтр считает, что есть). В итоге получаем компактное хранение информации о наличии товаров порядка 10 КБ на склад и быстрый способ вычисления предиката фильтра.

Оркестратор, получив список товаров, обогащает их идентификаторы различной метой из кеша поверх сервиса catalog для формирования карточки товара на фронте: картинка, название, цена, скидки.

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

Один день из жизни пода ML-сервиса

Какими бы впечатляющими результатами ни обладали ML-модели на этапе обучения, успех их внедрения во многом зависит от эффективности кода, обеспечивающего инференс. Узнаем, кто и как обслуживает ML-модели поискового сервиса Лавки, для этого посмотрим на один день из жизни пода сервиса search: 

Код сервиса поиска написан на С++ с применением REST-подхода и использует опенсорс-фреймворк userver. На схеме есть бургер из ML-моделей, который мы рассмотрим чуть позже. Бургеру на входе нужны фичи для предсказаний. Фичи вычисляются в момент вызова сервиса на основе текста запроса, данных о товарах и пользователе. 

Про товары модели узнают из shard-файла — это бинарный файл, в котором сохраняются предподсчитанные статистики типа числа заказов товара, CTR-ность, покупаемость в определённой геолокации и другие полезные данные.

Пользовательский профиль в форме счётчиков, вычисленных по истории покупок, получаем из быстрого key-value хранилища.

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

На выходе из ML-части все фичи, которые были предвычислены на основе счётчиков и статистик из shard-файла, подсчитанные в момент запроса и записанные в features log через Message broker, уезжают в долгосрочное хранилище — MapReduce Tables (это как раз та часть, которая потом будет использоваться для обучения). 

Кроме конвейера с шард-файлами, существует ещё один: конвейер дообученных DSSM-моделей. DSSM используется для генерации кандидатов, релевантных поисковому запросу. Свежие модели препятствуют деградации качества поиска на новинках в ассортименте Лавки и лучше отдают их на выдаче.

В бургере есть ещё ранжирующая и фильтрующая модели, которые деплоятся в под сервиса процессами CI по требованию разработчиков, например, перед проведением A/B-экспериментов.

Перед тем как нырнуть в ML-модели сервиса поиска Лавки, посмотрим, откуда они берут данные для процессов обучения.

Данные для обучения моделей

Когда пользователь в приложении Лавки кликает на любой товар в поисковой выдаче, открывая его карточку, кладёт в корзину или пролистывает ленту, все его действия отправляются как логи в специальное хранилище User Frontend Logs. Дальше они становятся доступны в подготовленной DWH-таблице User Actions. В этой таблице есть колонка Action Type, в которой видно, что item добавлен в корзину и, например, куплен, а какой-то — пролистан, и пользователь с ним не взаимодействовал. 

Одновременно с этим идёт запрос в бэкенд, где вычисляются фичи на каждый айтем и складываются в долгосрочное хранилище в виде item features. В нём по идентификатору запроса можно будет склеить эти две части и получить датасет, в котором будет описано, как пользователь взаимодействовал с айтемом. Это и будет информацией для обучения новой модели. 

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

Этап обучения делится на три части: собираем датасет, обучаем модель и потом тестируем и валидируем, что получилось хорошо.

Теперь можно перейти к ML-моделям в сервисе поиска Лавки и определению их роли в борьбе за такую поисковую выдачу, которая нравится пользователям.

Ныряем в нору за ML-кроликом 

Валерий Бабушкин в одном из своих видео сравнивал дизайн ML-систем с кроличьей норой: постепенно углубляясь в тему, можно пойти в разные ответвления и нырнуть достаточно глубоко в боковые проходы. Я же попробую не отдаляться в описании далеко в сторону от последовательности обработки запроса, чтобы на практике проверить роль отдельных ML-моделей в формировании релевантной выдачи.

Рантайм-часть сервиса поиска в части ML представляет из себя слоистую структуру в виде бургера. 

На самом верхнем уровне бургера — модели, которые помогают найти релевантные запросу товары. Далее функциональные слои — фильтрующая и ранжирующая формулы.

Сейчас мы рассмотрим принцип их работы, а затем попробуем немного сломать продакшн специальными ключами, отключающими практически любые части бургера моделей. На всякий случай предупрежу: ключики доступны только из админки поискового сервиса Лавки, а не с фронтенда… Поэтому, кстати, скрины будут отличаться от фронтендовых, но сути это не поменяет — проверим на практике, какой вклад вносят разные модели в качество поисковой выдачи.

С чего начинается поиск

Наиболее важный этап подготовки поисковой выдачи — генерация товаров-кандидатов, отвечающих на запрос пользователя. Здесь в ход идут такие технологии, как нейронные сети DSSM и BERT, дистиллированная в DSSM, а также алгоритм BM25.

CartUpdate DSSM (Deep Structured Semantic Models). Это двухбашенная нейронная сеть, в архитектуре которой одна башня отвечает за формирование эмбеддинга запроса, а вторая, документная, — эмбеддинга товара.

Схематично структуру обучения сети можно показать так:

[Query] —> [ Query Tower ]          [Document] —> [ Document Tower ]
                |                               |
            [Query Embedding]         [Document Embedding]
                        \              /
                       [Считаем сходство]

При обучении модель получает на вход множество пар: запрос и купленный по нему товар. Поисковый запрос превращается в N-мерный числовой вектор (эмбеддинг) в запросной башне нейросети. То же самое происходит с товаром — его название, описание, бренд и другие характеристики передаются на вход документной башне. Вычисляется косинусное сходство между векторами запроса и товара. Для обучения используется loss-функция, оптимизирующая веса обеих частей сети так, чтобы релевантные пары «притягивались», то есть имели большое косинусное сходство, нерелевантные — «отталкивались».

Товарные эмбеддинги в офлайне обсчитываются обученной документной башней DSSM и складываются в HNSW-индекс, который раз в несколько часов подкладывается в поды сервиса в shard-файле. В момент, когда вы ищете что-то в Лавке, запросной частью нейросети вычисляется эмбеддинг текста запроса и выполняется быстрый поиск ближайших соседей к нему в HNSW-индексе.

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

BERT → DSSM. Модель BERT (Bidirectional Encoder Representations from Transformers), предварительно дообученная на ассортименте Яндекс Лавки и дистиллированная в DSSM, помогает в глубоком понимании семантики текста. Это улучшает качество эмбеддингов и помогает находить товары по нетривиальным запросам, в тексте которых не встречаются слова из метаинформации о товаре.

BM25. BM25 — это алгоритм, основанный на tf-idf (term frequency-inverse document frequency), который оценивает релевантность текста документа на основе частоты термов в запросе и документе. Термы, например буквенные триграммы «кра-рас-асн-сны-ный» и словарные биграммы «красный банан», используются как ключи заранее подготовленного инвертированного индекса, а значения — это взвешенный по частоте список документов, в которых терм встречается.

На этом рисунке схематично показаны модели, участвующие в генерации кандидатов по поисковому запросу «красный бан».

Какая кандидатная модель лучше?

Пока мы не опустились на нижние слои бургера с фильтрующей и ранжирующей моделями, давайте посмотрим, что будет с поиском Лавки, если бы он содержал только одну из моделей кандидатогенераторов.

Довольно сложный запрос «овощи для борща» предполагает, что модель должна понимать семантику запроса. На рисунке ниже приведён топ кандидатов от BM25, CartUpdate DSSM и BERT DSSM, упорядоченный по убыванию релевантности товара запросу по мнению каждой модели.

Выдача BERT DSSM как самой умной модели выглядит достаточно хорошо: если бы я захотел приготовить себе суп, то взял бы первые два товара из этого списка. Выдача BM25 выглядит странно, не правда ли? Но теперь вы знаете, почему так происходит. Модель CartUpdate DSSM справилась с ответом превосходно — почти вся выдача для пользователя, который хочет приготовить борщ, пойдёт в корзину.

Запрос «полезные перекусы» не оставляет шансов BM25 — полнотекстовый поиск не способен на такое, но нейронные сети справляются довольно неплохо, причём субъективно BERT DSSM выдаёт более полезные перекусы.

Складывается впечатление, что BM25 запросто может быть замещён двумя другими моделями. Но это не так. Модели DSSM обладают инертностью, так как требуют этапа обучения. Например, поищем появившийся пару дней назад товар «Арбуз бруски „Из Лавки“, 500 г». Обе нейронные сети его не нашли, а BM25 справился блестяще.

Почему так произошло? Дело в том, что BERT DSSM была обучена однократно и команда поиска решила пока не конвейеризировать её дообучение, так как неочевидны выгоды от этого предприятия — ресурсозатратного и по человеческим ресурсам, и по вычислительным. Всё же для новых наименований товаров вычисляются эмбеддинги документной башней даннной модели и попадают в shard-файл, что позволяет вытягивать новинки этой моделью.

Ещё характерный пример поиска нового товара и бренда «Огурцы Globus»:

Алгоритм BM25 успешно находит нужное на первом месте. Остальные две модели стоят в сторонке именно из-за инерции. Интересно, что CartUpdate DSSM хотя бы другие солёные огурцы нашла, а BERT DSSM не справилась с задачей, потому что не дообучается на новом ассортименте.

Из этих примеров видно, что модели дополняют друг друга, и когда не справляется одна, ей помогают другие.

От верхнего слоя бургера моделей с кандидатогенераторами перейдём к нижним слоям — фильтрующему и ранжирующему. 

Фильтрация и ранжирование кандидатов

Товары-кандидаты сгенерированы в одно множество, теперь задача моделей BERT DSSM, CartUpdate DSSM и BM25 — отскорить все элементы этого множества, чтобы каждый получил свою оценку. 

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

В поиске CartUpdate DSSM в своих эмбеддингах больше зашивает знаний о покупаемости товаров. BERT DSSM — о смысловой нагрузке текста. BM25 хорошо улавливает общие части слов в запросе и названии товара.

Все оценки поступают главному судье (продолжая аналогию с дипломной комиссией — председателю). В роли председателя в нашем сервисе выступает CatBoost — модель, обученная на скорах от кандидатогенераторов отличать релевантные товары от нерелевантных. Мы ещё называем её фильтрующей формулой. В качестве таргета при её обучении используется оценка релевантности пар «запрос — товар» по шкале от rel+ до non-rel. Красный банан на первой позиции по запросу «красный бан» — это rel+, так как тут есть совпадение искомого товара и его характеристики.

Эту разметку делают люди и роботы, причём последние догоняют по качеству разметку людей! Для поискового сервиса этап фильтрации невозможно переоценить, ведь появление «стьюпидов» сильнее всего бьёт по его репутации. Например, вы хотите купить набор «Лего» своему любимому племяннику, а вместо этого делаете открытие, которое теперь невозможно забыть: в Лавке продаётся говяжье лёгкое для собак. 

На самом деле это некритичный кейс. Куда менее приятно, когда по запросам «без глютена», «халяль», «постное» поиск выдаёт товары, которые не соответствуют этим характеристикам.

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

Но вернёмся к последнему этапу ML в поиске — ранжированию. Оно предполагает, что самые вероятные к покупке товары попадут в топ выдачи. Например, ваш любимый сыр, который вы чаще всего покупаете, будет в верхней части экрана. Здесь тоже работает CatBoost, но теперь ранжирующий. А для того чтобы выдача стала персонализированной, при обучении на вход ему подаются персональные фичи пользователя. Это заранее подсчитанные статистики по истории покупок. В момент поискового запроса они вытаскиваются из key-value хранилища kv-user-storage и подаются в модель для предсказания ранжирующего скора.

Такой эксперимент может сделать каждый: поищите что-нибудь в Лавке под своим логином и во вкладке инкогнито — увидите разницу.

Выходим из ML-норы и оглядываемся: выводы из статьи

Качественный поиск в e-commerce — это не набор случайных моделей, а продуманная, инженерно и достаточно сложно устроенная ML-система, где каждый слой и компонент вносит свой вклад. Ключевые уроки для тех, кто интересуется развитием или построением поисковых сервисов и рекомендательных систем:

• Множественность моделей — сильная сторона. Нейронные сети (DSSM, BERT) превосходно справляются с пониманием смысла запроса и сложных пользовательских сценариев, а более «традиционная» BM25 остаётся незаменимой для поиска новых товаров и брендов, которые не охвачены нейронками из-за инертности выкаток и дообучения.

• Отлаженные конвейеры поставки товарных данных, пользовательских событий и истории, дообученных моделей — неотделимы от качества поиска. Если происходит разрыв цепи, то неминуема деградация сервиса.

Поиск в Яндекс Лавке прошёл путь от простых алгоритмов поиска по названию до сложной многоуровневой ML-системы, в которой каждая часть — от генерации кандидатов до ранжирования — играет важную роль в обеспечении релевантной и удобной поисковой выдачи для пользователя.