CHAPTER DEEP READ · System Design Interview Vol 2 · Ch 10

Design a Real-time Gaming Leaderboard

System Design Interview Vol 2 · Ch 10 · Alex Xu & Sahn Lam · 2022

What is this chapter about?

The weekly ranking in a mobile game, the step count board in a fitness app, the donor board in a livestream — they all look like nothing more than "sort people by score." This chapter builds one from scratch: millions of players at once, scores changing every second, and every one of them wants to be told, right now, where they stand.

One strange thing first

It sounds like a job for a rack of machines. But the first thing this chapter does is reach for a calculator. And the arithmetic says: a monthly board for five million active players is only a few hundred megabytes, and at its busiest takes a couple of thousand changes per second. One machine holds it. One machine keeps up with it.

That is the real lesson of the chapter: do the arithmetic before you draw the architecture. A great many "we obviously need a distributed system" instincts do not survive contact with a calculator.

Why the old way is hard

Put the scores in an ordinary database and "show me the top ten" is easy — sort by score, take the first ten rows.

The hard question is the other one: "where am I?" A database has no notion of "nth." All it can do is count: how many people scored higher than me? If you sit in the middle of twenty-five million players, it has to count ten million of them before it can answer "you're tenth-millionth." Let everybody ask that once and the machine falls over.

The mechanism, intuitively

① Counting has to be able to skip. Line everyone up by score. Chain them one by one only on the bottom row, then build a few express lanes above it, where a single hop clears a long stretch of people. The trick is that every hop also records how many people it just jumped over. So working out a rank means taking a few express hops and adding up what you skipped, instead of pointing at people one at a time. Twenty-five million players still take only about twenty steps.

② A leaderboard is one thing, and it doesn't cut. If there are too many players for one machine, the instinct is to split them across several. But "where am I" is a question about the whole field. Scatter players randomly across machines and each one knows only the order of its own handful — nobody can answer, so you have to ask all of them and stitch the answers together.

③ So you split by score band instead. Not random players, but score ranges: everyone above 900 on one machine, 800–899 on the next. Now "where am I" is simply how many people sit in the bands above mine (one number per machine) plus my place inside my own band. The price: if everyone's scores crowd into the same band, that machine gets crushed.

④ Don't be exact for everybody. The top ten must be perfect — but nobody alive cares about the difference between eight-millionth and eight-million-and-first place. Telling the vast middle "you're in the top 12%" is far cheaper than counting to the exact integer, and they understand it better anyway.

What it costs

To be this fast the board lives in memory, so a restart can lose the last few seconds — or minutes — of scores; the real ledger has to be kept on disk elsewhere, ready to rebuild the board at any time.

One line to remember

A leaderboard's hard part was never sorting — it is "where am I," a question you cannot answer without seeing the whole field. The fix is express lanes over the sorted line, each hop recording how many people it skipped, so a rank can be added up instead of counted out. When you genuinely must split across machines, you can only split by score band, never by player, or the field-wide ranking dissolves. And for almost everyone, "you're in the top 12%" is the better deal.

Want the mechanisms, the notation and the diagrams? → Switch to the deep read

In one line

On the surface this chapter builds a leaderboard for a game. What it actually teaches is two things. The first is counter-intuitive: do the arithmetic before you draw the architecture — five million DAU sounds like it demands a distributed system, but the numbers come out at roughly 2,500 QPS at peak and a few hundred megabytes, and one Redis instance is enough. The second is the chapter's central tension: a rank is a global quantity, and sharding is an act of localization, so the two are natively at war. Every design in the chapter — the span carried on skip-list pointers, score-bucketed shards, approximate percentiles — is haggling over the same question: how do you say "you are nth" without looking at all the data?

Glossary

