Redis 6.0 源码阅读笔记(5)-List 数据类型源码分析

傷城~ 2023-10-05 09:39 35阅读 0赞

#### 文章目录 ####

*  1. 存储的结构
 *  2. 数据存储源码分析
 *   *   *  2.1 数据存储过程
         *  2.2 数据存储结构 ziplist
         *   *  2.2.1 ziplist 简介
             *  2.2.2 ziplist 的结构
             *  2.2.3 ziplist 的插入
         *  2.3 数据存储结构 quicklist
         *   *  2.3.1 quicklist 简介
             *  2.3.2 quicklist 的具体结构
             *   *  2.3.2.1 quicklist 结构
                 *   *  quicklist 中 ziplist 存储数据总数的设置
                     *  quicklist 节点压缩深度的设置
                 *  2.3.2.2 quicklist 节点结构
             *  2.3.3 quicklist 重要操作

## 1. 存储的结构 ##

redis 对于 List 的存储共有 3 种存储形式，其中 `OBJ_ENCODING_LINKEDLIST`已经彻底废弃不再讨论，其它两种存储形式的内存结构如下图示例:

*  `OBJ_ENCODING_ZIPLIST`：底层结构类似数组，使用特定属性保存整个列表的元信息，如整个列表占用的内存大小，列表保存的数据开始的位置，列表保存的数据的个数等，其保存的数据被封装在 `zlentry`
    
    > `zlentry` 是压缩列表保存数据的节点，其结构与 ziplist 类似，都是使用内部属性保存元信息，指针 p 指向存储的元素
    
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUwNTMxMw_size_16_color_FFFFFF_t_70_pic_center]
 *  `OBJ_ENCODING_QUICKLIST`：采用双向链表结构，每个链表节点都保存一个 ziplist，数据实际存储在 ziplist 内部。redis 6.0 中 List 列表对象采用的存储结构只有 quicklist
    
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUwNTMxMw_size_16_color_FFFFFF_t_70_pic_center 1]

## 2. 数据存储源码分析 ##

#### 2.1 数据存储过程 ####

1.  Redis 中对列表命令的处理在 `t_list.c`文件中，一个入口函数为 `t_list.c#lpushCommand()`，从其源码来看，主要逻辑是调用 `pushGenericCommand()` 函数。这个函数比较简短，主要完成的操作如下
    
    > 1.  首先调用 `lookupKeyWrite()` 函数去数据库中查找是否存在目标 key 的数据
    > 2.  如果不存在就调用 `createQuicklistObject()` 函数新建一个存储结构为 quicklist 的 redisObject 对象，通过函数 `dbAdd()` 将其存储到数据库中，再调用`listTypePush()` 函数将 value 值插入到列表中
    
        void pushGenericCommand(client *c, int where) {
              
         int j, pushed = 0;
         robj *lobj = lookupKeyWrite(c->db,c->argv[1]);
        
         if (lobj && lobj->type != OBJ_LIST) {
              
             addReply(c,shared.wrongtypeerr);
             return;
         }
        
         for (j = 2; j < c->argc; j++) {
              
             if (!lobj) {
              
                 lobj = createQuicklistObject();
                 quicklistSetOptions(lobj->ptr, server.list_max_ziplist_size,
                                     server.list_compress_depth);
                 dbAdd(c->db,c->argv[1],lobj);
             }
             listTypePush(lobj,c->argv[j],where);
             pushed++;
         }
         addReplyLongLong(c, (lobj ? listTypeLength(lobj) : 0));
         if (pushed) {
              
             char *event = (where == LIST_HEAD) ? "lpush" : "rpush";
        
             signalModifiedKey(c,c->db,c->argv[1]);
             notifyKeyspaceEvent(NOTIFY_LIST,event,c->argv[1],c->db->id);
         }
         server.dirty += pushed;
        }
