«Баннерная крутилка» — один из самых высоконагруженных сервисов в Яндексе. Он умеет переживать 700 тысяч RPS, а иногда и больше. Каждый раз, когда приходит запрос, крутилка должна просмотреть базу из миллиарда документов и выбрать из них самые релевантные для пользователя. При этом выдерживаются весьма жесткие временные рамки: 99% всех запросов обрабатываются менее чем за 200 миллисекунд.

Какими принципами стоит руководствоваться при построении подобных высоконагруженных систем? Как устроены стадии отбора документов? Какое участие в ранжировании принимает ML? Обо всём этом на недавнем мероприятии для разработчиков в Ереване рассказал Артём Ваншулин, руководитель разработки ранжирования в команде баннерной системы. Сегодня мы делимся с сообществом текстовой версией его доклада. Передаём ему слово.

Как работают рекомендательные системы

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

Посмотрим на схему отбора документов, которые надо показать пользователю. Она применима к большинству сервисов рекомендаций — поиску, рекламе, ленте в соцсетях или на сайтах.

Сначала в систему поступает запрос на показ документов — для нас это рекламные объявления. Чтобы показать пользователю самые подходящие из документов, нужно выбрать наиболее релевантные и отранжировать их. Задача подбора релевантных кандидатов сама по себе очень интересна и сложна, она заслуживает отдельной статьи, не будем погружаться в детали. О том, как в целом это сделать, рассказывали мои коллеги в этой  лекции.

Когда мы собрали базу релевантных документов, начинается задача ранжирования. Обычно она проходит в несколько фаз, которые различаются по сложности и объёму обрабатываемых документов. К этим стадиям вернёмся чуть позже.

 В рамках задачи ранжирования есть стадия фильтрации, где работает бизнес‑логика. Например, нужно отфильтровать документы, которые нельзя показывать определённому пользователю — какой‑нибудь контент 18+. Или рекламодатель ограничил список доменов, где он желает показываться.

У рекомендательной системы «баннерной крутилки» есть ещё одна, специфическая стадия — аукцион. Во время этой стадии мы не просто ранжируем документы и выбираем самые релевантные, но ещё и определяем честную цену за показ документа на этой позиции: ставку рекламы — кто сколько готов заплатить за показ позиции именно этому пользователю на этой странице в этот момент времени. Но на аукцион отвлекаться тоже не будем: скажу только, что не всегда выше в ранжировании оказывается тот, кто предложил самую большую ставку. Ставка означает, что мы будем показывать объявление данного рекламодателя по предложенной им сумме и с указанными ограничениями.

В докладе я сконцентрируюсь на выделенных стадиях отбора релевантных документов.

Базовый принцип ранжирования

Главный принцип процесса обработки документов: много объектов — лёгкие операции, мало объектов — тяжёлые операции. Что это значит?

• Никаких тяжёлых ML‑моделей на ранних стадиях ранжирования, где много объектов — только самые лёгкие операции.

• Отсекать как можно больше объектов и как можно раньше.

• Нижние стадии ранжирования — «глупые»: нельзя позволять им выкидывать хорошие документы, иначе потом ранжировать будет нечего. Чем выше стадия ранжирования — тем меньше объектов в ней участвует. А значит, тем более тяжёлые операции мы можем выполнять.

Как облегчить первые стадии ранжирования

Шардирование

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

• Горизонтально масштабироваться по документам: мы не можем обрабатывать все документы на одной машине — они туда не влезают.

• Масштабироваться ещё и по CPU. Мы выполняем работу параллельно и, соответственно, сокращаем время ожидания и влезаем в тайминги.

