What is the difference between a top-K leaderboard and streaming heavy hitters?

They ask the same question — "who are the top ten?" — under two completely different constraints. A leaderboard keeps an exact score for every player and must answer "what rank am I?" for anyone, at any time, updated live; the whole point is that every one of 25 million scores is stored and kept in order. Streaming heavy hitters gives that up: the stream is a firehose of billions of events across so many distinct keys that you cannot afford one counter per key, so you keep an approximate summary in fixed memory and accept that the answer is "probably these, roughly these counts." The leaderboard is an exact ordered index (Redis sorted sets); heavy hitters is a probabilistic sketch (count-min) plus a small heap of the current top-K. Most real systems need both — the exact board for the product, the sketch for the firehose.

How does a Redis sorted set answer leaderboard rank in O(log n)?

A sorted set is not a sorted array you re-sort on every write. In the Redis docs’ own words, "Sorted sets are implemented via a dual-ported data structure containing both a skip list and a hash table, so every time we add an element Redis performs an O(log(N)) operation." The hash table maps a member to its score in O(1); the skip list keeps every member ordered by score with O(log n) insert and, crucially, O(log n) rank — because each skip-list node stores a span (how many nodes it jumps), Redis sums spans while it searches and reads out a member’s position without walking the whole list. So ZINCRBY (bump a score), ZREVRANK (what rank am I?), and ZREVRANGE (the top ten) are all O(log n). That is why a 25-million-player board updates and renders live instead of re-sorting a table.

What is a count-min sketch and when do you use it for top-K?

A count-min sketch is a fixed-size table of counters — a two-dimensional array of width w and depth d — that estimates how many times each key has been seen without ever storing the keys. Each key is hashed by d independent functions to one cell per row; an update adds to all d cells; the estimate for a key is the minimum of its d cells, because collisions only ever add, so the smallest cell is the least-inflated. The Cormode–Muthukrishnan guarantee is one-sided: the true count aᵢ ≤ estimate âᵢ, and with probability at least 1−δ, âᵢ ≤ aᵢ + ε‖a‖₁. You reach for it when the number of distinct keys is too large to hold one exact counter each — a billion keys fit in a kilobyte of counters — and you pair it with a min-heap of size K to track the current heaviest keys. The price is that it never undercounts but can overcount, so a rare key riding on a crowded cell can be reported too high.

Why does hash-partitioning a leaderboard break the rank query?

To scale past one machine you split the board across shards. If you range-partition (shard by score band), a global rank query is a running total across ordered shards, and "top ten overall" is a bounded scatter-gather of each shard’s local top ten. But if you hash-partition (shard by player ID for even write load), the scores are scrambled across shards with no order between them, so there is no way to compute a global rank without pulling every shard’s entire contents and merging — an O(n) query that defeats the point. "Top-K overall" still works as a scatter-gather (each shard returns its local top-K, the coordinator merges the K×shards candidates), because a global top-K member must be a local top-K member on its own shard. Arbitrary "what rank is player X?" does not. That trade — even writes vs cheap rank — is the honest deliberation of a sharded board.

How do you make a streaming top-K accurate enough to bill against?

You do not trust the sketch for money. The sketch and heap give you a seconds-fresh, approximate top-K for a dashboard; when the number must be exact — billing an advertiser, paying a creator — you run a lambda-style reconciliation: the same events are also written to a durable log, and a batch job periodically recomputes exact counts by grouping the raw events, overriding the approximate numbers. The stream layer answers "right now, roughly"; the batch layer answers "eventually, exactly," and the exact number wins where it matters. This is the same lambda-vs-kappa split that ad-click aggregation lives in, applied to counting instead of summing.

Top-K & Heavy Hitters

Who are the top ten right now? Easy at a thousand rows, brutal at a billion. Two questions wear one name: a live leaderboard of 25M players, and the heavy hitters of a firehose you can never store. Built from zero — why SQL ORDER BY dies, how a Redis sorted set answers rank in O(log n) with a skip list, how the board shards and why hashing breaks the rank query, then the streaming half: a count-min sketch that counts a billion keys in a kilobyte (and sometimes lies), a min-heap of the top ten, and lambda reconciliation when the number has to be billing-exact.