2.  `object.c` 是 redis 中创建各种 redisObject 对象的集中地，其`object.c#createQuicklistObject()` 函数用于创建一个底层存储结构为 quicklist 的 redis 对象，其实现如下
    
    > 可以看到代码很简单，主要分为了两步：
    > 
    > 1.  调用 quicklistCreate() 函数创建 quicklist 结构
    > 2.  调用创建redis 对象的通用函数 createObject() 新建一个 redisObject 对象用于返回
    
        robj *createQuicklistObject(void) {
              
         quicklist *l = quicklistCreate();
         robj *o = createObject(OBJ_LIST,l);
         o->encoding = OBJ_ENCODING_QUICKLIST;
         return o;
        }
3.  `quicklist.c#quicklistCreate()` 函数也比较简短，可以看到只是进行了内存申请和属性初始化的工作，从这里也可以看到quicklist 是保存了头尾节点的双向链表结构
    
        /* Create a new quicklist.
        * Free with quicklistRelease(). */
        quicklist *quicklistCreate(void) {
              
         struct quicklist *quicklist;
        
         quicklist = zmalloc(sizeof(*quicklist));
         quicklist->head = quicklist->tail = NULL;
         quicklist->len = 0;
         quicklist->count = 0;
         quicklist->compress = 0;
         quicklist->fill = -2;
         quicklist->bookmark_count = 0;
         return quicklist;
        }
4.  至此列表对象创建完毕，我们来看看 `t_list.c#listTypePush()` 将值添加到quicklist 中的操作。源码很简练，主要步骤如下
    
    > 1.  判断列表对象的编码类型是否为 OBJ\_ENCODING\_QUICKLIST，如果不是就报错
    > 2.  根据 where 参数判断数据插入 quicklist 的位置
    > 3.  getDecodedObject() 函数将需要插入的数据转成 sds 存储的 String 对象，并调用 sdslen() 函数获取数据的长度
    > 4.  quicklistPush() 函数完成数据插入
    
        /* The function pushes an element to the specified list object 'subject',
        * at head or tail position as specified by 'where'.
        *
        * There is no need for the caller to increment the refcount of 'value' as
        * the function takes care of it if needed. */
        void listTypePush(robj *subject, robj *value, int where) {
              
         if (subject->encoding == OBJ_ENCODING_QUICKLIST) {
              
             int pos = (where == LIST_HEAD) ? QUICKLIST_HEAD : QUICKLIST_TAIL;
             value = getDecodedObject(value);
             size_t len = sdslen(value->ptr);
             quicklistPush(subject->ptr, value->ptr, len, pos);
             decrRefCount(value);
         } else {
              
             serverPanic("Unknown list encoding");
         }
        }
5.  `quicklist.c#quicklistPush()` 函数根据入参 where 确定需要调用的插入函数，以 `QUICKLIST_HEAD` 从链表头部插入为例，调用 `quicklist.c#quicklistPushHead()` 函数
    
        void quicklistPush(quicklist *quicklist, void *value, const size_t sz,
                        int where) {
              
         if (where == QUICKLIST_HEAD) {
              
             quicklistPushHead(quicklist, value, sz);
         } else if (where == QUICKLIST_TAIL) {
              
             quicklistPushTail(quicklist, value, sz);
         }
        }
6.  `quicklist.c#quicklistPushHead()` 函数的实现如下，可以看到其主要步骤如下
    
    > 1.  如果 \_quicklistNodeAllowInsert() 函数检查 quicklist 的 head 头节点可以插入，就直接利用 ziplist 的函数 ziplistPush() 将数据插入到该节点的 ziplist 中，然后调用 quicklistNodeUpdateSz() 更新节点的保存的数据的长度
    > 2.  以上条件不成立，则调用 quicklistCreateNode() 新建一个 quicklist 节点，同样将数据插入到节点 ziplist 中并更新节点数据长度，最后调用 \_quicklistInsertNodeBefore() 函数将新建节点作为头节点插入到 quicklist 中
    > 3.  做完上面的工作，更新 quicklist 和 quicklist 头节点的 count 属性，该属性用于记录存储的元素的总数
    
        int quicklistPushHead(quicklist *quicklist, void *value, size_t sz) {
              
         quicklistNode *orig_head = quicklist->head;
         if (likely(
                 _quicklistNodeAllowInsert(quicklist->head, quicklist->fill, sz))) {
              
             quicklist->head->zl =
                 ziplistPush(quicklist->head->zl, value, sz, ZIPLIST_HEAD);
             quicklistNodeUpdateSz(quicklist->head);
         } else {
              
             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);
        }

