第7章 压缩列表

压缩列表(ziplist)时列表键和哈希键地底层实现之一. 当一个列表键只包含少量列表项, 并且每个列表项要么就是小整数值, 要么就是长度比较短的字符串, 那么Redis就会使用压缩列表来做列表键的底层实现.

7.1 压缩列表的构成

压缩列表是Redis为了节约内存而开发的, 由一系列特殊编码的连续内存块组成的顺序型(sequential)数据结构.

7.2 压缩列表节点的构成

• previous_entry_length属性的长度只能是1字节或5字节, 便于从后往前遍历节点:

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

  • 如果前一节点的长度大于等于254字节，那么previous_entry_length属性的长度为5字节：其中属性的第一字节会被设置为0xFE（十进制值254)，而之后的四个字节则用于保存前一节点的长度。

• encoding属性记录了节点的数据类型以及长度:

  • 一字节、两字节或者五字节长，值的最高位为00、01或者10的是字节数组编码：这种编码表示节点的content属性保存着字节数组，数组的长度由编码除去最高两位之后的其他位记录；

  • 一字节长，值的最高位以11开头的是整数编码：这种编码表示节点的content属性保存着整数值，整数值的类型和长度由编码除去最高两位之后的其他位记录；

7.3 连锁更新

在压缩列表中添加或删除节点可能导致它后一个节点的previous_entry_length字节数发生变化, 而这种变化又可能导致后续节点继续发生变化, 从而导致压缩列表的连锁更新.

因为连锁更新在最坏的情况下需要对压缩列表执行N次空间重分配操作, 而每次空间重分配最坏复杂度为O(N), 所以连锁更新的最坏情况为O(N^2). 但是连锁更新导致性能问题的几率很低:

• 条件严苛: 恰好有多个连续的长度介于250-253字节的节点;
• N不大就无所谓

7.4 压缩列表API