压缩列表

压缩列表是redis重要的一种底层结构,这个不懂也得知道点…

概念

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

压缩列表结构组成

属性	类型	长度	用途
zlbytes	uint32_t	4字节	记录整个压缩列表占用的内存字节数,在对压缩列表进行内存重分配,或者计算zlend的位置时使用
zltail	uint32_t	4字节	记录压缩列表表尾节点距离压缩列表的起始地址有多少字节,通过这个偏移量,程序无须遍历整个压缩列表就可以确定表尾节点的地址
zllen	uint16_t	2字节	记录了压缩列表包含的节点数量,当这个属性的值小于 UINT16_MAX(65535)时,这个属性的值就是压缩列表包含节点的数量,当这个值等于UINT16_MAX时,节点的真实数量需要遍历整个压缩列表才能计算得出
entryX	列表节点	不定	压缩列表包含的各个节点,节点的长度由节点保存的内存决定
zlend	uint8_t	1字节	特殊值0xFF(十进制255),用于标记压缩列表的末端

压缩列表示例

列表zlbytes属性的值为0xd2(十进制210),表示压缩列表的总长度为210字节
列表zltail属性的值为0xb3(十进制179),表示如果我们有一个指向压缩列表起始地址的指针p,那么只要用指针p加上偏移量179,就可以计算出表尾节点entry5的地址
列表zllen属性的值为0x5(十进制5),表示压缩列表包含五个节点

压缩列表节点

previous_entry_length：每个节点会使用一个或者五个字节来描述前一个节点占用的总字节数，如果前一个节点占用的总字节数小于 254，那么就用一个字节存储，反之如果前一个节点占用的总字节数超过了 254，那么一个字节就不够存储了，这里会用五个字节存储并将第一个字节的值存储为固定值 254 用于区分。
encoding：压缩列表可以存储 16位、32位、64位的整数以及字符串，encoding 就是用来区分后面的 content 字段中存储于的到底是哪种内容，分别占多少字节
content：没什么特别的，存储的就是具体的二进制内容，整数或者字符串。

分为两种

字节数组编码

编码	编码长度	content类型
00xxxxxx	一个字节	长度小于 63 字节的字节数组
01xxxxxx xxxxxxxx	两个字节	长度小于 16383 字节的字节数组
10xxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx	五个字节	长度小于 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属性负责保存节点的值,节点值可以是一个字节数组或者整数,值的类型和长度由节点的encoding属性决定

注意,整型数据的编码是固定11开头的八位二进制,而字符串类型的编码都是非固定的,因为它还需要通过后面的二进制位得到字符串的长度,稍有区别

previous_entry_length属性记录了前一个节点的长度,如果前一个节点长度小于254个字节,那么previous_entry_length属性需要用一个字节长度来保存这个长度值

现在假如一个压缩列表,有许多连续的,长度介于250~253字节之间的节点e1至eN

压缩列表的连锁更新

现在这些节点的previous_entry_length都只需要1字节长的,如果这时候我将长度为254的新节点new设置为压缩列表的表头节点,那么new就是e1的前置节点..

那么此时e1的previous_entry_length需要进行扩展,因为1节点肯定不够的,更新后,e1超出了254,所以e2的previous_entry_length也需要更新…

这样就会导致所有节点都会发生更新..

Redis将这种在特殊情况下产生的连续多次空间扩展操作称之为 “连锁更新”

因为连锁更新在最坏的情况下需要对压缩列表执行N次空间重分配操作,而每次空间重分配的最坏复杂度为O(N),所以连锁更新最坏的复杂度为O(N²)

但是,尽管连锁更新的复杂度较高,但它真正造成性能问题的几率非常低.因为很难恰好所有节点连续且长度都介于250字节到253字节之间..一般对几个节点进行连锁更新是不会影响性能的!

以上是我从各方渠道总结而来..大部分摘自 <Redis 设计与实现> 这本书