Design a real-time leaderboard

In 2 minutes

I would keep each board in an in-memory sorted set, one per period: daily, weekly and all-time. A sorted set pairs a hash map with a skip list, so adding a score, reading the top ten and finding a rank each take O(log n), about 22 steps for 5 million players. In our estimate, all boards fit in under a gigabyte, so one node is enough at the start. A client talks to a gateway that sends writes to a score service and reads to a rank service. The score service validates the score, updates the three sets with one atomic command, and appends the score to a queue, which a writer drains into durable history. If the store is lost, I replay the history to rebuild it. For ties, I fold the earlier time into the score, so equal points go to whoever got there first. For bursts, I coalesce updates per player, batch writes, and cache the top 100 for a second or two. If the board outgrows a node, I shard by score range, so a rank is the count in higher buckets plus the rank in my own, with exact ranks only for the top 1,000.

The question

Clarifying questions

• Does a player's score only go up, or can it fall? A best-score board needs an update only when the new score is higher. A running total just adds to the old one.
• How exact and how fresh must a rank be? An exact rank within a second is easy for thousands of players. For hundreds of millions it needs buckets or an approximation.
• How should ties be broken? Without a rule the order of equal scores is arbitrary and can flip between two page loads.
• How many players, and how many score updates in a burst? The size of the board decides if one machine holds it. The burst decides if writes need buffering.
• Do players see only their own rank, or friends' ranks too? Friends' ranks add a different read pattern: many small lookups for a short list of people.

Requirements

Functional

• Accept a score from a player and update the daily, weekly and all-time boards.
• Return the top 10 for any board.
• Return a player's rank and the few players just above and below them.
• Reset the daily and weekly boards on schedule and keep a record of the final results.

Non-functional

• A score appears on the board within 1 second.
• Top-10 reads: p99 under 50 ms.
• Rank lookup: p99 under 100 ms.
• The board can be rebuilt from stored scores after a crash, so no score is lost.

Back-of-the-envelope estimates

Assumptions for this exercise:

• These numbers are assumptions for the exercise, not facts about any real game.
• 2 million players are active in a day, each submitting about 20 scores a day.
• Each player looks at a board about 10 times a day, and peak traffic is 10 times the average.
• A board entry takes about 64 bytes: a player ID, a score and structure overhead. Boards hold 2 million (daily), 4 million (weekly) and 5 million (all-time) players.

The arithmetic:

• Score updates per second: 2M × 20 = 40M a day ÷ 86,400 s ≈ 463 → ≈ 460/s on average, about 4,600/s at a 10x peak
• Board reads per second: 2M × 10 = 20M a day ÷ 86,400 s ≈ 231 → ≈ 230/s on average, about 2,300/s at a 10x peak
• Memory for all boards: (2M + 4M + 5M) × 64 bytes = 704 million bytes → ≈ 0.7 GB, which fits on one node
• Cost of one rank lookup: log2(5,000,000) ≈ 22 steps in a balanced ordered structure → A few microseconds of work

High-level design

A client talks to an API gateway, which routes score submissions to the Score service and board reads to the Rank service. Splitting them lets the write path be hardened against bursts without touching reads.

The Sorted-set store is the heart of it. It keeps players ordered by score in memory, so adding a score, finding a rank and reading the top ten are all fast. There is one set for each board and period, for example one for today and one for this week.

In-memory data can be lost, so the Score service also appends every score to a Score queue. A History writer drains the queue into Score history, the durable record. If the sorted-set store is lost, we replay the history to rebuild it.

How a request flows

Submit a score

1. The game client sends the player's new score to the API gateway.
2. The gateway routes it to the Score service, which checks the score is plausible for this game.
3. The service updates the daily, weekly and all-time sets, only if the new score beats the old one.
4. It also appends the score to the queue, so the durable history catches up without slowing this request.
5. The Score service replies that the score was accepted.
6. The gateway returns the answer, and the player sees the board update within a second.

Show the top 10 and my rank

1. The client asks for the top 10 and the player's own position.
2. The gateway routes the read to the Rank service.
3. The service reads the first ten entries, then asks for the player's rank and the entries around it.
4. The store answers from memory in microseconds, using its ordered structure.
5. The Rank service attaches display names and builds one response.
6. The client draws the board with the player highlighted.

Save the history

1. Each accepted score was appended to the queue by the Score service.
2. The History writer takes scores from the queue in batches, at its own pace.
3. It writes each batch to the durable history, which is the source of truth for rebuilding boards.

Deep dive: a sorted set, daily keys and ties

A sorted set stores members, here players, each with a score, in score order. It combines a hash map from player to score with a skip list. A skip list is a linked list with extra express lanes above it. Higher lanes jump further, and each jump records how many entries it skips. A search starts in the top lane and drops down, so adding, updating and finding a rank each take O(log n) steps, about 22 for 5 million players. The recorded jump sizes are what let it add up a rank without walking the list. Reading the top ten takes O(log n) to find the start, then 10 steps.

