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 头中,所有整数都以小端格式存储。