《Redis设计与实现》知识点目录

Redis设计与实现

第一部分 数据结构与对象

第二章 简单动态字符串

• p8 简单动态字符串SDS

2.1 SDS的定义

• p9 每个sds.h/sdshdr结构表示一个SDS值

2.2 SDS与C字符串的区别

• p10 常数复杂度获取字符串长度
  • p10 获取一个SDS长度的复杂度仅为O(1)
• p11 杜绝缓冲区溢出
  • p11 SDS修改操作
• p12 减少修改字符串带来的内存重分配次数
  • p13 空间预分配
  • p14 惰性空间释放
• p15 二进制安全
  • p16 SDS的二进制安全
• p16 兼容部分C字符串函数
  • p17 SDS可以在有需要时重用<String.h>函数库
• p17 总结
  • p17 C字符串和SDS之间的区别

2.3 SDS API

• P17 SDS的主要操作API

2.4 重点回顾

• p18 SDS相比C字符串的优点

第三章 链表

3.1 链表和链表节点的实现

• p20 list结构
• p21 Redis链表的实现特性

3.2 链表和链表节点的API

• p21 用于操作链表和链表节点的API

3.3 重点回顾

第四章 字典

4.1 字典的实现

• p24 哈希表

  • p24 dictht结构

• p25 哈希表节点

  • p25 dictEntry结构

• p26 字典

  • p26 dic结构

4.2 哈希算法

• p27 Redis计算哈希值和索引值的方法
• p28 Redis使用MurmurHash2算法计算键的哈希值

4.3 解决键冲突

• p28 Redis的哈希表使用链地址法解决键冲突

4.4 rehash

• p29 Redis对字典的哈希表执行rehash的步骤如下
• p32 哈希表的扩展与收缩
  • p32 负载因子

4.5 渐进式rehash

• p33 渐进式rehash详细步骤
• p36 渐进式rehash执行期间的哈希表操作

4.6 字典API

• p36 字典的主要操作API

第五章 跳跃表

• p38 跳跃表

5.1 跳跃表的实现

• p39 跳跃表由zskiplistNode和zskiplist两个结构定义

• p39 zskiplist结构

• p40 跳跃表节点

  • p40 zskiplistNode结构
    • p40 层
    • p40 前进指针
    • p41 跨度
    • p42 后退指针
    • p42 分值和成员
  • p43 跳跃表

5.2 跳跃表API

• p44 跳跃表的所有操作API

第六章 整数集合

6.1 整数集合的实现

• p47 contents数组（整数集合底层实现）的真正类型取决于encoding的值

6.2 升级

• p48 升级整数集合并添加新元素的三步骤
• p50 升级之后新元素的摆放位置

6.3 升级的好处

• p50 提升灵活性
• p50 节约内存

6.4 降级

6.5 整数集合API

• p51 整数集合的操作API

第七章 压缩链表

• p52 压缩链表概念

7.1 压缩链表的构成

• p53 压缩链表组成部分详细说明

7.2 压缩链表节点的构成

• p54 previous_entry_length
• p55 压缩链表从表尾节点向表头结点进行遍历的完整过程
• p55 encoding
• p56 content

7.3 连锁更新

• p58 连锁更新

7.4 压缩链表API

• p59 压缩链表API

第八章 对象

8.1 对象的类型与编码

• p61 redisObject结构
• p61 类型
  • p61 对象的类型
  • p61 TYPE命令
• p62 编码和底层实现
  • p62 encoding属性记录了对象所使用的编码
  • p62 每种类型的对象可以使用的编码
  • p63 OBJECT ENCODING命令

8.2 字符串对象

• p64 字符串对象的编码可以是int、raw或者embstr
• p65 embstr编码的字符串对象来保存短字符串值的好处
• p66 字符串对象保存各类型值得编码方式
• p66 编码的转换
• p67 字符串命令的实现

8.3 列表对象

• p68 列表对象的编码可以是ziplist或者Linkedlist
• p70 编码转换
  • p70 列表对象使用ziplist编码的两个条件

8.4 哈希对象

