【笔记】Redis 设计与实现

本文记录了《Redis 设计与实现》中比较重要的内容。

数据结构

字典

字典在 Redis 中应用广泛。例如，字典键的实现、数据库的底层实现。

Redis 采用 MurmurHash2 算法计算哈希键值，采用链地址法解决哈希冲突。

当 Redis 的负载因子达到一定的大小，会采用 rehash 操作。执行 rehash 的时机如下：

当前数据库没有执行 BGSAVE 或 SAVE 指令，并且负载因子大于 1。
当前数据库正在执行 BGSAVE 或 SAVE 指令，并且负载因子大于 5。

这样做的目的是减少写时拷贝过程中内存的修改大小，提升性能。

由于一次性对大量的键值对（千万级或者亿级）执行 rehash 操作会阻塞当前服务器线程，无法继续执行命令，Redis 采用了渐进式 rehash 方法完成 rehash 操作。具体步骤如下：

为 ht[1] 分配空间，让字典同时拥有 ht[0] 和 ht[1]。
初始化索引计数器 rehashidx 为 0，表示 rehash 正式开始。
每当执行查找、插入、删除操作时，顺带对 ht[0][rehashidx] 的所有元素执行 rehash 操作到 ht[1] 中，完成后，rehashidx++。
当所有的键值对迁移完毕后，回收 ht[0] 的内存空间，把 ht[1] 变为 ht[0]，同时新建一个 ht[1] 用于下一次的 rehash 过程。

在执行 rehash 的过程中，对字典的删除、查找、更新操作会同时在两个哈希表上进行。例如，要在字典中查找一个键，程序首先在 ht[0] 中查找，如果没找到则在 ht[1] 中查找。对字典的插入操作直接在 ht[1] 上执行。

跳跃表

跳跃表是一种有序的数据结构，性能和平衡树相差不大，并且实现简单。

Redis 使用 zskiplistNode 结构表示一个跳跃表节点，有以下几个成员：

层：层高是一个 1-32 的随机数。包含前进指针和跨度两个属性。前进指针指向当前层的下一个节点，跨度记录了两者之间的距离，用于计算目标节点排位。
后退指针：用于表尾到表头的遍历。
分值：每个节点按照分值由小到大排序。如果分值相同，按照对象大小排序。
成员：一个字符串对象。

为了便于处理整个跳跃表，Redis 使用 zskiplist 管理整个跳跃表，这个结构包含了指向头尾节点的指针 head 和 tail，通过这两个指针，程序访问头尾节点的时间复杂度是 O(1)。通过 length 保存整个跳跃表的长度，获取长度的时间复杂度是 O(1)。同理，通过 level 保存跳跃表的最大层级。

整数集合

当 SET 内容不多，并且都是整数时，Redis 使用整数集合作为底层实现。

整数集合的元素类型包括 int16_t, int32_t, int64_t。所有的数据按照顺序由小到大排列。当新插入的元素的长度超过了整数集合中所有元素的长度，那么需要对整数集合执行升级操作。这种做法保证了灵活性，同时节约了内存。

整数集合的升级包括了以下的步骤：

根据新元素的类型，分配合适的底层数组空间大小。
将原有的元素转换为和新元素相同的类型，并将类型转换后的数放置在正确的位置上，保证相对顺序不变。
将新元素放到指定的位置。

整数集合不支持降级操作。

压缩链表

压缩列表是哈希键和集合键的底层实现之一，当数据量不大，并且列表键的列表项或者哈希键的键值是整型或者短字符串，就会使用压缩链表作为底层实现。

压缩链表的节点有以下几个字段构成：previous_entry_length、encoding、content。

previous_entry_length：前一个字段的长度。如果小于 254 字节，那么这个字段只有一个字节；否则，该字段有五个字节，第一个字节的内容是 254，后面的字节存储长度。
encoding：内容的编码方式。
content：具体内容。

压缩链表存在的问题是连锁更新：插入新的内容导致前面 entry 的长度变化，会导致后面的 entry 需要更多的内存保存 previous_entry_length，造成后续字段长度都发生了变化。这样会造成内存的多次重新分配。

对象

Redis 一共有五种对象，分别为：字符串对象、列表对象、哈希对象、集合对象、有序集合对象。每种对象在不同的使用场景下有不同的底层编码方式，可以优化使用效率。

STRING 对象编码方式分为三种：int、embstr 和 raw。embstr 针对短字符串进行了优化，减少了内存分配和释放的次数，并且由于采用连续存储的方式，提升了缓存的命中率。

LIST 对象编码方式分为两种：ziplist 和 linkedlist。当所有项的大小小于 64 字节，并且列表长度小于 512，使用 ziplist 编码。

