前言

与整数集合（intset）一样，压缩列表（ziplist）也不是基础数据结构，而是 Redis 自己设计的一种数据存储结构。它有点儿类似数组，通过一片连续的内存空间来存储数据。不过，它跟数组不同的一点是，它允许存储的数据大小不同。

一、压缩列表原理

听到“压缩”两个字，直观的反应就是节省内存。之所以说这种存储结构节省内存，是相较于数组的存储思路而言的。我们知道，数组要求每个元素的大小相同，如果我们要存储不同长度的字符串，那我们就需要用最大长度的字符串大小作为元素的大小（假设是 20 个字节）。存储小于 20 个字节长度的字符串的时候，便会浪费部分存储空间。

数组的优势是占用一片连续的空间，可以很好地利用 CPU 缓存访问数据。如果我们想要保留这种优势，又想节省存储空间，我们可以对数组进行压缩。

但是这样有一个问题，我们在遍历它的时候，由于不知道每个元素的大小是多少，因此也就无法计算出下一个节点的具体位置。这个时候，我们可以给每个节点增加一个 length 的属性。

如此，我们在遍历节点的时候就知道每个节点的长度（占用内存的大小），就可以很容易计算出下一个节点在内存中的位置。这种结构就像一个简单的压缩列表了。

二、Redis 压缩列表实现

压缩列表（ziplist）是列表和哈希的底层实现之一。

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

2.1 Redis 压缩列表的构成

压缩列表是 Redis 为了节约内存而开发的，是由一系列特殊编码的连续内存块组成的顺序型（sequential）数据结构。一个压缩列表可以包含任意多个节点（entry），每个节点可以保存一个字节数组或者一个整数值，如下图。

示例：

如上图，展示了一个总长为 80 字节，包含 3 个节点的压缩列表。如果我们有一个指向压缩列表起始地址的指针 p，那么表尾节点的地址就是 p+60。

2.2 Redis 压缩列表节点的构成

每个压缩列表节点可以保存一个字节数组或者一个整数值。其中，字节数组可以是以下三种长度中的一种：

  • 长度小于等于 63 (2^6-1) 字节的字节数组；
  • 长度小于等于 16383 (2^14-1) 字节的字节数组；
  • 长度小于等于 4294967295 (2^32-1) 字节的字节数组。

整数值可以是以下 6 种长度中的一种：

  • 4 位长，介于 0 至 12 之间的无符号整数；
  • 1 字节长的有符号整数；
  • 3 字节长的有符号整数；
  • int16_t 类型整数；
  • int32_t 类型整数；
  • int64_t 类型整数。

节点的 previous_entry_length 属性以字节为单位，记录了压缩列表中前一个节点的长度。previous_entry_length 属性的长度可以是 1 字节或者 5 字节。

  • 如果前一节点的长度小于 254 字节，那么 previous_entry_length 属性的长度为 1 字节，前一节点的长度就保存在这一个字节里面。
  • 如果前一节点的长度大于等于 254 字节，那么 previous_entry_length 属性的长度为 5 字节：其中属性的第一字节会被设置为 0xFE（十进制值 254），而之后的四个字节则用于保存前一节点的长度。

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

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

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

  • 编码的最高两位 00 表示节点保存的是一个字节数组。
  • 编码的后六位 001011 记录了字节数组的长度 11。
  • content 属性保存着节点的值 "hello world"。
  • 编码 11000000 表示节点保存的是一个 int16_t 类型的整数值。
  • content 属性保存着节点的值 10086。

2.3 常用操作的时间复杂度

操作时间复杂度
创建一个新的压缩列表O(1)
创建一个包含给定值的新节点，并将这个新节点添加到压缩列表的表头或者表尾平均 O(N)，最坏 O(N^2) (可能发生连锁更新)
将包含给定值的新节点插入到给定节点之后平均 O(N)，最坏 O(N^2) (可能发生连锁更新)
返回压缩列表给定索引上的节点O(N)
在压缩列表中查找并返回包含了给定值的节点因为节点的值可能是一个字节数组，所以检查节点值和给定值是否相同的复杂度为 O(N)，而查找整个列表的复杂度则为 O(N^2)
返回给定节点的下一个节点O(1)
返回给定节点的前一个节点O(1)
获取给定节点所保存的值O(1)
从压缩列表中删除给定的节点平均 O(N)，最坏 O(N^2) (可能发生连锁更新)
删除压缩列表在给定索引上的连续多个节点平均 O(N)，最坏 O(N^2) (可能发生连锁更新)
返回压缩列表目前占用的内存字节数O(1)
返回压缩列表目前包含的节点数量节点数量小于 65535 时为 O(1)，大于 65535 时为 O(N)

本文重点

  • 压缩列表是 Redis 为节约内存自己设计的一种顺序型数据结构。
  • 压缩列表被用作列表键和哈希键的底层实现之一。
  • 压缩列表可以包含多个节点，每个节点可以保存一个字节数组或者整数值。
  • 添加新节点到压缩列表，或者从压缩列表中删除节点，可能会引发连锁更新操作，但这种操作出现的几率并不高。

参考

  • 《Redis 设计与实现》
  • 《Redis 开发与运维》
  • 《Redis 官方文档》
说明：本文内容基于 Redis 7.0 之前版本。在 Redis 7.0 版本中，压缩列表（ziplist）已被列表包（listpack）取代，后者解决了级联更新等潜在问题。