【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;

我们解释下关键参数：

• *prev：指向前一个节点的指针
• *next：指向后一个节点的指针
• *zl：指向实际存储数据的ziplist
• sc：当前ziplist占用的字节数
• count：当前ziplist中存放的元素数（最大65536）
• encoding：表示采用的压缩算法（1:RAW、2:LZF）

结构图解

接下来我们看下当执行新增元素操作时，源码的底层代码逻辑

Redis 6和Redis 7pushGenericCommand()方法略有不同（其实主要就是listpack替代ziplist的区别）

搞定🎉～～～～