List的升级之路

Redis为什么这么快？

• 基于内存的数据库，所有操作都在内存上进行而非磁盘
• 单线程模型，支持IO多路复用
• 高效的数据结构

接下来，就分析一下Redis中是如何实现List（列表）对象的

• 在Redis 3.0版本中，List对象由list双向链表以及ziplist压缩列表实现
• Redis 3.2后，redis改由quicklist替换实现

那么，这些底层数据结构如何构成，以及quicklist相比于原来的结构有什么特点，还存在哪些不足之处？带着这些问题，开始进入List对象的升级之路。

列表List

List 类型的底层数据结构是由双向链表或压缩列表实现的：

• 如果列表的元素个数小于 512 个（默认值，可由 list-max-ziplist-entries 配置），列表每个元素的值都小于 64 字节（默认值，可由 list-max-ziplist-value 配置），Redis 会使用压缩列表作为 List 类型的底层数据结构；
• 如果列表的元素不满足上面的条件，Redis 会使用双向链表作为 List 类型的底层数据结构；

双向链表

双向链表的结构设计

Redis 封装了双向链表list，里面的节点ListNode有着前置跟后置的属性，双向操作起来会更加方便

其中，list 结构为链表提供了链表头指针 head、链表尾节点 tail、链表节点数量 len、以及可以自定义实现的 dup、free、match 函数...（自定义函数暂时还没去看有啥作用）

//底层都是用c写的，这里只是用java模拟一下
class ListNode{
    ListNode pre, next;
    int val;
    public ListNode(int val){
        this.val = val;
    }
}
public class list {
    ListNode head, tail;
    int len;
    public list(){
        head = new ListNode(0);
        tail = new ListNode(0);
        len = 0;
    }
}

链表的优缺点

• O(1)修改链表的值、支持双向遍历、通过len字段O(1)获取链表长度
• 链表节点可以保存不同类型的值，如字符串跟整数

• 链表每个节点之间的内存空间是不连续的（不像数组），无法很好利用CPU

  （主要是无法利用CPU缓存的局部性原理，当程序访问一个内存地址时，CPU 通常会将相邻的数据也加载到缓存行中，以提高数据访问效率。然而，对于链表节点而言，它们在内存中的位置相互分散，无法有效地利用缓存行，导致频繁的缓存不命中）

• 内存开销大，结构表头要分配空间，如head、tail以及自定义函数指针

那么，再看看3.0版本实现列表的另一个数据结构——ziplist 压缩列表

压缩列表

压缩列表最大的特点在于压缩（为节约内存而设计的），是一种内存紧凑型的数据结构，占用一块连续的内存空间，能够利用CPU缓存。

结构设计

压缩列表在表头有三个字段：

• zlbytes，记录整个压缩列表占用对内存字节数；
• zltail，记录压缩列表「尾部」节点距离起始地址由多少字节，也就是列表尾的偏移量；
• zllen，记录压缩列表包含的节点数量；
• zlend，标记压缩列表的结束点，固定值 0xFF（十进制255）。

在压缩列表中，如果我们要查找定位第一个元素和最后一个元素，可以通过表头三个字段（zllen）的长度直接定位，复杂度是 O(1)。而查找其他元素时，就没有这么高效了，只能逐个查找，此时的复杂度就是 O(N) 了，因此压缩列表不适合保存过多的元素

每一个压缩列表节点entry中，包含三个字段：

• prevlen，记录了「前一个节点」的长度，目的是为了实现从后向前遍历；
• encoding，记录了当前节点实际数据的「类型和长度」，类型主要有两种：字符串和整数。
• data，记录了当前节点的实际数据，类型和长度都由 encoding 决定；

当我们往压缩列表中插入数据时，压缩列表就会根据数据类型是字符串还是整数，以及数据的大小，会使用不同大小的空间来保存prevlen跟encoding字段的信息，这种根据数据大小和类型进行不同的空间大小分配的设计思想，正是 Redis 为了节省内存而采用的。

• 如果前一个节点的长度小于 254 字节，那么 prevlen 属性需要用 1 字节的空间来保存这个长度值；如果前一个节点的长度大于等于 254 字节，那么 prevlen 属性需要用 5 字节的空间来保存这个长度值；
• 如果当前节点的数据是整数，则 encoding 会使用 1 字节的空间进行编码，也就是 encoding 长度为 1 字节。通过 encoding 确认了整数类型，就可以确认整数数据的实际大小了，比如如果 encoding 编码确认了数据是 int16 整数，那么 data 的长度就是 int16 的大小。
• 如果当前节点的数据是字符串，根据字符串的长度大小，encoding 会使用 1 字节/2字节/5字节的空间进行编码，encoding 编码的前两个 bit 表示数据的类型，后续的其他 bit 标识字符串数据的实际长度，即 data 的长度。

