Подбор рекламных объектов в DSP: сколько стоит найти нужный баннер за сто миллисекунд

Мне давно было любопытно разобраться, как в RTB (Real Time Bidding — аукционная закупка рекламы в реальном времени) устроена хайлоад часть. Задача выглядит сложной: от площадок идет поток запросов на покупку рекламы (бид-реквестов), на стороне рекламного движка есть каталог рекламных объектов (кампаний и баннеров в них) со своими таргетингами, и на каждый входящий запрос надо успеть найти подходящие объекты, посчитать ставку и ответить. На весь обмен с биржей дается порядка ста миллисекунд, и в них должно поместиться все сразу — сеть в обе стороны, разбор запроса, подбор объекта, расчет ставки, сборка ответа. То есть на сам подбор остается еще меньше времени.

А еще такая система должна быть подвижной в обе стороны по нагрузке. Трафик у поставщиков не постоянен, он гуляет и в течение суток, и от поставщика к поставщику, так что держать максимальный конфиг под пиковую нагрузку круглосуточно нет смысла. Значит нужна возможность добавлять и убирать мощности, понимая при этом, сколько пропускной способности дает каждая добавленная единица. Спроектировать такое — интересная инженерная работа. Ну это я, как продакт работающий в этой сфере, так считаю :-)

В каждой компании где я работал с рекламными движками (DSP – Demand Side Platform) были свои кастомные решения, свое легаси – не везде можно найти обоснование каждому решению, поэтому мне всегда было интересно, как это устроено у других. Так что я решил разобраться, какие вообще бывают решения — чтобы лучше понимать возможности и ограничения, с которыми имеют дело мои разработчики. Это важно, потому что от выбора хранилища напрямую зависит сколько трафика мы физически способны обработать не отъехав, и что случится (а точнее что мы можем быстро сделать), если завтра нужно будет попросить у поставщика (в рекламе он называется SSP - Supply Side Platform) вдвое больше.

Поэтому вся статья — это конспект того, какие способы я нашел и какие выводы из этого смог сделать.

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

Что происходит в биддере*, пока идут эти сто миллисекунд

* биддер — это бэкенд DSP, который на каждый входящий запрос решает, участвовать ли в аукционе, и если да — каким баннером и по какой цене

По сути порядок всегда один:

1. предложение купить рекламный показ (он же бид реквест) приходит в биддер от биржи (она же SSP).

2. запрос разбирается (там большой JSON объект)

3. из каталога рекламных объектов выбираются те которые имеют подходящие таргетинги <— это этап который я хочу рассмотреть в этой статье

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

5. ответ со ставкой уходит в SSP Если подходящих кандидатов не нашли на шагах 3-4, то DSP сразу отвечает 204 и на этом прощается.

Пункты 1, 2, 5 – это по сути оверхеды: разбор входящего JSON на несколько килобайт, сборка ответа, работа с сетевым соединением, системные вызовы. В сумме это порядка ста микросекунд процессорного времени плюс сама сеть до биржи. Эти шаги не зависят от способа хранения и подбора рекламных объектов, поэтому я их буду игнорировать в этой статье.

Условия сравнения

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

• Нода: 8 vCPU, 32 GB памяти, без GPU. Под данные таргетингов доступно не все: операционная система, сам процесс биддера, буферы, сетевые соединения. Считаем, что полезных остается около 24 GB.

• Трафик: два сценария — 50 и 200 тысяч запросов в секунду.

• Каталог: 500 тысяч рекламных объектов(дальше для краткости — баннеров), принадлежащих 20 тысячам кампаний.

• Таргетинги: у каждой кампании свой список разрешенных баннерных мест примерно на 5 тысяч идентификаторов и свой список запрещенных доменов примерно на 30 тысяч.

• Бюджет на подбор: 10 миллисекунд из ста. Остальное уходит на сеть, разбор запроса, расчет ставки, применение ML моделей и сборку ответа.

Конкретно списки запрещенных доменов такого размера встречаются не каждый день, но огромные списочные таргетинги по строковым значениям встречаются часто и поиск по ним может быть ресурсоемким, поэтому рассмотреть такое точно нужно – просто в рамках этой статьи назовем этот список именно доменами. Порядки при этом вполне рыночные. Google разрешает указать в таргетинге до 10 тысяч идентификаторов паблишеров. LinkedIn держит потолок в 100 тысяч доменов на список запрещенных. Xandr отдает до 100 тысяч почтовых индексов в списке и до 100 списков на рекламную кампанию. DV360 ограничивает кампанию 10 тысячами локаций, причем целый список локаций считается там за одну позицию.

