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.

7. Sizing a Count-Min Sketch (The Actual Math)

The two error knobs map directly to the matrix dimensions:

• Width w = ⌈e / ε⌉ — controls how much you over-count. With ε = 0.001 (0.1% of total stream count), width ≈ 2,719 counters per row.
• Depth d = ⌈ln(1/δ)⌉ — controls the probability the error bound holds. With δ = 0.01 (99% confidence), depth = 5 rows.

So a sketch guaranteeing "estimates within 0.1% of stream size, 99% of the time" needs 5 × 2,719 ≈ 13,600 counters — about 54 KB with 4-byte counters. That is the magic of the structure: error scales with stream size, memory scales with error tolerance, and the number of unique keys is irrelevant.

The failure mode to understand: CMS always over-estimates, never under-estimates. For heavy hitters this is convenient — a true heavy hitter can never be missed by the sketch itself; you can only get false trending candidates from long-tail collisions. That's why the architecture keeps a candidate heap: the sketch nominates, the heap (with exact counts for a few hundred candidates) verifies.

8. The Companion Heap: From Counting to Top-K

The sketch answers "how many times did X appear?" but not "what are the top items?" — you can't iterate a sketch. The standard pairing:

For each incoming item:
    1. cms.add(item)
    2. est = cms.estimate(item)
    3. if est > heap.min() or heap.size < K:
           heap.push_or_update(item, est)   # keep only K entries

The min-heap holds exactly K entries, so total memory is O(sketch + K) — independent of stream cardinality. This add-then-check loop is O(1) amortized per event, which is what lets a single Flink task process hundreds of thousands of events per second.

9. Alternative: Lossy Counting

When you need frequencies with guarantees rather than a probabilistic estimate, Lossy Counting offers a different trade:

1. Divide the stream into buckets of width ⌈1/ε⌉.
2. Maintain a table of (item, count, max_error) entries; increment counts for seen items.
3. At each bucket boundary, evict every entry whose count + max_error ≤ current_bucket_id.

Items that are truly frequent survive the purges; long-tail noise is repeatedly evicted. The guarantee: every item with true frequency above εN is retained, and counts are under-estimated by at most εN. Memory is O((1/ε)·log(εN)) — larger than CMS but with deterministic (not probabilistic) bounds. Choose Lossy Counting when a missed heavy hitter is unacceptable (billing, abuse detection); choose CMS when raw speed and tiny memory win (trending, dashboards).

10. Production Considerations

• Merging across workers: CMS matrices with identical dimensions and hash functions merge by cell-wise addition. This makes the distributed story clean — every Flink partition keeps a local sketch, and the aggregator sums them. The merge property is also what enables the sliding-window trick of one sketch per minute.
• Skew is your friend: real streams follow Zipfian distributions (a few keys dominate). CMS accuracy on heavy hitters is far better than the worst-case bound suggests, because collisions mostly involve tiny counts.
• Hot-key detection doubles as protection: the same sketch that finds trending hashtags can flag a hot shard key or a DDoS source IP. Many teams run one sketch per API endpoint for exactly this reason — see Rate Limiting.
• Don't forget exact truth at rest: streams give the real-time view; a nightly MapReduce batch over the raw logs produces the authoritative counts and lets you measure the sketch's actual observed error.

Summary

1. Exact Count: Impossible with limited RAM — a hash map dies on the long tail.
2. Count-Min Sketch: kilobytes of memory, O(1) updates, always over-estimates; pair with a K-sized heap for Top-K.
3. Lossy Counting: deterministic error bounds at higher memory cost — for when missing a heavy hitter is not an option.
4. Architecture: Kafka → stream processor with local sketches → merged aggregate → Redis ZSET serving the API.

Related Concepts

• Bloom Filters
• HyperLogLog
• MapReduce
• Kafka Architecture