Redis integer set cannot be downgraded? Why?

I believe some students have never heard of integer collection, because redis only provides five encapsulated objects to the outside world! Previously, we analyzed the three data structures of redis: List, Hash, and Zset from the internal structure of redis. Today we will analyze how the set data structure is stored internally.

Basic structure

In src/t_set.c we found such a piece of code

From this we can know that in set it is composed of Composed of two data structures: hashtable intset. Regarding other internal structures of redis, I specifically introduce them in [redis column]. Hashtable is not our protagonist today. Today we first analyze intset, commonly known as integer set.

As we can see from the above picture, I constructed two set collections, namely [commonset] and [cs]. The former stores strings and the latter stores numbers.

We looked at the underlying data structures of the next two collections through the object encoding key and found that one is a hashtable and the other is an intset. This also verifies our description of the basic structure of set above.

The five major types provided externally in redis are actually an abstract object of redis called redisobject. The internal data structure of our redis is mapped internally

##The internal data structure of the commonset and cs collections can be understood like this

When to use intset

You can simply think that as long as it is a number, it will be stored using the intset structure. I'm afraid I'm going to give you a slap in the face. In fact, this is not the case.

The following two conditions need to be met at the same time:

intset

The picture shows it very clearly. The encoding in intset has three values, which represent the data type of contents storage. Someone here may have questions. Isn’t the type of contents just int8_t? Why do you need encoding? The source code tracking here does have nothing to do with int8_t. And 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 represent the length of the contents array!

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

The value range of int8_t is [-128,127]. Similar to byte in Java, 1 byte is 8 bits. His value range is

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

Add element

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

juejin The key inside is intset.

Above we added 5 elements and the lengths of these five elements are all within 16! So the current intset's encoding=INTSET_ENC_INT16. -123 occupies the top 16 positions in contents.

So the length of the contents of the current five elements is 16*5=80;

Note that when set stores int type data, it is stored internally in order from small to large.

Type changes

I don’t know if you have considered the above questions, or if you have encountered them! Intset defaults to int16 bits, just like the five elements we added above. At this time, the sixth element we add is 65535 (32 bits). Then what will intset do at this time when the length of 16 bits is not enough for storage?

In addition, when we add the 6th element and delete 65535, will the structure be the same as before adding it? Let’s take a look at these two questions below! ! !

Upgrade

First, let’s take a look at the first question. It turns out that all five elements are 16 bits, and the 65535 added at this time is 32 bits in length. So can we directly append 32 bits to 65535?

The answer is definitely not possible. First of all, direct appending cannot guarantee the order of the array elements! Secondly, if the first five are 16 bits each and the sixth one is 32 bits, then there are no extra fields in the intset structure to mark. In other words, it is impossible to judge whether 16-bit or 32-bit should be parsed during parsing.

In order to facilitate parsing, redis will upgrade the entire contents when high length is added. It means to expand the entire contents first, and then refill the data

and add 65535

. First, the expansion can be determined based on the length. The number of elements is 6, and each occupancy is 32, so the contents length is 32*6=192. At this time, the first 80 bits of content remain unchanged

Old data shift

After enough space has been opened up, we can The old data is shifted. Here we start moving from the end of the original array. Before moving, we need to clarify the sorting position in the new array.

At this time, we first compare 321 to determine that his ranking is fifth in the new array, then he will occupy the range 128~159 in the new contents.

Finally the first 5 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 his value must be at both ends of the new array. Negative numbers are on the far left, positive numbers are on the far right

Downgrade

Then the second problem comes when the newly added 65535 is deleted. What should redis do? At this time, the actual element length is 16 bits, but the encoding is 32 bits. In my opinion, it should be downgraded!

But unfortunately redis does not, so please think about why not? If you were asked to implement it, how would you implement it? How to judge whether downgrading is needed is very difficult. We need to re-traverse whether the remaining elements are less than the current length, and the implementation complexity is O(N). This is one of the reasons why downgrading is not performed

You may say that traversing it again will be in the memory quickly anyway, so have you ever thought about upgrading and downgrading back and forth if you encounter an upgrade situation after downgrading? This reduces the performance of our program. We know that upgrading is necessary, so the strategy of downgrading redis here is to ignore it

Summary

##Related tutorial recommendations:

Redis tutorial

The above is the detailed content of Redis integer set cannot be downgraded? Why?. For more information, please follow other related articles on the PHP Chinese website!