Привет! Это Николай Анохин из команды AI VK. В этой статье расскажу про кеширование кандидатов — подход, который делает рекомендательную систему заметно менее требовательной к железу и при этом не трогает качество выдачи. Механизм уже работает в рекомендациях VK Видео и VK Клипов.
Зачем понадобилось кеширование кандидатов
Каждый раз, когда пользователь отправляет запрос, рекомендательная система выполняет большой объём вычислений. Сначала она собирает кандидатов — айтемы, которые потенциально подойдут пользователю. Источники у них разные:
айтемы, похожие на недавние интересы пользователя;
айтемы от знакомых авторов;
свежие айтемы;
промо;
айтемы продуктовых квот.
Затем кандидаты проходят ранжирование, и уже из них формируется итоговая выдача. Схема даёт качественные рекомендации, но требует значительных вычислительных ресурсов: чем больше кандидатов доходит до ранжирования, тем выше latency — задержка обработки запроса — и тем больше потребление CPU. Поэтому крупные рекомендательные сервисы упираются в железо.
Стоит уточнить, откуда берётся эта зависимость. Ранжирование устроено так, что модель считает скор для каждого кандидата по отдельности, поэтому его стоимость растёт линейно вместе с числом объектов на входе. Сто лишних кандидатов в одном запросе — это сто лишних проходов модели, умноженных на весь поток запросов сервиса. При этом в выдачу попадают единицы: остальные кандидаты нужны только для того, чтобы модель могла выбрать из них лучших.
Отсюда естественный вопрос: можно ли сократить число кандидатов на входе в ранжирование так, чтобы качество рекомендаций не пострадало?
Гипотеза простая. Соседние запросы одного пользователя часто похожи друг на друга: между двумя открытиями ленты человек не успевает полностью поменять свои интересы. А значит, большая часть сильных кандидатов для следующего запроса уже была найдена на предыдущем. Если это так, их можно один раз вычислить, сохранить на короткое время и переиспользовать в нескольких последующих запросах.
Из чего собирается выдача: стримы и селекторы
Прежде чем говорить о кеше, нужно описать два уровня, на которых устроен отбор кандидатов.
Верхний уровень — стримы. Наш рекомендер разбит на несколько независимых стримов: один отвечает за основной персонализированный контент, другой — за свежие объекты, третий — за контент от важных авторов, четвёртый — за промо и продуктовые гарантии. Каждый стрим сам собирает кандидатов и сам их ранжирует, а результаты в конце объединяются в единую выдачу.
Нижний уровень — селекторы кандидатов, которые работают внутри стримов. Именно селектор ходит в источник данных и приносит оттуда список айтемов. Дальше по тексту они встречаются постоянно, поэтому разберём их отдельно.
Какие бывают селекторы
Селекторы удобно разложить на несколько типов — от того, к какому типу относится селектор, зависит, можно ли заменить его кешем.
Item-to-item. Ищут айтемы, похожие на те, с которыми пользователь недавно взаимодействовал.
Source-to-item. Отбирают айтемы от авторов, к которым пользователь проявлял интерес.
Векторные. Работают через HNSW-индексы по эмбеддингам. HNSW — это структура для быстрого приближённого поиска ближайших соседей в векторном пространстве: она строит многослойный граф, по которому можно добраться до похожих объектов за логарифмическое время вместо полного перебора базы.
Неперсонализированные. Работают на основе снапшота данных, который периодически обновляется, и выдают один и тот же набор всем пользователям в рамках контекста.
Продуктовые. Отвечают за специальные пулы — прогрев, промо и редакционные подборки. Кандидатов приносят немного, но эти кандидаты обязаны попасть в выдачу из-за продуктовых обязательств.
Разница между типами определяет и стратегию кеширования. Неперсонализированный селектор на снапшоте подходит для замены кешем лучше всего: его выдача и так меняется редко. Тяжёлые персонализированные селекторы — главная цель оптимизации, потому что именно они съедают основную долю вычислений. А обязательные продуктовые селекторы кешем заменять не стоит вовсе: риск нарушить гарантии выше, чем выигрыш на нескольких десятках кандидатов.
Почему кандидатов можно переиспользовать
Гипотезу про похожесть соседних запросов мы проверили на данных. Если взять два подряд идущих запроса одного пользователя, внутри одного стрима система часто находит почти один и тот же набор кандидатов — и при повторном ранжировании выполняет ту же работу второй раз.
Это видно на графиках ниже. Каждая точка соответствует паре последовательных запросов: по оси X показано время между запросами в секундах, а по оси Y — доля пересечения кандидатов (слева) и корреляция Спирмена между списками кандидатов (справа).
Читать эти графики нужно так: они не разрешают пользоваться одним набором кандидатов сколь угодно долго, а показывают, на каком горизонте переиспользование безопасно. На коротком интервале кандидаты достаточно стабильны. На длинном набор устаревает: пользователь совершает новые действия, появляются новые сигналы, меняется контекст, да и свежие объекты должны попадать в выдачу.
Полного совпадения между соседними запросами не бывает, и это нормально. Часть источников обновляется независимо от пользователя: появляется свежий контент, пересчитываются снапшоты, меняются продуктовые пулы. Плюс сам пользователь за время между запросами успевает что-то посмотреть или пролистать. Поэтому вопрос стоит не в том, совпадают ли наборы кандидатов, а в том, достаточно ли велика их пересекающаяся часть, чтобы на ней сэкономить.
Отсюда требование к кешу: он должен быть небольшим и короткоживущим. Задача — ненадолго сохранить только ту часть кандидатов, которая с высокой вероятностью снова пригодится.
Идея: кешировать top-k кандидатов
Базовая схема выглядит так. После обычного запроса мы берём из каждого стрима top-k кандидатов с самым высоким скором и записываем их в Redis.
Смысл в том, что на следующем запросе большую часть отбора можно не повторять. Набор кандидатов собирается компактным, из трёх частей:
кандидаты из кеша;
кандидаты из реактивных селекторов — облегчённых версий обычных, которые ловят свежие сигналы пользователя;
кандидаты из обязательных селекторов, которые нельзя заменить кешем.
Так мы перестаём заново ранжировать значительную часть кандидатов с низким скором. Именно они дают заметную долю вычислительной нагрузки, хотя в итоговую выдачу попадают редко. При этом кеширование не отменяет ранжирование: кандидаты из кеша всё равно скорятся заново в текущем контексте. Меняется не финальная модель, а количество объектов, которые до неё доходят.
Здесь стоит упомянуть два ключевых параметра, которые требуют баланса:
Размер кеша k. Чем он меньше, тем меньше кандидатов попадает в ранжирование и тем выше экономия CPU. Но при слишком маленьком k хороших кандидатов может не хватить — особенно если пользователь быстро исчерпает сохранённый список. В продуктовых метриках это проявится падением вовлечённости, конверсии или времени потребления.
TTL кеша. Длинный TTL повышает долю запросов, которые удаётся обслужить из кеша. Но рекомендации при этом становятся менее реактивными. Короткий TTL безопаснее для качества, зато и экономия меньше.
Проще говоря, слишком маленький k или слишком большой TTL бьют по качеству рекомендаций, а слишком большой k или слишком короткий TTL съедают выигрыш в производительности.
Реактивные селекторы: чтобы кеш не делал выдачу инертной
Главный риск кеширования в том, что рекомендации перестают замечать свежие действия пользователя. Человек посмотрел новое видео, подписался на автора, заинтересовался новой темой — а система продолжает работать со списком, который собрали до этого. Поэтому в кешированном режиме рядом с кешем всегда работают реактивные селекторы: облегчённые версии обычных, которые учитывают только новые сигналы, появившиеся после записи кеша.
Реактивность нужна разная, в зависимости от типа селектора:
item-to-item — к новым пользовательским событиям;
source-to-item — к новым авторским сигналам.
Выигрыш здесь именно в объёме работы. Полный item-to-item-селектор идёт по всей истории взаимодействий пользователя и для каждого объекта из неё ищет похожие. Реактивная версия берёт только те события, которые произошли после записи кеша, — а их за короткий TTL набирается немного. Логика та же, вход на порядок меньше.
Состав селекторов в кешированном режиме приходится настраивать аккуратно, и ошибиться можно в обе стороны. Если добавить слишком много кандидатов из реактивных селекторов, выигрыш от кеширования уменьшится — мы просто вернём в ранжирование то, что убрали. Если, наоборот, не включить в кешированный режим часть селекторов, можно нарушить продуктовые гарантии.
Универсальной конфигурации здесь нет: она зависит от продуктовой специфики конкретного рекомендера. Подбирать её приходится A/B-экспериментами — мы прогоняли через тесты размер кеша, длину TTL и состав селекторов в кешированном режиме, а следили при этом одновременно за экономией CPU и за продуктовыми метриками.
Как устроена реализация
Технически этап отбора кандидатов работает в двух режимах:
Обычный, без кеша. Включается, когда воспользоваться кешем нельзя. Такое бывает по трём причинам: для данного пользователя и контекста кеша ещё нет, он протух по TTL или сохранённые кандидаты уже исчерпаны. Стрим в этом случае работает как раньше: запускает полный набор селекторов с обычными квотами.
Кешированный. Включается, если для пользователя и текущего контекста нашёлся свежий кеш. Для него используется отдельная конфигурация селекторов: в неё добавляется селектор cached_candidates, а тяжёлые селекторы заменяются облегчёнными версиями — например, вместо полного item-to-item-селектора работает его реактивная версия.
Доля запросов, которые попали во второй режим, и есть hit rate — основная метрика эффективности механизма: она показывает, на какой части трафика мы вообще экономим.
Ключ кеша состоит из пользователя и контекста рекомендации — типа рекомендера, платформы и поверхности продукта. В значении лежат timestamp записи и наборы кандидатов по каждому стриму: идентификаторы айтемов вместе с их скорами.
Один кандидат занимает около 20 байт плюс служебные расходы. Общий же объём памяти Redis определяется тремя вещами: размером k, значением TTL и количеством контекстов, которые мы кешируем. Первое задаёт длину каждого списка, второе — сколько списков одновременно живёт в памяти, третье — сколько списков заводится на одного пользователя.
Результаты
На момент написания статьи на кешированный режим удалось перевести два рекомендера — VK Видео и VK Клипы. Экономию мы получили за счёт вывода реплик рекомендера, поэтому сократилось потребление не только CPU, но и остальных ресурсов: RAM, NVME, LAN. Платой стало масштабирование кластеров Redis в MDB — часть сэкономленного железа ушла туда.
Важно понимать, что перевод рекомендера на кеш — это не включение флага. Под каждый рекомендер заново подбирается своя конфигурация: какие селекторы заменяются кешем, какие получают реактивные версии, какие остаются нетронутыми, а также значения k и TTL.
Размер выигрыша сильно зависит от параметров конкретного рекомендера, и здесь стоит объяснить, почему цифры получаются разными. Первая причина — доля некешируемого трафика. В VK Видео половину RPS даёт поверхность doc2doc, то есть блок «Смотрите также» под видео. Кандидаты для него подбираются к конкретному ролику, а не к пользователю, поэтому ключ «пользователь плюс контекст» для такой поверхности не работает: сохранённый список пришлось бы заводить на каждую пару «пользователь — видео», и переиспользовать его было бы почти негде. Вторая причина: в разных рекомендерах разное количество кандидатов в некешированном режиме, и там, где их и так немного, сокращать особо нечего.
Вывод
Кеширование кандидатов убирает из рекомендательной системы повторную работу и при этом не изменяет основную модель ранжирования. Мы сохраняем сильных кандидатов после запроса, переиспользуем их в течение короткого времени и дополняем свежими сигналами от реактивных селекторов.
Главная инженерная идея не в том, чтобы кешировать рекомендации целиком. Кешируется только результат отбора кандидатов, и в кеш попадают лишь k лучших. Такой список достаточно короткий, чтобы экономия была заметной, и достаточно стабильный на времени жизни кеша, чтобы переиспользование оставалось безопасным. Итоговая выдача при этом всё равно строится с учётом актуального контекста запроса.
А сэкономленное железо — это ресурс, на котором можно запускать новые рекомендательные механики.