Redis(6) —— 底层数据结构 —— ziplist(压缩列表)
压缩列表是列表键和哈希键的底层实现之一
1. 压缩列表的用处
- 当一个列表键只包含少量列表项,且每个列表项是小整数值或短字符串,那么 Redis 就是用压缩列表来作为列表的底层实现。
- 当一个哈希键只包含少量键值对,并且每个键值对的键和值是小整数值或短字符串,那么 Redis 就会使用压缩列表来作为哈希键的底层实现。
2. 压缩列表的构成
压缩列表是由一系列特殊编码的连续内存块组成的顺序性数据结构。一个压缩列表可以包含任意多个节点(entry),每个节点可以保存一个字节数组或者一个整数值。
zlbytes: 记录整个压缩列表所占用的字节数:在对压缩列表进行内存重分配,或者计算zlend的位置时使用
zltail: 记录距离压缩列表表尾节点距离压缩列表的起始地址有多少字节
zllen: 记录了压缩列表的节点数量: 如果这个值小于 UNIX16_MAX(65535) 时,这个属性就是表示压缩列表节点的数量。大于等于 UNIX16_MAX 时,压缩列表节点的数量需要遍历才能得出
entryX: 压缩列表的节点,节点的长度由保存的内容决定
zlend: 用于标记压缩列表的末端
3. 压缩列表节点的构成
每个压缩列表节点可以保存一个字节数组或者一个整数值,且每个压缩列表节点都是由 privious_entry_length、encoding、content 三部分组成
字节数组的三种长度:(就是能表示长度在 32 字节以内的字符数组)
- 长度小于等于 63(26 - 1) 字节的字节数组
- 长度小于等于 16383(214 - 1) 字节的字节数组
- 长度小于等于 4294967295(232 - 1) 字节的字节数组
整数型值的六种长度:
- 4 位长,0 ~ 12 之间的无符号整数
- 1 字节长的有符号整数
- 3 字节长的有符号整数
- int16_t 类型整数
- int32_t 类型整数
- int64_t 类型整数
节点的 previous_entry_length 属性:
- 节点的 previous_entry_length 以字节为单位,记录前一个节点的长度
- 如果前一个节点的长度小于 254 字节,那么 previous_entry_length 属性长度为 1 字节:前一节点的长度就保存在这一个字节里面
- 如果前一个节点长度大于等于 254 字节,那么 privous_entry_lenght 属性长度为 5 字节,第一字节被设置为 0xFE(254),之后的四个字节保存前一节点的数量
- 压缩列表的从尾向头遍历就是根据这个属性实现的:当前节点的指针地址 - 前一节点的长度 = 前一节点的起始地址
节点的 encoding 属性:
- 节点的 encoding 属性记录了节点的 content 属性所保存数据的类型及长度
- 一字节、两字节或者五字节长,值得最高位为 00、01、10 的是字节数组编码;数组长度为编码去除最高两位的其他位记录
- 一字节长,值的最高位为 11,这种编码表示 content 保存的为整数值,整数值的类型和长度由编码出去最高两位之后的其它位记录。
节点的content属性:
- 节点的 content 属性负责保存节点的值。
- 节点值可以是一个字节数组或者整数,值的类型和长度由节点 encoding 属性决定
4. 连锁更新
添加新节点和删除节点都可能引发连锁更新:更改节点后的节点的 previous_entry_lenght 都可能改变而导致后面节点的 privous_entry_lenght 都可能发生改变。
参考资料
[1].《Redis 设计与实现》