Системный дизайн агрегации рекламных кликов: Kafka, Flink, окна, водяные знаки и exactly-once

Как спроектировать агрегацию рекламных кликов на system design интервью: Kafka и Flink, тумблинг-окна, водяные знаки и опоздавшие события, exactly-once, дедупликация кликов и сверка стрима с батчем.

13 мин чтениясистемный дизайн · стриминг · kafka · собеседования

Коротко

ВопросРешение в этом разборе
Нагрузка1 млрд кликов в сутки: около 12 тыс. в секунду в среднем, до 60 тыс. в пике
ТранспортKafka, топик кликов партиционирован по ad_id, хранит сырые события несколько дней
АгрегацияFlink: тумблинг-окна по минуте в event time, ключ — ad_id
Опоздавшие кликиводяной знак отстаёт на 30 с; что пришло позже — в отдельный поток и на батч-пересчёт
Дублиclick_id выдаётся при показе, Flink помнит его в состоянии с TTL
Exactly-onceчекпоинты Flink + транзакционный sink или идемпотентный upsert по (окно, ad_id)
Источник правдысырые клики в объектном хранилище; ночной батч пересчитывает итоги и сверяется со стримом

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

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

Шаг 1. Требования

ВопросОтвет интервьюераЧто это меняет
Что считаем?клики по объявлению за минутуключ агрегации (ad_id, минута)
Какие запросы?клики за последние M минут, топ-Nнужны и временные ряды, и топ
Фильтры?страна, устройство, кампаниянесколько измерений, OLAP-хранилище
Насколько свежие данные?задержка до пары минутбатча раз в час мало, нужен стрим
По этим цифрам выставляют счёт?даточность важнее скорости, нужна сверка
Сколько кликов?1 млрд в сутки, 2 млн объявленийсчитаем, хватит ли одной машины (не хватит)
Сколько хранить?агрегаты — годы, сырые — 30 днейразные хранилища и уровни детализации

Нефункциональные требования стоит проговорить вслух: клик нельзя потерять, нельзя посчитать дважды, система должна переживать падение любого узла без ручного вмешательства. Именно эти три пункта превращают простую задачу «сложить числа» в разговор про exactly-once.

Шаг 2. Оценка нагрузки

Посчитаем на салфетке, как в статье про оценку нагрузки:

  • 109/86 400≈11 60010^9 / 86\,400 \approx 11\,600 кликов в секунду в среднем. Пик в 5 раз выше — около 60 тыс. в секунду.
  • Событие клика с click_id, ad_id, временем, IP, user agent и страной — около 200 байт. Это 109⋅200=20010^9 \cdot 200 = 200 ГБ сырых данных в сутки и около 6 ТБ за 30 дней хранения.
  • Агрегаты маленькие. Если за минуту кликают по 200 тыс. разных объявлений, это 200 тыс. строк в минуту, около 290 млн строк в сутки на самой мелкой детализации. Часовые и дневные свёртки на порядки меньше.

Вывод: запись в базу на каждый клик (UPDATE ads SET clicks = clicks + 1) отпадает сразу. 60 тыс. инкрементов в секунду по горячим строкам упрутся в блокировки. Значит, клики пишем в лог, а считаем потоково.

Шаг 3. Архитектура

 Клик → Click API → Kafka (clicks, raw) ─┬─→ Flink: дедуп → окна → агрегаты ─→ OLAP (ClickHouse / Druid / Pinot)
                                         │                                        ↑
                                         └─→ архиватор → S3 / HDFS ─→ Spark (ночью) ┘ сверка и перезапись

Click API принимает клик, проверяет подпись, отдаёт пользователю редирект на сайт рекламодателя и пишет событие в Kafka. Пользователь не должен ждать агрегацию: запись в лог с acks=all — единственная синхронная операция.

Kafka — буфер и источник правды на ближайшие дни. Если Flink упадёт или в агрегации найдут баг, события можно перечитать с нужного смещения. Подробнее о том, чем лог отличается от классической очереди, — в статье про очереди сообщений.

Flink держит состояние (открытые окна, увиденные click_id) и периодически сохраняет его в чекпоинт. Выход — строки вида (window_start, ad_id, country, clicks).