HASH 对象编码方式有两种：ziplist 和 hashtable。当键值对的所有键和值的大小小于 64 字节，并且对象长度小于 512，使用 ziplist 编码方式。

SET 对象编码方式有两种：intset 和 hashtable。当所有的值都是整数，并且对象长度小于 512，使用 intset 作为底层编码方式。

ZSET 对象编码方式有两种：ziplist 和 skiplist。当所有元素的长度都小于 64 字节，同时长度小于 128 时，使用 ziplist 作为底层编码方式。

skilplist 编码方式同时使用了哈希表和跳跃表，兼顾了精确查找和范围查找的效率。

Redis 通过引用计数的方式实现内存的自动回收。同时，通过引用计数也可以实现对象的复用。

单机数据库

键过期删除策略

Redis 把所有键的过期时间添加到一个过期字典中，检查过期字典就可以判断一个键是否过期。

过期删除策略分为三种：定时删除、惰性删除、定期删除。

定时删除创建一个定时器，当定时器过期时，立刻删除数据键。这种策略对内存最为友好，但是会对 CPU 造成更多的负担。
惰性删除每次访问键时检查键是否过期，如果过期就删除这个键。这种策略对 CPU 最为友好，但是会造成内存的浪费。
定期删除结合了二者的优点。

Redis 采用惰性删除和定期删除两种过期删除策略。

RDB 持久化

RDB 持久化通过保存当前 Redis 数据库状态实现持久化。RDB 有两种命令可以实现持久化操作：SAVE 和 BGSAVE。

SAVE 操作阻塞当前进程，直到持久化操作完成，服务器不会执行新的命令。
BGSAVE 操作创建一个子进程执行持久化操作，在这个期间，服务器依旧可以执客户端发送的命令。

写入 RDB 文件的过程中，服务器会检查每个键是否是过期的，只写入没有过期的键。在载入 RDB 文件的过程中，如果服务器是在主模式下运行，那么会检查键是否过期；否则会把 RDB 文件全部载入。

由于 AOF 文件的更新频率比 RDB 更新频率更高，如果服务器开启了 AOF 持久化的功能，首先使用 AOF 文件来还原数据库的状态，只有在关闭了 AOF 持久化功能的情况下，服务器才会采用 RDB 文件持久化。

可以对数据库设置 RDB 文件的自动保存条件。Redis 通过 dirty 计数器保存上一次执行 RDB 操作后数据库的修改次数，通过 lastsave 时间戳记录距离上一次 RDB 操作的事件。每 100ms 就会检查这两个值，如果达到了自动保存条件就会执行 RDB 持久化操作。

RDB 文件结构如下

每个数据库结构如下

不带过期时间的键值对结构如下

带过期时间的键值对结构如下

AOF 持久化

AOF 持久化通过保存 Redis 服务器的写命令实现保存数据库的状态，分为命令追加、文件写入、文件同步三个部分。

服务器在执行完一个写命令之后，会将被执行的写命令追加到服务器的 aof_buf 缓冲区的末尾，服务器通过定时操作定期把缓冲区的命令写入到 AOF 文件中。可以通过设置 appendfsync 选项的值控制 AOF 文件的刷新行为。

appendfsync 选项的值	AOF 刷新行为
always	将 aof_buf 缓冲区的所有内容写入，并同步到 AOF 文件中。
everysec	将 aof_buf 缓冲区的所有内容写入到 AOF 文件中，如果距离上次同步 AOF 文件的时间超过一秒，那么再次对 AOF 文件进行同步，并且同步过程由专门的线程负责。
no	将 aof_buf 缓冲区的所有内容写入，不对 AOF 文件同步，具体的同步时间由操作系统决定。

appendfsync 选项的值直接决定了 AOF 持久化功能的效率和安全性。

如果 appendfsync 设置为always，写入的速度是最慢的，但是安全性是最高的，出现故障时仅仅丢失一个事件循环中写入的数据。
如果 appendfsync 设置为everysec，这个模式足够快，并且出现故障时丢失的时最近一秒内写入的数据。
如果 appendfsync 设置为no，写入速度是最快的，但是每次同步需要消耗的时间是最多的。

AOF 的载入过程见下图：

为了避免 AOF 文件过大造成数据库恢复时间过长的问题，Redis 提供了 AOF 重写的功能。重写功能是通过读取当前数据库的状态实现的。重写操作会执行大量的写入操作，调用的进程会陷入长时间的阻塞状态，因此 Redis 使用一个单独的子进程执行 AOF 重写操作，这样做有两个目的：

在重写的过程中，父进程可以处理其他的请求
避免使用锁，同时可以保证数据的安全性。

在子进程重写的过程中，服务器可能会接收到新的写命令，造成 AOF 文件状态与当前数据库状态的不一致。为了解决这个问题，Redis 设置了一个 AOF 缓冲区。在 AOF 重写过程中，服务器将接收到的写命令保存到缓冲区中。当子进程的 AOF 重写操作完成后，把缓冲区的内容写入到新的 AOF 文件中。

