One, foreword

Redis provides five data types: String, Hash, List, Set, and Zset. Understanding the characteristics of each data type is important for the development and operation of Redis.

The original resolution

The list in Redis is a data type that we often use. It can be applied to many scenarios depending on how it is used.

Second, the underlying analysis

1. Review of the previous section

In Redis 3.0, the List type can be implemented in two ways:

1. List objects implemented using ziplist.

A list object implemented using a linkedList.

The quickList data structure was added after version 3.2 to implement the List. Now let’s analyze the QuickList structure

2. Official description

Here’s what Redis says about QuickList:

    A doubly linked list of ziplists

    A generic doubly linked quicklist implementation
Copy the code

You can see that quickList is a bidirectional linked list, and a ziplist bidirectional linked list, that is, every node in quickList is a Ziplist. As you can see from the previous article, Ziplist itself is also a list of items that can be maintained in order, and items are stored in a contiguous block of memory. Does that mean quickList is a combination of compressed lists and double-entailed lists?

3. Structural analysis

Quicklist structure definition

/* * quicklist */
typedef struct quicklist {
    / / head node
    quicklistNode *head; 
    / / end nodes
    quicklistNode *tail; 
    // Number of entries in all ziplist entries
    unsigned long count; 
    // Number of quicklistNodes
    unsigned int len;   
    // The number of entries that can be saved in ziplist is controlled by the list-max-ziplist-size configuration item
    int fill : 16;       
    // The compression depth is controlled by the list-compressed-depth configuration item
    unsigned int compress : 16; 
} quicklist;
Copy the code

Quicklist structure attribute annotation

Note:

Fill: Indicates the number of entries that can be saved in the ziplist. The number is controlled by the list-max-ziplist-size configuration item

A negative number limits the size of a Ziplist in a quicklistNode, and a positive number limits the maximum size of a Ziplist in a quicklistNode.Copy the code
-5: Maximum storage space: 64 Kb <-- Do not set this value normally. -4: Maximum storage space: 32 Kb <-- Strongly not recommended. -3: Maximum storage space: 16 Kb <-- Not recommended. Maximum storage: 4 Kb <-- Recommended for positive integers means up to the value you set, and the current node is full. Usually performance is best at -2 (8 Kb size) or -1 (4 Kb size)Copy the code

Compress: indicates the compression depth, which is controlled by the list-compressed-depth configuration item

QuicklistNode represents a quickList node. All nodes in the middle of the quickList are compressed (LZF compression) except the two ends of the compress node.Copy the code

QuicklistNode structure definition

typedef struct quicklistNode {
    // The former node pointer
    struct quicklistNode *prev; 
    // After node pointer
    struct quicklistNode *next; 
    // Data pointer. The current node's data is not compressed, so it points to a Ziplist structure; Otherwise, it points to a quicklistLZF structure.
    unsigned char *zl;
    // The actual memory usage of the ziplist pointed to by zL. Note that if ziplist is compressed, the sZ value is still the ziplist size before compression
    unsigned int sz;  
    // The number of items contained in ziplist
    unsigned int count : 16;   
    // Whether ziplist is compressed. Value: 1 "ziplist" 2 "quicklistLZF
    unsigned int encoding : 2; 
    // Storage type, currently using a fixed value of 2 to indicate the use of ziplist storage
    unsigned int container : 2; 
    // Recompress =1 is set to recompress when the data is decompressed using a command like lindex
    unsigned int recompress : 1;
    unsigned int attempted_compress : 1; /* node can't compress; too small */
    unsigned int extra : 10; /* more bits to steal for future usage */
} quicklistNode;
Copy the code

QuicklistLZF structure definition

typedef struct quicklistLZF {
    unsigned int sz;  // The ziplist size after compression
    char compressed[];// Flexible array, store compressed ziplist byte array
} quicklistLZF;
Copy the code

4. Quicklist structure diagram

We can draw the quickList structure from the above structure definition:

Summary of key points

1. Double-endian linked lists

1. Double-ended linked list is convenient for push and POP operations at both ends of the table, but it has a large memory overhead;

2. In addition to saving data, two Pointers should be saved on each node of the double-ended list;

3. Each node of a double-ended linked list is a separate memory block, and the address is not continuous.

2. Compress lists

1. Ziplist has high storage efficiency because it is a whole block of continuous memory;

2. Ziplist is not conducive to modification operations, and every data change will cause a realLOC of memory;

3. When the Ziplist length is very long, one realloc may cause a large number of data copies, further reducing performance;

3, quicklist

1. A compromise between space efficiency and time efficiency;

2. Combining the advantages of double-endian linked lists and compressed lists;