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.
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
\[-2^{7} \sim 2^{7}-1 \\that is \\
-128 \sim 127
\]
sadd juejin -123 sadd juejin -6 sadd juejin 12 sadd juejin 56 sadd juejin 321
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
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
Summary
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!