Redis压缩列表

区分一下

3.2之前 Redis中的List有两种编码格式一个是LINKEDLIST 一个是ZIPLIST 这个ZIPLIST就是压缩列表

3.2之后来了一个QUICKLIST QUICKLIST是ZIPLIST和LINKEDLIST的结合体也就是说Redis中没有ZIPLIST和LINKEDLIST了然后在Redis5.0引入了LISTPACK用来替换QUiCKLIST中的ZIPLIST在REDIS7.0后完全取代了ZIPLIST

我们有说到压缩列表是List的底层数据结构，压缩列表主要用做为底层数据结构提供紧凑型的数据存储方式，能节约内存（节省链表指针的开销），小数据量的时候遍历访问性能好（连续+缓存命中率友好）。数据量少的时候会用它

什么情况是数据量小的呢

1.列表对象保存的所有字符串对象长度都小于64字节；

2.列表对象元素个数少于512个，注意，这是LIST的限制，而不是ZIPLIST的限制；

满足以上两点就会用ZIPLIST编码

ZIPLIST结构

zlbytes:表示该ZIPLIST一共占了多少字节数，这个数字是包含zlbytes本身占据的字节的。(夺大!)

zltail：ZIPLIST 尾巴节点相对于ZIPLIST的开头（起始指针）偏移的字节数。通过这个字段可以快速定位到尾部节点，例如现在有一个ZIPLIST，zl指向它的开头，如果要获取tail尾巴节点，即ZIPLIST里的最后一个节点，可以zl + zltail的值，这样定位到它。如果没有尾节点，就定位到 zlend

zllen:表示有多少个数据节点，在本例中就有3个节点。

entry1~entry3：表示压缩列表数据节点。

zlend：一个特殊的entry节点，表示ZIPLIST的结束。

ZIPLIST节点结构

就是上面的entry1 entry2....

他里面有三个字段

prevlen：表示上一个节点的数据长度。

encoding：编码类型。编码类型里还包含了一个entry的长度信息，可用于正向遍历

entry-data：实际的数据。

prevlen:

通过这个字段可以定位上一个节点的起始地址（或者说开头)也就是就是p-prevlen 可以跳到前一个节点的开头位置，实现从后往前操作，所以压缩列表才可以从后往前遍历。如果前一节点的长度，也就是前一个ENTRY的大小，小于254字节，那么prevlen属性需要用1字节长的空间来保存这个长度值，255是特殊字符，被zlend使用了如果前一节点的长度大于等于254字节，那么prevlen属性需要用5字节长的空间来保存这个长度值，注意5个字节中中第一个字节为11111110,也就是254,标志这是个5字节的prelen信息，剩下4字节来表示大小。(这也差太多了看人家MYSQL里面的可变长度列少了就1字节长了就2字节)

encoding:

00pppppp 1字节 String类型，且字符串长度小于2へ6，即小于等于63

01pppppplqqqqqqqq 2字节 String类型，长度小于2^14次方，即小于等于16383

10000000|qqqqqqqq|rrrrrrrr|ssssssss|tttttttt 5字节 String类型，长度小于2へ32次方

110000001 2个字节的 int16类型

110100001 4个字节的 int32类型

11111110 1个字节的 int64类型

费老劲了别背就记住前几位是标识类型后几位标识长度对于int类型只标识类型长度不用标

ZIPLIST性能

查询数据总量

由于ZIPLIST的header定义了记录节点数量的字段zllen,所以通常是可以在O(1)时间复杂度直接返回的,但是呢 zllen是两个字节的也就是说最多也就能存65534的长度大于了就存不下了就得遍历了

遍历去吧大于65534的节点数累死所以他只是应用节点数少的时候

查询指定节点

在ZIPLIST中查询指定数据的节点，需要遍历这个压缩列表，平均时间复杂度是O（N)。

更新数据

ZIPLIST的更新就是增加、删除数据，ZIPLIST提供头尾增减的能力，但是操作平均时间复杂度是O（N），因为在头部增加一个节点会导致后面节点都往后移动，所以更新的平均时间复杂度，可以看作O（N)。其中要注意的是更新操作可能带来连锁更新。注意上面所说的增加节点导致后移，不是连锁更新。连锁更新是指这个后移，发生了不止一次，而是多次。比如增加一个头部新节点，后面依赖它的节点，需要prevlen字段记录它的大小，原本只用1字节记录，因为更新可能膨胀为5字节，然后这个entry的大小就也膨胀了。所以，当这个新数据插入导致的后移完成之后，还需要逐步迭代更新。这种现象就是连锁更新，时间复杂度是O（Nへ2），6.2已经优化为O（N），不用太过担心连锁更新的情况，实际的业务中，很少会刚好遇到需要迭代更新超过2个节点的情况，所以ZIPLIST更新平均时间复杂度，还是可以看作O（N)。不过，ZIPLIST最大的问题还是连锁更新导致性能不稳定。

LISTPACK优化

优化了连锁更新

LISTPACK是为了解决ZIPLIST最大的痛点——连锁更新，我们先来看，ZIPLIST的问题本源。我们知道，ZIPLIST需要支持LIST，LIST是一种双端访问结构，所以需要能从后往前遍历，上面有讲，ZIPLIST的数据节点的结构是这样的：

其中，prevlen就表示上一个节点的数据长度，通过这个字段可以定位上一个节点的数据，可以说，连锁更新问题，就是因为prevlen导致的。

所以我们需要一种不记录prevlen，并且还能找到上一个节点的起始位置的办法，Redis使用了很巧妙的一种方式。我们直接看LISTPACK的节点定义：

1 <encoding-type><element-data><element-tot-len>

encoding-type是编码类型

element-data是数据内容

element-tot-len存储整个节点除它自身之外的长度。

element-tot-len 所占用的每个字节的第一个bit用于标识是否结束。0是结束，1是继续，剩下7个bit来存储数据大小。当我们需要找到当前元素的上一个元素时，我们可以从后向前依次查找每个字节，找到上一个Entry的element-tot-len 字段的结束标识，就可以算出上一个节点的首位置了。举个例子：如果上个节点的element-tot-len为00000001 10000100,每个字节第一个bit标志是否结束，所以这里的element-tot-len一共就两个字节，大小为00000010000100,即132字节。