• p71 哈希对象的编码可以是ziplist或者hashtable
• p73 编码转换
  • p73 哈希对象使用ziplist编码的两个条件
• p74 哈希命令的实现

8.5 集合对象

• p75 集合对象的编码可以是intset或者hashtable
• p75 编码的转换
  • p75 集合对象使用intset编码的两个条件
• p76 集合命令的实现

8.6 有序集合对象

• p77 有序集合对象的编码可以是ziplist或者skiplist
• p78 为什么有序集合需要同时使用跳跃表和字典来实现
• p79 编码的转换
  • p79 有序集合对象使用ziplist编码的两个条件
• p80 有序集合命令的实现

8.7 类型检查与命令多态

• p82 类型检查的实现
  • p83 类型检查过程
• p83 多态命令的实现
  • p83 一些命令是多态的

8.8 内存回收

• p84 Redis使用引用计数法实现内存回收机制
• p84 引用计数规则

8.9 对象共享

• p85 让多个键共享同一个值对象需要执行两个步骤
• p86 Redis在初始化服务器时创建了一万个字符串对象，包含0到9999的所有整数值，并将它们作为共享对象
• p86 OBJECT REFCOUNT命令
• p87 为什么Redis不共享包含字符串的对象

8.10 对象的空转时长

• p87 OBJECT IDLETIME命令

第二部分 单机数据库的实现

第九章 数据库

9.1 服务器中的数据库

• p90 redisServer结构和redisDb结构

9.2 切换数据库

• p91 SELECT命令
• p92 SELECT命令实现原理

9.3 数据库键空间

• p93 键空间
• p94 添加新键
• p95 删除键
• p95 更新键
• p97 对键取值
• p98 其他键空间操作
• p98 读写键空间时的维护操作
  • p98 服务器会记录键空间命中次数或键空间不命中次数
  • p98 键的LRU时间
  • p99 脏键标记

9.4 设置键的生存时间或过期时间

• p99 EXPIRE命令和PEXPIRE命令
• p99 EXPIREAT命令和PEXPIREAT命令
• p100 TTL命令和PTTL命令
• p100 设置过期时间
  • p101 设置生存时间和设置过期时间的命令之间的转换
• p101 保存过期时间
  • p101 过期字典
• p104 移除过期时间
  • p104 PERSIST命令
• p105 计算并返回剩余生存时间
  • p105 TTL命令和PTTL命令
• p106 过期键的判定

9.5 过期键删除策略

• p107 定时删除
• p108 惰性删除
• p108 定期删除

9.6 Redis的过期键删除策略

• p108 Redis服务器实际使用的是惰性删除和定期删除两种策略
• p109 惰性删除策略的实现
• p109 定期删除策略的实现

9.7 AOF、RDB和复制功能对过期键的处理

• p111 生成RDB文件

  • p111 已过期的键不会被保存到新创建的RDB文件中

• p111 载入RDB文件

• p112 AOF文件写入

• p112 AOF重写

• p112 复制

• p113 数据库通知

9.8 数据库通知

• p113 数据库通知
• p114 键空间通知和键事件通知
• p114 notify-keyspace-events选项决定了服务器所发送通知的类型
• p115 发送通知
  • p115 notifyKeyspaceEvent函数实现了发送数据库通知的功能
• p116 发送通知的实现

第十章 RDB持久化

• p118 数据库状态

10.1 RDB文件的创建与载入

• p119 SAVE命令和BGSAVE命令
• p120 AOF文件的更新频率通常比RDB文件的更新频率高
• p120 SAVE命令执行时的服务器状态
  • p120 SAVE命令执行时，Redis服务器将被阻塞
• p120 BGSAVE命令执行时候的服务器状态
  • p121 BGSAVE命令执行期间，服务器处理SAVE、BGSAVE、BGREWRITEAOF三个命令的方式会发生变化
• p121 RDB文件载入时的服务器状态
  • p121服务器在载入RDB文件期间，会一直处于阻塞状态，直到载入工作完成

10.2 自动间隔性保存

• p121 save选项
• p122 设置保存条件
  • p122 save选项默认条件
• p123 dirty计数器和lastsave属性
• p124 设置保存条件是否满足
  • p124 服务器周期性操作函数serverCron

