Redis经典面试题：List 底层是啥？

前面和大家聊了 Redis 面试的时候面到了 String 的底层，String 的底层是 SDS，卷到了 C。

不过既然说到了 String 的底层，那么另外一个问题也就呼之欲出了：

• List 底层是什么？

今天我们来聊一聊这个话题。

一 数据结构变迁

List 底层的数据结构经过了多次变迁：最早是 linkedlist 和 ziplist，后来在 Redis3.2 的时候引入了 quicklist，最近新的 7.0 版本又引入了 listpack。

List 底层数据结构的不断变化，其实也体现了 Redis 在实际应用中面临的一些挑战，以及 Redis 作者针对这些挑战所做出来的一些改变。

接下来我们就以 Redis3.2、Redis7.0 两个版本为关键节点，来分析不同时期 Redis 的底层数据结构。

二 linkedlist

在 Redis3.2 之前，List 底层的数据结构有两种，分别是：

1. linkedlist
2. ziplist

具体使用哪个，要看 List 中保存的元素数据：

• 如果 List 中每个元素的大小小于 64 并且元素数量小于 512，那么就使用 ziplist，否则就使用 linkedlist。

我们先来分析这个 linkedlist，先来看下 linkedlist 的数据结构，如下：

typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;

这个数据结构有点像我们 Java 中的 LinkedList，有前驱节点、后驱节点以及指向节点数据的指针。

然后再在一个 list 中将这些 listNode 串起来，给出头节点（head）、尾节点（tail）、节点值复制方法（dup）、节点值释放方法（free）、判断节点值是否相等的方法（match）以及链表上的节点数量（len）。

这样，我们就有了一个完整的链表了。

typedef struct list {
    listNode *head;
    listNode *tail;
    void *(*dup)(void *ptr);
    void (*free)(void *ptr);
    int (*match)(void *ptr, void *key);
    unsigned long len;
} list;

这种节点结构比较简单明了，每个节点上都有向前向后的指针，遍历很方便；并且有 len 属性去记录链表的长度，因此获取链表长度也比较方便。

既然如此完美，为什么还需要 ziplist 呢？

linkedlist 主要存在下面这样一些问题：

1. 内存开销大：

每个链表节点除了存储实际的数据外，还需要额外的空间来保存指向前一个节点和后一个节点的指针。这导致了较大的内存开销，尤其是当链表中的元素较小时，指针占用的内存空间可能超过了元素占用的内存空间。

2. 随机访问效率低：

LinkedList 不支持随机访问，要访问链表中的某个元素，必须从头节点开始遍历到目标节点。这意味着对于大型链表，访问时间可能很长，特别是在需要频繁随机访问的场景中。

3. 空间碎片问题：

链表的节点可能分散在内存的不同地方，这可能导致内存分配和释放时的碎片问题，尤其是在高并发的环境中。

为了解决 linkedlist 存在的这些问题，引入了 ziplist。

三 ziplist

相比于 linkedlist，ziplist 主要有如下一些特点：

1. 内存效率高：

ziplist 将所有元素紧密地存储在一起，减少了额外的开销，尤其是对于小的元素，它能够有效地利用空间，而且因为数据是在一整块内存中连续的，因此也不需要向前向后的指针。

2. 支持多种数据类型：

ziplist 可以存储整数和字符串，并且使用变长编码来表示这些数据，这使得它非常适合用于存储各种类型的小型数据，ziplist 中存储数据的单元是 entry，entry 中除了保存数据之外，还有一个字段叫做 prelen，这个记录了上一个 entry 占用字节数，根据这个参数就可以快速将指针移动到上个 entry 位置。

3. 更优的读写性能（在特定条件下）：

对于小数据集，ziplist 的连续存储方式可以利用 CPU 缓存，提高读取速度。虽然修改中间元素可能需要重构整个列表，但对于小列表，这种代价是可以接受的。

因此，在 Redis 中，对于那些元素数量不多且大小较小的列表和哈希表，使用 ziplist 能够提供更好的内存使用效率和较快的访问速度。而对于元素较多或数据较大的情况，Redis 可能会自动转换为其他数据结构以保持操作的效率。

这就是 ziplist，看起来也很完美，解决了 linkedlist 存在的问题，那么为什么又有 quicklist 呢？

