Redis基础数据结构——压缩列表(ZipList)

2021年10月18日 180点热度 1人点赞 0条评论

压缩列表(ziplist)是列表键和哈希键的底层实现之一。

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

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

压缩列表的实现

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

压缩列表的构成

一个压缩列表可以包含任意多个节点(entry), 每个节点可以保存一个字节数组或者一个整数值。

下图展示了压缩列表的各个组成部分:


下表记录了各个组成部分的类型、长度、以及用途:

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

可以看出,压缩列表主要是用压缩列表节点来存储数据的。

压缩列表节点的构成

每个压缩列表节点可以保存一个字节数组或者一个整数值, 其中, 字节数组可以是以下三种长度的其中一种:

  1. 长度小于等于 63 ($2^{6}-1$)字节的字节数组;
  2. 长度小于等于 16383 ($2^{14}-1$) 字节的字节数组;
  3. 长度小于等于 4294967295 ($2^{32}-1$)字节的字节数组;

而整数值则可以是以下六种长度的其中一种:

  1. 4 位长,介于 012 之间的无符号整数;
  2. 1 字节长的有符号整数;
  3. 3 字节长的有符号整数;
  4. int16_t 类型整数;
  5. int32_t 类型整数;
  6. int64_t 类型整数。

每个压缩列表节点都由 previous_entry_lengthencodingcontent 三个部分组成, 如图 7-4 所示。

接下来将分别介绍这三个组成部分。

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 属性所保存数据的类型以及长度:

  • 一字节、两字节或者五字节长, 值的最高位为 0001 或者 10 的是字节数组编码: 这种编码表示节点的 content 属性保存着字节数组, 数组的长度由编码除去最高两位之后的其他位记录;
  • 一字节长, 值的最高位以 11 开头的是整数编码: 这种编码表示节点的 content 属性保存着整数值, 整数值的类型和长度由编码除去最高两位之后的其他位记录;

表 7-2 记录了所有可用的字节数组编码, 而表 7-3 则记录了所有可用的整数编码。 表格中的下划线 _ 表示留空, 而 bx 等变量则代表实际的二进制数据, 为了方便阅读, 多个字节之间用空格隔开。


表 7-2 字节数组编码

编码 编码长度 content 属性保存的值
00bbbbbb 1 字节 长度小于等于 63 字节的字节数组。
01bbbbbb xxxxxxxx 2 字节 长度小于等于 16383 字节的字节数组。
10______ aaaaaaaa bbbbbbbb cccccccc dddddddd 5 字节 长度小于等于 4294967295 的字节数组。

表 7-3 整数编码

编码 编码长度 content 属性保存的值
11000000 1 字节 int16_t 类型的整数。
11010000 1 字节 int32_t 类型的整数。
11100000 1 字节 int64_t 类型的整数。
11110000 1 字节 24 位有符号整数。
11111110 1 字节 8 位有符号整数。
1111xxxx 1 字节 使用这一编码的节点没有相应的 content 属性, 因为编码本身的 xxxx 四个位已经保存了一个介于 012 之间的值, 所以它无须 content 属性。

content

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

agedcat_xuanzai

这个人很懒,什么都没留下

文章评论