#### 2.2 数据存储结构 ziplist ####

##### 2.2.1 ziplist 简介 #####

`ziplist` 是 redis 中存储 List 列表数据的一种结构，它的存在就是为了提高存储效率。`ziplist` 会将列表中每一个元素存放在前后连续的地址空间内，整体占用一大块内存，以减少内存碎片的产生。因为 ziplist 占用一块连续空间，对它的追加操作会引发内存的 realloc 导致 ziplist 的内存位置发生变化，因此往 ziplist 中插入数据时会产生一个新的 ziplist

##### 2.2.2 ziplist 的结构 #####

1.  在 `ziplist.c` 文件的文件头注释中，redis 的作者很清楚地解释了 ziplist 的结构，其示意图如下
    
    > 可以看到 ziplist的各个部分在内存上是前后相邻的，它们的含义如下：
    > 
    > 1.  `zlbytes`  
    >     32bit，表示 ziplist 占用的字节总数（包括 zlbytes 本身占用的4个字节）
    > 2.  `zltail`  
    >     32bit，表示 ziplist 中最后一个元素（entry）在 ziplist 中的偏移字节数。借助 zltail 的可以很方便地找到 ziplist 中最后一个元素而不用遍历整个ziplist，使得在 ziplist 尾端快速地执行 push 或 pop 操作成为可能
    > 3.  `zllen`  
    >     16bit，表示 ziplist 中存储是元素（entry）的个数。因为 zllen 字段只有16bit，所以可以表达的最大值为2^16 - 1。需要注意的是，如果 ziplist 中元素个数超过了16bit 能表达的最大值，那么必须对 ziplist 从头到尾遍历才能统计出 ziplist 存储的元素总数
    > 4.  `entry`  
    >     表示真正存放数据的数据项，长度不定，结构为 `zlentry`
    > 5.  `zlend`  
    >     8bit，ziplist 最后1个字节，是一个结束标记，值固定等于255
    
        ziplist 示意图
                 |<---- ziplist header ---->|<----------- entries ------------->|<-end->|
        字段类型   uint32_t  uint32_t uint16_t    ?        ?        ?        ?    uint8_t
                 +---------+--------+-------+--------+--------+--------+--------+-------+
        字段名    | zlbytes | zltail | zllen | entry1 | entry2 |  ...   | entryN | zlend |
                 +---------+--------+-------+--------+--------+--------+--------+-------+
                                            ^                          ^        ^
        偏移量指针                            |                          |        |
                                     ZIPLIST_ENTRY_HEAD                |   ZIPLIST_ENTRY_END
                                                                       |
                                                             ZIPLIST_ENTRY_TAIL
