Design a Leaderboard

Design a Leaderboard (real-time ranking at scale)

A leaderboard sounds like homework you already finished: "there's a scores table, I run SELECT ... ORDER BY score DESC LIMIT 100, done." That answer is complete for exactly one game session with a hundred players. Ship it to a game with 50M players and 10M daily-actives and it detonates on two separate axes at once. First, the query itself: sorting 50M rows to return 100 is O(N log N) — ~1.28 billion comparisons — on every single leaderboard page load. Second, and worse, the question players actually care about most: "what's my rank?" A player sitting at the median has ~25M people above them, and answering "how many players outscore me" naively is a COUNT(*) WHERE score > myscore that walks ~25M index entries per rank query. This lab derives why the answer is a Redis Sorted Set (a span-augmented skip list), where ZADD, ZREVRANGE, and ZREVRANK are all O(log N) — ~26 operations instead of 25 million — and then confronts the genuinely hard part that trips up strong candidates: a single user's exact rank once the board is sharded across nodes.

1. The Trap — the SQL leaderboard that melts under its own reads

Concretely: a mobile game, 50M registered players, one global all-time leaderboard, a scores(user_id PK, score, updated_at) table in Postgres. The product shows the top 100 and every player's own rank. Two naive queries run constantly:

-- top 100
SELECT user_id, score FROM scores ORDER BY score DESC LIMIT 100;
-- a player's rank
SELECT COUNT(*) + 1 AS rank FROM scores WHERE score > :myscore;

Trace the top-K query without an index. Sorting 50M rows to hand back 100 is O(N log N): 50,000,000 × log₂(50M) ≈ 50M × 25.6 ≈ 1.28 billion comparisons per query. At the read rate we compute in movement 4 (~11.6K reads/s average) that's ~1.28×10⁹ × 11,574 ≈ 1.5×10¹³ comparisons/second demanded of the database. That is not a tuning problem; it is physically impossible on one box.

"So add an index on score." Good instinct — it fixes top-K (a B-tree index scan reads just the first 100 leaves, cheap). But it does not fix rank-of-user, and rank is the query players hit most. COUNT(*) WHERE score > myscore on a B-tree index still has to walk every index entry in the matching range to count them — standard B-trees don't store subtree cardinalities, so there's no O(log N) "how many keys are above this one." For a median player, that's ~25,000,000 index entries scanned for a single rank lookup. Ten such lookups a second and you're reading a quarter-billion index entries a second — for one number.

That's the trap in one sentence: the leaderboard's headline feature (my rank) is exactly the operation a relational index is worst at. You need a structure where "how many elements rank above this one" is itself O(log N), not O(N).

2. Scope it like a senior (ask before you design)

Every one of these answers changes the design — pin them down before drawing a box:

• Top-K only, or arbitrary rank-of-user too? Showing the top 100 is easy (any indexed store does it). Returning any player's exact rank — and the neighbours around them ("you're #4,381,206, here are #4,381,204–208") — is the hard requirement that forces the data structure. Confirm the product needs it.
• Real-time or periodic? Does rank update the instant a score changes, or is a leaderboard snapshot recomputed every minute/hour acceptable? Batch snapshots make everything trivially cheap (precompute, cache, serve) and are the right answer for many products — don't build real-time if nobody needs it.
• Exact rank, or is "top 5%" enough? For 500M players, telling someone they're "rank 12,483,902" is meaningless to them and expensive to you; "top 3%" is cheap, shard-friendly, and often better UX. This single answer decides exact-vs-approximate (movement 6).
• Time windows? Daily / weekly / seasonal / all-time? Each window is its own ranking that must expire independently. This multiplies your write fan-out (one score submit touches every active window).
• Ties? Two players with identical scores — deterministic order (by earliest-achieved, then user_id) or don't-care? Matters for stable pagination.
• Score semantics: is a submitted score the player's new absolute best (ZADD, keep max) or a cumulative increment (ZINCRBY)? Changes the write op.
• Scale: total players, DAU, submissions/player/day, leaderboard views/player/day. Drives every number below.