事件

Redis 是一个事件驱动程序，事件类型分为文件事件和时间事件。

文件事件处理器基于 Reactor 模式开发，通过包装 I/O 多路复用函数实现。有两种类型的事件：

可读事件：客户端执行 write 操作、客户端执行 close 操作、客户端执行 connect 操作；
可写事件：客户端执行 read 操作。

时间事件有以下两种类型：

定时事件：让一段程序在指定的时间后执行一次；
周期性事件：让一段程序每隔一段时间执行一次。

所有时间事件存储在一个无序链表中，执行时遍历整个链表，处理所有已到达的时间事件。

原因：Redis 服务器只有一个周期性事件，使用链表不会影响性能。

客户端

Redis 使用一个链表保存所有建立连接的客户端，客户端结构体保存了客户端相关的属性。

输入缓冲区保存客户端输入的命令。这个缓冲区是可以动态扩展的，但是最大大小不能超过 1GB。

输出缓冲区保存服务端的响应，由固定大小缓冲区和可变大小缓冲区组成。

服务器

服务器接收到客户端发送的命令后，执行以下几个步骤：

读取命令请求，缓存在客户端结构体中；
执行命令，包含了以下四步：
- 查找命令实现
- 执行预备工作
- 调用命令的执行函数
- 执行后续工作。
将命令回复发送给客户端。

在执行预备工作的阶段，如果打开了 maxmemory 功能，那么先检查服务器的内存占用情况，必要时会执行内存回收的操作。

服务器每 100 毫秒执行一次 serverCron 函数。该函数主要的工作包括：更新服务器缓存、更新 LRU 时钟、检查持久化条件、执行被延迟的 BGREWRITEAOF 操作。

多机数据库

复制

复制分为两个步骤：同步和命令传播。

命令传播：主服务器会将写命令发送给从服务器。
同步：同步分为完全重同步和部分重同步：
- 完全重同步：适用于首次进行主从同步的情况。主服务器执行 BGSAVE 生成 RDB 文件，同时记录所有的写命令。把这些内容发送给从服务器，即可完成同步。
- 部分重同步：用于断线重连后主从复制，如果条件允许，主服务器将在连接断开后接收到的写命令发送给从服务器，从而解决了断线重连后完全重同步的低效问题。

部分重同步的实现依赖于三个机制：复制偏移量、复制积压缓冲区、服务器的运行 id。

复制偏移量用于确定主从服务器之间是否处于一致状态。如果主从服务器的复制偏移量相同，那么他们就处于一致状态；反之，他们就处于不一致状态。
复制积压缓冲区保存主服务器在命令传输阶段发送的写命令。当从服务器发送 PSYNC 命令时，如果复制积压缓冲区的内容包含所有缺失的数据，那么执行部分重同步操作；反之，执行完全重同步操作。
服务器的运行 id 用于确定从服务器复制的主服务器。当从服务保存的运行 id 和主服务器的运行 id 相同，那么主服务器可以尝试执行部分重同步操作；反之，主服务器需要使用完全重同步操作。

psync()的流程见下图。

从服务器通过心跳机制检测检查网络连接状态以及检测命令丢失情况。

Sentinel（哨兵机制）

由一个或者多个 Sentinel 实例组成的 Sentinel 系统可以监视任意多个主服务器，以及这些服务器下属的从服务器。如果被监视的主服务器下线，Sentinel 系统可以从下属的从服务器中选出一个服务器作为新的主服务器。Sentinel 保证了 Redis 系统的高可用性。

Sentinel 和每个服务器（主服务器和从服务器）建立了一条命令连接和一条订阅连接。完成后，Sentinel 每 10 秒发送一次 INFO 命令获取主服务器的当前信息，用于更新主服务器实例。在这个过程中，如果 Sentinel 系统发现了新的从服务器，会和这个从服务器之间建立一条命令连接和一条订阅连接，用于更新从服务器实例。

Sentinel 每 2 秒一次向主服务器和从服务器发送频道信息，并通过订阅连接接收频道消息，用于更新其他监视该服务器的 Sentinel 信息。当 Sentinel 发现了新的 Sentinel 后，会更新 sentinels 字典，并和该 Sentinel 建立一条命令连接（没有订阅连接）。

Sentinel 每 1 秒发送一次 PING 指令，持续回复无效命令超过一个固定的时间，Sentinel 判断主服务器已经下线（主观下线）。随后 Sentinel 会询问其他的 Sentinel 该服务器是否下线，如果足够多的 Sentinel 判断服务器已经处于主观下线状态，该服务器进入客观下线状态。