2.  `zlentry` 的结构源码并不复杂，比较关键的属性如下
    
    > 1.  `prevrawlen`  
    >     表示当前 entry 在 ziplist 中的前一个 entry 占用的总字节数。借助这个字段 ziplist 能够从后向前遍历，从当前 entry 的位置向前偏移 prevrawlen 个字节，就找到了前一个 entry
    > 2.  `prevrawlensize`  
    >     用于标志 `prevrawlen` 的数据类型。这个属性存在的意义如下，分界点在 254 是因为 ziplist 中的结束标记 `zlend` 值固定为 255，如果采用 255 来表示 entry 占用的字节数会导致遍历 ziplist 时提前结束
    >     
    >      *  如果前一个entry 占用字节数小于 254，那么 prevrawlen 只用 1 个字节来表示就足够了，即 prevrawlensize 为 1
    >      *  如果前一个 entry 占用字节数大于等于254，那么 prevrawlen 就用 5 个字节来表示，其中第 1 个字节的值是254（作为这种情况的标记），后面 4 个字节存储一个整型值来表示前一个 entry 的占用字节数，即 prevrawlensize 为 5
    > 3.  `encoding`  
    >     情况比较复杂，根据该属性第1个字节存储的数据共有 9 种情况，这个字段不仅表示了当前 entry 保存的数据的长度，还带有保存的数据的数据类型信息
    > 4.  `*p`  
    >     指向存储的字符串数据的指针
    
    <table> 
     <thead> 
      <tr> 
       <th align="left">encoding 字段第一个字节数据</th> 
       <th align="left">encoding 字段占用字节</th> 
       <th align="left">含义</th> 
      </tr> 
     </thead> 
     <tbody> 
      <tr> 
       <td align="left">00pppppp</td> 
       <td align="left">1 byte</td> 
       <td align="left">第1个字节最高两个bit是00，剩余的6个bit用来表示长度值，说明这个 entry 保存长度小于 (2^6 -1) 的字符串</td> 
      </tr> 
      <tr> 
       <td align="left">01pppppp</td> 
       <td align="left">2 bytes</td> 
       <td align="left">第1个字节最高两个bit是01，总共有14个bit用来表示长度值，说明这个 entry 可保存长度小于(2^14-1)的字符串</td> 
      </tr> 
      <tr> 
       <td align="left">10______</td> 
       <td align="left">5 bytes</td> 
       <td align="left">第1个字节最高两个bit是10，总共使用32个bit来表示长度值，说明这个 entry 最多可以存储长度为 (2^32-1) 的字符串</td> 
      </tr> 
      <tr> 
       <td align="left">11000000</td> 
       <td align="left">1 bytes</td> 
       <td align="left">entry 存储的数据为int16_t类型</td> 
      </tr> 
      <tr> 
       <td align="left">11010000</td> 
       <td align="left">1 bytes</td> 
       <td align="left">entry 存储的数据为int32_t类型</td> 
      </tr> 
      <tr> 
       <td align="left">11100000</td> 
       <td align="left">1 bytes</td> 
       <td align="left">entry 存储的数据为int64_t类型</td> 
      </tr> 
      <tr> 
       <td align="left">11110000</td> 
       <td align="left">1 bytes</td> 
       <td align="left">entry 存储的数据为3个字节长的整数</td> 
      </tr> 
      <tr> 
       <td align="left">11111110</td> 
       <td align="left">1 bytes</td> 
       <td align="left">entry 存储的数据为1个字节长的整数</td> 
      </tr> 
      <tr> 
       <td align="left">1111xxxx</td> 
       <td align="left">1 byte</td> 
       <td align="left">xxxx 的值在0001和1101之间，entry 存储的数据为0-12的整数，直接存储在 encoding 剩余 4 个 bit 内</td> 
      </tr> 
     </tbody> 
    </table>
    
        typedef struct zlentry {
              
         unsigned int prevrawlensize; /* Bytes used to encode the previous entry len*/
         unsigned int prevrawlen;     /* Previous entry len. */
         unsigned int lensize;        /* Bytes used to encode this entry type/len.
                                         For example strings have a 1, 2 or 5 bytes
                                         header. Integers always use a single byte.*/
         unsigned int len;            /* Bytes used to represent the actual entry.
                                         For strings this is just the string length
                                         while for integers it is 1, 2, 3, 4, 8 or
                                         0 (for 4 bit immediate) depending on the
                                         number range. */
         unsigned int headersize;     /* prevrawlensize + lensize. */
         unsigned char encoding;      /* Set to ZIP_STR_* or ZIP_INT_* depending on
                                         the entry encoding. However for 4 bits
                                         immediate integers this can assume a range
                                         of values and must be range-checked. */
         unsigned char *p;            /* Pointer to the very start of the entry, that
                                         is, this points to prev-entry-len field. */
        } zlentry;

