Redis实现-压缩列表

Redis实现-压缩列表

一、压缩列表在Redis中的使用

压缩列表(ziplist)是列表键和哈希键的底层实现之一。压缩列表是Redis为了节约内存而开发的。

当一个列表项，并且每个列表项要么就是小整数值，要么就是比较短的字符串，那么Redis就会使用压缩列表来做列表键的底层实现。

127.0.0.1:6379> rpush lst 1 3 5 10086 "hello" "world"
(integer) 6

当一个哈希键只包含少量键值对，并且每个键值对的键和值要么就是小整数值，要么就是比较短的字符串，那么Redis就会只用压缩列表作为哈希键的底层实现。

127.0.0.1:6379> hmset pro "name" "jack" "age" 18
OK

二、压缩列表的结构

1、压缩列表

压缩列表是一系列特殊编码的连续内存块组成的顺序型数据结构。

一个压缩列表可以包含任意多个结点，每个节点可以保存一个字节数组或者一个整数值。

属性	类型	长度
zlbytes	uint32_t	4字节
zltail	uint32_t	4字节
zllen	uint16_t	2字节
entry	列表节点	不定
zlend	uint8_t	1字节

• zlbytes

  # 用途
  记录整个压缩列表占用的内存字节数
  在对压缩列表进行内存重分配，或者计算zlend的位置时使用

• zltail

  # 用途
  记录压缩列表表尾节点距离起始地址有多少字节
  通过这个偏移量，程序无需遍历整个压缩列表就可以确定表尾节点的地址

• zllen

  # 用途
  记录了压缩列表包含的节点数量
  当这个数量小于UINT16_MAX(65535)时。这个属性的值就是压缩列表包含节点的数量
  当这个数量等于UINT16_MAX时，节点的真实数量需要遍历整个压缩列表才能计算得出

• entry

  # 用途
  压缩列表包含的各个节点，节点的长度由节点保存的内存决定

• zlend

  # 用途
  特殊值(OXFF)，用于标记压缩列表的末端

zlbytes属性的值为0xd2(十进制210)，表示压缩列表总长是210字节。

zltail属性的值为0xb3(十进制179)，这就可以计算出表尾节点entry3的地址。

zllen属性的值为0x5(十进制5)，表示压缩列表包含5个节点

2、压缩列表节点的构成

2.1、

每个压缩列表节点可以保存一个字节数组或者一个整数值。

字节数组可以是以下三种长度的其中一种：

1. 长度小于等于(2^6 - 1)字节的字节数组
2. 长度小于等于(2^14 - 1)字节的字节数组
3. 长度小于等于(2^32 - 1)字节的字节数组

整数值是以下六种长度的其中一种：

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

节点的结构：

• previous_entry_length

  以节点为单位，记录了压缩列表中前一个结点的长度。

  previous_entry_length属性的长度可以是1字节或者5字节。

  如果前一个结点的长度小于254字节，那么previous_entry_length属性的长度为1字节，前一个节点的长度就保存在这一个字节里面。

  如果前一个结点的长度大于等于254字节，那么previous_entry_length属性的长度为5字节，其中第一个字节会被设置为0xFE(十进制254)，四个字节保存前一个结点的长度

  用途：程序可以通过指针运算，根据当前节点的起始地址来计算出前一个结点的起始地址。

  

  在上图中P和C分别是entry2和entry3两个结点的起始值。如果已知了C地址。就可以都到P地址。

  P = C - entry3.previous_entry_length

  压缩列表的从表尾向表头遍历就是使用这一原理实现的，只要我们拥有了一个指向某个结点起始地址的指针，通过这个属性，程序就可以一直向前一个节点回溯，最终到达压缩列表的表头结点。

• encoding

  节点的encoding属性记录了节点的content属性所保存的类型以及长度。

  1. 一字节、两字节或者五字节，值的最高位为00、01或者10的是字节数组编码
     这种编码表示节点的content属性保存着字节数组，数组的长度由编码除去最高两位之后的其他位记录

  编码	编码长度	content属性保存的值
  00bbbbbb	1字节	长度小于等于(2^6 - 1)字节的字节数组
  01bbbbbb xxxxxxxx	2字节	长度小于等于(2^14 - 1)字节的字节数组
  10_ _ _ _ _ _ aaaaaaaa bbbbbbbb cccccccc dddddddd	5字节	长度小于等于(2^32 - 1)字节的字节数组

  2. 一字节长，值的最高位以11开头的是整数编码

     这种编码表示节点的content属性保存整数值，整数值的类型和长度由编码除去最高两位之后的其他位记录。

     编码	编码长度	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

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

  示例1

  

  编码最高两位00表示节点保存的是一个字节数组

  编码的后六位001011记录了字节数组的长度11。

  content属性保存着节点的值”hello world”。

​ 示例2

​

编码11000000表示节点保存的是以恶搞int16_t类型的整数值。

content属性保存着节点的值10086

三、连锁更新

每个节点的previous_entry_length属性都记录了前一个结点的长度。

previous_entry_length的长度由以下规则

如果前一个结点的长度小于254字节，previous_entry_length属性的长度为1字节

如果前一个结点的长度大于等于254字节，previous_entry_length属性的长度为5字节

现在，有一种情况：在一个压缩列表中，有多个连续的、长度介于250-253字节之间的结点。因为所有的结点长度都小于254字节，所以这些结点的previous_entry_length只需一个字节来存储。

这是，我们将一个长度大于等于254字节的新节点entry0设置为压缩列表的表头节点。

因为entry1的previous_entry_length属性长度是1个字节。没办法保存新节点的长度。所以程序将对压缩列表执行空间重分配操作，需要将entry1的previous_entry_length属性长度扩展到5字节长。

同样，entry1节点的长度增加，超过了254字节，entry2就无法保存entry1的节点长度。因此程序需要再次对压缩列表执行空间重分配操作。将entry2的previous_entry_length属性长度扩展到5字节长。

因为添加了entry0节点，导致了需要扩展entry1，引发了对entry2、entry3、entry4的扩展。为了让每个节点的previous_entry_length属性都符合压缩列表对节点的要求，程序需要不断对压缩列表执行空间重分配操作，知道entry4为止。

这种产生连续多次空间扩展操作称为"连锁更新"。

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

但是，它真正造成性能问题的机率是很低的

1. 长度介于250字节至253字节之间的节点，连锁更才有可能被引发。实际上情况并不多见
2. 只要更新的节点数量不多，就不会对性能造成影响。

四、压缩列表API

函数	作用
ziplistNew	创建一个新的压缩列表
ziplistPush	创建一个包含给定值的新节点，并将这个新节点添加到压缩列表到表头和表尾
ziplistInsert	将包含给定值的新节点插入到给定节点之后
ziplistIndex	返回压缩列表给定索引上的节点
ziplistNext	返回给定节点的下一个节点
ziplistDelete	从压缩列表中函数给定的节点