Хранение данных рекламных кампаний

Чтобы сравнивать разные способы хранения, сперва нужно оценить размер того, что будет храниться. Одно значение, хранимое строкой в хеш-множестве, обходится примерно в 60 байт: сам домен – это 15–25 символов, плюс заголовок строки, плюс накладные расходы таблицы на ячейку. Точная цифра зависит от языка и структуры, но порядок примерно такой. Дальше список запрещенных на 30 тысяч доменов — 30 000 × 60 = 1,8 мегабайта. Список площадок на 5 тысяч — 5 000 × 60 = 0,3 мегабайта. Итого 2,1 мегабайта требуется для хранения списков на каждую рекламную кампанию.

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

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

Это те способы обсуждения которых я смог найти:

• Внутри рекламного объекта. Списки в виде строк хранятся вместе с объектом.

• Ссылкой. Списки живут отдельными сущностями, объекты ссылаются на них по идентификатору. Так делают, например, Xandr и DV360.

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

Теперь можно попробовать оценить сколько займет наш целевой объем в 500 тысяч рекламных объектов (а точнее их списков) при разных способах хранения, с учетом свободной памяти на ноде около 24 ГБ:

• Внутри рекламного объекта: 500 тысяч × 2,1 МБ — около 1,05 терабайта. Сорок четыре ноды нужны только для того, чтобы данные куда-то легли. Не представляю как можно было бы успеть провести подбор баннеров из такого объема.

• Ссылкой: уникальных списков не 500 тысяч — по числу баннеров, а 20 тысяч — по числу кампаний. 20 000 × 2,1 МБ — это 42 гигабайта, плюс сами баннеры. Две ноды.

• Инвертированно плюс словарь: Здесь считать надо не списки, а связи. Пар «кампания + значение» около 700 миллионов: 20 тысяч кампаний на (30 + 5) тысяч значений в списках у каждой. Идентификаторы кампаний умещаются в диапазон до 65 тысяч, поэтому в сжатом множестве каждая связь занимает два байта — итого 1,4 гигабайта, плюс сами баннеры. Одна нода.

Здесь видно насколько способ хранения влияет на потребление ресурсов – при одних и тех же данных разброс от одной ноды до 40+.

Способы подбора

Способ 1. Общая реляционная база

SQL знают все, баннеры с таргетингами ложатся в таблицы без насилия, а условия отбора — ровно то, для чего язык запросов придуман. Тем более что у крупных маркетплейсов тот же PostgreSQL спокойно держит большие нагрузки — но там запросы однообразные и ложатся на индексы, а здесь каждый запрос проверяет десяток разнородных условий. Разработчики без опыта в RTB могут недооценить эту разницу. Пока трафик не начал кратно расти, оно действительно работает.

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

Еще одно неудобство возникающее с хранением списка баннеров в SQL – это непрозрачность подбора. Запрос един и команда не может отследить на каких этапах подбор отваливается чаще, а это нужно как для отладки, так и для обсуждения с SSP того какого трафика команде от них нужно больше, а какого меньше. Это можно попытаться решить какими-то дополнительными конструкциями, которые и без того монструозный запрос увеличивают в разы, но на фоне остальных проблем это просто не имеет смысла.

Способ 2. Встраиваемая база на каждой ноде

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

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

Логировать точки отказа при подборе этот способ также не позволяет — запрос по-прежнему один.

Способ 3. Перебор в памяти процесса

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

При таком способе пропадает планировщик SQL запросов, а вместе с ним — сюрпризы вида «запрос внезапно поехал по другому плану после того, как выросла одна из таблиц». В итоге время обработки становится предсказуемым. Контроль над порядком проверок, который в SQL отдан планировщику, здесь принадлежит разработчику. Логирование каждого этапа подбора также внедряется легко.

Что общего у первых трех способов

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

Способ 4. Битовые маски

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

Маски разворачивают эту связь – здесь вместо объекта ключом становится отдельное значение таргетинга — «Германия», «мобильные устройства», «sport.de» — и для него один раз записывается, кто из каталога это значение указал. Теперь по значению из запроса сразу известен список подходящих, и открывать по очереди ничего не нужно.

