Redis数据结构三之压缩列表

本篇笔记介绍压缩列表。

在 Redis 3.2 版本之前，压缩列表是列表对象、哈希对象、有序集合对象的的底层实现之一。

因为压缩列表本身结构上的一些缺陷，压缩列表这个结构被替换了，但是压缩列表结构本身有一些可取之处，并且替换它的新结构 listpack 与之很相似，所以我们这里还是介绍一下压缩列表的结构和存储

1、压缩列表的结构

压缩列表是 Redis 为了节约内存而开发的，由一个连续内存块组成的顺序型数据结构。

它的组成结构如下：

| zlbytes | zltail | zllen | entry1 | entry2 | ... | entryN | zlend |

压缩列表的英文名是 ziplist，所以它的属性都是 zl 开头。

1. 列表属性介绍

zlbytes

zlbytes 长度为 4 字节，记录整个压缩列表占用的内存字节数

zltail

zltail 长度为 4 字节，记录压缩列表最后一个节点，也就是我们结构示例中的 entryN 到 zlbytes 的地址之间的偏移量。

zllen

zllen 长度为 2 字节，记录的是压缩列表包含的节点数量，也就是结构中的 N。

zlend

zlend 长度为 1 字节，它的值为 0xFF（十进制 255），用于标记压缩列表的末端。

2. 压缩列表节点属性介绍

对于每一个 entry 节点，也就是压缩列表中的元素节点，它的结构示意如下：

| previous_entry_length | encoding | content |

previous_entry_length

previous_entry_length 属性记录的是压缩列表中前一个节点的长度

previous_entry_length 属性本身的长度可以是 1 字节或者 5 字节

如果前一节点的长度小于 254 字节，那么 previous_entry_length 属性的长度为 1 字节，前一个节点的长度保存在这个字节里

如果前一节点的长度大于等于 254 字节，那么 previous_entry_length 属性的长度为 5 字节，第一个字节被设置成 0xFE（也就是 254），之后的四个字节用于前一节点的长度。

通过 previous_entry_length 属性，我们可以通过当前节点的地址和 previous_entry_length 属性，计算出前一个节点的起始地址，压缩列表的从表尾到表头的遍历操作就是使用这个原理一个节点一个节点往前回溯实现的。

encoding

encoding 属性记录了节点的 content 属性所保存数据的类型以及长度。

encoding 的值如果是一字节长，且值的最高位以 11 开头，那么表示是整数编码，表示 content 属性保存着整数值。

encoding 的值为 一字节、两字节、五字节长，且值的最高位为 00、01、10 则表示是字节数组编码

content

content 属性保存的是节点的值，可以是一个字节数组或者整数，值的类型和长度由节点的 encoding 属性决定。

2、 连锁更新

在压缩列表的节点属性中，previous_entry_length 属性的长度是根据前一节点的长度来进行赋值的，如果前一节点的长度小于 254 字节，那么下一节点的 previous_entry_length 属性长度为 1 字节，如果前一节点的长度大于等于 254 字节，那么下一节点的 previous_entry_length 属性为 5 字节。

那么在这种情况下，就存在一种较为极端的情况，那就是压缩列表中每个节点的长度都在 250 – 253 字节之间，这时候，如果在表头插入一个长度大于等于 254 字节的节点，那么相对应的第二个节点的 previous_entry_length 的长度就要从 1 字节变为 4 字节，那么该节点的整体长度就大于等于 254 字节。

依此类推，压缩列表的每一个节点的长度都会产生连锁反应，长度都会逐个变成大于等于 254 字节长度，程序就需要不断地对压缩列表执行空间重分配的操作。

Redis 将这种在特殊情况下产生的连续多次空间扩展操作称为连锁更新。

除了新增节点这种情况，还有一种删除节点也可能造成连锁更新的情况，比如有这么几个节点，big 节点的长度大于等于 254 字节，small 节点长度小于254 字节，e1 到 eN 的节点长度都在 250-253 字节之间。

| zlbytes | zltail | zllen | big | small | entry1 | entry2 | ... | entryN | zlend |

这时候，删除 small 节点，entry1 节点的前节点的长度就会从 250-253 变成大于等于 254，因此 entry1 节点的 previous_entry_length 长度就会变成 5 字节，entry1 整体长度就会大于等于 254 字节，依次之后每个节点都会这样产生连锁更新。

尽管连锁更新的复杂度较高，但它真正造成性能问题的几率是很低的：

首先，压缩列表里要恰好有多个连续的、长度介于 250-253 字节之间的节点，连锁反应才有可能被引发

其次，即使出现连锁更新，但只要被更新的节点数量不多，就不会对性能造成任何影响，比如对只拥有三五个节点的压缩列表进行连锁更新。

3、压缩列表缺点

压缩列表虽然能节约内存，但仍然存在一些缺点：

• 需要通过遍历操作来查找节点，元素过多时会造成查询效率低下
• 对压缩列表节点进行新增或者修改时，可能会造成连锁更新的问题