Как лучше это реализовать? Можно попробовать сделать шардирование по городам — распределить по разным шардам документы, которые относятся, например, к Москве и Еревану. Но Москва гораздо больше, и её шард будет перегружен — так называемая проблема горячего ключа.

 Однако даже если найти два города, близких по количеству рекламных объявлений, то и здесь не всё может быть гладко. Особенно если города относятся к разным часовым поясам. Люди обычно более активны днём, а ночью спят. В итоге получится, что в разное время суток один шард будет сильно загружен, а другой — недозагружен. А хотелось бы более равномерно распределять ресурсы между шардами в течение дня и жить с меньшими мощностями: не держать большой запас железа из‑за неравномерности нагрузки.

 Экономим ресурсы — экономим деньги. Чтобы сделать шардирование более равномерным, мы используем инкрементальный айдишник и отображаем элементы в шарды по правилу shard=Id% NumberOfShards (главное, чтобы у каждого элемента было равновероятное попадание в любой шард).

Какое количество шардов считать оптимальным — 5, 10, 50 или 100? Или вообще каждому документу нужен свой шард? В последнем случае мы будем отвечать на запрос супербыстро, но это будет стоить просто невообразимое количество денег. Каждый шард — это fixed cost, который мы платим за один инстанс — обработку запроса, работу по сети и так далее.

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

 Итого: нужно соблюдать баланс между скоростью и стоимостью обработки. То, каким он будет для вас, зависит от задачи: где‑то важнее latency, где‑то — пропускная способность (меньше шардов — больше реплик), а где‑то требуется сэкономить ресурсы.

Кластеризация объектов

Взгляните на объекты с которыми вы работаете: можно ли выделить в них иерархию или как‑то сгруппировать их — по доменам, категориям, паблишерам? Работайте с группами объектов (а лучше с их иерархией), на ранних стадиях — с самыми высокоуровневыми. Так вы сможете отсекать сразу целый кластер объектов, которые вам не подходят, не разбираясь с каждым по отдельности.

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

Ленивая материализация объектов 

Попробуйте отсортировать всё, с чем работаете, по какому‑либо value. Двигайтесь по списку в порядке убывания приоритета до тех пор, пока объектов не станет достаточно. В этот момент процесс обработки можно завершить и переходить к следующей стадии ранжирования для «выживших» кандидатов. Таким образом мы можем сэкономить ресурсы, не обрабатывая нерелевантных кандидатов.

Растянутая во времени инициализация

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

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

На графике легко заметить, в какой момент мы внедрили ленивую инициализацию: именно тогда все линии падают вниз.

 За счёт ленивой инициализации мы выиграли 5% ёмкости. В наших цифрах это большое количество железа.

Протокольные перекладывания

Многие разработчики, в том числе и мы, строят микросервисную архитектуру. Объясню, как это выглядит. Рассмотрим:

• сервис A;

• сервис B;

• представление объекта в сервисе А (например, какой‑то класс);

• представление объекта в сервисе B.

Допустим, нам нужно переслать объект из первого сервиса во второй. Мы не отправлять классы по сети, но можем использовать для этого специальные протоколы: например, Protobuf и Flatbuffers.

Тогда мы:

• берём данные из одного объекта и перекладываем их в Protobuf;

• отправляем их по сети;

• принимаем данные в микросервисе B;

• десериализуем в Protobuf;

• из Protobuf формируем понятные коду классы.

На всё это требуется ёмкость. Но можно пойти другим путём — использовать непосредственно объект протокола. Для этого мы повсеместно внедряем Flatbuffers: так практически нет затрат на десериализацию. В примере про микросервисы A и B, это поможет сэкономить CPU в микросервисе B. Кроме того, можно работать с объектами прямо в Flatbuffers, не перекладывая их в классы выбранного языка программирования.

ML в ранжировании

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

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

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

Посмотрите на эту картинку с флеймграфами:

Флеймграфы — это некий способ профилирования того, чем занята ваша программа. О том, как они помогают нам оптимизировать программы в продакшне, уже писали на Хабре На картинке слева можно заметить, что стадия подготовки фичей занимает почти 10% ёмкости. А на картинке справа видно, что применение модели на посчитанных фичах обходится уже в 4,8%. Итого, подготовка фичей занимает в два раза больше ресурсов, чем само применение модели.

