Redis设计与实现.pdf

【核心代码】

Contents
1 第一部分：内部数据结构 3
1.1 简单动态字符串 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.1 sds 的用途 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.2 Redis 中的字符串 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1.3 优化追加操作 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.1.4 sds 模块的 API . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.1.5 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2 双端链表 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.1 双端链表的应用 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2.2 双端链表的实现 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.2.3 迭代器 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2.4 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.3 字典 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.3.1 字典的应用 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.3.2 字典的实现 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.3.3 创建新字典 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.3.4 添加键值对到字典 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.3.5 添加新元素到空白字典 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.3.6 添加新键值对时发生碰撞处理 . . . . . . . . . . . . . . . . . . . . . . . . 21
1.3.7 添加新键值对时触发了 rehash 操作 . . . . . . . . . . . . . . . . . . . . . 22
1.3.8 Rehash 执行过程 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.3.9 渐进式 rehash . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
1.3.10 字典的收缩 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
1.3.11 字典其他操作 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
1.3.12 字典的迭代 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
1.3.13 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
1.4 跳跃表 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
1.4.1 跳跃表的实现 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
1.4.2 跳跃表的应用 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
1.4.3 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2 第二部分：内存映射数据结构 37
2.1 整数集合 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.1.1 整数集合的应用 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.1.2 数据结构和主要操作 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.1.3 intset 运行实例 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.1.4 升级 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.1.5 关于升级 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
i
2.1.6 关于元素移动 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.1.7 其他操作 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.1.8 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
2.2 压缩列表 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
2.2.1 ziplist 的构成 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
2.2.2 节点的构成 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.2.3 创建新 ziplist . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
2.2.4 将节点添加到末端 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
2.2.5 将节点添加到某个/某些节点的前面 . . . . . . . . . . . . . . . . . . . . . 52
2.2.6 删除节点 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
2.2.7 遍历 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
2.2.8 查找元素、根据值定位节点 . . . . . . . . . . . . . . . . . . . . . . . . . 54
2.2.9 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
3 第三部分：Redis 数据类型 57
3.1 对象处理机制 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
3.1.1 redisObject 数据结构，以及 Redis 的数据类型 . . . . . . . . . . . . . . 58
3.1.2 命令的类型检查和多态 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
3.1.3 对象共享 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
3.1.4 引用计数以及对象的销毁 . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
3.1.5 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
3.2 字符串 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
3.2.1 字符串编码 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
3.2.2 编码的选择 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
3.2.3 字符串命令的实现 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
3.3 哈希表 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
3.3.1 字典编码的哈希表 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
3.3.2 压缩列表编码的哈希表 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
3.3.3 编码的选择 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
3.3.4 哈希命令的实现 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
3.4 列表 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
3.4.1 编码的选择 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
3.4.2 列表命令的实现 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
3.4.3 阻塞的条件 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
3.4.4 阻塞 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
3.4.5 阻塞因 LPUSH 、RPUSH 、LINSERT 等添加命令而被取消 . . . . . . . 69
3.4.6 先阻塞先服务（FBFS）策略 . . . . . . . . . . . . . . . . . . . . . . . . . 72
3.4.7 阻塞因超过最大等待时间而被取消 . . . . . . . . . . . . . . . . . . . . . 73
3.5 集合 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
3.5.1 编码的选择 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
3.5.2 编码的切换 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
3.5.3 字典编码的集合 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
3.5.4 集合命令的实现 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
3.5.5 求交集算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
3.5.6 求并集算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
3.5.7 求差集算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
3.6 有序集 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
3.6.1 编码的选择 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
3.6.2 编码的转换 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
3.6.3 ZIPLIST 编码的有序集 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
3.6.4 SKIPLIST 编码的有序集 . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
ii
4 第四部分：功能的实现 81
4.1 事务 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
4.1.1 事务 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
4.1.2 开始事务 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
4.1.3 命令入队 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
4.1.4 执行事务 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
4.1.5 在事务和非事务状态下执行命令 . . . . . . . . . . . . . . . . . . . . . . . 86
4.1.6 事务状态下的 DISCARD 、MULTI 和 WATCH 命令 . . . . . . . . . . . 86
4.1.7 带 WATCH 的事务 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
4.1.8 WATCH 命令的实现 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
4.1.9 WATCH 的触发 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
4.1.10 事务的 ACID 性质 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
4.1.11 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
4.2 订阅与发布 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
4.2.1 频道的订阅与信息发送 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
4.2.2 订阅频道 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
4.2.3 发送信息到频道 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
4.2.4 退订频道 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
4.2.5 模式的订阅与信息发送 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
4.2.6 订阅模式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
4.2.7 发送信息到模式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
4.2.8 退订模式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
4.2.9 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
4.3 Lua 脚本 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
4.3.1 初始化 Lua 环境 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
4.3.2 脚本的安全性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
4.3.3 脚本的执行 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
4.3.4 EVAL 命令的实现 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
4.3.5 EVALSHA 命令的实现 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
4.3.6 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
4.4 慢查询日志 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
4.4.1 相关数据结构 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
4.4.2 慢查询日志的记录 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
4.4.3 慢查询日志的操作 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
4.4.4 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
5 第五部分：内部运作机制 109
5.1 数据库 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
5.1.1 数据库的结构 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
5.1.2 数据库的切换 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
5.1.3 数据库键空间 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
5.1.4 键空间的操作 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
5.1.5 键的过期时间 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
5.1.6 过期时间的保存 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
5.1.7 设置生存时间 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
5.1.8 过期键的判定 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
5.1.9 过期键的清除 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
5.1.10 过期键的惰性删除策略 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
5.1.11 过期键的定期删除策略 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
5.1.12 过期键对 AOF 、RDB 和复制的影响 . . . . . . . . . . . . . . . . . . . . 122
5.1.13 数据库空间的收缩和扩展 . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
iii
5.1.14 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
5.2 RDB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
5.2.1 保存 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
5.2.2 SAVE 、BGSAVE 、AOF 写入和 BGREWRITEAOF . . . . . . . . . . 126
5.2.3 载入 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
5.2.4 RDB 文件结构 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
5.2.5 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
5.3 AOF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
5.3.1 AOF 命令同步 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
5.3.2 命令传播 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
5.3.3 缓存追加 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
5.3.4 文件写入和保存 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
5.3.5 AOF 保存模式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
5.3.6 AOF 保存模式对性能和安全性的影响 . . . . . . . . . . . . . . . . . . . . 138
5.3.7 AOF 文件的读取和数据还原 . . . . . . . . . . . . . . . . . . . . . . . . . 139
5.3.8 AOF 重写 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
5.3.9 AOF 重写的实现 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
5.3.10 AOF 后台重写 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
5.3.11 AOF 后台重写的触发条件 . . . . . . . . . . . . . . . . . . . . . . . . . . 144
5.3.12 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
5.4 事件 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
5.4.1 文件事件 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
5.4.2 时间事件 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
5.4.3 时间事件应用实例：服务器常规操作 . . . . . . . . . . . . . . . . . . . . 150
5.4.4 事件的执行与调度 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
5.4.5 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
5.5 服务器与客户端 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
5.5.1 初始化服务器 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
5.5.2 客户端连接到服务器 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
5.5.3 命令的请求、处理和结果返回 . . . . . . . . . . . . . . . . . . . . . . . . 158
5.5.4 命令请求实例：SET 的执行过程 . . . . . . . . . . . . . . . . . . . . . . 158
5.5.5 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
6 关于 161
7 通过捐款支持本书 163