System design practice

Ad Click Aggregator

medium Based on a system published by Uber streaming aggregation exactly-once olap real-world

Uber Eats ads: Kafka, one-minute Flink windows committed at each checkpoint, Pinot.

Solve it in your browser Read the lesson first

Uber Eats shows restaurants' ads in its app, and every ad the app shows (an impression) and every tap on one (a click) is an event. Restaurants pay for those events, so they have to be counted exactly once: a click counted twice overcharges the advertiser, and a lost one is lost revenue and an under-reported campaign. The counts feed two readers: the Ad Budget Service, which spends each campaign's budget and paces its ads, and the dashboards where advertisers watch their campaigns. Both need the numbers within minutes, not the next day.

Uber built this on Kafka, Flink and Pinot. The app's events go into a Kafka topic. A Flink job filters out invalid events, drops duplicates, and counts each ad's clicks and impressions in one-minute windows. Its output goes to a second topic in Kafka transactions that are committed only when Flink checkpoints, and the budget service and Pinot, the store behind the dashboards, read only committed records. Design that pipeline.

Functional requirements

Name the raw events topic events and the aggregates topic aggregates (both [Kafka]), and Pinot pinot: the tests in problem.proschi refer to them, to the given budget and ledger, and to the use case names above.

Scale

Uber's post gives one rate: hundreds of millions of ad events a week in 2021, on the order of a thousand a second on average. Every number below is an assumption for the exercise, for a pipeline built to take the meal-time peaks and years of growth.

Constraints

What is given

problem.proschi declares the app and the advertiser (the clients), the budget service and its ledger, which already exist, and Pinot's capacity. It holds the traffic, requirements and tests. Add the ingest tier, the two Kafka topics, the aggregation job and its checkpoint store, Pinot, the report service, the connections and the seven use cases.

What this model leaves out

Based on

How your design is checked

You write the design as text in Proschi. Tests run in your browser: a simulation of the traffic above checks latency, availability, cost and what happens when a machine fails. How the simulation works.

Start designing

Lesson · 13 min read

Learn it: Ad Click Aggregator #

Ad click aggregation: counting money exactly once, in minutes #

What you'll learn #

The problem, explained #

Uber Eats shows ads for restaurants. Each time the app shows an ad, it reports an impression; each time someone taps one, a click. Restaurants pay for these, so the counts are money. Uber's ads team, writing in 2021, set three requirements for the pipeline that counts them:

This looks like other counting problems on the roadmap. View counting counts unique viewers, approximately, with HyperLogLog; a view off by 1% is fine. Trending topics ranks terms, and nobody can tell if a count is slightly off. Metrics ingest aggregates measurements where losing a few seconds is acceptable. Here none of that holds: the count is an invoice line, so it must be exact and exactly once, and the same number must reach both the bill and the dashboard.

In this exercise you build one region of Uber's design. Seven use cases: the app's Record event, the job's Aggregate events, Publish aggregates and Checkpoint, Pinot's Load aggregates, the budget service's Update budget, and the advertiser's View report.

Back-of-the-envelope #

Uber's post gives one volume, hundreds of millions of ad events a week. The rates below are the exercise's assumptions for a peak with room to grow.

ad events at peak
20k / s
fewer writes after one-minute windows: 500 / s
40×
ingest and aggregation replicas at 2k each
16 + 16
Pinot servers for 1.5k operations a second
3
how stale an aggregate can be
≤ 3 min
a month for the reference design
$7,500

Ingest and aggregation. 20k events a second at about 2k per replica is 10 replicas at 100%. To stay under 70% after losing one, 15 must survive: 16, at 63% busy. The aggregation job reads the same 20k a second, so it needs the same 16.

Kafka. A broker takes about 50k writes a second in the simulation, so the raw topic's 20k fit on 3 brokers (13%) with room to lose one. The aggregates topic takes 500 a second; 2 brokers are plenty.

Windows. If about 30k ads have events in a given minute, the job emits 30k records a minute: 500 a second, 40 times fewer than the events. That is what Pinot and the budget service must take.

