Top K Heavy Hitters System Design: From Count-Min Sketch to Serving

The top K heavy hitters system design question asks you to find the K most frequent items in a huge, never-ending stream: the most-viewed videos in the last hour, the most-searched queries today, the IP addresses sending the most requests right now. The core decision is exact versus approximate counting. Exact counts need memory proportional to the number of distinct items; a count-min sketch plus a small heap answers from kilobytes of memory with a bounded overcount. Strong answers usually run both: a fast approximate path for "right now" and a slower exact path for numbers that must be right.

This prompt differs from two neighbors. A leaderboard ranks users by a score they update, which a sorted set handles. An ad click aggregator counts known keys accurately for billing. Here the item space is enormous, the stream is unbounded, and you only care about the top of the distribution.

1. Requirements and scale estimates

Functional requirements

• Return the top K items (K up to about 1,000) by event count for the last minute, hour and day.
• Optionally slice by a dimension such as country or category.
• Return each item's count, and say whether it is exact or estimated.

Non-functional requirements

• High, bursty write throughput; ingestion never blocks on the ranking.
• Fresh results within seconds to a minute for short windows; low-latency reads.
• Approximate is acceptable for short windows; ask whether daily numbers feed anything money-related, because that forces an exact path.
• Replays after failures must not double count.

Pin down the definitions too. Heavy hitters are every item whose count exceeds a fraction φ of the total N (there are always fewer than 1/φ of them). Top K is the K largest counts, whatever they are. On skewed traffic, which real traffic usually is, the two coincide. On flat traffic, the top K is fuzzy for any approximate method, so say that out loud.

The takeaway: one exact daily window is feasible on a sharded cluster, but exact state multiplies with every window size and dimension, while a sketch stays tiny and its memory grows only with 1/ε.

2. Exact vs approximate top K heavy hitters

Space-Saving keeps m counters; when a new item arrives and all are taken, it evicts the item with the smallest count and gives the newcomer that count plus one, so no item is overcounted by more than the smallest counter value, which is at most N/m. Misra–Gries instead decrements every counter when it is full, so it undercounts. Interviewers rarely need proofs; they want to hear that deterministic counter-based summaries exist next to sketches and that both can be merged across machines.

3. How the count-min sketch finds the top K

A count-min sketch is a grid of d rows by w columns of counters, with one hash function per row. Every event increments one counter in each row; a query takes the minimum across rows:

• update(x): for each row j, C[j][h_j(x)] += 1
• estimate(x): min over j of C[j][h_j(x)]

Collisions only ever add to a counter, so the estimate never undercounts. In Cormode and Muthukrishnan's paper, choosing w = ⌈e/ε⌉ and d = ⌈ln(1/δ)⌉ bounds the overcount by εN with probability at least 1 − δ, where N is the total count in the sketch. That is where the 109 KB figure in the table comes from.

The sketch does not remember which items it has seen, so it cannot list the top K by itself. Pair it with a min-heap of K candidates plus a hash map from item to heap entry, the same structure as the heap pattern in coding rounds:

1. Update the sketch for the incoming item and read its new estimate.
2. If the item is already a candidate, update its count in the heap.
3. Otherwise, if the heap holds fewer than K items or the estimate beats the heap's minimum, evict the minimum and insert the item.

Know the failure mode: a light item that collides with heavy ones gets an inflated estimate and can sneak into the heap. Three fixes are worth naming. Conservative update increments only the row counters that equal the item's current minimum, which shrinks overcounts while still never undercounting. A wider sketch lowers ε. And for numbers that matter, re-check the final candidates against exact counts from the batch path.

4. The streaming pipeline: Kafka, windows and hot keys

Events flow from producers into a partitioned, replayable log (Kafka or similar; see our message queue walkthrough), then through a stream processor such as Flink in three stages:

1. Pre-aggregate. Consumers read partitions in whatever order events arrived and keep a small local map per window, flushing partial counts (item, window, count) every few seconds. A viral item's million events become one record per task per flush.
2. Aggregate by key. Partial counts are re-partitioned by a hash of the item, so each item's whole count lives on exactly one task. Each task sums counts per item and window, exactly or in a sketch, and keeps a local top K.
3. Merge. A single merger combines the local top K lists, which is a tiny input: tasks × K items.