OLAP-хранилище отвечает на запросы дашборда: «клики по кампании за последний час с разбивкой по странам». Колоночные базы вроде ClickHouse, Druid или Pinot делают такие запросы за миллисекунды и умеют сворачивать минутные данные в часовые.

Архив и батч — вторая независимая линия подсчёта. Зачем она, когда есть стрим, — в шаге 7.

Шаг 4. Окна и event time

Главный вопрос интервьюера: «по какому времени вы относите клик к минуте?». Есть два варианта:

  • Processing time — когда событие дошло до Flink. Просто, но неверно: если мобильный клиент был офлайн 40 секунд, клик в 10:00:55 попадёт в минуту 10:01. А при перечитывании Kafka после сбоя вся история «сплющится» в текущую минуту.
  • Event time — когда клик случился, по метке в самом событии. Результат детерминирован: сколько раз ни перечитывай лог, окна получатся те же.

Для биллинга нужен event time. Тип окна — тумблинг (неперекрывающиеся окна по минуте): каждый клик попадает ровно в одно окно, суммы складываются в часы и дни без двойного счёта. Скользящие окна («последние 5 минут с шагом в минуту») нужны для алертов, а не для счёта — их проще собрать запросом из минутных агрегатов.

Ключ окна — ad_id. Kafka партиционирована по нему же, поэтому все клики одного объявления приходят в один инстанс оператора и считаются локально, без координации.

Шаг 5. Водяные знаки и опоздавшие события

С event time появляется проблема: когда закрыть окно 10:00–10:01? События приходят не по порядку, и Flink не знает, придёт ли ещё клик из 10:00:58.

Водяной знак (watermark) — это утверждение «событий старше T больше не будет». Самая частая стратегия — «максимальное увиденное время минус допустимая задержка». Окно [start, end) закрывается и выдаёт результат, когда водяной знак переходит end.

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

from collections import defaultdict WINDOW = 60 # секунд, окно в одну минуту LATENESS = 30 # насколько водяной знак отстаёт от максимального event time DEDUP_TTL = 600 # сколько помним click_id class ClickAggregator: def __init__(self): self.windows = defaultdict(int) # (window_start, ad_id) -> count self.seen = {} # click_id -> event_time self.max_ts = 0 self.watermark = 0 self.late = [] # опоздавшие события (side output) def on_click(self, click_id, ad_id, ts): if click_id in self.seen: return [] # дубль — игнорируем win = ts - ts % WINDOW if win + WINDOW <= self.watermark: self.late.append((click_id, ad_id, ts)) return [] # окно уже закрыто self.seen[click_id] = ts self.windows[(win, ad_id)] += 1 self.max_ts = max(self.max_ts, ts) return self.advance(self.max_ts - LATENESS) def advance(self, wm): if wm <= self.watermark: return [] self.watermark = wm ready = sorted(k for k in self.windows if k[0] + WINDOW <= wm) out = [(w, ad, self.windows.pop((w, ad))) for w, ad in ready] # чистим старые click_id, чтобы состояние не росло вечно self.seen = {c: t for c, t in self.seen.items() if t > wm - DEDUP_TTL} return out agg = ClickAggregator() events = [ ("c1", "ad1", 5), ("c2", "ad1", 20), ("c2", "ad1", 20), # c2 пришёл дважды ("c3", "ad2", 50), ("c4", "ad1", 70), ("c5", "ad1", 65), ("c6", "ad2", 95), # watermark = 65 ("c7", "ad1", 58), # опоздал на 37 с ("c8", "ad2", 130), # watermark = 100 ] for e in events: for w, ad, n in agg.on_click(*e): print(f"окно [{w}, {w + WINDOW}) {ad}: {n}") print("опоздавшие:", agg.late)

Вывод:

окно [0, 60) ad1: 2
окно [0, 60) ad2: 1
опоздавшие: [('c7', 'ad1', 58)]

Дубль c2 не посчитан, окно [0, 60) закрылось, когда клик c6 сдвинул водяной знак до 65, а клик c7 из уже закрытого окна ушёл в список опоздавших. Окно [60, 120) ещё открыто: водяной знак 100 до его конца не дошёл.

Выбор задержки — компромисс, и его стоит назвать на интервью:

Задержка водяного знакаСвежесть дашбордаДоля опоздавшихПамять под открытые окна
5 секундотличнаязаметнаямало
30 секундхорошаямалаяумеренно
10 минутплохая для алертовпочти нольмного

