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 the core algorithm behind Twitter Trending, Google Search Suggestions, and DDoS Detection.

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

With just a few kilobytes, you can count billions of items with 99.9% accuracy.

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 get "Last 5 mins", merge the 5 sketches (Sum their cells).
2. Exponential Decay:
   • Multiply all counters by 0.9 every minute. Old values fade away.

6. Architecture (Design Twitter Trending)

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 "#systemdesign" 1
5. API: ZRANGE trending 0 9 returns the global Top 10.

Summary

1. Exact Count: Impossible with limited RAM.
2. Count-Min Sketch: O(1) space and time, with controllable error rate.
3. Lossy Counting: Another popular algorithm for this problem.