Real-time game leaderboard

01 · CONTEXT AND REQUIREMENTS

What a real-time leaderboard is

In a game leaderboard, each player accumulates points and whoever has the most points is at the top. In the scenario from the ByteByteGo book, the player earns one point for each match won and, each month, a new tournament starts with a new leaderboard. The AWS database blog describes the leaderboard as a social feature in which players compare their performance.

The functional requirements are to show the top 10 players and the position of a specific user; as a bonus, to show the players four positions above and below them. The central non-functional requirement is real-time updating, since a batch history is not acceptable. If two players have the same score, they share the same rank.

02 · SCALE ESTIMATION

Back-of-the-envelope math

The book's problem statement mentions 5 million daily active users and 25 million monthly, with each player playing an average of 10 matches per day.

Spreading the 5 million users across the day gives about 50 users per second. With the matches, that is about 500 points per second on average and, with a peak of five times the average, 2,500 per second. The top 10 query, meanwhile, is around 50 per second, because the book assumes the player opens the game once a day and only then loads the leaderboard.

03 · API AND FIRST ATTEMPT

Starting with the relational database

The book proposes three routes in the APIAPI: one to update the score, one to fetch the top, and one to fetch a user's position. The update route is internal, called only by the game servers, because letting the client set the score is not safe, as it is exposed to a man-in-the-middle attack.

When the player wins, the client notifies the game service, which checks that the win is valid and calls the ranking service to update the score.

The simplest solution is a relational table with user and score: each win adds one point and the position comes from sorting the table by score, in descending order.

1. The player wins a match and the client notifies the game service.

2. The game service validates the win and calls the ranking service.

3. The ranking service increments the user's score in the table.

4. To show the position, the ranking service has to sort the players in the table, which gets slow with millions of rows.

The problem appears with millions of rows: according to the book, a rank operation takes tens of seconds, which is unacceptable for real time, and since the data changes all the time caching is not viable. Even with an index and LIMIT, finding a user's position requires scanning the table. The AWS database blog cites 35 seconds on average on a table with 50 million records, even with indexes. A relational database would work for batch, but that does not meet real time.

04 · REDIS SORTED SETS

A leaderboard that is born sorted

Redis keeps everything in memory, which allows fast reads and writes. Its data structure for this case is the sorted set: a collection of unique strings, the members, ordered by an associated score. Scores can repeat and, when that happens, the documentation says the strings are ordered lexicographically. The documentation itself cites online game leaderboards as a use case and describes the typical use as combining the top users with the user's position in the leaderboard.

Internally, the book describes a hash table and a skip list: the hash links users to scores and the skip list links scores to users. The Redis documentation describes the same idea and says that each element added costs a logarithmic operation; so does updating the score of an existing element. The AWS blog summarizes the difference from the relational database: the sorted set places the item in the right order at insertion or update, and finds positions logarithmically, whereas the relational database sorts during the query.

Each month a new sorted set is created and the previous ones go to historical storage. The book calculates that, in the worst case, the leaderboard takes about 650 MB in Redis and that, even doubling that value for overhead, a modern Redis server is more than enough; the peak of 2,500 writes per second is also within the capacity of a single server.

On durability: Redis has persistence, but restarting a large instance from disk is slow. It is also common to configure a read replicareplica, promoted when the primary fails. User names and photos live in MySQL, and the points recorded there can rebuild the leaderboard after an infrastructure failure.

1. With the win validated, the ranking service increments the player's score in the month's sorted set with ZINCRBY.

2. For the top of the leaderboard, the service reads the sorted set in descending order with ZREVRANGE, without having to sort anything on the spot.

3. For a player's position, the service calls ZREVRANK.

4. Names and photos come from MySQL and are joined to the result.

5. If the primary Redis fails, the replica is promoted and a new replica is attached.

6. Se o Redis for perdido por completo, os pontos registrados no MySQL permitem recriar o ranking.

05 · SCALING AND ALTERNATIVES

Sharding and NoSQL

With 5 million users per day, one Redis is enough. The book then imagines a scale one hundred times larger, with 500 million per day, where the worst case reaches 65 GB and 250,000 queries per second, which calls for sharding.

With fixed partitioning, the leaderboard is divided by score ranges, for example ten shards of one hundred points each, and the sharding is done in application code. This requires scores to be distributed evenly across the ranges. To know which range the user is in, a faster option is a secondary cache with the user-to-score mapping, and when the user changes range they must be removed from the current shard and moved to the new one.

1. Each shard holds the sorted set for a score range, and the application decides which shard to talk to.

2. When adding points, the service finds out which shard the user is in using the user-to-score map.

3. If the score crosses a range, the user leaves one shard and enters the next, for example from a lower-score shard to an intermediate one.

4. The top of the leaderboard comes from the shard with the highest scores.

5. A user's position adds the local rank in their shard to the total number of players with a higher score in the other shards.

The alternative is Redis Cluster, which divides the keys automatically into 16384 hash slots. The top 10 now requires gathering the top 10 of each shard and sorting in the application; with many partitions the latency rises, because the query waits for the slowest one, and there is no direct solution for a user's position. That is why the book opts for fixed partitioning. On AWS, ElastiCache for Redis in cluster mode adds shards to scale writes and read replicas to scale reads.

Another alternative is a NoSQL optimized for writes and able to sort items by score within the partition: the book cites DynamoDB, Cassandra, or MongoDB. If the partition key is just game and month, the data for the recent month lands on a hot partition. The way out is write sharding, which spreads the month across several partitions at the cost of complicating reads and writes, since reading the month requires querying all the partitions and merging the results.

06 · WRAP-UP

Ties, failures, and when to choose what

For tie-breaking, the book suggests storing the timestamp of each user's most recent win: in case of a tie, whoever has the older timestamp ranks ahead. A Redis hash with the user object avoids going to the database to fetch name and photo. If all of Redis is lost, the leaderboard can be rebuilt by calling ZINCRBY once per record of each user.

The book's starting point is a single sorted set, which covers the initial scale; sharding only comes in when the size and the queries exceed what one server supports.