10.3 RDB文件结构

• p125 RDB文件结构

• p126 check_sum校验和

• p126 databases部分

  • p126 RDB文件中的数据库结构

• p127 key_value_pairs部分

  • p127 不带过期时间的键值对结构
  • p128 带有过期时间的键值对结构

• p128 value的编码

10.4 分析RDB文件

• p133 od命令可以分析RDB文件
• p133 不包含任何键值对的RDB文件
• p134 包含字符串键的RDB文件
• p135 包含带有过期时间的字符串键的RDB文件
• p135 包含一个集合键的RDB文件
• p136 关于分析RDB文件的说明

第十一章 AOF持久化

11.1 AOF持久化的实现

• p139 命令追加
• p140 AOF文件的写入与同步
  • p140 Redis的服务器进程是一个事件循环
  • p140 appendfsync选项
  • p141 文件的写入和同步

11.2 AOF的载入与数据还原

• p142 Redis读取AOF文件并还原数据库的详细步骤

11.3 AOF重写

• p143 AOF重写
• p143 AOF文件重写的实现
  • p144 AOF重写功能的实现原理
  • p147 元素数量超过一个参数时，重写程序使用多条命令来记录键的值
• p147 AOF后台重写
  • p148 AOF重写缓冲区

第十二章 事件

• p151 文件事件和时间事件

12.1 文件事件

• p151 文件事件处理器
• p152 文件事件处理器的构成
• p152 I/O多路复用程序的实现
  • p152 Redis的I/O多路复用程序的所有功能都是通过包装常见的I/O多路复用函数库来实现的
• p153 事件的类型
  • p153 READABLE事件和WRITABLE事件
• p153 API
• p154 文件时间的处理器
  • p154 连接应答处理器
  • p155 命令请求处理器
  • p155 命令回复处理器
  • p155 一次完整的客户端与服务器连接事件示例

12.2 时间事件

• p156 定时事件和周期性事件
• p157 时间事件的实现
• p157 API
• p159 时间事件应用实例：serverCron函数

12.3 事件的调度与执行

• p160 事件处理角度下的服务器运行流程

第十三章 客户端

• p162 redisClient结构-客户端状态
• p163 clients链表

13.1 客户端属性

• p163 套接字描述符
• p164 名字
• p165 标志
  • p166 PUBSUB命令和SCRIPT LOAD命令的特殊性
• p167 输入缓冲区
• p168 命令与命令参数
• p169 命令的实现函数
  • p169 命令表
• p169 输出缓冲区
• p171 身份验证
• p171 时间
  • p172 客户端空转时间

13.2 客户端的创建与关闭

• p172 创建普通客户端
• p173 关闭普通客户端
  • p173 普通客户端关闭的原因
  • p173 两种限制客户端输出缓冲区大小的方式
• p174 Lua脚本的伪客户端
• p174 AOF文件的伪客户端

第十四章

14.1 命令请求的执行过程

• p177 发送命令请求
• p177 读取命令请求
• p178 命令执行器（1）：查找命令实现
  • p178 redisCommand结构的主要属性
  • p179 slags属性的标识
  • p181 命令名字的大小写不影响命令表的查找结果
• p181 命令执行器（2）：执行预备操作
• p182 命令执行器（3）：调用命令的实现函数
• p183 命令执行器（4）：执行后续工作
• p184 将命令回复发送给客户端
• p184 客户端接收并打印命令回复

14.2 serverCron函数

• p184 更新服务器时间缓存
• p185 更新LRU时钟
• p186 更新服务器每秒执行命令次数
• p187 更新服务器内存峰值记录
• p188 处理SIGTERM信号
• p189 管理客户端资源
• p189 管理数据库资源
• p189 执行被延迟的BGREWRITEAOF
• p190 检查持久化操作的运行状态
• p191 将AOF缓冲区中的内容写入AOF
• p191 关闭异步客户端
• p191 增加cronloops计数器的值

14.3 初始化服务器

• p192 初始化服务器状态结构
  • p193 initServerConfig函数
