Design a Top-K Service: Trending Items at a Million Events a Second
Design a top-K trending service — count-min sketch plus a min-heap, sliding windows, sharded merges, and the capacity math for 1M events/sec over 500M items.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
"Show me the top 10 trending hashtags right now" sounds like a GROUP BY ... ORDER BY count DESC LIMIT 10. It is — until the stream hits a million events a second and the distinct items number in the hundreds of millions, at which point the exact query needs gigabytes of RAM and a full sort on every refresh.
The trick that makes top-K tractable is giving up exactness where it doesn't matter. You don't need to know #worldcup has exactly 4,192,013 mentions — just that it beats everything except #election, and roughly by how much. That concession — approximate counts for the long tail, exact tracking only for heavy hitters — is the whole design.
This follows the standard interview rubric: requirements, capacity math, the count-min-sketch-plus-heap core, then the deep dives that get probed hardest — sliding windows, sharding, and Space-Saving.
What the service actually has to do
Functional requirements are short: ingest a stream of events, each carrying an item_id. Answer one query — the K most frequent items, optionally scoped to a window like "the last hour." K is small and known ahead: top 10, top 100, rarely more.
Non-functional requirements are where the design lives:
- Write throughput: ~1M events/sec at peak, no dropped stream.
- Query latency: single-digit milliseconds — dashboards poll constantly.
- Accuracy: 99.9% — heavy-hitter counts within 0.1% of true, and the ranking of the top K almost never wrong.
- Memory: bounded and constant, never growing with distinct items ever seen.
That last bound is what kills the naive design.
Why counting everything doesn't scale
The obvious approach keeps an exact HashMap<item, count>, increments on each event, and at query time sorts every entry for the top K.
function naiveTopK(events, k) {
const counts = new Map();
for (const item of events) {
counts.set(item, (counts.get(item) || 0) + 1);
}
return [...counts.entries()]
.sort((a, b) => b[1] - a[1]) // O(U log U) — U = distinct items
.slice(0, k);
}The problem is the long tail: hundreds of millions of distinct keys, most seen once or twice. Held in one place, 500M keys at ~40 bytes each is ~20 GB, and the query-time sort is O(U log U) — far too slow on demand. You'd be paying to precisely count millions of items that will never crack anyone's top 100.
The fix: spend almost no memory on the tail, and exact memory only on the K items that might actually rank.
The core: count-min sketch plus a min-heap
A count-min sketch is a fixed-size frequency estimator: a d × w array of counters with d independent hash functions. To record an event, hash the item with each function and increment the counter it lands on in every row. To estimate a count, take the minimum across the d rows — collisions only ever inflate a counter, so the smallest row is closest to truth.
w columns ->
row 0 (h0): [ 0 3 0 1 ... ]
row 1 (h1): [ 1 0 2 0 ... ] estimate(x) = min over rows of row_i[h_i(x)]
row 2 (h2): [ 0 0 1 4 ... ]The error is bounded: an estimate over-counts by at most ε·N/w with probability 1 − e^(−d), giving a sizing formula for error within ε·N at confidence 1 − δ:
w = ceil(e / ε) d = ceil(ln(1 / δ))The sketch tells you how big an item is in constant space. Pair it with a min-heap of size K: increment the sketch, look up the estimate, and if it beats the heap's minimum (or the heap isn't full), insert it, evicting the old minimum if needed. Memory is the sketch plus K entries; per-event cost is O(d + log K). A side hashmap tracks what's already in the heap so an existing item updates in place.
Walkthrough: top-2 hashtags in a live stream
Take K = 2, sketch returning exact counts (small enough that nothing collides):
| Event | Est. count | Rule fired | Heap after |
|---|---|---|---|
| #ai | 1 | not full → add | {#ai:1} |
| #dsa | 1 | not full → add | {#ai:1, #dsa:1} |
| #ai | 2 | update in place | {#ai:2, #dsa:1} |
| #cats | 1 | full, 1 > min(1)? skip | {#ai:2, #dsa:1} |
| #ai | 3 | update in place | {#ai:3, #dsa:1} |
Final top-2: #ai (3), #dsa (1) — the true answer. #cats never dislodged anyone because its estimate never beat the heap-min. Had it spiked past 1 later, it would kick #dsa out, then flicker back in if #dsa surged again — harmless for a dashboard, but exactly what Space-Saving (below) is built to eliminate.
How do you compute top-K over a sliding window?
"Trending in the last hour" means old events must age out, or a single ever-growing sketch reports last month's viral moment forever. The fix is a bucketed sketch: B sub-sketches, one per time slice — e.g. 60 one-minute sketches covering a rolling hour.
Each event increments only the current bucket; a query sums the sub-sketches pointwise. When the clock advances, the oldest bucket is zeroed and reused, so memory never grows. The heap is rebuilt at each rotation by re-scanning candidates, so anything that trended 61 minutes ago quietly falls off.
Granularity is a direct trade: 60 one-minute buckets give minute-level freshness at 60× the memory of one sketch; 12 five-minute buckets cut memory to a fifth but blur the edge by up to five minutes.
How do you shard across machines and merge correctly?
One node can't ingest 1M events/sec, so partition by item_id hash — every occurrence lands on the same shard, keeping local counts exact. Each shard keeps a local top-K′ heap where K′ = α·K (say 4K) — a margin beyond the K it strictly needs.
An aggregator pulls every shard's top-K′ and merges into the global top-K. The subtlety: a naive merge can miss an item ranked just below the cutoff on several shards that sums to a global winner. The fix treats each shard's K′-th score as a ceiling on what it didn't report, trusting a rank only once no combination of those ceilings could displace it. Under a random partition, K′ = O(K·√shards) catches the true top-K with high probability — why the margin α exists. (Hash partitioning has one weak spot — a single overloaded key — covered in the FAQ.)
Capacity estimation: 1M events/sec, 500M items, 99.9%, top-100
Target error ε = 1e-4 of N, confidence δ = 1e-3:
w = e/ε ≈ 27,183columns,d = ln(1/δ) ≈ 7rows.- One sketch: 27,183 × 7 ≈ 190k counters × 4 bytes ≈ 760 KB.
- 60 one-minute buckets: 60 × 760 KB ≈ 45 MB per shard; the K=100 heap adds ~10 KB.
Throughput needs 10 shards at ~100k updates/sec each, ~20 nodes with replication. Query QPS stays low — reads come from heap snapshots, not recomputation.
Compare the exact design fairly, sharded the same way rather than as one unsharded total: 500M items / 10 shards is ~50M keys/shard × 40 bytes ≈ 2 GB per shard (20 GB system-wide) against the sketch's 45 MB per shard — roughly 44× less memory, plus the O(U log U) sort the exact design still owes per query. That 44×, not the far bigger number from comparing an unsharded total to a sharded footprint, is the justification for the sketch.
Deep dive: when Space-Saving beats count-min plus heap
Space-Saving (Metwally et al.) tracks exactly K+1 counters in a Stream-Summary structure. On a miss it replaces the minimum counter with the new item, setting its count to min + 1 — absorbing the evicted count as an error bound. It uses O(K) memory instead of O(1/ε) and is usually more accurate for pure top-K because the replacement is monotonic.
Pick Space-Saving when only the top-K heavy hitters matter — tighter error, less memory, no flicker. Pick count-min when you also need point queries for arbitrary items, or need to merge sketches from many streams additively (sketches sum cleanly; Stream-Summaries don't). Most trending systems layer both.
How this shows up in interviews
Say "hashmap and sort," and a good interviewer asks for the distinct-item count — the memory bound is the reason to switch to a sketch. From there the probes are predictable: derive the w = e/ε, d = ln(1/δ) sizing; handle a sliding window; shard the writes and defend the merge margin; account for a hot key.
The strongest signal is naming the flicker caveat before you're asked and offering Space-Saving as the fix, then stating the one knob you'd turn if the workload changed: window granularity, ε, or shard count.
Further learning
- "Top-K System Design Interview w/ Ex-Meta Senior Manager" — Hello Interview — a full mock covering the sketch, the heap, and the sharded merge.
- Practice this topic on YeetCode — step through the design interactively.
Related designs that share the streaming-and-sharding toolkit: Design a Proximity Service, Design YouTube, Design Instagram, and Design Twitter.
FAQ
Why not just use a database GROUP BY for top-K trending?
The grouping isn't the bottleneck — the sort is. GROUP BY item_id ORDER BY count DESC LIMIT K still materializes one group per distinct key before sorting, an O(U log U) scan re-run on every poll. For 500M items that's ~20 GB of exact counters in one place, or ~2 GB per shard partitioned like the sketch — either way, orders of magnitude more than the sketch's fixed footprint.
How does a count-min sketch avoid unbounded memory?
It never stores item identities — just a fixed d × w grid of counters every item hashes into. Memory is set once by the accuracy target (w = e/ε, d = ln(1/δ)) and never grows with the number of distinct items seen. A ~760 KB sketch tracks a universe of hundreds of millions of keys.
Could you shrink a rolling window by decrementing old counts instead of bucketing?
Not safely. The estimate only works because collisions can only inflate a counter — decrementing to expire old events could push a shared cell below the true count for an unrelated key hashed into it. Bucketing never subtracts: each bucket only increments, and an expired one is zeroed and reused. The real knob is bucket count versus freshness.
What happens when a single item goes viral and floods one shard?
Hashing by item_id lands all of an item's traffic on one shard — great for exactness, painful when that item spikes and its rate becomes the bottleneck. The fix: detect the skew and split that hot key onto a secondary ring of mini-shards, folding its total back into the merge with everyone else's top-K′.
Why doesn't Space-Saving suffer the heap's "flicker" problem?
A near-cutoff item's count-min estimate can drift up or down between events, occasionally overtaking the heap-min and later losing again. Space-Saving avoids this by construction: it only replaces the single smallest of its K+1 counters, absorbing the evicted count into the new item's floor, so a counter is monotonic non-decreasing while it stays — the safer pick when a UI can't tolerate visible churn near the list's bottom.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.