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

In this issue, Xiaobian will bring you about Redis SortedSet structure score field loss precision problem solution, the article is rich in content and professional analysis and description for everyone, after reading this article I hope you can gain something.

I. Problem phenomena

Redis SortedSet is used in the project to store the offline messages of users, and msgid (message ID) stored by score value. msgid is generated by snowflake algorithm and ordered according to time.

The msgid generated has an 18-bit decimal integer, such as 215857550229364736

We found that msgid values are very close and cannot be distinguished by score in redis.

For example, store the following data in the tzset structure of redis

ZADD tzset 215857497028812800 test1

ZADD tzset 215857540511162369 test2

ZADD tzset 215857550229364736 test3

ZADD tzset 215857550229364737 test4

Check the results.

We find that score values are expressed in scientific notation, and the score values of test3 and test4 are the same.

Use score=215857550229364736 to execute the query, and the result is as follows

Using 215857550229364736 query, test4 with score of 215857550229364737 was also found

Use 215857550229364739 to check, unexpectedly can also find out

This phenomenon bothers our system functionality and affects the accuracy of message synchronization TimeLine (see Message Synchronization Mechanisms Based on the TimeLine Model).

II. Causes of problems

Query related data found that the Score in Sorted Sets is of type double, and our msgid is of type long. The problem is that when long is converted to double, precision is lost.

1. Introduction to snowflake algorithm

The message ID adopts snowflake algorithm and adopts 64-bit binary integer. Binary specific digit meaning as shown in the figure below.

One, no. The most significant bit in binary is negative, but the id we generate uses positive numbers, so the most significant bit is fixed to 0.

41 bits to record the timestamp (milliseconds).

If it is used only to represent positive integers (positive numbers include 0 in computers), the range of values that can be represented is 0 to 241−1, minus 1 because the range of values that can be represented starts from 0, not 1.

That is to say, 41 bits can represent 241−1 milliseconds, which translates into (241−1)/(1000 <$60 <$60 <$24 <$365)=69 years.

10 bits to record the machine ID.

Can be deployed on 1024 nodes, including 5-bit datacenterId and 5-bit workerId

12 bits, serial number, used to record different ids generated within the same millisecond.

The largest positive integer that can be represented by 12 bits is 4095, that is, 0, 1, 2, 3,... 4095 These 4096 numbers represent 4096 ID numbers generated by the same machine within the same time period (milliseconds).

2. Doubler data structure

The structure of double data is as follows

3. Problem positioning

63-bit (minus sign) numbers are converted to 52-bit numbers, rounding off from one bit, resulting in reduced accuracy. So 215857550229364736, 215857550229364737, and 215857550229364739 are converted to double, and the computer considers them to be the same number.

III. SOLUTIONS

Problem found, how to solve it?

ID generation strategy It is difficult to design a 52-bit ID generator to ensure that all IDs in the whole system life cycle are unique.

The score data type of Redis cannot be modified.

Using 52 bits to represent 63 bits of data will definitely lose information. The method of converting long integer to double by default will affect the service. Can you customize a conversion (mapping) method according to the service characteristics? The answer is yes.

There are several ideas

Because Redis caches messages for up to 15 days (assuming) or up to how many. Can you truncate some of the high bits of the 41-bit timestamp to ensure that the timestamp length is sufficient for the Redis cache time period? Calculate the length log(15*24*60*60*1000)=30.2, about 30 binary digits can represent 15 days under the existing rules. Therefore, masking the first 11 bits of the 41-bit timestamp saves 11 bits of binary information. 63 bits can be represented by 52 bits.

However, this method has a fatal problem. When the 15-day time period expires, the timestamp becomes extremely small (new period), which causes the data Score value after the previous period to be larger than the new period. The message sequence is out of order, which will cause offline messages to be dropped. This is unacceptable!

Remove the 10-bit work machine ID and the highest bit of the serial number.

Removing these 11 bits does not affect the order of messages, but it may cause score values to conflict (same). Analyze the possibility of score conflicts.

A 12-bit serial number can represent 4096 numbers. Remove the highest bit, can represent 2048 numbers. Therefore, a single msgid generation node (dispatch module) needs more than 2048 messages per millisecond per user before score duplication can occur. This is basically impossible to happen.

(2) Remove the 10bit worker ID number, it takes the same millisecond, the same user receives messages in different dispatch nodes, and the score may conflict. Even if this happens, since we do a modulo 128 random distribution of the 12-bit sequence number (solving the binning problem), the probability of score collision is divided by 128*128 even if different disptch generates the same user msgid in the same millisecond. This probability is very low.

(3) Even if a score conflict occurs (two messages have the same score), it will at most cause pulling offline messages and pulling messages with the same score (originally pulling 10 offline messages at a time, the result may be pulled to 11), and it will not affect the business.

Therefore, it has no effect on the service by removing the highest bit of 10-bit working machine id and serial number to convert 63-bit (excluding sign bit) msgid into 52-bit score. At the same time, it solves the problem that redis sorted set loses precision.

Therefore, it has no effect on the service by removing the highest bit of 10-bit working machine id and serial number to convert 63-bit (excluding sign bit) msgid into 52-bit score. At the same time, it solves the problem that redis sorted set loses precision.

The above is what is the solution to the problem of missing precision in the Redis SortedSet structure score field shared by Xiaobian. If there is a similar doubt, please refer to the above analysis for understanding. If you want to know more about it, please pay attention to the industry information channel.

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.