Shulou(Shulou.com)05/31 Report--

This article is about how to use the ordered collection of Redis to achieve the ranking function. The editor thinks it is very practical, so share it with you as a reference and follow the editor to have a look.

A typical game ranking includes the following common features:

Be able to record each player's score

Be able to update the player's score

Can query the scores and rankings of each player

Be able to query the top N players by rank

You can query the players with M names before and after the specified players.

Furthermore, the above operations need to be done in real time in a short period of time in order to maximize the effectiveness of the rankings.

As a player ranking rising x bit will cause a change in the ranking of x + 1 players (including that player), if the traditional database (such as MySQL) is used to achieve the ranking, when there are a large number of players, it will lead to frequent changes to the database and the performance will not be satisfied, so we can only think of another way.

As a member of NoSQL, Redis has been widely used in recent years. Compared with Memcached, Redis has more data types and operation interfaces, and has a wider scope of application, in which the ordered set (sorted set, also known as zset) is very suitable for the construction of rankings. The following is a brief summary.

1. Installation of Redis

It is very easy to install Redis under Ubuntu. Execute the following command:

$sudo apt-get install redis-server

After installation, run the command line client redis-cli to access the local redis server.

$redis-cliredis 127.0.0.1purl 6379 >

If you want to use the latest version, you need to go to the Redis website (redis.io) to download the latest code and compile it by yourself.

2. Common commands of ZSet

First of all, an ordered set is a set, and its members (member) are unique, and secondly, each member is associated with a score (score), so that members can be sorted by score. For an introduction to ordered sets, see redis.io/topics/data. , whose orders can be found in redis.io/commands#so.

Here are a few commands that can be used in the rankings.

Suppose lb is the name of the ranking, and user1, user2 and so on are the unique identifiers of players.

1) zadd-- sets player scores

Command format: zadd ranking list name score player identification time complexity: O (log (N))

The scores of 4 players are set below. If the player score already exists, the previous score will be overwritten.

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

2) zscore-- to check player scores

Command format: zscore ranking name player identification time complexity: O (1)

Here is a look at the scores of user2 in the lb rankings.

Redis 127.0.0.1 6379 > zscore lb user2 "95"

3) zrevrange-- views the ranking by rank

Command format: zrevrange ranking name start position end position [withscores] time complexity: O (log (N) + M)

Because rankings are generally sorted by score from high to low, we use zrevrange, while the command zrange is sorted by score from lowest to highest.

Both the start position and the end position are indexes that start with 0 and are included. If the end position is-1, the view range is the entire ranking.

With withscores, the player's score will be returned.

The following is to view all player scores.

Redis 127.0.1 redis 6379 > zrevrange lb 0-1 withscores "user3"95"user2"95"user4"90"user1"89"

The following is to query the scores of the top three players.

Redis 127.0.1 withscores 6379 > zrevrange lb 0 2 withscores "user3"95"user2"95"user4"90"

4) zrevrank-- to view players' rankings

Command format: zrevrank ranking name player identification time complexity: O (log (N))

Similar to zrevrange, zrevrank returns player rankings in order of scores from highest to lowest (actually returns an index starting with 0), while zrank returns rankings in order of scores from lowest to highest.

The following is the ranking of players user3 and user4.

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

5) zincrby-- increases or decreases player scores

Command format: zincrby ranking list name score increment player identification time complexity: O (log (N))

Some rankings reset the player's score when it changes, while others modify the player's score incrementally, which can be positive or negative. If the player is not in the league table when performing zincrby, his original score is considered to be 0, which is equivalent to performing zdd.

Next, increase the score of user4 by 6, raising its ranking to the first place.

Redis 127.0.0.1 redis 6379 > zincrby lb 6 user4 "96" redis 127.0.1 redis 6379 > zrevrange lb 0-1 withscores "user4"96"user3"95"user2"95"user1"89"

6) zrem-- removes a player

Command format: zrem ranking name player identification time complexity: O (log (N))

Next, remove the player user4.

Redis 127.0.0.1 redis 6379 > zrem lb user4 (integer) 1redis 127.0.0.1 1redis 6379 > zrevrange lb 0-1 withscores "user3", 95 "user2", 95 "user1"89"

7) del-- deletes the ranking list

Command format: del ranking name

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

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

3. The same score problem

There are always some imperfections in free solutions. As we can see from the previous example, user2 and user3 have the same score, but when sorted in reverse order by score, user3 comes before user2. In practical application scenarios, we prefer to see user2 ahead of user3, because user2 joins the rankings before user3, that is, user2 reaches the score first.

However, when Redis encounters the same score, it is sorted according to the dictionary order of the collection members themselves. Here, it is sorted according to the two strings "user2" and "user3". If it is sorted in reverse order, user3 naturally comes first.

To solve this problem, we can consider adding a timestamp to the score, which is calculated as follows:

Time-stamped score = actual score * 10000000000 + (9999999999-timestamp)

Timestamp We use the time () function provided by the system, that is, the number of seconds since January 1, 1970, and we use a 32-bit timestamp (which lasts until 2038). Because the 32-bit timestamp is a 10-bit decimal integer (maximum 4294967295), we let the timestamp occupy the lower 10 bits (decimal integer), and the actual score is increased by 10 ^ 10 times, and then the result of the addition of the two parts is taken as the score of zset. Considering that it needs to be arranged in reverse chronological order, the timestamp part needs to be reversed, which is why you use 9999999999 to subtract the timestamp. When we want to read the player's actual score, we only need to remove the last 10 digits.

At first, the plan looks good, but there are two problems.

The first problem is a small problem. It is not enough to use seconds as the timestamp to distinguish. If there are two same scores in the same second, there will still be the previous problem. Of course, we can choose a more accurate timestamp, but in the actual scene, it doesn't matter who ranks first in the same second.

The second problem is a big problem, because Redis's fraction type uses double,64-bit double-precision floating-point numbers with only 52 significant digits, and it can accurately represent integers ranging from-2 ^ 53 to 2 ^ 53, up to a maximum of 16-bit decimal integers (the maximum is 9007199254740992, which cannot even be fully represented). That is to say, if the previous timestamp occupies 10 places, the score will be left with only 6 places, which is not enough for some ranking scores. We can consider reducing the number of timestamp digits, for example, starting from January 1, 2015, but this still does not increase many digits. Or reduce the degree of differentiation, in minutes, hours as the timestamp unit.

If the score type of Redis is int64, we don't have the above troubles. Speaking of which, Redis should really provide an additional int64 type of ZSet, but for now it can only be a fantasy unless you change its source code.

Since Redis can't solve the ranking problem perfectly, is it necessary to implement a special ranking data structure on its own? After all, there are many places that can be optimized in the ranking table in practical application, which is more pyramidal than players. The lower the number of players is, the more players there are. If there are a large number of players in the same score, players may surpass many players if they add one point. This provides the possibility for optimization.

Thank you for reading! On "how to use the orderly collection of Redis to achieve ranking function" this article is shared here, I hope the above content can be of some help to you, so that you can learn more knowledge, if you think the article is good, you can share it out for more people to see it!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.