Reids数据结构学习 - 压缩列表(六)

压缩列表是列表键和hash键的底层实现之一, 当一个键只包含少量列表项、且每个列表项要么是小整数值、要么是长度比较短的字符串、那么redis就会使用压缩列表作为底层实现

压缩列表的组成

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

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

zltytes: 压缩列表的总长度

zltail: 表示表头和表尾节点的位置偏移量

zllen: 表示压缩列表包含的节点数

压缩列表节点的构成

每个压缩列表节点可以保存一个字节数组或者一个整数值, 字节数组可以是下边任意一种:

1. 长度小于等于63(2⁶-1)字节的字节数组
2. 长度小于等于16383 (2¹⁴-1)字节的字节数组
3. 长度小于等于 4294964295 (2³²-1)字节的字节数组

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

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

每个压缩列表节点由 previous_entry_length、encoding、content 三个部分组成

previous_entry_length

节点的previous_entry_length 属性以字节为单位, 记录压缩列表前一个节点的长度, 可以是1字节 或者 5字节, 若前一个节点的长度＜254字节, 则 previous_entry_length 的长度为1字节, 前一个节点的长度保存在这里; 若前一节点的长度≥254字节, 则privous_entry_length 的属性为 5字节, 其中第一字节的值为 0xFE(254)

因为节点的previous_entry_length 属性记录了前一个节点的长度, 所以程序可以通过指针运算、根据当前节点的起始地址计算前一个节点的起始地址, 压缩列表的 从表尾向表头遍历 操作是使用这一原理实现的. 完整过程如下:

• 首先、我们拥有指向压缩列表表尾节点 entry4 起始地址的指针p1(指向表尾节点的指针可以通过指向压缩列表 起始地址的指针 + zltail 属性得到)
• 通过 p1 - entry4.previous_entry_lenght 可以得到指向entry4 节点的前一节点entry3 的起始地址指针p2
• 同理可以得到 entry2 的起始指针 p3 和 entry1 的起始指针 p4, 完成整个压缩列表的遍历

encoding

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

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

content 属性

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

• 编码的最高两位 00 表示节点保存的是一个字节数组
• 编码的后六位 001011 记录字节数组的长度 11
• content属性保存着节点值 hello world

• 编码 11000000 表示节点保存的是一个 int16_t 类型的整数值
• content 属性保存着节点的值 10086

连锁更新

每个节点的previous_entry_length 属性记录了前一个节点的长度, 若<254字节, 需要1字节空间保存, 若≥254字节, 需要5字节空间保存, 假设现有1压缩列表, e1 ~ eN 节点的长度都在 250~253字节之间, 此时, 若需要插入一个长度≥254字节的节点new到表头, 那么new节点将成为e1的前置节点, 因为e1的previous_entry_length属性仅1字节, 无法保存new节点的属性, 需要重新对压缩列表执行空间分配, 扩展e1节点的previous_entry_length属性, 那么麻烦事儿来了…, e1原本的长度介于250~253之间, e2.privous_entry_length可以使用1字节, 现在e1的长度为 250+4 ~ 253+4, e2就需要5字节来记录e1的长度, …., 依次引起连锁更新, 程序需要不断扩展空间, 类似的、删除节点也可能早上连锁更新

最坏情况下、需要对压缩列表执行N次空间重分配工作, 每次空间重分配的最坏复杂度为 O(N), 所以连锁更新的最坏复杂度为 O(N²), 复杂度非常高, 但真正造成性能问题的概率很小:

• 压缩列表恰好有多个连续的、长度介于250~253字节之间的节点、连锁更新才可能被引发, 这种情况本身出现的概率较低
• 即时出现连锁更新、但只要被更新的节点不多、就不会对性能造成影响, eg、三五个节点的连锁更新绝不会影响性能

所以: ziplistPush的平均时间复杂度仅为 O(N), 可以放心的使用

重点回顾

• 压缩列表是一种为节约内存而开发的顺序型数据结构
• 压缩列表是列表键和hash键的底层实现之一
• 压缩列表可以包含多个节点、每个节点可以保存一个字节数组或者整数值
• 添加新节点到压缩列表、或者从压缩列表删除节点，可能会引起连锁更新操作, 但概率较低