《Redis设计与实现》对Redis的大多数单机功能以及所有多机功能的实现原理进行了介绍，展示了这些功能的核心数据结构以及关键的算法思想。通过阅读本书，读者可以快速、有效地了解Redis的内部构造以及运作机制，这些知识可以帮助读者更好、更高效地使用Redis。本书主要分为四大部分。第一部分“数据结构与对象”介绍了Redis中的各种对象及其数据结构，并说明这些数据结构如何影响对象的功能和性能。第二部分“单机数据库的实现”对Redis实现单机数据库的方法进行了介绍，包括数据库、RDB持久化、AOF持久化、事件等。第三部分“多机数据库的实现”对Redis的Sentinel、复制（replication）、集群（cluster）三个多机功能进行了介绍。第四部分“独立功能的实现”对Redis中各个相对独立的功能模块进行了介绍，涉及发布与订阅、事务、Lua脚本、排序、二进制位数组、慢查询日志、监视器等。

黄健宏，软件开发者，他喜欢函数式编程，热爱开源软件。出于对数据库的强烈兴趣，他开始阅读和分析 Redis 源代码，并对 Redis 2.6 和 Redis 3.0 的源代码进行了详细注释。他翻译并维护着 Redis 中文文档网站 www.RedisDoc.com ，编写了 OORedis 库。除此之外，他还是《Redis in Action》一书的译者。

前言
致谢
第1章 引言 1
1.1 Redis版本说明 1
1.2 章节编排 1
1.3 推荐的阅读方法 4
1.4 行文规则 4
1.5 配套网站 5

第一部分·数据结构与对象
第2章 简单动态字符串 8
2.1 SDS的定义 9
2.2 SDS与C字符串的区别 10
2.3 SDS API 17
2.4 重点回顾 18
2.5 参考资料 18
第3章 链表 19
3.1 链表和链表节点的实现 20
3.2 链表和链表节点的API 21
3.3 重点回顾 22
第4章 字典 23
4.1 字典的实现 24
4.2 哈希算法 27
4.3 解决键冲突 28
4.4 rehash 29
4.5 渐进式rehash 32
4.6 字典API 36
4.7 重点回顾 37
第5章 跳跃表 38
5.1 跳跃表的实现 39
5.2 跳跃表API 44
5.3 重点回顾 45
第6章 整数集合 46
6.1 整数集合的实现 46
6.2 升级 48
6.3 升级的好处 50
6.4 降级 51
6.5 整数集合API 51
6.6 重点回顾 51
第7章 压缩列表 52
7.1 压缩列表的构成 52
7.2 压缩列表节点的构成 54
7.3 连锁更新 57
7.4 压缩列表API 59
7.5 重点回顾 59
第8章 对象 60
8.1 对象的类型与编码 60
8.2 字符串对象 64
8.3 列表对象 68
8.4 哈希对象 71
8.5 集合对象 75
8.6 有序集合对象 77
8.7 类型检查与命令多态 81
8.8 内存回收 84
8.9 对象共享 85
8.10 对象的空转时长 87
8.11 重点回顾 88

第二部分·单机数据库的实现
第9章 数据库 90
9.1 服务器中的数据库 90
9.2 切换数据库 91
9.3 数据库键空间 93
9.4 设置键的生存时间或过期时间 99
9.5 过期键删除策略 107
9.6 Redis的过期键删除策略 108
9.7 AOF、RDB和复制功能对过期键的处理 111
9.8 数据库通知 113
9.9 重点回顾 117
第10章 RDB持久化 118
10.1 RDB 文件的创建与载入 119
10.2 自动间隔性保存 121
10.3 RDB 文件结构 125
10.4 分析RDB文件 133
10.5 重点回顾 137
10.6 参考资料 137
第11章 AOF持久化 138
11.1 AOF持久化的实现 139
11.2 AOF文件的载入与数据还原 142
11.3 AOF重写 143
11.4 重点回顾 150
第12章 事件 151
12.1 文件事件 151
12.2 时间事件 156
12.3 事件的调度与执行 159
12.4 重点回顾 161
12.5 参考资料 161
第13章 客户端 162
13.1 客户端属性 163
13.2 客户端的创建与关闭 172
13.3 重点回顾 174
第14章 服务器 176
14.1 命令请求的执行过程 176
14.2 serverCron函数 184
14.3 初始化服务器 192
14.4 重点回顾 196

