This is the second day of my participation in the August Text Challenge.More challenges in August

preface

  • Previously we have studied the list structure of redis five data structures. Inside it are linkedList and zipList structures. That’s what we’ve learned. I did not check it in combination with the operation before. In fact, there is a combination of the two, quickList

The structure evolution

  • Above we add a data with key zlist. The underlying layer is built using QuickList. In the ziplist section, we learned that redis uses Ziplist to store data for both hash and list basic data structures. In list we do quicklist. Here’s a quick reminder that QuickList is implemented internally with Ziplist.

linkedList

  • Before we start with quicklist, let’s briefly review the linkedList, which is a common two-line linkedList. We build our linked list with two Pointers.

C + + pointer

  • Redis runs on memory, and memory is very valuable so Redis feels a bit memory hungry after designing a two-line linked list. Because Pointers themselves also need to open up space. The placeholders vary according to the system. Here I summarize that a pointer placeholder is the basic bit of a system operation
  • What do I mean by the base place here? If you have a 64-bit system then a pointer is 64-bit or 8 bytes. If you have a 32-bit system then a pointer is 32 bits which is 4 bytes
  • That is, if I store N English letters in a bidirectional linked list in Redis, we know that each letter should be 1 byte. Then N elements are N listNodes. 2*(n-1) Pointers are needed to maintain N listNodes. On a 64-bit system, we need 129 times more space to store content. In this case, we only have N bytes of content, but we need it2*(N-1)*8+NBytes to build the listNode.
  • As the nodes increase, we waste more and more. So Redis combines Ziplist on the basis of bidirectional linked list for improvement.

Transitional reason

ziplist

  • In the Ziplist section, we know that Ziplist is a piece of continuous memory, which is an improved structure of Memory by Redis. Ziplist achieves high memory usage!

Linkedlist + ziplist benefits

Quicklist introduced

  • Quicklist was introduced after Redis3.2, and I’m using the redis6.4 convenient source code here.
  • Redis6.4 seems to have cancelled quickList. Structure. So I made a special release of 3.2. The specific version is redis3.2.4!!

True face of Lushan mountain

quicklist

  • Through his source code we clearly see his internal data structure! This should be familiar to you. Quicklist is basically our linkedList structure. The inside is just a bidirectional list with a little bit more properties

  • Does it feel like a linkedList by looking at a graph?

  • Let’s take a look at what each property in QuickList means

quicklistNode

  • Quicklist is just an abstract concept, and it’s the Members of QuickList, QuickList Nodes, that are responsible for storing the data.

  • The role of each attribute

  • From the above attributes, we can also know that the data structure in the Node is ziplist. On the basis of Ziplist will be in compression to achieve higher efficiency of memory use!

  • Here we don’t need to know too much about compression! The main purpose is to encode something that you can’t actually use while redis is decoding it. The reCOMPRESS attribute is used to mark the duration of the decoding operation.

insert

  • Now that we know the basic structure of QuickList, let’s look at what happens when we insert! We also mentioned above in the redis.conf configuration filelist-max-ziplist-sizeProperty is used to set the ziplist store size Settings for each node in the QuickList.
Attribute values role
– 1 The ziplist size of each quicklistNode cannot exceed 4kb
2 – The ziplist size of each quicklistNode cannot exceed 8kb
– 3 The ziplist size of each quicklistNode cannot exceed 16kb
4 – The ziplist size of each quicklistNode cannot exceed 32kb
– 5 The ziplist size of each quicklistNode cannot exceed 64kb
int The maximum number of entries in ziplist

Insert on both ends

  • The first case is that the data we need to insert is on both ends. We set it up in the redis.conf configuration file as shown abovelist-max-ziplist-size: 2. Indicates that the maximum number of entries in the ziplist node is 2. At this point we have two contents stored in the head node and one node stored in the tail node!
  • At this point if we want to add an element to the header it’s obj1. As you can imagine, redis will create a ziplist structure that contains obj1, adding the ziplist to the head of the list

  • When obj2 joins the tail, because the number of nodes in the tail is 1 and has not yet peaked at 2, it joins directly. The final effect is shown below

The middle insert

St =>start: Insert ziplistInsert=>operation: Insert subziplistInsert into ziplist =>operation: Split the ziplist into two ziplists and add insertNear=>operation: Insert newZipInsert=>operation: Condition: Indicates whether the Ziplist can contain headtailCond. =>condition: Indicates that the ziplist is inserted at both ends of the Ziplist. NearheadtailCond =>condition: Whether the adjacent ziplist can contain e=>end: St ->cond cond(yes)->ziplistInsert cond(no)->headtailCond(yes)->nearheadtailCond (no)->subziplistInsert  nearheadtailCond(yes)->insertNear nearheadtailCond(no)->newZipInsertCopy the code

conclusion

reference

LZF compression algorithm