##### 2.2.3 ziplist 的插入 #####

`ziplist.c#ziplistPush()` 函数是 ziplist 插入数据的函数之一，源码其实是去调用 `ziplist.c#__ziplistInsert()` 函数，这个函数的实现如下：

> 1.  首先调用 ZIP\_DECODE\_PREVLEN() 计算出待插入位置的 entry 的prevrawlen 属性，也就是这个 entry 的前一个节点的长度
> 2.  调用 zipTryEncoding() 尝试将要插入的数据转成整数编码，然后将待插入数据占用的总字节数赋给 reqlen，另外考虑到数据包装成 `zlentry` 所需要的额外内存，reqlen 需要累加
> 3.  由于插入导致的 ziplist 对于内存的新增需求，除了待插入 entry 占用的内存之外，还要考虑待插入位置原来的 entry 的 prevrawlen 字段的变化。因为它保存的是新节点插入前的前一个 entry 的总长度，现在变成了保存待插入的 entry 的总长度，这样它的 prevrawlen 字段本身需要的内存也可能发生变化。这个变化可调用 zipPrevLenByteDiff() 计算出来的，如果变大了，是正值，否则是负值
> 4.  根据计算出来的插入新节点后的 ziplist 大小调用 ziplistResize() 重新调整 ziplist 大小，ziplistResize() 的实现里会调用 zrealloc 重新申请内存
> 5.  如果 zipPrevLenByteDiff() 计算出来的变化值不为 0， 则需要调用 \_\_ziplistCascadeUpdate() 函数级联更新 entry 的 prevrawlen 字段
> 6.  最后将待插入位置的 entry 及其后面的所有 entry 都向后挪动，并将组装好的新的 entry 放在待插入位置

*  连锁更新
    
    > 之前已经提到，在 ziplist 中当 entry 的前驱节点长度小于 254 字节，那么这个 entry 的 prev\_entry\_length 属性的占用的空间为1字节，当前驱节点的长度大于或等于254字节，那么 prev\_entry\_length 属性占用的空间增长为5字节。这样就会产生一个特殊场景：
    > 
    >  *  假如 ziplist 有 N 个连续的 entry 节点的长度介于 250-253字节，此时它们记录前一个节点的长度的 prev\_entry\_length 都只需要 1 个字节。但是某一时刻 entry1 节点前添加了一个新节点 entryM，它的长度大于或等于254字节。这时 entry1 的 prev\_entry\_length 属性需要记录 entryM 的长度，但是由于 entry1 的 prev\_entry\_length 属性只有1个字节，没法记录entryM 的长度，就需要将其 prev\_entry\_length 扩展为5个字节。这就会使得原本长度为250到253字节的 entry1 变为大于或等于254字节，使得 entry2 也需要扩展 prev\_entry\_length 属性为5字节，从而引发 entry3 直达 entryN 的 prev\_entry\_length 属性的改变。这就是Redis压缩列表的连锁更新，在实际中连锁更新这种会造成性能降低的情况很少见，因此对Redis的性能影响很小

