Redis设计与实现之压缩列表
压缩列表的构成
压缩列表的目的
压缩列表是 Redis 为了 节约内存 而开发的， 由一系列 特殊编码的连续内存块 组成的顺序型（sequential）数据结构。
压缩列表存储的数据
一个压缩列表可以包含 任意多个节点（entry） ， 每个节点可以保存 一个字节数组 或者 一个整数值 。
压缩列表的组成
各个部分说明
| 属性 | 类型 | 长度 | 用途 |
|---|---|---|---|
| zlbytes | uint32_t | 4字节 | 记录 整个压缩列表占用的内存字节数 ：在对压缩列表进行内存重分配，或者计算 zlend 的位置时使用 |
| zltail | uint32_t | 4字节 | 记录 压缩列表表尾节点距离压缩列表的起始地址有多少字节 ： 通过这个偏移量，程序无须遍历整个压缩列表就可以确定表尾节点的地址。 |
| zllen | uint16_t | 2字节 | 记录 压缩列表包含的节点数量 : 当这个属性的值小于 UINT16_MAX （65535）时， 这个属性的值就是压缩列表包含节点的数量； 当这个值等于 UINT16_MAX 时， 节点的真实数量需要遍历整个压缩列表才能计算得出。 |
| entryX | 列表数据节点 | 不定 | 压缩列表包含的各个节点，节点的长度由节点保存的内容决定。 |
| zlend | uint_8 | 1字节 | 特殊值 0xFF （十进制 255 ），用于 标记压缩列表的末端 。 |
压缩列表的示例
包含五个节点的压缩列表
- 列表 zlbytes 属性的值为 0xd2 （十进制 210）， 表示压缩列表的总长为 210 字节。
- 列表 zltail 属性的值为 0xb3 （十进制 179）， 这表示如果我们有一个指向压缩列表起始地址的指针 p ， 那么只要用指针 p 加上偏移量 179 ， 就可以计算出表尾节点 entry5 的地址。
- 列表 zllen 属性的值为 0x5 （十进制 5）， 表示压缩列表包含五个节点。
压缩列表节点的构成
存储数据
每个压缩列表节点可以保存一个字节数组或者一个整数值
支持的字节数组
- 长度小于等于 63 （2^{6}-1）字节的字节数组；
- 长度小于等于 16383 （2^{14}-1） 字节的字节数组；
- 长度小于等于 4294967295 （2^{32}-1）字节的字节数组
支持的整数值
- 4 位长，介于 0 至 12 之间的无符号整数；
- 1 字节长的有符号整数；
- 3 字节长的有符号整数；
- int16_t 类型整数；
- int32_t 类型整数；
- int64_t 类型整数。
压缩列表节点的构成
图示
具体实现可参照: ziplist.c/__ziplistInsert方法
- previous_entry_length : 记录前一个节点的长度
- encoding : 记录content所保存的数据类型及长度
- content : 节点具体保存的值
previous_entry_length属性
previous_entry_length 属性的长度可以是 1 字节 或者 5 字节 ：
- 如果前一节点的长度小于 254 字节， 那么 previous_entry_length 属性的长度为 1 字节： 前一节点的长度就保存在这一个字节里面
- 如果前一节点的长度大于等于 254 字节， 那么 previous_entry_length 属性的长度为 5 字节： 其中属性的第一字节会被设置为 0xFE （十进制值 254）， 而之后的四个字节则用于保存前一节点的长度。
前一个节点长度为5图示 : previous_entry_length 属性的值为 0x05 ， 表示前一节点的长度为 5 字节。
前一个节点长度为10086 : previous_entry_length 属性的值为 0xFE00002766,其中值的最高位字节 0xFE 表示这是一个五字节长的 previous_entry_length 属性， 而之后的四字节 0x00002766 （十进制值 10086 ）才是前一节点的实际长度。
计算前一个节点的指针地址
如果我们有一个指向当前节点起始地址的指针 c ， 那么我们只要用指针 c 减去当前节点 previous_entry_length 属性的值， 就可以得出一个指向前一个节点起始地址的指针 p,图示如下:
【知识点】
压缩列表的从表尾向表头遍历操作就是使用这一原理实现的： 只要我们拥有了一个指向某个节点起始地址的指针， 那么通过这个指针以及这个节点的 previous_entry_length 属性， 程序就可以一直向前一个节点回溯， 最终到达压缩列表的表头节点。
从表尾节点向表头节点进行遍历的过程
- 首先，我们拥有指向压缩列表表尾节点 entry4 起始地址的指针 p1 （指向表尾节点的指针可以通过指向压缩列表起始地址的指针加上 zltail 属性的值得出）
- 通过用 p1 减去 entry4 节点 previous_entry_length 属性的值， 我们得到一个指向 entry4 前一节点 entry3 起始地址的指针 p2
- 通过用 p2 减去 entry3 节点 previous_entry_length 属性的值， 我们得到一个指向 entry3 前一节点 entry2 起始地址的指针 p3
- 通过用 p3 减去 entry2 节点 previous_entry_length 属性的值， 我们得到一个指向 entry2 前一节点 entry1 起始地址的指针 p4 ， entry1 为压缩列表的表头节点
- 最终， 我们从表尾节点向表头节点遍历了整个列表
encoding 属性
节点的 encoding 属性记录节点的 content 属性所保存的 数据类型 以及 长度
- 1字节、2字节 或者 5字节 长， 值的最高位为 00 、 01 或者 10 的是字节数组编码： 这种编码表示节点的 content 属性保存着字节数组， 数组的长度由编码除去最高两位之后的其他位记录
- 1字节 长， 值的最高位以 11 开头的是整数编码： 这种编码表示节点的 content 属性保存着 整数值， 整数值的类型和长度由编码除去最高两位之后的其他位记录
可用的字节数组编码
| 编码 | 编码长度 | content属性保存的值 |
|---|---|---|
| 00bbbbbb | 1 字节 | 长度小于等于 63 字节的字节数组 |
| 01bbbbbb xxxxxxxx | 2 字节 | 长度小于等于 16383 字节的字节数组 |
| 10______ aaaaaaaa bbbbbbbb cccccccc dddddddd | 5 字节 | 长度小于等于 4294967295 的字节数组 |
所有可用的整数编码
| 编码 | 编码长度 | content属性保存的值 |
|---|---|---|
| 11000000 | 1 字节 | int16_t 类型的整数 |
| 11010000 | 1 字节 | int32_t 类型的整数 |
| 11100000 | 1 字节 | int64_t 类型的整数 |
| 11110000 | 1 字节 | 24 位有符号整数 |
| 11111110 | 1 字节 | 8 位有符号整数 |
| 1111xxxx | 1 字节 | 使用这一编码的节点没有相应的 content 属性， 因为编码本身的 xxxx 四个位已经保存了一个介于 0 和 12 之间的值， 所以它无须 content 属性 |
content 属性
节点的 content 属性负责保存节点的值， 节点值可以是一个 字节数组 或者 整数， 值的类型和长度由节点的 encoding 属性决定。
保存字节数组的示例
- 编码的最高两位 00 表示节点保存的是一个字节数组
- 编码的后六位 001011 记录了字节数组的长度 11
- content 属性保存着节点的值 “hello world”
保存整数的示例
- 编码 11000000 表示节点保存的是一个 int16_t 类型的整数值；
- content 属性保存着节点的值 10086 。