System Design Lab›System Design Questions›Design Top-K Heavy Hitters
Design Top-K Heavy Hitters
MediumData Processingstreamingrankingdistributedreal-time
Question Overview
Design a system that continuously ranks the most viewed or most searched items across billions of events per day. It tests stream partitioning, counting in bounded memory with sketches and heaps, sliding windows, and how an approximate real-time path is reconciled with an exact batch path.…
Sign up to see the full question and AI interviewer
Requirements
- Ingest a continuous stream of view or search events keyed by item ID
- Return the top K items, K up to 1,000, for 1-minute, 1-hour, and 24-hour sliding windows
- Support global rankings plus per-region and per-category rankings
- Fast-path rankings at most about 1 minute stale, with bounded approximation error
- Exact historical counts for reporting, produced by a batch path over raw events
- Read API under 50 ms at p99, served from precomputed rankings
Back-of-the-envelope numbers
- Ingest: 10B events/day ÷ 86,400 s ≈ 116K events/s average, ~350K/s at 3× peak
- Bandwidth: 116K/s × 100 B ≈ 11.6 MB/s average (~35 MB/s at peak); the raw log is 10B × 100 B = 1 TB/day
- Exact minute buckets: 116K/s × 60 ≈ 7M events/minute, so ≤ 7M keys × ~50 B ≈ 350 MB per bucket, and 1,440 buckets ≈ 500 GB worst case
- Count-min sketch: width 2^17 ≈ 131K × depth 5 × 4-byte counters ≈ 2.6 MB per bucket, so 1,440 minute sketches ≈ 3.8 GB
- Sketch error: a 1-hour window holds 116K × 3,600 ≈ 420M events; overcount ≤ (e ÷ 131K) × 420M ≈ 8.7K with probability 1 − e^-5 ≈ 99.3%
- Merge: 100 counting partitions × local top 1,000 = 100K candidates per minute to the merger, trivially sorted in memory
- Reads: 10K QPS served from precomputed lists in cache; a K = 1,000 response of ~50 KB caps egress at ~500 MB/s
Key components
- Ingestion log: a Kafka topic partitioned by item_id hash, so every event for an item reaches the same counter and local top-K lists merge exactly
- Stream counters (Flink or Kafka Streams) keeping per-minute counts per partition in a hash map or count-min sketch plus a min-heap of candidates
- Local combiners that pre-aggregate repeated keys before partitioning, shrinking traffic and softening hot keys during viral spikes
- Window assembler that forms 1-hour and 24-hour sliding windows by adding the newest minute bucket and expiring the oldest one
- Top-K merger that combines each partition's local top-K into the global list and writes it to a cache keyed by window and dimension
- Batch path: raw events archived to object storage and recounted exactly by hourly and daily Spark jobs that correct the fast path
- Read API that only serves precomputed rankings from cache and never counts on request
Common mistakes
- Keeping an exact hash map of all 100M items for every window and dimension on one machine, which fails once windows multiply
- Merging local top-K lists from randomly split partitions; an item moderately popular everywhere can be globally top yet missing from every local list
- Using a count-min sketch without a heap or candidate set; the sketch estimates a given key's count but cannot list the heavy keys
- Computing the ranking at read time by scanning counters instead of precomputing it continuously and serving from cache
- Recomputing the whole 24-hour window every minute instead of maintaining minute buckets that are added and expired
- Ignoring hot keys: a viral item sends all its events to one partition unless events are pre-aggregated first
- Serving approximate sketch counts in reports that need exact numbers, instead of backfilling them from the batch path
Likely follow-ups
- How would you answer top-K for an arbitrary past range, such as 2 PM to 5 PM last Tuesday?
- What happens when one item receives 30% of all events during a viral spike?
- How would you stop bots from pushing an item into the trending list?
- How would you size the count-min sketch so its error is small relative to the K-th item's count?
- How would you add per-country rankings for 200 countries without 200× the cost?
- How do late or duplicated events affect your counts, and how does the batch path correct them?
No community solutions yet
Be the first to publish your solution
Practice ‘Design Top-K Heavy Hitters’ with an AI Interviewer
Get scored feedback on your diagram, scalability approach, and trade-offs. Free while we grow — up to 3 full interviews a day.