第三部分·多机数据库的实现
第15章 复制 198
15.1 旧版复制功能的实现 199
15.2 旧版复制功能的缺陷 201
15.3 新版复制功能的实现 203
15.4 部分重同步的实现 204
15.5 PSYNC 命令的实现 209
15.6 复制的实现 211
15.7 心跳检测 216
15.8 重点回顾 218
第16章 Sentinel 219
16.1 启动并初始化Sentinel 220
16.2 获取主服务器信息 227
16.3 获取从服务器信息 229
16.4 向主服务器和从服务器发送信息 230
16.5 接收来自主服务器和从服务器的频道信息 231
16.6 检测主观下线状态 234
16.7 检查客观下线状态 236
16.8 选举领头Sentinel 238
16.9 故障转移 240
16.10 重点回顾 243
16.11 参考资料 244
第17章 集群 245
17.1 节点 245
17.2 槽指派 251
17.3 在集群中执行命令 258
17.4 重新分片 265
17.5 ASK错误 267
17.6 复制与故障转移 273
17.7 消息 281
17.8 重点回顾 288

第四部分·独立功能的实现
第18章 发布与订阅 290
18.1 频道的订阅与退订 292
18.2 模式的订阅与退订 295
18.3 发送消息 298
18.4 查看订阅信息 300
18.5 重点回顾 303
18.6 参考资料 304
第19章 事务 305
19.1 事务的实现 306
19.2 WATCH 命令的实现 310
19.3 事务的ACID 性质 314
19.4 重点回顾 319
19.5 参考资料 320
第20章 Lua脚本 321
20.1 创建并修改Lua 环境 322
20.2 Lua 环境协作组件 327
20.3 EVAL命令的实现 329
20.4 EVALSHA 命令的实现 332
20.5 脚本管理命令的实现 333
20.6 脚本复制 336
20.7 重点回顾 342
20.8 参考资料 343
第21章 排序 344
21.1 SORT 命令的实现 345
21.2 ALPHA 选项的实现 347
21.3 ASC 选项和DESC 选项的实现 348
21.4 BY选项的实现 350
21.5 带有ALPHA 选项的BY 选项的实现 352
21.6 LIMIT 选项的实现 353
21.7 GET选项的实现 355
21.8 STORE 选项的实现 358
21.9 多个选项的执行顺序 359
21.10 重点回顾 361
第22章 二进制位数组 362
22.1 位数组的表示 363
22.2 GETBIT命令的实现 365
22.3 SETBIT 命令的实现 366
22.4 BITCOUNT 命令的实现 369
22.5 BITOP 命令的实现 376
22.6 重点回顾 377
22.7 参考资料 377
第23章 慢查询日志 378
23.1 慢查询记录的保存 380
23.2 慢查询日志的阅览和删除 382
23.3 添加新日志 383
23.4 重点回顾 385
第24章 监视器 386
24.1 成为监视器 387
24.2 向监视器发送命令信息 387
24.3 重点回顾 388

1、 SDS

常数复杂度获取字符串长度

记录自身长度，避免缓冲区溢出

减少修改字符串时带来的内存重分配次数：空间预分配，惰性空间释放

二进制安全

只关心二进制化的字符串，不关心具体格式，只会严格的按照二进制的数据存取，不会妄图以某种特殊格式解析数据。

兼容部分 C 字符串函数

2、跳表

组成：zskiplist、zskiplistNode

复杂度：Olg(N)、最坏O(N)

有序集合键的底层实现之一、集群。

前进指针：遍历

跨度：计算排位 （Rank），在查找某个节点的过程中，将沿途访问过的所有层的跨度累加起来，得到的结果就是目标节点在跳跃表中的排位。

每个节点的层数是 1～32之间的随机数

同一跳跃表中，多个节点可以包含相同的分值，但每个节点的成员对象必须是唯一的

跳跃表中的节点按照分值大小进行排序，当分值相同时，节点按照成员对象的大小进行排序

3、字典

链地址法解决键冲突

渐进式 hash: h[0]、h[1]

4、垃圾回收

引用计数

对象共享：共享值为 0～9999的字符串对象

5、过期键删除策略

定时删除：存在大量待删除过期键时占用较多CPU时间，影响服务器的响应时间和吞吐量

Redis 采用策略：

惰性删除：读写指令前执行 expireIfNeeded 函数检查键是否过期

过期键如果不被删除，则占用内存不释放。浪费内存，有内存泄漏风险 。

