Gaming Leaderboard

Real-time Rankings

Design a leaderboard that ranks up to 100 million players of a game, shows the top of the board and each player's own rank within a second of a match ending, and keeps daily, weekly and all-time boards.

Overview

A leaderboard ranks players by score. When a match ends, the player's score goes in, and the player expects to see the new rank at once: the top 100, where they stand overall, and who is just above them.

The top of the board is easy; any database can sort and return 100 rows. The hard question is the rank of an ordinary player in the middle of 100 million. A B-tree index keeps scores in order, but it does not know how many entries sit above a given score, so the database has to count them one by one. The standard answer is an in-memory sorted set: a structure that keeps a count at every step of its index, so the rank of any member costs O(log N) steps: a few dozen for 100 million players instead of millions.

Interviewers use this problem to see whether you know why the naive query fails, which data structure fixes it, and what you do about the details that break real leaderboards: two players with the same score, a match reported twice, weekly resets, and a board too large for one machine.

Questions to ask first

How many players, how active? — 100 million on the all-time board; 20 million play each day, 12 matches each
What is the score? — The best single-match score, a whole number under about 2 million
Which boards? — Daily, weekly, season and all-time, per game
How fresh must ranks be? — A player sees their new rank within a second of the match ending
Who reports scores? — Our game servers, never the game client
Exact rank for everyone? — Exact for all players; approximate is acceptable only if the board outgrows one machine
Ties? — Equal scores: whoever reached the score first ranks higher

What you will be able to do

Explain why a SQL rank query slows down as the board grows and how a sorted set answers it in O(log N).
Write scores so that retries, late reports and lower scores cannot corrupt the board.
Break ties by time inside one sorted-set score without losing precision.
Run daily, weekly and season boards with keys, expiry and snapshots.
Scale past one Redis node and recover when the in-memory copy is lost.

Key concepts

Sorted sets
Skip list rank
ZADD GT
Idempotent score writes
Composite tie-break score
Time-window keys
Scatter-gather rank
Approximate rank
Rebuild from the source of truth

Functional requirements

Record a player's score when a match ends; keep each player's best score per board
Return the top N players of a board (N up to 100)
Return a player's rank, score and percentile on a board
Return the players just above and below a player
Return a leaderboard of a player's friends
Keep daily, weekly, season and all-time boards; start each new period empty
Keep the top 1,000 of every finished period for history

Non-functional requirements

A new score shows in ranks within 1 second (a target we chose)
Rank and top-N reads answer in under 50 ms at p99 (a target we chose)
A match reported twice counts once
No score is lost for good: the board can be rebuilt from durable storage
Only game servers can submit scores

Interview questions

Why not just use SQL with an index on score?
How do you break ties?
ZADD or ZINCRBY?
How do daily and weekly boards reset?
How would you show a friends leaderboard?
The game grows to a billion players. What changes?
What happens if Redis loses data?
How do you stop cheating from wrecking the board?