压缩列表(ziplist)

ziplist是一个经过特殊编码的双向链表，它的设计目标是节省内存。它可以存储字符串或者整数。其中整数是按二进制进行编码的，而不是字符串序列。

它能以O(1)的时间复杂度在列表的两端进行push和pop操作。但是由于每个操作都 u 要对ziplist所使用的内存进行重新分配，所以实际操作的复杂度与ziplist占用的内存大小有关。

在redis中，有序集合、散列和列表都直接或间接使用了压缩列表。当有序集合或散列的元素个数较少，并且元素都是短字符串时，redis便会使用压缩列表作为底层数据存储。redis的列表使用的快速链表数据结构进行存储，而快速链表就是双向链表与压缩列表的组合。

总的来说，ziplist有如下特性：

  • 本质上是一个字节数组
  • 是redis为了节约内存而设计的一种线性结构
  • 可以包含多个元素，每个元素可以是一个字节数组或一个整数

在redis中，压缩列表主要由 5 部分组成：

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

191708309348283.png

如上图所示，这是一个包含三个节点的压缩列表的示例：

  • zlbytes 属性的值为 0x50（十进制 80），表示压缩列表的总长为 80 字节。
  • zltail 属性的值为 0x3c（十进制 60），这表示如果我们有一个指向压缩列表起始地址的指针 p，那么只要用指针 p 加上偏移量 60，就可以计算出表尾节点 entry3 的地址。
  • zllen 属性的值为 0x3（十进制 3），表示压缩列表包含三个节点。

对于压缩列表而言，每个entry的数据结构又包含三部分，分别是：

  • previous_entry_length:表示前一个元素的长度，占 1 字节或者 5 字节
    • 当前一个元素的长度小于 254 字节时，使用 1 字节表示记录上一个元素长度
    • 当前一个元素的长度大于或等于 254 字节时，用 5 字节表示。其中第一个字节固定为0xFE(十进制为 254)，后 4 字节才是上一个元素的真正长度
  • encoding：当前元素的编码，记录节点的content字段锁保存的数据的类型以及长度，它的类型一共有两种，分别是字节数组和整数。它的长度可能为 1字节、2 字节或者 5 字节
  • content：用于保存当前节点的内容，节点内容类型和长度由encoding决定

encoding内容说明

当content要存储的数据是字节数组时:

内容 长度 描述
00 bbbbbb 1字节 最大长度为 63 的字节数组
01 bbbbbb xxxxxxxx 2字节｜最大长度 2^14-1的字节数组
10 ________ aaaaaaaa bbbbbbbb cccccccc dddddddd 5字节 最大长度2^32-1的字节数组

当content要存储的数据是整数时：

内容 长度 描述
11000000 1字节 int16_t类型整数(2字节)
11010000 1字节 int32_t类型整数(4字节)
11100000 1字节 int64_t类型整数(8字节)
11110000 1字节 24位有符号整数(3字节)
11111110 1字节 8 位有符号整数(1字节)
1111xxxx 1字节 用xxxx思维表示内容，此时将不在需要content
11111111 1字节 表示压缩列表的结束