Redis, do you understand the list

Preface

• We have learned before redis Of the five data structures list structure . Its interior is linkedList and zipList Two structures . This is what we have learned . I didn't check it in combination with the operation before . In fact, there is a combination of the two quickList

Structural evolution

• We added a key by zlist The data of . adopt object encoding zlist Viewing the bottom layer is through quicklist To build . Before that ziplist The chapter summarizes what we learned in redis in hash and list The basic data structures all use ziplist Storing data . stay list We do quicklist. Here we explain in advance quicklist Inside is based on ziplist To achieve .

linkedList

• At the beginning quicklist Before, let's simply sort out what we learned before linkedList , He is a common
  Double linked list
  . Complete the construction of our linked list through two pointers .

C++ The pointer

• redis It runs on memory , And memory is very valuable, so redis After designing the double-line linked list, I feel a little memory consumption . Because the pointer itself also needs to open up space . According to different systems, the pointer occupies different positions . Here I have summarized that a pointer placeholder is a basic bit of system operation

• What does the basic bit mean here ？ Joining you is 64 A pointer to the bit system is 64 Bitwise is 8 Bytes . If you are 32 A pointer to the bit system is 32 Bitwise is 4 Bytes

• That is, if I were redis Store... In a medium to two-way linked list N English letters , We also know that a letter should account for 1 Bytes . So this N One element is N Of listNode .  So keep N individual listNode In the middle 2*(N-1) A pointer to the . stay 64 In the bit system, that is, we need to open up nearly 129 Times more space to store content . In the above case, we only have N Bytes of content , But I need
  2*(N-1)*8+N
  Bytes to build listNode.

• With the increasing number of nodes, we waste more and more . therefore redis On the basis of two-way linked list, it combines ziplist Make improvements .

Transition reasons

ziplist

• stay ziplist In the chapter we know ziplist It's a piece of continuous memory , yes redis An improved structure of memory .ziplist High memory utilization is realized ！

linkedlist+ziplist benefits

quicklist introduce

• quicklist Is in redis3.2 And then introduced , Here's what I'm using redis6.4 Convenient source code doesn't seem to have quicklist Source code .

• Later, after reading redis6.4 Seems to have cancelled quicklist .  structure . So I made another special 3.2 Version of . What is specific here is redis3.2.4 edition ！！！

The true face of Lushan Mountain

quicklist

• Through his source code, we can clearly see his internal data structure ！ This should be familiar to you .quicklist It can be said that it was before us linkedList  structure . The internal is a two-way linked list, but there are a little more attributes

• Through the diagram is not feeling and linkedList equally .

• Now let's see quicklist The meaning of each attribute in

quicklistNode

• quicklist It's just an abstract concept , What is really responsible for data storage is the composition quicklist Members of quicklistNode .

• The role of each attribute

• Through the above properties , We can also learn node The data structure in the node is ziplist . stay ziplist On this basis, it will be compressed to achieve higher memory efficiency ！

• We don't need to know much about compression here ！ The main purpose is a kind of coding , This kind of coding can't really be used during use redis Will decode . During the decoding operation, it is through recompress Property to mark .

insert

• In understanding quicklist After the basic structure, we are looking at insert What will happen to the structure ！ We also mentioned above in redis.conf In profile
  list-max-ziplist-size
  Property is used to set quicklist In each node in the ziplist The size of the storage is set .

Insert both ends

• The first case is that the data we need to insert is at both ends . As shown in the figure above, we are redis.conf In the configuration file
  list-max-ziplist-size: 2
   . Represents the internal node ziplist in entry The maximum number is 2 . At this point we head Two contents have been stored in the header node ,tail The tail node stores 1 Nodes ！

• At this time, if we want to add an element to the header, it is obj1 .  It's conceivable that we can't join , This is the time redis Will recreate a ziplist Structure and contains obj1 , Will create a new ziplist After adding to the head of the linked list

• and obj2 When adding a tail node , Because the number of nodes at the tail node is 1 It hasn't reached its peak yet 2, So I just joined . The final result is as follows

Intermediate insertion

st=>start: Insert
ziplistInsert=>operation:  towards ziplist Insert
subziplistInsert=>operation:  Will be ziplist Split two ziplist,  Add... At the corresponding position
insertNear=>operation:  Insert adjacent ziplist in
newZipInsert=>operation:  newly build ziplist Insert
cond=>condition: ziplist Whether it can accommodate
headtailCond=>condition:  The insertion position is ziplist Both ends
nearheadtailCond=>condition:  adjacent ziplist Whether it can accommodate
e=>end:  a happy day

st->cond
cond(yes)->ziplistInsert
cond(no)->headtailCond(yes)->nearheadtailCond
headtailCond(no)->subziplistInsert
nearheadtailCond(yes)->insertNear
nearheadtailCond(no)->newZipInsert


summary

reference

[lzf Compression algorithm ](