Earlier versions of Redis stored list data structures using ziplist, a compressed list, and linkedlist, a common two-way linkedlist. That is, ziplist is used when there are few elements and linkedlist is used when there are many elements.

The quick list is ziplist+ LinkedList

A quick list

typedef struct quicklist {
    quicklistNode *head; / / the head pointer
    quicklistNode *tail; / / the tail pointer
    unsigned long count; // The total number of nodes in the compressed list.
    unsigned long len;   // Quick list number of nodes.
    int fill : QL_FILL_BITS; // The value of list-max-ziplist-size is used to set the size of the compressed list node. /* fill factor for individual nodes */
    unsigned int compress : QL_COMP_BITS; /* depth of end nodes not to compress; 0=off */
    unsigned int bookmark_count: QL_BM_BITS;
    quicklistBookmark bookmarks[];
} quicklist;

Copy the code

The value is 14 bits on a 32-bit machine or 16 bits on a 64-bit machine. The value of the list-compressed-depth parameter is used to set the compression depth. The default compression depth of the quick list is 0, that is, no compression. To support fast push/ POP operations, the first and last nodes of the fast list are not compressed, and the compression depth is 1. If the compression depth is 2, it means that the first and second nodes at the beginning and end of the quick list are not compressed.

  • Bookmark_count: 4 bits,
  • Bookmarks array length. Bookmarks: This is an optional field that is used when the quick list reallocates memory and does not take up space when it is not used.

Quick list node



typedef struct quicklistNode {
    struct quicklistNode *prev;
    struct quicklistNode *next;
    unsigned char *zl;
    unsigned int sz;             /* ziplist size in bytes */
    unsigned int count : 16;     /* count of items in ziplist */
    unsigned int encoding : 2;   /* RAW==1 or LZF==2 */
    unsigned int container : 2;  /* NONE==1 or ZIPLIST==2 */
    unsigned int recompress : 1; /* was this node previous compressed? * /
    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
  • Z1: Data pointer to a Ziplist structure if the current node’s data is not compressed, otherwise, it points to a quicklistLZF structure.
  • Sz: represents the total size of the data pointed to by ZL. Note that if the data is compressed, it represents the size of the data before compression.
  • Count: 16 bits, indicating the number of data items in the current quick list node.
  • Encoding: Indicates whether the data of the current node is compressed. Currently, there are only two values: 1: the data is not compressed. 2 means it is compressed, and LZF compression algorithm is used.
  • The container:
  • Recompress: When you want to extract the compressed data using a command like lindex, set recompress=1 and wait for the opportunity to compress the data.

The default internal length of a Ziplist in QuickList is 8K bytes

Quicklist’s default compression depth is 0, meaning no compression. The actual compression depth is determined by the list-compressed-depth configuration parameter. To support fast push/pop operations, the first and last ziplists of the QuickList are uncompressed, and the depth is 1. A depth of 2 means that the first ziplist and the second ziplist in quickList are not compressed.

Please add the following text and link at the end of the article: This article is participating in the “Gold Digging Booklet free learning!” Event, click to view details of the event