Leaderboard - a sorted set and the rank nobody stores

Why this design

A leaderboard looks like a SELECT ... ORDER BY score DESC LIMIT 10, and for a few thousand players it is. It stops being one when two questions have to be answered for millions of players at once: who is in the top ten, and what is MY rank. The first is easy with an index. The second is the trap - "count everyone above me" over a B-tree is a scan, and storing rank in a column means one good game rewrites most of the table. The answer is a structure that keeps members in order AND knows how many sit between any two points: a sorted set.

What you will learn

• Why rank is computed at read time, never stored, and the one exception (a frozen season).
• How a sorted set (skip list + hash) gives O(log N) insert, O(log N) rank and O(log N + 10) top ten.
• That 50M players is about 5 GB in a sorted set and 100M updates a day is ~1,200/s - one Redis node handles both.
• Why the sorted set is an index you can rebuild, not the source of truth, and what that costs on failover.
• How ties are broken by packing time into the score, and where that trick runs out.

How to read this board

1. Top: SCORE PATH. A player finishes a match, the game server reports it, the score service records it durably and publishes an event.
2. Right: STORES. The score store (truth) and the red sorted set (the index that answers ranks).
3. Bottom: READ PATH. A player opens the board; the leaderboard API asks the sorted set and decorates ten ids with names.
4. Bottom right: JOBS. The rebuild job and the season snapshot - the two things that exist because the sorted set can be lost.
5. Press play for the walkthrough, then read pages 1 to 6, then the tables at the bottom.
6. The conversation to have is the red box: one key, one shard. Page 5 says what you would do when one node is no longer enough.

Functional

• Submit a score at the end of a match. A player's board score is their BEST score this season (or a running total - pick one; this board uses best).
• Show the top 10 (and top 100) for the global board.
• Show my rank and score, and the 5 players directly above and below me ("around me").
• Boards per season. A season ends, its final ranks are frozen and prizes are paid from that snapshot.
• Display names and avatars beside each entry.

Non-functional

• Top ten and my rank: p99 under 50 ms. My rank appears on the end-of-match screen, so it is on the critical path of every game.
• A new score is visible on the board within 1 to 2 seconds.
• Scores are durable: an accepted match result is never lost. The ranking index may be rebuilt.
• Ranks are exact for the top 10,000. Below that, "top 12%" is an acceptable answer if exact becomes expensive.
• Score submission is authoritative from the game server, never the client, or the top ten fills with cheaters.

Out of scope

• Friends-only boards (a small per-user sorted set, or a sort at read time over a few hundred friends).
• Anti-cheat beyond "only the game server may submit".
• Per-region boards - the same design with one key per region.

Assumptions

Players on the all-time board          50,000,000
Daily active players                   10,000,000
Matches per player per day                     10
Board opens per player per day                  3
Peak factor                                    x5

Writes

Score submissions   10M x 10    = 100,000,000 / day
                    / 86,400    =       1,160 /s average
                    x 5         =      ~5,800 /s peak

Reads

My rank on the results screen   = 1 per match
                                =   1,160 /s avg, 5,800 /s peak
Board opens  10M x 3 = 30M/day  =     350 /s avg, 1,750 /s peak
  each = ZREVRANGE 0 9 + ZREVRANK + around-me range
Total sorted-set commands at peak    ~ 5,800 + 1,750 x 3
                                     ~ 11,000 /s

A single Redis node does well over 100,000 simple commands a second, and these are O(log N) with log2(50M) ≈ 26 levels. So the sorted set is not a throughput problem today - it is a single-node problem: there is exactly one of it. Throughput would become the problem at roughly 10x this traffic.

Why not SQL

SELECT count(*) FROM best_scores WHERE score > :mine
  rank 25,000,000 = scan 25M index entries
  ~ seconds per query, x 5,800 /s  = impossible

A B-tree finds a score fast but does not know how many entries sit before it. A skip list in a sorted set stores the span of every link, so it counts while it walks.

The sorted set

member  player id, 16 B
score   8 B double
skip list node + hash entry + pointers ~ 70 B
                         ~ 100 B per member
50M members x 100 B    =  ~5 GB
one key per season, keep current + previous = ~10 GB

