Game Leaderboard
Real-time ranked scores: a sorted set for O(log n) rank and range queries, tie-breaking and best-score semantics, score-bucketed sharding for cheap global rank, multiple materialized boards, and a cached hot top-N.
~30 min · intermediate
Problem & Requirements
Maintain ranked scores and answer three queries fast: the top N players, a given player's rank, and the window of players just above and below a given player ("you're #4,213, here's who's near you"). Scores update constantly as people play, and everyone wants to see where they stand right now, so both writes and rank reads have to stay cheap as the player count grows into the millions.
The whole prototype hangs on one data structure. Sorting the entire score table on every query is O(n log n) and dies immediately, so the core is a sorted set: a structure that keeps members ordered by score and supports insert, rank-of-a-member, and range-by-rank all in O(log n). Once a single board outgrows one machine, it has to be sharded — and ranking across shards is the hard part, because a global rank needs to know how many players everywhere outscore you. Real products show many boards at once (all-time, daily, regional, friends), each a materialized view updated on every score submit. And because the top page is read far more than it changes, it's cached. Those four principles are the prototype, and the sorted set is the one doing most of the work.
Functional
submit(player, score)records a score;top(n),rank(player), andaround(player, k)are the read queries.- Ties resolve deterministically (earlier achiever ranks higher), and a board keeps each player's best score.
- Support several boards concurrently, including time-windowed ones that expire.
Non-functional (back-of-envelope)
| Quantity | Target | What it forces |
|---|---|---|
| Players per board | up to ~10⁸ | One sorted set may not fit one node → sharding |
| Score submits | ~10⁴–10⁵ /s | O(log n) updates, not full re-sorts |
| Rank/top reads | ~10⁶ /s | Read-heavy → cache the hot top-N and rank lookups |
top(n) cost | O(log n + n), n ~ 100 | Sorted set gives the top slice directly; no scan |
rank(player) cost | O(log n) per shard | Cheap within a shard; the cross-shard sum is the design challenge |
| Boards | global + daily + weekly + region + friends | Each is a materialized view maintained on write |
The rank row is where the difficulty hides. Within one sorted set, a player's rank is an O(log n) index lookup. Split the board across shards and that simple lookup becomes "how many players, across all shards, have a higher score than this one" — which is cheap only if the sharding scheme is chosen specifically to make it cheap. That choice is step four.
Design
Four components, each tied to its principle:
- Sorted set — the per-board core. It keeps
(score, member)ordered and exposes add, rank, top-N, and range-around-member in O(log n). This stands in for a Redis ZSET, which is a skip list plus a hash map; see sorted sets. - Submit path — applies a score to a board with deterministic tie-breaking and best-score semantics, moving the member within the sorted order rather than appending.
- Sharding — for a board too large for one node, partition by score range so each shard holds a contiguous band of scores. Global rank is then "members in higher-scoring shards, plus local rank," which is cheap; the cost is rebalancing shards as the score distribution shifts. See sharding. The alternative — partitioning by player (consistent hashing, as in the distributed-cache prototype) — makes writes trivially balanced but turns global rank into a scatter-gather across every shard, which is why score-bucketing is the usual leaderboard choice.
- Materialized boards — each distinct leaderboard (all-time, daily, weekly, per-region) is its own sorted set, updated on every relevant submit, with time-windowed boards keyed by period and expired when the window closes. See materialized views. A friends board is the exception: it's usually assembled at read time by intersecting a player's friend list with the global scores, since materializing one per player is too many views.
- Cache — the top-N page and per-player rank are read enormously and change slowly relative to that read rate, so they're cached with a short TTL. See caching, and the distributed-cache prototype for the store behind it.
The reference is Redis, where a ZSET is the textbook leaderboard: ZADD to submit, ZREVRANGE for the top, ZREVRANK for a rank, ZRANGEBYSCORE for a window. The instructive limitation is that a ZSET is a single key living on one Redis node, so it can't natively span a cluster — which is exactly why a board past one node's capacity forces the score-bucketing in step four rather than getting sharding for free.
Build it
The obvious version keeps a map of player to score and sorts it whenever someone asks for the top or a rank. Submit is O(1), but every read sorts the whole table — O(n log n) for the top, O(n) to count a rank — and reads outnumber writes by orders of magnitude, so this spends all its effort in the worst place. The fix is to keep the data ordered as it's written, which is the next step.
Keep members ordered by score continuously, so rank is a position lookup and the top is a slice. The structure below pairs a member -> score map with a sorted list of (score, member), giving O(log n) add, rank, and range — the same shape as a Redis ZSET (a skip list with a hash-map side index; the SortedList here is a stand-in for the skip list). around returns the window of players bracketing a member, which is the "players near you" query that a pure top-N can't answer.
Two players with the same score need a stable order, and the rule players expect is that whoever reached the score first ranks higher. Fold that into the sort key by composing the score with the achievement time, inverted so that for equal scores the earlier timestamp sorts ahead. A leaderboard also usually keeps a player's best score rather than their latest, so a submit that doesn't beat the stored score is ignored. These two rules turn the raw sorted set into one that behaves like a game expects.
One sorted set has to fit on one node, and a hundred million members won't. Partition by score band: each shard owns a contiguous range, ordered from highest band to lowest. A player's global rank is then the total membership of all higher-scoring shards plus their local rank inside their own shard, and the top-N reads from the top shard down until it has N. Both stay cheap because the shards are ordered by score. Partitioning by player instead (consistent hashing) would balance writes but force a scatter-gather count across every shard for a single rank, which is why score-bucketed sharding is the leaderboard default.
Players don't see one leaderboard; they see all-time, daily, weekly, and regional ones. Maintain each as its own sorted set updated on every submit — a materialized view per board — with time-windowed boards keyed by their period so a new day starts a fresh set and old ones expire. The cost is paid on write (one submit touches several boards), which is the right place given how read-heavy the system is. A friends board is left out of this fan-out: materializing one per player is too many views, so it's assembled at read time instead.
The top page is requested by nearly everyone and changes far more slowly than it's read, so serving it from the sorted set on every request wastes work. Cache the top-N and per-player rank with a short TTL — a second or two is invisible to players and collapses the read load by orders of magnitude. This is plain caching (the distributed-cache prototype is the store behind it); the short TTL is the whole trick, since it bounds staleness without needing to invalidate the cache on every single score submit.
Tradeoffs
| Decision | What it buys | What it costs |
|---|---|---|
| Sorted set over re-sorting | O(log n) submit/rank/range; the top is a direct slice | More memory than a plain map; a structure to maintain |
| Tie-break + best-score | Deterministic, intuitive ordering | A submit may move a member; composite sort key |
| Score-bucketed sharding | Global rank = higher-shard counts + local rank, cheaply | Rebalancing as the score distribution drifts; boundary moves between shards |
| Player-hash sharding (rejected) | Perfectly balanced writes | Global rank becomes a scatter-gather count across all shards |
| Materialized boards | Each board read-cheap; time windows expire on their own | Every submit fans out to several boards; storage per board |
| Friends board at read | Avoids one view per player | Read-time assembly cost scales with friend-list size |
| Short-TTL cache on top-N | Collapses the dominant read load | Bounded staleness; rank can be slightly behind for a second or two |
Scaling it up
The toy stops short of the parts that matter at real scale. The notable gaps:
Exact rank for everyone is too expensive; approximate it. Keeping every player's exact global rank current under a high submit rate is costly, and players outside the top few thousand don't need an exact number. Production leaderboards keep exact ranks for the top slice and approximate the long tail — a coarse score histogram or percentile buckets gives "top 12%" or "rank ≈ 40,000" cheaply, and the score-band shards from step four are already most of a histogram. The approximation is invisible where it's used and saves the expensive cross-shard counting.
Rebalancing the score bands. Fixed score cutoffs skew as the population shifts (everyone climbs over a season), overloading the top band. Real systems either pick band boundaries from the live score distribution and adjust them, or use a two-level scheme where a coarse global histogram routes to per-band sorted sets. This is the leaderboard version of the rebalancing problem that the distributed-cache prototype solved with virtual nodes.
Time windows and resets. Daily and weekly boards need clean rollover (when exactly does "today" end, in whose timezone) and a cheap way to expire the old window's data without a stop-the-world delete. Redis TTLs on the window-keyed ZSETs handle most of it; seasonal resets that archive the final standings need an explicit snapshot before the wipe.
Anti-cheat and write validation. A leaderboard is an attractive target for forged scores. Submits need server-side validation, rate limiting (the rate-limiter prototype plugs in here), and often anomaly detection on improbable jumps, with a path to retract a score and re-rank. None of that is in the data structure, but all of it sits in front of the submit path.
Persistence and the single-node ZSET limit. A pure in-memory Redis ZSET is fast and volatile; a real deployment needs persistence or rebuild-from-source-of-truth, and because one ZSET is bound to one node, a board past that node's memory is forced into the sharding from step four rather than getting it from Redis Cluster automatically. The score data's authoritative copy usually lives in a durable store, with the sorted sets as a rebuildable materialized layer on top.
This is the second feeds-and-social prototype, alongside the news-feed timeline, and it reuses the materialized-view and caching ideas from there and the distributed cache directly. The natural next steps are a dedicated sorted-set / skip-list prototype that builds the O(log n) structure from scratch rather than borrowing one, an approximate-rank prototype around score histograms and percentile estimation (the long-tail ranking deferred above), and a rate limiter prototype to guard the submit path. Each extends this foundation set without re-covering the ranking core settled here.
References
- Redis sorted sets —
ZADD,ZREVRANGE,ZREVRANK,ZRANGEBYSCORE, and the skip-list + hash-map implementation: https://redis.io/docs/latest/develop/data-types/sorted-sets/ - Redis leaderboard patterns — building real-time leaderboards on ZSETs, including windowed boards: https://redis.io/learn/howtos/solutions/microservices/caching
- Redis Cluster specification — why a single key (a ZSET) lives on one shard, which forces application-level sharding for huge boards: https://redis.io/docs/latest/operate/oss_and_stack/reference/cluster-spec/
- Foundations referenced inline: sorted sets · sharding · materialized views · caching