这篇文章我们来分析 Redis 数据结构的第三个：ziplist。
什么是 ziplist
什么是 ziplist？Redis 官方是这样定义的：
The ziplist is a specially encoded dually linked list that is designed to be very memory efficient. It stores both strings and integer values, where integers are encoded as actual integers instead of a series of characters. It allows push and pop operations on either side of the list in O(1) time.
翻译如下：
ziplist 是一个经过特殊编码的双向链表，它的设计目标就是为了提高存储效率。ziplist 可以用于存储字符串或整数，其中整数是按真正的二进制表示进行编码的，而不是编码成字符串序列。它能以 O(1) 的时间复杂度在表的两端提供 pus h和 pop 操作。
从上我们可以提炼如下几点信息：
- ziplist 是一个双向链表。事实上 ziplist 由一系列特殊编码的连续内存块组成的顺序型数据结构。
- 目的是为了提供存储效率。ziplist 是 Redis 为了节约内存而开发的。
- 用于存储字符串或者整数。当一个列表键或者哈希键值对包含少量的元素项，且每项要么是小整数型，要么就是长度比较短的字符串时，Redis 就会使用 ziplist 来做他们的底层实现。
ziplist 的结构
ziplist 的结构如下图：
| 结构 | 类型 | 长度 | 说明 |
|---|---|---|---|
| zlbytes | uint32_t | 4 字节 | ziplist 总字节数 |
| zltail | uint32_t | 4 字节 | ziplist 中最后一个 entry 元素起始距离的偏移量。通过这个偏移量，程序无须遍历整个列表就可以确定尾节点的地址 |
| zllen | uint16_t | 2 字节 | 记录 ziplist 包含的节点数量，也就是 ziplist 里面有多少个 entry。当有该值小于 UINT16_MAX(65535) 时，这个属性值就是压缩列表中包含的 entry 节点数；当这个值等于 UINT16_MAX 时，entry 节点的真实数量需要遍历整个 ziplist 才能计算出来 |
| entry | 不定 | ziplist 的节点，节点长度由节点保存的内容决定 | |
| zlend | uint8_t | 1 字节 | 表示 ziplist 结尾的一个特殊值，编码为单字节等于 255 |
压缩表中的每个 entry 都大体上包含以下 3 个部分：
- prevlen：上一个 entry 的长度。它主要是为了能够逆序遍历，有了上一个。
- encoding：记录了节点的 entry-data 属性所保存的数据类型和长度
- entry-data：负责保存节点的值。0-12 小的整数时没有没有该项
prevlen
prevlen 记录着上一个 entry 节点的长度，即名为 previous_entry_length 。它的属性长度可以是 1 个字节或者 5 个字节：
- 如果前一个节点的长度小于 254 字节，那么它的长度为 1 字节
- 如果前一个节点的长度大于等于 254 字节，那么它的长度为 5 字节，其中第一个字节设置为 254 （fe）作为标记，代表后边有一个大的值，其余 4 个字节表示上一个 entry 节点的长度。
正是因为 prevlen 记录着上一个 entry 节点的长度，所以我们可以通过指针运算来获取前一个节点的起始位置，然后依次类推就可以实现 ziplist 从表尾向表头遍历操作：在 ziplist 结构中 zltail 记录着最后一个 entry 节点起始地址，根据该地址减去该节点的 prevlen 值就可以得到倒数第二节点的起始地址，然后根据倒数第二节点的起始值减去该节点的 prevlen 值，就可以得到倒数第三个 entry 节点的起始位置，以此类推，就可以得到第一个 entry 节点的起始位置，实现 ziplist 表尾向表头遍历。
由于 prevlen 长度可以是 1 字节或者 5 字节，这样就会产生一个问题：连锁更新。如果已有的 ziplist 中有多个连续的 entry 节点（e1 ~ en）的长度都是介于 250 ~ 253 字节，现在在表头添加一个元素，该元素的长度大于 254，因为 e1 的 prevlen 长度仅为 1 字节，它是没有办法保存新节点的长度，所以程序需要对 ziplist 执行空间重分配操作，将 e1 的 prevlen 属性从原来的 1 字节扩展到 5 字节。当 e1 的 prevlen 属性长度扩展到 5 字节，那么其长度变为了 254 ~ 257，这时 e2 的 prevlen 属性就没法保存了，也需要执行空间重分配，将 prevlen 属性扩展到 5 字节，这时 e3 就没法保存了也需要执行，就这样 e1 引发 e2 扩展，e2 引发 e3 扩展 ... 依次到 en，就这样程序需要不断地对 ziplist 执行空间重分配，这个连续执行多次空间扩展的操作就称之为 ”连锁更新“。
可能有小伙伴认为这种连续分配存储空间的过程很消耗性能，其实不然，首先 ziplist 这种数据结构本身存储的数据就不是很多，而且还需要存在很多连续的元素其长度都介于 250 ~ 253 之间，这种概率本身就很小。
encoding
encoding 记录了节点的 entry-data 属性所保存数据的类型及长度：
- 1 字节(00)、2 字节(01)或者 5 字节长(10)， 值的最高位为 00 、 01 或者 10 的是字节数组编码： 这种编码表示节点的 entry-data 属性保存着字节数组， 数组的长度由编码除去最高两位之后的其他位记录
- 1 字节长， 值的最高位以 11 开头的是整数编码： 这种编码表示节点的 entry-data 属性保存着整数值， 整数值的类型和长度由编码除去最高两位之后的其他位记录
- 字节数组编码
| 字节数组编码 | 编码长度 | entry-data 属性保存的值 |
|---|---|---|
| 00bbbbbb | 1 字节 | 长度小于等于63 字节的字节数组 |
| 01bbbbbb xxxxxxxx | 2 字节 | 长度小于等于16 383 字节的字节数组 |
| 10______ aaaaaaaa bbbbbbbb cccccccc dddddddd | 5 字节 | 长度小于等于 4 294 967 295 的字节数组 |
- 整数编码
| 字节数组编码 | 编码长度 | entry-data 属性保存的值 |
|---|---|---|
| 11000000 | 1 字节 | int16_t 类型的整数 |
| 11010000 | 1 字节 | int32_t 类型的整数 |
| 11100000 | 1 字节 | int64_t 类型的整数 |
| 11110000 | 1 字节 | 24 位有符号整数 |
| 11111110 | 1 字节 | 8 位有符号整数 |
| 1111xxxx | 1 字节 | 使用这一编码的节点没有相应的 entry-data 属性，因为编码本身的xxxx 四个位已经保存了一个介于0 和12 之间的值，所以它无须 entry-data 属性 |
entry-data
entry-data 负责保存节点的值， 节点值可以是一个字节数组或者整数， 值的类型和长度由节点的 encoding 属性决定。
下面我们将演示如何将 "sike"，”redis“，10086、9这四个元素插入到 ziplist 中。
- 插入第一个节点 ”sike“
”sike“ 4 字节数组，那么 encoding 就是 00000100，prevlen 为空，zllen = 1，zltail = 0x000a (4 字节的 zlbytes、4 字节 的 zltail、2 字节的 zllen)，zlbytes = 0x0011。如下：
- 插入第二个节点 ”redis“
"redis" 5 字节数组，所以 encoding 为 00000101，prevlen 为 ”sike“ 节点的起始地址，所以为 10 即（0x0a）,zllen = 2 即 0x02，ztail 为当前节点的起始位置 16 即 0x10，zlbytes 为 ”sike“ 的长度 + ”redis“ 的长度为 24 ，即 0x18，所以如下：
- 插入第三个节点 10086
10086 为 int16_t 类型的证书，所以 encoding = 11000000，得到下图：
- 插入第四个节点 9
因为 9 < 13 ,所以没有 entry-data 这个属性，按照上面的规律计算得到下图：
参考
- 《Redis 设计与实现》
- Redis内部数据结构详解(4)——ziplist
- Redis Ziplist （一）
Java 面试宝典是大明哥全力打造的 Java 精品面试题，它是一份靠谱、强大、详细、经典的 Java 后端面试宝典。它不仅仅只是一道道面试题，而是一套完整的 Java 知识体系，一套你 Java 知识点的扫盲贴。
它的内容包括：
- 大厂真题：Java 面试宝典里面的题目都是最近几年的高频的大厂面试真题。
- 原创内容：Java 面试宝典内容全部都是大明哥原创，内容全面且通俗易懂，回答部分可以直接作为面试回答内容。
- 持续更新：一次购买，永久有效。大明哥会持续更新 3+ 年，累计更新 1000+，宝典会不断迭代更新，保证最新、最全面。
- 覆盖全面：本宝典累计更新 1000+，从 Java 入门到 Java 架构的高频面试题，实现 360° 全覆盖。
- 不止面试：内容包含面试题解析、内容详解、知识扩展，它不仅仅只是一份面试题，更是一套完整的 Java 知识体系。
- 宝典详情：https://www.yuque.com/chenssy/sike-java/xvlo920axlp7sf4k
- 宝典总览：https://www.yuque.com/chenssy/sike-java/yogsehzntzgp4ly1
- 宝典进展：https://www.yuque.com/chenssy/sike-java/en9ned7loo47z5aw
目前 Java 面试宝典累计更新 400+ 道，总字数 42w+。大明哥还在持续更新中，下图是大明哥在 2024-12 月份的更新情况：
想了解详情的小伙伴，扫描下面二维码加大明哥微信【daming091】咨询
同时，大明哥也整理一套目前市面最常见的热点面试题。微信搜[大明哥聊 Java]或扫描下方二维码关注大明哥的原创公众号[大明哥聊 Java] ，回复【面试题】 即可免费领取。