unsigned char *__ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) {
        
        size_t curlen = intrev32ifbe(ZIPLIST_BYTES(zl)), reqlen;
        unsigned int prevlensize, prevlen = 0;
        size_t offset;
        int nextdiff = 0;
        unsigned char encoding = 0;
        long long value = 123456789; /* initialized to avoid warning. Using a value
                                        that is easy to see if for some reason
                                        we use it uninitialized. */
        zlentry tail;
    
        /* Find out prevlen for the entry that is inserted. */
        if (p[0] != ZIP_END) {
        
            ZIP_DECODE_PREVLEN(p, prevlensize, prevlen);
        } else {
        
            unsigned char *ptail = ZIPLIST_ENTRY_TAIL(zl);
            if (ptail[0] != ZIP_END) {
        
                prevlen = zipRawEntryLength(ptail);
            }
        }
    
        /* See if the entry can be encoded */
        if (zipTryEncoding(s,slen,&value,&encoding)) {
        
            /* 'encoding' is set to the appropriate integer encoding */
            reqlen = zipIntSize(encoding);
        } else {
        
            /* 'encoding' is untouched, however zipStoreEntryEncoding will use the
             * string length to figure out how to encode it. */
            reqlen = slen;
        }
        /* We need space for both the length of the previous entry and
         * the length of the payload. */
        reqlen += zipStorePrevEntryLength(NULL,prevlen);
        reqlen += zipStoreEntryEncoding(NULL,encoding,slen);
    
        /* When the insert position is not equal to the tail, we need to
         * make sure that the next entry can hold this entry's length in
         * its prevlen field. */
        int forcelarge = 0;
        nextdiff = (p[0] != ZIP_END) ? zipPrevLenByteDiff(p,reqlen) : 0;
        if (nextdiff == -4 && reqlen < 4) {
        
            nextdiff = 0;
            forcelarge = 1;
        }
    
        /* Store offset because a realloc may change the address of zl. */
        offset = p-zl;
        zl = ziplistResize(zl,curlen+reqlen+nextdiff);
        p = zl+offset;
    
        /* Apply memory move when necessary and update tail offset. */
        if (p[0] != ZIP_END) {
        
            /* Subtract one because of the ZIP_END bytes */
            memmove(p+reqlen,p-nextdiff,curlen-offset-1+nextdiff);
    
            /* Encode this entry's raw length in the next entry. */
            if (forcelarge)
                zipStorePrevEntryLengthLarge(p+reqlen,reqlen);
            else
                zipStorePrevEntryLength(p+reqlen,reqlen);
    
            /* Update offset for tail */
            ZIPLIST_TAIL_OFFSET(zl) =
                intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+reqlen);
    
            /* When the tail contains more than one entry, we need to take
             * "nextdiff" in account as well. Otherwise, a change in the
             * size of prevlen doesn't have an effect on the *tail* offset. */
            zipEntry(p+reqlen, &tail);
            if (p[reqlen+tail.headersize+tail.len] != ZIP_END) {
        
                ZIPLIST_TAIL_OFFSET(zl) =
                    intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff);
            }
        } else {
        
            /* This element will be the new tail. */
            ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(p-zl);
        }
    
        /* When nextdiff != 0, the raw length of the next entry has changed, so
         * we need to cascade the update throughout the ziplist */
        if (nextdiff != 0) {
        
            offset = p-zl;
            zl = __ziplistCascadeUpdate(zl,p+reqlen);
            p = zl+offset;
        }
    
        /* Write the entry */
        p += zipStorePrevEntryLength(p,prevlen);
        p += zipStoreEntryEncoding(p,encoding,slen);
        if (ZIP_IS_STR(encoding)) {
        
            memcpy(p,s,slen);
        } else {
        
            zipSaveInteger(p,value,encoding);
        }
        ZIPLIST_INCR_LENGTH(zl,1);
        return zl;
    }

#### 2.3 数据存储结构 quicklist ####

##### 2.3.1 quicklist 简介 #####

`quicklist` 是 redis 3.2 版本引入的存储结构，它是一个双向链表，链表中的每个节点都使用 ziplist 存储数据。在 redis 3.2 版本之前，redis 中 List 对象的底层数据结构是 `ziplist` 和 `linkedlist`。当 List 对象中元素的长度比较小或者数量比较少的时候，采用 ziplist 存储；当列表对象中元素的长度比较大或者数量比较多的时候，则转而使用双向列表 linkedlist 来存储。但是这样的设计有一定的缺陷，原因如下：

