【Redis】深入理解 Redis 常用数据类型源码及底层实现(5.详解List数据结构)

本文是深入理解 Redis 常用数据类型源码及底层实现系列的第5篇～前4篇可移步(￣∇￣)/

【Redis】深入理解 Redis 常用数据类型源码及底层实现（1.结构与源码概述）-CSDN博客

【Redis】深入理解 Redis 常用数据类型源码及底层实现(2.版本区别+dictEntry & redisObject详解)-CSDN博客

【Redis】深入理解 Redis 常用数据类型源码及底层实现(3.详解String数据结构)-CSDN博客

【Redis】深入理解 Redis 常用数据类型源码及底层实现(4.详解Hash数据结构)_查看 hash-max-ziplist-entries 命令-CSDN博客

正文开始～

在Redis 3之前，List数据结构底层ziplist和linkedlist双向链表（当列表对象中元素的长度比较小或者数量比较少的时候，采用ziplist来存储（内存紧凑，访问效率高，但是更新效率低，当数据量较大时，可能导致大量的内存复制）当列表对像中元素的长度比较大或者数据数量比较多的时候会使用linkedlist（修改效率高，但是内存开销大，当节点较多时，会产生大量的内存碎片）。

后续综合了两者的优缺点，使用quicklist替换了ziplist和linkedlist双向链表。

虽然都是quicklist，但其实在Redis 6及其以前和Redis 7及其以后也存在较大的不同。简单一句话来理解就是：Redis 6的quicklist中装的是ziplist而Redis 7的quicklist中装的是listpack（看过上一篇介绍Hash得文章的朋友应该了解listpack就是用来替代ziplist的）

我们可以对比下来看，首先是相关的配置参数

先看下都有的list-compress-depth和list-max-ziplist-size

list-compress-depth指的是压缩配置，表示一个quicklist两端不被压缩的节点个数（这里的节点是quicklist双向链表的节点，不是里面的ziplist/listpack）

- 取值含义：

- - 0：默认值，表示都不压缩
  - n：quicklist两端各有n个节点不被压缩（中间的都压缩，n=1/2/3……）

list-max-ziplist-size指的是ziplist中的entry的配置

- 取值含义：

- - 正值：表示按照数据项个数来限定每个quicklist节点上的ziplist的长度（例如取5的时候，表示每个quicklist节点的ziplist最多包含5个数据项）
  - 负值：表示按照占用字节数来限定每个quicklist节点上的ziplist长度

- - - 取值含义（只能取-5/-4/-3/-2/-1五个值）

- - - - -5：每个quicklist节点上的ziplist大小不能超过64Kb（1kb=1024 bytes，即64*1024 bytes）
      - -4：每个quicklist节点上的ziplist大小不能超过32Kb（1kb=1024 bytes，即32*1024 bytes）
      - -3：每个quicklist节点上的ziplist大小不能超过16Kb（1kb=1024 bytes，即16*1024 bytes）
      - -2：默认值，每个quicklist节点上的ziplist大小不能超过8Kb（1kb=1024 bytes，即8*1024 bytes）
      - -1：每个quicklist节点上的ziplist大小不能超过4Kb（1kb=1024 bytes，即4*1024 bytes）

而Redis 7多了一个参数list-max-listpack-size，这个参数的含义跟list-max-ziplist-size基本一致，不过指的不是ziplist中的entry，而是listpack中的entry的配置

取值含义：

- 正值：表示按照数据项个数来限定每个quicklist节点上的listpack的长度（例如取5的时候，表示每个quicklist节点的listpack最多包含5个数据项）
- 负值：表示按照占用字节数来限定每个quicklist节点上的ziplist长度

- - 取值含义（只能取-5/-4/-3/-2/-1五个值）

- - - -5：每个quicklist节点上的listpack大小不能超过64Kb（1kb=1024 bytes，即64*1024 bytes）
    - -4：每个quicklist节点上的listpack大小不能超过32Kb（1kb=1024 bytes，即32*1024 bytes）
    - -3：每个quicklist节点上的listpack大小不能超过16Kb（1kb=1024 bytes，即16*1024 bytes）
    - -2：默认值，每个quicklist节点上的listpack大小不能超过8Kb（1kb=1024 bytes，即8*1024 bytes）
    - -1：每个quicklist节点上的listpack大小不能超过4Kb（1kb=1024 bytes，即4*1024 bytes）

看张比较形象的图

quicklist.h

在quicklist.h的源代码中，我们可以看到每个节点被封装成了quicklistNode对象

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;

我们解释下关键参数：

*head：指向双向列表表头的指针
*tail：指向双向列表表尾的指针
count：记录ziplist中存放的元素个数
len：双向链表的长度（quicklistNode的数量）
compress：压缩深度（默认0表示不压缩）

不知道有没有小伙伴觉得奇怪，这些参数都没见到ziplist，但是为什么count表示的是ziplist中存放的元素个数？

那是因为在每个quicklistNode对象中，装着一个ziplist

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;

我们解释下关键参数：