BOOK DEEP READ · System Design Interview Vol 2 · Ch 6
System Design Interview Vol 2 · Ch 6 · Alex Xu & Sahn Lam · 2022
An ad scrolls past on your phone and you tap it. For that one tap, an advertiser pays the platform. Worldwide there are a billion such taps a day. This chapter is about one thing: how to count those billion taps into a bill nobody can poke a hole in.
It sounds like counting — tap, add one, a child could do it. But the moment the number turns into money, its nature changes completely. It is no longer a reading on a pedometer; it is the till in a cash register. Nobody cares if a pedometer skips a step. If the till comes up short, the month doesn't balance. Everything hard about this chapter comes from that switch of identity.
Three things. Too many: ten thousand taps a second on average, fifty thousand at peak — no single machine can count that, so dozens of machines count in parallel and someone has to add it all up. They arrive late: you tap an ad on the subway, the signal drops, and your phone only sends the record once you're back above ground. It may be three minutes late, or three hours. Does that tap belong to "that minute back then" or "this minute now"? They arrive twice: the network hiccups, the phone never sees an acknowledgement, so it sends again — count the same tap twice and the advertiser has been overcharged.
Keep the running receipts. An incoming tap isn't counted right away; it is first parked, untouched, in one long queue — the way a shop keeps the stub of every receipt. If you later get the sum wrong or change the rules, you just run the stubs through again.
One drawer per minute. Instead of maintaining a single "total" that keeps changing, give every minute its own drawer, and let each tap fall into the minute it was born in. The drawers sit end to end and never overlap, so no tap can land in two of them.
Give latecomers a grace period. When a minute ends, don't seal the drawer immediately — wait another three minutes, the way the last bus waits three more minutes before it pulls out. Almost all the stragglers make it. The ones that truly don't get settled overnight.
Number every receipt. Each tap is born carrying a globally unique number. Before accepting it, check whether that number has been seen before; if it has, throw it away. Send the same one a hundred times and it still counts once.
Fast and accurate pull against each other here. A longer grace period recovers more late taps and gives a truer bill — but the answer arrives later, and advertisers watching a live dashboard to adjust their bids can't use a number that shows up too late. So the industry usually walks on two legs: publish a "good enough, fast" number within minutes for people to look at, then overnight recount from the full pile of stubs to get the "accurate" number that actually settles the bill — and compare the two, raising an alarm if they drift too far apart.
The cost is worth stating plainly: from then on this system permanently carries two sets of numbers and a reconciliation line, which is an order of magnitude more to operate than "counting one number".
Counting clicks isn't counting, it's bookkeeping. So the system stores every tap verbatim first, counts into per-minute drawers, gives latecomers a grace period, numbers every receipt against duplicates, and overnight recounts from the original stubs to reconcile — the fast number is for people to look at, the accurate one is what gets paid.
Want the mechanisms, the notation and the diagrams? → Switch to the deep read
On the surface this chapter builds a counter. In substance it builds an accounting ledger on top of stream processing. Once the number turns directly into money, the system's first property is no longer throughput or latency but being reconcilable, recomputable, and neither double-counted nor dropped. The authors use this problem to walk through the three hardest things in stream processing — event time and watermarks, exactly-once semantics, and hot partitions — in correctness-first order.
This is Chapter 6 of Volume 2, right after Ch4 (building a distributed message queue by hand) and Ch5 (the time-series write path of a monitoring system): the first hands this chapter the replayable log it lives on, the second the pattern for aggregating huge write volumes into time windows. What it adds is a constraint neither earlier chapter had — the result has to be good enough to bill from. In the real world it maps to the billing and reporting pipelines behind Google Ads and Meta Ads, and to the Kafka + Flink + Druid/Pinot chain that is close to an industry default today.
Put the scale on the table first. The book's numbers: 1 billion clicks per day, 2 million ads in the catalog. A billion over 86,400 seconds is ~10K QPS on average; taking peak as 5× average gives 50K QPS at peak. A click event is about 0.1 KB (ad id, timestamp, user id, IP, country), so ~100 GB of raw data a day and ~3 TB a month.
Two deliverables: the click count for a given ad_id over the last M minutes, and the top 100 most-clicked ads each minute, both filterable by IP, user and country. End-to-end latency should be "within a few minutes" — milliseconds aren't needed, but neither is tomorrow acceptable.
What actually sets the tone is one line among the non-functional requirements: this data is used for billing. Undercount and the platform gives impressions away; overcount and you have overcharged a customer, which is a compliance and trust problem. Almost every design choice downstream — why the raw log must be persisted, why event time, why exactly-once is non-negotiable — can be derived backwards from that line. Put bluntly: nobody sues you when a monitoring metric drops a few points; an ad invoice off by a cent is a different matter.
Click events don't go straight into a database; they go into Kafka. The reason isn't only smoothing out peaks: this log is the single source of truth for the whole system. Raw events are also forked to object storage (S3 / HDFS) with a retention measured in months — every recomputation, reconciliation and definition change works by running it through again.
There is one design in the book that is easy to skim past: aggregation results are not written to the database directly, but into a second queue. One consumption step has to do two things — persist the result and advance the read position (offset) — and those two live in different systems, so they are not naturally atomic; crash in between and you either double-count or lose data. Adding a queue collapses atomicity into one place (the queue's transactional commit), and the downstream database write is made idempotent, so a replay writes nothing wrong.
The computation has the shape of MapReduce, only running on a stream: map nodes validate, clean and enrich (resolving an IP to a country, say), then hash on ad_id to fan events out; aggregate nodes keep "count per ad_id per minute" in memory; reduce nodes merge the partial results into a global top N.
A sense of scale for why this works: 2 million ad_ids, one counter row each per minute (id plus count, a dozen-odd bytes), so a full minute's count table is on the order of tens of megabytes — comfortably in one machine's memory. Top 100 is maintained with a min-heap of capacity 100, and one pass over 2 million rows is O(n log 100) — log 100 is under 7, i.e. a constant factor, so this step is not the bottleneck. The real bottlenecks are always whether partitions are even and whether state can be persisted reliably — never raw compute.
A click carries two times: when it happened (event time, stamped by the client into the data) and when it was received (processing time).
Processing time is far simpler to implement — no waiting, no buffering of out-of-order data, seal the window the moment the clock ticks. But it files "the user tapped on the subway and the phone only sent it after surfacing" into the wrong minute, and around midnight into the wrong billing day. For a report that is an error; for an invoice it is a wrong entry. So the chapter picks event time.
The price is confronting out-of-order arrival: a click with event time 12:00:30 may only land at 12:03. The answer is a watermark — after the window's nominal boundary passes, wait a while longer before sealing and settling. This is a bet with a posted price: wait 3 minutes and almost every straggler is recovered, at the cost of end-to-end latency going from ~1 minute to ~4; wait 30 minutes and the extra recovery is marginal while the delay strips the live dashboard of its point. And a watermark never truly covers the tail — what handles "hours late" is the batch backfill below.
A tumbling window cuts time into abutting, non-overlapping cells, one per minute. Billing can only use it: overlap the windows and a single click falls into two of them and is counted twice. A sliding window advances a small step at a time with heavy overlap, which suits "the hottest ads in the last 5 minutes".
There is a cheap trick in practice: compute only tumbling windows in the stream, land them in the OLAP store, and answer "the last M minutes" at query time by summing M one-minute cells — moving the cost of a sliding window from "maintained in memory forever" to "summed on read".
Table 1 · The three delivery semantics, and why this problem must buy the most expensive one
| Semantics | Meaning | Cost | Usable here? |
|---|---|---|---|
| At most once | No retry; a failure loses the event | Cheapest, fastest | No — a loss is money not collected |
| At least once | Retry on failure, duplicates possible | Cheap, but results skew high | Not alone — needs dedup |
| Exactly once | Effect equivalent to processing once | Lower throughput, latency jitters with checkpoints | Required — the books must balance |
What needs clearing up: "exactly once" never meant the message crossed the network exactly once. Transmission still duplicates whenever it must; what is guaranteed is that the effect landing in the result is equivalent to processing it once (end-to-end exactly-once). Two implementation routes:
16 GB of 16-byte keys alone, so it needs expiry, sharded by time window and dropped a whole shard at a time.People reach for a Bloom filter (a probabilistic structure that answers "have I seen this value?" using little memory) to shrink dedup cost — careful: it has false positives, so it will judge a never-seen click a duplicate and drop it, which in billing terms means undercharging. It is only good as a coarse pre-filter; anything it calls "possibly seen" must still be checked against the exact store.
Hashing on ad_id assumes traffic is roughly even across ad ids. Advertising is precisely not that: one giant advertiser running a promotion can drive a single partition to dozens of times the average, and a partition can only be processed by one consumer, so adding machines does not rescue it.
The standard answer is two-stage aggregation: append a random suffix to the hot key, splitting ad_id into ad_id:0 … ad_id:N spread over N partitions that each count locally, then have a second stage add the N parts back together. Three costs: the extra merge latency, the need to identify hot keys dynamically (today's hot key may not be tomorrow's), and the split factor N itself having to track traffic.
The streaming result is "the fast one". Separately, a batch job runs once a day, recounts yesterday from the raw log in object storage, compares it ad by ad against the streaming result, alerts past a drift threshold, and settles on the batch figure.
That same raw log also powers recomputation: when a definition changes or a bug surfaces, replay the log from a chosen point into a fresh table, verify, then cut over — no rewriting history, no downtime. This is exactly the Kappa move: don't maintain two codebases, maintain one replayable log.
Every trade-off in this chapter collapses onto one axis: accuracy ↔ latency ↔ cost, and you cannot maximise all three — which is precisely the trio standing side by side in the title of Google's Dataflow paper.
Table 2 · Two architectures: Lambda vs Kappa
| Lambda (batch + stream) | Kappa (one stream + replayable log) | |
|---|---|---|
| Correctness | The batch path is authoritative and eventually right | Replaying the same log yields the same result |
| Code | The same logic written twice; the two definitions drift apart over time | One implementation; changing logic means a replay |
| Latency | Fast path in minutes, authoritative result T+1 | Minutes; recomputation on demand |
| Cost | Two clusters, two operational burdens | One cluster, but longer log retention costs more |
| Fits | Heavy regulation demanding an independent authority | Most realtime analytics; the chapter's pick |
The chapter picks Kappa but keeps a daily batch reconciliation line — strictly "Kappa in the lead with batch as auditor", which is also where most real advertising companies settle.
Table 3 · How long should the watermark wait (this chapter: 1B clicks/day, minutes end-to-end)
| Grace period | What it covers | End-to-end latency | Cost |
|---|---|---|---|
3 s | Only network jitter | < 1 min | High late rate, the books don't balance; dashboards only |
3 min | Most mobile re-sends | ~4 min | The sweet spot; the chapter's choice |
30 min+ | Marginal extra recovery | Half an hour plus | Live reporting loses its point |
| None; leave it to batch | 100% coverage | T+1 | No realtime view; day-end settlement needs this layer regardless |
Two more judgements that don't fit a table:
This problem is the canonical specimen of correctness-first stream processing, and that is exactly what an interview is testing: whether, after you say "Flink windowed aggregation", you add unprompted, "but this number gets billed, so I need event time, exactly-once, and a reconciliation line." In practice the chain has almost hardened into Kafka (the log) + Flink (stateful streaming) + Pinot / Druid / ClickHouse (OLAP queries) + S3 / HDFS (raw data and batch reconciliation).
3 TB.① The crux isn't "count fast" but "count well enough to bill from" — that one non-functional line, "used for billing", derives every design downstream.
② Scale: 1B clicks/day, 2M ads → 10K QPS average, 50K QPS peak, ~100 GB/day, ~3 TB/month; minutes end-to-end.
③ Land a replayable log first (Kafka + object storage) as the single source of truth; write aggregates into a second queue so atomicity collapses into one place.
④ The computation is map–aggregate–reduce on a stream: hash by ad_id, count per minute in memory, merge top N with a min-heap. Bottlenecks are partition evenness and state durability, not compute.
⑤ Billing requires event time; the price is out-of-order data, handled by a watermark that holds the window open a few more minutes — a bet, not a guarantee.
⑥ Billing can only use tumbling windows (no overlap); "the last M minutes" is answered by summing M one-minute cells at query time.
⑦ Exactly-once is about effect: either transactions / two-phase commit, or at-least-once plus UUID idempotent dedup — whose hidden cost is the dedup store (a billion keys a day).
⑧ Hot advertisers saturate a single partition; fix it with random-suffix two-stage aggregation.
⑨ The ballast is daily batch reconciliation plus replayable recomputation: the fast number is for people to look at, the accurate one settles the bill.