Pinot. 500 writes and 1k dashboard queries a second, at 2k of each per server, is 0.75 of a server. 3 servers run at 25%, and 38% after losing one. Loading the raw events instead would be 20k writes plus the queries: at least 16 servers to stay under 70% after losing one, $9,600 a month for Pinot alone.

Freshness. A one-minute window closes, and its record waits for the next checkpoint (every two minutes) to be committed. An event waits up to a minute for its window to close, then up to two more for the commit: an aggregate is visible at most three minutes after its events.

TierLoadReplicasBusy
Ingest20k events / s1663%
Aggregation job20k events / s1663%
Raw events topic20k writes / s313%
Aggregates topic500 writes / s21%
Pinot500 writes + 1k queries / s325%
Report service1k queries / s317%

Concepts #

Append first, count later #

The app's request has one job: make sure the event is not lost. Writing it to a replicated Kafka topic does that in a few milliseconds, and the app gets 202. Everything else (validating, deduplicating, counting, charging) happens in the stream, where it can fall behind for a minute, restart or be redeployed without the app noticing and without losing an event.

The tempting alternative is to increment a counter row in a database during the request. At 20k events a second that is four times what one PostgreSQL primary takes, every app request waits for the write, and a click whose response timed out is retried and counted again. A log in front of the counting also gives you replay: Uber keeps its topics for three days, so a bad deploy of the job can be fixed and the events counted again.

Pre-aggregate in windows #

Nobody bills or charts a single click. Advertisers look at clicks per hour or per day, and the budget service needs spend per campaign every few minutes. So the job groups events by ad and minute (a tumbling window: fixed, non-overlapping, one minute long) and emits one record per group when the minute ends: the ad, the minute, the clicks, the impressions.

What it buys: 40 times fewer writes downstream, small tables, and dashboard queries that sum a few thousand rows instead of millions. Hourly and daily numbers are sums of the minutes. What it costs: up to a minute of delay, and detail is gone. A question about one specific click needs the raw events, which stay in Kafka for three days and in the data warehouse for analysts.

Uber's job keys every event by the ad identifier and its minute bucket, so a late event still lands in the minute it happened.

Partition by ad, size for the event rate #

Each window's count lives in the state of one Flink task. To keep every event of an ad in the same task, key the stream by ad: the ingest service produces with the ad as the Kafka key, so one partition and one task see all of that ad's events. Within one consumer group, each partition is read by a single consumer at a time, so the partition count caps the aggregation job's parallelism. Give the raw topic enough partitions for the event rate, with headroom, from day one.

Size each tier for what it receives. The ingest tier and the aggregation job see every event; Pinot and the budget service see only aggregates. A job sized for its output instead of its input falls behind, its consumer lag grows, and the budget service paces with stale numbers. The simulation has no lag, so this problem asks the job to keep Aggregate events under 50 ms at p99 instead.

Exactly once: checkpoints and transactions #

