Design Top-K Heavy Hitters

Prompt

"Design a service that returns the top 100 most frequently searched queries over the last hour, and over the last day. Searches arrive as a stream. Results should be available within about a minute."

Clarifying questions

• What is the key space? Search query strings. Effectively unbounded: hundreds of millions of distinct queries per day, with a long tail of one-offs.
• How exact must the top 100 be? Approximate is fine for the dashboard, but the ranking of the top few should be stable and the counts should be within a few percent. A separate exact daily report is desirable.
• What windows? Sliding one hour and sliding one day, with a minute of granularity acceptable. Not every possible window length.
• Is there a filter dimension? Yes: country. Assume ~200 values. No arbitrary dimensions.
• Freshness? Under 60 seconds from event to visibility.
• Do we count unique users or raw events? Raw events. Unique users is a follow-up.

Requirements

Functional

• Ingest a stream of (query, country, timestamp) events.
• top(k, window, country) returns the k heaviest keys and their approximate counts.
• Support k up to 1,000 and windows of 1 hour and 24 hours.

Non-functional

• Freshness under 60 s; query latency under 100 ms.
• Bounded memory regardless of key cardinality.
• Stated, measurable error bounds on counts.
• No single machine sees the whole stream: the design must be distributed from the start.

Back-of-envelope

• Assume 100,000 search events per second average, peak 300,000/s. Per day: 100 K x 86,400 = 8.6 billion events.
• Distinct queries per day: assume 500 million. A 40-byte string plus an 8-byte counter per key is ~48 bytes; exact per-day counting would need 500 M x 48 B = 24 GB per country slice worst case, and 200 countries could multiply that (in practice most countries are small, but a global slice alone is 24 GB). Doable on a big machine, impossible per aggregator node at peak throughput with low latency, and pointless for a top-100 answer. This is the argument for sketches.
• Event size on the wire: ~100 bytes. Ingest bandwidth: 300 K x 100 B = 30 MB/s peak. Small.
• Sketch sizing: a count-min sketch with error factor 0.0001 (relative to total count) and confidence 99.9% needs width W = e/0.0001 ≈ 27,000 and depth D = ln(1/0.001) ≈ 7: 189,000 counters x 4 bytes ≈ 760 KB. Per minute, per country, that is 760 KB x 200 countries ≈ 150 MB/minute of sketch state, about 220 GB/day. Big but it lives in cheap storage, and most countries can use narrower sketches.
• Top-K lists per minute: 1,000 entries x 60 bytes = 60 KB per minute per country. Trivial.