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

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

压缩列表的组成

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

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

压缩列表.png

zltytes: 压缩列表的总长度

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

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

压缩列表节点的构成

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

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

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

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

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

压缩列表节点.png

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, 完成整个压缩列表的遍历

从尾部向头部变量压缩列表.png

encoding

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

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

压缩列表字节数组.png

压缩列表整型值.png

content 属性

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

压缩列表保存字符数组示例.png

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

压缩列表保存整型值示例.png

编码 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键的底层实现之一
压缩列表可以包含多个节点、每个节点可以保存一个字节数组或者整数值
添加新节点到压缩列表、或者从压缩列表删除节点，可能会引起连锁更新操作, 但概率较低