"Exactly once" in a stream pipeline is three separate guarantees, and the pipeline is only as good as the weakest.

  1. The job's state. Flink periodically takes a checkpoint: a snapshot of every task's state (open windows, the event ids it has seen for deduplication) together with the Kafka offsets it had read up to, stored durably. After a crash it restores the last checkpoint and re-reads from those offsets, so every event is reflected in the state once.
  2. The job's output. Restoring state does not unsend records. If the job published a window's aggregate and then crashed before the next checkpoint, it would replay the same events and publish the aggregate again. So Flink writes its output into a Kafka transaction and commits it only when the checkpoint completes: a two-phase commit between the checkpoint and the topic. After a crash, the uncommitted transaction is aborted and the records are produced again from the restored state.
  3. The readers. Consumers read with read_committed, so they never see records of an aborted transaction. And because any consumer can itself crash between applying a record and committing its offset, every aggregate carries a record UUID: the budget service applies each UUID once, Pinot upserts by it, and Hive (Uber's data warehouse) deduplicates by it.

What it costs is delay. Readers see nothing until the checkpoint commits, so the checkpoint interval is the pipeline's latency. Uber checkpoints every two minutes instead of the ten-minute default its post mentions (Flink itself leaves checkpointing off until you set an interval), and says plainly that the result is not quite real time, but fast enough for pacing and reporting.

Deep dive Why not just deduplicate at the end?

A database at the end could reject a record UUID it has already seen, and some pipelines stop there. It works for one sink, but each new reader must implement it, and a reader that does not, a dashboard cache or a second consumer, double-counts. Committing output with the checkpoint keeps duplicates out of the topic, so every reader starts from a clean stream, and the UUID stays as a second line of defence.

One number for billing and dashboards #

The budget service and the dashboards must agree. If the budget is charged from the raw clicks while the dashboard shows the aggregates, the two numbers drift apart: the raw stream holds invalid and duplicate events the aggregation job filtered out, and a consumer restart redelivers some of them. An advertiser who sees 1,840 clicks on the dashboard and pays for 1,903 has a dispute, not a report.

So both read the committed aggregates topic. The budget service records each applied record UUID in its ledger, in the same transaction as the spend, and ignores one it has seen. Pinot ingests the same topic with upserts. One number, computed once, read twice.

An OLAP store for the dashboards #

Dashboards ask analytical questions: clicks and impressions for this campaign, per day, over the last week. A row store answers that by scanning; an OLAP store such as Apache Pinot keeps columns, indexes and pre-sorted segments, and answers in tens of milliseconds while ingesting from Kafka in real time. Uber chose Pinot and used its upsert feature (keyed by the record UUID) so a redelivered aggregate replaces itself instead of adding a row.

The advertiser never queries Pinot directly: a report service checks who is asking, which campaigns they may see, and turns the request into a query.

Designing it step by step #

1. Scope. Ask who reads the counts (billing and advertisers), how fresh they must be (minutes), and how exact (exactly once, because it is money). Ask the event rate at peak and the reporting granularity (per minute, rolled up).

2. High level. App → load balancer → ingest service → raw events topic. Aggregation job reads the topic, checkpoints to object storage, writes the aggregates topic. Pinot and the budget service read the aggregates topic. Advertiser → load balancer → report service → Pinot.

3. Deep dive.

Record event. Produce to Kafka keyed by ad, answer 202 after the broker acknowledges. Nothing else on this path.

Aggregate events. The job filters invalid events, drops duplicates using the event ids in its keyed state, and adds the event to its ad's current minute. No external call per event.

Publish aggregates and Checkpoint. When a minute closes, the job writes its record, with a fresh record UUID, into the open transaction. Every two minutes it stores its checkpoint, then commits the transaction.

The readers. Pinot ingests the aggregates with upserts by record UUID; the budget service applies each record UUID once. Both read committed records only.

Size it. 16 ingest and 16 aggregation replicas for 20k events a second, 3 Pinot servers, 3 report replicas, 3 and 2 brokers, two of everything to lose one machine. About $7,500 of the $9,000.

4. Wrap up. Name the trade-off: freshness bounded by the checkpoint interval in exchange for exactness. Mention what you would watch: consumer lag on the raw topic, checkpoint duration and failures, and the gap between the aggregates and a daily batch recount.

Common mistakes #

Counting in the request (wrong/count-in-the-request). The ingest service increments a counter row per event before it answers. 20k writes a second saturate the database and the app waits on them; a retried request counts twice. Caught by "Recording an event only appends it to Kafka" and Record event's p99.

Storing every raw event in Pinot (wrong/raw-events-into-pinot). The job inserts each cleaned event and dashboards sum at query time. Pinot takes 20k writes a second instead of 500 and needs at least four times the servers. Caught by "Events are aggregated in the stream, in memory" and the budget.

Charging the budget from raw clicks (wrong/charge-budget-per-raw-click). The budget service reads the raw events topic, so it charges for invalid and duplicate clicks the job would have dropped, and for redelivered ones after a restart; billing and the dashboard disagree. Caught by "Pinot and the budget read only committed aggregates".

Publishing before the checkpoint (wrong/publish-before-checkpoint). Each window's record is committed to Kafka the moment the window closes. A crash before the next checkpoint replays the events and publishes the aggregate twice. Caught by "Aggregates are committed only after a checkpoint".

Classic mistakes beyond the tests:

In the interview #

Likely follow-ups:

Further reading #

Now design it

Review cards for this problem

Short questions on the ideas it needs, from the review cards. Review them daily so they stick.

More system design problems