定期删除：expires 字典中随机检查一部分键的过期时间，并删除过期键。

主服务器删除一个过期键后，向从服务器发送 DEL 指令，显式地删除过期键，从服务器不会主动删除过期键，需要等待主节点发送 DEL 命令，保证数据的一致性。

6、 数据库

由 dict 和 expires 组成，dict 字典负责保存键值对，expires 字典保存键的过期时间

所有数据库保存在 redisServer.db 中，数据库数量由redisServer.dbnum 保存

客户端通过修改目标数据库指针，让它指向 redisServer.db 数组中的不同元素来切换不同数据库。

7、RDB

保存所有键值对数据，压缩二进制文件

SAVE 阻塞主进程，BGSAVE fork 子进程负责创建 rdb 文件，不阻塞。

8、AOF

保存所有写命令。BGREWRITEAOF 重写 AOF 文件，减小 AOF 文件大小 。

子进程执行重写：

父进程可以继续处理命令请求

子进程带有服务器进程的数据副本，使用子进程而不是线程，可以避免在使用锁的情况下，保证数据的安全性。

子进程完成 AOF 重写后，向父进程发送信号，父进程调用信号处理函数（阻塞）并执行以下工作：

将 AOF 重写缓冲区中的所有内容写入到新的 AOF 文件，对新的 AOF 文件进行改名，原子地覆盖现有的 AOF 文件，

完成新旧两个 AOF 文件的替换。

数据一致性：

执行 BGREWRITEAOF 时，Redis 服务器维护一个 AOF 重写缓冲区，该缓冲区会在子进程创建新 AOF 文件期间，

记录服务器执行的所有写命令。当子进程完成创建新的 AOF 文件工作之后，服务器会将重写缓冲区的所有内容追加到新 AOF 文件的末尾，使得新旧两个 AOF 文件所保存的数据库状态一致。最后，服务器用新的 AOF 文件替换旧的 AOF 文件 ，以此来完成 AOF 文件的重写。

客户端（发送命令） > 命令处理器 （追加命令）> AOF 缓冲区 、AOF 重写缓冲区

9、事件

文件事件

处理并发：I/O 多路复用程序将所有产生事件的套接字放到一个队列里。

时间事件（存放在链表中, 属性：id、when、timeProc（函数） ）

定时事件：让程序在指定的时间之后执行一次

周期事件：让程序每隔指定时间执行一次

10、客户端

服务器端维护 clients 链表保存所有客户端的状态

11、同步

PSYNC 命令（新），完整重同步（初次复制）、部分重同步（断线后重复制）

部分重同步三要素：

复制偏移量

复制积压缓冲区（replication backlog）：如果 offset 偏移量之后的数据仍在 replication backlog 中，执行部分重同步；否则执行完整重同步。

服务器 run ID：若断线恢复，主服务器 run ID 不变，执行部分重同步；否则执行完整重同步。

12、 Sentinel

两个与主服务器的异步网络连接

命令连接，用于向主服务器发送命令，并接收回复

订阅连接，订阅主服务器的 Sentinel:hello 频道

每 10s 向主服务器发送 INFO 命令，获取服务器信息

主观下线 （SRI_S_DOWN，在 down-after-milliseconds 时间内，连续向Sentinel返回无效回复）－> 客观下线（足够多主观下线投票）

min-salves-to-write 1:至少向一个 slave 节点写数据，避免 master 网络隔离后继续写数据，造成数据不一致。

13、Cluster

16384 个槽、Gossip 协议

单个 master （无 slave）挂掉，则整个集群挂掉，可设置 cluster-require-full-coverage no 解决

bgsave 打开，多个实例同时 fork ，响应时间增大（关闭 bgsave，开 aof）

依赖客户端成熟度（智能客户端）

失效检测：

ping -> PFAIL -> FAIL

14、事务

将多个命令请求打包（队列），一次性、按顺序执行多个命令。

单线程串行执行事务，保证隔离性。

15、SORT 实现

根据数据项的 u.score 排序

单线程 mgetall，或者 hgetall 的时候会阻塞后续的调用

解决：redis 只拿来操作一些复杂的数据结构，比如 sorted set 之类的数据，可以拿来用 score 做排序，用吞吐量更好的多线程 memcached 来做 kv 缓存。

zadd的时候key已经过期了，导致一些看起来匪夷所思的bug之类的

解决：用expire then zadd的方式巧妙地解决了这些问题。