前情提要:
《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 的数据结构
Redis 源码可以点击这里下载,方便查看其中定义的一些数据结构。
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 ),用于标记压缩列表的末端。 |
ziplist 中的每个 entry 都以包含两条信息的元数据作为前缀。首先,存储上一个 entry 的长度,以便能够从后向前遍历列表。其次,提供 entry encoding,表示 entry 类型,整数或字符串,如果是字符串,它还表示字符串有效负载的长度。因此,完整的 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
zipList 的每个 entry 都包含 prevlen 来记录上一个节点的大小,长度是1个或5个字节:
当一种边界场景下,插入了一个 entry,entry 的大小超过了 254 字节,导致后续大范围的 entry 的 prevlen 由1字节转为用5个字节来保存,触发了连锁更新,同时删除也可能触发连锁更新。
《redis 从0到1完整学习 (一):安装&初识 redis》
《redis 从0到1完整学习 (二):redis 常用命令》
《redis 从0到1完整学习 (三):redis 数据结构》
《redis 从0到1完整学习 (四):字符串 SDS 数据结构》
《redis 从0到1完整学习 (五):集合 IntSet 数据结构》
《redis 从0到1完整学习 (六):Hash 表数据结构》