Redis source code analysis -- QuickList of redis list implementation principle

In the last article 《Redis List implementation principle ziplist structure 》, We analyzed ziplist Structure how to use a complete piece of memory to store list data .

It also raises a question ： If the linked list is very long ,ziplist Every time a node is inserted or deleted, a large number of memory copies are required , This performance is unacceptable .

In this paper, quicklist How does the structure solve this problem , And implement Redis List type of .

quicklist The design idea of is very simple , Put a long ziplist Split into multiple short ziplist, Avoid large memory copies when inserting or deleting elements .

ziplist The form of storing data is more similar to array , and quicklist It is a real linked list structure , It consists of quicklistNode Nodes are linked , stay quicklistNode Use in ziplist Store the data .

Tips ： The following codes in this article, unless otherwise specified , All located in quicklist.h/quicklist.c in .

This article is about “ node ”, Unless otherwise specified , All means quicklistNode node , instead of ziplist The nodes in the .

Definition

quicklistNode Is defined as follows ：

typedef struct quicklistNode {
    struct quicklistNode *prev;
    struct quicklistNode *next;
    unsigned char *zl;
    unsigned int sz;             
    unsigned int count : 16;  
    unsigned int encoding : 2; 
    unsigned int container : 2; 
    unsigned int recompress : 1;
    unsigned int attempted_compress : 1;
    unsigned int extra : 10; 
} quicklistNode;

• prev、next： Point to the precursor node , Rear drive node .
• zl：ziplist, Responsible for storing data .
• sz：ziplist Number of bytes occupied .
• count：ziplist The number of elements .
• encoding：2 Represents that the node is compressed ,1 Means no compression .
• container： It's fixed at present as 2, On behalf of the use of ziplist Store the data .
• recompress：1 For temporary decompression （ For reading data, etc ）, Then compress it when necessary .
• extra： Reserved properties , Not used yet .

When the linked list is very long , The data access frequency of intermediate nodes is low . At this time Redis The intermediate node data will be compressed , Further save memory space .Redis Lossless compression algorithm is adopted —LZF Algorithm .

The compressed node is defined as follows ：

typedef struct quicklistLZF {
    unsigned int sz;
    char compressed[];
} quicklistLZF;

• sz： Compressed ziplist size .
• compressed： Compressed storage ziplist Byte array .

quicklist Is defined as follows ：

typedef struct quicklist {
    quicklistNode *head;
    quicklistNode *tail;
    unsigned long count;        
    unsigned long len;          
    int fill : QL_FILL_BITS;              
    unsigned int compress : QL_COMP_BITS;
    unsigned int bookmark_count: QL_BM_BITS;
    quicklistBookmark bookmarks[];
} quicklist;

• head、tail： Point to the head node 、 Tail node .
• count： Of all nodes ziplist The sum of the number of elements .
• len： Number of nodes .
• fill：16bit, Used to determine the node ziplist Whether is full .
• compress：16bit, Storage node compression configuration .

quicklist The structure of is shown in the figure 2-5 Shown .

Operational analysis

Insert elements into quicklist Head ：

int quicklistPushHead(quicklist *quicklist, void *value, size_t sz) {
    quicklistNode *orig_head = quicklist->head;
    // [1]
    if (likely(
            _quicklistNodeAllowInsert(quicklist->head, quicklist->fill, sz))) {
        // [2]
        quicklist->head->zl =
            ziplistPush(quicklist->head->zl, value, sz, ZIPLIST_HEAD);
        // [3]
        quicklistNodeUpdateSz(quicklist->head);
    } else {
        // [4]
        quicklistNode *node = quicklistCreateNode();
        node->zl = ziplistPush(ziplistNew(), value, sz, ZIPLIST_HEAD);

        quicklistNodeUpdateSz(node);
        _quicklistInsertNodeBefore(quicklist, quicklist->head, node);
    }
    quicklist->count++;
    quicklist->head->count++;
    return (orig_head != quicklist->head);
}

Parameter description ：

• value、sz： Insert the content and size of the element .

【1】 Judge head node ziplist Whether is full ,_quicklistNodeAllowInsert Function according to quicklist.fill Property to determine whether the node is full .

【2】head Node is not full , Call directly ziplistPush function , Insert elements into ziplist in .

【3】 to update quicklistNode.sz attribute .

【4】head Node full , Create a new node , Insert element into new node ziplist in , Then insert the node head into quicklist in .

It can also be in quicklist Insert the element at the specified position ：

REDIS_STATIC void _quicklistInsert(quicklist *quicklist, quicklistEntry *entry,
                                   void *value, const size_t sz, int after) {
    int full = 0, at_tail = 0, at_head = 0, full_next = 0, full_prev = 0;
    int fill = quicklist->fill;
    quicklistNode *node = entry->node;
    quicklistNode *new_node = NULL;
    ...
    // [1]
    if (!_quicklistNodeAllowInsert(node, fill, sz)) {
        full = 1;
    }

    if (after && (entry->offset == node->count)) {
        at_tail = 1;
        if (!_quicklistNodeAllowInsert(node->next, fill, sz)) {
            full_next = 1;
        }
    }

    if (!after && (entry->offset == 0)) {
        at_head = 1;
        if (!_quicklistNodeAllowInsert(node->prev, fill, sz)) {
            full_prev = 1;
        }
    }
    // [2]
    ...
}

Parameter description ：

• entry：quicklistEntry structure ,quicklistEntry.node Specifies the of the element to insert quicklistNode node ,quicklistEntry.offset Specify insert ziplist Index position of .
• after： Whether in quicklistEntry.offset Then insert .

【1】 Set the following flags according to the parameters .

