System Design HLD-19.19
Design a real-time leaderboard
Design a real-time leaderboard: Redis sorted sets for updates, top N and rank, ties, sharding very large boards, and approximate rank for the long tail.
The problem
A mobile game shows a leaderboard: the top 10 players worldwide, and below it, "You are #48,213". Scores change constantly as people play, and both the top of the board and your own rank should update within a second or two.
The two questions sound easy. In a relational database, the top 10 is ORDER BY score DESC LIMIT 10, which an index handles well. But "what is my rank?" is SELECT COUNT(*) WHERE score > mine, which counts up to millions of rows, for every player, every time they look. The design is about a data structure that answers both questions in logarithmic time, and what to do when one machine is not enough.
Requirements
Functional
- Update a player's score after each match (set or increment).
- Show the top N players with scores.
- Show a player's own rank and the players just above and below.
- Separate boards: daily, weekly, all-time; per region.
Non-functional
- Scale: 50 million daily players; 300 million players on the all-time board.
- Freshness: updates visible within about a second.
- Latency: board and rank queries in a few milliseconds at the server.
- Durability: scores must not be lost; the board can be rebuilt from them.
Out of scope
- Anti-cheat validation of scores (a hook before the update), and friends-only leaderboards (an extension).
Estimates
- Updates: 50M players x 10 matches a day = 500 million updates a day, about 5,800 per second on average and roughly 17,000 at a 3x peak.
- Reads: if players open the board 5 times a day, 250 million reads a day, about 2,900 per second, mostly for the top N, which is the same for everyone and can be cached for a second.
- Memory: assume about 100 bytes per player in a sorted set (id, score and index overhead). A daily board of 50M players is about 5 GB; the all-time board of 300M is about 30 GB.
- Both fit in memory, and tens of thousands of operations a second is within reach of one in-memory node. So one node per board works for a long time; sharding is for the very largest boards or for headroom.
API
POST /v1/boards/{board}/scores { player_id, delta: 120 } -> { score, rank }
GET /v1/boards/{board}/top?n=10 -> [{ rank, player_id, score }]
GET /v1/boards/{board}/players/{player_id}?around=2 -> { rank, score, neighbours: [...] }
Board names carry the period: daily:2026-10-04, weekly:2026-W40, alltime.
Data model
- Score store (durable, a database partitioned by player):
board, player_id, score, updated_at. The source of truth. - Sorted set per board (in memory): member
player_id, scorescore. Redis sorted sets keep members ordered by score using a skip list together with a hash map from member to score, so updates, rank lookups and range reads are all logarithmic ( Distributed caches: Redis and Memcached ). - Top-N cache: the current top 100 per board, refreshed every second.
ZINCRBY daily:2026-10-04 120 player:42 # O(log N) update
ZREVRANGE daily:2026-10-04 0 9 WITHSCORES # top 10, O(log N + 10)
ZREVRANK daily:2026-10-04 player:42 # rank, O(log N)
High-level design
- Update path A game server reports a result. The score service validates it, writes the new score to the durable store, and increments the player's score in the board's sorted set, which re-positions the player in logarithmic time.
- Read path The top N comes from a cache refreshed every second from the sorted set, since it is the same for everyone. A player's rank and neighbours are read from the sorted set directly.
- Rebuild path If the in-memory node fails, a replica takes over; if all copies are lost, a new board is loaded from the durable score store. Old periodic boards are archived to the store and deleted from memory.
Deep dives
Deep dive 1: Why a sorted set
A sorted set is a skip list: a sorted linked list with extra "express lanes" that let a search skip ahead, giving logarithmic search, insert and delete. Each node also counts how many elements its links skip, so the structure can compute a rank while it searches, without counting everything above. Paired with a hash map from member to score, a score change is "find the old position, remove, insert at the new one", all logarithmic.
For 50 million players, log2 of 50 million is about 26, so an update or rank query touches a few dozen nodes instead of scanning millions of rows. The same idea works with a balanced tree that stores subtree sizes; the sorted set just packages it.
Ties: two players with the same score need a stable order, usually "whoever got there first ranks higher". Encode it into the score: score x 2^22 + (2^22 - 1 - seconds since the period started), as long as the combined number stays below 2^53 so a double holds it exactly. A weekly board has about 605,000 seconds, which fits in 2^20, so 2^22 leaves room.
Deep dive 2: Periods and resets
Daily and weekly boards are separate keys (daily:2026-10-04). Each update writes to all of the player's current boards. A new period simply starts a new key, so there is no "reset" job at midnight; old keys get an expiry after they are archived. Time zones matter: a global daily board needs one definition of "day", usually UTC.
Deep dive 3: Sharding very large boards
When a board outgrows a node, or updates outgrow one node's throughput, split it:
- By player id hash: updates spread evenly. The global top 10 is the merge of each shard's top 10 (exact, since the global top 10 must be within the shards' top 10s). A player's rank is the sum over shards of "players above my score", which is a scatter-gather to every shard.
- By score range: shard 1 holds scores 0 to 999, shard 2 holds 1,000 to 4,999, and so on. Rank is "everyone in higher shards (a stored count) plus my rank in my shard", so one shard answers. But players move between shards as scores grow, and the top shard gets hot as everyone competes there ( Hot partitions and the celebrity problem ), so boundaries must be rebalanced.
Often the simplest answer is to avoid one giant board: per-region, per-league or per-tier boards are smaller, and players find them more motivating than "#48,213,977".
Deep dive 4: Approximate rank for the long tail
Nobody needs to know they are exactly 179,463rd rather than 170,911th. Precise rank matters near the top. So keep the top few thousand exactly, and for everyone else keep a histogram of scores: count of players per score bucket. A rank is then "players in higher buckets, plus a fraction of my bucket".
# Exact rank needs the whole sorted set; approximate rank needs only a
# histogram of scores. 200,000 players with a long-tailed score spread.
import bisect, random
rnd = random.Random(11)
scores = [int(rnd.paretovariate(1.6) * 100) for _ in range(200_000)]
ordered = sorted(scores)
N = len(ordered)
def exact_rank(s): # 1 = best: players strictly above, plus 1
return N - bisect.bisect_right(ordered, s) + 1
# histogram: 200 buckets of equal width up to the 99.9th percentile,
# everything above kept exactly (the top of the board matters most)
cut = ordered[int(N * 0.999)]
WIDTH = cut / 200
counts = [0] * 200
top = []
for s in scores:
if s >= cut:
top.append(s)
else:
counts[int(s // WIDTH)] += 1
top.sort()
def approx_rank(s):
if s >= cut:
return len(top) - bisect.bisect_right(top, s) + 1
b = int(s // WIDTH)
above = len(top) + sum(counts[b + 1:])
frac = (s - b * WIDTH) / WIDTH # assume evenly spread inside bucket
return above + round(counts[b] * (1 - frac)) + 1
print(f"{N:,} players; histogram of 200 buckets plus {len(top)} top scores")
for pct in (0.9995, 0.99, 0.9, 0.5, 0.1):
s = ordered[int(N * pct)]
e, a = exact_rank(s), approx_rank(s)
print(f"score {s:5}: exact rank {e:7,} approx {a:7,} "
f"error {abs(a - e) / e:6.2%}")Output
200,000 players; histogram of 200 buckets plus 200 top scores
score 11797: exact rank 100 approx 100 error 0.00%
score 1748: exact rank 2,000 approx 2,001 error 0.05%
score 422: exact rank 19,970 approx 20,010 error 0.20%
score 154: exact rank 99,208 approx 100,380 error 1.18%
score 106: exact rank 179,463 approx 170,911 error 4.77% The top 200 are exact, so rank 100 is exact. At rank 2,000 the estimate is off by one, at rank 20,000 by 0.2 percent, and only in the crowded bottom of the board, where thousands of players share a few scores, does it drift by a few percent. The histogram is 200 counters instead of 200,000 entries, it shards trivially (add the shards' histograms), and it is updated with one increment per score change. Display far-down ranks as "top 15 percent" and nobody will notice.
Try it
Try this:
- Sort all six, then Check.
- A board is sharded by player hash into 8 shards. How many shards does "top 10" touch? And "my rank"?
- Why is the global top 100 exactly the merge of each shard's top 100, and never something outside them?
Bottlenecks and failure modes
| Failure | Impact | Mitigation |
|---|---|---|
| In-memory node lost | Board unavailable | Replica failover; rebuild from the durable score store |
| Top-N read on every request | Needless load | Cache top N for a second; it is the same for everyone |
| One giant board | Memory and write limits | Shard by player hash, or split by region or league |
| Score-range shards | Hot top shard | Rebalance boundaries; prefer hash sharding with merge |
| Ties ordered randomly | Ranks flicker | Encode time into the score as a tie-breaker |
| Cheating | Bogus scores at the top | Validate on the game server; review top entries |
Trade-offs we made
| Option | Wins when | Loses when |
|---|---|---|
| In-memory sorted set (chosen) | Logarithmic update, top N and rank | Memory-bound; needs a durable source to rebuild |
| SQL ORDER BY with an index | Durable and simple for top N | Rank queries count many rows |
| Hash sharding with merge (chosen at scale) | Even load; exact top N | Rank requires asking every shard |
| Approximate rank for the tail (chosen) | Constant time, tiny, shards trivially | Off by a few percent far from the top |
Extensions
- Friends leaderboards: fetch friends' scores and sort the small list at read time.
- Around me: neighbours by rank with
ZREVRANGEaround the player's rank. - Seasons and rewards paid out from an archived, frozen board.
- Live updates pushed over WebSockets for players watching the board.
In the wild
Where you will see this: game leaderboards, fitness and coding challenge rankings, sales dashboards, and any "top N" list that changes in real time. The common recipe is an in-memory sorted structure for speed, a durable store for truth, smaller boards rather than one giant one, and approximate ranks wherever exactness does not matter.
Check yourself
-
Why is 'what is my rank?' slow in a plain SQL table?
Show answer
B. It counts all rows with a higher score, which can be millions Counting is linear in the number of players above you; a sorted set computes rank while it searches.
-
How is a tie between two players broken stably?
Show answer
B. Encode the time of the score into the sorted value so the earlier player ranks higher A combined score keeps one sorted set and a deterministic order.
-
With 8 hash shards, how do you get the exact global top 10?
Show answer
B. Merge the top 10 from each shard Any global top-10 player is in their own shard's top 10.
-
When is approximate rank acceptable?
Show answer
B. Far from the top, where 'top 15 percent' tells the player what they need Exactness matters near the top; elsewhere a histogram is cheap and good enough.
Recap
- A sorted set (skip list plus hash map) gives logarithmic updates, top N and rank.
- Keep scores durable elsewhere so the in-memory board can be rebuilt.
- Cache the top N for a second; break ties by encoding time into the score.
- Use a key per period instead of reset jobs; split giant boards by region, league or player hash.
- Approximate rank with a histogram for players far from the top.
Next up
- Crack the system design round learning path