redis source note  
daoluan  
September 10, 2017  
2
Contents  
1
剖析心得  
5
5
5
5
1
1
1
.1 源码日志 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  
.2 从哪里开始读起 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  
.3 不在浮沙筑高台 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  
I redis 服务框架  
7
2
初探 redis  
9
2
2
2
.1 redis 在缓存系统所处的位置 . . . . . . . . . . . . . . . . . . . . . . . .  
9
.2 从主函数开始 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11  
.3 redis 如何运作 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11  
2
2
2
2
2
.3.1 详细的过程 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11  
.3.2 新连接的处理流程 . . . . . . . . . . . . . . . . . . . . . . . . . 15  
.3.3 请求的处理流程 . . . . . . . . . . . . . . . . . . . . . . . . . . . 17  
.3.4 执行命令 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19  
.3.5 在哪里回复客户端 . . . . . . . . . . . . . . . . . . . . . . . . . 20  
2
.4 redis 事件驱动模型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21  
2
2
.4.1 概述 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21  
.4.2 其他模型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21  
3
redis 事件驱动详解  
23  
3
.1 概述 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23  
3
3
.1.1 事件驱动数据结构 . . . . . . . . . . . . . . . . . . . . . . . . . 23  
.1.2 事件循环中心 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25  
3
.2 redis 事件驱动原理 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27  
3
3
3
3
3
.2.1 事件注册详解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27  
.2.2 准备监听工作 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28  
.2.3 为监听套接字注册事件 . . . . . . . . . . . . . . . . . . . . . . . 28  
.2.4 事件循环 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30  
.2.5 事件触发 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31  
3
4
CONTENTS  
3
3
.3 redis  memcache 的事件驱动比较 . . . . . . . . . . . . . . . . . . . . 32  
.4 总结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32  
II redis 基础数据结构  
35  
37  
41  
43  
47  
4
5
6
7
redis 数据结构 redisObject  
redis 数据结构 adlist  
redis 数据结构 sds  
redis 数据结构 dict  
7.1 redis 的键值对存储在哪里 . . . . . . . . . . . . . . . . . . . . . . . . . 47  
7.2 哈希表 dict . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48  
7.3 扩展哈希表 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50  
7.4 重置哈希表 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50  
7.5 低效率的哈希表添加替换 . . . . . . . . . . . . . . . . . . . . . . . . . 52  
7.6 哈希表的迭代 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54  
8
9
redis 数据结构 ziplist  
57  
.1 概述 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57  
.2 压缩双链表的具体实现 . . . . . . . . . . . . . . . . . . . . . . . . . . . 57  
8
8
redis 数据结构 skiplist  
61  
9
9
9
9
9
9
.1 概述 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61  
.2 跳表的数据结构 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62  
.3 跳表的插入 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63  
.4 跳表的删除 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66  
.5 redis 中的跳表 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67  
.6 redis 选用 skiplist 场景 . . . . . . . . . . . . . . . . . . . . . . . . . . . 68  
1
0 redis 数据结构 intset  
69  
0.1 intset 结构体 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69  
0.2 intset 搜索 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70  
0.3 intset 插入 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71  
1
1
1
III redis 内功心法  
75  
1
1 redis 数据淘汰机制  
77  
1
1
1
1.1 概述 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77  
1.2 LRU 数据淘汰机制 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78  
1.3 TTL 数据淘汰机制 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79  
CONTENTS  
5
11.4 总结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80  
1
1
2 RDB 持久化策略 87  
1
1
1
1
2.1 简介 redis 持久化 RDBAOF . . . . . . . . . . . . . . . . . . . . . . 87  
2.2 数据结构 rio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87  
2.3 RDB 持久化的运作机制 . . . . . . . . . . . . . . . . . . . . . . . . . . 90  
2.4 RDB 数据的组织方式 . . . . . . . . . . . . . . . . . . . . . . . . . . . 95  
3 AOF 持久化策略  
97  
1
1
1
1
1
1
3.1 数据结构 rio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97  
3.2 AOF 数据组织方式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97  
3.3 AOF 持久化运作机制 . . . . . . . . . . . . . . . . . . . . . . . . . . . 98  
3.4 细说更新缓存 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111  
3.5 AOF 恢复过程 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116  
3.6 AOF 的适用场景 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120  
1
1
1
4 主从复制  
121  
1
1
1
1
1
4.1 积压空间 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122  
4.2 主从数据同步机制概述 . . . . . . . . . . . . . . . . . . . . . . . . . . . 129  
4.3 全同步 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133  
4.4 部分同步 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141  
4.5 总结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152  
5 redis 事务机制  
153  
1
1
1
1
1
5.1 redis 事务简述 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153  
5.2 redis 命令队列 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153  
5.3 键值的监视 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157  
5.4 redis 事务的执行与取消 . . . . . . . . . . . . . . . . . . . . . . . . . . 162  
5.5 redis 事务番外篇 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165  
6 redis  lua 脚本  
167  
1
1
1
1
1
1
1
6.1 lua . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167  
6.2 redis 为什么添加 lua 支持 . . . . . . . . . . . . . . . . . . . . . . . . . 169  
6.3 lua 环境的初始化 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170  
6.4 redis lua 脚本的执行过程 . . . . . . . . . . . . . . . . . . . . . . . . . 172  
6.5 脏命令 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178  
6.6 lua 脚本的传播 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181  
6.7 总结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182  
1
7 redis 监视机制  
183  
7.1 redis 哨兵的服务框架 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183  
7.2 定时程序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186  
7.3 哨兵与 redis 服务器的互联 . . . . . . . . . . . . . . . . . . . . . . . . . 186  
1
1
1
6
CONTENTS  
17.4 HELLO 命令 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190  
1
8 redis 集群  
195  
1
1
8.1 前奏 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195  
8.2 也谈一致性哈希算法(consistent hashing . . . . . . . . . . . . . . . 196  
1
1
1
8.2.1 背景 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196  
8.2.2 一致性哈希算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . 197  
8.2.3 虚拟节点 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199  
1
1
1
1
8.3 一致性哈希解决的问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . 200  
8.4 怎么实现? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201  
8.5 twemproxy - redis 集群管理方案 . . . . . . . . . . . . . . . . . . . . . 201  
8.6 redis 官方版本支持的集群 . . . . . . . . . . . . . . . . . . . . . . . . . 202  
IV redis 操练  
203  
1
9 积分排行榜  
205  
1
1
1
1
9.1 需求 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205  
9.2 ZSET 命令简介 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205  
9.3 实现 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206  
9.4 性能 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206  
2
2
0 分布式锁  
207  
2
0.1 死锁的问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208  
1 消息中间件  
211  
21.1 以分布式的消息队列 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212  
V 其他  
219  
2
2 内存数据管理  
221  
22.1 共享对象 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221  
22.2 两种内存分配策略 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221  
22.3 memory aware 支持 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222  
22.4 zmalloc_get_private_dirty() 函数 . . . . . . . . . . . . . . . . . . . . 224  
22.5 总结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226  
22.6 redis 日志和断言 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227  
22.7 redis 断言 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228  
2
3 redis  memcache  
231  
3.1 单进程单线程与单进程多线程 . . . . . . . . . . . . . . . . . . . . . . . 231  
3.2 丰富与简单的数据结构 . . . . . . . . . . . . . . . . . . . . . . . . . . . 231  
3.3 其他 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231  
2
2
2
CONTENTS  
7
23.4 性能测试 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232  
8
CONTENTS  
Chapter 1  
剖析心得  
我的心得  
1
1
1
.1 源码日志  
.2 从哪里开始读起  
.3 不在浮沙筑高台  
9
10  
CHAPTER 1. 剖析心得  
Part I  
redis 服务框架  
1
1
Chapter 2  
初探 redis  
这一篇带大家大概浏览 redis。  
2
.1 redis 在缓存系统所处的位置  
通常,在系统中,我们会把数据交由数据库来存储,但传统的数据库增删查改的  
性能优先,且比较复杂。根据 80/20 法则,百分之八十的业务访问集中在百分之二十  
的数据上。是否可以有一个存在于物理内存中的数据中间层,来缓存一些常用的数据,  
解决传统数据库数据读写性能问题。常用的数据都存储在内存中,读写性能非常可观。  
1
3
14  
CHAPTER 2. 初探 REDIS  
这种思维在计算机中很常见,之前学习计算机系统的时候就有见过这张图:越  
往上的存储设备,存储的速度就会更快。诸如,redis, memcache 属于 nosql,即 not  
only sql,可见它们是为了弥补传统数据库的不足。  
包括 redis/memcache 这样的 key-value 内存存储系统,非常适合于读多写少的  
业务场景,而 redis 是一个基于多种数据结构的内存存储系统,让缓存系统更加好玩。  
2.2. 从主函数开始  
15  
2
.2 从主函数开始  
»
»»»»>  
2
.3 redis 如何运作  
在刚刚接触 redis 的时候,最想要知道的是一个’set name Jhon’ 命令到达 redis  
服务器的时候,它是如何返回’OK’ 的?里面命令处理的流程如何,具体细节怎么样?  
阅读别人的代码是很枯燥的,但带着好奇心阅读代码,是一件很兴奋的事情,接着翻  
到了 redis 源码的 main 函数。  
redis 在启动做了一些初始化逻辑,比如配置文件读取,数据中心初始化,网络通  
信模块初始化等,待所有初始化任务完毕后,便开始等待请求。  
当请求到来时,redis 进程会被唤醒,原理是 epoll. select, kqueue 等一些 I/O 多  
路复用的系统调用。接着读取来来自客户端的数据,解析命令,查找命令,并执行命令。  
执行命令’set name Jhon’ 的时候,redis 会在预先初始化好的哈希表里头,查找  
key=’name’ 对应的位置,并存入。  
最后,把回复的内容准备好回送给客户端,客户端于是收到了’OK’.  
2
.3.1 详细的过程  
带着命令是如何被处理的这个问题去读代码。刚开始的时候,会有一堆的变量和  
函数等着读者,但只要抓住主干就好了,下面就是 redis 的主干部分。  
int main ( int argc , char ** argv ) {  
.
. . . . .  
/
/ 初 始 化 服 务 器 配 置, 主 要 是 填 充 redisServer 结 构 体 中 的 各  
种 参 数  
initServerConfig () ;  
16  
CHAPTER 2. 初探 REDIS  
.
. . . . .  
/
/  始 化 服 务 器  
i n i t S e r v e r () ;  
.
. . . . .  
/
/  入 事 件 循 环  
aeMain ( server . e l ) ;  
}
分别来看看它们主要做了什么?  
initServerConfig  
initServerConfig 主要是填充 struct redisServer 这个结构体,redis 所有相关的配  
置都在里面。  
initServer  
void i n i t S e r v e r () {  
/
/  建 事 件 循 环 结 构 体  
server . e l = aeCreateEventLoop ( server . maxclients+  
REDIS_EVENTLOOP_FDSET_INCR) ;  
/
/  配 数 据 集 空 间  
server . db = zmalloc ( sizeof ( redisDb ) * server . dbnum) ;  
/
/
* Open the TCP l i s t e n i n g socket for the user commands .  
*/  
/ listenToPort ()  有 调 用 l i s t e n ()  
i f ( server . port != 0 &&  
listenToPort ( server . port , server . ipfd ,& server .  
ipfd_count ) == REDIS_ERR)  
e x i t (1) ;  
.
. . . . .  
/
/
/ 初 始 化 redis 数 据 集  
* Create the Redis databases , and i n i t i a l i z e other  
i n t e r n a l s t a t e . */  
2.3. REDIS 如何运作  
17  
for ( j = 0; j < server .REDIS_DEFAULT_DBNUM; j++) { // 初  
始 化 多 个 数 据 库  
/
/ 哈 希 表, 用 于 存 储 键 值 对  
server . db [ j ] . dict = dictCreate(&dbDictType ,NULL) ;  
/
/ 哈 希 表, 用 于 存 储 每 个 键 的 过 期 时 间  
server . db [ j ] . expires = dictCreate(&keyptrDictType ,  
NULL) ;  
server . db [ j ] . blocking_keys = dictCreate(&  
keylistDictType ,NULL) ;  
server . db [ j ] . ready_keys = dictCreate(&setDictType ,  
NULL) ;  
server . db [ j ] . watched_keys = dictCreate(&  
keylistDictType ,NULL) ;  
server . db [ j ] . id = j ;  
server . db [ j ] . avg_ttl = 0;  
}
.
. . . . .  
/
/
/
/  建 接 收 TCP  者 UNIX  套 接 字 的 事 件 处 理  
/ TCP  
* Create an event handler for accepting new connections  
in TCP and Unix  
*
domain sockets . */  
for ( j = 0; j < server . ipfd_count ; j++) {  
/
/ acceptTcpHandler () tcp  接 接 受 处 理 函 数  
i f ( aeCreateFileEvent ( server . el , server . ipfd [ j ] ,  
AE_READABLE,  
acceptTcpHandler ,NULL) == AE_ERR)  
{
redisPanic (  
Unrecoverable ␣ error ␣ creating ␣ server . ipfd  
␣ f i l e ␣ event . ” ) ;  
}
}
.
. . . . .  
}
在这里,创建了事件中心,是 redis 的网络模块,如果你有学过 linux 下的网络  
编程,那么知道这里一定和 select/epoll/kqueue 相关。  
接着,是初始化数据中心,我们平时使用 redis 设置的键值对,就是存储在里面。  
这里不急着深入它是怎么做到存储我们的键值对的,接着往下看好了,因为我们主要  
是想把大致的脉络弄清楚。  
18  
CHAPTER 2. 初探 REDIS  
在最后一段的代码中,redis listen fd 注册了回调函数 acceptTcpHandler,也  
就是说当新的客户端连接的时候,这个函数会被调用,详情接下来再展开。  
aeMain  
接着就开始等待请求的到来。  
void aeMain ( aeEventLoop *eventLoop ) {  
eventLoop>stop = 0;  
while ( ! eventLoop>stop ) {  
/
/ 进 入 事 件 循 环 可 能 会 进 入 睡 眠 状 态。 在 睡 眠 之 前, 执 行 预  
设 置 的 函 数 aeSetBeforeSleepProc () 。  
i f ( eventLoop>b e f o r e s l e e p != NULL)  
eventLoop>b e f o r e s l e e p ( eventLoop ) ;  
/
/ AE_ALL_EVENTS  示 处 理 所 有 的 事 件  
aeProcessEvents ( eventLoop , AE_ALL_EVENTS) ;  
}
}
前面的两个函数都属于是初始化的工作,到这里的时候,redis 正式进入等待接  
收请求的状态。具体的实现,和 select/epoll/kqueue 这些 IO 多路复用的系统调用相  
关,而这也是网络编程的基础部分了。继续跟踪调用链:  
int aeProcessEvents ( aeEventLoop *eventLoop , int f l a g s )  
{
.
. . . . .  
/
/  用 IO  路 复 用 函 数 阻 塞 监 听  
numevents = aeApiPoll ( eventLoop , tvp ) ;  
/
/  理 已 经 触 发 的 事 件  
for ( j = 0; j < numevents ; j++) {  
/
/  到 I /O  件 表 中 存 储 的 数 据  
aeFileEvent * fe = &eventLoop>events [ eventLoop>  
f i r e d [ j ] . fd ] ;  
int mask = eventLoop>f i r e d [ j ] . mask ;  
int fd = eventLoop>f i r e d [ j ] . fd ;  
2.3. REDIS 如何运作  
19  
int r f i r e d = 0;  
/
* note the fe>mask & mask & . . . code : maybe an  
already processed  
*
event removed an element that f i r e d and we  
s t i l l didn ’ t  
*
processed , so we check i f the event i s s t i l l  
v a l i d . */  
/
/  事 件  
i f ( fe>mask & mask & AE_READABLE) {  
r f i r e d = 1;  
fe>r f i l e P r o c ( eventLoop , fd , fe>clientData ,  
mask) ;  
}
/
/  事 件  
i f ( fe>mask & mask & AE_WRITABLE) {  
i f ( ! r f i r e d | | fe>wfileProc != fe>r f i l e P r o c  
)
fe>wfileProc ( eventLoop , fd , fe>clientData  
,
mask) ;  
}
processed++;  
}
}
/
/
/  理 定 时 事 件  
* Check time events */  
i f ( f l a g s & AE_TIME_EVENTS)  
processed += processTimeEvents ( eventLoop ) ;  
return processed ; /* return the number of processed f i l e /  
time events */  
}
可以看到,aeApiPoll 即是 IO 多路复用调用的地方,当有请求到来的时候,进程  
会觉醒以处理到来的请求。  
2
.3.2 新连接的处理流程  
initServer 的讲解中,redis 注册了回调函数 acceptTcpHandler,当有新的连  
接到来时,这个函数会被回调,上面的函数指针 rfileProc 实际上就是指向了 ac-  
ceptTcpHandler。下面是 acceptTcpHandler 的核心代码:  
20  
CHAPTER 2. 初探 REDIS  
/
/  于 TCP  收 请 求 的 处 理 函 数  
void acceptTcpHandler ( aeEventLoop * el , int fd , void * privdata  
,
int mask) {  
int cport , cfd ;  
char cip [REDIS_IP_STR_LEN ] ;  
REDIS_NOTUSED( e l ) ;  
REDIS_NOTUSED(mask) ;  
REDIS_NOTUSED( privdata ) ;  
/
/  收 客 户 端 请 求  
cfd = anetTcpAccept ( server . neterr , fd , cip , sizeof ( cip ) ,  
cport ) ;  
&
/
/  错  
i f ( cfd == AE_ERR) {  
redisLog (REDIS_WARNING, ” Accepting ␣ c l i e n t ␣ connection : ␣  
%
s ” , server . neterr ) ;  
return ;  
}
/
/  录  
redisLog (REDIS_VERBOSE, ” Accepted␣%s:%d” , cip , cport ) ;  
/
/  正 有 意 思 的 地 方  
acceptCommonHandler ( cfd , 0 ) ;  
}
anetTcpAccept  接 收 一 个 请 求 cfd  真 正 有 意 思 的 地 方 是  
acceptCommonHandler  而 acceptCommonHandler  核 心 的 调 用 是  
createClient  r e d i s 对 于 每 一 个 客 户 端 的 连 接, 都 会 对 应 一 个  
结 构 体 struct r e d i s C l i e n t  下 面 是 createClient  核 心 代  
码:  
r e d i s C l i e n t * createClient ( int fd ) {  
r e d i s C l i e n t *c = zmalloc ( sizeof ( r e d i s C l i e n t ) ) ;  
/
* passing 1 as fd i t i s p o s s i b l e to create a non  
connected c l i e n t .  
*
*
This i s u s e f u l since a l l the Redis commands needs to  
be executed  
in the context of a c l i e n t . When commands are executed  
2.3. REDIS 如何运作  
21  
in other  
contexts ( for instance a Lua s c r i p t ) we need a non  
*
connected c l i e n t . */  
i f ( fd != 1) {  
anetNonBlock (NULL, fd ) ;  
anetEnableTcpNoDelay (NULL, fd ) ;  
i f ( server . tcpkeepalive )  
anetKeepAlive (NULL, fd , server . tcpkeepalive ) ;  
/
/
/  接 收 到 的 套 接 字 注 册 监 听 事 件  
/ readQueryFromClient ()  该 为 处 理 客 户 端 请 求 的 函 数  
i f ( aeCreateFileEvent ( server . el , fd ,AE_READABLE,  
readQueryFromClient , c ) == AE_ERR)  
{
c l o s e ( fd ) ;  
z f r e e ( c ) ;  
return NULL;  
}
}
.
. . . . .  
return c ;  
}
可以看到,createClient 在事件中心为与客户端连接的套接字注册了 read-  
QueryFromClient 回调函数,而这也就是说当客户端有请求数据过来的时候,ac-  
ceptTcpHandler 会被调用。于是,我们找到了’set name Jhon’ 开始处理的地方。  
2
.3.3 请求的处理流程  
readQueryFromClient 则是获取来自客户端的数据,接下来它会调用 processIn-  
putBuffer 解析命令和执行命令,对于命令的执行,调用的是函数 processCommand。  
下面是 processCommand 核心代码:  
int processCommand ( r e d i s C l i e n t *c ) {  
.
/
/
. . . . .  
/  找 命 令, r e d i s C l i e n t . cmd  此 时 赋 值  
* Now lookup the command and check ASAP about t r i v i a l  
error conditions  
*
such as wrong arity , bad command name and so f o r t h . */  
c>cmd = c>lastcmd = lookupCommand( c>argv[0]> ptr ) ;  
22  
CHAPTER 2. 初探 REDIS  
/
/  有 找 到 命 令  
i f ( ! c>cmd) {  
flagTransaction ( c ) ;  
addReplyErrorFormat ( c , ”unknown␣command␣’%s ’ ” ,  
(
char*) c>argv[0]> ptr ) ;  
return REDIS_OK;  
/
/  数 个 数 不 符 合  
}
else i f (( c>cmd>a r i t y > 0 && c>cmd>a r i t y != c>argc  
)
| |  
(
c>argc < c>cmd>a r i t y ) ) {  
flagTransaction ( c ) ;  
addReplyErrorFormat ( c , ”wrong␣number␣ of ␣arguments␣ fo r ␣  
%s ’ ␣command” ,  
c>cmd>name) ;  
return REDIS_OK;  
}
.
. . . .  
/
/
i f ( c>f l a g s & REDIS_MULTI &&  
c>cmd>proc != execCommand && c>cmd>proc !=  
discardCommand &&  
/  入 命 令 队 列 的 情 况  
* Exec the command */  
c>cmd>proc != multiCommand && c>cmd>proc !=  
watchCommand)  
{
/
/  令 入 队  
queueMultiCommand( c ) ;  
addReply ( c , shared . queued ) ;  
/
/
/ 真 正 执 行 命 令。  
/ 注 意, 如 果 是 设 置 了 多 命 令 模 式, 那 么 不 是 直 接 执 行 命 令, 而  
是 让 命 令 入 队  
}
else {  
c a l l ( c ,REDIS_CALL_FULL) ;  
i f ( listLength ( server . ready_keys ) )  
handleClientsBlockedOnLists () ;  
}
return REDIS_OK;  
}
如上可以看到,redis 首先根据客户端给出的命令字在命令表中查找对应的 c-  
cmd, struct redisCommand.  
>
2.3. REDIS 如何运作  
23  
c>cmd = c>lastcmd = lookupCommand( c>argv[0]> ptr ) ;  
redis 在初始化的时候准备了一个大数组,初始化了所有的命令,即初始化多个  
struct redisCommand,在 struct redisCommand 中就有该命令对应的回调函数指针。  
找到命令结构体后,则开始执行命令,核心调用是 call().  
2
.3.4 执行命令  
call() 做的事情有很多,但这里只关注这一句话:call() 调用了命令的回调函数。  
/
/
/ c a l l ()  数 是 执 行 命 令 的 核 心 函 数, 真 正 执 行 命 令 的 地 方  
* Call () i s the core of Redis execution of a command */  
void c a l l ( r e d i s C l i e n t *c , int f l a g s ) {  
.
. . . . .  
/
/  行 命 令 对 应 的 处 理 函 数  
c>cmd>proc ( c ) ;  
.
. . . . .  
}
对于’set name Jhon’ 命令,对应的回调函数是 setCommand() 函数。setCommand  
set 命令的参数做了检测,因为还提供设置一个键值对的过期时间等功能,这里只  
关注最简单的情况。  
24  
CHAPTER 2. 初探 REDIS  
void setCommand( r e d i s C l i e n t *c ) {  
.
. . . . .  
setGenericCommand ( c , flags , c>argv [ 1 ] , c>argv [ 2 ] , expire ,  
unit ,NULL,NULL) ;  
}
void setGenericCommand ( r e d i s C l i e n t *c , int flags , robj *key ,  
robj *val , robj * expire , int unit , robj *ok_reply , robj *  
abort_reply ) {  
.
. . . . .  
setKey ( c>db , key , val ) ;  
. . . . .  
addReply ( c , ok_reply ? ok_reply : shared . ok ) ;  
.
}
void setKey ( redisDb *db , robj *key , robj * val ) {  
i f ( lookupKeyWrite (db , key ) == NULL) {  
dbAdd(db , key , val ) ;  
}
else {  
dbOverwrite (db , key , val ) ;  
}
.
. . . . .  
}
setKey() 首先查看 key 是否存在于数据集中,如果存在则覆盖写;如果不存在则  
添加到数据集中。这里关注 key 不存在的情况:  
void dbAdd( redisDb *db , robj *key , robj * val ) {  
sds copy = sdsdup ( key>ptr ) ;  
int r e t v a l = dictAdd (db>dict , copy , val ) ;  
redisAssertWithInfo (NULL, key , r e t v a l == REDIS_OK) ;  
}
dictAdd() 就是把 key 存到字典中,实际上即是存到一个哈希表。  
2
.3.5 在哪里回复客户端  
最后,回到 setGenericCommand(), 会调用 addReply()addReply() 会为与客户  
端连接的套接字注册可写事件,把’ok’ 添加到客户端的回复缓存中。待再一次回到事  
件循环的时候,如果这个套接字可写,相应的回调函数就可以被回调了。回复缓存中  
2.4. REDIS 事件驱动模型  
25  
的数据会被发送到客户端。  
由此’set name Jhon’ 命令执行完毕。  
在把这个流程捋顺的过程,我省去了很多的细节,只关注场景最简单情况最单一  
的时候,其他的代码都没有去看。这对我们快速了解一个系统的原理是很关键的。同  
样,在面对其他系统代码的时候,也可以带着这三个最简单的问题去阅读:它是谁,  
它从哪里来,又到哪里去。  
2
.4 redis 事件驱动模型  
2
.4.1 概述  
»
»»»»>  
2
.4.2 其他模型  
»
»»»»>  
26  
CHAPTER 2. 初探 REDIS  
Chapter 3  
redis 事件驱动详解  
3
.1 概述  
redis 内部有一个小型的事件驱动,它和 libevent 网络库的事件驱动一样,都是  
依托 I/O 多路复用技术支撑起来的。  
利用 I/O 多路复用技术,监听感兴趣的文件 I/O 事件,例如读事件,写事件等,  
同时也要维护一个以文件描述符为主键,数据为某个预设函数的事件表,这里其实就  
是一个数组或者链表。当事件触发时,比如某个文件描述符可读,系统会返回文件描  
述符值,用这个值在事件表中找到相应的数据项,从而实现回调。同样的,定时事件  
也是可以实现的,因为系统提供的 I/O 多路复用技术中的函数允许我们设定时间值。  
上面一段话比较综合,可能需要一些 linux 系统编程和网络编程的基础,但你会  
看到多数事件驱动程序都是这么实现的。  
3
.1.1 事件驱动数据结构  
redis 事件驱动内部有四个主要的数据结构,分别是:事件循环结构体,文件事件  
结构体,时间事件结构体和触发事件结构体。  
/
/
/  件 事 件 结 构 体  
* File event structure */  
typedef struct aeFileEvent {  
int mask ; /* one of AE_(READABLE|WRITABLE) */  
/
/  调 函 数 指 针  
aeFileProc * r f i l e P r o c ;  
aeFileProc * wfileProc ;  
/
/ clientData 参 数 一 般 是 指 向 r e d i s C l i e n t  指 针  
2
7
28  
CHAPTER 3. REDIS 事件驱动详解  
void * clientData ;  
aeFileEvent ;  
}
/
/
/  间 事 件 结 构 体  
* Time event structure */  
typedef struct aeTimeEvent {  
long long id ; /* time event i d e n t i f i e r . */  
long when_sec ; /* seconds */  
long when_ms ; /* milliseconds */  
/
/  时 回 调 函 数 指 针  
aeTimeProc *timeProc ;  
/
/ 定 时 事 件 清 理 函 数, 当 删 除 定 时 事 件 的 时 候 会 被 调 用  
aeEventFinalizerProc * f i n a l i z e r P r o c ;  
/
/ clientData 参 数 一 般 是 指 向 r e d i s C l i e n t  指 针  
void * clientData ;  
/
/  时 事 件 表 采 用 链 表 来 维 护  
struct aeTimeEvent *next ;  
}
aeTimeEvent ;  
/
/
/  发 事 件  
* A f i r e d event */  
typedef struct aeFiredEvent {  
int fd ;  
int mask ;  
}
aeFiredEvent ;  
/
/
/  件 循 环 结 构 体  
* State of an event based program */  
typedef struct aeEventLoop {  
int maxfd ;  
r e g i s t e r e d */  
int s e t s i z e ; /* max number of f i l e d e s c r i p t o r s tracked */  
/* h i g h e s t f i l e d es cr ip t o r currently  
/
/ 记 录 最 大 的 定 时 事 件 id + 1  
long long timeEventNextId ;  
/
/  于 系 统 时 间 的 矫 正  
time_t lastTime ;  
/* Used to d etect system clock skew  
3.1. 概述  
29  
*
/
/
/ I /O  件 表  
aeFileEvent * events ; /* Registered events */  
/
/  触 发 的 事 件  
aeFiredEvent * f i r e d ; /* Fired events */  
/
/  时 事 件 表  
aeTimeEvent *timeEventHead ;  
/
/  件 循 环 结 束 标 识  
int stop ;  
/
/  于 不 同 的 I /O  路 复 用 技 术, 有 不 同 的 数 据, 详 见 各 自 实  
void * apidata ; /* This i s used for p o l l i n g API s p e c i f i c  
data */  
/
/  的 循 环 前 需 要 执 行 的 操 作  
aeBeforeSleepProc * b e f o r e s l e e p ;  
aeEventLoop ;  
}
上面的数据结构能给我们很好的提示:事件循环结构体维护 I/O 事件表,定时事  
件表和触发事件表。  
3
.1.2 事件循环中心  
redis 的主函数中调用 initServer() 函数从而初始化事件循环中心(EventLoop),  
它的主要工作是在 aeCreateEventLoop() 中完成的。  
aeEventLoop *aeCreateEventLoop ( int s e t s i z e ) {  
aeEventLoop *eventLoop ;  
int i ;  
/
/  配 空 间  
i f (( eventLoop = zmalloc ( sizeof (* eventLoop ) ) ) == NULL)  
goto err ;  
/
/  配 文 件 事 件 结 构 体 空 间  
eventLoop>events = zmalloc ( sizeof ( aeFileEvent ) * s e t s i z e ) ;  
/
/  配 已 触 发 事 件 结 构 体 空 间  
30  
CHAPTER 3. REDIS 事件驱动详解  
eventLoop>f i r e d = zmalloc ( sizeof ( aeFiredEvent ) * s e t s i z e ) ;  
i f ( eventLoop>events == NULL | | eventLoop>f i r e d == NULL  
)
goto err ;  
eventLoop>s e t s i z e = s e t s i z e ;  
eventLoop>lastTime = time (NULL) ;  
/
/  间 事 件 链 表 头  
eventLoop>timeEventHead = NULL;  
/
/  续 提 到  
eventLoop>timeEventNextId = 0;  
eventLoop>stop = 0;  
eventLoop>maxfd = 1;  
/
/  入 事 件 循 环 前 需 要 执 行 的 操 作, 此 项 会 在 redis main () 函  
数 中 设 置  
eventLoop>b e f o r e s l e e p = NULL;  
/
/  这 里, aeApiCreate ()  数 对 于 每 个 IO  路 复 用 模 型 的 实  
现 都 有 不 同, 具 体 参 见 源 代 码, 因 为 每 种 IO  路 复 用 模 型 的  
初 始 化 都 不 同  
i f ( aeApiCreate ( eventLoop ) == 1) goto err ;  
/
* Events with mask == AE_NONE are not set . So l e t ’ s  
i n i t i a l i z e the  
*
vector with i t . */  
/
/  始 化 事 件 类 型 掩 码 为 无 事 件 状 态  
for ( i = 0; i < s e t s i z e ; i++)  
eventLoop>events [ i ] . mask = AE_NONE;  
return eventLoop ;  
err :  
i f ( eventLoop ) {  
z f r e e ( eventLoop>events ) ;  
z f r e e ( eventLoop>f i r e d ) ;  
z f r e e ( eventLoop ) ;  
}
return NULL;  
}
有上面初始化工作只是完成了一个空空的事件中心而已。要想驱动事件循环,还  
需要下面的工作。  
3.2. REDIS 事件驱动原理  
31  
3
.2 redis 事件驱动原理  
3
.2.1 事件注册详解  
文件 I/O 事件注册主要操作在 aeCreateFileEvent() 中完成。aeCreateFileEvent()  
会根据文件描述符的数值大小在事件循环结构体的 I/O 事件表中取一个数据空间,利  
用系统提供的 I/O 多路复用技术监听感兴趣的 I/O 事件,并设置回调函数。  
int aeCreateFileEvent ( aeEventLoop *eventLoop , int fd , int  
mask ,  
aeFileProc *proc , void * clientData )  
{
i f ( fd >= eventLoop>s e t s i z e ) {  
errno = ERANGE;  
return AE_ERR;  
}
/
/  I /O  件 表 中 选 择 一 个 空 间  
aeFileEvent * f e = &eventLoop>events [ fd ] ;  
/
/ aeApiAddEvent ()  在 此 函 数 中 调 用, 对 于 不 同 IO  路 复 用  
实 现, 会 有 所 不 同  
i f ( aeApiAddEvent ( eventLoop , fd , mask) == 1)  
return AE_ERR;  
fe>mask |= mask ;  
/
/  置 回 调 函 数  
i f (mask & AE_READABLE) fe>r f i l e P r o c = proc ;  
i f (mask & AE_WRITABLE) fe>wfileProc = proc ;  
fe>clientData = clientData ;  
i f ( fd > eventLoop>maxfd )  
eventLoop>maxfd = fd ;  
return AE_OK;  
}
对于不同版本的 I/O 多路复用,比如 epollselectkqueue 等,redis 有各自的  
版本,但接口统一,譬如 aeApiAddEvent()。  
32  
CHAPTER 3. REDIS 事件驱动详解  
3
.2.2 准备监听工作  
initServer() 中调用了 aeCreateEventLoop() 完成了事件中心的初始化,init-  
Server() 还做了监听的准备。  
/
/
* Open the TCP l i s t e n i n g socket for the user commands . */  
/ listenToPort ()  有 调 用 l i s t e n ()  
i f ( server . port != 0 &&  
listenToPort ( server . port , server . ipfd ,& server . ipfd_count )  
=
= REDIS_ERR)  
e x i t (1) ;  
/
/
/ UNIX  套 接 字  
* Open the l i s t e n i n g Unix domain socket . */  
i f ( server . unixsocket != NULL) {  
unlink ( server . unixsocket ) ; /* don ’ t care i f t h i s f a i l s */  
server . sofd = anetUnixServer ( server . neterr , server .  
unixsocket , server . unixsocketperm ) ;  
i f ( server . sofd == ANET_ERR) {  
redisLog (REDIS_WARNING, ”Opening␣ socket : ␣%s ” , server .  
neterr ) ;  
e x i t (1) ;  
}
}
从上面可以看出,redis 提供了 TCP UNIX 域套接字两种工作方式。以 TCP  
工作方式为例,listenPort() 创建绑定了套接字并启动了监听。  
3
.2.3 为监听套接字注册事件  
在进入事件循环前还需要做一些准备工作。紧接着,initServer() 为所有的监听套  
接字注册了读事件,响应函数为 acceptTcpHandler() 或者 acceptUnixHandler()。  
3.2. REDIS 事件驱动原理  
33  
/
/
/
/  建 接 收 TCP  者 UNIX  套 接 字 的 事 件 处 理  
/ TCP  
* Create an event handler for accepting new connections  
in TCP and Unix  
*
domain sockets . */  
for ( j = 0; j < server . ipfd_count ; j++) {  
/
/ acceptTcpHandler () tcp  接 接 受 处 理 函 数  
i f ( aeCreateFileEvent ( server . el , server . ipfd [ j ] ,  
AE_READABLE,  
acceptTcpHandler ,NULL) == AE_ERR)  
{
redisPanic (  
Unrecoverable ␣ error ␣ creating ␣ server . ipfd  
␣ f i l e ␣ event . ” ) ;  
}
}
/
/ UNIX  套 接 字  
i f ( server . sofd > 0 && aeCreateFileEvent ( server . el , server  
.
sofd ,AE_READABLE,  
acceptUnixHandler ,NULL) == AE_ERR) redisPanic ( ”  
Unrecoverable ␣ error ␣ creating ␣ server . sofd ␣ f i l e ␣  
event . ” ) ;  
来 看 看 acceptTcpHandler ()  了 什 么:  
/
/  于 TCP  收 请 求 的 处 理 函 数  
void acceptTcpHandler ( aeEventLoop * el , int fd , void * privdata  
,
int mask) {  
int cport , cfd ;  
char cip [REDIS_IP_STR_LEN ] ;  
REDIS_NOTUSED( e l ) ;  
REDIS_NOTUSED(mask) ;  
REDIS_NOTUSED( privdata ) ;  
/
/  收 客 户 端 请 求  
cfd = anetTcpAccept ( server . neterr , fd , cip , sizeof ( cip ) ,  
cport ) ;  
&
/
/  错  
i f ( cfd == AE_ERR) {  
34  
CHAPTER 3. REDIS 事件驱动详解  
redisLog (REDIS_WARNING, ” Accepting ␣ c l i e n t ␣ connection : ␣  
%
s ” , server . neterr ) ;  
return ;  
}
/
/  录  
redisLog (REDIS_VERBOSE, ” Accepted␣%s:%d” , cip , cport ) ;  
/
/  正 有 意 思 的 地 方  
acceptCommonHandler ( cfd , 0 ) ;  
}
接收套接字与客户端建立连接后,调用 acceptCommonHandler()acceptCom-  
monHandler() 主要工作就是:  
1
. 建立并保存服务端与客户端的连接信息,这些信息保存在一个 struct re-  
disClient 结构体中;2. 为与客户端连接的套接字注册读事件,相应的回调函数为  
readQueryFromClient()readQueryFromClient() 作用是从套接字读取数据,执行相  
应操作并回复客户端。  
3
.2.4 事件循环  
以上做好了准备工作,可以进入事件循环。跳出 initServer() 回到 main() 中,  
main() 会调用 aeMain()。进入事件循环发生在 aeProcessEvents() 中:  
1
. 根据定时事件表计算需要等待的最短时间;2. 调用 redis api aeApiPoll() 进  
入监听轮询,如果没有事件发生就会进入睡眠状态,其实就是 I/O 多路复用 select()  
epoll() 等的调用;3. 有事件发生会被唤醒,处理已触发的 I/O 事件和定时事件。  
void aeMain ( aeEventLoop *eventLoop ) {  
eventLoop>stop = 0;  
while ( ! eventLoop>stop ) {  
/
/ 进 入 事 件 循 环 可 能 会 进 入 睡 眠 状 态。 在 睡 眠 之 前, 执 行 预  
设 置 的 函 数 aeSetBeforeSleepProc () 。  
i f ( eventLoop>b e f o r e s l e e p != NULL)  
eventLoop>b e f o r e s l e e p ( eventLoop ) ;  
/
/ AE_ALL_EVENTS  示 处 理 所 有 的 事 件  
aeProcessEvents ( eventLoop , AE_ALL_EVENTS) ;  
}
}
»
»» 此处考虑要不要加代码了  
3.2. REDIS 事件驱动原理  
35  
3
.2.5 事件触发  
这里以 select 版本的 redis api 实现作为讲解,aeApiPoll() 调用了 select() 进入  
了监听轮询。aeApiPoll() tvp 参数是最小等待时间,它会被预先计算出来,它主要  
完成:  
1
. 拷贝读写的 fdsetselect() 的调用会破坏传入的 fdset,实际上有两份 fdset,  
一份作为备份,另一份用作调用。每次调用 select() 之前都从备份中直接拷贝一份;  
2
. 调用 select()3. 被唤醒后,检查 fdset 中的每一个文件描述符,并将可读或者可  
写的描述符记录到触发表当中。  
接下来的操作便是执行相应的回调函数,代码在上一段中已经贴出:先处理 I/O  
事件,再处理定时事件。  
static int aeApiPoll ( aeEventLoop *eventLoop , struct timeval *  
tvp ) {  
aeApiState * state = eventLoop>apidata ;  
int retval , j , numevents = 0;  
/
*
真 有 意 思, 在 aeApiState  构 中:  
typedef s t r u c t aeApiState {  
fd_set rfds , wfds ;  
fd_set _rfds , _wfds ;  
aeApiState ;  
}
在 调 用 s e l e c t ()  时 候 传 入 的 是 _rfds  _wfds  所 有 监 听 的  
数 据 在 r fds  wfds 中。  
在 下 次 需 要 调 用 s e l e c ()  时 候, 会 将 rf ds  wfds  的 数 据  
拷 贝 进 _rfds  _wfds 中。 */  
memcpy(&state >_rfds ,& state >rfds , sizeof ( fd_set ) ) ;  
memcpy(&state >_wfds,& state >wfds , sizeof ( fd_set ) ) ;  
r e t v a l = s e l e c t ( eventLoop>maxfd+1,  
&
state >_rfds ,& state >_wfds ,NULL, tvp ) ;  
i f ( r e t v a l > 0) {  
/  询  
/
for ( j = 0; j <= eventLoop>maxfd ; j++) {  
int mask = 0;  
aeFileEvent * fe = &eventLoop>events [ j ] ;  
i f ( fe>mask == AE_NONE) continue ;  
i f ( fe>mask & AE_READABLE && FD_ISSET( j ,& state >  
_
rfds ) )  
mask |= AE_READABLE;  
36  
CHAPTER 3. REDIS 事件驱动详解  
i f ( fe>mask & AE_WRITABLE && FD_ISSET( j ,& state >  
_
wfds ) )  
mask |= AE_WRITABLE;  
/
/  加 到 触 发 事 件 表 中  
eventLoop>f i r e d [ numevents ] . fd = j ;  
eventLoop>f i r e d [ numevents ] . mask = mask ;  
numevents++;  
}
}
return numevents ;  
}
3
.3 redis  memcache 的事件驱动比较  
»
»»»»>  
3
.4 总结  
redis 的事件驱动总结如下:  
1
2
3
. 初始化事件循环结构体  
. 注册监听套接字的读事件  
. 注册定时事件  
3.4. 总结  
37  
4
5
6
. 进入事件循环  
. 如果监听套接字变为可读,会接收客户端请求,并为对应的套接字注册读事件  
. 如果与客户端连接的套接字变为可读,执行相应的操作  
38  
CHAPTER 3. REDIS 事件驱动详解  
Part II  
redis 基础数据结构  
3
9
Chapter 4  
redis 数据结构 redisObject  
redis key-value 存储系统,其中 key 类型一般为字符串,而 value 类型则为  
redis 对象(redis object)。redis 对象可以绑定各种类型的数据,譬如 stringlist set。  
typedef struct redisObject {  
/
/  刚 好 32 b i t s  
/
/ 对 象 的 类 型, 字 符 串/ 表/ 合/ 希 表  
unsigned type : 4 ;  
/
/  使 用 的 两 个 位  
unsigned notused : 2 ;  
/* Not used */  
/
/
/ 编 码 的 方 式, redis 为 了 节 省 空 间, 提 供 多 种 方 式 来 保 存 一 个  
数 据  
/  如: “ 123456789  会 被 存 储 为 整 数 123456789  
unsigned encoding : 4 ;  
/
/ 当 内 存 紧 张, 淘 汰 数 据 的 时 候 用 到  
/* lru time ( r e l a t i v e to server .  
unsigned lru : 2 2 ;  
l r u c l o c k ) */  
/
/  用 计 数  
int refcount ;  
/
/  据 指 针  
void * ptr ;  
4
1
42  
CHAPTER 4. REDIS 数据结构 REDISOBJECT  
}
robj ;  
redis 中定义了 struct redisObject,它是一个简单优秀的数据结构,因为在 redis-  
Object 中数据属性和数据分开来了,其中,数据属性包括数据类型,存储编码方式,  
淘汰时钟,引用计数。下面一一展开:  
数据类型,标记了 redis 对象绑定的是什么类型的数据,有下面几种可能的值;  
/
* Object types */  
define REDIS_STRING 0  
define REDIS_LIST 1  
define REDIS_SET 2  
define REDIS_ZSET 3  
define REDIS_HASH 4  
#
#
#
#
#
存储编码方式 ,一 个数据 ,可 以以多种方式存储。譬如 ,数 据类型为 REDIS_SET 的  
数据编码方式可能为 REDIS_ENCODING_HT ,也 可能为 REDIS_ENCODING_INTSET。  
/
*
*
* Objects encoding . Some kind of o b j e c t s l i k e Strings and  
Hashes can be  
i n t e r n a l l y represented in multiple ways . The ’ encoding ’  
f i e l d of the o b j e c t  
i s se t to one of t h i s f i e l d s for t h i s o b j e c t . */  
#
define REDIS_ENCODING_RAW 0  
/* Raw representation */  
/* Encoded as in teger */  
/* Encoded as hash t a b l e */  
#
define REDIS_ENCODING_INT 1  
define REDIS_ENCODING_HT 2  
#
#
define REDIS_ENCODING_ZIPMAP 3 /* Encoded as zipmap */  
define REDIS_ENCODING_LINKEDLIST 4 /* Encoded as regular  
linked l i s t */  
define REDIS_ENCODING_ZIPLIST 5 /* Encoded as z i p l i s t */  
define REDIS_ENCODING_INTSET 6 /* Encoded as i n t s e t */  
define REDIS_ENCODING_SKIPLIST 7 /* Encoded as s k i p l i s t */  
#
#
#
#
淘汰时钟,redis 对数据集占用内存的大小有「实时」的计算,当超出限额时,会  
淘汰超时的数据。  
引用计数,一个 redis 对象可能被多个指针引用。当需要增加或者减少引用的时  
候,必须调用相应的函数,程序员必须遵守这一准则。  
/
/ 增 加 redis 对 象 引 用  
void incrRefCount ( robj *o ) {  
4
3
o>refcount++;  
}
/
/ 减 少 redis 对 象 引 用。 特 别 的, 引 用 为 零 的 时 候 会 销 毁 对 象  
void decrRefCount ( robj *o ) {  
i f (o>refcount <= 0) redisPanic ( ” decrRefCount␣ against ␣  
refcount ␣<=␣0” ) ;  
/
/ 如 果 取 消 的 是 最 后 一 个 引 用, 则 释 放 资 源  
i f (o>refcount == 1) {  
/
/ 不 同 数 据 类 型, 销 毁 操 作 不 同  
switch (o>type ) {  
case REDIS_STRING: freeStringObject ( o ) ; break ;  
case REDIS_LIST: freeListObject ( o ) ; break ;  
case REDIS_SET: freeSetObject ( o ) ; break ;  
case REDIS_ZSET: freeZsetObject ( o ) ; break ;  
case REDIS_HASH: freeHashObject ( o ) ; break ;  
default : redisPanic ( ”Unknown␣ object ␣type ” ) ; break ;  
}
z f r e e ( o ) ;  
else {  
o>refcount −−;  
}
}
}
得益于 redis 是单进程单线程工作的,所以增加/减少引用的操作不必保证原子  
性,这在 memcache 中是做不到的。  
struct redisObject 把最后一个指针留给了真正的数据。  
44  
CHAPTER 4. REDIS 数据结构 REDISOBJECT  
Chapter 5  
redis 数据结构 adlist  
就是链表  
4
5
46  
CHAPTER 5. REDIS 数据结构 ADLIST  
Chapter 6  
redis 数据结构 sds  
sds 被称为是 Hacking String. hack 的地方就在 sds 保存了字符串的长度以及剩  
余空间。sds 的实现在 sds.c 中。  
sds 头部的实现:  
struct sdshdr {  
int len ;  
int f r e e ;  
char buf [ ] ;  
}
;
倘若使用指针即 char *buf,分配内存需要量两个步骤:一次分配结构体,一次  
分配 char *buf,在是否内存的时候也需要释放两次内存:一次为 char *buf,一次为  
结构体内存。而用长度为 0 的字符数组可以将分配和释放内存的次数都降低为 1 次,  
从而简化内存的管理。  
4
7
48  
CHAPTER 6. REDIS 数据结构 SDS  
4
9
另外,长度为 0 的数组即 char buf[] 不占用内存:  
/ char buf [ ]  情 况  
/
struct sdshdr s ;  
p r i n t f ( ”%d” , sizeof ( s ) ) ;  
/ 8  
/
/
/ char * buf  情 况  
struct sdshdr s ;  
p r i n t f ( ”%d” , sizeof ( s ) ) ;  
/
/ 12  
redis 中涉及较多的字符串操作,譬如 APPEND 命令。相比普通的字符串,sds  
获取字符串的长度以及剩余空间的复杂度都是 O(1),前者需要 O(N).  
/
/ 返 回 sdshdr . len  
static i n l i n e size_t sdslen ( const sds s ) {  
struct sdshdr *sh = ( void *) ( s(sizeof ( struct sdshdr ) ) ) ;  
return sh>len ;  
}
/
/ 返 回 sdshdr . fr e e  
static i n l i n e size_t s d s a v a i l ( const sds s ) {  
struct sdshdr *sh = ( void *) ( s(sizeof ( struct sdshdr ) ) ) ;  
return sh>f r e e ;  
}
sds.c 中还实现了针对 sds 的字符串操作函数,譬如分配,追加,释放等。  
50  
CHAPTER 6. REDIS 数据结构 SDS  
Chapter 7  
redis 数据结构 dict  
7
.1 redis 的键值对存储在哪里  
redis 中有多个数据集,数据集采用的数据结构是哈希表,用以存储键值对。  
默认所有的客户端都是使用第一个数据集,如果客户端有需要可以使用 select 命令来  
选择不同的数据集。redis 在初始化服务器的时候就会初始化所有的数据集:  
void i n i t S e r v e r () {  
.
. . . . .  
/
/  配 数 据 集 空 间  
server . db = zmalloc ( sizeof ( redisDb ) * server . dbnum) ;  
.
/
/
. . . . .  
/ 初 始 化 redis 数 据 集  
* Create the Redis databases , and i n i t i a l i z e other  
i n t e r n a l s t a t e . */  
for ( j = 0; j < server .REDIS_DEFAULT_DBNUM; j++) { // 初  
始 化 多 个 数 据 库  
/
/ 哈 希 表, 用 于 存 储 键 值 对  
server . db [ j ] . dict = dictCreate(&dbDictType ,NULL) ;  
/
/ 哈 希 表, 用 于 存 储 每 个 键 的 过 期 时 间  
server . db [ j ] . expires = dictCreate(&keyptrDictType ,  
NULL) ;  
.
. . . . .  
}
.
. . . . .  
}
5
1
52  
CHAPTER 7. REDIS 数据结构 DICT  
7
.2 哈希表 dict  
数据集采用的数据结构是哈希表,数据真正存储在哈希表中,用开链法解决冲突  
问题,struct dictht 即为一个哈希表。但在 redis 哈希表数据结构 struct dict 中有两  
个哈希表,下文将两个哈希表分别称为第一个和第二个哈希表,redis 提供两个哈希  
表是为了能够在不中断服务的情况下扩展(expand)哈希表,很有趣的一部分。  
/
/ 可 以 把 它 认 为 是 一 个 链 表, 提 示, 开 链 法  
typedef struct dictEntry {  
void *key ;  
union {  
void * val ;  
uint64_t u64 ;  
int64_t s64 ;  
v ;  
}
struct dictEntry *next ;  
}
dictEntry ;  
/
/ 要 存 储 多 种 多 样 的 数 据 结 构, 势 必 不 同 的 数 据 有 不 同 的 哈 希 算 法,  
不 同 的 键 值 比 较 算 法, 不 同 的 析 构 函 数。  
typedef struct dictType {  
/
/  希 函 数  
unsigned int (* hashFunction ) ( const void *key ) ;  
void *(*keyDup) ( void * privdata , const void *key ) ;  
void *(* valDup ) ( void * privdata , const void * obj ) ;  
7.2. 哈希表 DICT  
53  
/
/  较 函 数  
int (* keyCompare ) ( void * privdata , const void *key1 , const  
void *key2 ) ;  
/
/  值 析 构 函 数  
void (* keyDestructor ) ( void * privdata , void *key ) ;  
void (* valDestructor ) ( void * privdata , void * obj ) ;  
dictType ;  
}
/
/
/  般 哈 希 表 数 据 结 构  
* This i s our hash t a b l e structure . Every dictionary has two  
of t h i s as we  
implement incremental rehashing , for the old to the new  
t a b l e . */  
*
typedef struct dictht {  
/  个 哈 希 表  
dictEntry ** table ;  
/
/
/  希 表 的 大 小  
unsigned long s i z e ;  
/
/  希 表 大 小 掩 码  
unsigned long sizemask ;  
/
/  希 表 中 数 据 项 数 量  
unsigned long used ;  
dictht ;  
}
/
/ 哈 希 表 (字 典) 数 据 结 构, redis 的 所 有 键 值 对 都 会 存 储 在 这 里。  
其 中 包 含 两 个 哈 希 表。  
typedef struct dict {  
/
/ 哈 希 表 的 类 型, 包 括 哈 希 函 数, 比 较 函 数, 键 值 的 内 存 释 放 函  
dictType *type ;  
/
/  储 一 些 额 外 的 数 据  
void * privdata ;  
/
/  个 哈 希 表  
dictht ht [ 2 ] ;  
54  
CHAPTER 7. REDIS 数据结构 DICT  
/
/ 哈 希 表 重 置 下 标, 指 定 的 是 哈 希 数 组 的 数 组 下 标  
int rehashidx ; /* rehashing not in progress i f rehashidx  
= 1 */  
=
/
/  定 到 哈 希 表 的 迭 代 器 个 数  
int i t e r a t o r s ; /* number of i t e r a t o r s currently running  
*/  
dict ;  
}
7
.3 扩展哈希表  
redis 为每个数据集配备两个哈希表,能在不中断服务的情况下扩展哈希表。平  
时哈希表扩展的做法是,为新的哈希表另外开辟一个空间,将原哈希表的数据重新计  
算哈希值,以移动到新哈希表。如果原哈希表数据过多,中间大量的计算过程较好费  
大量时间。  
redis 扩展哈希表的做法有点小聪明:为第二个哈希表分配新空间,其空间大小为原  
哈希表键值对数量的两倍(是的,没错),接着逐步将第一个哈希表中的数据移动到  
第二个哈希表;待移动完毕后,将第二个哈希值赋值给第一个哈希表,第二个哈希表  
置空。在这个过程中,数据会分布在两个哈希表,这时候就要求在 CURD 时,都要  
考虑两个哈希表。  
而这里,将第一个哈希表中的数据移动到第二个哈希表被称为重置哈希(rehash)。  
7
.4 重置哈希表  
CURD 的时候会执行一步的重置哈希表操作,在服务器定时程序 serverCorn()  
中会执行一定时间的重置哈希表操作。为什么在定时程序中重置哈希表了,还 CURD  
的时候还要呢?或者反过来问。一个可能的原因是 redis 做了两手准备:在服务器空  
闲的时候,定时程序会完成重置哈希表;在服务器过载的时候,更多重置哈希表操作  
会落在 CURD 的服务上。  
下面是重置哈希表的函数,其主要任务就是选择哈希表中的一个位置上的单链表,重  
新计算哈希值,放到第二个哈希表。  
int dictRehash ( dict *d , int n) {  
/
/ 重 置 哈 希 表 结 束, 直 接 返 回  
i f ( ! dictIsRehashing (d) ) return 0;  
while (n−−) {  
dictEntry *de , *nextde ;  
/
/ 第 一 个 哈 希 表 为 空, 证 明 重 置 哈 希 表 已 经 完 成, 将 第 二 个  
哈 希 表 赋 值 给 第 一 个,  
7.4. 重置哈希表  
55  
/
/
/  束  
* Check i f we already rehashed the whole t a b l e . . . */  
i f (d>ht [ 0 ] . used == 0) {  
z f r e e (d>ht [ 0 ] . table ) ;  
d>ht [ 0 ] = d>ht [ 1 ] ;  
_
dictReset(&d>ht [ 1 ] ) ;  
d>rehashidx = 1;  
return 0;  
}
/
* Note that rehashidx can ’ t overflow as we are sure  
there are more  
*
elements because ht [ 0 ] . used != 0 */  
a s s e r t (d>ht [ 0 ] . s i z e > (unsigned)d>rehashidx ) ;  
/
/  到 哈 希 表 中 不 为 空 的 位 置  
while (d>ht [ 0 ] . table [ d>rehashidx ] == NULL) d>  
rehashidx++;  
de = d>ht [ 0 ] . table [ d>rehashidx ] ;  
/
/
/  位 置 的 所 有 数 据 移 动 到 第 二 个 哈 希 表  
* Move a l l the keys in t h i s bucket from the old to  
the new hash HT */  
while ( de ) {  
unsigned int h ;  
nextde = de>next ;  
/
/
* Get the index in the new hash t a b l e */  
/  算 哈 希 值  
h = dictHashKey (d , de>key ) & d>ht [ 1 ] . sizemask ;  
/
/  插 法  
de>next = d>ht [ 1 ] . table [ h ] ;  
d>ht [ 1 ] . table [ h ] = de ;  
/
/  新 哈 希 表 中 的 数 据 量  
d>ht [ 0 ] . used−−;  
d>ht [ 1 ] . used++;  
de = nextde ;  
}
/
/  空  
56  
CHAPTER 7. REDIS 数据结构 DICT  
d>ht [ 0 ] . table [ d>rehashidx ] = NULL;  
/  向 哈 希 表 的 下 一 个 位 置  
/
d>rehashidx++;  
}
return 1;  
}
7
.5 低效率的哈希表添加替换  
redis 添加替换的时候,都先要查看数据集中是否已经存在该键,也就是一个  
查找的过程,如果一个 redis 命令导致过多的查找,会导致效率低下。可能是为了扬  
长避短,即高读性能和低写性能,redis 中数据的添加和替换效率不高,特别是替换效  
率低的恶心。  
7.5. 低效率的哈希表添加替换  
57  
redis SET 命令的调用链中,添加键值对会导致了 2 次的键值对查找;替换键  
值对最多会导致 4 次的键值对查找。在 dict 的实现中,dictFind() _dictIndex()  
都会导致键值对的查找,详细可以参看源码。所以,从源码来看,经常在 redis 上写  
不是一个明智的选择。  
58  
CHAPTER 7. REDIS 数据结构 DICT  
7
.6 哈希表的迭代  
RDB AOF 持久化操作中,都需要迭代哈希表。哈希表的遍历本身难度不  
大,但因为每个数据集都有两个哈希表,所以遍历哈希表的时候也需要注意遍历两个  
哈希表:第一个哈希表遍历完毕的时候,如果发现重置哈希表尚未结束,则需要继续  
遍历第二个哈希表。  
/
/  代 器 取 下 一 个 数 据 项 的 入 口  
dictEntry * dictNext ( d i c t I t e r a t o r * i t e r )  
{
while (1) {  
i f ( iter >entry == NULL) {  
dictht *ht = &ite r >d>ht [ iter >table ] ;  
/
/  的 迭 代 器  
i f ( iter >index == 1 && iter >table == 0) {  
i f ( it er >s a f e )  
ite r >d>i t e r a t o r s ++;  
else  
iter >f i n g e r p r i n t = dictFingerprint ( ite r  
>d) ;  
}
iter >index++;  
/
/ 下 标 超 过 了 哈 希 表 大 小, 不 合 法  
i f ( iter >index >= ( signed ) ht>s i z e ) {  
/
/
/ 如 果 正 在 重 置 哈 希 表, redis 会 尝 试 在 第 二 个 哈  
希 表 上 进 行 迭 代,  
/  则 真 的 就 不 合 法 了  
i f ( dictIsRehashing ( iter >d) && ite r >table  
= 0) {  
=
/
/ 正 在 重 置 哈 希 表, 证 明 数 据 正 在 从 第 一 个 哈 希 表  
整 合 到 第 二 个 哈 希 表,  
/  指 向 第 二 个 哈 希 表  
ite r >table++;  
/
iter >index = 0;  
ht = &iter >d>ht [ 1 ] ;  
}
/
else {  
/ 否 则 迭 代 完 毕, 这 是 真 正 不 合 法 的 情 况  
break ;  
}
}
7.6. 哈希表的迭代  
59  
/
/  得 数 据 项 入 口  
ite r >entry = ht>table [ ite r >index ] ;  
}
else {  
/
ite r >entry = iter >nextEntry ;  
/  得 下 一 个 数 据 项 人 口  
}
/
/
/ 迭 代 器 会 保 存 下 一 个 数 据 项 的 入 口, 因 为 用 户 可 能 会 删 除  
此 函 数 返 回 的 数 据 项  
/ 入 口, 如 此 会 导 致 迭 代 器 失 效, 找 不 到 下 一 个 数 据 项 入 口  
i f ( iter >entry ) {  
/
* We need to save the ’ next ’ here , the i t e r a t o r  
user  
*
may d e l e t e the entry we are returning . */  
ite r >nextEntry = ite r >entry>next ;  
return iter >entry ;  
}
}
return NULL;  
}
60  
CHAPTER 7. REDIS 数据结构 DICT  
Chapter 8  
redis 数据结构 ziplist  
8
.1 概述  
redis 中,list 有两种存储方式:双链表(LinkedList)和压缩双链表(ziplist)。  
双链表即普通数据结构中遇到的,在 adlist.h adlist.c 中实现。压缩双链表以连续  
的内存空间来表示双链表,压缩双链表节省前驱和后驱指针的空间(8B),这在小的  
list 上,压缩效率是非常明显的;压缩双链表在 ziplist.h ziplist.c 中实现。  
这篇主要详述压缩双链表,普通双链表可以参看其他。  
8
.2 压缩双链表的具体实现  
在压缩双链表中,节省了前驱和后驱指针的空间,共 8 个字节,这让数据在内存  
中更为紧凑。只要清晰的描述每个数据项的边界,就可以轻易得到后驱数据项的位置;  
只要描述前驱数据项的大小,就可以定位前驱数据项的位置,redis 就是这么做的。  
ziplist 的格式可以表示为:  
<
zlbytes ><z l t a i l ><zllen ><entry >... < entry><zlend>  
zlbytes ziplist 占用的空间;zltail 是最后一个数据项的偏移位置,这方便逆向  
遍历链表,也是双链表的特性;zllen 是数据项 entry 的个数;zlend 就是 255,占 1B.  
详细展开 entry 的结构。  
entry 的格式即为典型的 type-lenght-value,即 TLV,表述如下:  
|
< prelen><<encoding+l e n s i z e ><len>><data >|  
|
−−−1−−−−−−−−−−−−−−−−2−−−−−−−−−−−−−−3−−−|  
1)是前驱数据项的大小。因为不用描述前驱的数据类型,描述较为简单。  
6
1
62  
CHAPTER 8. REDIS 数据结构 ZIPLIST  
2)是此数据项的的类型和数据大小。为了节省空间,redis 预设定了多种长度  
的字符串和整数。  
种长度的字符串  
3
#
define ZIP_STR_06B (0 << 6)  
define ZIP_STR_14B (1 << 6)  
define ZIP_STR_32B (2 << 6)  
#
#
5
种长度的整数  
#
define ZIP_INT_16B (0 xc0 | 0<<4)  
define ZIP_INT_32B (0 xc0 | 1<<4)  
define ZIP_INT_64B (0 xc0 | 2<<4)  
define ZIP_INT_24B (0 xc0 | 3<<4)  
define ZIP_INT_8B 0 xfe  
#
#
#
#
3)为真正的数据。  
透过 ziplist 查找函数 ziplistFind(),熟悉 ziplist entry 对数据格式:  
/
/
/  z i p l i s t  查 找 数 据 项  
* Find pointer to the entry equal to the s p e c i f i e d entry .  
Skip ’ skip ’ e n t r i e s  
*
between every comparison . Returns NULL when the f i e l d could  
not be found . */  
unsigned char * z i p l i s t F i n d (unsigned char *p , unsigned char *  
vstr , unsigned int vlen , unsigned int skip ) {  
int skipcnt = 0;  
unsigned char vencoding = 0;  
long long v l l = 0;  
while (p [ 0 ] != ZIP_END) {  
unsigned int prevlensize , encoding , l e n s i z e , len ;  
unsigned char *q ;  
ZIP_DECODE_PREVLENSIZE(p , p r e v l e n s i z e ) ;  
/
/
/
/ 跳 过 前 驱 数 据 项 大 小, 解 析 数 据 项 大 小  
/ len  data  小  
/ l e n s i z e  len  占 内 存 大 小  
ZIP_DECODE_LENGTH(p + prevlensize , encoding , l e n s i z e ,  
len ) ;  
8.2. 压缩双链表的具体实现  
63  
/
/ q  向 data  
q = p + p r e v l e n s i z e + l e n s i z e ;  
i f ( skipcnt == 0) {  
/
* Compare current entry with s p e c i f i e d entry */  
i f (ZIP_IS_STR( encoding ) ) {  
/
/  符 串 比 较  
i f ( len == vlen && memcmp(q , vstr , vlen ) ==  
) {  
return p ;  
0
}
}
/
else {  
/  数 比 较  
/
* Find out i f the searched f i e l d can be  
encoded . Note that  
*
*
we do i t only the f i r s t time , once done  
vencoding i s s et  
to nonzero and v l l i s s et to the i n teger  
value . */  
i f ( vencoding == 0) {  
/
/  试 将 v s t r  析 为 整 数  
i f ( ! zipTryEncoding ( vstr , vlen , &vll , &  
vencoding ) ) {  
/
* I f the entry can ’ t be encoded we  
set i t to  
*
UCHAR_MAX so that we don ’ t retry  
again the next  
*
time . */  
/
/  能 编 码 为 数 字 ! ! ! 会 导 致 当 前 查 找  
的 数 据 项 被 跳 过  
vencoding = UCHAR_MAX;  
}
/
* Must be nonzero by now */  
a s s e r t ( vencoding ) ;  
}
/
* Compare current entry with s p e c i f i e d entry  
,
do i t only  
*
*
i f vencoding != UCHAR_MAX because i f there  
i s no encoding  
p o s s i b l e for the f i e l d i t can ’ t be a v a l i d  
in teger . */  
64  
CHAPTER 8. REDIS 数据结构 ZIPLIST  
i f ( vencoding != UCHAR_MAX) {  
/  取 整 数  
long long l l = zipLoadInteger (q , encoding  
/
)
;
i f ( l l == v l l ) {  
return p ;  
}
}
}
/
* Reset skip count */  
skipcnt = skip ;  
}
}
else {  
/
skipcnt −−;  
* Skip entry */  
/
/
/  动 到 z i p l i s t  下 一 个 数 据 项  
* Move to next entry */  
p = q + len ;  
}
/
/  有 找 到  
return NULL;  
}
 》》》 》》 》》 》》  》》  
