文章目录
- 1. 引言
- 2. redis 源码下载
- 3. zipList 数据结构
- 3.1 整体
- 3.2 entry 数据结构分析
- 3.3 连锁更新
- 4. 参考
1. 引言
前情提要：
《redis 从0到1完整学习 （一）：安装&初识 redis》
《redis 从0到1完整学习 （二）：redis 常用命令》
《redis 从0到1完整学习 （三）：redis 数据结构》
《redis 从0到1完整学习 （四）：字符串 SDS 数据结构》
《redis 从0到1完整学习 （五）：集合 IntSet 数据结构》
《redis 从0到1完整学习 （六）：Hash 表数据结构》
本文主要结合源码来介绍 ZipList 的数据结构
2. redis 源码下载
Redis 源码可以点击这里下载，方便查看其中定义的一些数据结构。
3. zipList 数据结构
3.1 整体
zipList 是为了提高存储效率而设计的一种特殊编码的双向链表，由一系列特殊编码的连续内存块组成。可以在任意一端进行 push 和 pop 操作，并且该操作的时间复杂度为 O(1)。它可以存储字符串或者整数，存储整数时是采用整数的二进制而不是字符串形式存储。
zipList 数据结构示意图：
| 名称 | 类型 | size | 用途 |
|---|---|---|---|
| zlbytes | uint32_t | 4 字节 | 记录整个 zipList 占用的字节总数，即图中 zlbytes 的起始 到 zlend 的末尾 |
| zltail | uint32_t | 4 字节 | 记录 zipList 尾节点距离起始地址有多少字节，即图中 zlbytes 起始 到 tail 起始的偏移量，通过这个偏移量，可以确定尾节点的地址 |
| zllen | uint16_t | 2 字节 | 记录了压缩列表包含的节点数量。 最大值为 UINT16_MAX （65534）。如果超过这个值，会记录为65535。 |
| entry | 不定 | 压缩列表包含的各个节点，节点的长度由节点保存的内容决定。 | |
| zlend | uint8_t | 1 字节 | 特殊值 0xFF （十进制 255 ），用于标记压缩列表的末端。 |
3.2 entry 数据结构分析
ziplist 中的每个 entry 都以包含两条信息的元数据作为前缀。首先，存储上一个 entry 的长度，以便能够从后向前遍历列表。其次，提供 entry encoding，表示 entry 类型，整数或字符串，如果是字符串，它还表示字符串有效负载的长度。因此，完整的 entry 存储如下：
- prevlen：前一个 entry 的长度，占1个或5个字节。
- 如果前一个 entry 的长度 < 254字节，则采用1个字节来保存这个长度值
- 如果前一个 entry 的长度 > 254字节，则采用5个字节来保存这个长度值，第一个字节为 0xfe，后四个字节才是真实长度数据
- encoding：编码属性，记录数据类型（字符串还是整数）以及长度，占用1个、2个或5个字节
- entry-data：负责保存 entry 数据，可以是字符串或整数
根据 redis 源码的注解来看，encoding 的编码如下：
（1）字符串编码
| encoding 格式 | 编码长度 | 字符串大小 |
|---|---|---|
| |00pppppp| | 1 bytes | <= 63 bytes |
| |01pppppp|qqqqqqqq| | 2 bytes | <= 16383 bytes |
| |10000000|qqqqqqqq|rrrrrrrr|ssssssss|tttttttt| | 5 bytes | <= 4294967295 bytes |
例如，下面保存 ab、bc 字符串示例：
* [13 00 00 00] [0e 00 00 00] [02 00] [00 02 61 62] [04 02 62 63] [ff]
* | | | | | |
* zlbytes zltail zllen "ab" "bc" end
*
a 的 ASCII 码是97，对应的16进制是61；
b 的 ASCII 码是98，对应的16进制是62；
c 的 ASCII 码是99，对应的16进制是63；
ab 的编码是 6162，长度是2字节，所以 encoding 是 00000010 即 16进制02，而前一个 entry 不存在，因而 prevlen 为 0，所以 ab 编码为 00026162；同样的 bc 前一个 entry 为 ab，字节一共为4，所以 bc 编码为 04026263。
（2）数字编码
| encoding 格式 | 编码长度 | 整数类型 |
|---|---|---|
| 11000000 | 1 | int16_t（2 bytes） |
| 11010000 | 1 | int32_t（4 bytes） |
| 11100000 | 1 | int64_t（8 bytes） |
| 11110000 | 1 | 24位有符整数(3 bytes) |
| 11111110 | 1 | 8位有符整数(1 bytes) |
| 1111xxxx | 1 | 在xxxx位置保存数值，范围从0001~1101，减1后结果为实际值 |
例如，下面是 redis 源码给出的保存 2、5 整数示例：
* [0f 00 00 00] [0c 00 00 00] [02 00] [00 f3] [02 f6] [ff]
* | | | | | |
* zlbytes zltail zllen "2" "5" end
*
2 的长度在 0001~1101，对应上面表格的最后一种，所以 encoding 为 11110011，即16进制的 f3 （这里的3，实际为2+1）；同样 5 encoding 为 11110110，即 f6
3.3 连锁更新
zipList 的每个 entry 都包含 prevlen 来记录上一个节点的大小，长度是1个或5个字节：
- 如果前一节点的长度 < 254字节，则采用1个字节来保存这个长度值
- 如果前一节点的长度 >= 254字节，则采用5个字节来保存这个长度值，第一个字节为0xfe，后四个字节才是真实长度数据
当一种边界场景下，插入了一个 entry，entry 的大小超过了 254 字节，导致后续大范围的 entry 的 prevlen 由1字节转为用5个字节来保存，触发了连锁更新，同时删除也可能触发连锁更新。
4. 参考
《redis 从0到1完整学习 （一）：安装&初识 redis》
《redis 从0到1完整学习 （二）：redis 常用命令》
《redis 从0到1完整学习 （三）：redis 数据结构》
《redis 从0到1完整学习 （四）：字符串 SDS 数据结构》
《redis 从0到1完整学习 （五）：集合 IntSet 数据结构》
《redis 从0到1完整学习 （六）：Hash 表数据结构》
