Learn / System Design
Module 11 · System Design · Five more whole designs
Continue where you left off ×
Counting clicks in real time (ad click aggregation and top-k)
Before you start. You need three things. A queue is a line that one part of a system writes to and another reads from at its own speed, and a partition is one lane of it (The order slip rail (queues & the utilization cliff) gave you the queue and what happens when it fills). A count-min sketch is a small grid of counters that guesses how often each thing appeared, never too low and sometimes too high (Counting the crowd without a register (HyperLogLog, count-min, top-k) built one). And the six steps of a design round from Design the Whole Thing (the interview, assembled) : clarify, estimate, API, data, design, scale.
The idea in 30 seconds
A click log, partitioned by ad id, is the source of truth. Everything else is derived and can be rebuilt by replay.
Stream processing keeps tallies up to date as clicks arrive, and a tumbling window cuts the endless stream into one-minute counts.
A late event is a click that arrives after its window seemed over. A watermark is the rule for how long to wait.
A hot ad overloads one partition, and the fix is to split that ad across lanes and add the pieces.
A unique click id makes a repeat harmless, which is the practical form of exactly once.
Reconciliation checks a fast approximate count against a slow exact one, and the exact one is what is billed.
Read the story
Lesson 52 of 73 in System Design
The rest of this lesson is part of a plan.
A plan opens every lesson, board, video, lab and paper on chalk. Yearly is $39/year , or $19.50 for your first yearLAUNCH50 , ends 1 Nov, 18:30 UTC .
See plans Already a member? Sign in
Or start free : a free account opens lessons 2 and 3 of every track.
In this lesson 20 February 2002: a click becomes money The click log: the receipt roll that nothing else may contradict Stream processing: a tally that does not wait for closing time Late events and the watermark: when is a minute really over? Hot ad partition: one lane gets the whole stampede The same click twice, and the id that makes it harmless The count-min sketch: a fast answer at a fixed size Reconciliation: the end-of-day count of the roll against the board 1. Clarify 2. Estimate 3. API 4. Data 5. Design 6. Scale The follow-up: top 100 ads in the last minute What to say about scale Terms it explains: click log, Stream processing, tumbling window, late event, watermark, skew, hot partition, click id, count-min sketch, reconciliation.
Review System Design
Mark as read Saved in this browser, and to your account when you sign in.