Top-K Heavy Hitters (Streaming)

Finding the Top K (The "Trending" Problem)

In a stream of 1 Billion events, how do you find the 10 most frequent items using only 100MB of RAM? This is a useful model for trend detection, query-frequency analysis, and traffic-abuse detection. It is not a description of any named company's private ranking system.

1. Requirements

• Input: A never-ending stream of strings (queries, IPs, hashtags).
• Output: The top 10 most frequent items in the last X minutes.
• Constraint: You cannot store every item. (10B items * 100 Bytes = 1TB RAM).

2. Approach 1: Batch Processing (MapReduce)

If we don't need real-time, we can use a distributed file system.

1. Split: Divide logs into 100 files.
2. Map: Emit (Key, 1) for every occurrence.
3. Shuffle: Group by Key. (Key, [1, 1, 1, 1]).
4. Reduce: Sum the lists. (Key, Total).
5. Sort: Sort by Total and take Top 10.

• Con: High latency. Takes minutes/hours.

3. Approach 2: Streaming with Hash Map

Store HashMap<String, Integer>.

• Problem: In the "Long Tail" of the internet, there are billions of unique keys that appear once. Storing them fills up memory instantly.

4. Approach 3: Probabilistic Data Structures (Count-Min Sketch)

A Count-Min Sketch is a 2D array that trades accuracy for space. It is the "Bloom Filter" of counting.

Structure

• Matrix: A Width x Depth array of counters (e.g., 1000 x 5). Use 0 as initial value.
• Hash Functions: 5 different hash functions ($h_1, h_2... h_5$).

Algorithm

1. Add(Item):
   • Calculate row indices: $r_1 = h_1(item), r_2 = h_2(item)...$
   • Increment Matrix[0][r1], Matrix[1][r2]...
2. Estimate(Item):
   • Get values at all 5 positions.
   • Return the Minimum of these values.
   • Why Min? Because collisions only add to the count. The true count cannot be higher than the minimum observed value.

Space Efficiency

For nonnegative increments, a Count-Min Sketch overestimates frequencies. Width controls the additive error bound; depth controls the probability of exceeding that bound. Error is relative to total stream weight, so rare items may have large relative errors. A sketch cannot enumerate keys; keep a separate candidate set or use a heavy-hitter structure.

5. Sliding Windows

"Trending" means "Popular Right Now", not "Popular since 2010". We need to forget old data.

1. Time Slicing:
   • Create a CMS (Count-Min Sketch) for Minute 1, Minute 2, Minute 3.
   • To approximate "Last 5 mins", sum compatible sketches with identical dimensions and hashes. Bucket boundaries make this an approximate window unless partial buckets are handled.
2. Exponential Decay:
   • Multiply all counters by 0.9 every minute. Old values fade away.

6. An illustrative trend-detection architecture

1. Ingestion: Tweets enter Kafka.
2. Processor: Apache Flink / Spark Streaming workers read the stream.
3. Aggregation:
   • Workers maintain a local Count-Min Sketch in memory.
   • Every 10 seconds, flush the Top 100 candidates to a central Redis.
4. Storage: Redis Sorted Set (ZSET).
   • ZINCRBY trending 1 "#systemdesign"
5. API: ZRANGE trending 0 9 REV WITHSCORES returns the highest scores in the stored candidate set. Local top-100 truncation can omit a globally important key, so validate candidate recall.

Summary

1. Exact Count: Needs storage proportional to distinct keys unless the key universe is bounded; external storage is another option.
2. Count-Min Sketch: For chosen width and depth, memory stays fixed as the stream grows; updates visit every row. Accuracy depends on those parameters and stream weight.
3. Lossy Counting: Another popular algorithm for this problem.

Sources and verification

Redis Count-Min Sketch documentation explains dimensions and error. For a design exercise, feed a burst of a previously unseen key near a window boundary: measure candidate recall, overcount, and expiry lag separately. Exponential decay produces a weighted history, not an exact time window.