Позиции в маске — кампании, а не баннеры

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

Если нумеровать баннеры, каждое значение таргетинга размножится столько раз, сколько в кампании баннеров — при 25 баннерах это двадцатипятикратный рост объема на ровном месте. Поэтому нумеруют кампании: в наших вводных это 20 тысяч позиций вместо 500 тысяч, и таргетинг каждой кампании записан ровно один раз.

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

Как выполняется проверка

Наложением строк друг на друга. Пришел запрос из Германии с мобильного:

Кампании:           К1  К2  К3  К4  К5  К6  К7  К8

Маска «Германия»     1   0   1   1   0   1   0   1
Маска «мобильные»    1   1   1   0   0   1   1   0
                    ───────────────────────────── AND
Пересечение          1   0   1   0   0   1   0   0

Прошли К1, К3 и К6 — единицы остались там, где они были в обеих строках. Дальше проверяется домен из запроса, допустим sport.de, строка для него хранится так же, то есть заранее известно, кто именно этот домен запретил:

Кандидаты            1   0   1   0   0   1   0   0
Запретили sport.de   0   0   1   0   0   0   0   1
                    ───────────────────────────── AND NOT
Остались             1   0   0   0   0   1   0   0

К3 выбыла — единица стояла в обеих строках, и вычитание ее убрало. Дальше идут К1 и К6.

В нашем каталоге кампаний 20 тысяч, так что строка — это 20 тысяч бит, около 2,5 килобайт. Процессор накладывает их друг на друга кусками по 64 позиции, то есть проход по всем кампаниям — порядка трехсот операций вместо двадцати тысяч последовательных сравнений.

Стоит обратить внимание, что длина списка запрещенных элементов в кампании перестает иметь значение. Запрещено ли в кампании три домена или тридцать тысяч — из запроса приходит один домен, по нему достается одна строка, и дальше одна операция.

Сколько таких строк придется держать

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

Спасает формат хранения. Roaring — это библиотека и формат сжатых битовых множеств. Внутри он хранит не сплошную строку бит, а куски, для каждого из которых форма записи выбирается по факту заполнения: много единиц — пишется битовая строка, мало — список номеров позиций, где эти единицы стоят. Куски без единиц не хранятся вообще. Поэтому «Германия», которую указали тысячи кампаний, занимает свои 2,5 килобайта, а «sport.de», упомянутый тремя кампаниями, двенадцать байт, хотя формально это множества одной длины.

Формат не экспериментальный: Roaring лежит внутри Lucene и Elasticsearch, Druid, ClickHouse, Pinot, Spark, и под него есть готовые библиотеки почти для любого языка. Это не значит, что завести его в горячем пути биддера бесплатно — сборку и обновление множеств придется писать самим, но сам формат достаточно обкатан.

Списки разрешенных и запрещенных значений

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

Поэтому на каждое значение заводится не одна строка, а две: «кто разрешил sport.de» и «кто запретил sport.de». Дальше они применяются по-разному. Разрешающая накладывается пересечением — из кандидатов остаются только те, кто в ней есть. Запрещающая вычитается — те, кто в ней есть, убираются. Выходит по одной простой операции на каждую строку.

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

Подбор баннеров

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

Сколько кампаний доживает до этого шага — вопрос селективности таргетингов, и точного числа тут быть не может. Дальше в расчетах я исхожу из того, что кампаний подберется пара десятков: при 25 баннерах на кампанию это пятьсот записей, и каждую надо сверить с рекламным местом из запроса: оно объявляет размер, тип медиа и параметры отображения, а баннер должен им соответствовать. Фильтрация здесь идет не по спискам, а по коротким простым значениям, поэтому особой оптимизации не требует.

Логирование подбора

Чтобы узнать, сколько кандидатов пережило каждый шаг, достаточно посчитать единицы в строке после очередного наложения. Было 20 тысяч кампаний, после гео осталось 3 тысячи, после списка площадок 400, после запрещенных доменов 380. Чтобы все это увидеть можно просто считать оставшиеся строчки

Известные проблемы

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

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

Способ 5. Индекс по условиям

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

Идея пятого способа в том, чтобы этих кампаний вообще не касаться.

