Detailed examples of how Redis implements rankings and the same points sorting function by time

This article brings you relevant knowledge about Redis, which mainly introduces the Redis implementation ranking list and the sorting of the same points by time. This article introduces it to you in great detail through example code, as follows Let's take a look, I hope it will be helpful to everyone.

Recommended learning: Redis video tutorial

In daily development, we often encounter the need to calculate user scores, etc. Sorting, for example, in the game, the combat effectiveness needs to be ranked, in team activities, the contribution value of each team needs to be ranked, in WeChat, the number of steps of each friend needs to be ranked, in this case, the order of redis is generally selected. The collection stores the user's scores to meet the needs of the rankings. However, the ranking methods in different scenarios are also slightly different. The following is a summary based on my daily development.

Requirement: Rank the contribution value of each team in the team activity.

Identical points are not considered

Redis’ Sorted Set is an ordered set of String type. Set members are unique, which means that duplicate data cannot appear in the set.

Each element is associated with a double type score. Redis uses scores to sort the members of the collection from small to large.

The members of an ordered set are unique, but the scores can be repeated.

Ignore the situation of having the same points, and implement the ranking list:

// 准备数据，其中value为每个队伍的ID，score为队伍的贡献值
> zadd z1 5 a 6 b 1 c 2 d 10 e
(integer) 5

// 分页查询排行榜所有的队伍和贡献值，要使用zrevrange，而不是zrange，贡献值越大越排在前面
> zrevrange z1 0 2 withscores
1) "e"
2) "10"
3) "b"
4) "6"
5) "a"
6) "5"

// 增加某个队伍的贡献值
> zincrby z1 3 d
"5"
> zincrby z1 4 c
"5"

// 查询排行榜所有的队伍
> zrevrange z1 0 -1 withscores
 1) "e"
 2) "10"
 3) "b"
 4) "6"
 5) "d"
 6) "5"
 7) "c"
 8) "5"
 9) "a"
10) "5"

// 查询某个队伍的排名
> zrevrank z1 d
(integer) 2

The default implementation of Redis is that members with the same score are sorted in dictionary order (09, AZ, a~z), which is used above is zrevrange, so it is in reverse order, so sorting with the same score cannot be sorted according to time priority.

Same points are sorted by time, and the ranking is unique

In the above implementation, if the contribution value of two teams is the same, that is, the points value is the same, they cannot be ranked according to time.

So we need to design a score = contribution value timestamp . Whoever has a higher score will be ranked first. Finally, the contribution value must be analyzed based on the score.

Design 1

Use integers to store score values. The score itself in redis is a double type, and the maximum integer number that can be accurately stored is 2^53=9007199254740992 (16 bits). A timestamp accurate to milliseconds requires 13 digits, leaving only 3 digits for the storage contribution value. Currently, if the time is accurate to seconds, only 10 digits are needed, leaving 6 digits for the contribution value.

Overall design: The high 3 bits represent the contribution value, and the low 13 bits represent the timestamp.

If we simply put the score structure together: Contribution value * 10^13 timestamp, because the larger the score, the closer it will be, and the smaller the timestamp, the closer it will be. In this way, the two Some of the judgment rules are opposite, and the two cannot be simply combined into a score.

But we can think in reverse and subtract the timestamp from the same large enough number Integer.MAX. The smaller the timestamp, the greater the difference we get, so we can change the structure of the score. Contribute value to: * 10^13 (Integer.MAX-timestamp), so that we can meet our needs.

Design 2

Since the score value of redis is of double type, you can use the integer part to store the contribution value, the decimal part to store the timestamp, and use a maximum value to subtract it from the part of the same timestamp.

In this way, the overall design becomes: Score = contribution value (Integer.MAX-timestamp) * 10^-13

Disadvantages: Since the score value is composed of two It is calculated using a variable, so when adding contribution value to the team, you cannot simply use the previous zincrby to change the score value. In this way, adding contribution value to the team under concurrent conditions will lead to inaccurate score values.

Error situation simulation:

