August's Box

Redis设计与实现笔记-章7.压缩列表

压缩列表(ziplist)是哈希键和列表键的底层实现之一(当一个列表键只包含少量元素,不超过list_max_ziplist_entries的配置,并且元素要么是小整数或短字符串时),是为了节约内存,由一系列特殊编码的连续内存块组成的顺序型数据结构。一个压缩列表可以包含任意多个节点(entry),每个节点可以保存一个字符数组或一个整数值。

压缩列表的定义

ziplist结构

ziplist的整体布局如下:


| zlbytes | zltail | zllen | entry1 | entry2 |entry3 | … | entryN | zlend |
|:——-:|:——:|:—–:|:——:|:——:|:—–:|:—:|:——:|:—–:|

不同组成部分的类型和用途如下:

  • zlbytes: uint32_t类型,占4字节,记录整个ziplist占用字节数,在对ziplist进行内存重分配或定位zlend时使用
  • zltail: uint32_t类型,占4字节,记录尾节点距离ziplist起始地址的距离,即偏移量,用于定位尾节点位置
  • zllen: uint16_t类型,占2字节,记录ziplist包含节点的数目,当值小于UINT16_MAX(65535)时为节点数目,当值等于UINT16_MAX时需要遍历ziplist才能计算
  • entryX:节点类型,可以是字符数组也可以是整数值,长度由节点内容决定
  • zlend:uint8_t类型,占1字节,特殊值0xFF(255),用于标记ziplist末端

entry的定义

entry节点由以下三个部分构成:

| previous_entry_length | encoding | content |

不同组成部分的类型和用途如下:

  • previous_entry_length: 表示前一个节点的长度,以字节为单位,该属性可以为1个字节或5个字节,当前一个节点的长度小于254字节时该属性为1个字节(例:0x05),保存的即前一个节点的长度(5),当前一个节点的长度大于等于254字节时该属性为5个字节(例:0xFE00002766),其中第一个字节为默认值0xFE(254),后四个字节保存前一个节点的长度(0x00002766,10086)。通过该属性,我们可以从尾节点开始往前实现ziplist的遍历(当前指针向前偏移该属性即可)
  • encoding: 记录content保存的数据的类型和长度,该属性可以为1字节、2字节和5字节长。当属性为1字节且最高位为11开始的表示整数,其他表示字节数组。具体内容如下:
编码 编码长度 content属性保存的值
11000000 1字节 int16_t类型的整数
11010000 1字节 int32_t类型的整数
11100000 1字节 int64_t类型的整数
11110000 1字节 24位有符号整数
11111110 1字节 8位有符号整数
1111xxxx 1字节 该编码无content属性,xxxx位保存的是(1111xxxx & 0x0f) - 1,范围为0~12
00bbbbbb 1字节 长度小于等于63字节的字节数组
01bbbbbb xxxxxxxx 2字节 长度小于等于16383字节的字节数组
10__ aaaaaaaa bbbbbbbb cccccccc dddddddd 5字节 长度小于等于4294967295字节的字节数组,不包含_部分
  • content: 保存节点的值,类型和长度由encoding决定

连锁更新

previous_entry_length的定义可知,该属性记录了前一节点的长度,当ziplist中所有节点的长度均介于250-253之间时候,每个节点的previous_entry_length属性都是一个字节。当在头部插入一长度大于等于254的节点时,原来头部e1的节点previous_entry_length属性需要扩展到5节点,此时需要对ziplist执行空间重新分配,重新分配后e1的长度又大于等于254,e2也需要扩容,从而引起连锁更新。此时复杂度成为O(N^2),同理删除长节点链表里某一短节点时等等,均会出现连锁更新(ps:当ziplist节点均介于254-257时插入短节点不会出现连锁更新,避免抖动直接用5字节存储了只需要1字节的长度编码__ziplistCascadeUpdate)。不过,这些情况出现的概率很低,所以更新的平均复杂度在O(N)。

ziplist相关API

相关api定义在ziplist.h里,实现在ziplist.c,主要api如下:

函数 作用和代码逻辑 时间复杂度
ziplistNew 创建新的压缩列表,为表头和表末端分配内存,初始化几个属性 O(1)
ziplistPush 添加新节点到ziplist的头部或尾部,根据where参数计算插入位置是头部还是尾部,调用__ziplistInsert:1. 获取插入位置前一个节点的长度 2. 尝试转换插入字符串为整数(zipTryEncoding)并计算插入节点所需字节长度(节点值长度+前置节点长度编码长度+当前节点值encoding长度)3. 插入新节点不在末端时,计算插入位置节点的前置节点长度编码长度字节和当前节点的长度编码长度字节大小差nextdiff(zipPrevLenByteDiff)来resize当前的ziplist(ziplistResize,不改变原有数据)4. 后移现有元素,将新元素的长度编码到后置节点,设置表尾迁移量,如果nextdiff不为0还需级联更新后续节点(__ziplistCascadeUpdate,计算前置节点长度编码所需字节和当前previous_entry_length长度,少则扩容继续更新,多或者够用即退出,连锁更新可能出现) 5. 写入新节点,设置新节点三个属性,更新ziplist的length O(N),最坏情况O(N^2)
ziplistInsert 插入新节点到指定节点之后,__ziplistInsert O(N),最坏情况O(N^2)
ziplistIndex 返回给定索引上的节点,索引为正从头开始,计算节点占用字符累加进行遍历zipRawEntryLength,负从尾开始,根据前置节点长度累减进行遍历 O(N)
ziplistFind 查找并返回包含指定值的节点,skip参数表示隔skip个节点查找,ziplist encode其他结构时(如hash)使用 查找值是整数时为O(N),字节数组时为O(N^2)(compare为O(N))
ziplistNext 返回给定节点下一个节点,加zipRawEntryLength得到 O(1)
ziplistPrev 返回给定节点前一个节点,减去前置节点长度得到 O(1)
ziplistGet 返回给定节点保存的值,根据encoding返回值和是否成功 O(1)
ziplistDelete 删除给定节点,调用__ziplistDelete(删除给定节点后num个节点,传入num参数为1):1. 计算被删除节点占用字节数,计算第一个删除节点的前置节点的长度编码所需字节和最后一个删除节点的后置节点first已有前置节点长度的编码所需字节长度差nextdiff 2. 更新first节点的前置节点长度编码,前移后续节点,resize和设置ziplist相关属性 3. nextdiff不为0时进行级联更新后续节点(__ziplistCascadeUpdate O(N),最坏情况O(N^2)
ziplistDeleteRange 删除连续几个节点,调用__ziplistDelete O(N),最坏情况O(N^2)
ziplistBlobLen 返回ziplist占用字节数,直接返回 O(1)
ziplistLen 返回ziplist包含节点数量 数量小于65535时为O(1),否则遍历统计O(N)