• p193 载入配置选项
• p194 初始化服务器数据结构
  • p194 initServer函数
  • p195 共享对象
• p195 还原数据库状态
• p196 执行事件循环

第三部分 多机数据库的实现

第十五章 复制

15.1 旧版复制功能的实现

• p199 SYNC命令执行步骤
• p200 命令传播

15.2 旧版复制功能的缺陷

• p201 初次复制和断线后重复制
• p203 SYNC命令是一个非常耗费资源的操作

15.3 新版复制功能的实现

• p203 完整重同步和部分重同步

15.4 部分重同步的实现

• p205 复制偏移量

• p206 复制积压缓冲区

  • p206 固定长度先进先出队列
  • p209 根据需要调整复制积压缓冲区大小

• p208 服务器运行ID

15.5 PSYNC命令的实现

• p209 PSYNC命令的两种调用方法
• p209 接收到PSYNC命令的主服务器向从服务器返回的三种回复

15.6 复制的实现

• p211 步骤1：设置主服务器的地址和端口
• p212 步骤2：建立套接字连接
• p212 步骤3：发送PING命令
• p213 步骤4：身份验证
• p214 步骤5：发送端口信息
• p215 步骤6：同步
• p216 步骤7：命令传播

15.7 心跳检测

• p216 发送REPLCONF ACK命令对于主从服务器有三个作用
• p216 检测主从服务器的网络连接状态
• p217 辅助实现min-slaves配置选项
• p127 检测命令丢失
  • p218 Redis2.8版本以前的命令丢失

第十六章 Sentinel

• p219 Sentinel
• p220 故障转移操作

16.1 启动并初始化Sentinel

• p220 启动一个Sentinel可以使用命令redis-sentinel
• p221 当一个Sentinel启动时，它需要以下步骤
• p221 初始化服务器
• p221 Sentinel模式下Redis服务器主要功能的使用情况
• p222 使用Sentinel专用代码
• p222 初始化Sentinel状态
• p223 初始化Sentinel状态的master属性
  • p223 每个sentinelRedisInstence结构代表一个被监视的Redis服务器实例
• p226 创建连向主服务器的网络连接
  • p226 Sentinel会创建两个连向主服务器的异步网络连接

16.2 获取主服务器信息

• p227 主服务器INFO命令回复

16.3 获取从服务器信息

• p229 从服务器INFO命令回复

16.4 向主服务器和从服务器发送信息

• p230 信息中和Sentinel有关的参数
• p231 信息中和主服务器有关的参数

16.5 接收来自主服务器和从服务器的频道信息

• p232 更新sentinels字典
• p234 创建连向其他Sentinel的命令连接
  • p234 Sentinel之间不会创建订阅连接

16.6 检测主观下线状态

• p235 down-after-milliseconds选项
• p235 主观下线时长选项的作用范围
• p236 多个Sentinel设置的主观下线时长可能不同

16.7 检查客观下线状态

• p236 发送SENTINEL is-master-down-by-addr命令
• p237 接收SENTINEL is-master-down-by-addr命令
• p237 接收SENTINEL is-master-down-by-addr命令的回复
  • p238 客观下线状态的判断条件

16.8 选举领头Sentinel

• 当一个主服务器被判断为客观下线时进行选举

16.9 故障转移

• p240 故障转移的三个步骤
• p241 选出新的主服务器
  • p241 新的主服务器是怎样挑选出来的
• p242 修改从服务器的复制目标
• p243 将旧的主服务器变为从服务器

第十七章 集群

17.1 节点

• p245 CLUSTER MEET命令
• p247 启动节点
• p247 集群数据结构
  • p247 clusterNode结构
  • p248 clusterLink结构
  • p249 clusterState结构
• p250 CLUSLTER MEET命令的实现

17.2 槽指派

• p253 记录节点的槽指派信息
• p254 传播节点的槽指派信息
• p255 记录集群所有槽的指派信息
• p257 CLUSTER ADDSLOTS命令的实现

17.3 在集群中的执行命令

• p260 计算键属于哪个槽
• p260 判断槽是否由当前节点负责处理
• p261 MOVED错误
• p261 节点数据库的实现
  • p261 slots_to_key跳跃表

