Redis source code and design analysis -- 7. Quick list

Redis Quick list

1. Introduce

Previously, we introduced the linked list structure and the compressed list structure , They are the underlying implementation of list keys , But the additional space of the linked list is a little high , because prev and next The pointer will take up part of the space （64 Bit system occupancy 8 + 8 = 16 byte ）. And each node of the linked list allocates memory separately , Will increase the fragmentation of memory .

So in redis-3.2 Version start ,Redis Use quicklist As the underlying implementation of the list key .

2. quicklist Realization

quicklist It's actually zipList and linkedList Mixture , It is the zipList Put it in linkedList In each node of , Achieve compact storage .

2.1 quicklist Head structure

typedef struct quicklist {
    
    //  Point to the head ( Leftmost )quicklist Pointer to node 
    quicklistNode *head;

    //  Point to the tail ( Far right )quicklist Pointer to node 
    quicklistNode *tail;

    // ziplist Node counter 
    unsigned long count;

    // quicklist Node counter 
    unsigned int len;

    //  preservation ziplist Size , Profile settings , Occupy 16bits
    int fill : 16;

    //  Node compression , Profile settings , Occupy 16bits,0 Means no compression 
    unsigned int compress : 16;
} quicklist;

among fill and compress Properties are configurable , stay redis.conf In file .

• fill The configuration corresponding to the property ：list-max-ziplist-size -2
  • When the number is negative , Means ：
    • -1 Represent each quicklistNode Node ziplist The byte size cannot exceed 4kb.
    • -2 Represent each quicklistNode Node ziplist The byte size cannot exceed 8kb（ Default ）.
    • -3 Represent each quicklistNode Node ziplist The byte size cannot exceed 16kb.
    • -4 Represent each quicklistNode Node ziplist The byte size cannot exceed 32kb.
    • -5 Represent each quicklistNode Node ziplist The byte size cannot exceed 64kb.
  • When the number is positive , Means ：
    • Express ziplist The structure can contain entry Maximum number of , The maximum value is 2 ^ 15.
  • compress The configuration corresponding to the property ：list-compress-depth 0
  • 0 Means no compression （ Default ）.
  • 1 Express quicklist At both ends of the list 1 Nodes are not compressed , Middle node compression .
  • 2 Express quicklist At both ends of the list 2 Nodes are not compressed , Middle node compression .
  • 3 Express quicklist At both ends of the list 3 Nodes are not compressed , Middle node compression .
  • The maximum value is 2 ^ 16.

2.2 quicklist The node structure

typedef struct quicklistNode {
    
    struct quicklistNode *prev;     // Precursor node pointer 
    struct quicklistNode *next;     // Subsequent node pointer 

    //  When the compressed data parameter is not set, it points to a ziplist structure , Set the compressed data parameter to quicklistLZF structure 
    unsigned char *zl;

    //  Compressed list ziplist The total length of 
    unsigned int sz;

    // ziplist Number of nodes in , Occupy 16 bits length 
    unsigned int count : 16;

    //  Indicates whether to use LZF Compression algorithm compression quicklist node ,1 It means not to use ,2 Said the , Occupy 2 bits length 
    unsigned int encoding : 2;

    //  It means a quicklistNode Whether nodes adopt ziplist Structure holds data ,2 Said the ,1 It means not to use , The default is 2, Occupy 2bits length 
    unsigned int container : 2;

    //  Mark quicklist Whether it has been compressed , Occupy 1bit length 
    //  If recompress by 1, Wait to be compressed again 
    unsigned int recompress : 1;

    //  Used during testing 
    unsigned int attempted_compress : 1;

    //  Extra extension bits , Occupy 10bits length 
    unsigned int extra : 10;
} quicklistNode;

2.3 Compressed ziplist

typedef struct quicklistLZF {
    
    //  Said by LZF After the algorithm compresses ziplist Size 
    unsigned int sz;

    //  Save the compressed ziplist Array of , Flexible array 
    char compressed[];
} quicklistLZF;

2.4 quicklistEntry

//  management quicklist in quicklistNode In nodes ziplist The structure of information 
typedef struct quicklistEntry {
    
	//  Point to the quicklist The pointer to 
    const quicklist *quicklist;
    //  Point to the quicklistNode Pointer to node 
    quicklistNode *node;
    //  Point to the present ziplist Pointer to structure  
    unsigned char *zi;
     //  Point to the present ziplist String of structure vlaue member  
    unsigned char *value;
    //  Point to the present ziplist Integer of structure value member  
    long long longval;            
    //  Save the current ziplist The number and size of bytes of the structure 
    unsigned int sz;
    //  Save relative ziplist The offset 
    int offset;
} quicklistEntry;

3. Common operations

3.1 Insert

quicklist You can choose to insert in the head or tail , Corresponding API yes quicklistPushHead and quicklistPushTail：

int quicklistPushHead(quicklist *quicklist, void *value, size_t sz) {
    
	//  Backup header node address 
    quicklistNode *orig_head = quicklist->head;

    //  If ziplist You can insert entry node 
    if (likely(
            _quicklistNodeAllowInsert(quicklist->head, quicklist->fill, sz))) {
    
        quicklist->head->zl =
        	//  The nodes push To the head 
            ziplistPush(quicklist->head->zl, value, sz, ZIPLIST_HEAD);
        //  to update quicklistNode Record ziplist The size of sz
        quicklistNodeUpdateSz(quicklist->head);
    } else {
    
    	//  If you cannot insert entry Node to ziplist
    	//  Create a new quicklistNode node 
        quicklistNode *node = quicklistCreateNode();

        // take entry node push To the newly created quicklistNode In nodes 
        node->zl = ziplistPush(ziplistNew(), value, sz, ZIPLIST_HEAD);

		//  to update ziplist Size sz
        quicklistNodeUpdateSz(node);
        //  Insert the newly created node in front of the head node 
        _quicklistInsertNodeBefore(quicklist, quicklist->head, node);
    }
    //  to update quicklistNode Counter 
    quicklist->count++;
    //  to update entry Counter 
    quicklist->head->count++;
    //  If you change the header node pointer, it returns 1, Otherwise return to 0
    return (orig_head != quicklist->head);
}

int quicklistPushTail(quicklist *quicklist, void *value, size_t sz) {
    
    quicklistNode *orig_tail = quicklist->tail;

    //  If ziplist You can insert entry node 
    if (likely(
            _quicklistNodeAllowInsert(quicklist->tail, quicklist->fill, sz))) {
    
        quicklist->tail->zl =
       		//  The nodes push To the tail 
            ziplistPush(quicklist->tail->zl, value, sz, ZIPLIST_TAIL);
        //  to update quicklistNode Record ziplist The size of sz
        quicklistNodeUpdateSz(quicklist->tail);
    } else {
    
    	//  Create a new quicklistNode node 
        quicklistNode *node = quicklistCreateNode();

        //  take entry node push To the newly created quicklistNode In nodes 
        node->zl = ziplistPush(ziplistNew(), value, sz, ZIPLIST_TAIL);

		//  to update ziplist Size sz
        quicklistNodeUpdateSz(node);
        //  Insert the newly created node after the tail node 
        _quicklistInsertNodeAfter(quicklist, quicklist->tail, node);
    }
    //  to update quicklistNode Counter 
    quicklist->count++;
    //  to update entry Counter 
    quicklist->tail->count++;
    //  If you change the tail node pointer, it returns 1, Otherwise return to 0
    return (orig_tail != quicklist->tail);
}

Reference material ：

《Redis Design and implementation 》

Redis Source code analysis and comments