Concepts / Storage and data / Sorted sets and leaderboards

Sorted sets and leaderboards

Keeping millions of scores ordered with O(log n) updates.

System design conceptStorage and data1 Nov 2026

01The intuition

The problem it solves

A school sports day keeps a leaderboard on a whiteboard: names sorted by points. Every time a runner finishes, someone rubs out a line, moves everyone below it down and writes the new entry. With 30 runners it is fine. With 3 million players in an online game scoring every few seconds, rewriting a sorted list for every score is millions of moves a second, and "what is my rank?" means counting everyone above me.

A sorted set is a structure that keeps items ordered by a score and lets you insert, update, find a rank and read a range, each in O(log n) time. It is the whiteboard that does not need rewriting.

Build it one piece at a time

Step 1: a sorted array, and why it fails. Keep (score, player) pairs sorted. Finding a rank is a binary search, O(log n). Inserting means shifting everything after the position, O(n). For 3 million players and 100,000 score updates a second, that is 1011 moves a second. Not possible.

Step 2: a balanced tree, or a skip list. A balanced binary search tree (or a skip list, which is simpler to build and what Redis uses) keeps order with O(log n) insert and delete. A skip list is a sorted linked list with express lanes: level 1 links every node, level 2 every second node, level 3 every fourth, and so on, so a search skips ahead like an express train and drops to local lanes near the target.

OperationSorted arraySkip list / balanced tree
update a scoreO(n)O(log n): remove, re-insert
rank of a playerO(log n)O(log n) if each node stores the count of nodes it skips
top 10O(1)O(10): walk from the head
players ranked 1,000–1,050O(1) sliceO(log n + 50)

Step 3: add a hash map beside it. To update Rao's score you must find Rao's node. A hash map from player to node makes that O(1); the sorted structure then handles the reordering. A sorted set is exactly this pair: map plus skip list.

Step 4: store the rank counts. Each express-lane link records how many base nodes it jumps over. Rank is then computed on the way down by summing the jumps, O(log n), and "the 1,000th player" is found by the same sums in reverse.

Step 5: go beyond one machine. Three million entries at about 100 bytes each is 300 MB, which fits one machine's memory with room to spare, and a single node handles about 100,000 sorted-set operations a second. For a global game with 100 million players, shard by score range (the top band is small and hot; replicate it), or keep one sorted set per league or region and merge only for the global top 100.

Why it works, with the numbers

Logarithms are small. For 3 million players:

log2(3,000,000) ≈ 22, so an update touches about 22 nodes instead of shifting up to 3 million entries

At 100,000 updates a second that is 2.2 million node operations a second, comfortable for one core. The guarantee is that after every update the set is exactly sorted and every rank is exact. The failure modes are the hash map and the list getting out of step (the two updates must be one atomic operation), a tie rule that is not deterministic (two players on 500 points must be ordered by something stable, like who reached it first), and a single hot set that one machine cannot keep up with, which the sharding in step 5 addresses.

The trade-off you must say out loud

Exact ranks in memory on one machine, or approximate ranks (bucketed scores, periodic snapshots) across many. Say which the product needs: a player's exact position among a billion is rarely worth the cost, while the exact top 100 always is. The interviewer may ask about a weekly leaderboard; the answer is a sorted set per week keyed by week number, expired when the week is old.

Where it shows up in the 100 Google problems

02Used in these problems