Ten gigabytes fits in memory on one node with room to spare, which is why the board can draw one. It is also why it is tempting never to split it.

The score store (truth)

score_events row   ~ 80 B   (player, season, points, time)
100M / day x 80 B  =   8 GB / day
keep 90 days       = 720 GB, then roll up or archive

best_scores row    ~ 60 B
50M players        =   3 GB per season

Tie-breaking inside one double

score = points x 2^32 + (2^32 - 1 - seconds_since_season_start)
  earlier achiever ranks higher at equal points
  a double is exact to 2^53, so points must stay under 2^21
  = 2,097,152 points - check the game can never exceed it

Redis orders equal scores by member name, which is arbitrary. Packing time into the low bits makes ties deterministic and fair, at the cost of a hard ceiling on the score.

Targets

• Score submission: 99.95 percent. A lost result is a support ticket.
• Rank reads: 99.9 percent, degrading to "rank unavailable" rather than a wrong number.

What fails, and what it costs

• The sorted set node (red). Replicated to a standby asynchronously. On failover the standby may be missing the last second of ZADDs - those players see their old best. The fix is that the score service never relied on Redis for durability: the rebuild job replays score events from the last checkpoint and the board heals in seconds to minutes.
• Losing the sorted set entirely. Rebuild from best_scores: read 50M rows, ZADD in batches of 1,000 - about 50,000 pipelined batches, a few minutes. During that window serve the top ten from a cached copy and hide "my rank".
• The score store. The durable part; a primary with a synchronous standby. If it is down, submissions are queued at the game server and retried - the match result is held, not dropped.
• The event log. If the rank updater lags, the board is stale, not wrong. Alert on consumer lag above 5 seconds.

Degrade, do not lie

A rank that is stale by two seconds is fine. A rank that is wrong after a failover and stays wrong is not. That is why the updater writes with ZADD GT (only raise a score), which makes replaying the same events twice harmless.

Score path

The match ends on the game server, which is the only thing allowed to report a score. The score service inserts the result into score_events, upserts best_scores if it beat the old best, and publishes a score event. The rank updater consumes events and runs ZADD season:42 GT <packed score> <player>. GT means the stored score only ever goes up, so a replayed or out-of-order event cannot lower anyone.

Read path

• Top ten: ZREVRANGE season:42 0 9 WITHSCORES - O(log N + 10).
• My rank: ZREVRANK season:42 <player> - O(log N); add 1 for a human rank.
• Around me: ZREVRANGE season:42 rank-5 rank+5.
• Then one multi-get of ten display names from the profile cache. The sorted set holds ids only, so a rename never touches it.

Why rank is never stored

Rank is a function of everyone else. If player A jumps from 900,000th to 10th, every player from 10th to 899,999th drops by one. A rank column turns one score update into up to N row updates; a sorted set turns it into one O(log N) insert and computes rank on the way down the skip list. The one time a rank IS written is when it stops changing: the season snapshot copies the final order into season_final_ranks so prizes are paid from a fixed list.

When one node is not enough

• Read replicas for ZREVRANGE / ZREVRANK - easy, slightly stale.
• Split by score range (shard 1 holds scores above X ...). My rank = my rank in my shard + the sizes (ZCARD) of all higher shards. Exact, but boundaries must move as scores grow.
• Exact rank for the top 10,000, and a percentile from a histogram of score buckets for everyone else. Most games do this.

Topology

• Score service and leaderboard API: stateless, several replicas behind a load balancer, one region near the game servers.
• Redis: one primary per season key with one replica in another zone, persistence on (AOF every second) to shorten rebuilds.
• Postgres: primary with a synchronous standby for score_events and best_scores.
• Event log: a partitioned log (Kafka or similar) keyed by player id, so one player's events stay in order.

Rollout

• Build the new season key before the season starts; flip the API to it by config at the season boundary.
• Change the score packing only with a new key, never in place - old and new scores do not compare.
• Canary the rank updater by running it into a shadow key and diffing the top 1,000 against the live key.

What to watch

Redis CPU (it is one thread), command latency p99, memory of the season key, rank updater consumer lag, and the count gap between ZCARD season:42 and the row count of best_scores for that season - if they drift apart, the index is missing players.