preface

The Dragon Boat Festival operation on an activity demand, which has a demand point, the same gold value to be sorted in accordance with the order of the first hand to arrive, and is added with red remarks. After my colleague finished the development, WHEN I reviewed the code, I found that in order to implement the update operation, a lot of unnecessary code was generated, and the readability was too poor. In addition, rewards were given to users in the early morning every day, and the code was too redundant, without considering the performance requirements.

So while the Dragon Boat Festival itself to simply achieve a different way to deal with (not necessarily the best), just from a different perspective to look at the solution.

## It is too late for you to update recently, because I am in charge of many projects and I am busy. ## There will be questions on the end face of Baidu (senior T5 / Senior T6) in the next installmentCopy the code

I wish you a happy Dragon Boat Festival oh, don’t forget to learn 😁 😁 😁!

How to sort ordered set contract values?

When the score is the same, Redis uses lexicographical sorting, which is the alphabetical order of “ABC”; Let’s put this into practice:

127.0.0.1:6379> 127.0.0.1:6379> zadd amu 10 xiaoming (INTEGER) 1 127.0.0.1:6379> zadd amu 10 amu (integer) 1 127.0.0.1:6379> zadd amu 10 xiaohong (integer) 1 127.0.0.1:6379> ZRANGE amu 0-1 withscores 1) "amu" 2) "10"  3) "xiaohong" 4) "10" 5) "xiaoming" 6) "10"Copy the code

As you can see from the above, it will return the sorted order by comparing the first letter of the field for the same value.

Redis Zset implements ranking by time order thinking

  • Redis ordered collection values are double 8-byte 64-bit, fully separable and logically stored according to the Snowflake algorithm
  • It can be simple, but it must not be complicated (my colleague uses ordered collections + hashes (storing the last update timestamp), which is very cumbersome)
  • In the case of the same score, the order is sorted according to the earliest time update, so the high point must store the score, and the low point store the timestamp
  • Pay attention to the problem of score overflow and estimate the maximum score that users will reach in advance
  • Every time you update your credits, you need tozscorethenzadd, you can’t guarantee atomic operations; Once concurrency occurs, it is important to note this when dealing with atomic operations

Back-end programmers must: Redis-Lua guarantees atomic operations in concurrent situations

Three practical schemes

① Scheme 1: calculate the scheme through the time difference; Score + End timestamp (fixed bits)

Note that this is just a demonstration: you don’t actually get the value first and then override the original value, see the details at the end

package.path = package.path."; ~/redis-lua/src/? .lua"  -- Directory where redis.lua is located

local json_encode = require "cjson" .encode
local redis = require("redis")

local reds, err = redis.connect('127.0.0.1'.6379)

local key = string.format("dragon:boat:festival:date:%s".os.date('%Y%m%d')) -- Leaderboard Key
local endtime = 1623600000          -- The end time of the activity
local value   = 9999                -- Users increase the score value
local sufix   = endtime - os.time(a)-- The difference between the time the user updated the score and the end time
local user_id = 1001                The user ID is an ordered set of fields

local diff = 5 - string.len(sufix)  -- Calculates whether the timestamp difference length is less than 5. Because the leaderboard is daily, the maximum time difference is 86,400
if diff < 5 then 
    for i=1,diff do
        sufix = 0. sufixend
end

local score   = value .. sufix      -- to form a new value
local res, err = reds:zadd(key, score, user_id)
print(sufix)
print(res)
print(key)
Copy the code

From the above, you can see the overall structure of the idea, mainly to get the score update is the difference between the end of the distance, and then combined with the score; Scores in the front, after the time difference; After getting the score in the set, you can get the score by cutting off a fixed number of digits. The above result set is as follows:

➜ ~ lua hello. Lua Dragon: Boat: Festival:date:20210613

04403
Copy the code

You may have a question: do I take out the score value first, process it into new_SCORE and then save it, or will there be concurrency problems? This is a very good problem: the above operations are not atomic, and concurrent operations can cause our SOCRE inaccuracies, which will be dealt with at the end of this article.

(2) Scheme 2: by bit operation; The principle is fraction + end timestamp (fixed bits)

  • First: you need the end time of the activity as a constraintendtime
  • Second: on the scorescoreLet’s move it to the left27Plus the timestamp difference; In the same integral case, the later you add, after you calculatenew_scoreThe smaller; Realize the principle ofnew_score = score << 27 + (endtime – os.time())
  • Then: We can do this by taking the score from the setMoves to the right27. The timestamp difference is removed and the true integral is displayed