System design · Systems. The source ↗

A free, interactive, animated visual explainer of Top-K & Heavy Hitters — built to be understood, not skimmed.

Questions

What is the difference between a top-K leaderboard and streaming heavy hitters?: They ask the same question — "who are the top ten?" — under two completely different constraints. A leaderboard keeps an exact score for every player and must answer "what rank am I?" for anyone, at any time, updated live; the whole point is that every one of 25 million scores is stored and kept in order. Streaming heavy hitters gives that up: the stream is a firehose of billions of events across so many distinct keys that you cannot afford one counter per key, so you keep an approximate summary in fixed memory and accept that the answer is "probably these, roughly these counts." The leaderboard is an exact ordered index (Redis sorted sets); heavy hitters is a probabilistic sketch (count-min) plus a small heap of the current top-K. Most real systems need both — the exact board for the product, the sketch for the firehose.
How does a Redis sorted set answer leaderboard rank in O(log n)?: A sorted set is not a sorted array you re-sort on every write. In the Redis docs’ own words, "Sorted sets are implemented via a dual-ported data structure containing both a skip list and a hash table, so every time we add an element Redis performs an O(log(N)) operation." The hash table maps a member to its score in O(1); the skip list keeps every member ordered by score with O(log n) insert and, crucially, O(log n) rank — because each skip-list node stores a span (how many nodes it jumps), Redis sums spans while it searches and reads out a member’s position without walking the whole list. So ZINCRBY (bump a score), ZREVRANK (what rank am I?), and ZREVRANGE (the top ten) are all O(log n). That is why a 25-million-player board updates and renders live instead of re-sorting a table.
What is a count-min sketch and when do you use it for top-K?: A count-min sketch is a fixed-size table of counters — a two-dimensional array of width w and depth d — that estimates how many times each key has been seen without ever storing the keys. Each key is hashed by d independent functions to one cell per row; an update adds to all d cells; the estimate for a key is the minimum of its d cells, because collisions only ever add, so the smallest cell is the least-inflated. The Cormode–Muthukrishnan guarantee is one-sided: the true count aᵢ ≤ estimate âᵢ, and with probability at least 1−δ, âᵢ ≤ aᵢ + ε‖a‖₁. You reach for it when the number of distinct keys is too large to hold one exact counter each — a billion keys fit in a kilobyte of counters — and you pair it with a min-heap of size K to track the current heaviest keys. The price is that it never undercounts but can overcount, so a rare key riding on a crowded cell can be reported too high.
Why does hash-partitioning a leaderboard break the rank query?: To scale past one machine you split the board across shards. If you range-partition (shard by score band), a global rank query is a running total across ordered shards, and "top ten overall" is a bounded scatter-gather of each shard’s local top ten. But if you hash-partition (shard by player ID for even write load), the scores are scrambled across shards with no order between them, so there is no way to compute a global rank without pulling every shard’s entire contents and merging — an O(n) query that defeats the point. "Top-K overall" still works as a scatter-gather (each shard returns its local top-K, the coordinator merges the K×shards candidates), because a global top-K member must be a local top-K member on its own shard. Arbitrary "what rank is player X?" does not. That trade — even writes vs cheap rank — is the honest deliberation of a sharded board.
How do you make a streaming top-K accurate enough to bill against?: You do not trust the sketch for money. The sketch and heap give you a seconds-fresh, approximate top-K for a dashboard; when the number must be exact — billing an advertiser, paying a creator — you run a lambda-style reconciliation: the same events are also written to a durable log, and a batch job periodically recomputes exact counts by grouping the raw events, overriding the approximate numbers. The stream layer answers "right now, roughly"; the batch layer answers "eventually, exactly," and the exact number wins where it matters. This is the same lambda-vs-kappa split that ad-click aggregation lives in, applied to counting instead of summing.

Top-K & Heavy Hitters

Questions

Related explainers