Leaderboard
A leaderboard answers three questions fast: who’s on top, what’s my rank, and who’s around me. A heap gives you the top but not “my rank”. An ordered structure with subtree counts gives you both, and in production that is a Redis sorted set: a skip list plus a hash table, where ZINCRBY and ZREVRANK are O(log N) and the top K is O(log N + K). One sorted set holds about 100M players in ≈10 GB. The hard part starts when one node isn’t enough: shard by player and every rank query scatters to all shards; shard by score range and the top shard runs hot. Past that, you keep the top exact and serve everyone else an approximate rank from score buckets.
The problem
Section titled “The problem”Games, fitness apps, coding contests and sales dashboards all show ranked lists. A mobile game with 100M players wants a global all-time board, a weekly and a daily one, maybe per region and per friend group, all updated live as matches finish.
The goals conflict:
| Goal | What it means | Pulls toward |
|---|---|---|
| Live | A finished match shows in the ranking within a second or two | Update the ranking on every score event |
| Exact at the top | #1, #2, #3 must be right; prizes depend on it | Strict ordering, deterministic ties |
| “My rank” for everyone | Each of 100M players sees their own position | Rank queries in O(log N), not O(N) |
| Cheap at scale | Millions of reads per minute during events | Caching, approximation for the long tail |
| Fair | No self-reported scores, no double counting | Server-authoritative scores, idempotent updates |
Requirements and scope
Section titled “Requirements and scope”| In scope (typical) | Ask about | |
|---|---|---|
| Functional | Submit score; top K; rank of a player; players around a player; daily, weekly and all-time boards. | Is the score cumulative (sum of points) or a best (max single run)? Friends-only boards? |
| Scale | 100M players, 50k score updates/s at peak, 20k reads/s. | Players on each board, or active players? Peak event traffic? |
| Latency | Read under 50 ms p99; an update visible within ~1 s. | Must “my rank” be exact, or is “top 3%” acceptable below the top 10k? |
| Ties | Deterministic: earlier achiever ranks higher, or shared rank (“1, 2, 2, 4”). | Which tie rule? It changes the score encoding. |
| Durability | No score is lost; the ranking can be rebuilt. | Is the ranking the source of truth, or a view? |
| Out of scope | Matchmaking, anti-cheat ML, rewards payout. |
Back of the envelope
Section titled “Back of the envelope”Drag the assumptions. Memory is rarely the problem; throughput per shard is, and the moment you need more than one shard, rank queries change shape.
What to say out loud: “One sorted set fits 100M players in about 10 GB, and every operation is O(log N), about 27 steps. Memory is fine. Writes across three windows are around 150k a second, so I need a few shards, and then I have to decide how a rank query works when no single shard sees everyone.”
API and data model
Section titled “API and data model”POST /scores { match_id, player_id, points } -- from the game server onlyGET /boards/{board}/top?k=10 -> [ { rank, player, score } ]GET /boards/{board}/rank/{player} -> { rank, score, percentile }GET /boards/{board}/around/{player}?n=5 -> [ { rank, player, score } ] -- n above, n below
board key "lb:{game}:{window}:{period}" e.g. lb:g1:weekly:2026-W46sorted set member = player_id, score = encoded score (a double)score events { event_id, player_id, points, at } -- durable log, dedupe on event_idscore DB (board, player_id) -> total, updated_at -- source of truthTwo decisions hide in that sketch:
- The sorted set is a view, not the record. Scores land in a durable log and a database first. The sorted set is rebuilt from them if lost. That keeps Redis free to be fast and lets you replay.
- Ties are encoded into the score. Redis orders equal scores by member name, which is arbitrary. For “earlier achiever wins”, pack time into the score:
encoded = points × 2^32 + (2^32 − 1 − seconds_since_season_start). A double is exact up to 2^53, so that leaves 21 bits (≈2M) for points. For shared ranks (“1, 2, 2, 4”), compute a player’s rank as 1 + the number of players with a strictly higher score:ZCOUNT key (score +inf.
High-level design
Section titled “High-level design”Step through each flow. Writes go through a log, so they can be deduped and replayed; reads are a handful of O(log N) commands.
| Component | Role | Why it’s there |
|---|---|---|
| Game server | Decides match results and emits score events. | Clients can’t be trusted with their own scores. |
| Score events (Kafka) | Durable, partitioned by player. | Ordering per player, replay after failures, decouples bursts. |
| Score updater (×N) | Dedupes by event id, writes the DB, updates each window’s sorted set. | Exactly-once effect from at-least-once delivery (idempotency). |
| Score DB | Totals per (board, player). | Source of truth; rebuild input; history. |
| Redis sorted sets | One key per board and period, sharded if needed. | O(log N) rank and range queries in memory. |
| Leaderboard API (×N) | Stateless reads; caches the top K for a second. | The top list is identical for everyone, so cache it. |
| Window job | Snapshots finished periods, sets expiry on old keys. | Rewards and history without unbounded memory. |
Deep dive: what a sorted set gives you
Section titled “Deep dive: what a sorted set gives you”The sorted containers page covers ordered structures in depth. The short version for this design:
| Structure | Update score | Top K | Rank of a player | Verdict |
|---|---|---|---|---|
| Sort on every read | O(1) | O(N log N) | O(N log N) | Fine for 1,000 players, nothing more |
| Heap of size K | O(log K) | O(K log K) | Not supported | Top-only boards |
| Balanced BST / skip list with counts | O(log N) | O(log N + K) | O(log N) | The answer |
SQL ORDER BY score with an index |
O(log N) | O(log N + K) | O(N): counts rows above | Rank is the problem |
Redis implements a sorted set as a skip list plus a hash table: the hash maps member → score in O(1); the skip list keeps members ordered and stores span counts on its links, so walking down to a member also sums how many members it passed. That sum is the rank. The commands you’ll use:
| Command | Does | Cost |
|---|---|---|
ZINCRBY key delta member |
add to a cumulative score | O(log N) |
ZADD key GT score member |
keep the best score only (Redis 6.2+) | O(log N) |
ZREVRANK key member |
0-based rank, highest first | O(log N) |
ZRANGE key 0 9 REV WITHSCORES |
top 10 | O(log N + 10) |
ZCOUNT key (s +inf |
how many score above s | O(log N) |
ZSCORE key member / ZCARD key |
score / size | O(1) |
A SQL table can do top K with an index but not rank: SELECT COUNT(*) WHERE score > ? scans everything above you, O(N) for a player in the middle. That one gap is why leaderboards live in Redis (or a custom order-statistic tree) even when everything else lives in Postgres.
Deep dive: sharding when one node isn’t enough
Section titled “Deep dive: sharding when one node isn’t enough”Once writes exceed one primary, you have to split players across shards, and you have two choices. Run both:
| Shard by player hash | Shard by score range | |
|---|---|---|
| Write | 1 shard, even load | 1 shard; a move (remove + add) when crossing a band |
| Top K | Scatter: top K from each of S shards, merge S × K | 1 shard (the top band) |
| My rank | Scatter: sum of ZCOUNT (s +inf over S shards |
Local ZREVRANK + cached sizes of the bands above |
| Hot spots | None | The top band: strongest players play most and every top-K read lands there |
| Rebalancing | Consistent hashing, rarely needed | Bands drift as scores grow; boundaries must move |
rank(board, player): s <- ZSCORE on shard_of(player) above <- parallel for each shard i: ZCOUNT board (s +inf -- O(log N_i) each return 1 + sum(above) -- S calls, one round tripThe scatter is one parallel round trip, so with 4-16 shards it’s often fine. For top K, cache the merged result for a second: it’s the same for everyone. Score-range sharding is worth it only when reads dominate and you can afford to split the top band further (e.g., the top 1% on its own, over-provisioned shard).
A common hybrid: a single small “top” sorted set with only players above a threshold (say the top 10k), exact and unsharded, plus hash-sharded sets for everyone, plus a bucket histogram for approximate rank. That’s the next section.
Deep dive: approximate rank, windows and persistence
Section titled “Deep dive: approximate rank, windows and persistence”Approximate rank. Most players don’t need “#48,213”; they need “top 12%”. Keep a count of players per score bucket. Rank ≈ players in higher buckets + an interpolated share of your own bucket. A few hundred counters, updated with one HINCRBY per score change, replace a scatter across every shard:
on score change (old -> new): if bucket(old) != bucket(new): HINCRBY hist bucket(old) -1 ; HINCRBY hist bucket(new) +1
approx_rank(score): b <- bucket(score) above <- sum of hist[j] for j > b -- keep a prefix sum, refreshed every few s frac <- (upper(b) - score) / (upper(b) - lower(b)) return above + ceil(frac * hist[b])Choose buckets where players are: equal-width buckets waste resolution on the empty top end; quantile buckets fix the middle but blur the top. Hence the hybrid: exact for the top N, buckets for the rest.
Time windows. A daily board is just a separate key per period: lb:g1:daily:2026-11-14. Each score event updates every window it counts toward (3 ZINCRBYs for daily, weekly, all-time). At midnight writes move to the new key; nothing is reset. Set an EXPIRE on old keys after snapshotting the final standings. A rolling “last 7 days” board can be computed with ZUNIONSTORE of 7 daily keys (O(N) + O(M log M), so run it every few minutes into a cached key, not per request). Pick one timezone (usually UTC) and say so, or each region needs its own period boundaries; see time handling.
Persistence. Redis with AOF and a replica protects against most failures, but the sorted sets are still a derived view. The durable log plus the score DB are the truth:
- Every score event has an id; the updater records processed ids (or the last offset per partition) so replays don’t double-count.
- A lost replica is resynced from the primary. A lost primary fails over to its replica, losing at most the last few writes of async replication.
- Those writes are repaired by replaying the log from a checkpoint. Idempotent updates make the replay safe.
- If everything is gone, rebuild by scanning the DB and
ZADDing in batches of a few thousand. Meanwhile serve the last cached top list.
Failure modes
Section titled “Failure modes”| What breaks | What you see | Design response |
|---|---|---|
| Duplicate score events | Players gain points twice | Dedupe on event id in the updater; idempotent writes |
| Redis primary fails | Writes error for seconds | Replica promotion; replay the log from the last checkpoint |
| Hot top shard (range sharding) | p99 for top-K reads climbs | Cache top K for ~1 s; split or over-provision the top band |
| Scatter read to a slow shard | Rank latency = slowest shard | Timeouts, hedged requests, fall back to approximate rank |
| Celebrity/event spike | Read QPS 50× | Top K served from cache or CDN; rank via buckets |
| Score overflow in encoded ties | Wrong order at high scores | Check bit budget: points × 2^32 must stay under 2^53 |
| Cheating | Impossible scores at #1 | Server-authoritative scores, plausibility checks, delayed publish of top ranks |
| Midnight rollover | Burst of “new day” writes, empty board | New key per period, pre-create, show yesterday’s final until today has data |
What it costs
Section titled “What it costs”| Operation | Time | Space |
|---|---|---|
Update score (ZINCRBY) |
O(log N): ≈27 levels at 100M | ≈100 B per member (skip list node + hash entry) |
Top K (ZRANGE … REV) |
O(log N + K) | — |
Rank (ZREVRANK) |
O(log N) on one set; S × O(log N/S) hash-sharded | — |
| Around me | O(log N + 2n) | — |
| Approximate rank | O(B) or O(1) with a cached prefix sum | B counters |
| Rolling window union | O(N) + O(M log M) per rebuild | One extra set |
| Throughput | ≈100k O(log N) ops/s per Redis primary (order of magnitude) | 100M players ≈ 10 GB per board |
In the interview
Section titled “In the interview”A good 45-minute arc:
- Clarify (5 min). Cumulative or best score, tie rule, which windows, exact rank for everyone or only the top, scale.
- Data structure (5-10 min). Why a heap fails for rank and SQL fails for rank; ordered structure with counts; Redis sorted set and its costs.
- Write path (10 min). Server-authoritative score events, log, idempotent updater, DB as the source of truth, one
ZINCRBYper window. - Read path (5 min). Top K cached, rank, around-me with a range read, profile lookups.
- Scale (10 min). Estimate per-shard throughput; hash vs range sharding and how rank works in each; hybrid exact top + approximate buckets.
- Stretch (5 min). Windows and rollover, rebuild from DB, friends leaderboards (a small set per player, or fetch friends’ scores and sort, since friend lists are small).
Follow-ups to expect: “Two players tie.” Encode time into the score, or use competition ranking via ZCOUNT. “Show rank for all 500M players.” Exact top 10k, percentile from buckets for everyone else. “Redis is lost.” Replay the log into a rebuilt set; the DB is the truth. “Friends leaderboard.” Friend lists are small (hundreds), so ZMSCORE the friends from the global board and sort them in the API.
Check yourself
Section titled “Check yourself”Go deeper
Section titled “Go deeper”- Redis docs: Sorted sets: the skip list + hash table design, ranges, ties ordered lexicographically.
- Redis docs: ZREVRANK and ZUNIONSTORE: exact complexities for rank and window merges.
- Pugh: Skip lists, a probabilistic alternative to balanced trees (CACM 1990): the structure under every sorted set.
- AWS: Building a real-time gaming leaderboard with Amazon ElastiCache for Redis: a production walkthrough of the sorted-set pattern.
Concept pages to drill: Sorted containers · Heap · Segment tree · Idempotency · Caching · Time handling · Distributed thinking