A leaderboard looks like a single SQL query: ORDER BY score DESC LIMIT 100. For a hundred players, it is. For 50 million players whose scores change every few seconds, and who each want to know "what's my rank?", that query falls over badly. The fix turns out to be one well-chosen data structure, and most of this lab is about understanding why it works and where it stops working.
You'll design it from a blank page. Decide each step yourself before reading on.
The brief
You're building the ranking system for a popular mobile game. Players finish matches and earn points. The game shows:
- The global top 100 for the current season.
- Your own rank, like "#1,284,519", and the players just above and below you.
- Weekly boards that reset every Monday.
- A friends board: where you stand among people you follow.
Who uses it?
- Game servers, which report match results.
- Players, who open the leaderboard screen after nearly every match.
In scope: score updates, global and weekly boards, top N, my rank, players around me, friends boards, and ties.
Out of scope: anti-cheat (a separate system decides if a score is valid before it reaches you), matchmaking, rewards at season end, and the social graph itself.
Requirements
Functional
- Record a player's new season score after each match.
- Return the top N players with scores.
- Return any player's exact rank and score.
- Return the 5 players above and below a given player.
- Keep separate all-time-season and weekly boards.
- Rank a player among their friends.
Non-functional
- Fresh: a new score shows up in ranks within about a second.
- Fast: rank and top-100 reads under 50 ms at the server.
- Exact rank for the top players. For a player at #1,284,519, a rank that's off by a few is acceptable for a moment, but it should settle to exact.
- Durable: scores are never lost. The board itself can be rebuilt.
- Fair ties: equal scores are ordered by a clear rule, the same way every time.