Design a Leaderboard (Gaming / Rankings)
Difficulty: Tier 2 Asked at: gaming companies, Amazon, Careem (loyalty), Meta Time budget: 45 min
A leaderboard answers “who’s in the top 100?” and “what’s my rank?” over millions of players whose scores
change constantly. The naive answer — sort everyone on every query — is hopeless at scale. The signature
tool is the sorted set (Redis ZSET / skip list), and the signature challenge is rank queries at
scale plus the “rank among 100 million” problem. Small design, sharp data-structure insight.
Prerequisites: Caching / Redis, Sharding, Indexing
1. Requirements
Functional:
- Update a player’s score.
- Get the top K players.
- Get a player’s rank and their neighbors (scores just above/below).
- Support leaderboards scoped by time (daily/weekly/all-time) and by segment (region, friends).
Non-functional:
- Real-time-ish — scores update and ranks reflect quickly.
- Low-latency top-K and rank queries.
- Scale — millions to hundreds of millions of players; high update rate.
- Accuracy (exact ranks) — though approximate rank is acceptable at extreme scale.
Out of scope: the game itself, anti-cheat (mention score validation matters).
2. Estimation
- 100M players, many active, scores updating frequently → 100K+ updates/sec during peak.
- Top-K queries: constant (every player sees the leaderboard). Rank-of-me queries: also constant.
- 🚨 The hard operation is “rank of player X” — naively it’s “count how many have a higher score,”
which is O(N) if you scan. Needs a structure that maintains order.
3. The core: a sorted set
🚨 Use a sorted set (Redis ZSET, backed by a skip list + hash). It maintains players ordered by score
and supports exactly the operations you need in logarithmic time:
| Operation |
ZSET command |
Cost |
| Update score |
ZADD key score member |
O(log N) |
| Top K |
ZREVRANGE key 0 K-1 |
O(log N + K) |
| Player’s rank |
ZREVRANK key member |
O(log N) |
| Neighbors |
ZREVRANGE around rank |
O(log N + range) |
The skip list keeps elements sorted (fast range + rank); the hash maps member → score (fast update). 🚨
This one data structure solves the whole problem — recognizing that a sorted set gives O(log N) rank is
the key insight. (Caching / Redis)
4. High-level design
flowchart LR
Game[Game servers] -->|score update| API[Leaderboard Service]
API -->|ZADD| Redis[(Redis Sorted Set<br/>per leaderboard)]
Client -->|top K / my rank| API
API -->|ZREVRANGE / ZREVRANK| Redis
Redis -.snapshot/persist.-> DB[(Durable store<br/>backup + history)]
Score updates and queries hit the in-memory sorted set. A durable store backs it up (Redis persistence /
periodic snapshots) and holds history for time-scoped boards.
5. Deep dives
5a. Rank queries at scale — why not SQL?
SELECT COUNT(*) WHERE score > my_score gives a rank but is O(N) per query and hammers the DB at scale.
Even an index helps only so much under constant updates. The sorted set maintains order incrementally on
each update, so rank is O(log N) — 🚨 the reason to reach for a specialized structure instead of a
relational query.
5b. Scaling beyond one node — sharding
100M players may exceed one Redis node’s memory/throughput. Options:
- Shard by score range — each shard owns a score band; global top-K comes from the top shard, rank
requires summing counts across shards below you. Enables exact global rank.
- Shard by segment — separate leaderboards per region/game mode (often what you actually want), each
fitting a node. Global board aggregates.
- 🚨 Global exact rank across shards is the hard part — you must combine per-shard ranks. For the top-K
it’s easy (merge tops); for arbitrary “rank of me” among 100M, you sum “how many above me” across shards.
5c. Approximate rank at extreme scale
Do you really need “you are #4,271,908”? Usually not — “top 5%” or “rank ~4.2M” is fine below the top.
🚨 Serve exact ranks for the top N (which everyone cares about) and approximate ranks (percentile/bucketed)
for the long tail — using histograms of score distribution to estimate rank cheaply. This sidesteps the
expensive cross-shard exact-rank computation for the 99% who are mid-pack.
5d. Time-scoped and segmented boards
Daily/weekly boards = separate sorted sets keyed by period (leaderboard:2026-07-24), expiring old ones.
All-time is a persistent set. Friend leaderboards = a small sorted set per social graph, or filter the
global set by the friend list at query time (small K).
5e. Durability & consistency
Redis is the fast serving layer; persist to a durable store (AOF/snapshots or a backing DB) so a crash
doesn’t lose scores. Score updates should be idempotent/validated (anti-cheat: reject impossible jumps).
Slight staleness in ranks is acceptable; exactness of the stored score is not.
6. Bottlenecks & scaling further
- Rank/top-K speed → sorted set (O(log N)), in memory.
- Scale beyond one node → shard by score range or segment; merge for global.
- Cross-shard exact rank → exact for top N, approximate (percentile) for the tail.
- Update volume → sorted set updates are O(log N); batch/coalesce very hot updates.
- Durability → persist Redis + backing store; validate scores.
7. Trade-off summary
| Decision |
Chosen |
Alternative |
Why |
| Data structure |
Sorted set (skip list) |
SQL COUNT/ORDER BY |
O(log N) rank vs O(N) scan |
| Scale |
Shard by score range / segment |
Single node |
100M players exceed one node |
| Global rank |
Exact top-N, approximate tail |
Exact everywhere |
Cross-shard exact rank is costly; tail doesn’t need it |
| Time scopes |
Separate sets per period |
One set with filtering |
Clean expiry, isolation |
| Durability |
Redis + backing store |
Redis only |
Don’t lose scores on crash |
8. Follow-up questions
Why not just use a database with ORDER BY score and COUNT for rank?
Because those operations don't scale to millions of constantly-updating players at low latency. Getting a
player's rank via `SELECT COUNT(*) WHERE score > my_score` is O(N) — it effectively counts a large portion of
the table per query — and at 100 million players with constant queries that's crushing, even with an index,
especially since the index must be maintained against a high update rate. `ORDER BY score LIMIT K` for the
top-K is cheaper with an index but rank-of-arbitrary-player remains the problem. A sorted set (skip list plus
hash, as in Redis) instead maintains the ordering incrementally: each score update is O(log N), and it can
return a player's rank in O(log N) and the top-K in O(log N + K) directly, because order is kept continuously
rather than computed per query. Recognizing that rank queries want a structure that maintains sorted order —
not a relational aggregate — is the core insight, and it's why leaderboards are the poster child for sorted
sets.
How does a sorted set give you O(log N) rank and top-K at once?
It combines two structures. A skip list keeps all members ordered by score and, augmented with span/width
counts at each level, supports finding the top-K by walking from the head (O(log N + K)) and computing a
member's rank by summing the spans skipped while locating it (O(log N)). A companion hash map from member to
score gives O(1) lookup of a player's current score, which makes updating (remove-and-reinsert at the new
score position) O(log N). So updates, top-K, rank-of-member, and neighbor queries are all logarithmic because
the ordering is maintained structurally as scores change, rather than recomputed. That's exactly the set of
operations a leaderboard needs, which is why a single sorted set solves essentially the whole problem on one
node — the design difficulty only appears when the data outgrows a single node and you must shard.
You have 100M players across multiple shards. How do you compute a global rank?
Global rank is the hard part of sharding because a player's rank depends on everyone, not just their shard.
If you shard by score range, each shard owns a contiguous score band, so a player's global rank is their rank
within their own shard plus the total number of players in all higher-band shards — you keep a maintained
count per shard and sum the counts of shards above, which is cheap, making exact global rank feasible. If you
shard by segment (region/mode) instead, there isn't one global order unless you aggregate, so a true global
board requires merging. For the top-K globally it's always easy: take each shard's top-K and merge them. The
expensive case is exact "rank of an arbitrary mid-pack player among 100M" across arbitrary sharding — which
is why the common answer is to compute exact ranks only for the top N (what everyone actually cares about)
and use approximate, percentile-based ranks for the long tail, avoiding costly cross-shard exact computation
for players who don't need a precise number.
Is exact rank really necessary for every player?
Almost never below the top. Players intensely care about the exact top of the board — who's #1, the top 100,
and their own precise position if they're near the top — but for the vast mid-pack, "you're rank ~4.2 million"
or "top 5%" is entirely sufficient and arguably more meaningful than a precise but volatile integer that
changes every second. Exploiting this lets you serve exact ranks for the top N from the sorted set directly
and approximate ranks for everyone else using a histogram of the score distribution: to estimate a score's
rank, sum the counts of buckets above it, which is cheap and avoids the expensive exact cross-shard
computation for the 99% who are mid-pack. This is a classic case of matching precision to what the user
actually needs — spending exactness where it's noticed (the top) and using cheap approximations where it
isn't (the tail) — which dramatically reduces the cost of the hardest operation at extreme scale.
9. What junior / mid / senior answers look like
- Junior: stores scores in a table and sorts/counts per query. Works small; O(N) rank queries collapse
at scale.
- Mid: uses a sorted set (Redis ZSET) for O(log N) updates, top-K, and rank; time-scoped keys; durable
backup.
- Senior: all that plus sharding by score range or segment with a strategy for global rank, exact-top-N /
approximate-tail to avoid costly cross-shard exact ranks, coalescing very hot updates, score validation for
anti-cheat, and clean handling of time-scoped and friend leaderboards.
Further reading