Таргетинг кампании — это логическое выражение: страна Германия, и устройство мобильное, и площадка из такого-то списка, и не эти домены. Входящий запрос — набор конкретных значений. Задача формулируется как «найти все выражения, истинные на этом наборе», и решить ее можно без перебора выражений.

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

Запрос: Германия, мобильное, sport.de

Список «страна = Германия»    →  К7, К12, К40
Список «устройство = мобил.»  →  К7, К12, К88
Список «домен = sport.de»     →  К7, К40

Совпадений:  К7 — 3,  К12 — 2,  К40 — 2,  К88 — 1

У К7 в таргетинге три условия — проходит.
У К12 их два, по домену она не таргетируется вовсе,
то есть подходит под любой домен — проходит.
У К40 три условия, совпало два — отпадает.

У К12 нет ограничения по домену, и она проходит именно поэтому: условий, которых кампания не задавала, в ее пороге нет. Число совпадений сравнивается с числом собственных условий кампании, а не с числом параметров запроса.

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

Куда на самом деле переехала зависимость

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

Индекс выигрывает тем сильнее, чем разнообразнее таргетинги в каталоге. Если все кампании таргетируются на одни и те же пять стран, списки получатся длинными, и преимущество над масками станет совсем небольшим, а требование к переиндексации никуда не денется.

В реальном каталоге на 20 тысяч кампаний список «страна = Германия» — это не три записи, а тысячи так что и обходить его придется целиком. Удвоение числа кампаний удваивает и его. То есть зависимость просто переехала – с размера каталога на длину списков для популярных значений.

Дерево вместо списков

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

Индекс приходится собирать

Набор списков из примера выше — «страна = Германия → К7, К12, К40» — это и есть индекс: структура, ведущая от условий к кампаниям. Маски устроены по тому же принципу, отличается форма записи и способ вычисления.

Первое отличие от подхода с битмасками в том, что у каждой кампании хранится, сколько всего условий в ее таргетинге. Без этого числа счет совпадений бессмыслен — три совпадения означают «прошла» для кампании с тремя условиями и «не добрала» для кампании с пятью. И как только рекламодатель добавляет к таргетингу еще одно условие, меняется не только список этого условия, но и должен обновиться счетчик примененных условий в самой кампании, а значит все ее остальные списки начинают считаться иначе.

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

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

Третье — логирование отсева здесь нужно дополнительно добавлять. У масок достаточно посчитать единицы после каждого шага. Индекс же знает про отпавшую кампанию только то, что ей нужно было пять совпадений, а набралось три — какие именно два условия не сошлись, схема по построению не выясняет, потому что она и не обходит условия кампании по одному. Чтобы ответить на вопрос «почему эта кампания не подошла», приходится дописывать отдельный механизм.

Сравнение ресурсоемкости

Расчет в наносекундах на баннер.

Перебор в памяти. Баннер лежит структурой с фиксированной раскладкой: проверить страну — обратиться по известному смещению и сравнить два числа, около 1–2 нс. Списочные проверки дороже, порядка 30 нс, но до них доходит меньшинство баннеров, потому что большинство отсеивается раньше. В среднем 15 нс на баннер, то есть 7,5 мс на весь каталог.

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

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

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

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

1. Одна маска — это 20 тысяч бит, то есть 2,5 килобайта или 313 машинных слов. Если у кампаний в среднем десяток заданных таргетингов и на каждый идет разрешающая и запрещающая маска, получается двадцать наложений: двадцать масок по 2,5 килобайта, в сумме 50 килобайт чтений и около 6300 операций над словами. Плюс двадцать обращений к хеш-таблице, чтобы сами маски найти. Данные такого объема целиком помещаются в кеш процессора, так что операция занимает несколько микросекунд.

2. Сверка баннеров с рекламным местом. Допустим, после всех масок осталось два десятка кампаний: при 25 баннерах на кампанию это 500 записей. Считаю их по тем же 15 нс, хотя проверок здесь всего три-четыре вместо десятка, так что оценка с запасом — 7,5 микросекунды.

В сумме около 15 микросекунд, из них половину занимает обычный линейный перебор, но перебирается 500 записей (баннеров) вместо полумиллиона.

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

Потолок каталога

У первых трех способов стоимость подбора растет вместе с каталогом, значит у каждого есть размер, после которого он перестает укладываться в отведенные на подбор десять миллисекунд. Считается делением: 10 мс на 150 нс — около 65 тысяч баннеров для обеих баз, 10 мс на 15 нс — около 700 тысяч для перебора в памяти. У масок и индекса такого потолка нет: их стоимость от числа баннеров не зависит, и ограничение приходит от памяти, а оно на порядки выше.

