Top K / Leaderboard

What the interviewer is asking

"Design a leaderboard" and "find the top K" are two of the most common counting questions in system design interviews, and they are often asked together. The first is a game's live leaderboard: every player's score, the top 100, and "what's my rank?" for any of 10 million players. The second is a heavy-hitters question: the 10 most-played songs of the last hour, counted from a stream of a billion plays a day.

Both rank things by a number that keeps changing. The interviewer wants you to find the expensive part of each, size it, and pick a structure that makes it cheap. The walkthrough follows the 8 steps of the interview framework: scope, data, API, the busy path, numbers, services, scale and deep dives.

1. Scope: what version 1 must do

• Report scores: game servers send each player's new score after a match.
• The top 100: the board everyone opens.
• My rank: any player's own place; most will never be in the top 100.
• Top songs: the 10 most-played songs of the last hour.

Name the rest and park it: friends-only boards, past seasons and anti-cheat. Worth saying even in version 1: scores come only from game servers, never from the players' apps, which anyone can modify.

2. Data: scores, play events and per-minute counts

The leaderboard is a single mapping, player → score, about 10 million pairs. Don't store ranks: one score change can move thousands of them, so a rank is worked out when someone asks.

The songs board starts from play events on a stream, one per play (song id, time), and keeps counts per song per minute. One running total per song could never forget plays older than an hour; per-minute counts can be added up over exactly the last 60 minutes.

3. The API

POST /scores                 (from a game server)
  {"player": "ana", "score": 1830}
GET /leaderboard/top?n=100   → 100 players, best first
GET /leaderboard/rank/ana    → {"rank": 41207, "score": 1830}
GET /top-songs?window=1h     → 10 songs, most played first

POST /scores carries the player's new total, not the points just won. A game server whose call times out sends it again; if the first call was saved, setting the same total twice changes nothing (the call is idempotent), while "add 50" would count the points twice: 1,880 instead of 1,830. The game keeps each player's points in its own database; the leaderboard only mirrors them.

4. The busy path: the board and your rank

In the simplest design a leaderboard service keeps the scores in a SQL table. Finding Ana's rank:

1. Her app sends GET /leaderboard/rank/ana.
2. The service reads her score: 1,830.
3. It counts the players with a higher score: 41,206.
4. It answers rank 41,207: that count plus 1.

The top 100 is the same for every player; every rank is different. For the songs board, the busy path is at the other end: counting every play as it arrives.

5. The numbers

From the interviewer: 10 million players; at busy hours, 5,000 score updates and 100,000 board reads a second (say 1 million players online, each refreshing about every 10 seconds), 20 reads for every update. The music app has 1 billion plays a day.

• Plays: 1 billion ÷ 100,000 seconds (a day is 86,400, rounded up) = 10,000 a second, about 11,600 with the exact day. Busy hours run about 5× that: 50,000 plays a second.
• Plays in a busy hour: 50,000 × 3,600 = 180 million.
• The leaderboard in memory: 10 million players at about 100 bytes each is about 1 GB.

6. Services: a leaderboard service and counters

Counting plays needs a service of its own, apart from the leaderboard service. Adding 1 to a song's row in a database for every play means 50,000 writes a second; say one database server takes about 5,000, so that's 10× too many. Read replicas don't help (every copy applies every write), and neither does a cache (it saves reads, not writes).

Instead, counter servers read the play stream and count in memory, where adding 1 is nearly free. Every few seconds they write only the top 10 into a top-K cache that GET /top-songs reads.

7. Scale: split the plays, share the top 100

Plays, split by song id. Say one counter handles about 20,000 plays a second: 50,000 at busy hours need 3. The song id picks the stream partition (hash it, mod 3), so every play of a song reaches the same counter and its whole count lives in one place. Round robin, or splitting by listener, would spread every hit song over all 3 counters: no counter would know its real count.

The top 100, kept in memory. 100,000 reads a second for the same top 100 would swamp a database that answers about 5,000. Each leaderboard server keeps the list in its own memory and refreshes it once a second; a list at most a second old is fine for players.

8. Deep dive: a sorted set for ranks

Ranks can't be shared, so 100,000 rank reads a second remain. Without an index, ORDER BY score DESC LIMIT 100 scans all 10 million rows, and so does a rank, SELECT COUNT(*) + 1 FROM scores WHERE score > 1830. An index on score fixes the top 100, now its first 100 entries, but not the rank: a database index keeps no counts, so counting the scores above yours walks them, about 5 million entries for a player halfway down.