Code implementation is as follows:

local redis = require("redis")

-- Get the true score in the set
-- @param Score Number User score in the collection
function get_score(score)
    return math.floor(score / (2 ^ 27)) 
end

-- Calculates the fraction after the bit operation
-- @param Point Number Increased score
-- @param timestamp Number Indicates the end time of the activity
function to_score(point, timestamp)
    point = tonumber(point) or 0
    timestamp = tonumber(timestamp) or 0
    local score = point * (2 ^ 27)+ (timestamp - os.time())
    return score
end

local endtime = 1623686400   -- The end time of the activity
local new_score = to_score(999, endtime)
local res, err = reds:zadd(key, new_score, user_id)
print(new_score)
print(get_score(new_score))
Copy the code

Execution result:

134083555799, 999,Copy the code

Observation questions:

Although we add the timestamp difference by the bit left and right movement operation, although the probability of the set contract score is the same is smaller. But I don’t know if you’re smart enough to notice that this is a second timestamp, and there are cases where you get to the same fraction at the same time, and you still get the set sorted by the dictionary of the elements which is not very demanding, so you can completely ignore the probability of that happening.

If the result set is super rigorous: we can be accurate to the timestamp to milliseconds or microseconds

# # note: score = level + time (the current system time stamp) score is 64 - bit Long Long (signed) ensure that our combination of digits within the given positionCopy the code

③ Scheme three: based on the idea of snowflake algorithm

# # snowflake structure below 0-0000000000, 0000000000, 0000000000, 0000000000-00000-00000-000000000000 (1) the first for not using (2) The following 41 bits are in milliseconds (the 41 bits can last for 69 years.) ③ The following five bits are datacenterId and workerId. (A 10-bit datacenterId and a five-bit workerId can be deployed on a maximum of 1024 nodes. The last 12 bits are counted in milliseconds (the 12-bit count sequence number supports 4096 ID numbers generated by each node per millisecond). ⑤ The total number is exactly 64 bits, which is a Long. (Converts to a string of length 18)Copy the code

Why the idea of snowflake? This is because the lua algorithm was used in the project to implement and modify the algorithm, so when reviewing the code, my first thought was to use the snowflake algorithm idea to achieve the ranking. Of course, there are some similarities with solution 2, but there are many ways to do it.

List implementation principle # # 1 high without + 41 timestamp + 22 points If it is can be represented as such 0 (highest reserved) | 000000000000 000000 000000 (22 points) | 0 0000000000 0000000000 0000000000 0000000000(41 bit timestamp) The score is high and the timestamp is low, so that no matter what the timestamp is, the larger the score is, the larger the value will be, which meets our requirements. 22 bit is the value that meets our business requirements: Support a maximum of (2^21-1) 41-bit timestamp support a maximum of milliseconds: 2^40-1Copy the code

What if 22 bits doesn’t meet our business needs, it’s too small? So we can compress the 41 bit timestamp as well. We can compress the timestamp in the same way as we did in scenario 2: the active end time – the current timestamp. We can compress the 32 bit or 16 bit from the 64 bit. Here I do it in code:

local time = os.time
local bits = {}
-- Perform a bit operation on each bit and return the value
local function _bits_op(left, right, func)
    if left < right then
        left, right = right, left
    end
    local result = 0
    local shift = 1
    while left ~= 0 do
        local num_1   = left % 2  -- Take mod to get each digit (rightmost)
        local num_2   = right % 2 Take over -
        local ok, ret = pcall(func, num_1, num_2)
        ret = tonumber(ret) or 0
        result = shift * ret + result
        shift  = shift * 2
        left   = math.modf(left / 2)  - moves to the right
        right  = math.modf(right / 2) - moves to the right
    end
    return result
end

- or operation
function bits.bits_bor(left, right)
    return _bits_op(left, right, function(left1, right1)
        return (left1 == 1 or right1 == 1) and 1 or 0
    end)
end

- moves to the right
function bits.bits_rshift(left, num)
    return math.floor(left / (2 ^ num))
end

- left
function bits.bits_lshift(left, num)
    return left * (2 ^ num)
end

-- Get points
function bits.get_score(score, bitnum)
    score = tonumber(score) or 0
    local bit_num = tonumber(bitnum) or 41
    return bits.bits_rshift(score, bit_num)
end