• full： The node to be inserted ziplist Whether is full .
• at_tail： whether ziplist Tail insertion .
• at_head： whether ziplist Head insertion .
• full_next： Whether the rear drive node is full .
• full_prev： Whether the precursor node is full . Tips ： Head insertion refers to inserting the head of the linked list , Tail insertion refers to inserting the tail of the linked list .

【2】 Handle according to the above marks , The code is cumbersome , It's not listed here anymore .

The execution logic here is shown in table 2-2 Shown .

Conditions	Condition statement	Processing mode
!full && after	The node to be inserted is not full ,ziplist Tail insertion	Check again ziplist Whether the back drive element exists at the insertion position , If not, call ziplistPush Function insert element （ faster ）, Otherwise, call ziplistInsert Insert elements
!full && !after	The node to be inserted is not full , Not ziplist Tail insertion	call ziplistInsert Function insert element
full && at_tail && node -> next && !full_next && after	The node to be inserted is full , Tail insertion , The rear drive node is not full	Insert the element into the back drive node ziplist in
full && at_head && node -> prev && !full_prev && !after	The node to be inserted is full ,ziplist Head insertion , The precursor node is not full	Insert the element into the precursor node ziplist in
full && ((at_tail && node -> next && full_next && after) ||(at_head && node->prev && full_prev && !after))	The following conditions are met ：(1) The node to be inserted is full (2) Tail plug and the rear drive node is full , Or the header is inserted and the precursor node is full	Build a new node , Insert the element into the new node , And according to after Parameter to insert the new node quicklist in
full	The node to be inserted is full , And at the node ziplist Intermediate insertion	Split the data of the inserted node into two nodes , Then insert it into the new node after splitting

Let's just look at the implementation of the last scenario ：

    // [1]
    quicklistDecompressNodeForUse(node);
    // [2]
    new_node = _quicklistSplitNode(node, entry->offset, after);
    new_node->zl = ziplistPush(new_node->zl, value, sz,
                                after ? ZIPLIST_HEAD : ZIPLIST_TAIL);
    new_node->count++;
    quicklistNodeUpdateSz(new_node);
    // [3]
    __quicklistInsertNode(quicklist, node, new_node, after);
    // [4]
    _quicklistMergeNodes(quicklist, node);

【1】 If the node is compressed , Then unzip the node .

【2】 Split a new node from the inserted node , And insert the element into the new node .

【3】 Insert the new node into quicklist in .

【4】 Try merging nodes ._quicklistMergeNodes Try the following ：

• take node->prev->prev Merge into node->prev.
• take node->next Merge into node->next->next.
• take node->prev Merge into node.
• take node Merge into node->next. Merger conditions ： If the combined node size still meets quicklist.fill Parameter requirements , Then merge nodes . This scenario deals with B+ The node splitting and merging of the tree are somewhat similar .

quicklist Common functions are shown in table 2-3 Shown .

function	effect
quicklistCreate、quicklistNew	Create an empty quicklist
quicklistPushHead,quicklistPushTail	stay quicklist Head 、 Tail-insert element
quicklistIndex	Find the for a given index quicklistEntry node
quicklistDelEntry	Delete the given element

Configuration instructions

• list-max-ziplist-size： To configure server.list_max_ziplist_size attribute , This value is assigned to quicklist.fill. Take a positive value , Express quicklist Node ziplist How many elements can be stored at most . for example , Configure to 5, Represent each quicklist Node ziplist Include at most 5 Elements . Take a negative value , Express quicklist Node ziplist Maximum number of bytes . At this time , It can only take -1 To -5 These five values （ The default value is -2）, The meaning of each value is as follows ：undefined-5： Every quicklist nodes ziplist The size cannot exceed 64 KB.undefined-4： Every quicklist nodes ziplist The size cannot exceed 32 KB.undefined-3： Every quicklist nodes ziplist The size cannot exceed 16 KB.undefined-2： Every quicklist nodes ziplist The size cannot exceed 8 KB.undefined-1： Every quicklist nodes ziplist The size cannot exceed 4 KB.
• list-compress-depth： To configure server.list_compress_depth attribute , This value is assigned to quicklist.compress.undefined0： Indicates that the nodes are not compressed ,Redis Default configuration .undefined1： Express quicklist There are... At both ends 1 Nodes are not compressed , Middle node compression .undefined2： Express quicklist There are... At both ends 2 Nodes are not compressed , Middle node compression .undefined3： Express quicklist There are... At both ends 3 Nodes are not compressed , Middle node compression .undefined And so on .

code

ziplist Due to its compact structure , Efficient use of memory , So in Redis Is widely used in , Can be used to save a list of users 、 hash 、 Ordered sets and other data .

List types have only one encoding format OBJ_ENCODING_QUICKLIST, Use quicklist Store the data （redisObject.ptr Point to quicklist structure ）. The implementation code of list type is in t_list.c in , Readers can check the source code for more details of the implementation .

summary

• ziplist It's a compact data structure , Use a complete memory to store all the data of the linked list .
• ziplist Elements in support of different encoding formats , To maximize memory savings .
• quicklist Through segmentation ziplist To improve insertion efficiency 、 Performance of operations such as deleting elements .
• The coding format of the linked list is only OBJ_ENCODING_QUICKLIST.

This article is excerpted from the author's new book 《Redis Core principles and practices 》. Through in-depth analysis Redis 6.0 Source code , Sum up Redis Design and implementation of core functions . By reading this book , Readers can understand Redis Internal mechanism and latest features , And learn Redis Related data structures and algorithms 、Unix Programming 、 Storage system design , A series of knowledge such as distributed system architecture .

With the consent of the editor of the book , I will continue to publish some chapters of the book , As a preview of the book , Welcome to , thank you .

YuQue platform preview ：《Redis Core principles and practices 》