Design a realtime gaming leaderboard
"Sort 100M players by score" sounds like one line of SQL. The whole problem is that the sort changes 50,000 times a second and everyone wants their rank back in a few milliseconds — so the real question is which rank you actually owe exactly, and which you can fake.
0. The hinge
The hinge is the moment the prompt stops being generic and the architecture becomes forced. Here it arrives the instant you write the numbers down: 50k writes/s each re-orders a shared index, and rank queries must be O(log N), not O(N). Every interesting decision — sorted sets over SQL, a top-k cache, range partitioning, exact-vs-approximate rank, season namespacing — falls out of defending that one constraint. Lead with it.
SELECT COUNT(*) WHERE score > mine with an index on score." A B-tree index on score gives you ordered traversal, but a rank still means counting the rows above you — O(N) per query unless the index carries subtree cardinalities. At 100M rows and tens of thousands of rank reads per second that is a non-starter. The job is to pick a structure where rank itself is cheap, and a Redis sorted set (a skip list) is the canonical one.
1. Clarify the contract
Treat the prompt as a product contract before a box diagram. What it must do:
- Submit a score for a player, keeping their best (or latest) score per board.
- Return the top-k of a board (the page everyone stares at).
- Return a single player's rank and the slice of players around them ("you are #4,021 of 100M").
- Scope boards by season / time window, by region, and by friend set.
What it explicitly need not do, and saying so out loud earns signal: it is not a system of record — the authoritative score lives in the game's match-result store; the leaderboard is a derived, rebuildable view (DDIA Ch. 11's materialized view: a read-optimised projection you can always recompute from the source events). It does not need transactional consistency with the wallet or the match log. And tail ranks do not need to be exact — nobody renders "you are #8,403,118" and checks the last three digits.
2. Put numbers on the shape
The numbers are what make the structure choice forced. Take 100M players on a board and 50k score updates/s at peak.
Memory per board. A Redis sorted-set entry is roughly a 64-bit double score plus the member string plus skip-list pointers — call it ~64 B amortised per member. So one board is
100\,000\,000 \times 64\,\text{B} \approx 6.4\,\text{GB}
That fits in RAM on a single large node, which is exactly why an in-memory sorted set is viable at all — but it is big enough that you will not casually hold dozens of boards on one machine, and it is the number that motivates partitioning later.
Cost of a write / rank read. A sorted set is a skip list: ZADD (insert/update) and ZREVRANK (rank query) are both O(\log N). At 100M members,
\log_2(10^8) \approx 27 \text{ comparisons}
So every write and every rank read is ~27 pointer hops, not 100M. That single fact — 27 \ll 10^8 — is the whole reason this design works. At 50k writes/s that is ~1.35M comparisons/s of ordering work, trivial for one core.
Read amplification, and the cache that kills it. Reads dwarf writes — most traffic is "show me the top 100." If the hot top-k page is cached and 99% of reads hit it, then only 1% reach the sorted set, and the expensive rank-recompute work effectively disappears for the common case. The cache converts a re-sorting-index problem into a near-static-page problem for the 99% path.
3. Define the surface area
Keep the API small and expressed in product terms; the season, shard, and cache layout must not leak into it.
| API / operation | Why it exists |
|---|---|
submit_score(player, board, score, session_id) | Idempotent write keyed by session_id (a match can be reported twice); keeps the best score for the active season. |
get_top(board, k) | The hot read. Served from the top-k cache almost always. |
get_rank(player, board) | Single-player rank. O(\log N) at the top; approximate below the cutoff (deep dive 1). |
get_around(player, board, w) | The w players just above/below you — one ZREVRANGE slice once you know the rank. |
get_friends_rank(player, board) | Fetch the friend set's scores (small N), sort locally — a different problem from global rank. |
4. Model the data
The data model is the first architecture. The leaderboard is two layers over a source of truth it does not own.
The key naming carries the whole season story: the sorted set is keyed lb:{game}:{board}:{season}. A new season is a new key — see deep dive 2. The member is the player ID; the score is the game score, with a tie-break encoded into the score's low bits (deep dive on ties below). The authoritative best-score-per-player lives in a durable store so the sorted set can be rebuilt from scratch (DDIA Ch. 11: the materialized view is derived state, never the system of record).
5. Linearized design
Walk a score update and a rank read through the system in the order they actually move; the first bottleneck exposes itself.
- Validate & deduplicate. A match-end event arrives with
session_id. Reject duplicates idempotently (see lesson 12) so a retried report can't double-count. - Decide if it's the player's best. Read the current best from the player→score map; if the new score isn't higher, stop — most updates don't change the ordering at all.
- Update the sorted set. One
ZADD lb:{board}:{season} score player— O(\log N) \approx 27 hops. This is the only write that touches the ordered index. - Invalidate / refresh top-k. If the new score breaks into the cached top-k, refresh that page; otherwise the cache is untouched (the common case for the 99% of updates that don't crack the top).
- Read path: top-k.
get_tophits the cache (~99%) and returns a near-static page. On miss, oneZREVRANGE 0 k-1. - Read path: my rank.
ZREVRANK playerfor an exact top rank, or an approximate bucket lookup below the cutoff (deep dive 1), thenZREVRANGEfor the neighbours.
The bottleneck the walk exposes: it is not the writes (27 hops × 50k/s is nothing) and not the cached reads (99% are a page lookup). It is the 1% of reads that ask for an exact deep rank plus the memory ceiling of a single board. Both are addressed in the deep dives.
6. Deep dives
Deep dive 1 — Exact rank vs approximate: exactness only matters at the top
This is the decision worth your strongest minutes. A ZREVRANK is O(\log N) and exact — cheap enough. So why approximate at all? Because the moment you partition the board (deep dive 3), a global rank stops being one skip-list lookup: you must ask every shard "how many players do you have above score S?" and sum. That cross-shard fan-out is what gets expensive at the tail.
The insight that rescues you: rank precision is only valuable near the top. The player ranked #3 vs #4 cares about the exact integer — there's a prize, a name on a wall, bragging rights. The player ranked ~#8.4M does not; "top 9%" or "top 8.4M" is indistinguishable to them from the true 8,403,118. So split the board at a cutoff (say the top 10k):
- Above the cutoff: keep an exact sorted set. Ranks are
ZREVRANK, exact, fast — this set is tiny (10k members, sub-MB). - Below the cutoff: serve an approximate rank from a histogram of score buckets (a count-min / percentile sketch). To answer "rank of score S," sum the counts of all buckets above S's bucket — O(\text{buckets}), independent of N, and cheap to keep incrementally as scores move. The error is bounded by bucket width, which is invisible at the tail.
This is DDIA Ch. 3's lesson restated: a sorted structure (SSTable / skip list) makes ordered reads and exact rank cheap where you need them; a coarse summary structure makes approximate aggregate counts cheap where exactness is wasted. You pay for precision only on the 10k entries that justify it.
Deep dive 2 — Season resets via namespacing (an O(1) metadata operation)
A season reset sounds destructive — "wipe 100M scores and start over" — and if you model it as deletes it is a 6.4 GB churn that hammers the node mid-event. Instead, namespace the board by season in the key: lb:arena:s14 vs lb:arena:s15. "Reset" becomes flipping the active-season pointer to s15; new scores land in a fresh, empty sorted set, and the old season's key is read-only history you can archive or expire with a TTL on your own schedule.
This is why namespacing is the right move and a season column in a shared table is wrong: with a column, a reset means rewriting or filtering 100M rows on every query forever; with a key prefix it's an O(1) pointer flip and the old data is physically separate. It also fixes the season-reset race for free — a late-arriving score for the previous season is written to s14, never accidentally counted in s15, because they are different keys.
Deep dive 3 — Partition the sorted set by score range for scale
One board is 6.4 GB and a write hotspot if a single game blows up. To scale past one node, partition. The naive choice — partition by player ID hash — is wrong here: it scatters every rank query across all shards because rank is about order, and player ID has nothing to do with score order. Instead partition by score range: shard 0 holds scores ≥9000, shard 1 holds 8000–8999, and so on.
Range partitioning is DDIA Ch. 6's key-range strategy, and it brings Ch. 6's named hazard with it: hot-spotting. A range partition keeps related keys together so range scans (top-k, rank-counting) stay local — but it concentrates load on whichever range is hot. For leaderboards the hot range is structurally predictable: the top shard is read constantly (everyone watches the leaders) and the bottom shard absorbs the season-start pile-up. Mitigate by giving the top range its own replicas and its own cache (this is exactly the top-k cache earning its place again — lesson 06), and by splitting hot ranges finer than cold ones. A rank query now becomes "find my shard by score, get my offset within it, add the populations of all higher shards" — the higher-shard populations are the bucket counts from deep dive 1, so the two ideas compose.
The sharpest senior question — the score=0 pile-up
ZREVRANK returns a rank, but every tied player gets a different integer determined by member sort order, and asking "which of the million am I?" naively means scanning the tie group — O(N), the exact thing we forbade. Three composed fixes: (1) namespace by season so the pile-up is isolated to the new season's key and never mixed with last season's spread (deep dive 2). (2) Tie-break inside the score: store composite = score · 2^k − timestamp so earlier achievers rank above later ones — now no two players are truly tied, the ordering is total, and the structure stays O(\log N) with no scan. (3) Below the cutoff, don't compute an integer at all: everyone in the 0-bucket is honestly "unranked / top 100%" via the approximate buckets of deep dive 1. The senior move is recognising that an exact integer rank for a million tied players is a meaningless number you should refuse to compute, not an expensive one you should optimise.
7. Trade-offs
| Choice | Buys | Costs | Choose when |
|---|---|---|---|
| Exact rank vs approximate (bucketed) | Exact integer rank; cross-shard fan-out avoided. | Exactness costs O(log N) per shard summed; only worth it for a few entries. | Above the cutoff (top-k competitive); approximate everywhere below. |
| Sorted set (skip list) vs SQL index | Rank as an O(log N) structural property, in-RAM. | Volatile, derived state you must be able to rebuild; ~6.4 GB/board. | Always for the index; SQL/store keeps the source of truth. |
| Range-partition vs single node | Scale past one node's RAM; local range scans. | Hot-spotting on top/bottom ranges; rank needs shard population sums. | Board > one node, or a hot range needs isolated capacity. |
| Cache top-k vs live query | ~99% of reads become a static page; rank-recompute disappears. | Brief staleness on the top page after a lead change. | Always — reads dwarf writes and the top page is the hot read. |
| Realtime publish vs delayed (anti-cheat) | Engagement; instant gratification. | Fraud exposure — a cheated score is visibly #1 before review. | Casual boards realtime; competitive boards quarantine until verified. |
The sharpest trade-off is exact vs approximate rank, because it is the one that scales the whole design. If you insist on exact global rank everywhere, range partitioning forces a fan-out-and-sum on every single rank read and the top shard's cache stops helping the tail. Conceding that the tail tolerates approximation is what lets the top stay exact and cheap — you spend your precision budget only where a human can perceive the difference.
8. Failure modes
| Failure | Mitigation |
|---|---|
| Cheater takes top rank | Quarantine suspicious scores in a side state; rank publicly only after anti-cheat verification. The top is exactly where you can afford the review latency. |
| Hot top shard / hot global board | Top-k cache (lesson 06) absorbs the read flood; extra replicas on the top range; split the hot range finer (lesson 07). |
| Season reset race / late score | Namespace by season key; a stray score writes to the old season's set, never the new one. O(1) pointer flip, no 100M-row churn. |
| Duplicate score submit | Idempotency keyed by session_id + player (lesson 12) so a retried match report can't double-count. |
| Sorted-set node loss | It's a derived materialized view — rebuild from the durable best-score store. Replicate the hot top range so reads survive a node loss without a full rebuild wait. |
9. Interview prompts you should be ready for
- Why a Redis sorted set instead of an indexed SQL column? (senior answer) A B-tree index gives ordered traversal but a rank still means counting rows above you — O(N) per query unless the index stores subtree cardinalities. A sorted set is a skip list where ZADD and ZREVRANK are both O(log N) ≈ 27 hops at 100M members; rank is a structural property of the index, not a scan. The score store stays the source of truth; the sorted set is a rebuildable view.
- How big is one board and why does it matter? (senior answer) ~100M × ~64 B ≈ 6.4 GB — fits in RAM on a big node, which is why in-memory sorted sets are viable, but big enough that you won't pack many boards per node, which is what motivates range partitioning.
- When do you serve approximate rank, and how? (senior answer) Everywhere below a top-k cutoff. Keep an exact sorted set for the top (say 10k members) and answer tail ranks from a histogram of score buckets — sum the counts above your bucket, O(buckets) and independent of N. Precision is only perceptible near the top, so spend it only there.
- How do you handle a season reset on a live 100M-player board? (senior answer) Namespace the board by season in the key and flip an active-season pointer — O(1). New scores land in a fresh empty set; the old season becomes read-only history with a TTL. Never model it as 100M deletes, and never as a season column that you filter on every query forever.
- A million players are tied at score=0 at season start — serve get_rank without an O(N) tie scan. (senior answer) Encode a tie-break into the score (e.g. score·2^k − timestamp) so the ordering is total and stays O(log N) with no scan; isolate the pile-up by season namespace; and below the cutoff refuse to compute an exact integer — everyone in the 0-bucket is honestly "top 100%." An exact rank among a million ties is a meaningless number, not an expensive one.
- Why partition by score range and not by player ID hash? (senior answer) Rank is about order, and player ID has no relation to score order — hashing scatters every rank query across all shards. Range partitioning (DDIA Ch. 6) keeps order local so rank = offset-in-shard + populations of higher shards, at the cost of hot-spotting on the top and bottom ranges, which you isolate with replicas and the top-k cache.
- How does the top-k cache change the math? (senior answer) Reads dwarf writes and they nearly all want the same top page. A ~99% hit-rate means only 1% of reads touch the sorted set, so the rank-recompute and cross-shard work disappears for the common case — the cache turns a continuously re-sorted index into a near-static page for almost all traffic.
- How do you stop a cheater from sitting at #1? (senior answer) Quarantine suspicious scores in a side state and publish a top rank only after anti-cheat verification. The top is precisely where you can afford a little review latency, because it's a tiny set and it's the only place exactness (and integrity) is perceived.
Related foundation lessons
The design leans on three foundation lessons, each for a specific reason. Range partitioning and the hot-shard hazard (lesson 07) is the backbone of deep dive 3 — partitioning by score range is what scales the board past one node, and its hot top/bottom ranges are exactly Ch. 6's hot-spotting. The top-k cache (lesson 06) is what makes the read-heavy workload tractable: a ~99% hit-rate on the hot page removes the rank-recompute cost from the common path and protects the hot top shard. And the score-update flow is best modeled as a stream of match-end events feeding a materialized view, so async messaging (lesson 11) is how submissions arrive durably and idempotently; idempotent dedup of those events draws on lesson 12.