The usual answer is an in-memory sorted set, such as Redis's: players kept in score order, together with how many players each step of a search jumps over, so it adds up a rank while it finds the player. Setting a score and finding a rank each take about log n steps, about 23 for 10 million, and the top N is read straight off the front. In Redis these are ZADD, ZREVRANK and ZRANGE with REV. At about 1 GB the set fits in one server's memory; one in-memory server handles about 100,000 simple operations a second, so a replica or two share the rank reads.

A small run, highest first: Ben 300, Cy 200, Ana 120, Dee 90. Eli joins with 250, Fay with 150, and Ana's new total of 280 moves her to second: the top 3 is Ben, Ana, Eli, and Fay is 5th. When Dee's total becomes 260, Fay drops to 6th without her own score changing, which is why ranks are never stored.

9. Deep dive: top K from a stream

A sliding hour. The last hour is the sum of the last 60 per-minute counts, and each new minute pushes the oldest out. A song with 1,200 plays from 10:00 to 10:59, 40 of them in the 10:00 minute, and 70 plays in the 11:00 minute has 1,200 − 40 + 70 = 1,230 for the hour to 11:00. A running total per song, minus the minute that drops out, keeps it ready. A total reset on the hour would empty the board at 11:00, and keeping every play with its time means recounting about 180 million plays for a busy hour.

A min-heap of size K per counter. Every few seconds each counter finds its top K with a min-heap of size K, the pattern of the Kth Largest Element in a Stream coding lesson: the smallest of the K sits on top, and each song only has to beat the top. On a tiny counter with 12 plays of 5 songs and K = 2:

song  plays  heap after it (top first)
A     2      A:2
B     1      B:1 A:2
C     5      A:2 C:5    5 beats 1: B leaves
D     1      A:2 C:5    1 doesn't beat 2: skipped
E     3      E:3 C:5    3 beats 2: A leaves

Each song costs one look at the top, plus about log K steps when it gets in, and the heap never holds more than K songs.

A merger. Each counter sends its own top K to a merger, which keeps the best K of those 3 × K songs. This is exact because each song is counted on one counter only: a song in the true top K has at most K − 1 songs above it anywhere, so at most K − 1 on its own counter, and so it is in that counter's top K. With counter 1 (A to E: C 5, E 3), counter 2 (F to J: G 7, F 6) and counter 3 (K to O: M 4, K 3), the merger picks G and F. Sending only each counter's top 1 would miss F, which shares a counter with G.

10. Deep dive: approximate counts

Some keys never stop coming, like hashtags: new ones every second, most used once, so exact counts grow without end. A Count-Min Sketch keeps a small, fixed table of counters: a few rows, each with its own hash function. Each key adds 1 to one counter per row, and its estimate is the smallest of its counters. Other keys on the same counters only add, so it can over-count but never under-counts; more counters per row shrink the error. A sketch of 4 rows of 1 million counters, 4 bytes each, takes 16 MB however many keys there are, and a min-heap of size K over the estimates keeps the heavy hitters.

Use it where near is good enough: trending songs and hashtags. Don't use it where the exact number matters: a tournament's prize leaderboard (an over-count can put the wrong player first, and 10 million scores fit exactly in about 1 GB anyway) or paying artists for each play.

What breaks first

• A viral song: all its plays go to one counter, but it would need 40% of all busy-hour plays to fill that counter's 20,000 a second. If it happens, split that one song over several counters and add up its parts at the merger.
• A counter crash: its counts lived only in memory; a new counter rebuilds them by replaying the last hour of its partition from the stream.
• Ties: to rank whoever got there first higher, fold the time into the score.
• The sorted set's server: a replica takes over, and the set can be rebuilt from the game's own database of points.

Summary: the order to follow

1. Scope: scores in; the top 100, my rank and the top 10 songs out.
2. Data: player → score; play events and counts per song per minute.
3. API: POST /scores with the new total, so a repeat is harmless.
4. Busy path: reading the board and your rank; counting every play.
5. Numbers: 100,000 board reads and 50,000 plays a second at busy hours.
6. Services: a leaderboard service; counters reading the play stream.
7. Scale: plays split by song id over 3 counters; the top 100 kept in memory.
8. Deep dives: a sorted set for ranks; a sliding hour, a min-heap per counter and a merger; a Count-Min Sketch where near is good enough.

The same pattern answers many "top K" questions: trending hashtags, the most-viewed videos, the busiest API keys. Count where the events arrive, split by the thing you count, keep only the top K, and merge.