Assume that the current contribution value of team A is 10. Player X in team A adds 1 contribution value to the team, and the score is calculated in the program to be 11. Player Y of team A adds a contribution value of 1 to the team, and the score is calculated in the program to be 11.yyy Player X of team A calls the zadd command of redis to set the team's contribution value to 11.xxx Player Y of team A calls the zadd command of redis Set the team's contribution value to 11.yyy Finally, the contribution value of team A is calculated to be 11. The atomicity of the operation of increasing the contribution value cannot be guaranteed.

At this time, you need to use a lua script to ensure the atomicity of the two operations of calculating and setting the contribution value:

// 其中KEYS[1]为排行榜key，KEYS[2]为队伍ID
// 其中ARGV[1]为增加的贡献值，ARGV[2]为Integer.MAX-时间戳
local score = redis.call('zscore', KEYS[1], KEYS[2]) 
if not(score) then
	score=0 
end 
score=math.floor(score) + tonumber(ARGV[1]) + tonumber(ARGV[2]) 
redis.call('zadd', KEYS[1], score, KEYS[2]) return 1

Since the time function cannot be used in redis, (Integer.MAX - timestamp) * The 10^-13 part is calculated and passed in by the program outside the script.

You can continue to use the above commands for functions such as paging the ranking list and querying the team's ranking.

Same points are sorted by time, tied rankings

The so-called tied rankings are rankings with the same ranking situation.

The results we expect are as follows:

##b992c992##de

当然现实中也有排名不跳过的情况，我这里考虑的是排名跳过的情况。

redis中score的设计还是采用上面的分数=贡献值 + (Integer.MAX-时间戳) * 10^-13，只是在查询排名时需要进行计算。

比如要查上表中队伍b的排名，思路如下：

• 首先查到队伍b的score
• 再查到跟队伍b的score的整数部分相同（也就是贡献值一样），排在第一个的队伍的value（队伍ID）
• 根据上一步得到的队伍ID查询此队伍的排名就是队伍b的排名

使用命令实现上面的步骤如下：

> zscore 排行榜key teamId
> zrevrangebyscore(排行榜key, 上一步得到的score+1, 上一步得到的score, limit, 0 , 1)
> zrevrank(排行榜key, 上一步得到的teamId)

为了性能考虑，可以使用下面的脚本一次查出来：

// KEYS[1]表示排行榜key
// KEYS[2]表示要查询的队伍的ID
local rank = 0 
local score = redis.call('zscore', KEYS[1], KEYS[2]) 
if not(score) then
    score=0 
else 
    score=math.floor(score) 
    local firstScore = redis.call('zrevrangebyscore', KEYS[1], score+1, score, 'limit', 0, 1) 
    rank=redis.call('zrevrank', KEYS[1], firstScore[1]) 
end 
return {score,rank}

下面附上分页查询排行榜的脚本，假如一页10条，不用下面的脚本需要查询10次上面的脚本，如果连上面的脚本都没有使用的话就要查询30次redis。

// 排行榜key
// ARGV[1]分页起始偏移
// ARGV[2]分页结束偏移
local list = redis.call('zrevrange', KEYS[1], ARGV[1], ARGV[2], 'withscores') 
local result={} 
local i = 1 
for k,v in pairs(list) do 
    if k%2 == 0 then 
        local teamId = list[k-1] 
        local score = math.floor(v) 
        local firstScore = redis.call('zrevrangebyscore', KEYS[1], score+1, score, 'limit', 0, 1) 
        local rank=redis.call('zrevrank', KEYS[1], firstScore[1]) 
        local l = {teamId=teamId, contributionValue=score, teamRank=rank+1} 
        result[i] = l i = i + 1 
    end 
end 
return cjson.encode(result)

此脚本使用了cjson库，返回的是一个json。

推荐学习：Redis视频教程

Team ID	Contribution value	Ranking
a	100	1
88	4
87	5

The above is the detailed content of Detailed examples of how Redis implements rankings and the same points sorting function by time. For more information, please follow other related articles on the PHP Chinese website!