Redis笔记——底层数据结构之压缩列表

是什么？

        本质上就是紧凑的列表。

        压缩列表在 Redis 中有两种编码方式，分别是 ZIPLIST 与 LISTTPACK。LISTPACK 从 Redis 5.0 引入，直至 Redis 7.0 完全替换了 ZIPLIST，可以看作是 ZIPLIST 的进阶版。

有什么作用？

        在 List 文章中，提到了 ZIPLIST 是 LIST 的底层数据结构之一，提供紧凑型的数据存储，能节约内存（节省链表指针开销）。在数据量较少时，遍历访问性能好（连续且缓存命中率高）。

ZIPLIST的结构

* ZIPLIST 结构如下：
<zlbytes><zltail><zllen><entry><entry>...<entry><zlend>

* 字段含义：
zlbytes：占用4字节，表示该 ZIPLIST 总共占用了多少字节。
zltail：占用4字节，表示最后一个 entry 节点相对于起始指针的偏移量，可快速定位尾部节点，如果
    没有尾部节点则定为到 zlend。
zllen：占用2字节，表示共有多少个 entry 节点。
entry：数据节点。
zlend：占用1字节，一个特殊的节点，表示 ZIPLIST 的结束，值为255。

* 数据节点 entry 的结构如下：
<prevlen><encoding><entry-data>

* 字段含义：
prevlen：上一个数据节点的长度。当前数据节点起始地址 - prevlen 可以快速定位到上一个数据节点
    的起始地址。通过 prevlen 实现从后向前操作。
I、  255 是特殊字符，被 zlend 节点占用了。
II、 如果上一个数据节点大小 < 254字节，那当前数据节点的 prevlen 属性需要用1字节记录该长度值。
III、如果上一个数据节点大小 ≥ 254字节，那当前数据节点的 prevlen 属性需要用5字节记录该长度值。
此时该5个字节的第一个字节值为 11111110 即 254，标志这是个5个字节的 prevlen 属性，剩下的4个
字节用于记录该长度值。
encoding：编码类型，同时还记录着 entry-data 属性值的长度。
entry-data：实际的数据。

操作详析

查询 ZIPLIST 数据总量

        因为 ZIPLIST 本身通过 zllen 节点存储了节点数量，所以通常情况下时间复杂度为O(1)。

        需要注意的是，因为 zllen 节点本身只占用2个字节，表示长度的上限就是65535。当数据节点超过65535个zllen 为0，此时需要遍历数据节点，以获取真正的长度，时间复杂度为O(n)。

查询指定数据节点

        需要遍历数据节点，时间复杂度为O(n)。

更新数据

        ZIPLIST 提供头尾增减的能力，在头部增加节点会导致后续全部节点的后移，所以平均时间复杂度看作O(n)。

        ZIPLIST 的更新操作可能导致连锁更新，这个连锁更新与刚刚的增加节点导致的节点后移不是同一个概念。

        比如在头部新增一个大小 > 254字节的数据节点，此时第二个数据节点的 prevlen 需要记录第一个节点的长度，原本 1 字节的 prevlen 膨胀为5字节，其本身数据节点大小也随之改变。所以当这个新的数据节点插入导致的后续节点位移完成后，还需要逐步更新迭代，这种现象称为连锁更新。时间复杂度是O(n^2)，在 Redis 6.2 中已经优化为O(n)。

LISTPACK优化

连锁更新的根本原因

        ZIPLIST 作为 LIST 的底层数据结构，需要支持其双端操作的特性（既可以从前向后访问，也可以从后向前访问）。上面我们上面我们提到了 ZIPLIST 的数据节点的结构。

<prevlen><encoding><entry-data>

        prevlen 属性用于记录上一个数据节点的长度，基于此来实现从后向前访问数据节点。可以说 ZIPLIST 连锁更新问题就是因为 prevlen 导致的。我们需要一种不借助 prevlen，还能找到上一节点的起始位置的方法。

LISTPACK的解决方案

* LISTPACK 结构如下：
<encoding-type><element-data><element-tot-len>

* 字段含义：
encoding-type：编码类型。
element-data：数据内容。
element-tot-len：存储整个数据节点，除了它自身之外的长度。

        找到上一节点的关键就在于 element-tot-len。element-tot-len 所占用的每一个字节的第一个 bit 用于标识是否结束，0是结束，1是继续，剩下的7个 bit 用来存储数据大小。

        当我们从后向前访问数据节点时，我们可以从后向前查找前一个数据节点的 element-tot-len 的每一个字节，直至找到其结束标识，这样就可以算出前一个数据节点的起始位置了。

        举个栗子：上个节点的 element-tot-len 为 00000001 10000100，从后向前查询，根据结束标志0，确认 element-tot-len 属性为2字节，上个节点总大小（不包含 element-tot-len ）为 0000001 0000100 ==> 132字节，即再向前走132字节，就到了该节点的起始位置了。