Design a Top-K Leaderboard

The ask

A top-K leaderboard answers one question again and again. Which items have the highest counts right now?

The worked setting is a game with 100,000,000 players. The board shows the top 10 players by score in the current one-minute window.

The same shape serves many systems. Any ranked short list over a fast event flow is a top-K problem.

The board must refresh every minute. A board that lags by an hour describes a game nobody is playing anymore.

Estimate the scale

Score events arrive at 1,000,000,000 a day. Every event adds points to one player's window score.

1,000,000,000 score events / 86,400 seconds = 11,574 events per second.

Windows are one minute long. A day holds 1,440 windows, from 24 hours x 60 minutes.

Each window starts empty. Scores from the last window never leak into the next one.

Exact counting tracks every player's count in the window. Most players score a little, and a few score enormously.

API and data

Record score takes a player ID, a points value, and a timestamp. The event joins the current window at once.

Get top players takes a window and returns the ranked top 10. It reads a prepared board, never the raw events.

A score event holds the player, the points, and the time. Events are small and are dropped after the window closes.

A board record holds one finished window and its top 10 players with their counts. Finished boards are kept so readers can compare windows.

High-level design

Score events enter an append-only event log first. Workers read the log as a stream and update the current window's counts.

Counting is sharded by player ID. One player's events always reach the same shard, so each count has one home.

At the end of a minute, each shard reports its own top players. A merger combines the shard lists into the window's board.

With 100 shards as the design figure, the merger handles a short list from each shard. The merge stays cheap even at full event speed.

100 shards x 10 players = 1,000 candidates reach the merger for each board.

Readers hit a cache that holds the current board. One prepared answer serves every reader in that minute.

Deep dive: approximate counting

Approximate counting means keeping a small summary that estimates counts instead of storing every item's exact count. The summary trades a little accuracy for a great deal of memory.

Exact counting in one window is heavy. Holding one 16-byte entry for each of 100,000,000 players takes far more room than the summary.

100,000,000 players x 16 bytes = 1.6 GB of exact counts per window.

A sketch is the small summary that approximate counting keeps. One common sketch is the count-min sketch, a grid of counters shared by all items.

Each item is hashed to one counter in each row of the grid. Its estimated count is the smallest of its counters, since collisions only ever add counts.

The worked sketch holds 1,000,000 counters of 4 bytes each. Its whole memory is a rounding error next to the exact counts.

1,000,000 counters x 4 bytes = 4 MB for the sketch.

Heavy hitters are the items with counts far above the rest. Their counts tower over the collision error, so the sketch finds them reliably.

The board cares only about heavy hitters. An error that swaps two tiny counts never touches the top 10.

From sketch to board

The sketch alone cannot name its leaders. It estimates counts for items it is asked about, but it stores no item names.

Each shard therefore keeps a small candidate list beside its sketch. Items whose estimates pass a threshold join the candidate list.

Candidates get an exact count in a second pass over the window's events. The final order comes from exact counts of the candidates, not from estimates.

The two stages divide the work. The sketch finds who might lead, and the exact pass settles who does.

Ties are broken by the time the score was reached. The earlier reach ranks higher, and the rule is stated wherever the board is shown.

Freshness and windows

A fixed window resets every minute. A player strong early and idle late still leads until the window turns.

The board labels its window plainly. Readers see the minute the board describes, so a just-closed board is never mistaken for a live one.

Late events land in the window they belong to. A board already published gains a corrected version rather than a silent edit.

Old boards expire from the cache quickly. Only the current board and the last few finished boards stay hot.

When parts fail

A dead shard loses its slice of the current window. The board for that minute carries a gap, and the next window starts clean.

A merger failure delays the board, never the counting. Events keep landing in the log, and the board is rebuilt when the merger returns.

Readers see the previous board during a delay. A labelled old board beats an error page for a fast-moving game.

Evaluation and trade-offs

Approximate counting trades a small, bounded error for a summary 400 times smaller in the worked figures. The board spends that saving on speed.

1.6 GB exact counts / 4 MB sketch = about 400 times less memory for the sketch.

The exact second pass trades a little delay for a trustworthy order. Estimates nominate, and exact counts decide.

Fixed windows trade smoothness for simplicity. The board is easy to explain, rebuild, and cache, one minute at a time.

Exact counting against approximate counting