《Redis设计与实现》简读

一、数据结构与对象

简单动态字符串（SDS）

• 相比C字符串增加记录字符串长度的，获取字符串长度复杂度为O(1)
• 相比C字符串增加记录已分配内存空间，可以避免缓冲区溢出
• 空间预分配和空间惰性释放
• 二进制安全，不是以空字符（\0）来判断字符串是否结束
• 遵循C字符串以空字符结尾的惯例，可以兼容部分C字符串函数

关于空间预分配和空间惰性释放

• 字符串增长操作时，如果修改后长度小于1M则分配该字符串长度2倍的内存空间，如果修改后长度大于等于1M则分配该字符串长度+1M的内存空间。（预分配，避免每次增长操作都需要进行内存重分配执行系统调用）
• 字符串缩短操作时，程序不会立即释放缩短后多出来的字节，而是在需要时再释放。（惰性释放，避免以后需要增长操作时重分配内存，会在较短的时间内造成内存浪费，文中未提及何时是“需要时”）

最佳实践：因为对字符串的增长或缩短操作都有可能需要执行内存重分配，所以修改相同键使用SDS类型保存的值时保持修改前后长度一致。

链表

• 双端，获取某节点前后置节点对复杂度为O(1)
• 无环，表头prev指针和表尾next指针都指向NULL
• 记录表头尾节点，获取表头尾节点的复杂度为O(1)
• 记录链表长度，获取链表长度复杂度为O(1)
• 空指针保存值，可以保存各种不同类型的值

字典

• 使用链地址法解决冲突，当多个键被分配到相同哈希索引时将新键添加到节点链表表头
• 字典包含ht[0]和ht[1]（ht[1]仅为rehash时使用）两个哈希表，当哈希表保存的键值对数量太多或太少时使用重新散列（rehash）维持哈希表负载因子在合理范围之内
• rehash操作采用渐进式，分量将ht[0]中的键值对rehash到ht[1]，新键值对统一保存到ht[1]中

rehash步骤

1. 扩展操作（没有执行BGSAVE或BGREWRITEAOF且负载因子大于等于1；正在执行BGSAVE或BGREWRITEAOF且负载因子大于等于5），为ht[1]分配第一个大于等于当前包含键值对数量（ht[0].used）*2的<math><msubsup><mi>2</mi><mi></mi><mi>n</mi></msubsup></math>内存空间
2. 收缩操作（负载因子小于0.1时），为ht[1]分配第一个大于等于当前包含键值对数量的<math><msubsup><mi>2</mi><mi></mi><mi>n</mi></msubsup></math>内存空间
3. 将保存在ht[0]中的所有键值对rehash到ht[1]
4. 释放ht[0]，将ht[1]设置为ht[0]，创建新的空白哈希表ht[1]

负载因子＝哈希表已保存节点数量／哈希表大小

Redis使用MurmurHash2算法来计算键的哈希值

跳跃表

• 有序集合的底层实现之一
• 每个节点可以保存一个字节数组或整数值
• 链表中的节点按照分值大小排序，分值相同时按对象大小排序

整数集合

• 可以保存int16_t（-32768至32767）、int32_t（-2147483648至2147483647）、int64_t（-9223372036854775808至9223372036854775807）三种类型的整数集
• 为节约内存，集合类型使用最小类型保存整数，仅当新添加的整数大于当前所能容纳的值范围时进行升级操作
• 因为每次添加新元素都有可能引起升级，所以添加新元素的时间复杂度为O(N)
• 不支持降级操作

升级步骤

1. 根据新元素的类型扩展底层数组空间，并为新元素分配空间
2. 转换现有元素至新的类型，保持有序性放置元素
3. 添加新元素，当新元素小于所有先有元素时放置在索引0，当新元素大于所有先有元素师放置在索引length-1

最佳实践：为了避免添加新元素时产生升级操作，应向同一整数集合添加相同类型的整数

压缩列表

• 作为列表键和哈希键的底层实现之一
• 添加或删除节点都可能造成连锁更新，连锁更新最坏时间复杂度为O(<math><msubsup><mi>N</mi><mi></mi><mi>2</mi></msubsup></math>)

对象

• 字符串对象（REDIS_STRING即string）
• 列表对象（REDIS_LIST即list）
• 哈希对象（REDIS_HASH即hash）
• 集合对象（REDIS_SET即set）
• 有序集合对象（REDIS_ZSET即zset）

<div align=center>不同类型和编码的对象</div>