为什么要设计成从后往前遍历呢？

主要为了快速定位最新数据，从后往前遍历，更符合内存访问的局部性原理

压缩列表的缺陷

• 前面说到了，压缩列表的最大优点是内存紧凑，节省内存——体现在按照数据类型和大小进行内存分配，同时支持倒序遍历，O(1)获得头尾指针
• 但是，获取任意位置的时间复杂度是O(n),因此就限制了ziplist不能保存过多元素
• 压缩列表中prevLen字段，记录前一个节点的长度，很容易会造成连锁更新的问题（假设一个压缩列表中有多个连续的、长度在 250～253 之间的节点，因为这些节点长度值小于 254 字节，所以 prevlen 属性需要用 1 字节的空间来保存这个长度值。 此时， 将一个长度大于等于 254 字节的新节点加入到压缩列表的表头节点，prevLen需要用到5个字节进行保存，会导致当前节点会大于254，接着引起后续空间的重新分配，这就会直接影响到压缩列表的访问性能。

因此，压缩列表只会用于保存的节点数量不多的场景，只要节点数量足够小，即使发生连锁更新，也是能接受的。

quicklist

在Redis 3.2版本中，Redis将双向链表和压缩列表整合成quicklist，本质上是一个链表，链表的每一个节点是一个压缩列表

为什么要这样做？

双向链表的不足总结起来就是1. 内存分配不连续，无法利用好CPU缓存；2. 相对压缩列表，内存占用还是大了点

前面提到，压缩列表的不足在于1. 不能保存过多元素 2.紧凑的空间设计（prevLen）导致的连锁更新的风险。

于是，quicklist通过控制每个链表节点中压缩列表的大小跟存储元素个数，来尽量减轻规避连锁更新 <注意，是减轻，而不是解决> 的问题。同时，继承双向链表优秀的修改结构。

结构设计

在向 quicklist 添加一个元素的时候，不会像普通的链表那样，直接新建一个链表节点。而是会先检查插入位置的压缩列表是否能容纳该元素，如果能容纳就直接保存到 quicklistNode 结构里的压缩列表，如果不能容纳，才会新建一个新的 quicklistNode 结构

缺点

硬要说quicklist的缺点

• 内存消耗，每个节点都要维护一个列表
• 访问效率 先要定位节点，再从后往前遍历压缩列表中的元素，效率是优点低的
• 不支持范围查询

但是，quicklist仍然是一种在某些场景下有效的数据结构，特别是在处理大型有序列表时，能够节省内存和提供一定的操作效率。

到这，List的数据结构的升级之路介绍完

连锁更新如何解决？

压缩列表其实是个非常优秀的数据结构，用到连续的内存空间来紧凑地保存数据，其实正中Redis的下怀。那连锁更新的问题要如何解决呢？

本质上，连锁更新的问题来源于prevLen这个字段，像listpack就通过把prevLen字段去掉来避免连锁更新的发生。

为什么quicklist不去掉prevLen来避免连锁更新呢？

虽然去掉压缩列表的 prevLen 字段可以简化设计并避免连锁更新的问题，但这样做会导致快速链表在大型列表的场景下失去其优势，因为节点之间的距离无法确定，难以快速定位和操作特定位置的元素。

listpack紧凑列表

listpack是hash对象和zset对象的底层实现结构。

同样是为了节省内存开销，沿用了一块连续的内存空间来紧凑地保存数据，并且为了节省内存的开销。

相比于压缩列表，listpack 没有记录前一个节点长度的字段了，listpack 只记录当前节点的长度，当我们向 listpack 加入一个新元素的时候，不会影响其他节点的长度字段的变化，从而避免了压缩列表的连锁更新问题，分别是

• encoding，当前元素的编码类型
• data，实际存放的数据；
• len，编码类型和元素数据这两部分的长度——可以用于从后向前遍历，当我们需要找到当前元素的上一个元素时，我们可以从后向前依次查找每个字节，找到上一个Entry的结束标识位，进而可以计算出上一个元素的长度。

listpack 支持从左向右正向查询列表，也支持从右向左反向查询列表

参考：

1. juejin.cn/post/709353…
2. xiaolincoding.com/redis/data_…