Top-k / trending

1 · Clarifying questions

The word "top" is doing a lot of work in the prompt. Five minutes of questions usually settles the design before any boxes go on the board.

2 · Capacity math, on a napkin

Pick numbers that justify the sketch. If the answer fits in a hash map, you don't need any of this — say so out loud, then build the version that doesn't.

The two numbers that matter are 25 GB/sec of ingest and 100M distinct items per window. The first sets the scale of the ingest tier; the second is why we reach for a sketch rather than a hash map of exact counters.

3 · API and data model

The wire surface is small. The state behind it is where the design lives.

Endpoints

POST /v1/event              # fire-and-forget, batched by client
{"item_id":"t_8AQ9", "type":"view", "ts":1715990400}
→ 202

GET  /v1/top?window=1h&k=100   # the read path
→ 200 {"window":"1h","computed_at":"2026-05-18T12:03:00Z",
       "results":[{"item_id":"t_8AQ9","score":4129312}, ...]}

GET  /v1/top?window=24h&k=10&segment=us-en
→ 200 {...}                    # optional segment dimension

State

per-window state (real-time path)
  cms              count-min sketch       # fixed-size matrix of counters
  candidates       min-heap of size k+δ   # heavy-hitters set
  decay            per-bucket timestamps  # for sliding-window roll-off

materialised answer
  top_k:{window}   list[item_id, score]   # cached, regenerated every N seconds

historical store (batch path)
  events_raw                              # all events, partitioned by minute
  rollup_1m, rollup_1h                    # exact counts, computed offline

The read path never touches the sketch directly. It reads the materialised top-k list, which the real-time worker regenerates from the sketch and the heavy-hitter heap on a fixed cadence (every 5–15 seconds is typical).

4 · High-level architecture

Four tiers. Ingest absorbs the firehose. Real-time workers maintain the sketch and the heap. A historical store keeps exact counts for backfill and audit. A small query API serves the cached answer.

Real-time and batch run side by side. The real-time worker maintains the sketch and emits the materialised top-k into Redis. The batch path reads the raw event log from Kafka into ClickHouse, computes exact rollups, and reconciles the real-time numbers within a few minutes.

5 · The hard part — count-min sketch and heavy hitters

Exact counting at this scale is impractical: 100M distinct items per window times a counter cell is ~25 GB of state, replicated, per shard, per window. The count-min sketch trades that for a fixed-size matrix and a known overestimate.

A count-min sketch is a matrix of d rows by w columns of integer counters, plus d independent hash functions. To record an event for item x, increment cell[i][h_i(x) mod w] for every row. To estimate the count of x, take the minimum across the d cells it hashed into. The minimum is the tightest bound because every collision is an overestimate, never an underestimate.

# count-min sketch — increment and query
class CMS:
    def __init__(self, d=5, w=2_000_000):
        self.d, self.w = d, w
        self.cells = [[0] * w for _ in range(d)]
        self.seeds = [random_seed() for _ in range(d)]

    def add(self, x, weight=1):
        for i in range(self.d):
            j = hash(self.seeds[i], x) % self.w
            self.cells[i][j] += weight

    def estimate(self, x):
        return min(self.cells[i][hash(self.seeds[i], x) % self.w]
                   for i in range(self.d))

With w = 2M and d = 5, the error bound is roughly 2N / w with probability 1 - (1/2)^d. For 500M events/sec into a one-hour window, that's an overestimate of a few thousand per item with ~97% confidence — small relative to the millions of counts that the top-100 items actually carry.

The sketch alone doesn't tell you who is in the top-k; it only answers point queries. The heavy-hitters trick is to keep a small min-heap of size k + δ alongside the sketch. On every increment, look up the item's current estimate; if it exceeds the heap's minimum, promote it into the heap and evict the current minimum. The heap converges on the true top-k as long as δ is generous enough to absorb the sketch's overestimate.

Decay and windowing

For tumbling windows, keep a separate sketch per bucket; drop the bucket when it rolls off. For sliding windows, the cleanest pattern is a ring of small sketches (per-minute) that the worker sums when serving a query — at the cost of a small additional error from summing independent over-estimates. Exponential decay (multiply every counter by 0.99 per tick) is tempting but tends to bias toward recent items in a way that's hard to reason about under a sketch's error bound.

6 · Failure modes & runbook

What goes wrong, what oncall sees, what the runbook says. The interview-room version of the operational story.

7 · Cost & operability

The pleasant surprise of the sketch is that its memory is fixed regardless of how many distinct items show up. A few hundred MB per window covers the entire workload. The bill is dominated by the ingest tier and the historical store.

Tuning the sketch dimensions is the main operability lever. Wider sketches (larger w) reduce the error proportionally but cost RAM linearly; more rows (larger d) tighten the confidence bound but cost extra hash work per event. Most production systems land near d = 5 and pick w to deliver the accuracy the product actually asks for.

8 · Trade-offs & what's next

The interesting follow-ups split into architectural choices and product extensions.

Further reading

• Cormode & Muthukrishnan — "An Improved Data Stream Summary: The Count-Min Sketch and its Applications" (2005). The original paper. Short and readable; the bound proofs are worth the hour.
• Manku & Motwani — "Approximate Frequency Counts over Data Streams" (2002). The lossy-counting algorithm; an alternative to CMS + heap with a different error model.
• Metwally, Agrawal, El Abbadi — "Efficient Computation of Frequent and Top-k Elements in Data Streams" (2005). The Space-Saving algorithm, often used in place of the CMS-plus-heap combination.
• Twitter Engineering — "Trending Topics". The closest public writeup of a real top-k system at scale.
• Jay Kreps — "Questioning the Lambda Architecture" (2014). The kappa-vs-lambda essay; required reading before defending either in a design round.
• Adjacent: Streaming aggregation. Windowing, watermarks, and exactly-once semantics.
• Adjacent: Bloom filter simulator. The probabilistic-structure intuition transfers directly.
• Adjacent: Caching strategies. How to think about the materialised top-k cache.