17.4 重新分片

• p266 重新分片的实现原理

17.5 ASK错误

• p268 CLUSTER SETSLOT IMPORTING命令的实现
• p269 CLUSTER SETSLOT MIGRATING命令的实现
• p270 ASK错误
• p271 ASKING命令
• p273 ASK错误和MOVED错误的区别

17.6 复制与故障转移

• p275 设置从节点
• p278 故障检测
• p280 故障转移
• p280 选举新的主节点

17.7 消息

• p282 消息头
• p284 MEET、PING、PONG消息的实现
  • p284 Gossip协议
• p285 FAIL消息的实现
• p286 PUBLISH消息的实现

第四部分 独立功能的实现

第十八章 发布与订阅

• p290 SUBSCRIBE命令
• p290 PSUBSCRIBE命令

18.1 频道的订阅与退订

• p292 pubsub_channels字典
• p293 订阅频道
• p294 退订频道

18.2 模式的订阅与退订

• p296 订阅模式
• p297 退订模式

18.3 发送消息

• p298 将消息发送给频道订阅者
• p299 将消息发送给模式订阅者

18.4 查看订阅信息

• p301 PUBSUB CHANNELS
• p301 PUBSUB NUMSUB
• p303 PUBSUB NUMPAT

第十九章 事务

19.1 事务的实现

• p306 事务开始
  • p306 MULTI命令
• p306 命令入队
• p307 事务队列
  • p307 mstate属性
• p309 执行事务
  • p309 EXEC命令

19.2 WATCH命令的实现

• p311 使用WATCH命令监视数据库键
• p312 监视机制的触发
• p313 判断事务是否安全
• p313 一个完整的WATCH事务执行过程

19.3 事务的ACID性质

• p314 原子性
• p315 一致性
  • p316 入队错误
  • p317 执行错误
  • p317 服务器停机
• p318 隔离性
• p318 耐久性
  • p319 no-appendfsync-on-rewrite配置选项对耐久性的影响

第二十章 Lua脚本

第二十一章 排序

• p344 ALPHA选项

21.1 SORT<key>命令的实现

• p346 服务器执行SORT numbers命令的详细步骤

21.2 ALPHA选项的实现

• p348 服务器执行SORT fruits ALPHA命令的详细步骤

21.3 ASC选项和DESC选项的实现

21.4 BY选项的实现

• p350 服务器执行SORT fruits BY \*-price命令的详细步骤

21.5 带有ALPHA选项的BY选项的实现

• p352 服务器执行SORT fruits BY \*-id ALPHA命令的详细步骤

21.6 LIMIT选项的实现

• p354 服务器执行SORT alphabet ALPHA LIMIT 0 4命令的详细步骤

21.7 GET选项的实现

• p356 服务器执行SORT studenst ALPHA GET \*-name命令的详细步骤

21.8 STORE选项的实现

• p359 服务器执行SORT students ALPHA GET \*-name命令的详细步骤

21.9 多个选项的执行顺序

• p359 选项的的执行顺序
  • p259 一个SORT命令的执行过程可以分为以下四步

第二十二章 二进制位数组

• p362 Redis提供了SETBIT、GETBIT、BITCOUNT、BITOP四个命令用于处理二进制位数组

22.1 位数组的表示

• p363 Redis使用字符串对象来表示位数组

22.2 GETBIT命令的实现

22.3 SETBIT命令的实现

• p367 SETBIT命令的执行示例
• p367 带扩展操作的SETBIT命令示例

22.4 BITCOUNT命令的实现

• p370 二进制位统计算法（1）：遍历算法
• p370 二进制位统计算法（2）：查表算法
• p371 二进制位统计算法（3）：variable-precision SWAR算法
  • p372 计算汉明重量
• p374 二进制位统计算法（4）：Redis的实现

22.5 BITOP命令的实现

第二十三章 慢查询日志

• p379 SLOWLOG GET命令

23.1 慢查询记录的保存

23.2 慢查询日志的阅览和删除

23.3 添加新日志

第二十四章 监视器

24.1 成为监视器

24.2 向监视器发送命令信息