Раз мы заговорили про фичи, давайте вспомним, какими они вообще бывают.

Какие бывают фичи для моделей

Классифицировать фичи можно по‑разному. Здесь предлагаю группировать их по способу подготовки:

• Фичи, которые связаны с пользователем То, что касается его пола, возраста, интересов. Такие фичи мы можем посчитать один раз на запрос и использовать для всех кандидатов.

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

• Фичи про взаимодействие пользователя и кандидата. Самые неприятные и жгучие. Например, как именно взаимодействовал с этим документом пользователь: видел ли он его, лайкал ли автора документа, интересовался ли тематикой.

Почему третий тип фичей я назвал неприятными? Потому что их нужно считать для каждого документа и именно во время запроса. Допустим, пользователь ввёл запрос [конференция Яндекса], а находится он в Москве. Ему можно показать конференцию в Ереване, но более релевантно будет рассказать о будущих конференциях Яндекса в Москве. Эта фича очень дорогая, потому что мы не можем подготовить её предварительно.

Так как же применять тяжёлые нейросетевые модели в рантайме и платить за это как можно меньше?

Как быстро и недорого применять нейросети в рантайме

Представим, что у нас есть нейросеть — большой жёлтый прямоугольник. Мы учим её попадать в какой‑то таргет, например, клик пользователя. Но фичи и саму нейросеть устраиваем так, что фичи от документа попадают в одну часть нейросети, а поисковый запрос пользователя и данные о нём — во вторую часть. И только на самом последнем этапе происходит обучение таргета — получается позднее связывание.

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

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

Часть нейросети, связанная с документом, ничего не знает про текущий запрос, а все свои знания собирает в вектор (embed) документа, который мы считаем в офлайне. А вторая часть ничего не знает про документы. Все свои знания про пользователя, запрос и рантайм‑составляющие она аккумулирует в векторе запроса, который можно вычислить один раз в рамках запроса.

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

Какие бывают стадии ранжирования

Описанная модель очень хорошо подходит для первой стадии ранжирования (L1), где очень много кандидатов. Эту стадию хотелось бы выполнять качественно, но с ограниченными ресурсами.

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

Дальше мы выбираем топ кандидатов — отсекаем некоторое n с каждого шарда и отправляем уже на одну машину, которую называем Метой. Она агрегирует топы по всем шардам, а потом из общего списка выбирает некоторые подмножества. Если с каждого шарда прилетело, например, по 100 документов, из всего множества мы выберем 300 лучших. И уже лучшие документы отправим в самую тяжёлую стадию ранжирования — L3.

На стадии L3 мы можем позволить себе самые классные модели и тяжёлые фичи, потому что здесь уже немного документов. Недавно мы добавили сюда нижний пункт в схеме — нейросети для кандидатов. В этом проекте мы в рантайме делаем инференс на GPU для всех документов, которые пришли на L3 стадию. Одна GPU держит миллион кандидатов в секунду, то есть в рантайме обрабатывает миллион документов каждую секунду. По‑моему, неплохо.

И ещё раз о ключевых принципах ранжирования 

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

• Много объектов — лёгкие операции, мало объектов — тяжёлые операции.

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

• Анализируйте объекты, с которыми работаете: старайтесь выделить в них иерархию или сгруппировать их по какому‑то признаку.

• Ленивая материализация и растянутая во времени инициализация объектов облегчают первые стадии ранжирования.

• Избавляйтесь от протокольных перекладываний, используйте объект протокола, например, Flatbuffers.

• Затраты на применение ML‑моделей складываются из затрат на инференс и затрат на подготовку фичей.

• Иногда простое скалярное произведение может заменить тяжёлые модели.

На этом, пожалуй, всё.