有 quicklist 当然也是因为 ziplist 的有不足的地方，有哪些不足呢？

1. 修改操作的成本：

在 ziplist 中修改中间的元素或删除多个元素时，往往需要重新构建整个 ziplist，因为其内部结构是连续的，比如现在有 A、B、C 三个元素，现在在 B 前面插入 D，那么 B 的 prelen 就会发生变化，进而导致 B 的大小发生变化，进而导致 C 的 prelen 发生变化。。。这一系列操作下来就导致较高的 CPU 和内存使用。

2. 大小限制：

ziplist 的大小和元素数量有限制。一旦 ziplist 的总大小超过了 512 字节（对于列表）或占用的空间超过 1MB（对于哈希表），或者当单个字符串元素的长度超过 64 字节时，Redis 会自动将其转换为其他数据结构。

3. 不适合大数据集：

ziplist 对于处理大量数据或较大的数据元素不够高效，尤其是在需要频繁的修改操作时。

由于 ziplist 存在的这些局限性，因此，Redis3.2 又引入了 quicklist。

四 quicklist

quicklist 本质上是由多个 ziplist 组成的双向链表。这种设计结合了 linkedlist 和 ziplist 的优点。

quicklist 本质上算是一个 linkedlist，只不过在这个 linkedlist 中，每个元素是一个 ziplist。

我们来看下 linkedlist 的定义：

typedef struct quicklistNode {
    struct quicklistNode *prev;
    struct quicklistNode *next;
    unsigned char *entry;
    size_t sz;             /* entry size in bytes */
    unsigned int count : 16;     /* count of items in listpack */
    unsigned int encoding : 2;   /* RAW==1 or LZF==2 */
    unsigned int container : 2;  /* PLAIN==1 or PACKED==2 */
    unsigned int recompress : 1; /* was this node previous compressed? */
    unsigned int attempted_compress : 1; /* node can't compress; too small */
    unsigned int dont_compress : 1; /* prevent compression of entry that will be used later */
    unsigned int extra : 9; /* more bits to steal for future usage */
} quicklistNode;

其实从这个数据结构中可以看到，这个 quicklistNode 和 listNode 还是有一些相像的。最大的差别在于节点变成了 ziplist。

因此在 quicklist 中存在两种极端情况：

1. ziplist 只有一个 entry，那么此时的 quicklist 就变成了linkedlist。
2. ziplist 特别大，并且 quicklist 上只有一个 ziplist，那么此时的 quicklist 就变成了 ziplist 了。

因此在使用 quicklist 的时候，需要合理控制 ziplist 的大小，官方推荐的 ziplist 大小不超过 8KB，这个可根据自己的实际情况去配置。

总结一下，quicklist 具备如下一些优势：

1. 扩展性：

quicklist 允许每个节点独立成为一个 ziplist，这样就可以在不破坏整个结构的情况下单独修改或添加 ziplist 节点，提高了修改操作的效率。

2. 内存效率：

尽管 quicklist 在节点之间增加了额外的链接开销，但由于每个 ziplist 节点的大小受到限制，这有助于避免单个大的数据结构占据过多的连续内存空间，从而减少了内存碎片。

3. 性能优化：

quicklist 在读取和写入操作上提供了更好的平均性能，特别是对于大数据集和频繁的修改操作。

4. 适应性：

quicklist 可以根据数据的大小和类型动态调整，使其能够适应各种工作负载。

其实在我看来，quicklist 最大的优势在于减小了 ziplist 中更新数据时，连锁更新的影响范围，连锁更新的问题实际上没解决，但是把影响范围缩小了。

因此还有一个 listpack。

五 listpack

listpack 和 ziplist 其实非常像，区别在于 listpack 的 entry 中不再记录上一个元素的字节大小，也就是 prelen，而是单纯的记录自身的大小。

这样，每当数据更新的时候，就不会影响下一个元素了。

这也是目前 Redis 的 List 结构底层数据的最终形态。

六 小结

好啦，小伙伴们掌握了 linkedlist、ziplist、quicklist 以及 listpack，Redis 中 List 底层的数据结构相信就是不在话下了吧～再也不怕 Redis 面试卷 C 了～