Отдельно — сколько запросов нода успевает обработать. Это можно посчитать разделив количество ядер (восемь) на время подбора одного запроса.

У обеих баз на их потолке в 65 тысяч баннеров получается около тысячи запросов в секунду. У перебора в памяти тоже около тысячи, только на полном каталоге в 500 тысяч баннеров, а не на 65 тысячах — ту же тысячу запросов он выдает, обслуживая в семь раз больше баннеров. Разница ровно в стоимости обработки одной записи: 15 наносекунд против 150.

Где стоит ограничитель

У первых трех способов подбор занимает почти все время обработки — именно он определяет, сколько запросов вытянет нода.

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

В результате получается вот такая таблица. Это все конечно результат теоретизирования на объявленных выше вводных, и реальные замеры могут показать другие значения. Но здесь важнее порядок чисел – вряд ли он может измениться кардинально.

Стоит отметить, что способ 5 требует наличия дополнительного процесса. Конвейер сборки индекса — это свой бэклог, свои дежурства, свой источник инцидентов, и при сравнении «одна нода вместо пятидесяти» это нужно учитывать. У способов 3 и 4 такого нет: данные загружаются в память и используются как есть.

У первых двух способов вопрос о количестве нод не стоит. Для них добавление нод увеличивает пропускную способность, но не ускоряет обработку одного запроса, так что биды отваливаются по таймауту. Обе схемы при этом рабочие: их потолок лежит в районе 65 тысяч баннеров (на нашем теоретическом железе), и пока каталог меньше, они всех устраивают. Какие-то DSP могут с такой конфигурации начать, но стоит учитывать, что дальнейшее масштабирование потребует рефакторинга всего механизма подбора. Да и содержание изначального железа может быть дороже чем при других способах фильтрации.

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

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

Разрыв между перебором в памяти и масками — примерно в пятьдесят раз по железу, на одном и том же трафике, от смены способа хранения таргетингов.

Маски и индекс на этих вводных неразличимы. У обоих подбор ушел в фон. Разница проявится дальше: маска растет линейно с числом кампаний, а индекс — с длиной списков для популярных значений, что при разнообразных таргетингах растет медленнее. Где-то на сотне тысяч кампаний линии пересекаются, и дальше индекс отрывается.

Приемы, которые работают поверх любого способа

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

Порядок проверок

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

Поэтому дешевые и сильно отсекающие условия имеет смысл ставить первыми, а дорогие — туда, где кандидатов уже мало. Перестраивать при этом ничего не нужно — меняется только последовательность.

Работает это там, где последовательность вообще существует: в способах 1 и 2 порядок выбирает планировщик, а в переборе в памяти, масках и индексе он задается явно.

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

Сам по себе прием не новый: в базах данных динамическая перестройка плана по ходу выполнения известна как adaptive query processing. Чего я не нашел — описаний того, чтобы кто-то делал это для рекламного таргетинга, где набор кампаний меняется каждый день и вместе с ним меняется, какое условие режет сильнее. Попробую у себя на работе.

Двухступенчатый подбор: кампании, потом баннеры

Разбирался выше в разделе про битмаски, но прием общий. Плоская раскладка — кампания + баннер, где каждая запись отдельный баннер — означает, что один и тот же таргетинг записан столько раз, сколько в кампании баннеров. При подборе через маски — это становится множителем к объему памяти, а при переборе в памяти — множителем к числу проверок на каждый запрос. Разделение на две ступени убирает его в обоих случаях.

Дробление каталога между нодами

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

Тогда каталог придется делить между нодами, и встает вопрос, как сопоставлять запросы с кампаниями, которые теперь лежат в разных местах. Можно рассылать каждый запрос во все части сразу и собирать ответы вместе. Ну это расточительно — запрос обрабатывается несколькими нодами вместо одной, общий ответ не быстрее самой медленной из них, а внутри стомиллисекундного окна такая зависимость стоит дорого.

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

Как это складывается вместе

Из рассмотренных механизмов и приемов складывается примерно такая воронка проверок.

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

Маски вычитают списки запрещенных. Даже если на первом шаге стоит индекс, запреты все равно снимаются масками — индекс с ними не работает.

