[redis advanced ziplist] if someone asks you what is a compressed list? Please dump this article directly to him.

We're working 、 Contact in learning Redis when , I've almost heard of the compressed list data structure , But what exactly does it do ？ How it is realized ？ Not many people have a deep understanding of , however ... The interviewer may ask .

The following are based on Redis6.0

One 、 What is? ZipList

Redis The use of memory is extremely demanding , When you read Redis Source code time , You'll find out , When we use the same data structure to store data , A small amount of data may be a data structure with a very compact memory , Because the memory is compact , So when we insert data , It is often necessary to reapply memory , Then move the metadata to the new memory and insert it , When the amount of data is large , The overhead of this structure caused by copying the original data is far greater than its memory advantage .

ZipList Is that when 【zset】 and 【hash】 A data structure used by container objects when the number of elements is small or the length of elements is short . It's a continuous memory space , Each element is next to each other , There is no memory gap in the middle . At the same time, it is also a specially coded two-way linked list , Its design goal is to improve memory storage efficiency ,

ziplist Can be used to store strings or integers , Where integers are encoded in the true binary representation , Instead of encoding into a sequence of strings . It can take O(1) The time complexity of the table is provided at both ends of the table push and pop operation

Redis Use ZipList Of Default Conditions

• The number of key value pairs is less than 128 individual
• The length of each element value in all key value pairs 【 Less than or equal to 】64 byte

Here we are only concerned with the second condition 【 The length of each element value in all key value pairs is less than or equal to 64 byte 】 Make a demonstration , The number of key value pairs is less than 128 You can try it yourself . Shown below , Current bytes key by fenglan This zset Structure inserted value exceed 64 Byte time ,zset The data structure will be upgraded to a jump table SkipList.

Upgrade to SkipList

Two 、ZipList data structure

ZipList data structure

uint32_t It means a int type , Occupy 32 position , That is to say 4 byte . uint16_t Occupy 16 position , It's only used. int It's low 16 position ,2 byte . This definition saves memory space .

The picture above is ZipList The overall data structure of

• zlbytes：ZipList The total number of bytes
• zltail： The offset of the last element , Used to quickly locate to the last node
• zllen： How many elements are there in all , That is, the length of the element .
• zlend：ZipList End flag bit , Constant value 255

among zltail This field is used to implement the double linked list structure , It can quickly locate the last element , Traverse forward from the last element .

Redis establish ZipList The source code is as follows , We can see from the source code ,Redis Yes 1 individual uint32_t、1 individual uint16_t、1 individual uint8_t Of memory space , It is in line with our above figure except entry All memory space required for data other than .

establish ZipList

Next, let's take a look at the specific data storage structure 【entry】

typedef struct zlentry {
    unsigned int prevrawlensize; /*  Previous entry Of prevrawlen Field ( That is, the following field ) Size */
    unsigned int prevrawlen;     /*  Previous entry Byte length of  */
    unsigned int lensize;        /*  At present entry Of len Field size */
    unsigned int len;            /*  At present entrty Byte length of  */
    unsigned int headersize;     /* prevrawlensize + lensize Size */
    unsigned char encoding;      /*  Element type encoding */
    unsigned char *p;            /*  Pointer to the first address of the specific data content */
} zlentry;

Why ZipList Record the previous entry The length of ？ The answer is because when ZipList When traversing backwards , This field allows you to quickly navigate to the location of the next element .

among prevrawlen It's a longer int Type data , When the string length is less than 254 when , Use a byte to represent , Greater than or equal to 254 when Use 5 In bytes , The first ground connection is 254, The remaining four bytes represent the length of the string .

3、 ... and 、 Update elements

1. New elements

because ZipList Memory is compact , So to insert a new element, you need to expand the memory ,Redis Would call ziplistResize Method to reapply memory space , Then put the original list into the new memory space at one time .

2. update cascade

entry The length of the previous element is saved in (prevrawlen), It's a variable length integer , So if the previous element of the current element changes ( Delete... For example ), that , Of the current element prevrawlen The fields will also change . Of the current element prevrawlen Change , The next element of the current element prevrawlen It's going to change , This triggers a massive update cascade , When there are many elements , Even affect Redis Whether it can normally provide external services . therefore ziplist Too many elements not suitable for storage .

Four 、 summary

• Redis To save memory space ZipList,zset and hash The number of container objects in the system default key value pairs is less than 512 The length of each element value in one or all key value pairs 【 Less than or equal to 】64 byte , Use compressed list (ziplist) For storage , Otherwise, it will be upgraded to SkipList.
• ZipList It's a two-way list .
• A compressed list is a contiguous block of memory , Each element is next to each other , There is no memory gap in the middle
• ziplist Can be used to store strings or integers , Where integers are encoded in the true binary representation , Instead of encoding into a sequence of strings . It can take O(1) The time complexity of the table is provided at both ends of the table push and pop operation
• ZipList Of Entry The length of the previous element is recorded in so that the bidirectional linked list can be traversed backwards .
• Because the memory is very compact , So you need to re apply for memory when adding new elements .
• Maybe when the element changes , Cascading updates occur .

Originality is not easy. , Three in a row ！！

Search on wechat ： The wind billows under the clouds Study 、 Interview information 、 Deep content 、 Source code reading 、 performance optimization 、 Industry Secrets 、 Career planning is everything .