Системный дизайн агрегации рекламных кликов: Kafka, Flink, окна, водяные знаки и exactly-once
Как спроектировать агрегацию рекламных кликов на system design интервью: Kafka и Flink, тумблинг-окна, водяные знаки и опоздавшие события, exactly-once, дедупликация кликов и сверка стрима с батчем.
Коротко
| Вопрос | Решение в этом разборе |
|---|---|
| Нагрузка | 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. Оценка нагрузки
Посчитаем на салфетке, как в статье про оценку нагрузки:
- кликов в секунду в среднем. Пик в 5 раз выше — около 60 тыс. в секунду.
- Событие клика с
click_id,ad_id, временем, IP, user agent и страной — около 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 решает это так:
- Чекпоинты. Источник периодически вставляет в поток барьеры. Когда барьер проходит все операторы, их состояние и смещения Kafka сохраняются атомарно. После сбоя всё откатывается к одной согласованной точке.
- Транзакционный 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 минут, остальное время уйдёт на детали, которые интервьюер выберет сам.