类型	编码	对象
REDIS_STRING	REDIS_ENCODING_INT（整数值）	使用整数值实现的字符串对象
REDIS_STRING	REDIS_ENCODING_EMBSTR（小于32字节字符串）	使用embstr编码的简单动态字符串实现的字符串对象
REDIS_STRING	REDIS_ENCODING_RAW（大于32字节字符串）	使用简单字动态字符串实现的字符串对象
REDIS_LIST	REDIS_ENCODING_ZIPLIST（默认配置下，所有元素长度小于64字节且元素数量小于513，查看命令：CONFIG GET list-max-ziplist*）	使用压缩列表实现的列表对象
REDIS_LIST	REDIS_ENCODING_LINKEDLIST	使用双端链表实现的列表对象
REDIS_HASH	REDIS_ENCODING_ZIPLIST （默认配置下，所有元素长度小于64字节且元素数量小于513，查看命令：CONFIG GET hash-max-ziplist*）	使用压缩列表实现的列表对象
REDIS_HASH	REDIS_ENCODING_HT	使用字典实现的哈希对象
REDIS_SET	REDIS_ENCODING_INTSET（默认配置下，所有元素都是整数值且元素数量小于513，查看命令：CONFIG GET set-max-intset-entries）	使用整数集合实现的集合对象
REDIS_SET	REDIS_ENCODING_HT	使用字典实现的集合对象
REDIS_ZSET	REDIS_ENCODING_ZIPLIST（默认配置下，所有元素长度小于64字节且元素数量小于128，查看命令：CONFIG GET zset-max-ziplist*）	使用压缩列表实现的有序集合对象
REDIS_ZSET	REDIS_ENCODING_SKIPLIST	使用跳跃链表和字典实现的有序集合对象

备注

1. TYPE KEY（获取键的对应值对象类型）
2. OBJECT ENCODING KEY（获取键的对应值对象编码）

内存回收、对象共享、空转时长度

• 每个对象都有引用计数器，当引用计数为0时对象所占用的内存将被释放
• Redis初始化服务时自动创建0-9999的字符串对象（包括数据结构中嵌套了字符串对象的：linkedlist的列表对象、hashtable的哈希对象、hashtable的集合对象、zset的有序集合对象），值在对应范围内的字符串对象将共享同一对象
• 每个对象记录有最后一次被命令程序访问的时间，当maxmemory且回收内存算法为volatile-lru或allkeys-lru时内存一旦超过maxmemory上限则优先释放空转时长较高的键值对

最佳实践：为了最大程度的节省内存，应将简单字符或重复率较高的字符串对应成0-9999范围内的数字。

二、单机数据库的实现

数据库

• Redis有多个数据库，默认值为16（查看命令：CONFIG GET databases）
• 过期键有惰性删除和定期删除两种策略
• 从服务器不会自主删除过期键

惰性删除：当读取的键是一个过期键时才会将该键删除并返回空。

定期删除：在规定的时间内分多次遍历每个数据库，从expires字典中随机检查一部分键的过期时间（也即每次执行定期删除并不一定能把所有的过期键都删除）。

最佳实践：主从模式下从服务器在读取到过期键时不会主动删除且会当成正常键返回数据，当数据中包含较多的过期键时主服务器的定期删除策略可能需要较长时间才能将该过期键删除，因此Redis的主从模式不同于Mysql的主从模式（主写从读），如果使用类似Mysql主从的用法时需注意过期数据在一定时间内可能是脏数据。

RDB持久化

• RDB文件用于保存和还原Redis服务器所有数据库中的数据
• SAVE由服务器进程执行，因此会阻塞服务器
• BGSAVE由子进程执行，因此不会阻塞服务器
• RDB是一个经过压缩的二进制文件

AOF持久化

• AOF文件通过保存所有修改数据库的写命令请求来记录服务器的数据库状态
• AOF文件中所有命令均以Redis命令请求协议保存
• 命令请求会先保存到AOF缓冲区中，再定期保存到AOF文件
• AOF重写通过读取数据库中的键值对来重新产生一个AOF文件，该文件减少了很多不再需要的命令因此文件体积更小

事件

• Redis是由时间事件和文件事件组成的事件驱动程序
• 文件事件处理器是基于Reactor模式实现的网络通信程序，事件分为读事件、写事件
• 时间事件分为定时事件、周期事件
• serverCron是一个周期性事件，它是Redis周期性事件的主要函数
• 因为事件处理在时间事件和文件事件中轮训，且不会抢占，时间事件不一定在设定的时间立即执行

客户端

• 客户端发送的请求记录在服务端的输入缓冲区，该缓冲区大小为1G。
• 服务端的输出缓冲区分固定缓冲区（16KB）和可变缓冲区（查看命令：CONFIG GET client-output-buffer-limit）。
• Redis默认最大连接数为10000（查看命令：CONFIG GET maxclients）
• 网络连接关闭、发送不合协议格式的命令请求、CLIENT KILL、空转时间超时、输入、输出缓冲区大小超过限制时，客户端将被关闭。
• 客户端的空转时间超过timeout设置的值时将被关闭（查看命令：CONFIG GET timeout）。

• 可变输出缓冲区分普通客户端、pubsub（发布／订阅模式）、slave三种客户端限制。默认情况下，普通客户端无限制（阻塞式的消息应答模式通常不会造成输出缓冲区堆积），pubsub客户端超过32m或持续60s超高8m，slave客户端超高256m或持续60s超过64m，对于超过限制的客户端Redis将关闭连接。
• 最大连接数受系统当前文件描述符数量限制，最大只能取文件描述符数量限制－32（Redis最多会占用32个文件描述符）。
• 如果客户端是主服务器、从服务器、被BLPOP等命令阻塞、正在执行SUBSCRIBE等订阅命令，将不受timeout设置影响。