Chapter 9  
redis 数据结构 skiplist  
9
.1 概述  
跳表(skiplist)是一个特俗的链表,相比一般的链表,有更高的查找效率,其效  
率可比拟于二叉查找树。  
一张关于跳表和跳表搜索过程如下图:  
在图中,需要寻找 68,在给出的查找过程中,利用跳表数据结构优势,只比较了  
次,横箭头不比较,竖箭头比较。由此可见,跳表预先间隔地保存了有序链表中的  
节点,从而在查找过程中能达到类似于二分搜索的效果,而二分搜索思想就是通过比  
较中点数据放弃另一半的查找,从而节省一半的查找时间。  
3
缺点即浪费了空间,自古空间和时间两难全。  
插播一段:跳表在 1990 年由 William Pugh 提出,而红黑树早在 1972 年由鲁道  
夫·贝尔发明了。红黑树在空间和时间效率上略胜跳表一筹,但跳表实现相对简单得  
到程序猿们的青睐。redis leveldb 中都有采用跳表。  
6
5
66  
CHAPTER 9. REDIS 数据结构 SKIPLIST  
这篇文章,借着 redis 的源码了解跳表的实现。  
9
.2 跳表的数据结构  
从上图中,总结跳表的性质:  
1
2
3
4
5
. 由很多层结构组成  
. 每一层都是一个有序的链表  
. 最底层 (Level 1) 的链表包含所有元素  
. 如果一个元素出现在 Level i 的链表中,则它在 Level i 之下的链表也都会出现。  
. 每个节点包含两个指针,一个指向同一链表中的下一个元素,一个指向下面一  
层的元素。  
redis 中跳表数据结构定义:  
/
/
/  表 节 点 结 构 体  
* ZSETs use a s p e c i a l i z e d version of S k i p l i s t s */  
typedef struct zskiplistNode {  
/
/  点 数 据  
robj * obj ;  
/
/ 分 数, 游 戏 分 数? 按 游 戏 分 数 排 序  
double score ;  
/
/  驱 指 针  
struct zskiplistNode *backward ;  
9.3. 跳表的插入  
67  
/
/  驱 指 针 数 组 TODO  
struct z s k i p l i s t L e v e l {  
struct zskiplistNode * forward ;  
/
/  到 下 一 个 数 据 项 需 要 走 多 少 步  
unsigned int span ;  
} l e v e l [ ] ;  
zskiplistNode ;  
}
typedef struct z s k i p l i s t {  
/  表 头 尾 指 针  
struct zskiplistNode *header , * t a i l ;  
/
/
/  表 的 长 度  
unsigned long length ;  
/
/  表 的 高 度  
int l e v e l ;  
}
z s k i p l i s t ;  
特别的,在上图中似乎每个数据都被保存了多次,其实只保存了一次。在 struct  
zskiplistNode 中数据和指针是分开存储的,struct zskiplistLevel 即是一个描述跳表层  
级的数据结构。  
9
.3 跳表的插入  
跳表算法描述如下:找出每一层新插入数据位置的前驱并保存,在 redis 中跳表  
插入是根据 score/member 的大小(看不懂可以参看 redis ZADD 命令)来决定插入  
的位置;将新数据插入到指定位置,并调整指针,在 redis 中还会调整 span。  
什么是 span?  
6
2
8
CHAPTER 9. REDIS 数据结构 SKIPLIST  
span 即从两个相邻节点间隔了多少节点。譬如 level 1-1 span 就是 1level  
-1 span 2。  
因为新出入数据的层数是随机的,有两种情况 小于等于原有的层数;大于原  
有的层数。需要做特殊处理。  
)小于等于原有的层数  
1
redis 中跳表插入算法的具体实现:  
zskiplistNode * z s l I n s e r t ( z s k i p l i s t * zsl , double score , robj *  
obj ) {  
zskiplistNode *update [ZSKIPLIST_MAXLEVEL] , *x ;  
unsigned int rank [ZSKIPLIST_MAXLEVEL ] ;  
int i , l e v e l ;  
redisAssert ( ! isnan ( score ) ) ;  
x = zsl >header ;  
/
/ 遍 历 s k i p l i s t  所 有 的 层, 找 到 数 据 将 要 插 入 的 位 置, 并 保  
存 在 update 中  
for ( i = zsl >level 1; i >= 0; i −−) {  
/
* store rank that i s crossed to reach the i n s e r t  
pos i ti on */  
rank [ i ] = i == ( zsl >level 1) ? 0 : rank [ i +1];  
/
/  表 的 搜 索  
while (x>l e v e l [ i ] . forward &&  
x>l e v e l [ i ] . forward>score < score | |  
x>l e v e l [ i ] . forward>score == score &&  
compareStringObjects (x>l e v e l [ i ] . forward>obj  
(
(
,
obj ) < 0) ) ) {  
rank [ i ] += x>l e v e l [ i ] . span ;  
x = x>l e v e l [ i ] . forward ;  
9.3. 跳表的插入  
69  
}
/
/ update [ i ]  录 了 新 数 据 项 的 前 驱  
update [ i ] = x ;  
}
/
/
/ random  个 l e v e l  是 随 机 的  
* we assume the key i s not already inside , since we  
allow duplicated  
*
*
*
scores , and the rei n s e r t i o n of score and redis o b j e c t  
should never  
happen since the c a l l e r of z s l I n s e r t () should t e s t in  
the hash t a b l e  
i f the element i s already inside or not . */  
l e v e l = zslRandomLevel () ;  
/
/ random l e v e l  原 有 的 zsl >l e v e l 大, 需 要 增 加 s k i p l i s t  
 l e v e l  
i f ( l e v e l > zsl >l e v e l ) {  
for ( i = zsl >l e v e l ; i < l e v e l ; i++) {  
rank [ i ] = 0;  
update [ i ] = zsl >header ;  
update [ i ]> l e v e l [ i ] . span = zsl >length ;  
}
zsl >l e v e l = l e v e l ;  
}
/
/  入  
x = zslCreateNode ( level , score , obj ) ;  
for ( i = 0; i < l e v e l ; i++) {  
/
/  节 点 项 插 到 update [ i ]  后 面  
x>l e v e l [ i ] . forward = update [ i ]> l e v e l [ i ] . forward ;  
update [ i ]> l e v e l [ i ] . forward = x ;  
/
* update span covered by update [ i ] as x i s inserted  
here */  
x>l e v e l [ i ] . span = update [ i ]> l e v e l [ i ] . span  ( rank  
[
0 ]  rank [ i ] ) ;  
update [ i ]> l e v e l [ i ] . span = ( rank [ 0 ]  rank [ i ] ) + 1;  
}
/
/  高 的 l e v e l  未 调 整 span  
70  
CHAPTER 9. REDIS 数据结构 SKIPLIST  
/
* increment span for untouched l e v e l s */  
for ( i = l e v e l ; i < zsl >l e v e l ; i++) {  
update [ i ]> l e v e l [ i ] . span++;  
}
/
/  整 新 节 点 的 前 驱 指 针  
x>backward = ( update [ 0 ] == zsl >header ) ? NULL : update  
[
0 ] ;  
i f (x>l e v e l [ 0 ] . forward )  
x>l e v e l [ 0 ] . forward>backward = x ;  
else  
zsl >t a i l = x ;  
/
/  整 s k i p l i s t  长 度  
zsl >length++;  
return x ;  
}
9
.4 跳表的删除  
跳表的删除算和插入算法步骤类似:找出每一层需删除数据的前驱并保存;接着  
调整指针,在 redis 中还会调整 span。  
redis 中跳表删除算法的具体实现:  
/
/
/
/ x  需 要 删 除 的 节 点  
/ update 是 每 一 个 层 x  前 驱 数 组  
* Internal function used by zslDelete , zslDeleteByScore and  
zslDeleteByRank */  
9.5. REDIS 中的跳表  
71  
void zslDeleteNode ( z s k i p l i s t * zsl , zskiplistNode *x ,  
zskiplistNode ** update ) {  
int i ;  
/
/  整 span  forward  针  
for ( i = 0; i < zsl >l e v e l ; i++) {  
i f ( update [ i ]> l e v e l [ i ] . forward == x) {  
update [ i ]> l e v e l [ i ] . span += x>l e v e l [ i ] . span  1;  
update [ i ]> l e v e l [ i ] . forward = x>l e v e l [ i ] . forward  
;
}
}
else {  
/
/ update [ i]> l e v e l [ i ] . forward == NULL, 只 调 整  
span  
update [ i ]> l e v e l [ i ] . span = 1;  
}
/
/  整 后 驱 指 针  
i f (x>l e v e l [ 0 ] . forward ) {  
x>l e v e l [ 0 ] . forward>backward = x>backward ;  
else {  
zsl >t a i l = x>backward ;  
}
}
/
/ 删 除 某 一 个 节 点 后, 层 数 l e v e l  能 降 低, 调 整 l e v e l  
while ( zsl >l e v e l > 1 && zsl >header>l e v e l [ zsl >level 1].  
forward == NULL)  
zsl >level −−;  
/
/  整 跳 表 的 长 度  
zsl >length −−;  
}
9
.5 redis 中的跳表  
redis 中结合跳表(skiplist)和哈希表(dict)形成一个新的数据结构 zset。添加  
dict 是为了快速定位跳表中是否存在某个 member!  
typedef struct zset {  
dict * dict ;  
z s k i p l i s t * z s l ;  
72  
CHAPTER 9. REDIS 数据结构 SKIPLIST  
}
zset ;  
9
.6 redis 选用 skiplist 场景  
ZXX 命令是针对有序集合(sorted set)的,譬如:  
ZADD  
ZCARD  
ZCOUNT  
ZINCRBY  
ZINTERSTORE  
ZLEXCOUNT  
ZRANGE  
ZRANGEBYLEX  
ZRANGEBYSCORE  
ZRANK  
ZREM  
ZREMRANGEBYLEX  
ZREMRANGEBYRANK  
ZREMRANGEBYSCORE  
ZREVRANGE  
ZREVRANGEBYSCORE  
ZREVRANK  
ZSCAN  
ZSCORE  
ZUNIONSTORE  
Chapter 10  
redis 数据结构 intset  
intset dict 都是 sadd 命令的底层数据结构,当添加的所有数据都是整数时,  
会使用前者;否则使用后者。特别的,当遇到添加数据为字符串,即不能表示为整数  
时,redis 会把数据结构转换为 dict,即把 intset 中的数据全部搬迁到 dict。  
本片展开的是 intsetdict 的文章可以参看之前写的《深入剖析 redis 数据结构  
dict》。  
1
0.1 intset 结构体  
intset 底层本质是一个有序的、不重复的、整型的数组,支持不同类型整数。  
typedef struct i n t s e t {  
/  个 整 数 的 类 型  
uint32_t encoding ;  
/
/
/ i n t s e t  度  
uint32_t length ;  
/
/  数 数 组  
int8_t contents [ ] ;  
i n t s e t ;  
}
encoding 能下面的三个值:分别是 1632 64 位整数:  
/
*
* Note that these encodings are ordered , so :  
INTSET_ENC_INT16 < INTSET_ENC_INT32 < INTSET_ENC_INT64. */  
define INTSET_ENC_INT16 ( sizeof ( int16_t ) )  
#
7
3
74  
CHAPTER 10. REDIS 数据结构 INTSET  
#
define INTSET_ENC_INT32 ( sizeof ( int32_t ) )  
#
define INTSET_ENC_INT64 ( sizeof ( int64_t ) )  
1
0.2 intset 搜索  
intset 是有序的整数数组,可以用二分搜索查找。  
static uint8_t intsetSearch ( i n t s e t * is , int64_t value ,  
uint32_t *pos ) {  
int min = 0 , max = i n t r e v 3 2 i f b e ( is >length ) 1, mid = 1;  
int64_t cur = 1;  
/
/
* The value can never be found when the set i s empty */  
/  合 为 空  
i f ( i n t r e v 3 2 i f b e ( is >length ) == 0) {  
i f ( pos ) *pos = 0;  
return 0;  
}
else {  
/
* Check for the case where we know we cannot find  
the value ,  
*
but do know the i n s e r t po sit i on . */  
/
i f ( value > _intsetGet ( is , i n t r e v 3 2 i f b e ( is >length ) 1)  
/ value  最 大 元 素 还 大  
)
{
i f ( pos ) *pos = i n t r e v 3 2 i f b e ( is >length ) ;  
return 0;  
/
}
/ value  最 小 元 素 还 小  
else i f ( value < _intsetGet ( is , 0 ) ) {  
i f ( pos ) *pos = 0;  
return 0;  
}
}
/
/  分 查 找  
while (max >= min) {  
mid = (min+max) /2;  
cur = _intsetGet ( is , mid)