CSE Roadmap

Common tier · about 4 hours · 8 parts

Part 2 of 8 · 2 min read

Scope and numbers

Small data, hard question.

Think of a scoreboard at a sports ground. Points change all the time, and every spectator wants to see who leads and where their own team stands. The board must stay right at every moment.

Questions and the answers assumed here (from the book's sample talk).

  1. How is the score earned? One point for each match a player wins.
  2. Time segments? A new tournament starts each month, with a new leaderboard.
  3. What is shown? The top 10 players and the rank of one chosen player. Bonus: the four players above and below that player.
  4. Scale? 5 million daily active users and 25 million monthly active users. Each plays about 10 matches a day.
  5. Ties? Equal scores share a rank. Tie-breaking is a bonus.
  6. Real time? Yes. A batch result a few hours old is not acceptable.

Requirements.

  • R1. Show the top 10.
  • R2. Show a player's rank.
  • R3. Optional: show neighbours.
  • R4. Score updates appear in real time.
  • R5. Scalable, available and reliable.

Numbers (from the book).

  • Players: 5,000,000 a day / 100,000 seconds is about 50 per second (the exact figure, with 86,400 seconds, is 58). Peak at 5 times is about 250.
  • Score updates: 50 × 10 matches = about 500 per second, with a peak of 2,500.
  • Top-10 reads: each player opens the game once a day, so about 50 per second.
  • Memory: an id of 24 characters plus a 2-byte score is 26 bytes. For 25 million players, 26 × 25,000,000 = 650 MB. Even doubled for overhead, it fits on one modern server.

These loads are small. One well-chosen store handles them. The hard part is the rank query, not the volume.

Leaderboard

A leaderboard is a list of players ordered by score, with the highest first.

Example: mary1934 with 120 points is rank 1, and bob_7 with 119 points is rank 2.

Check yourself: 1. Why is a tournament reset each month useful for sizing? 2. What is the peak update rate? 3. How much memory does the worst case need?