Top K Trending
IntermediateOverview
A top-K system continuously answers "what are the K most frequent items right now" - trending hashtags, most-viewed videos, top search queries, best-selling products. The hard part is scale: you cannot keep an exact counter for billions of distinct items in memory, so the design leans on approximate counting (count-min sketch) for real-time answers and an accurate batch recompute for correctness - a textbook Lambda architecture.
Functional Requirements
- Return the top K items by frequency over a time window (last hour, day, or all-time).
- Update rankings in near real time as events stream in.
- Support multiple windows and multiple item types (hashtags, videos, queries).
Non-Functional Requirements
- Scalable: ingest millions of events/sec across billions of distinct items.
- Low latency: reading the current top-K is a fast, cached lookup (< 100 ms).
- Approximate is acceptable for the real-time view; the batch layer provides exactness.
- Memory-bounded: cannot store an exact counter per distinct item.
Capacity Estimation
Assume 10M events/sec (e.g., hashtag mentions), over 1B distinct items, K = 100.
- Ingest: 10M/s events feed the counting layer; at ~50 bytes/event that's ~500 MB/s into the pipeline.
- Exact counting is infeasible in memory: 1B items x (key + 8-byte counter) ~ tens of GB per window per node - and that's before replication. This is the core motivation for a Count-Min Sketch, which uses a fixed few MB regardless of item count.
- Output: the top-K list is tiny (100 items) and served from cache at very high QPS.
The gap between 1B distinct items and a few MB of memory is exactly why approximate structures exist.
High-Level Architecture
The architecture uses the Lambda pattern. Events stream into Kafka. A real-time 'Speed Layer' (e.g., Flink/Spark Streaming) uses a probabilistic data structure (Count-Min Sketch) to estimate counts and maintain a running Top-K list in Redis. Simultaneously, a 'Batch Layer' (Hadoop/Spark) runs hourly over the raw logs to compute the perfectly accurate Top-K, overwriting the approximate real-time data.
Data Model
| Entity | Fields / Schema | Storage Choice |
|---|---|---|
| event | item_id, ts, type | Partitioned log (Kafka), partitioned by item_id |
| sketch | count-min sketch matrix + min-heap of current top-K | In-memory (per shard), snapshotted to disk |
| topk_realtime | window, ranked [item_id, approx_count] | Redis (fast read) |
| topk_accurate | window, ranked [item_id, exact_count] | KV / columnar store (batch output) |
Detailed Design
Speed Layer: Count-Min Sketch + Heap
A Count-Min Sketch is a probabilistic data structure consisting of a 2-D array of counters and several hash functions. To count an item, hash it with each function and increment the corresponding cells; to estimate its count, take the minimum across those cells (which bounds the overestimate from hash collisions). It uses fixed memory (a few MB) for any number of distinct items, never undercounts, and only ever overcounts - perfect for "trending."
Alongside the sketch, each shard keeps a min-heap of size K. When an item's estimated count exceeds the heap's minimum, it enters the heap. This gives an approximate top-K per shard in constant memory.
Sharding and Merging
The event log is partitioned by item_id so each shard counts a disjoint slice. An aggregator node then merges the per-shard heaps into a global top-K. Partitioning by item keeps each item's counts on one shard, preventing double-counting issues during aggregation.
Batch Layer: Exact Recompute
In parallel, raw events land in storage (S3) and a periodic MapReduce job counts every item exactly, producing an authoritative top-K for each completed window (e.g., every hour). This corrects the sketch's approximation and handles all-time or long-window rankings that the speed layer can't hold.
Time Windows
For a sliding window (e.g., "last hour"), we maintain a sketch per time bucket (e.g., per minute) and sum the last 60 buckets, expiring old buckets. This keeps counts scoped to the window without unbounded memory.
Bottlenecks & Solutions
The biggest operational pain is managing the Sliding Windows. If you want a "Last 24 Hours" sliding window updating every minute, keeping 1,440 minute-level sketches and summing them every second is very CPU intensive. A common optimization is to use exponential decay (reducing the weight of older counts over time) rather than strict sliding windows, which requires far less memory and CPU.