当一个主服务器处于客观下线状态后，监视该主服务器的 Sentinel 需要选举出一个领头 Sentinel，执行故障转移操作。选举流程采用 Raft 算法的一个实现，具体流程如下：

所有的 Sentinel 都有被选举为领头 Sentinel 的资格。
每个发现自己监听的主服务器处于客观下线状态的 Sentinel 都会要求其他的 Sentinel 设置自己为局部领头 Sentinel。
最先向目标 Sentinel 发送设置要求的源 Sentinel 会被设置为目标 Sentinel 的局部领头 Sentinel，其他的设置要求都会被忽略。（即先到先得）
如果某个 Sentinel 被半数以上的 Sentinel 选举为局部领头 Sentinel，这个 Sentinel 将成为领头 Sentinel。
如果在规定时间内没有选出领头 Sentinel，那么过一段时间后再次进行选举，直到选出领头 Sentinel 为止。
领头 Sentinel 负责故障转移操作，包括确定新的主服务器、修改从服务器的复制目标、将下线的主服务器设置为新主服务器的从服务器。

选举新主服务器步骤如下：

删除已经下线的从服务器（保证从服务器都是在线的）。
删除最近 5 秒内没有回复过领头 Sentinel 的 INFO 命令的从服务器（保证从服务器的网络状态良好）。
删除和主服务器断开连接超过 down-after-milliseconds*10 的从服务器（保证从服务器的数据内容都是尽可能新的）。
之后，领头 Sentinel 根据服务器的优先级排序，选出优先级最大的从服务器。如果有多个最高优先级的从服务器，选择复制偏移量最大的从服务器。如果有多个优先级最高、复制偏移量最大的从服务器，选择 ID 最小的从服务器。

集群

节点通过 CLUSTER MEET 命令连接。当节点 A 和节点 B 完成握手后，节点 A 通过 Gossip 协议扩散给所在集群的其他节点，告知节点 B 已经加入到集群中了。

Gossip 协议的执行过程如下：Gossip 过程是由种子节点发起，当一个种子节点有状态需要更新到网络中的其他节点时，它会随机的选择周围几个节点散播消息，收到消息的节点也会重复该过程，直至最终网络中所有的节点都收到了消息。这个过程可能需要一定的时间，由于不能保证某个时刻所有节点都收到消息，但是理论上最终所有节点都会收到消息，因此它是一个最终一致性协议。

Redis 集群采用分片的方式保存键值对，数据库总共分为 16384 个槽，每个 key 都属于其中一个槽，每个服务器可以同时处理 0-16384 个槽中的键。

每个槽的指派信息记录在一个 bitmap 中，同时记录了集群中所有槽指派信息。在集群中，每个节点通过消息传播的方式，告知集群内其他的节点自己负责的槽。

当客户端向集群内的任意节点发送和键相关的命令时，节点需要计算出键属于哪个槽，并且判断这个槽是否由自己负责的。如果不是自己负责的，需要给客户端发送一个 MOVE 错误。客户端接收到这个消息后，将会被重定向到正确的节点，然后再次发送相同的命令。

Redis 使用 CRC-16 校验和确定每个数据键属于哪个槽。

Redis 集群提供了重新分片的功能。重新分片指的是将任意数量的指派给某个节点（源节点）的槽划分给另一个节点（目标节点），Redis 使用管理软件 redis-trib 执行。重新分片操作可以在线进行，集群不需要下线。在操作过程中，如果客户端向源节点发送数据键相关的命令，并且数据键属于正在被迁移的槽，那么源节点首先在自己的数据库查找键，如果不存在，向客户端发送一个 ASK 错误。客户端接收到这个错误后，将会重定向到目标节点，并且重新执行数据键相关的命令。

MOVE 错误和 ASK 错误的区别如下：

MOVE 命令的效果是永久性的。
ASK 命令的效果是临时性的。

集群内每个节点通过发送 PING 消息确定集群内的节点是否在线。如果接收了 PING 消息的节点没有在规定时间内返回 PONG 消息，那么发送 PING 消息的节点会把接收 PING 消息的节点标记为 ** 疑似下线 ** 状态。如果有半数以上的主节点认为某个主节点处于疑似下线状态，那么该节点会被标记为已下线，并通过消息广播的形式通知集群内所有的节点。

当 Redis 集群中的主节点下线后，需要选出一个从节点成为新的主节点。选举的过程和 Sentinel 选举领头节点的过程类似，也是 Raft 算法的实现。选举过程如下：

当从节点发现自己的主节点已下线，它会要求所有具有投票权的主节点给自己投票。
主节点会把接收到的第一个从节点设置为新的主节点。
如果一个从节点获得 n/2+1 个主节点的投票支持，那么就会成为新的主节点。

参考

《Redis 设计与实现》
P2P 网络核心技术：Gossip 协议