Во Flink это WatermarkStrategy.forBoundedOutOfOrderness(Duration.ofSeconds(30)). Опоздавшие события не надо выбрасывать молча: allowedLateness позволяет обновить уже выданный результат, а sideOutputLateData отправляет совсем поздние клики в отдельный поток. Их можно дописать в OLAP поправкой или оставить на батч-пересчёт.

Ещё одна ловушка — простаивающие партиции. Водяной знак оператора — минимум по всем входным партициям. Если в одну партицию Kafka ночью ничего не пишут, её водяной знак стоит на месте, и окна не закрываются нигде. Лечится withIdleness(...): партиция без событий дольше заданного времени перестаёт тормозить общий водяной знак.

Шаг 6. Exactly-once и дедупликация

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

Дубли на входе

Пользователь дважды кликнул, браузер повторил запрос, Click API получил таймаут от Kafka и отправил событие снова. Это логические дубли: в логе два события об одном клике. Никакой exactly-once внутри Flink их не уберёт — для него это два разных сообщения.

Решение — уникальный click_id. Его генерирует рекламный сервер при показе объявления и вшивает в подписанную ссылку (как получать такие идентификаторы — в статье про генератор уникальных ID). Flink хранит увиденные click_id в keyed state с TTL — в модели выше это словарь seen. Это та же задача, что contains duplicate nearby: найти повтор в окне ограниченного размера, не храня всю историю.

Сколько это стоит по памяти? Если помнить click_id 10 минут, при пиковых 60 тыс. кликов в секунду это 36 млн идентификаторов. По 16 байт плюс накладные расходы состояния — несколько гигабайт на весь кластер, распределённых по ключам. RocksDB-бэкенд Flink держит это на диске. Если память всё же жмёт, можно поставить перед точной проверкой фильтр Блума: он отсеет заведомо новые клики, а в точное состояние пойдут только подозрительные.

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

Дубли при сбоях

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

Flink решает это так:

  1. Чекпоинты. Источник периодически вставляет в поток барьеры. Когда барьер проходит все операторы, их состояние и смещения Kafka сохраняются атомарно. После сбоя всё откатывается к одной согласованной точке.
  2. Транзакционный sink. Результаты пишутся в выходной топик Kafka внутри транзакции, которая коммитится только при завершении чекпоинта (схема похожа на двухфазный коммит). Потребители читают с isolation.level=read_committed и незакоммиченного не видят.

Цена — задержка: результаты видны только после чекпоинта, поэтому интервал чекпоинтов (обычно десятки секунд) добавляется к задержке дашборда. И частая ошибка конфигурации: таймаут транзакции продюсера должен быть больше, чем интервал чекпоинта плюс время восстановления, но не больше transaction.max.timeout.ms на брокере. Иначе брокер оборвёт транзакцию, и данные пропадут.

Более простой путь — идемпотентная запись. Строка (window_start, ad_id, country) имеет естественный ключ, и её можно писать как upsert: повторная запись того же окна перезаписывает ту же строку тем же значением. Получается effectively-once без транзакций. Подробно этот приём разобран в статье про идемпотентность. Важно: работает только для перезаписи итога окна. Инкремент clicks = clicks + n при повторе задвоится.

Шаг 7. Сверка с батчем

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

Сырые клики из Kafka архивируются в объектное хранилище, разложенные по часам. Раз в сутки (или раз в час) батч-задача на Spark пересчитывает агрегаты по всем событиям, включая опоздавших, и сравнивает со стримом:

def reconcile(stream, batch, tolerance=0.001): """stream, batch: {(hour, ad_id): clicks}. Возвращает ключи, где расхождение выше допуска.""" diffs = [] for key in stream.keys() | batch.keys(): s, b = stream.get(key, 0), batch.get(key, 0) if b == 0 and s == 0: continue rel = abs(s - b) / max(b, 1) if rel > tolerance: diffs.append((key, s, b, round(rel * 100, 2))) return sorted(diffs) stream = {("10:00", "ad1"): 10_000, ("10:00", "ad2"): 5_012, ("11:00", "ad1"): 9_870} batch = {("10:00", "ad1"): 10_004, ("10:00", "ad2"): 4_890, ("11:00", "ad1"): 9_870, ("11:00", "ad3"): 120} for key, s, b, pct in reconcile(stream, batch): print(key, "стрим:", s, "батч:", b, f"расхождение {pct}%")
('10:00', 'ad2') стрим: 5012 батч: 4890 расхождение 2.49%
('11:00', 'ad3') стрим: 0 батч: 120 расхождение 100.0%