> 1.  双向链表便于在列表的两端进行push和pop操作，但是它的内存开销比较大。首先它的每个节点上除了要保存数据之外，还要额外保存两个指针；其次双向链表的各个节点是单独的内存块，地址不连续，节点增多了容易产生内存碎片
> 2.  ziplist 由于是一整块连续内存，所以存储效率很高。但是它每次增删数据都会引发一次内存的 realloc，当 ziplist 存储的数据很多的时候，一次realloc 可能会导致大量的数据拷贝，影响性能

因为以上原因，结合了双向链表和 ziplist 的优点，能够在时间效率和空间效率间实现较好折中的 `quicklist` 就应运而生了

##### 2.3.2 quicklist 的具体结构 #####

###### 2.3.2.1 quicklist 结构 ######

`quicklist` 的数据结构定义在 `quicklist.h` 文件中，其关键属性如下:

> 1.  `head`: 指向头节点的指针
> 2.  `tail`: 指向尾节点的指针
> 3.  `count`: 所有 ziplist 中存储数据的 entry 的个数总和
> 4.  `len`: quicklistNode 节点的个数综合
> 5.  `fill`: 单个 quicklistNode 节点中的 ziplist 存放 entry 总数的大小设置，由`list-max-ziplist-size`参数设置
> 6.  `compress`: 节点压缩深度设置，也就是 quicklist 首尾两端不被压缩的节点的个数，由`list-compress-depth`参数设置