Выбор баннера под рекламное место. Размер, тип медиа, параметры отображения, заодно расписание и пороги ставки — все, что не превращается в множество. Ставится до сетевых обращений: если ни один баннер кампании не подходит, идти за ее состоянием незачем.

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

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

Ускорение проверок — самое очевидное применение. Второе применение — возможность ответить клиентам, какого именно трафика не хватает их кампаниям. Например из лога может быть видно, что за сутки под гео и формат рекламной кампании пришло два миллиона запросов, из них список площадок отсек 94 процента, и если расширить список на десять площадок такого же качества, объем вырастет примерно вдвое. Без разбивки по шагам доставать такие данные сложно.

Приложение: кто и что использует на практике

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

Twitter (X), соцсеть с собственной рекламной платформой. Разбили рекламный сервинг на отдельные сервисы и описали, как управляют их шардированием. Кампании раскидываются по шардам хешированием по идентификатору аккаунта — двадцать четыре шарда, у каждого свои идентичные инстансы. Число шардов подбирается из условия, что данные должны целиком помещаться в память инстанса. Отдельно описана библиотека, позволяющая менять число шардов без передеплоя клиентов. Sharding, simplification, and Twitter's ads serving platform · How we built Twitter's highly reliable ads pacing service

Pinterest, рекламная платформа внутри соцсети. Два текста, оба по делу. Первый — про то, как индекс активных объявлений публиковался раз в несколько часов и загружался в память сервиса — из-за нехватки памяти его пришлось разрезать на девять частей, а когда объем рекламы вырос, память кончилась и там. Решением стало вынести индекс во внешнее key-value хранилище, что позволило увеличить каталог в шестьдесят раз. Второй — про сам конвейер сборки индекса: базовая сборка плюс инкрементальная, по мотивам гугловской Caffeine, с секундными задержками. Там же прямо сказано, что команда индексации постоянно участвует в разборе тикетов вида «почему моя кампания не тратит», и что встроенные средства наблюдаемости позволяют находить причину быстро. How we scaled the size of Pinterest's ad corpus by 60x · How ads indexing works at Pinterest

AdGear, ныне часть Samsung Ads — рекламная платформа. Поддерживают открытую реализацию BE-tree на C. Показательны встроенные типы атрибутов: сегменты аудитории и лимиты показов на пользователя, то есть структура изначально сделана под рекламный таргетинг. github.com/adgear/be-tree

Yahoo и Стэнфорд — работа, на которую ссылаются почти все. Описывает, как строить инвертированный индекс по булевым выражениям и сопоставлять их с входящим набором значений. Там же лежит основа схемы со счетом совпадений. Efficiently Evaluating Complex Boolean Expressions (SIGMOD 2010)

Открытая реализация того же алгоритма на Go, написанная прямо под RTB. В описании сформулирована ровно наша задача: наивный способ — перебрать все баннеры и сравнить таргетинги по одному, что слишком медленно при миллионах баннеров, притом что весь цикл RTB должен уложиться в сто миллисекунд. github.com/csimplestring/bool-expr-indexer

Meta — пример того, куда уходят системы самого большого масштаба. Andromeda, их движок отбора кандидатов, построен на глубокой нейросети и работает на NVIDIA Grace Hopper и собственных ускорителях Meta, с иерархическим индексом. Масштаб — десятки миллионов кандидатов, сужаемых до нескольких тысяч перед аукционом. Полезен как граница применимости: на пять-шесть порядков выше того, о чем шла речь в статье. engineering.fb.com — Meta Andromeda

Лимиты в интерфейсах как отражение архитектуры. Xandr держит почтовые индексы отдельной сущностью уровня аккаунта: до ста тысяч индексов в списке, до ста списков на кампанию, до восьми тысяч списков на аккаунт. DV360 ограничивает кампанию десятью тысячами локаций, причем целый список локаций считается за одну позицию. LinkedIn — сто тысяч доменов на список запрещенных. Xandr — postal code lists · DV360 — geography targeting · LinkedIn — brand safety hub

Наблюдаемость отсева как продукт. Adobe Advertising DSP показывает причины, по которым ставка не была сделана, с разбивкой по конкретным сделкам и по дням — то есть воронка биддинга вынесена в отчет для клиента. Adobe Advertising DSP — brand safety and media quality