Two details here separate strong answers. First, merging local top K lists is only correct because stage 2 partitions by item. If you partitioned randomly, an item ranked K+1 on every machine could be first globally, and no merge of local lists would find it. Second, partitioning by item creates hot keys: the heaviest hitter lands on one task, which is exactly the problem you are solving. Stage 1 pre-aggregation removes that hotspot, because stage 2 then receives at most one partial count per stage-1 task per flush, however popular the item is.

Windows

Use 1-minute tumbling windows as the base unit and build longer views from them: the last hour is the sum of 60 minute buckets, advanced every minute. With exact keyed counts this is exact. With sketches it is half true: sketches with the same width, depth and hash seeds merge by adding counters, so summing minute sketches gives exactly the sketch you would have built over the hour. The candidate list is the hard part. An item that is steady all hour but never in any minute's top K would be missed, so keep candidate lists several times larger than K per bucket and re-estimate their union against the merged sketch.

Window by event time, not arrival time, using watermarks. Flink's window documentation covers tumbling, sliding and session windows; by default late elements are dropped, and you can set allowed lateness or route late events to a side output, which the batch path can fold in later. For fault tolerance, checkpoint operator state together with the Kafka offsets and make result writes idempotent upserts keyed by window, so a replay overwrites rather than double counts.

5. Storage and serving the top K

The output is small. Each closed window writes one record per metric and dimension, keyed like topk:views:country=US:1h:2026-10-14T09:00, holding up to K_max = 1,000 entries of (item_id, count, exact_or_estimate). Keep the latest windows in Redis for reads and the history in a durable store such as Cassandra or a columnar OLAP database.

• API: GET /v1/topk?metric=views&window=1h&k=10&country=US returns items, counts, the window start, an as-of time and an approximate flag. Serve any k up to K_max by slicing the stored list.
• Caching: results change once per window step, so cache them with a TTL equal to that step; they are even CDN-friendly.
• Enrichment: join titles and thumbnails at read time from a metadata cache rather than storing them in the results.
• Exact correction: a daily batch job over raw events in object storage recomputes the exact top K and overwrites the approximate record. That is the lambda pattern; the ad click aggregator walkthrough compares it with a single streaming (kappa) path.

At smaller scale, you might not need a pipeline at all. Redis ships a probabilistic Top-K structure based on the HeavyKeeper algorithm (TOPK.ADD, TOPK.LIST) and count-min sketch commands. One structure per time bucket with an expiry gives you windowed top K on a single node. Mentioning when the simple design suffices is itself a senior signal.

6. Trade-offs and follow-up questions

Expect follow-ups like these: how would you detect a sudden spike (compare the current window with a trailing baseline per item), how would you support deletions or decrements (count-min handles negative updates with weaker guarantees, so prefer exact state), and how would you top K across regions (merge regional sketches or local lists, which works because both summaries are mergeable). For the shared building blocks, keep our system design interview cheat sheet handy, and see the system design interview help page for more prompts.

FAQ

What is the difference between top K and heavy hitters?

Heavy hitters are all items whose count exceeds a fixed fraction of the total, so there can be few or none. Top K is always the K largest counts. On skewed traffic they pick out the same items; on flat traffic the top K is hard to estimate reliably with any approximate method.

How does a count-min sketch find the top K items?

It doesn't on its own, because it only estimates counts for items you ask about. Pair it with a min-heap of K candidates: update the sketch for each event, read the estimate, and insert the item into the heap if it beats the current minimum. The sketch never undercounts, so watch for light items inflated by collisions.

How big should a count-min sketch be?

Set width to e divided by epsilon, rounded up, and depth to the natural log of 1 over delta, rounded up. With epsilon 0.001 and delta 0.01 that is 2,719 columns by 5 rows, about 109 KB with 8-byte counters, and the overcount stays within 0.1% of the total count with 99% probability.

Can you merge top K results from multiple servers?

Only safely if each item's full count lives on one server, which means partitioning by item. With random partitioning, an item just outside every server's local top K can be first overall. Sketches with the same width, depth and hash seeds can be merged by adding counters, and Space-Saving summaries are mergeable too.

How do you compute top K over a sliding window?

Aggregate into small tumbling buckets, such as one minute, and sum the last 60 buckets for an hourly view that advances every minute. With sketches, merge the bucket sketches and re-estimate a union of per-bucket candidate lists, keeping those lists several times larger than K so steady items aren't missed.

When do you need exact top K counts?

When the numbers feed payments, payouts, billing or public reporting, or when items near rank K must be ordered correctly. Run a batch job over raw events that recomputes exact counts and replaces the approximate results, while the streaming path keeps short windows fresh.