Расхождение в четыре клика на 10 тысяч укладывается в допуск 0,1% — это опоздавшие события. А 2,5% по ad2 и целиком пропавшее ad3 — повод для алерта: в первом случае похоже на сломанную дедупликацию, во втором — на потерянную партицию.

Дальше правило простое: счёт выставляется по батчу. Стрим даёт быстрые предварительные цифры для дашборда, батч перезаписывает их окончательными. Такая схема с двумя линиями называется лямбда-архитектурой. Её критикуют за то, что одну логику приходится писать дважды. Альтернатива — каппа-архитектура: батча нет, а пересчёт делается тем же Flink-джобом, перечитывающим Kafka или архив. На интервью стоит назвать оба варианта и объяснить выбор: для биллинга вторая независимая реализация — плюс, а не минус, она ловит баги первой.

Шаг 8. Горячие ключи и масштабирование

Ключ ad_id хорош, пока клики распределены ровно. Но рекламу в финале чемпионата кликают в сотни раз чаще средней, и все эти клики приходят в одну партицию и один поток Flink.

Варианты, от простого к сложному:

  • Предагрегация. Перед keyBy каждый инстанс локально суммирует клики за пару секунд и отправляет дальше частичные суммы. Число сообщений на горячий ключ падает в сотни раз.
  • Соль в ключе. Ключ ad_id#k, где k от 0 до 15: горячее объявление размазывается на 16 потоков, а второй уровень складывает 16 частичных сумм. Дедупликация при этом должна идти по click_id, а не по солёному ключу, иначе дубль попадёт в другую соль.
  • Масштабирование Kafka и Flink. Число партиций задаёт потолок параллелизма. При 60 тыс. событий в секунду хватит нескольких десятков партиций, но их стоит заложить с запасом: увеличение числа партиций меняет распределение ключей. Как это устроено в общем виде — в статье про шардирование и репликацию.

Запрос «топ-100 объявлений за последнюю минуту» тоже лучше считать в стриме: второй оператор принимает минутные агрегаты и держит кучу размера N — тот же приём, что в задаче top K frequent. Если точность топа не важна, а ключей миллионы, подойдёт Count-Min Sketch.

Шаг 9. Хранение и запросы

Минутные агрегаты пишутся в OLAP-таблицу со схемой примерно такой: window_start, ad_id, campaign_id, country, device, clicks. Партиционирование по дню, сортировка по (ad_id, window_start) — тогда запрос «клики объявления за час» читает один непрерывный кусок.

Детализация снижается со временем: минуты храним неделю, часы — год, дни — бессрочно. Свёртку делает сама база (материализованные представления в ClickHouse, rollup в Druid) или фоновая задача.

Типичные ошибки на интервью

  • Считать в базе инкрементом на каждый клик. Не выдерживает нагрузку и не переживает повторы.
  • Окна по processing time. Перечитывание лога после сбоя даёт другие цифры, а для биллинга это недопустимо.
  • «Включим exactly-once во Flink, и дублей не будет». Exactly-once защищает от повторов при сбоях, но не от двух событий об одном клике. Нужен click_id.
  • Выбрасывать опоздавшие события. Это потерянные деньги. Их надо хотя бы сохранить и учесть батчем.
  • Не упомянуть сверку. Для денежных метрик интервьюер почти наверняка спросит: «как вы узнаете, что цифры правильные?».
  • Забыть про горячие ключи. Распределение кликов по объявлениям сильно неравномерное, и одна кампания может положить партицию.

Итог

Схема держится на трёх идеях. Во-первых, клики пишутся в неизменяемый лог, а не в счётчики, поэтому любой результат можно пересчитать. Во-вторых, считаем по event time с водяными знаками, а дубли отсекаем по click_id и exactly-once-чекпоинтам. В-третьих, у стрима есть независимая батч-проверка, и деньги выставляются по ней. Если на интервью уложить эти три идеи в первые 15 минут, остальное время уйдёт на детали, которые интервьюер выберет сам.

Потренироваться в спокойной обстановке

Все задачи