There are various leaderboards, such as player rank rankings, score rankings, etc. A player’s ranking in the leaderboard is a sign of their power, and the player at the top of the leaderboard has a lot of honor in the virtual world, so the ranking is the goal of the core gamer.

A typical game leaderboard has the following common features:

  1. The ability to keep track of each player’s score;
  2. The ability to update a player’s score;
  3. The ability to query each player’s score and ranking;
  4. The ability to query top N players by rank;
  5. Allows you to query the M names of players before and after the specified player.

Further, all of this needs to be done in real time and in a short period of time to get the most out of the leaderboard.

As a player’s ranking goes up by x places, the ranking of X +1 players will change (including the player). If the traditional database (such as MySQL) is used to achieve the leaderboard, when the number of players is too large, the database will be frequently modified and the performance will not be satisfied, so we can only think of another method.

As a member of NoSQL, Redis has been widely used in recent years. Redis has a wider range of data types and operation interfaces than Memcached, with sorted sets (also known as Zsets) being ideal for building lists. Here is a brief summary.

1. Installation of Redis

To install Redis on Ubuntu, run the following command:

$ sudo apt-get install redis-server

After the installation, run the redis- CLI client to access the local Redis server.

6379 > $redis – cli redis 127.0.0.1:

If you want to use the latest version, you need to download the latest version from the Redis website (redis.io).

2. Common ZSet commands

An ordered set is first a set whose members are unique. Second, each member is associated with a score, so that members can be sorted by score. For an introduction to ordered collections, see Redis. IO /topics/data… IO /commands#so… .

Here are a few commands that can be used for leaderboards.

Assume that LB is the name of the leaderboard and user1, user2, and so on are the unique identifications of players.

1) Zadd — Set the player’s score

Zadd Leaderboard name Score Player identifier Time complexity: O(log(N))

The four players’ scores are set below, and if a player’s score already exists, the previous score will be overwritten.

> redis 127.0.0.1:6379> zadd lb 89 user1
> (integer1 > redis 127.0.0.1:6379> zadd lb 95 user2 > (integer1 > redis 127.0.0.1:6379> zadd lb 95 user3 > (integer1 > redis 127.0.0.1:6379> zadd lb 90 user4 > (integer1)Copy the code
2) ZScore — See the player score

Command format: zScore Leaderboard name Player identifier Time complexity: O(1)

Here’s a look at user2’s score in the LB leaderboard.

Redis 127.0.0.1:6379> zscore lb user2 “95”

3) Zrevrange — View leaderboards by rank

Format: zrevrange Start position End position [withscores] Time complexity: O(log(N)+M)

Since the leaderboard is generally ranked by highest to lowest score, we use zrevrange, and the command zrange is ordered by lowest to highest score.

Both the start and end positions are indexes that start at 0 and are included. If the end position is -1, the entire leaderboard is displayed.

Withscores returns the player’s score.

Here’s a look at all player scores.

> redis 127.0.0.1:6379> Zrevrange lb 0-1 withscores > 1) user3 > 2) 95 > 3) User2 > 4) 95 > 5) User4 > 6) 90 > 7) User1 > 8) 89Copy the code

Here’s how to query the scores of the top three players.

> redis 127.0.0.1:6379> Zrevrange lb 0 2 withscores > 1) user3 > 2) 95 > 3) User2 > 4) 95 > 5) User4 > 6) 90Copy the code
4) ZRevRank — See where players rank

Command format: zRevRank List name Player identifier Time complexity: O(log(N))

Similar to ZRevRange, ZRevRank returns the player rank in descending order of points (it actually returns an index starting with 0), while the corresponding ZRank returns the player rank in descending order of points.

Here’s how to query the ranking of user3 and user4.

> redis 127.0.0.1:6379> zrevrank lb user3
> (integer0 > redis 127.0.0.1:6379> zrevRank lb user1 > (integer) 3
Copy the code
5) Zincrby — increase or decrease a player’s score

