【Redis】—— 压缩列表 redis

压缩列表压缩列表（ziplist）是列表键和哈希键的底层实现之一。当一个列表键只包含少量列表项，并且每个列表项要么就是小整数值，要么就是长度比较短的字符串，那么 Redis 就会使用压缩列表来做列表键的底层实现。
压缩列表的构成压缩列表是 Redis 为了节省内存而开发的，是由一系列特殊编码的连续内存块组成的顺序型数据结构。一个压缩列表可以包含任意多个节点（entry），每个节点可以保存一个字节数组或者一个整数值。

文章图片

zlbytes ：4字节，记录整个压缩列表占用的内存字节数。在对压缩列表进行内存重分配或者计算 zlend 的位置时使用
zltail ：4字节，记录压缩列表表尾节点距离压缩列表的起始地址有多少个字节。通过这个偏移量，无须便利整个压缩列表就可以确定表尾节点的地址
zllen ：记录了压缩列表包含的节点数量。当这个属性的值小于 65535 时，这个属性的值就是压缩列表包含节点的数量，当这个值等于 65535 时，节点的真实数量需要便利才能计算得出
entryX ：压缩列表包含的各个节点，节点的长度由节点保存的内存决定
zlend ：特殊值 0xFF（十进制 255），用于标记压缩列表的末端

压缩列表节点的构成每个压缩列表可以保存一个字节数组或者一个整数值。
每个压缩列表节点都由 previous_entry_length 、encoding 、content 三个部分组成。
previous_entry_length
previous_entry_length 属性以字节为单位，记录了压缩列表中前一个节点的长度。previous_entry_length 属性的长度可以是 1 字节或者 5 字节。

如果前一节点的长度小于 254 字节，那么 previous_entry_length 属性的长度为 1 字节；否则长度为 5 字节，其中属性的第一个字节设置为 0xFE ，而之后的四个字节则用于保存前一节点的长度。

压缩列表从表尾向表头遍历操作就是使用这一原理实现的，只要拥有了一个指向某个节点起始地址的指针，那么通过这个指针以及这个节点的 previous_entry_length 属性，就可以一直向前一个节点回溯，最终到达压缩列表的表头节点。
encoding
encoding 属性记录了节点的 content 属性所保存数据的类型以及长度。
content
节点的 content 属性负责保存节点的值，节点值可以是一个字节数组或者整数，值的类型和长度由节点的 encoding 属性决定。
连锁更新由于每个节点的 previous_entry_length 属性都记录了前一个节点的长度，假如存在一个压缩列表中，又多个连续的、长度介于 250 字节到 253 字节之间的节点，这时将一个长度大于等于 254 字节的新节点设置为压缩列表的表头节点，之前的第一个节点中的 previous_entry_length 属性长度仅为 1，没办法保存新节点的长度，所以会对压缩列表执行空间重分配操作，将当前节点的 previous_entry_length 属性从原来的 1 字节长拓展为 5 字节长。
同理，当前节点发生重分配操作后，可能会影响到后面的下一个节点，最坏情况下，可能会一直影响到最后一个节点。
Redis 将这种在特殊情况下产生的连续多次空间拓展操作称之为”连锁更新“。
除了添加新节点可能会引发连锁更新之外，删除节点也可能会引发连锁更新。
因为连锁更新在最坏情况下需要对压缩列表执行 N 次空间重分配操作，而每次空间重分配的最坏复杂度为 O(N)，所以连续更新的最坏复杂度为 O(N2)。
【【Redis】—— 压缩列表】尽管连锁更新的复杂度较高，但真正造成性能问题的几率是很低的。首先，压缩列表里恰好有多个连续的、长度介于 250 字节至 253 字节之间的节点，连锁更新才可能被触发，在实际中，这种情况并不多见。其次，即使出现连锁更新，但只要被更新的节点数量不多，就不会对性能造成任何影响。