概述

本文将通过源代码对 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 编码:

如果 sorted set 的编码是 Ziplist,并且新插入的元素导致上面的两个条件不再同时满足,那么 Redis 会将其编码转换成 SkipList。


Skiplist 源码解析

如果对跳表不了解,可以先阅读:http://timd.cn/data-structure/skiplist/

以下是 src/server.h 中定义的两个结构体:

其中:

下面是一个Redis SkipList 的示例(未画 backward 指针):

redis-skiplist-example.jpg

下面分析几个与跳表有关的操作:

1,创建跳表:

其中:

2,向跳表中插入新节点:

其中:

下面对 zslInsert() 的代码进行分析:

关于查找、删除等操作,以后有机会再补充。通过这两个函数已经可以对 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 的结构如下:

<prevlen> <encoding> <entry-data>

有时编码也代表 entry 本身。此时,可以省略 <entry-data> 部分:

<prevlen> <encoding>

前一个 entry 的长度 <prevlen> 的编码方式如下:

因此几乎所有 entry 的编码都如下:

<prevlen from 0 to 253> <encoding> <entry-data>

如果前一个 entry 的长度大于 253 字节,那么将使用如下的编码:

0xFE <4 bytes unsigned little endian prevlen> <encoding> <entry-data>

entry 的编码依赖于 entry 的内容:

第一个字节足够用于确定 entry 的种类,不同类型和编码的概述如下:

在 Ziplist 头中,所有整数都以小端格式存储。