A Leaderboard for ChessHop

In this chapter, we design one system the way a system design interview goes. An interview usually goes in this order:

  1. The interviewer states the problem in one line.
  2. You ask clarifying questions.
  3. You agree on the functional requirements and the quality attributes.
  4. You estimate the load.
  5. You design the API, the parts of the system, and the data. At each step, you consider alternatives and choose one.
  6. You look at scaling and failures.

Our problem is this one: “Design a leaderboard for ChessHop.”

A leaderboard lists the participants of something, each with their rank, ordered by a score.

ChessHop

ChessHop is a made-up online chess site, like Chess.com or Lichess. Players play rated games in three time controls: bullet, blitz, and rapid. A time control sets how much time each player has for the game. Bullet games are the shortest, and rapid games are the longest.

Each player has a rating in each time control. A rating goes up after a win and down after a loss. So one game changes two players’ ratings.

What exists

ChessHop is already split into two services behind a gateway.

graph TD
    C[Clients: website, apps] --> G[Gateway]
    G --> PS[Player service]
    G -.->|WebSocket| GS[Game service]
    PS --> PDB[(Player database: sharded by player)]
    GS --> PDB
  • The player service handles accounts, profiles, and game history, over a REST API. It runs as several instances.
  • The game service runs live games over WebSockets. During a game, both players send moves, and the game service sends each move to the other player. So the communication goes both ways, and it happens often. When a game ends, the game service computes both players’ new ratings and saves them. It also runs as several instances.
  • The player database holds the accounts, each player’s rating in each time control, and the games. Both services use it. It is sharded by player with consistent hashing, and each shard has replicas.

In an interview, the interviewer gives you a diagram like this one, or you ask for it. Every part of it is something we have covered: services behind a gateway, WebSockets, sharding, consistent hashing, and replicas.

Why shard by player

Recall how we chose a shard key for Shopend, the hosted shop platform. We chose the shop as the shard key, because almost every operation is about one shop. With the shop as the shard key, the data each operation needs is on one shard.

The same reasoning applies to ChessHop. Almost every request is about one player: a profile, a player’s game history, or a player’s ratings. With the player as the shard key, all of one player’s rows are on one shard, so each of those requests goes to one shard.

A game has two players, so it does not belong to one player. I keep a copy of each game on each player’s shard. Then each player’s game history is on one shard.

Let’s consider the other shard keys we could use:

  • By rating. A rating changes after every game, so the player’s row would move to another shard whenever the rating crosses a shard’s range. A shard key should not change. Also, the shard with the highest ratings would get every request for the first pages of the leaderboard.
  • By time control. There are only three time controls, so there could be at most three shards. I assume blitz is the most played time control, so its shard would get most of the load.
  • By game. A player’s game history would be spread over every shard.

So the player is the right shard key for ChessHop. The cost is that a query that compares players has to go across shards. A leaderboard compares every player with every other player, so it needs a query across all the shards.