 楔子  下面来解密 Redis 的列表，整篇文章分为三个部分。
Redis 列表的相关命令 先来看看列表的相关命令，我们首先要学会如何使用它。 lpush key value1 value2 ...：将多个值设置到列表里面，从左边 push rpush key value1 value2 ...：将多个值设置到列表里面，从右边 push lrange key start end：遍历列表，索引从 0 开始，最后一个为 -1，且包含两端 lpop key：从列表的左端弹出一个值，列表长度改变 rpop key：从列表的右端弹出一个值，列表长度改变 lindex key index：获取指定索引位置的元素，列表长度不变 llen key：获取指定列表的长度 lrem key count value：删除 count 个 value，如果 count 为 0，那么将全部删除 ltrim key start end：从 start 截取到 end，再重新赋值给 key rpoplpush key1 key2：移除 key1 的最后一个元素，并添加到 key2 的开头 lset key index value：将 key 中索引为 index 的元素设置为 value linsert key before/after value1 value2：在首次出现的 value1 的前面或者后面插入一个 value2。如果 value1 不存在，则该语句无效 以上就是 Redis 列表的一些基础操作，其实还有两个 API 我们没有说，先卖个关子。 Redis 列表的应用场景 列表的典型使用场景主要有两个。 1）文章列表 对于博客站点来说，当用户和文章都越来越多时，为了加快程序的响应速度，我们可以把用户自己的文章存入到 List 中。因为 List 是有序的结构，所以这样还可以完美地实现分页功能，从而加速程序的响应速度。 当然这里以博客站点为例，还有很多其它与之类似的场景。 2）消息队列 在消息队列方面，虽然 Redis 的专业程度不如 RabbitMQ，网络或者系统出故障时可能会丢数据。但由于它轻量、使用方便，所以如果你的业务场景比较简单，那么完全可以考虑使用 Redis 作为消息队列。 而把 Redis 当作队列来使用，肯定最先想到的就是使用 List 这个数据类型。因为 List 底层的实现是一个链表（一会说），在头部和尾部操作元素，时间复杂度都是 O(1)，这意味着它非常符合消息队列的模型。 生产者使用 LPUSH 发布消息： 消费者使用 RPOP 拉取消息： 这个模型非常简单，也很容易理解。
但这里有个小问题，当队列中已经没有消息了，消费者在执行 RPOP 时，会返回 NULL。而我们在编写消费者逻辑时，一般是一个「死循环」，这个逻辑需要不断地从队列中拉取消息进行处理，伪代码一般会这么写： 如果此时队列为空，那消费者依旧会频繁拉取消息，这会造成「CPU 空转」，不仅浪费 CPU 资源，还会对 Redis 造成压力。怎么解决这个问题呢？最容易想到的一个解决办法是，当队列为空时，我们可以「休眠」一会，再去尝试拉取消息。 这就解决了 CPU 空转问题，但又带来另外一个问题：当消费者在休眠等待时，有新消息来了，那消费者处理新消息就会存在「延迟」。如果缩短这个延迟，只能减小休眠的时间，但休眠时间变小，又有可能引发 CPU 空转问题。那如何做，既能及时处理新消息，还能避免 CPU 空转呢？ Redis 是否存在这样一种机制：如果队列为空，消费者在拉取消息时就「阻塞等待」，一旦有新消息过来，就通知消费者立即处理新消息呢？幸运的是，Redis 确实提供了「阻塞式」拉取消息的命令：BRPOP / BLPOP，这里的 B 指的是阻塞（Block）。
现在可以这样来拉取消息了： 使用 BRPOP 这种阻塞式方式拉取消息时，还支持传入一个「超时时间」，如果设置为 0，则表示不设置超时，直到有新消息才返回，否则会在指定的超时时间后返回 NULL。所以这个方案不错，既兼顾了效率，还避免了 CPU 空转问题，一举两得。
解决了消息处理不及时的问题，我们可以再思考一下，这种队列模型有什么缺点呢？显然缺点非常明显且致命：
第一个问题是功能上的，使用 List 做消息队列，它仅仅支持最简单的，一组生产者对应一组消费者，不能满足多组生产者和消费者的业务场景。 第二个问题就比较棘手了，因为从 List 中 POP 一条消息出来后，这条消息就会立即从链表中删除。也就是说，无论消费者是否处理成功，这条消息都没办法再次消费了，这也意味着，如果消费者在处理消息时异常宕机，那这条消息就相当于丢失了。 所以 List 可以用在消息队列上面，但它只能适用于简单的业务场景，或者对数据丢失不那么敏感的业务场景。 比如我前一段时间写了一个客户投诉的后台，运营和客户之间基于 WebSocket + XMPP 通信。客户使用的是 APP，发送的消息需要先通过 XMPP 协议发送给后台的一个组件，组件将消息推送到队列。我编写的后台服务再从队列里面取消息，通过 WebSocket 发送给前端，最终展示在页面上，让运营查看。 而这个队列就是使用 Redis 的 List 实现的，当初我想引入 RabbitMQ，后来经过商量之后其他人觉得没必要，认为投诉消息丢了就丢了，这玩意也不太重要，丢了就让客户重发一遍😂。不过到目前为止，还没有遇见过丢失消息的情况，服务运行的还是很稳定的。 Redis 列表的实现原理 Redis 提供了一个命令，可以让我们查看某个类型使用的底层数据结构。 我们看到 List 类型的底层数据结构是 quicklist，这是 Redis 在 3.2 版本时引入的数据结构。早期的 List 类型是使用 ziplist（压缩列表）和双向链表实现的，Redis3.2 的时候改为 quicklist，下面就来看一下这几个结构的具体实现。  双向链表 由于 C 语言本身没有链表这个数据结构，所以 Redis 自己设计了一个链表数据结构。 有了前继节点和后继节点，可以看出节点之间会形成一个双向链表。
有了 ListNode 之后，Redis 在其基础之上又封装了一层，这样操作起来会更加方便。 Redis 封装了一个数据结构叫 list ，该结构提供了链表头节点 head、链表尾节点 tail、链表节点数量 len、以及可以自定义实现的 dup、free、match 函数。
举个例子，下图是由 list 和 3 个 ListNode 组成的双向链表。
结构还是比较简单和清晰的，毕竟链表算是最常见的数据结构之一了。那么问题来了，双向链表它的优缺点是什么呢？ 优点： 1）listNode 链表节点的结构里带有 prev 和 next 指针，获取某个节点的前置节点或后置节点的时间复杂度只需 O(1)；而且这两个指针都可以指向 NULL，所以对链表的访问以 NULL 为终点，是无环链表。 2）由于 list 内部包含了头节点 head 和尾节点 tail，所以获取链表的头节点和尾节点的时间复杂度只需 O(1)。 3）list 内部的成员变量 len 会维护持有的链表节点个数，所以获取链表中节点数量的时间复杂度为 O(1)。 4）链表节点使用 void* 指针来保存节点值，并且可以通过 list 结构的 dup, free, match 三个属性为节点值设置类型特定函数，所以链表可以用于保存各种不同类型的值（的指针）。 缺点： 1）链表和数组不同，链表的每个节点之间的内存都是不连续的，这意味着链表无法像数组那样很好地利用 CPU 缓存。 2）每一个链表节点除了保存值之外，还包含了 prev 和 next 两个指针，因此会有额外的内存开销。 在 Redis 3.2 之前，List 会使用双向链表作为底层数据结构的实现，但如果 List 对象的数据量比较少，那么会采用压缩列表（ziplist）来实现，它的优势是节省内存空间，并且是内存紧凑型的数据结构。 下面来看一下压缩列表。 压缩列表（ziplist） 压缩列表的特点是节省内存，它是由连续内存块组成的顺序型数据结构，有点类似于数组。
在压缩列表中，如果我们要查找第一个元素和最后一个元素，可以通过表头三个字段的长度直接定位，复杂度是 O(1)。而查找其它元素时，就没有这么高效了，只能逐个查找，此时的复杂度就是 O(N) 级别，因此压缩列表不适合保存过多的元素。 然后压缩列表的每一个节点叫做一个 entry，是一个结构体，其内部字段如下：
压缩列表节点包含三部分内容：
当我们往压缩列表中插入数据时，压缩列表就会根据数据是字符串还是整数，以及数据的大小，选择不同空间大小的 prevlen 和 encoding。我们看到这种做法类似于 SDS，目的就是将元数据所占的内存降到最低。 然后我们再来仔细观察一下压缩列表的结构，它除了查询元素没那么高效之外，还有没有别的问题呢？ 假设一个压缩列表中有多个连续的、长度在 250～253 之间的节点，如下图：
因为这些节点长度值小于 254 字节，所以 prevlen 字段需要用 1 字节的空间来保存这个长度值。这时如果将一个长度大于等于 254 字节的新节点加入到压缩列表的头部，即新节点将成为 entry1 的前继节点，如下图所示：
因为 entry1 节点的 prevlen 字段只有 1 个字节大小，无法保存新节点的长度，此时就需要对压缩列表的空间进行重分配操作。将 entry1 节点的 prevlen 字段从原来的 1 字节大小扩展为 5 字节大小，因此 entry1 节点的大小相比之前会增加 4 字节。 而 entry1 一旦增加，那么 entry1 也会大于等于 254 字节，所以此时就要扩展 entry2 的 prevlen 字段。而一旦扩展 entry2 的 prevlen 字段，那么会有什么结果相信你已经猜到了，就像多米诺骨牌一样，连锁效应一发不可收拾。
空间扩展就意味着重新分配内存，所以一旦出现「连锁更新」，就会导致压缩列表占用的内存空间被多次重新分配，这会直接影响到压缩列表的访问性能。 因此虽然压缩列表紧凑型的内存布局能节省内存开销，但如果保存的元素数量增加了，或是元素变大了，会导致内存重新分配，最糟糕的是会有「连锁更新」的问题。因此压缩列表只用于保存节点数量不多的场景，如果节点数量足够少，即使发生连锁更新也是能接受的。 quicklist 总之从效果上看，压缩列表和双向链表都不尽人意，所以 Redis 在 3.2 版本设计了新的数据结构 quicklist，并将 List 对象的底层数据结构改由 quicklist 实现。而 quicklist 就相当于将双向链表和压缩列表结合起来了。 另外多提一句，压缩列表不仅可以作为 List 的底层结构，还可以作为 Hash 和 ZSet 的底层结构。但我们说压缩列表性能不行，于是在 Redis5.0 又设计出了新的数据结构 listpack，它不仅沿用了压缩列表紧凑型的内存布局，还提升了性能。在 Redis6.? 版本，将 Hash 和 Zset 的底层数据结构实现之一的压缩列表，替换成了 listpack。
总之 quicklist 和 listpack 的设计目标，就是尽可能地保持压缩列表节省内存的优势，同时解决连锁更新的问题。 下面看一下 quicklist，而 listpack 我们后续再说。 接下来看看，quicklistNode 的结构定义： 可以看到，quicklistNode 结构体里包含了前一个节点和后一个节点的指针，这样每个 quicklistNode 形成了一个双向链表。但是链表节点的元素不再是单纯保存元素值，而是保存了一个压缩列表，所以 quicklistNode 结构体里有个指向压缩列表的指针 *zl。
在向 quicklist 添加一个元素的时候，不会像普通的链表那样，直接新建一个链表节点。而是会检查插入位置的压缩列表是否能容纳该元素，如果能容纳就直接保存；如果不能容纳，则新建一个 quicklistNode 结构。 listpack quicklist 虽然通过控制 quicklistNode 结构里的压缩列表的大小或者元素个数，来减少连锁更新带来的性能影响，但是并没有完全解决连锁更新的问题。因为 quicklistNode 还是使用了压缩列表来保存元素，压缩列表连锁更新的问题，来源于它的结构设计，所以要想彻底解决这个问题，需要设计一个新的数据结构。 于是 Redis 在 5.0 的时候新设计了一个数据结构叫 listpack，目的是替代压缩列表，它最大特点是 listpack 中每个节点不再包含前一个节点的长度了，压缩列表每个节点正因为需要保存前一个节点的长度字段，就会有连锁更新的隐患。
listpack 采用了压缩列表的很多优秀的设计，比如还是用一块连续的内存空间来紧凑地保存数据，并且为了节省内存的开销，listpack 节点会采用不同的编码方式保存不同大小的数据。
listpack 头包含两个属性，分别记录了 listpack 总字节数和元素数量，大小分别为 4 字节和 2 字节；然后 listpack 末尾也有个结尾标识，和压缩列表一样，值也为固定的 0xFF。而 listpack entry 就是 listpack 的节点了，每个 listpack 节点结构如下：
可以看到 listpack 的结构和压缩列表（ziplist）还是很相似的，只是没有记录前一个节点长度的字段了，listpack 只记录当前节点的长度。当我们向 listpack 加入一个新元素的时候，不会影响其它节点的长度字段的变化，从而避免了压缩列表的连锁更新问题。 小结 虽然 Redis 的 List 采用了 quicklist，但我们要理解这其中的变迁。首先是 ziplist，它的设计初衷就是「节省内存」，在存储数据时，把内存利用率发挥到了极致：
但是缺点也很明显：
想要解决 ziplist 的问题，比较简单直接的方案就是，多个数据项不再用一个 ziplist 来存，而是分散到多个 ziplist 中，每个 ziplist 用指针串起来。这样修改其中一个数据项，即便发生连锁更新，也只会影响这一个 ziplist，其它 ziplist 不受影响，这种方案就是 quicklist。 所以 quicklist 相当于将 ziplist 和双向链表结合在了一起，它的 LPUSH, LPOP, RPUSH, RPOP 的时间复杂度都是 O(1)。 另外还可以设置 List 中每个 ziplist 节点可保存的元素个数 / 总大小，通过 list-max-ziplist-size 配置：
ziplist 超过上述任意一个配置，添加新元素就会新建 ziplist 插入到链表中。另外 List 因为更多是两头操作，那么为了节省内存，还可以把中间的 ziplist「压缩」，具体可看 list-compress-depth 配置项，默认配置不压缩。 虽然引入了 quicklist，但连锁更新的问题并没有得到解决，只是相应的范围变小了而已。要想彻底解决 ziplist 连锁更新的问题，本质上必须要修改 ziplist 的存储结构，也就是不要让每个元素保存「上一个」元素的长度即可。于是 Redis 又设计出了 listpack，对于那些使用了 ziplist 的数据数据结构，将其内部的 ziplist 换成 listpack。 ziplist 和 listpack 的结构非常相似，ziplist 之所以要保存上一个元素的长度（导致连锁更新的原因），主要是为了能够从后往前遍历。但 listpack 每个元素项不再保存上一个元素的长度，而是通过优化元素内字段的顺序，来保证既可以从前往后、也可以从后往前遍历，同时避免了连锁更新的问题。 本文参考自：
|
|
|