Assume for this lab: 50M registered players; 10M DAU; ~10 score submissions/DAU/day; ~100 leaderboard-or-rank views/DAU/day; top-K and exact rank-of-any-user both required; near-real-time (a couple seconds' staleness OK); daily + weekly + all-time windows; ties broken deterministically; score = keep-the-max (ZADD with a max-merge). Exact rank required at 50M; at 100× we'll allow approximate for the long tail (movement 7).

3. Reason to the design (derive it, don't recite it)

Attempt 1 — RDBMS table + ORDER BY. Covered in The Trap. Top-K without an index is a 1.28-billion-comparison sort per read; rank-of-user even with an index is an O(N) range count (~25M entries for a median player). Dead on reads. Reject.

Attempt 2 — keep the table, precompute a rank column. Store each player's rank as a materialised integer, updated on write. Now reads are trivial (SELECT rank WHERE user_id=?, O(1)). But look at the write: when one player's score changes and they jump from #4,000,000 to #3,999,000, the ranks of the ~1,000 players they leap-frogged all shift by one. A single score submit can invalidate millions of rank values. At ~1.2K writes/s each potentially rewriting a huge swath of the table, you've moved the O(N) cost from reads to writes and made it worse (writes now contend and cascade). Reject.

What we actually need is a single structure that does all three of these in sublinear time:

• submitScore(user, score) — insert-or-update one element,
• getTopK(k) — the k highest by score,
• getRank(user) — the number of elements that rank above a given element.

That third operation is the tell. A plain sorted array gives O(1) rank but O(N) insert; a plain balanced BST gives O(log N) insert but O(N) rank (you'd have to count nodes). The structure that gives O(log N) for all three is an order-statistics tree: a balanced search tree where every node also stores the size of its subtree. To find an element's rank you walk from the root to the element, summing subtree sizes as you step right — O(log N). To find the k-th element you descend using those sizes — O(log N).

Attempt 3 — Redis Sorted Set, which is exactly this. A Redis ZSET is two structures kept in sync: a hash (member → score, gives O(1) ZSCORE) and a skip list ordered by (score, member). The skip list is the order-statistics tree in disguise: each forward pointer stores a span — the number of elements it skips over. Summing spans along the search path yields rank in O(log N), which is precisely why ZRANK/ZREVRANK are O(log N) and not O(N). So:

submitScore(u, s)  ->  ZADD board GT u s        # O(log N); GT = keep the max
getTopK(k)         ->  ZREVRANGE board 0 k-1     # O(log N + k)
getRank(u)         ->  ZREVRANK board u          # O(log N)  <-- the whole ballgame
getScore(u)        ->  ZSCORE board u            # O(1)

For a median player: ZREVRANK is ~log₂(50M) ≈ 26 skip-list hops versus the ~25,000,000 index entries the SQL COUNT walked — a ~10⁵× reduction (25M / 26 ≈ 960,000) in work for the exact same answer. That is why the sorted set is the mechanism, not a habit.

4. Build it — the design worksheet

This is the artifact you'd produce on the whiteboard. Work it in order; every number is traced, recompute it yourself before an interview.

Functional requirements

• submitScore(userId, score) — keep the player's max; update all active time windows.
• getTopK(k) — the top k with scores, for a given window.
• getRank(userId) — the player's 1-based rank in a window.
• getNeighbors(userId, w) — the w players immediately above and below (the "you're here" view).

Non-functional requirements

• Low read latency (single-digit ms for top-K and rank) — reads dominate 10:1.
• Durability of scores — a cache flush must not lose a player's progress (the ZSET is a fast index over a durable source of truth, not the source of truth itself).
• Availability > strict consistency for the ranking view — a rank that's a second or two stale is fine; losing writes is not.

Back-of-envelope estimation (BOTE)

• Writes: 10M DAU × 10 submissions/day = 100M submissions/day ÷ 86,400s ≈ 1,157/s ≈ ~1.2K writes/s avg. Gaming has a strong evening peak; take 5× → ~5.8K writes/s peak.
• Reads: 10M DAU × 100 views/day = 1B/day ÷ 86,400 ≈ 11,574/s ≈ ~11.6K reads/s avg; 5× peak → ~58K reads/s peak. Read:write ≈ 10:1 — confirmed read-heavy.
• Total peak ops: ~5.8K + ~58K ≈ ~64K ops/s. Hold that number — a single Redis node sustains 100K+ simple ops/s, so this fits on one node. (The punchline of movement 6: at this scale you do not shard for throughput. You shard at 100×.)
• Memory for the all-time sorted set (N = 50M members): per-entry cost in a Redis ZSET, broken down —
  • member string (a numeric userId as an sds string): ~30 B
  • score (IEEE-754 double): 8 B
  • skip-list node (backward ptr + level array, avg ~1.33 forward ptrs each with a span): ~30 B
  • hash (dict) entry for O(1) ZSCORE (key ptr + val + next + bucket load): ~32 B
  • ≈ 100 B/entry.
  50,000,000 × 100 B = 5 GB for one all-time board. With 1 primary + 2 replicas → ~15 GB total cluster memory — a single modest Redis instance. The daily/weekly windows are smaller (bounded by DAU, not total players) and TTL out, adding little.

API sketch

POST /v1/scores
     body: { userId, score }              // keep-max semantics
     -> 200 { rank, score }               // ZADD GT; return new rank

GET  /v1/leaderboard?window=all&k=100
     -> 200 { entries: [{userId, score, rank}, ...] }   // ZREVRANGE 0..k-1

GET  /v1/rank/{userId}?window=weekly
     -> 200 { rank, score, percentile }    // ZREVRANK (+ ZCARD for percentile)
     -> 404 if the user has no score in that window

GET  /v1/rank/{userId}/neighbors?window=all&w=5
     -> 200 { entries: [...11 rows centred on the user...] }   // ZREVRANK then ZREVRANGE r-w .. r+w

Data model & partitioning — the hard part

One Redis key per (metric, window): lb:all, lb:weekly:2026-W28, lb:daily:2026-07-11. Daily/weekly keys carry a TTL so they self-expire; all-time never expires. Behind them, a durable store (Cassandra/DynamoDB, userId → best_score) is the source of truth so the ZSET can be rebuilt after a flush. A submit does ZADD GT to each active window; persistence to the durable store is async, off the hot path.

The question the interviewer is really probing: a global ranking is inherently one totally-ordered list — how do you shard that? Three strategies, and their costs (full table in movement 6):

• (a) Hash + scatter-gather. Shard players by hash(userId) mod P; each shard is its own sorted set. Top-K = ask all P shards for their local top-k, merge (the global top-k is always a subset of the union of per-shard top-k). Rank-of-user = your local rank in your own shard is not your global rank, so you must ask every other shard "ZCOUNT how many of yours score above X" and sum. Exact, but O(P log N) with a fan-out whose latency is bounded by the slowest shard (straggler). Writes spread evenly — no hot shard.
• (b) Score-range buckets (range sharding). Shard by score band (0–1K on shard A, 1K–2K on B, …). Top-K = just the top band's shard. Rank = local rank in your band + total counts of all higher bands (few, cheap). But: players cluster in low bands → skewed, hot low-band shards; and a score increase can move a player across shards (delete here, insert there — a cross-shard migration on a hot path).
• (c) Approximate rank via a score histogram. Maintain a coarse count-per-score-bucket per shard. Rank ≈ sum of counts in buckets above yours (+ interpolation within your bucket). O(#buckets), trivially mergeable across shards, no straggler-sensitive fan-out. Gives "top 3%", not "#12,483,902". The right answer when the product doesn't need exact deep ranks.

High-level diagram — write path vs read path

Writes route to the single owning shard (hash(userId) mod P) and persist async to the durable store. Reads (top-K, rank) fan out across all P shards and merge — that fan-out, not the per-op cost, is what movement 5 breaks.

Rubric — what a strong answer hits

• States the BOTE (writes/s, reads/s, memory) out loud and notices that ~64K peak ops and 5 GB fit on one node — i.e. does NOT over-shard at 50M.
• Names the sorted set / order-statistics tree because getRank needs O(log N) "count above," and can explain the span-augmented skip list — not "add an index" (which leaves rank O(N)).
• Treats sharding a global ranking as the genuinely hard problem, and picks among hash+scatter-gather, range buckets, and approximate rank with the trade-off stated.
• Keeps a durable source of truth behind the cache (the ZSET is a fast index, rebuildable), and puts persistence off the hot path.
• Distinguishes exact rank (top-K + your neighbours) from approximate rank (deep tail = "top 3%").
• Model-answer reading: the guide has no dedicated leaderboard page; build your worksheet against the closest concept pages — Designing YouTube Likes Counter (the counter/aggregation angle), Data Sharding Techniques, and Designing Typeahead — Trie + Precomputed Top-K (the top-K-at-scale angle).

5. Break it — three traced failure scenarios

1. Hot-key write contention on a single sorted set (at 100× scale). At the base 50M/~64K ops/s, one node is fine. Now grow to 500M players and a live esports finale driving the write rate up 100× → peak submitScore ~580K writes/s, all ZADD to the one hot key lb:all. Redis executes commands single-threaded; a realistic ceiling is ~100K–150K ops/s per node. So 580K writes/s against one key is a 4–6× overload — the command queue backs up, latency climbs from sub-ms to seconds, and reads sharing that node stall too. Adding read replicas does not help: replicas offload reads but every write still funnels through the single primary that owns the key. The key insight: a leaderboard's hot key is a write hot key, and you can't replica your way out of write contention — you must shard the key space.

2. Sharding silently breaks exact global rank. You shard by hash(userId) mod 32. A player is #1 on their own shard of ~1.5M members. Naively you return "rank 1." Wrong: there are 31 other shards, and if just 100 players scattered across them outscore this player, their true global rank is ~101, not 1. Local rank ≠ global rank — ever, for hash sharding. To get the exact answer you must fan out: ZCOUNT(shard_i, (myscore, +inf)) on all 32 shards and sum. Each ZCOUNT is ~log₂(15.6M) ≈ 27 hops (cheap), but the request now waits on 32 parallel RPCs and finishes only when the slowest shard replies — one GC pause or a hot neighbour on any single shard tail-latency-poisons every rank query. This is the straggler tax that movement 6 weighs against approximate rank.

3. Ties + concurrent updates = pagination drift. A client pages the board 100 at a time: ZREVRANGE 0 99, then ZREVRANGE 100 199. Between the two calls, a player ranked #40 submits a higher score and jumps to #5. Everyone from #5–#39 shifts down one rank. The player who was at index 99 is now at index 100 — so page 2 (100 199) repeats them, and the player who was at 100 got pushed to 101 and is skipped only if they moved, etc. Offset pagination over a mutating ranking double-shows or drops rows. The tie sub-case makes it worse: two players with the same score are ordered lexicographically by member, so a member-id change or a same-score insert reshuffles within the tie band. Fix: paginate by score cursor (ZREVRANGEBYSCORE ... LIMIT offset count anchored on the last seen (score, member)) instead of by numeric index, so a shift above your cursor doesn't duplicate rows below it.

6. Optimise — with trade-offs

Bottlenecks worth naming out loud:

• The board's single hot key is a write bottleneck, not a read one (Break It #1). The fix is horizontal sharding of the key space, which then imposes the scatter-gather rank cost (Break It #2) — you're trading a throughput wall for a fan-out/tail-latency cost. That trade is the whole design conversation at 100×.
• Exact deep rank is the expensive query. Top-K is always cheap (bounded work). It's "rank #12M of 500M" that forces either an all-shard fan-out (exact, straggler-bound) or a histogram (approximate, cheap). Decide which the product actually needs (movement 2).
• Write fan-out across time windows: one submit touching daily+weekly+all-time is 3× the write ops. Batch them in a single pipelined/MULTI round-trip to the owning shard.

Decision	Option A	Option B	Pick when
Core ranking structure	Redis Sorted Set (span-augmented skip list): ZADD/ZREVRANGE/ZREVRANK all O(log N)	RDBMS table + B-tree index on score	Sorted Set whenever rank-of-user matters — the B-tree does top-K fine but leaves rank an O(N) range COUNT (~25M entries for a median player). Reach for the DB only if you need heavy relational queries on the same data and rank is rare/offline.
Exact vs approximate rank	Exact rank via all-shard ZCOUNT fan-out	Approximate rank via score histogram / percentile buckets	Exact for the top-K and a player's immediate neighbourhood (cheap, and users care). Approximate for the deep tail ("top 3%") — O(#buckets), mergeable, no straggler tax; the number is more meaningful to the user anyway. Most large boards do both: exact near the top, approximate below.
Sharding strategy for the global board	Hash + scatter-gather (even load; rank = fan-out sum)	Score-range buckets (top-K = one shard; rank = cheap band sums)	Hash when writes must spread evenly and you can pay the rank fan-out. Range buckets when top-K dominates and rank is rare — but beware low-score-band skew and cross-shard migration when a score climbs out of its band. Hash is the safer default; range buckets are a specialised optimisation.
Update cadence	Real-time (ZADD on every submit)	Batch snapshot (recompute board every N seconds, serve from cache)	Real-time when players expect their rank to move the instant they score (competitive games). Batch when a few seconds/minutes of staleness is fine (weekly marketing boards) — batch collapses reads to serving a static blob and removes almost all hot-key pressure. Don't pay for real-time nobody notices.
Durability of the ranking	ZSET as index over a durable store (Cassandra source of truth, async persist)	Redis AOF/RDB as the only copy	Index-over-durable-store almost always — a Redis flush/failover must never lose a player's lifetime best; the ZSET is rebuildable from the source of truth. Redis-only persistence is acceptable only for ephemeral boards (a single daily board you're willing to lose).

7. Defend under drilling

Q1 — "Why not just an indexed SQL column? Indexes are sorted."
An index makes top-K cheap but leaves rank-of-user O(N): COUNT(*) WHERE score > X walks every index entry in the range because a plain B-tree doesn't store subtree cardinalities — ~25M entries for a median player in a 50M board. The sorted set's skip list stores a span per pointer, so it sums "how many are above" in ~26 hops. Rank is the headline feature and the index is worst at exactly it.

Q2 — "Redis is in-memory; what happens on a crash / failover?"
The ZSET is a rebuildable index, not the system of record. Every submit also persists to a durable store (Cassandra, userId→best_score) asynchronously off the hot path. On cold start we rebuild the ZSET from that store (ZADD in bulk); in steady state we run 1 primary + 2 replicas per shard with AOF for fast recovery. A player's lifetime best is never only in RAM.

Q3 — "How do you do time-windowed boards without recomputing?"
One ZSET per (window,bucket): lb:daily:2026-07-11, lb:weekly:2026-W28, lb:all. A submit pipelines a ZADD to each active window in one round-trip. Daily/weekly keys carry a TTL and self-expire — no sweeper job, no recompute. All-time never expires. Reads target the specific window key.

Q4 — "Two players tie. What's the order, and why does it matter for paging?"
Redis orders ties by member lexicographically. For a stable, product-meaningful tiebreak (earliest to reach the score wins) we encode the score as a composite: score * 10^13 - achieved_at_ms as the ZSET score, so an earlier timestamp sorts higher within the same raw score. And we paginate by score cursor (ZREVRANGEBYSCORE anchored on last-seen), not numeric offset, so a rank shift above the cursor can't duplicate or drop rows below it (Break It #3).

Q5 — "A viral moment 100×'s your write rate. Walk me through what breaks and your fix."
Peak submitScore goes ~1.2K→~580K writes/s and memory ~5→500 GB (5B members × 100 B). Both blow past one node: 580K writes/s > a single Redis primary's ~100K–150K ops/s, and 500 GB > one box's RAM. Fix: shard the key by hash(userId) mod P. Sizing P: memory needs 500 GB ÷ ~25 GB usable/node = 20 shards; write throughput needs 580K ÷ ~80K/node ≈ 8 shards. Take P = 32 (power of two, headroom on both) → ~15.6M members and ~18K writes/s per shard — comfortable. Top-K becomes a 32-way merge of per-shard top-K; rank becomes the scatter-gather in Q6.

Q6 (the hard one) — "Give me a single user's exact rank among 500M entries once it's sharded."
Local rank on the user's own shard is not global rank (Break It #2). Exact global rank = 1 + ∑ over all P shards of ZCOUNT(shard_i, (myscore, +inf)) — "how many players on each shard outscore me," summed. Each ZCOUNT is ~log₂(15.6M)≈27 hops (fast); the cost is the P-way parallel fan-out whose latency is bounded by the slowest shard (straggler). Three ways to make it acceptable: (a) issue all P in parallel and cap with a deadline/hedged request; (b) for the deep tail, serve approximate rank from a periodically-merged global score histogram (O(#buckets), no fan-out) and reserve exact fan-out for the top ranks where users actually care and shard-local counts are tiny; (c) if exact-everywhere is truly required, precompute per-shard cumulative-count checkpoints refreshed every few seconds so a rank query reads cached partial sums instead of live-counting. The honest staff answer: exact real-time rank for an arbitrary deep-tail user at 500M is expensive and rarely needed — give exact ranks where they matter (the top) and approximate where they don't.

Q7 — "Cheater submits an impossible score and sits at #1. Design response?"
Ranking is a fast index; correctness lives at write admission. Validate/authenticate submissions server-side (signed session, server-recomputed score, anomaly checks) before ZADD. Removing a bad entry is a single ZREM on the owning shard (O(log N)) plus a tombstone in the durable store — the structure makes correction cheap; the policy is what's hard.

8. You can now defend

• You can show, with a traced number (~25M index entries vs ~26 skip-list hops, a ~10⁵× gap), why rank-of-user forces an order-statistics structure and an indexed SQL column doesn't cut it.
• You can size the system honestly — recognise that 50M players / ~64K ops / 5 GB fit on one Redis node, and refuse to over-shard until the numbers (100×: 580K writes/s, 500 GB) actually force P≈32.
• You can articulate the genuinely hard problem — exact rank over a sharded global ranking — and defend the scatter-gather-ZCOUNT answer, its straggler cost, and when to trade it for an approximate histogram.
• You can pick real-time vs batch, exact vs approximate, and hash vs range sharding each as a stated trade-off tied to a product requirement, not a reflex.

---

Re-authored/Deepened for this guide. Model-answer reading: Designing YouTube Likes Counter (System Design Problems, the counter/aggregation angle); Data Sharding Techniques and Designing Typeahead — Trie + Precomputed Top-K for the sharded-top-K angle. Escalation cross-referenced with Consistent Hashing, Shard Keys: many-key skew vs a single hot key, Data Partitioning — Fan-out Stragglers (Deep Dive), Designing Unique ID Generator, and the Memory & Cache-Sizing Playbook.

I just read a lesson on **Design a Leaderboard** (Hands-On Builds) and want to truly understand it. Explain Design a Leaderboard from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Teach me **Design a Leaderboard** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Quiz me on **Design a Leaderboard** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Help me remember **Design a Leaderboard** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.