Ranking from the Player Database

The ratings are already in the player database. So the first design to try is to answer both endpoints from it. We assume ChessHop uses a relational database. It has these tables, among others:

• players (id, username, email, created_at, …)
• ratings (player_id, time_control, rating, reached_at), with the primary key (player_id, time_control)
• games (id, time_control, white_id, black_id, result, ended_at, …)

Every table is sharded by player. Here are player 5512’s rows in ratings:

reached_at is when the player reached that rating. It changes every time the rating changes.

A page

Let’s answer GET /leaderboards/blitz?page=3. Page 3 is ranks 101 to 150.

The players are spread over the shards by player ID, not by rating. So the 150 highest blitz ratings could be on any shard. Each shard has to return its own 150 highest blitz ratings. Fewer is not enough. Suppose each shard returned only 50, and one shard happened to hold all of ranks 1 to 150. Then ranks 51 to 150 would be missing.

On each shard, an index on (time_control, rating) keeps the blitz ratings in order. So a shard reads its 150 highest from the start of the index, without sorting. Here is the query each shard runs:

SELECT player_id, rating
FROM ratings
WHERE time_control = 'blitz'
ORDER BY rating DESC
LIMIT 150;

The leaderboard service merges the lists from all the shards and keeps ranks 101 to 150. This is a query across shards, like the ones we ran for operations across Shopend’s shops. For the first pages, each shard reads only 150 entries. That number does not change as the number of players grows. Reading 150 entries takes a few milliseconds.

A player’s rank

Now let’s answer GET /leaderboards/blitz/players/5512.

1. Read player 5512’s blitz rating: 2140. That is one row, on player 5512’s shard.
2. On every shard, count the blitz ratings higher than 2140. Add up the counts. The rank is that sum plus one.

The index finds 2140 quickly. But the index does not store how many entries come before 2140. So each shard has to walk through the entries above 2140 and count them.

That count grows with the number of players. For a player in the middle of the leaderboard, it is about half of all the players: about 10 million of the 20 million.

Counting 10 million entries takes far longer than looking up 150. And it happens for every rank request. Every profile page sends three rank requests, one for each time control, and many people open profiles at the same time. With 20 million players, we cannot meet the one-second requirement this way.

A page in the middle

A page in the middle of the leaderboard has the same problem. Page 100,000 is ranks 4,999,951 to 5,000,000. Any shard could hold all of them. So each shard has to return its 5 million highest ratings for the merge, and the leaderboard service has to merge them all.