Redis zset的实现原理
- 时间:
- 浏览:0
- 来源:跟我学网络
概述
本文将通过源代码对 Redis 的 zset（sorted set）的实现原理进行分析。
Redis 源码
Redis 源码在：https://github.com/redis/redis。
README. md
src/server.c 源文件中定义的全局变量 redisCommandTable 用于定义所有 Redis 命令，指定命令的名称、实现命令的函数、命令需要的参数的个数、命令的其它属性。
src/server.c
接下来都将以 zadd 命令为例进行说明，zadd 命令的实现函数是 zaddCommand()，它的声明在 src/server.h 头文件中：
src/Makefile
如果对 Makefile 不了解，可以先阅读：http://timd.cn/makefile/
通过 Makefile 可以看出与 zset 相关的命令由 src/t_zset.c 源文件中定义的函数实现。
src/t_zset.c
createZsetObject() 和 createZsetZiplistObject() 的实现在 src/object.c 源文件中：
可见当使用 Skiplist 编码时，用到了 dict 和 Skiplist；当使用 Ziplist 编码时，用到了 Ziplist。后面将对 Skiplist 和 Ziplist 进行分析。
接下来看 zsetAdd() 的流程：
综上得出：
sorted set 的编码可以是 Skiplist，也可以是 Ziplist。并且只有当下面的两个条件都满足时，才会使用 Ziplist 编码：
- 元素数量不超过 zset_max_ziplist_entries 选项
- 所有元素的长度都不超过 zset_max_ziplist_value 选项
如果 sorted set 的编码是 Ziplist，并且新插入的元素导致上面的两个条件不再同时满足，那么 Redis 会将其编码转换成 SkipList。
Skiplist 源码解析
如果对跳表不了解，可以先阅读：http://timd.cn/data-structure/skiplist/
以下是 src/server.h 中定义的两个结构体：
其中：
zskiplistNode 是跳表的节点：
ele 表示跳表中的元素
score 表示元素的分值，跳表根据该值对节点进行排序
backward 指向前一个节点，头节点和第一节点的前一个节点是 NULL
数组 level：
level 的长度表示节点占据的高度，头节点的高度是 ZSKIPLIST_MAXLEVEL，其它节点的高度在 1 和 ZSKIPLIST_MAXLEVEL 之间（包含 1 和 ZSKIPLIST_MAXLEVEL）
分量 level[i] 包含 2 个域：
- forward 指向第 i 层上的下一个节点，最后一个节点在第 i 层上的下一个节点是 NULL
- span 表示到第 i 层的下一个节点之间的节点数量
zskiplist 是跳表：
- header、tail 分别指向跳表的头节点、尾节点
- length 表示跳表的长度
- level 表示跳表当前的最大层数
下面是一个Redis SkipList 的示例（未画 backward 指针）：
下面分析几个与跳表有关的操作：
1，创建跳表：
其中：
- zslCreateNode() 用于使用指定的层数创建跳表节点
- zslCreate() 用于创建新跳表
2，向跳表中插入新节点：
其中：
- zslRandomLevel() 的返回值是 1 和 ZSKIPLIST_MAXLEVEL 之间的一个整数（包含 1 和 ZSKIPLIST_MAXLEVEL）
- zslInsert() 用于向跳表中插入新节点
下面对 zslInsert() 的代码进行分析：
从最高层向下，逐层寻找每层的插入位置，并计算插入位置到头节点的距离
- update[] 数组中的第 i 个分量表示：在第 i 层，新节点将被插入到 update[i] 的后面
- rank[] 数组中的第 i 个分量表示：update[i] 距离头节点的长度
随机生成新节点占据的层数 level（1 到 ZSKIPLIST_MAXLEVEL 之间）
如果 level 大于跳表的当前高度，那么更新 update[]、rank[]，重置跳表的高度
创建新节点 x
从最底层向上，调整插入点和新节点的 forward 指针，以及 span 值，直到 level
递增未达到的层级的 span 值
调整 x 以及 x 的 forward 的 backward 指针；如果 x 是最后一个节点，将跳表的 tail 指向它
增加跳表长度
关于查找、删除等操作，以后有机会再补充。通过这两个函数已经可以对 Redis Skiplist 有完整的了解了。
Ziplist 介绍
Ziplist 的源码在 src/ziplist.c 源文件中。
1，Ziplist 的总体布局
<zlbytes> <zltail> <zllen> <entry> <entry> ... <entry> <zlend>
注意：除非另外规定，否则所有域都以小端（little endian）格式存储。
<uint32_t zlbytes> 是用于保存 Ziplist 占用的字节数的无符号整数（包含 zlbytes 域本身的四个字节）。存储该值的目的是为了能够在不遍历 Ziplist 的情况下，改变整个结构的大小。
<uint32_t zltail> 是 Ziplist 中最后一个 entry 的偏移。它允许在不遍历整个列表的情况下，在远端执行弹出操作。
<uint32_t zllen> 是entry 的数量。当 entry 的数量超过 2^16-2 时，该值被设置为 2^16-1，此时如果想要知道列表中有多少条目，需要遍历整个列表。
<uint32_t zlend> 是代表 Ziplist 的结尾的特殊 entry。它被编码为等于 255 的单字节。任何常规 entry 的首字节都不会被设置为 255。
2，Ziplist Entry
Ziplist 中的 entry 以包含 2 部分信息的元数据开头：
- 前一个 entry 的长度。存储它的目的是为了支持从后向前遍历列表
- entry 的编码。它表示 entry 的类型：整型或字符串，当 entry 是字符串时，编码也表示字符串的长度
因此，完整的 entry 的结构如下：
<prevlen> <encoding> <entry-data>
有时编码也代表 entry 本身。此时，可以省略 <entry-data> 部分：
<prevlen> <encoding>
前一个 entry 的长度 <prevlen> 的编码方式如下：
- 如果该长度小于 254 字节，它只使用一个字节（8 位无符号整数）表示该长度
- 当该长度大于或等于 254 时，它将占用 5 个字节。第一个字节被设置为 254（FE），这意味着后面是一个较大的值。其余 4 个字节保存前一个 entry 的长度
因此几乎所有 entry 的编码都如下：
<prevlen from 0 to 253> <encoding> <entry-data>
如果前一个 entry 的长度大于 253 字节，那么将使用如下的编码：
0xFE <4 bytes unsigned little endian prevlen> <encoding> <entry-data>
entry 的编码依赖于 entry 的内容：
- 如果 entry 是字符串，编码的第一个字节的前 2 位保存用于存储字符串长度的编码的类型，其后是真正的字符串长度
- 如果 entry 是整型，前 2 位都被设置为 1。后面的 2 位用于指定这个头之后将存储哪种整数
第一个字节足够用于确定 entry 的种类，不同类型和编码的概述如下：
|00pppppp| - 1 字节
长度小于或等于 63 字节（6 位）的字符串值。
"pppppp" 表示 6 位无符号长度
|01pppppp|qqqqqqqq| - 2 字节
长度小于或等于 16383 字节（14 位）的字符串值。
注意：以大端格式存储这个 14 位数值
|10000000|qqqqqqqq|rrrrrrrr|ssssssss|tttttttt| - 5 字节
长度大于或等于 16384 字节的字符串值。
只有第一个字节后面的 4 个字节表示该长度（最大可达 2^32-1）。第一个字节的低 6 位未被使用，且都被设置为 0。
注意：以大端格式存储这个 32位数值
|11000000| - 3 字节
编码为 int16_t（2 字节） 的整数
|11010000| - 5 字节
编码为 int32_t（4 字节） 的整数
|11100000| - 9 字节
编码为 int64_t（8 字节） 的整数
|11110000| - 4 字节
编码为 24 位（3 字节）有符号的整数
|11111110| - 2 字节
编码为 8 位（1 字节）有符号的整数
|1111xxxx| - xxxx 在 0001 和 1101 之间
|11111111| - 代表 Ziplist 结束的特殊 entry
在 Ziplist 头中，所有整数都以小端格式存储。