A Leaderboard

In this chapter, we design a leaderboard for an online chess site the way a system design interview goes, and we apply what the course has covered so far to each decision.

After reading this chapter, you should be able to:

  • Follow the steps of a system design interview, from clarifying questions to scaling and failures
  • Explain why a player’s rank is too slow to compute from a sharded relational database
  • Explain why caching, denormalization, a materialized view, and read replicas do not make a rank cheap
  • Explain how a balanced search tree augmented with subtree sizes finds a rank in logarithmic time
  • Use a Redis sorted set to set a score, get a rank, and get a range of ranks, with ties broken by time
  • Justify a service of its own for the leaderboard, with its own copy of the data
  • Compare a message, a direct call, and polling a database for getting new ratings to the leaderboard
  • Choose a delivery guarantee, and handle messages that arrive twice or out of order
  • Explain how the leaderboard recovers when its data is lost
  • Agree on what real time means, and use polling with HTTP caching for open pages

Sections

  1. A Leaderboard for ChessHop
  2. Requirements
  3. Load Assumptions
  4. The API
  5. Where the Leaderboard Runs
  6. Ranking from the Player Database
  7. Making the Rank Cheaper
  8. Keeping Players in Order
  9. Sorted Sets in Redis
  10. Ties
  11. The Leaderboard’s Data
  12. Getting the New Ratings
  13. Handling the Messages
  14. Usernames
  15. Losing the Leaderboard’s Data
  16. Real-Time Updates
  17. Putting It Together