-- Update the score
function bits.to_score(point, curtime, bitnum)
    local points = tonumber(point) or 0
    local timestamp = tonumber(curtime) or 0
    local bit_num = tonumber(bitnum) or 41
    local score = 0
    score = bits.bits_bor(score, points)
    score = bits.bits_lshift(score, bit_num)
    score = bits.bits_bor(score, (timestamp - time()))
    return score
end

local score = 0    -- Current score
local cur_ponit = bits.get_score(score)
print(cur_ponit)
local new_score  = bits.to_score(cur_ponit + 99999.1625068800)
local res, err = reds:zadd(key, new_score, user_id)
print(new_score)
print(bits.get_score(new_score))
Copy the code

Generate results:

0 -- initialize the true fraction 219900126533365579 -- Perform bit operation 99999 -- restore the true fractionCopy the code

Left shift and right Shift At the beginning of the job, you might have some of these interview questions. Colloquial: displacement is the data into binary, moving left and right; If you move to the left, you fill in zero on the right; If you move to the right, zero in on the left, and delete the overflow. So the simpler way to think about it is: multiplication of integers moving to the left; Moving to the right is the divisible division of integers. So you can better understand the above case code

For example:

Left shift (<<) : Move the first number to the left by the number of digits specified by the second number, and fill in the null positions ## Notice that left shift is equivalent to multiplication; A << 1 = a * 2 => a * 2^num => a * 2^num => a * 2^num => a * 2^num For example, a >> 1 = a / 2 => a / 2^numCopy the code

How do I guarantee atomic operations

Concurrent cases redis – lua guarantee atomic operation this article has clearly set forth the concurrent cases to ensure atomicity operation, this is the test, the basis of a senior development engineer want to know now no matter big or small company, under the business scenario of users and large amount of data is easy to appear the concurrent scenarios, so we must understand and use.

package.path = package.path."; ~/redis-lua/src/? .lua"  -- Directory where redis.lua is located
local json_encode = require "cjson" .encode
local redis = require("redis")
local reds, err = redis.connect('127.0.0.1'.6379)

-- Update the user score value
local _update_score = [[ local key = KEYS[1] local field = ARGV[1] local score = ARGV[2] local timestamp = ARGV[3] score = tonumber(score) or Timestamp = tonumber(timestamp) or 0 -- time difference local cur_score = redis.call('zscore', key, Cur_score = tonumber(cur_score) or 0 local ponit = math.floor(cur_score/(2 ^ 27) Ponit = tonumber(ponit) or 0 local ret = {"score", 0,"res", Local res = num * (2 ^ 27) + timestamp Redis.call ('zadd', key, res, field) -- Insert ret[2] = num ret[4] = res return ret]]

local key = string.format("dragon:boat:festival:date:%s".os.date('%Y%m%d')) -- Leaderboard Key
local endtime = 1623600000          -- The end time of the activity
local score   = 9999                -- Users increase the score value
local sufix   = endtime - os.time(a)-- The difference between the time the user updated the score and the end time
local user_id = 1001                The user ID is an ordered set of fields

local res , err = reds:eval(_update_score, 1, key, user_id,  score, sufix)
print(json_encode(res))
Copy the code

The result set:

: : Dragon Boat Festival: date: 20210614 [" score ", 19997, "res", 2683951855961] 127.0.0.1:6379 > ZSCORE dragon:boat:festival:date:20210614 1001 "2683951855961"Copy the code

It is recommended to use evalsha to cache the scripts and not reload them every time. This reduces network overhead and response time and ensures fast service response.

conclusion

The above three schemes are processed by different schemes according to the codes submitted by my colleagues, trying to ensure the simplicity of the business. Otherwise, hundreds of lines of code are needed to implement what could have been solved with more than ten lines of code. But in the end, we are going to implement ordering processing of ordered sets according to rules other than Redis. Just let’s not blindly have this phenomenon in the implementation of the function: “can achieve, no matter how the process! “That’s not true. You have to keep optimizing your code to get better at making it look good. It’s self-responsibility

It is important to ensure that atomic operations are performed concurrently!

Maybe you have the following questions:

You may ask, lua5.3 introduced the bit library, why not use it directly? ② You may also ask how the performance compares to your colleagues' implementations and what are the advantages? Note that the next lua tutorial will answer your questions. Leave questions here; You can also look up the data, the actual run to see the performanceCopy the code

If there are different plans or questions, welcome to criticize!