Leaderboard: a set of members each carrying a score, supporting "give me the top N" and "what rank is this member." This chapter designs a monthly board that resets each month.
Sorted set: a Redis structure where every member has a score and the set stays ordered by it. Commands: ZADD (write), ZINCRBY (add to a score), ZREVRANGE (top N), ZREVRANK (a member's rank).
Skip list: a sorted linked list with a few layers of express-lane indexes stacked on top; lookups and positioning are O(log n) — multiply the data by a million and you add only about twenty steps.
Span: an extra number stored on each skip-list pointer — how many nodes this one hop jumps over. A rank is the sum of the spans along the path.
Sharding / partitioning: splitting one large dataset across machines by some key, so each machine holds only a slice.
Hash slot: Redis Cluster hashes a key name into one of 16384 slots, and slots are assigned to nodes. A single key always lands entirely on one node.
Scatter-gather: a query that must ask every shard and merge the answers. It gets more expensive with more shards, and is held hostage by the slowest one.
QPS: queries per second. P99 latency: out of a hundred requests, how long the 99th-slowest one took.
Source of truth: the authoritative copy. A cache or in-memory structure can be rebuilt from it; if it is lost, the data is genuinely gone.

Where it sits

Chapter 10 of Volume 2. It follows Ch9 on object storage — where you build a storage component yourself — and returns to assembling a system from off-the-shelf parts, except that it pushes the estimation craft of Vol 1 Ch2 to its limit: the most important decision in the chapter is made after the arithmetic, not before it. The real-world counterparts are weekly and monthly boards in mobile games, rankings in fitness apps like Strava, live sales boards in e-commerce, donor boards in livestreams — anything that wants a live rank.

What the chapter is solving

The requirements are small, and every one of them bites: ① show the top ten; ② show a given user's exact rank; ③ show the four users above and below them; ④ reflect a score change in real time. The first two look like the same feature and differ by an order of magnitude in cost — which is exactly the engine of the chapter.

The book's scale assumptions and the arithmetic on them are worth memorizing verbatim; this is the kind of estimate you reproduce at a whiteboard:

5 million DAU. A day is about 10^5 seconds, so on average about 50 players/second start a game; at a 5× peak, 250/second.
Ten games per player per day → score updates at about 500 QPS, peaking near 2,500 QPS.
Fetching the top ten: one open per user per day → about 50 QPS.
Storage: assume 25 million users in a month; each entry is a 24-byte user ID plus a 2-byte score = 26 bytes, so 25M × 26B ≈ 650MB.

The conclusion is the line to keep: 2,500 QPS and a few hundred megabytes is comfortably within one Redis instance (a single instance serves simple commands in the hundreds of thousands per second range). One honest correction: 650MB is the raw payload — skip-list nodes and hash-table entries both carry pointers, so real memory is typically a multiple of that. Even so, it is still single-machine territory. The value of estimation is not precision; it is that it tells you what you do not have to build.

So where is the difficulty? Requirement ②. In a relational database, SELECT COUNT(*) FROM scores WHERE score > ? has to actually count those rows, index or no index. A player in the middle of twenty-five million scans ten million index entries for a single query. "What rank am I" is not a sorting problem, it is a counting problem — and counting is inherently O(n). Every trick in the chapter exists to push that O(n) down.

The core, properly

① Inside a sorted set: a rank is counted, not sorted

A Redis sorted set maintains two indexes at once: a hash table (member → score, so looking up one player's score is O(1)) and a skip list ordered by score, which handles ranges and ranks.

The intuition for a skip list is a metro system: the bottom layer is the local train stopping everywhere (all nodes on one sorted list), and above it sit express lines skipping more and more stations. To find a position you take the fastest line, overshoot, drop a level, and repeat — O(log n) hops, so twenty-five million players is about twenty-some steps.

But a skip list alone still cannot state a rank. The actual mechanism is this: every pointer additionally stores a span — how many nodes this hop crossed. So ZREVRANK never counts heads; it sums spans along the way. A rank goes from "count n people" to "add up log n numbers," and the chapter's hard problem is erased in one stroke.

Two implementation details worth carrying: ties are broken by the member name's lexicographic order (so equal scores get a deterministic — but arrival-order-blind — ordering), and the bottom list carries back pointers, so walking from high score to low (ZREVRANGE) is as fast as walking forward.

Fig 1 · A rank is the sum of the spans stored on skip-list pointers; "where am I" turns from counting ten million people into adding twenty numbers.

② A rank is global; sharding is local

The arithmetic already told us one node suffices. The book still pushes "but what if it doesn't" all the way — because that push is what exposes how a leaderboard differs from ordinary business data.

Start with a commonly misread fact: Redis Cluster will not shard your leaderboard. It hashes key names into 16384 slots, and the whole board is one key — it sits entirely on one node, and adding cluster nodes helps not at all. To shard, the application has to cut one board into several keys. There are only two ways to cut.

Cut by hashing the player (scatter players over N boards): writes distribute perfectly, and ranking breaks completely — each shard knows only its own members' order. A global rank means asking every shard and merging; so does a global top ten. More shards is more expensive, and you inherit the slowest shard's latency.

Cut by score bucket (900+ on one, 800–899 on the next…): this is the path that works. A global rank is the sum of the member counts of every higher bucket (one cheap ZCARD-class number per bucket) plus my rank inside my own bucket. The top ten comes from the highest bucket alone. The cost is equally honest: the distribution drifts — rebalance the game or end a season and everyone crowds into a few buckets, which become hot shards, and bucket boundaries are hard to redraw online.

The comparison is worth keeping as a general rule: the shard key must line up with the query's scope. Ordinary business queries ask about "one user's data," so sharding by user is natural; a rank asks about the whole field, so it must be sharded by score — the very dimension being queried.

Fig 2 · Sharding by player evens out writes but destroys ranking; sharding by score band keeps rank computable, at the price of hot buckets when the distribution drifts.

③ Exact ranks are expensive, and almost nobody needs one

Even with sharding done right, computing an exact rank for every one of tens of millions of players is money thrown away. The book's way out is to relax the requirement: the top ten must be exact (it is the product's shop window), and a player's four neighbours above and below are cheap too — take their rank with ZREVRANK, then one short ZREVRANGE over the adjacent slice.

What is genuinely expensive is the exact "8,120,431st" in the middle — and that is precisely the number no user cares about. The alternative is an approximate percentile: bucket players by score, maintain only a count per bucket, and answer "you're in the top 12%." The cost drops from "maintain a global ranking in real time" to "refresh a few dozen counters periodically," and the answer is easier to read besides.

In an interview this move is worth more than any technology choice: volunteering that requirement ② can be downgraded for the middle of the pack shows you are designing a system rather than implementing a spec.

④ The write path: no direct clients, and Redis is not the ledger

Two questions remain that are easy to skip and costly to have skipped.

Can the client write to Redis directly? No. First, scores must be adjudicated server-side; letting the client report its own score hands out the right to cheat. Second, shipping Redis credentials to a few million phones is the same as having no credentials. The path must be: client → game service (validate, compute the score) → leaderboard.

Can Redis be the source of truth? No. It is an in-memory structure persisted by snapshots and an append-only log: with the log fsynced once a second, the worst case loses tens of seconds of writes; with snapshots alone it can lose minutes. So scores are also written to a durable ledger (a relational database, or via a log like Kafka that feeds both the board and the warehouse), and the board in Redis is defined as a derived view that can be rebuilt from the ledger at any time. "The Redis cluster died" then degrades from an incident into a rebuild.

Two design details ride along: the board stores only user IDs and scores (which is what makes the 26-byte entry true), with names and avatars fetched from the database and cached; and the monthly board uses a month-stamped key (rank:2026-09), so a season reset is a single key deletion.

Fig 3 · The server adjudicates the score, then it lands in both a durable ledger and the in-memory board; the board is defined as a view that can always be rebuilt.

Key trade-offs

Table 1 · Three implementations: the difference is not speed, it is what "where am I" costs

Option	What it buys	What it costs (honestly)	When to pick it
Relational DB	No new component; top ten is an index read; durable by nature, can be the ledger	Rank is a count, `O(n)`: a mid-table player scans ten million index entries, and live updates keep the index churning	Tens of thousands of players, or ranks refreshed nightly
Redis sorted set (the book's pick)	Write and rank both `O(log n)`; one command per score update; a single instance carries this chapter's whole load	Not a source of truth (needs a durable ledger alongside); memory billed by the GB; one board is one key, so a cluster can't scale it out	The default answer for a live board — use it, don't pre-shard
NoSQL (e.g. DynamoDB)	Durability and elastic capacity handled by the managed service; replicated by default	You build ranking yourself: one partition key for the whole board is a hot partition, and splitting into N partitions turns the top ten into a scatter-gather	Already deep in that managed stack and able to live with approximate ranks

Table 2 · If the day really comes: the two ways to cut

Cut	What improves	What gets expensive (honestly)	When it applies
By player hash	Perfectly even writes; trivial to scale in and out; Redis Cluster does it for free	Ranking is destroyed: every rank query and every top-ten fans out to all shards and merges	Only when you need per-player history, not a global rank
By score bucket	Rank = sum of higher-bucket counts + rank within bucket; top ten asks one bucket	Drift means hotspots: a season or a balance patch crowds players into a few buckets, and boundaries resist online redrawing	The only workable cut if exact global ranks must survive
Don't cut yet	Zero complexity; entirely sufficient at the scale this chapter computed	A single-node ceiling overhead: memory and single-threaded throughput both cap out, so have a plan for the day you cross it	Whenever the arithmetic says it fits — i.e. most of the time

Table 3 · Rank precision: tiering the requirement is the cheapest optimization

Requirement	How	What it costs (honestly)
Top ten	One `ZREVRANGE 0 9`, or ask the highest bucket only	Nearly free — but must be exactly right; it is the shop window
Four above and below me	Get my rank, then read the adjacent slice	One lookup plus one short range read; still cheap
Exact rank for the middle	Maintain a strict global ranking	The priciest item, and nobody cares: 8,120,431st and 8,120,432nd mean the same thing to a player
"You're in the top 12%"	Bucket by score, keep only per-bucket counts, refresh periodically	Approximate and slightly stale; in exchange cost drops an order of magnitude and users understand it better

Why it matters / in real systems

This chapter travels far beyond games: any "live rank" or "live top N" is the same problem — trending topics, live e-commerce sales boards, livestream donors, sorting anomaly scores in fraud detection. And the criterion is always the same: ask first how exact the "nth" has to be and who is going to read it, then decide whether it deserves a distributed system.

EVIDENCE FROM INDUSTRY

"Span" is not a textbook nicety; it is a modification Redis made to the skip list on purpose. The comment in Redis's own source states: "This skiplist implementation is almost a C translation of the original algorithm described by William Pugh in Skip Lists: A Probabilistic Alternative to Balanced Trees, modified in three ways: a) this implementation allows for repeated scores. b) the comparison is not just by key (our 'score') but by satellite data. c) there is a back pointer, so it's a doubly linked list with the back pointers being only at 'level 1'. This allows to traverse the list from tail to head, useful for ZREVRANGE." The two properties this chapter leans on — equal scores allowed, and walking from high to low as fast as low to high — were deliberately added, not inherited.Redis source src/t_zset.c · github.com/redis/redis
"Don't shard yet" has vendor backing — and the vendor names leaderboards as the workload that hits the single-node ceiling first. Google Cloud's launch post for Memorystore for Redis Cluster says: "in industries like gaming (leaderboards, session stores), finance (fraud detection), ads (ultra-low-latency serving), or retail (checkouts), workloads push the boundaries of a standalone Redis shard and require the performance and horizontal scale of Redis Cluster," and claims the new service "provides 60 times more throughput with microseconds latencies and supports 10 times more data." Note what it concedes: a single shard does top out — this chapter's numbers simply have not reached it.Kyle Meggs & Matt Geerling · Google Cloud Blog · 2023-08-30 · Memorystore for Redis Cluster Launched
"Redis is not the ledger" comes with an exact number. Redis's shipped config file is blunt about the three fsync policies: "no: don't fsync, just let the OS flush the data when it wants. Faster. / always: fsync after every write to the append only log. Slow, Safest. / everysec: fsync only one time every second. Compromise." And it states plainly that with default Linux settings "it is possible to lose up to 30 seconds of log in the worst scenario"; with snapshots alone, "a power outage may result into a few minutes of writes lost." Treating the leaderboard as the only copy means accepting that number.Redis official redis.conf comments · github.com/redis/redis
Stuffing a whole board under one partition key hits hot partitions on managed NoSQL. Amazon's DynamoDB paper describes throttling caused by skewed access and the adaptive-capacity and split-for-traffic mechanisms built in response — which is exactly why this chapter's NoSQL option must break the board into N partition keys and then scatter-gather over them.Source: Elhemali et al., "Amazon DynamoDB: A Scalable, Predictably Performant, and Fully Managed NoSQL Database Service," USENIX ATC 2022. That domain is blocked by this run's egress proxy, so the citation is text-only.

Pitfalls and disputes

Sharding on arrival. The chapter's biggest lesson is that the arithmetic says don't. Drawing a sharding diagram before estimating is the most common way to lose points in an interview; conversely, computing 2,500 QPS and then saying "one instance is enough, and here is my plan for the day it isn't" lifts the whole conversation.
Expecting Redis Cluster to scale a leaderboard. It shards by key, and a board is one key — add all the nodes you like, the key stays on one of them. Sharding has to happen in the application.
Reading 650MB as real memory. That is the raw payload; pointer overhead in skip-list nodes and hash entries makes actual usage a multiple of it. Capacity planning off the raw number will bite.
Maintaining exact ranks for the middle of the pack. The most expensive feature is often the least-viewed one. Ask who reads it and what they do with it before building it.
Ignoring ties. A sorted set breaks equal scores by member name, so two players on 500 get different ranks in an order unrelated to who got there first. If the product wants "same score, same rank" or "earliest first," you must encode a timestamp into the score yourself (say, score in the high bits and an inverted timestamp in the low bits) — a step the book leaves out and every implementation trips over.
What the chapter does not cover: cross-continent write latency eating the word "real-time," the traffic spike at a season rollover, rolling back and recomputing cheated scores, and friends-only boards — which are really many small boards rather than one large one, and often closer to what the product actually needs.

Takeaways

① The real lesson is the order of operations: estimate first, architect second. The numbers say five million DAU fits on one Redis instance.

② Keep the arithmetic: 5M DAU ÷ 10^5 s ≈ 50/sec, peak ×5; ten games each → ~500 QPS, ~2,500 at peak; a monthly board is 25M × 26B ≈ 650MB.

③ The hard part is not sorting, it is "where am I" — which a relational database can only answer by counting, at O(n).

④ A sorted set is a hash table (score by member, O(1)) plus a skip list (ordered by score); rank is the sum of pointer spans, turning an O(n) count into an O(log n) addition.

⑤ A rank is global; sharding is localization — the chapter's central tension.

⑥ Redis Cluster hashes keys into 16384 slots, and a board is one key: it will not shard your leaderboard.

⑦ Sharding by player hash destroys ranking; sharding by score bucket preserves it, at the price of hot buckets when the distribution drifts.

⑧ General rule: the shard key must match the query's scope — a field-wide query shards by the dimension being queried.

⑨ Tiering the requirement saves the most: exact for the top ten, cheap for your four neighbours, an approximate percentile for everyone in the middle.

⑩ Two hard lines: no direct client writes (the server adjudicates the score), and an in-memory board is not a ledger — it must be rebuildable from a durable one.