typedef struct quicklist {
        
        quicklistNode *head;
        quicklistNode *tail;
        unsigned long count;        /* total count of all entries in all ziplists */
        unsigned long len;          /* number of quicklistNodes */
        int fill : QL_FILL_BITS;              /* 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;

###### quicklist 中 ziplist 存储数据总数的设置 ######

因为 quicklist 中包含了 ziplist 和链表，每个 quicklistNode 的大小就是一个需要考虑的点。如果单个 quicklistNode 的 ziplist 中存储的数据太多，必然会影响插入效率；如果单个 quicklistNode 存储的数据太少，又会跟普通链表一样造成空间浪费。这样一个 quicklistNode 节点上 ziplist 的合理长度是很难判断的，使用者可以考虑自身的应用场景通过 `list-max-ziplist-size`参数来设置，这个值最终存放在 `quicklist-> fill` 属性中：

> fill 参数可正可负，正负表示的含义不同:
> 
> 1.  如果参数为正，表示按照 entry 个数来限定每个节点中的元素个数，比如 3 代表每个节点中存放的元素个数不能超过3  
>     fill 为正数时的最大值：  
>     `#define FILL_MAX (1 << 15)`
> 2.  如果参数为负，表示按照字节数来限定每个节点中的元素个数，它只能取以下五个数，其含义如下：  
>     `-1` 每个节点的 ziplist 大小不能超过4kb  
>     `-2` 每个节点的 ziplist 大小不能超过8kb（-2是默认值）  
>     `-3` 每个节点的 ziplist 大小不能超过16kb  
>     `-4` 每个节点的 ziplist 大小不能超过32kb  
>     `-5` 每个节点的 ziplist 大小不能超过64kb  
>     `-1～-5` 对应以下数组：  
>     /\* Optimization levels for size-based filling \*/  
>     static const size\_t optimization\_level\[\] = \{4096, 8192, 16384, 32768, 65536\};

###### quicklist 节点压缩深度的设置 ######

List 的设计目标是存放很长的列表数据，当列表很长时占用的内存空间必然会相应增多。但是当列表很长的时候，List 中访问频率最高的是两端的数据，中间的数据访问频率较低，如果对使用频率较低的数据进行压缩，在需要使用时再进行解压缩，那就可以进一步减少数据存储的空间。基于此，redis 提供参数 `list-compress-depth` 来进行数据压缩配置，该值最终存放在 `quicklist-> compress` 属性中：

> compress：代表首尾两端不被压缩的 quicklistNode 节点个数
> 
>  *  0 特殊值，表示不压缩
>  *  1 表示 quicklist 首尾各有 1 个节点不压缩，中间的节点压缩
>  *  2 表示quicklist 首尾各有 2 个节点不压缩，中间的节点压缩  
>     compress最大值：  
>     `#define COMPRESS_MAX (1 << 16)`

###### 2.3.2.2 quicklist 节点结构 ######

quicklist 的节点结构为 `quicklistNode`，定义在 `quicklist.h` 文件中，其关键属性如下:

> 1.  `prev`: 指向链表前一个节点的指针
> 2.  `next`: 指向链表后一个节点的指针
> 3.  `zl`: 数据指针。如果当前节点的数据没有压缩，那么它指向一个ziplist结构；否则，它指向一个quicklistLZF 结构
> 4.  `sz`: 表示 zl 指向的 ziplist 的占用字节数总大小，即便 ziplist 被压缩了 sz 的值仍然是压缩前的 ziplist 大小
> 5.  `count`: 表示 ziplist 里面包含的 entry 个数
> 6.  `encoding`: 表示 ziplist 的编码，1 表示没有压缩，2 表示LZF压缩编码
> 7.  `container`: 用来表明一个 quicklist 节点下面是直接存数据，还是使用ziplist存数据，或者用其它的结构来存数据。目前的实现中该值是固定为2，表示使用 ziplist 作为数据容器
> 8.  `recompress`: bool 值，为 true 表示数据暂时解压

/* quicklistNode is a 32 byte struct describing a ziplist for a quicklist.
     * We use bit fields keep the quicklistNode at 32 bytes.
     * count: 16 bits, max 65536 (max zl bytes is 65k, so max count actually < 32k).
     * encoding: 2 bits, RAW=1, LZF=2.
     * container: 2 bits, NONE=1, ZIPLIST=2.
     * recompress: 1 bit, bool, true if node is temporarry decompressed for usage.
     * attempted_compress: 1 bit, boolean, used for verifying during testing.
     * extra: 10 bits, free for future use; pads out the remainder of 32 bits */
    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;

`quicklistLZF` 是对 ziplist 利用LZF算法进行压缩后 quicklistNode 节点 `quicklistNode->zl` 指向的数据结构，只有两个属性：

> 1.  `sz`: 表示压缩后的ziplist大小
> 2.  `compressed`: 是个数组，存放压缩后的 ziplist 字节数组

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

##### 2.3.3 quicklist 重要操作 #####

1.  任意指定位置插入  
    `quicklist.c#quicklistInsertAfter()`和`quicklist.c#quicklistInsertBefore()`分别在指定位置后面和前面插入数据，其实现都是调用 `quicklist.c#_quicklistInsert()` 函数。这种在任意指定位置插入数据的操作，情况比较复杂有很多的逻辑分支：
    
    > 1.  当插入位置所在的 ziplist 大小没有超过限制时，直接插入到ziplist中
    > 2.  当插入位置所在的 ziplist 大小超过了限制，但插入的位置位于 ziplist 两端，并且相邻的quicklist链表节点的 ziplist 大小没有超过限制，那么就转而插入到相邻的那个quicklist链表节点的 ziplist 中
    > 3.  当插入位置所在的 ziplist 大小超过了限制，但插入的位置位于 ziplist 两端，并且相邻的quicklist链表节点的 ziplist 大小也超过限制，这时需要新建一个quicklist链表节点插入
    > 4.  对于插入位置所在的 ziplist 大小超过了限制的其它情况（主要对应于在ziplist中间插入数据的情况），则需要从待插入位置把当前 ziplist 分裂为两个节点，再在其中一个节点上插入数据

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUwNTMxMw_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20200905175537172.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUwNTMxMw==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUwNTMxMw_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20200912213553117.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUwNTMxMw==,size_16,color_FFFFFF,t_70#pic_center