Daily and weekly boards are just different keys. Name them by period, such as a key per date and a key per week. A submission updates all three current keys. At midnight nothing is deleted or reset: new submissions go to a new key, and the old key gets a short TTL after you have saved its final top results. This avoids a slow mass delete at the busiest moment.

Ties. Equal scores come out in an arbitrary order, so two players can swap places between page loads. The fair rule in most games is that whoever reached the score first ranks higher. Fold that into one number. If points stay under a million and the period is a week (604,800 seconds), then:

• composite = points × 1,000,000 + (999,999 − seconds since the period started)

A higher composite wins, and among equal points the earlier time gives the higher composite. This stays far below 2^53, about 9 × 10^15, so a double stores it exactly. To show the real score, divide the composite by a million and drop the fraction.

For a best-score board, ask the store for an update that applies only if the new value is greater. A running total just adds to the old value. Either way, do it as one atomic command, so two quick submissions cannot overwrite each other.

Deep dive: rank at very large scale

One sorted set works up to the memory and write rate of one node. Past that, you shard. There are two ways, and the interview answer is to compare them.

1. Shard by player ID. Each shard holds a share of the players. The top 10 is a merge: ask every shard for its top 10, then take the best 10 of those. A player's rank is a sum: ask every shard how many players score higher, then add. Writes are spread evenly, but every rank read touches every shard.
2. Shard by score range (buckets). Each bucket holds players whose scores fall in one range, say 0 to 999, 1,000 to 1,999 and so on. A player's rank is the number of players in all higher buckets plus their rank inside their own bucket. Per-bucket counts live in a small table that is refreshed every few seconds. Each read touches one bucket plus that table.

Here is a worked example. The buckets above yours hold 4,200,000 players in total, and you are 316th inside your own bucket. Your rank is 4,200,000 + 316 = 4,200,316. The count may lag a few seconds, so that is slightly approximate, and that is fine.

Choose bucket edges from the shape of the data, not equal widths. Scores are usually bunched, so equal widths give some buckets millions of players and others none. Pick edges at percentiles and re-balance them once a day. When a player's score crosses an edge, move them between buckets in one step.

Most players do not need exactness. Show exact ranks for the top 1,000, where people care about every place, and a percentile for everyone else: 'top 12%'. A cheap histogram of scores answers that without reading the board at all.

Deep dive: surviving write bursts

Bursts come at the end of a round or a season, which is exactly when people watch the board most. Protect the store in layers.

• Coalesce. A player who submits ten scores in a few seconds only needs their best one on a best-score board. The Score service can hold updates for a very short window per player and write only the highest.
• Batch. Send many updates to the store in one round trip, using pipelining. Round trips, not the work itself, are the cost at this volume.
• Buffer. If writes must be accepted faster than the store takes them, put them in a queue and let the board lag by a few seconds. Players mostly cannot tell the difference between 1 and 3 seconds.
• Limit per player. Cap submissions per player per second. It stops one buggy client or one cheater from flooding the system.

Reads need relief too. The top 100 is identical for every viewer, so build it once and cache it for one or two seconds. Thousands of readers then share a single store call. A player's own rank is personal and is not cached, but it is only one cheap lookup.

Keep the durable history as the source of truth. The sorted set is a fast index that can be rebuilt. Replaying a day of scores, at about 40 million records in our estimate, takes minutes in batches, not hours. Test the replay before you need it. While it runs, serve the last cached top 100 and tell clients that ranks are updating.

If a single board still becomes a hot key, split it. Keep a sorted set per bucket, as in the rank design above, so that burst writes land on different nodes.

Trade-offs

• Ranking structure: An in-memory sorted set over A SQL table with ORDER BY and a COUNT for rank. Rank and top-k take a few dozen steps instead of scanning rows. The cost is that memory is not durable, so you also keep a history to rebuild from.
• Tie-break rule: Fold the earlier time into the score over Leave ties in arbitrary order. The board is stable and fair in the way players expect. The cost is a slightly more complex score and care about number precision.
• Board freshness: Update at once, and cache the top 100 for 1 to 2 seconds over Rebuild the boards every minute. Players see progress almost immediately and readers share one cached page. The cost is a little staleness at the top.
• Rank for huge boards: Exact for the top 1,000, approximate beyond over Exact everywhere. It is cheap and matches what players care about. The cost is that mid-table ranks can be off by a few places for a few seconds.

Common follow-up questions

How do you reset the daily board at midnight?
You do not reset it. Write to a new key named for the new date, and save the final top results of the old one. Give the old key a TTL so memory is freed later and slowly. To follow each player's local day instead, put the time zone in the key name.

How would you show a player's friends on the board?
Fetch each friend's score in one pipelined call, then sort the list in the service. That works well for a few hundred friends. For very large friend lists, keep a small sorted set per player that is updated when a friend scores.

How do you deal with cheaters?
Do not trust the client. Let the game server compute or sign the score, check it against sane limits, and flag outliers for review. To remove a cheater, delete the member from every board and add a record to the history, so a rebuild does not bring them back.

What happens if the sorted-set store crashes?
A replica takes over, and it may be a few updates behind. If the whole store is lost, replay the score history to rebuild it. During the rebuild, serve the last cached top 100 and mark ranks as updating.