Redis- Structure – Quick list

Note: The Redis source code version analyzed in this series is github.com/Sidfate/red… , is the latest version of the article published.

Prospects for the feed

Before introducing quick lists, it is recommended that you take a look at Ziplist and AdList, especially Ziplist (see my article “Redis- Structure – Compressed Lists”). I will explain the adlist briefly below.

adlist

Adlist is just a regular bidirectional list implementation, show you source code:

    typedef struct listNode {
        struct listNode *prev;
        struct listNode *next;
        void *value;
    } listNode;
    
    typedef struct list {
        listNode *head;
        listNode *tail;
        void *(*dup)(void *ptr);
        void (*free) (void *ptr);
        int (*match)(void *ptr, void *key);
        unsigned long len;
    } list;
Copy the code

If you are not familiar with the above structure, you can find it on the Internet or in any data structure book, I won’t go into the details here.

quicklist

In the early version of Redis, the list key is implemented in two ways, ziplist is used when the number of elements is small, and adlist is used when the number of elements is large. However, in the version after 3.2, quickList is used instead:

    > lpush test_list 1
    (integer) 1
    > object encoding test_list
    "quicklist"
Copy the code

Why design a QuickList specifically to redefine? Next from the source point of view to interpret. Redis source code comments:

quicklist.c – A doubly linked list of ziplists

Then look at the source code structure implementation:

    typedef struct quicklistNode {
        struct quicklistNode *prev;
        struct quicklistNode *next;
        unsigned char *zl;         
        unsigned int sz;             /* Total number of bytes used by ziplist */
        unsigned int count : 16;     /* Number of ziplist elements */
        unsigned int encoding : 2;   /* Compressed, 2 indicates compressed, 1 indicates native */
        unsigned int container : 2;  
        unsigned int recompress : 1; 
        unsigned int attempted_compress : 1; 
        unsigned int extra : 10; 
    } quicklistNode;
    
    typedef struct quicklist {
        quicklistNode *head;
        quicklistNode *tail;
        unsigned long count;        /* Sum of all ziplists elements */
        unsigned long len;          /* Number of quicklistNodes */
        int fill : 16;              
        unsigned int compress : 16; 
    } quicklist;
Copy the code

For detailed explanation of the fields, please refer to the field description section at the end of this article.

So you see why I started with ziplist and Adlist, because quickList is actually a ziplist adlist. No picture to say JB:

Now that we know the structure, back to our original question, why is the structure of QuickList designed this way? Quicklist balances the pros and cons of Ziplist and AdList:

• Bidirectional linked lists are easy to push and pop on both sides of the table, but they are expensive in memory. First, it holds two Pointers on each node in addition to data; Secondly, each node of the bidirectional linked list is a separate memory block, and the address is not continuous, so the number of nodes is easy to generate memory fragmentation, which is not conducive to memory management.
• Ziplist is efficient because it is a single block of contiguous memory. However, it is not conducive to modification operations, as each data change causes an in-memory realLOC. Especially when the Ziplist length is very long, one realloc may result in a large number of data copies, further reducing performance.

But the question remains: how long is the Ziplist contained in a QuickList Node? If the length is small, with the ordinary bidirectional linked list is about the same, or memory fragmentation problem; As the size increases, the ziplist on each QuickList node requires large chunks of contiguous memory, and the efficiency of operating memory decreases. So this length must be a balance value. It is an option provided by Redis. The default value is -2.

# -5: max size: 64 Kb  <-- not recommended for normal workloads
# -4: max size: 32 Kb  <-- not recommended
# -3: max size: 16 Kb  <-- probably not recommended
# -2: max size: 8 Kb   <-- good
# -1: max size: 4 Kb   <-- good
# Positive numbers mean store up to _exactly_ that number of elements
# per list node.
# The highest performing option is usually -2 (8 Kb size) or -1 (4 Kb size),
# but if your use case is unique, adjust the settings as necessary.
list-max-ziplist-size -2
Copy the code

The only thing to note is that when list-max-ziplist-size is set to a positive number, it indicates the number of elements stored in each list node.

The compression mechanism

If you look closely at the source code structure of QuickList, you may also notice that the word COMPRESS appears a lot. This is because Redis provides a compression mechanism for QuickList.

When the QuickList is long, the data that is most easily accessed is likely to be on both ends, with the data in the middle being accessed infrequently (and with poor performance). If this is the case, Redis also provides an option to compress the data nodes in the middle for further memory savings. The Redis configuration parameter, list-compressed-depth, is used to do this.

# Lists can also be compressed. The depth of compression is the depth at which ziplist nodes are not needed at the beginning of the list (explained below). In order to perform fast push/ POP operations, the head and tail of the list are usually uncompressed. # 0: the compression mechanism is disabled. # 1: The compression depth 1 means that all internal nodes except the head and tail are compressed. For example: # [head]->node->node->... ->node->[tail] # Since [head], [tail] is never compressed, their direct nodes are compressed later. # 2: [head]->[next]->node->node->... ->node->[prev]->[tail] # 2 uncompress head, head->next, tail->prev and tail. # 3: [head]->[next]->[next]->node->node->... ->node->[prev]->[prev]->[tail] # list-compress-depth 0Copy the code

This parameter is the default is 0, that is, without compression, Redis for internal node quicklist compression algorithm, using LZF – a lossless compression algorithm, interested can look at the zh.wikipedia.org/wiki/LZFSE.

Structure field details

Most of the fields in the source structure have been explained in the previous section, but there are still some fields that I will explain in general here.

First add a structure, quicklistLZF, which will appear in the following instructions:

    typedef struct quicklistLZF {
        unsigned int sz; /* LZF size in bytes*/
        char compressed[];
    } quicklistLZF;
Copy the code

One of the things I find missing from many articles on the web is that the official explanation states that quicklistNode is a 32-byte structure, which should be for 64-bit systems because prev, Next, and ZL are Pointers. It is 8 bytes on a 64-bit system, and the following structure is the same.

It is also important to note that the QuickList structure is 40 bytes on a 64-bit system, but the length I calculated above is 36 bytes. This involves the structure’s byte alignment convention, which is also intended to improve the efficiency of data reading.

Why is the count in a quicklistNode 16 bits?

We already know that the ziplist size is limited by the list-max-ziplist-size parameter. There are two cases in terms of positive and negative values:

• When this parameter is positive, it exactly represents the maximum number of items contained in the ziplist that zl points to in a quicklistNode structure.list-max-ziplist-sizeThe parameter is stored by the QuickList structure’s Fill field, which is 16 bits, so the value it can express can be represented in 16 bits.
• When this parameter is negative, the maximum ziplist length that can be represented is 64 Kb. Each data item in Ziplist requires at least 2 bytes to represent (see Redis- Structure – Compressed List). Therefore, the number of items in ziplist should not exceed 32 KILobytes; 16 bits is sufficient.