Using the ordered collection of Redis to realize the leaderboard function example code

preface

There are various leaderboards in the game, such as player rank, score rank and so on. The rank of players in the leaderboard is a symbol of their strength. The players at the top of the list have great glory in the virtual world, so the rank has become the goal of core players.

A typical game leaderboard includes the following common features:

Be able to record points for each player; The ability to update player scores; Be able to query the score and ranking of each player; Can query the top N players by rank; Can query M players before and after a given player.

Further, the above operations need to be completed in real time in a short time to maximize the effectiveness of the leaderboard.

As the ranking of x +1 player will change if one player rises in rank (including that player), if traditional database (such as MySQL) is adopted to realize leaderboard, when the number of players is too large, the database will be frequently modified and the performance cannot be satisfied, so we have to 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 interfaces than Memcached, where ordered collections (sorted set, also known as zset) are well suited for leaderboards. The following is a brief summary of 1.

1. Installation of Redis

Installing Redis under Ubuntu is very simple, just execute the following command:

$ sudo apt-get install redis-server

Once installed, run the command line client ES38en-ES39en to access the local redis server.

$ redis-cli
redis 127.0.0.1:6379>

If you want to use the latest version, need to Redis official website (ES45en.io) download the latest code compiled by yourself, steps skip.

2. Common ZSet commands

An ordered set is first a set whose members (member) are unique, and second, each member is associated with a score (score) so that the members can be sorted by score. The introduction of an ordered set of see redis. io/topics/data... See redis.io/commands#so... .

Here are some commands you can use for leaderboards.

Suppose lb is the name of the leaderboard, and user1, user2, etc. are the only 1 identification for the player.

1) zadd -- Set player scores

Command format: zadd Leaderboard name score Player identification Time complexity: O(log(N))

The following sets the score for four players, and if the player score already exists, the previous score will be overwritten.

redis 127.0.0.1:6379> zadd lb 89 user1
(integer) 1
redis 127.0.0.1:6379> zadd lb 95 user2
(integer) 1
redis 127.0.0.1:6379> zadd lb 95 user3
(integer) 1
redis 127.0.0.1:6379> zadd lb 90 user4
(integer) 1

2) zscore -- Check player scores

Command format: zscore Leaderboard name: Player identification Time complexity: O(1)
Check out user2's score on the lb leaderboard below.

redis 127.0.0.1:6379> zscore lb user2
 " 95 " 

3) zrevrange -- View the leaderboard by rank

Time complexity: O(log(N)+M)

Since leaderboard 1 generally ranks scores from highest to lowest, we used zrevrange, while the command zrange ranks scores from lowest to highest.

Both start and end positions are indexed starting at 0 and are included. If the end position is -1, the view scope is the entire leaderboard.

withscores returns the player's score.

See below for all player scores.

redis 127.0.0.1:6379> zrevrange lb 0 -1 withscores

 " user3 " 
 " 95 " 
 " user2 " 
 " 95 " 
 " user4 " 
 " 90 " 
 " user1 " 
 " 89 " 

The following is to query the top 3 player scores.

redis 127.0.0.1:6379> zrevrange lb 0 2 withscores

 " user3 " 
 " 95 " 
 " user2 " 
 " 95 " 
 " user4 " 
 " 90 " 

4) zrevrank -- Check the player's ranking

Command format: zrevrank Leaderboard name Player identification Time complexity: O(log(N))

Similar to zrevrange, zrevrank returns the player's ranking in a descending order of scores (what is actually returned is an index starting at 0), while the corresponding zrank returns the ranking in a descending order of scores.

Below is the ranking of query players user3 and user4.

redis 127.0.0.1:6379> zrevrank lb user3
(integer) 0
redis 127.0.0.1:6379> zrevrank lb user1
(integer) 3

5) zincrby -- increase or decrease player score

Command format: zincrby Leaderboard name score increment player id Time complexity: O(log(N))

Some leaderboards reset the player's score as it changes, while others change the player's score in increments, either positive or negative. If the player is not in the leaderboard when zincrby is executed, the original score is considered to be 0, equivalent to zdd.

The following 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

 " user4 " 
 " 96 " 
 " user3 " 
 " 95 " 
 " user2 " 
 " 95 " 
 " user1 " 
 " 89 " 

6) zrem -- Remove a player

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

Now remove player user4.

redis 127.0.0.1:6379> zrem lb user4
(integer) 1
redis 127.0.0.1:6379> zrevrange lb 0 -1 withscores

 " user3 " 
 " 95 " 
 " user2 " 
 " 95 " 
 " user1 " 
 " 89 " 

7) del -- Delete the list

Command format: del leaderboard name

The leaderboard object is created when we first call zadd or zincrby, and when we want to delete it, we simply call the redis generic command del.

redis 127.0.0.1:6379> del lb
(integer) 1
redis 127.0.0.1:6379> get lb
(nil)

3. Same score problem

Free solutions are always imperfect. As we can see from the previous example, user2 and user3 have the same score, but user3 comes before user2 in the reverse order of scores. In the practical application scenario, we prefer to see user2 rank ahead of user3, because user2 joins the ranking before user3, which means user2 reaches this score first.

However, when Redis encounters the same score, it is sorted according to the dictionary order of the members of the set. In this case, it is sorted according to the two strings of "user2" and "user3". In reverse order, user3 naturally comes first.

To solve this problem, we can consider adding a time stamp into the score, which is calculated as follows:

[

Timestamped score = actual score *10000000000 + (9999999999, timestamp)

]

timestamp we adopt the system to provide time () function, which is the number of seconds since January 1, 1970, we adopt 32-bit timestamp (this can get to 2038), because the 32-bit timestamp is 10 decimal integer (maximum 4294967295), so we let the timestamp occupy low 10 (decimal integer), 10 ^ 10 times the actual score is expanded, then taking the results of the two parts together as zset scores. Considering that you want to go in reverse chronological order, this part of the timestamp needs to be reversed by 1, which is why you subtract the timestamp from 9999999999. When we want to read the player's actual score, we only need to remove the last 10 digits.

The scheme looks good at first sight, but there are two problems.

The first problem is a minor one. Using seconds as time stamps may not be differentiated enough. If two fractions of the same second occur, the previous problems will still occur.

The second problem is a big one, because Redis USES double as the fractional type. 64-bit double-precision floating-point Numbers have only 52 significant digits, and can accurately express integers ranging from -2^53 to 2^53, with the maximum representing 16-bit decimal integers (the maximum is 9007199254740992, even 16 bits cannot be fully represented). That is, if the preceding timestamp takes up 10 places, there will be only 6 places left in the score, which is not enough for some leaderboard scores. We could consider reducing the number of timestamps, such as starting on January 1, 2015, but that still wouldn't add a few digits. Or reduce the distinction by using minutes or hours as timestamps.

If the score type for Redis is int64, we don't have this problem. At this point, Redis really should provide an additional int64 type of ZSet, but for now it's a fantasy unless you change the source code.

Since Redis is not a perfect solution to the leaderboard problem, is it ultimately necessary to implement a dedicated leaderboard data structure yourself? After all, the leaderboard in the actual application has many areas that can be optimized, which are distributed in a pyramid with players. The lower the score, the more players there are. If there are a large number of players with the same score, players who increase one point may surpass many players, which provides the possibility for optimization.

conclusion