Redis设计与实现-第7章-压缩列表

Posted on | Edited on | In

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

1
2
3
4
5
redis> RPUSH lst 1 3 5 10086 "hello" "world"
(integer) 6

redis> OBJECT ENCODING lst
"ziplist"

压缩列表的构成

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

一个压缩列表有一下几个组成部分

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

压缩列表节点的构成

每个压缩列表节点可以保存一个字节数组或者一个整数值，而每个节点都由previous_entry_length、encoding、content三个部分组成。

整数编码可以保存的类型：

  • 4位长，介于0-12之间的无符号整数
  • 1字节长的有符号整数
  • 3字节长的有符号整数
  • uint16_t类型
  • uint32_t类型
  • uint64_t类型

previous_entry_length

节点的previous_entry_length属性以字节为单位，记录了压缩列表中前一个节点的长度。因为有了这个长度，所以程序可以通过指针运算，根据当前节点的起始地址来计算出前一个节点的起始地址。

压缩列表的从表尾向表头遍历操作就是使用这一原理实现的。

encoding

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

  • 一字节、两字节或者五字节，值的最高位为00、01或者10的是字节数组编码。
  • 一字节，值的最高位以11开头的是整数编码。

content

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

连锁更新

由于previous_entry_length可能是一个或者五个字节，所有插入和删除操作带来的连锁更新在最坏情况下需要对压缩列表执行N次空间重分配操作，而每次空间重分配的最坏复杂度为O(N)，所有连锁更新的最坏复杂度为O(N^2)。

但连锁更新的条件比较苛刻，而且压缩列表中的数据量也不会太多，因此不需要注意性能问题，平均复杂度仍然是O(N)。