Making the Rank Cheaper

Let’s check whether caching, denormalization, a materialized view, or more read replicas makes a player’s rank cheap enough.

Caching

We could cache each player’s rank and expire it after a fixed time.

The second performance requirement says a new rank must show in real time. So a cached rank can stay in the cache only for a moment, and almost every request still has to count. Also, each player’s rank is a different entry in the cache. Few requests ask for the same player’s rank within that moment, so few requests share an entry.

Denormalization

We could add a rank column to the ratings table. We would update it whenever a rating changes. Then a player’s rank is one row.

But when one player’s rating changes, the rank of every player they move past changes too. Here is how many players that is in the middle of the leaderboard:

• Most ratings are near the middle. We assume about half the players, 10 million, have a rating in a band 500 points wide around the middle. That is about $10,000,000/500=20,000$ players at each rating point.
• We assume a game changes a rating by about 8 points. That is a typical change when two players with equal ratings play.
• So one rating change in the middle moves the player past about $8\times 20,000=160,000$ players.

Each of those 160,000 players’ rank would have to be updated. Those players are on every shard. At the peak, 1,000 ratings change a second, and each of those changes means updating about 160,000 rows.

A materialized view

We could keep every player’s rank in a materialized view. The database refreshes the view.

Refreshing the view means ranking all 20 million players again. That takes far too long to do after every game. Also, the ratings are spread over shards, and a materialized view is kept in one database.

More read replicas

We could add replicas to spread the counting over more servers.

But each count is still the same amount of work on whichever replica runs it. So we would need many replicas, and more as the number of players grows.

What we need instead

None of the four makes a rank cheap enough. The problem is how the player database stores the ratings. Its index keeps the ratings in order, but it does not know how many ratings come before a given one.

So we need something that keeps the players in order and also knows each player’s rank.