Command format: zincrby Leaderboard name score increment Player identifier Time complexity: O(log(N))

Some leaderboards reset a player’s score when they change, while others change a player’s score incrementally, either positively or negatively. If the player is not on the leaderboard when the zincrby is executed, the original score is considered to be 0, which is equivalent to ZDD.

Let’s increase the score of user4 by 6, so that it rises to the first place.

> redis 127.0.0.1:6379> zincrby lb 6 user4 > 96 > Redis 127.0.0.1:6379> Zrevrange lb 0-1 withscores > 1) user4 > 2) "96" > 3) "user3" > 4) "95" > 5) "user2" > 6) "95" > 7) "user1" > 8) "89"Copy the code
6) Zrem — Remove a player

Command format: zrem Leaderboard name Player identifier Time complexity: O(log(N))

Let’s remove the player user4.

> redis 127.0.0.1:6379> zrem lb user4
> (integer) 1 > Redis 127.0.0.1:6379> Zrevrange lb 0-1 withscores > 1) User3 > 2) 95 > 3) User2 > 4) 95 > 5) User1 > 6) "89"Copy the code
7) Del — Delete the leaderboard

Command format: del Indicates the name of the leaderboard

The leaderboard object is created when we first call zadd or zincrby. To delete it, call the redis general command del.

> redis 127.0.0.1:6379> del lb
> (integer) 1 > redis 127.0.0.1:6379> get lb > nilCopy the code

3. Same score problem

The free plan is always a little less than perfect. As you can see from the previous example, user2 and user3 have the same score, but when sorting by score in reverse order, user3 is ranked before User2. In the actual application scenario, we would prefer to see user2 rank ahead of user3, because user2 joins the leaderboard before user3, that is, user2 reaches the score first.

However, when Redis encounters the same score, it sorts according to the lexicographical order of the set members themselves. Here, it sorts according to the two strings “user2” and “user3”. If it sorts in reverse order, user3 will naturally rank first.

To solve this problem, we can consider adding a timestamp to the score. The calculation formula is:

Timestamp = actual timestamp *10000000000 + (9999999999 — timestamp)

Timestamp We use the system-provided time() function, which is the number of seconds since January 1, 1970, we use a 32-bit timestamp (this will last until 2038), since the 32-bit timestamp is a 10-bit decimal integer (maximum: 4294967295), So we make the timestamp the lower 10 bits (decimal integer), the actual fraction 10^10 times larger, and then add the two parts together as the fraction of the Zset. Given the backward chronological order, the timestamp part needs to be reversed, which is why the timestamp is subtracted from 9999999999. When we want to read a player’s actual score, we just remove the last 10 bits.

At first glance, this looks good, but there are two problems.

The first problem is a small one. If the second is used as the time stamp, the differentiation may not be enough. If two time stamps with the same fraction occur in the same second, the previous problem will still occur.

The second problem is a big one, because Redis uses double as the fractional type. A 64-bit double floating-point number has only 52 significant digits. It can accurately represent integers ranging from -2^53 to 2^53, and can only represent 16-digit decimal integers (9007199254740992, In fact, even 16 bits is not complete). This means that if the previous timestamp is 10 places, the score is only 6 places left, which is not enough for some leaderboard scores. We could consider reducing the number of timestamp digits to, say, January 1, 2015, but that would still not add a few digits. Or reduce the distinction and use minutes and hours as the time stamp units.

If Redis had a score type of INT64, we wouldn’t have that problem. At this point, Redis really should provide an int64 ZSet, but this is a fantasy, unless you change the source code.

Since Redis can’t solve the leaderboard problem perfectly, is it ultimately necessary to implement a dedicated leaderboard data structure? After all, there are a lot of things that can be done to optimize the leaderboard in the real world. The leaderboard is a pyramid of players, the lower the segment, the more players there are, the larger the number of players on the same score, and a single point can surpass many players.

This article is also published in the wechat public number [Trail Information], welcome to scan the code to follow!