Таргетированная реклама. Компактное хранение поисковых ресурсов

На митапе VK Tech Talks | Engines & KPHP программист-разработчик ВКонтакте Иван Бураков рассказал, как в социальной сети экономят на оперативной памяти в таргетированной рекламе и поисковой системе.

Что такое таргетирование?

Таргетирование — это рекламный механизм, позволяющий выделить из всей имеющейся аудитории только ту часть, которая удовлетворяет заданным критериям (целевую аудиторию), и показать рекламу именно ей. Несложно догадаться, что по такому же принципу работает поиск пользователей ВКонтакте по критериям. Например, можно установить критерий поиска людей в конкретном городе. Отсюда приходим к выводу, что таргетирование = поиск.

Поиск начинается с поискового запроса. Рассмотрим пример, который может пережёвывать движок:

Обычный запрос объединяет в себе несколько параметров с ограничениями, которые потом объединяются через “И”, “ИЛИ”, “НЕТ”, и выдает результат. С технической стороны задача реализуема.

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

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

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

Ретаргетинг

Теперь разберёмся с группами ретаргетинга. Ретаргетинг — это рекламный механизм, посредством которого онлайн-реклама направляется пользователям, которые уже просмотрели рекламируемый продукт на странице рекламодателя. Группы ретаргетинга — это множество таких пользователей. Всего таких групп около 400 миллиардов.

Проблемы

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

Эти 4 задачи нужно было реализовать или улучшить в новом движке. Проблема в том, что при прямом использовании встроенных структур в C++ std:set уходит много памяти, а поставленные выше задачи нужно решать очень эффективно.

При прямой реализации на одного пользователя уходит 100 байт. Умножим их на 400 миллиардов групп и получим необходимое количество оперативной памяти. Покупать столько памяти неразумно.

Как это решается и в чем возникает проблема?

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

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

Весь этот цикл называется переиндексация. Этот процесс имеет ряд преимуществ, с которыми весь процесс обращения к данным работает очень быстро:

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

Теперь к поисковым индексам!

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

С++ std:set потребляет слишком много памяти, поэтому мы придумали свою структуру данных — ПИМЧИ (поисковый индекс с малым числом изменений).

Но с новой структурой данных возникла проблема: при запуске движок теряет 2 терабайта.

При запуске движок в какой-то вектор читает элементы со снимков и копирует их в ПИМЧИ. Вектор удаляется, а ПИМЧИ остаётся. После удаления вектора остаётся много неиспользуемой памяти.

Для устранения этой проблемы используется кастомный аллокатор. Если объяснять простыми словами, каждая группа пользователей следует друг за другом с выделенной для неё памятью.

Осталось реализовать протухание:

Итог

После устранения всех ошибок ПИМЧИ вышел в релиз. Таким образом мы получили полный функционал C++ std:set, но с меньшим потреблением памяти.

Теперь взглянем на потребляемую память:

В итоге мы в 10 раз уменьшили потребление памяти и вместо хранения 40 байт мы храним 4 байта и 1 битик.

На этом доклад подошёл к концу. Полное видео выступления ниже:

The Brown Room — независимое интернет-издание про социальные сети и современные технологии.

Автор: Владислав Сатонин
Корректоры: Влад Воробьёв, Арсений Метелёв
Слайды и данные: VK Tech