服务器

• serverCron函数默认每100毫秒执行一次，主要包括更新服务器状态信息、处理服务接收的SIGTERM信号、管理客户端资源和数据库状态、检查执行持久化等。

命令请求步骤

1. 客户端将命令请求发送给服务器
2. 服务器读取命令请求并解析出命令参数
3. 命令执行器根据参数查找命令的实现函数，执行实现函数并得出命令回复
4. 服务器将命令回复返回给客户端

服务器启动步骤

1. 初始化服务器状态
2. 载入服务器配置
3. 初始化服务器数据结构
4. 还原数据库状态
5. 执行事件循环

三、多机数据库的的实现

复制

• Reids 2.8以前没有部分重同步功能，命令丢失无法检测，断线后需要重新执行一次完整同步
• 部分重同步通过复制偏移量、复制挤压缓冲区、服务器运行ID三部分实现
• 从服务器默认以1s一次的频率向主服务器发送REPLCONF ACK <replication_offset>(从服务器当前复制偏移量) 以完成心跳检测、命令丢失检测

Sentinel（哨兵）

• Sentinel是运行在特殊模式下的Redis服务器，使用不同的命令表
• Sentinel向被监视的主服务器以及其属下的从服务器创建命令连接和订阅连接，命令连接用于向主服务器发送命令，订阅连接用于接收__sentinel__:hello频道的订阅信息（感知其他Sentinel的存在）
• 监视同一主服务器的Sentinel感知到其他Sentinel的存在后相互建立命令连接，用于主服务器主观下线后相互询问是否同意主观下线，当收集够足够多票数（大于1/2）后判断为客观下线并进行故障转移

集群

• 集群的整个数据库（集群模式下只能使用一个数据库）被分为16384个槽，每个节点会记录指派给自己的槽以及哪些槽指派给了其他哪个节点
• 节点在收到命令请求时先检查所需处理的键是否位于自己的槽中，不是则返回MOVED错误引导客户端跳转正确节点
• 重新分片工作由redis-trib负责，用于将已指派的槽从源节点转移到目标节点
• 重新分片过程中如果客户端请求一个已经转移到新节点的键则返回ASK错误引导客户端跳转新节点
• 集群中的从节点用于复制主节点并在主节点下线后从中选举出新的主节点

MOVED错误表示所请求的键负责权已经转移到另一节点，ASK错误则只是槽正在转移时的一种临时性错误

四、独立功能的实现

发布与订阅

• 发布订阅分为频道发布订阅和模式发布订阅两种
• 服务器状态在pubsub_channels字典保存所有频道订阅关系，在pubsub_patterns链表保存所有模式订阅关系

事务

• 事务是提供了一种将多个命令打包然后一次性按先进先出顺序执行的机制，并不具备回滚功能
• 事务执行过程中不会中断，直到所有命令都被执行完之后才会结束事务
• 带有WATCH命令的事务可以监视某个键是否被修改，如果事务执行过程中被修改则客户端的REDIS_DIRTY_CAS标志将被打开，事务将被服务器拒绝提交

Lua脚本

• Redis内嵌Lua执行环境，并对环境中的函数进行一些修改以适应Redis，当需要执行Redis命令时使用伪客户端
• Redis使用脚本字典来保存所有执行或载入过的Lua脚本，脚本的SHA1校验和作为键名
• Lua脚本在执行前服务器会为其设置一个超时处理钩子，脚本运行超时时可以使用SCRIPT KILL来中止脚本或SHUTDOWN nosave关闭整个服务器

Redis创建Lua执行环境步骤

1. 创建基础Lua环境
2. 载入函数库到Lua环境中
3. 创建包含对Redis进行操作的函数的全局表格
4. 使用自制随机函数替代Lua原有带副作用的随机函数（自制随机函数具有以下特征：①对于相同seed，math.random总产生相同的随机数序列；②除非显示修改math.randomseed中的seed，否则均使用math.randomseed(0)初始化seed）
5. 创建排序辅助函数，Lua环境使用该函数对一部分Redis命令的结果进行排序
6. 创建可以提供更多详细错误信息的错误报告辅助函数redis.pcall
7. 保护Lua环境的全局变量，防止执行脚本过程中修改全局变量
8. 将修改完成后的Lua环境保存到服务器状态的Lua属性中

排序

• SORT命令由快速排序算法实现
• SORT命令通过将元素保存在数组中，再对数组进行排序

慢查询日志

• Redis默认记录执行超过10000us的命令（查看命令：CONFIG GET slowlog-log-slower-than）
• Redis默认保留128条慢查询日志，超过后旧的日志将被优先删除（查看命令：CONFIG GET slowlog-max-len）