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

This article mainly shows you "what is the reason why the redis integer set cannot be degraded". The content is simple and easy to understand, and the organization is clear. I hope it can help you solve your doubts. Let Xiaobian lead you to study and learn "what is the reason why the redis integer set cannot be degraded" this article.

basic structure

In src/t_set.c we find this code

There are two data structures in set: hashtable+intset. For other internal structures of redis, I specifically introduced them in the redis column. hashtable is not our protagonist today, we first analyze intset commonly known as integer set today.

From the above figure we can see that I have constructed two sets called [commonset] and [cs]. Two collections, the former storing strings and the latter storing numbers exclusively.

We look at the underlying data structure of the next two collections through object encoding key and find that one is hashtable and the other is intset. This also validates our description of the basic structure of set above.

In redis, five types are provided to the outside world. In fact, an abstract object called redisobject is all redis. internally mapped our redis internal data structure

For commonset and cs, the internal data structure can be roughly understood as follows

When to use intset

You can assume that any number will be stored using intset structures, but I'm afraid I'm going to give you a hard time. Actually, it's not.

The following two conditions must be met simultaneously:

intset

The figure shows clearly that encoding in intset has three values, which represent the data type stored in contents. Some people may wonder if the type of contents is int8_t. Why do we need encoding? Here through the source code tracking internal indeed has nothing to do with int8_t. The default type of data is int16_t. There is no need to explain too much about length here. Remember that the number of contents elements does not mean the length of the contents array!

Students who understand intset all know that in the three value ranges of encoding, the upgrade operation is involved! Before we talk about upgrading, let's first understand how the value range of int in C and C++ is defined

int8_t has a value range of [-128,127]. It is similar to java byte, which takes up 1 byte, that is, 8 bits. His range is

\[-2 ^{7} \sim 2^{7}-1 \\that is\\ -128 \sim 127 \]

add element sadd juejin -123sadd juejin -6sadd juejin 12sadd juejin 56sadd juejin 321

Juejin is the intset inside this key.

Above we added 5 elements and the length of these five elements are within 16! So the encoding of the current intset =INTSET_ENC_INT16. - 123 is in the top 16 of the contents.

Therefore, the current five elements account for the length of contents is 16*5=80 ;

Note that set stores int data internally in descending order.

Type change

I don't know if you've ever considered the above question, or if you've ever encountered it! intset defaults to int16 bits, just like the five elements we added above. At this point we add the 6th element 65535(32 bits). Then the length of 16 bits is not enough to store at this time what intset will do!

In addition, when we add the sixth element and delete 65535, the structure is the same as before! Let's take these two questions and find out!!

upgrade

Let's look at the first question first. The original five elements are 16 bits can be satisfied, this time added 65535 is 32 bits in length. Can we add 32 bits to 65535?

The answer is definitely not, first of all, direct addition cannot guarantee the size order of array elements! Second, if the first five are 16 bits and the sixth is 32 bits, then there are no extra fields in the intset structure to mark. That is to say, when parsing, it is impossible to determine whether 16-bit or 32-bit should be parsed.

Redis updates the entire contents for ease of parsing when there is a high length addition. This means that the entire contents will be expanded first, and then the data will be refilled.

Joined 65535

First of all, according to length, the number of elements after expansion can be determined to be 6, each occupying 32, so the length of contents is 32*6=192. The first 80 bits remain unchanged.

old data shift

Once we have enough space, we can shift the old data. Here we start at the end of the original array, and we need to specify the sort position in the new array before moving.

At this point, we first compare 321 to determine that it ranks fifth in the new array, so it will occupy the interval 128~159 in the new contents.

Eventually the first five elements will be moved.

Finally, fill in the newly added elements. When an upgrade occurs, it must be because the length of the new element is greater than the original length. Then its values must be at both ends of the new array. Negative numbers on the far left, positive numbers on the far right.

downgrade

The next question is what to do when the newly added 65535 is deleted redis. At this time, the actual element length of 16 bits can be satisfied, but at this time encoding is 32 bits. According to my opinion, it should be demoted in the realization!

But unfortunately redis doesn't, so think about why not? How would you do it if you could?

Why don't you get demoted?

When we add more than the current length of the element we easily know that we need to upgrade at this time, but when we delete a piece of data we how to determine whether we need to downgrade is very difficult, we need to re-traverse whether the remaining elements are less than the current length, to achieve complexity O(N). that's one of that reason why there's no demoting.

You might say it's in memory very quickly, but have you ever thought that if you downgrade and then encounter an upgrade, then the upgrade and downgrade will reduce the performance of our program? We know that promotion is necessary, so the strategy of demoting redis is to ignore it.

summary

The above is "redis integer set can not be demoted what is the reason" all the content of this article, thank you for reading! I believe that everyone has a certain understanding, hope to share the content to help everyone, if you still want to learn more knowledge, welcome to 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.