角色

Raft 协议包含三种角色：

  • Leader
  • Follower
  • Candidate

image

  1. 选举计时器超时（Leader 超时没有发送心跳）
  2. 选举成功（获得半数以上投票）
  3. 选举失败（投票数不够，或者有了新的 Leader）
  4. 有了比自己 term 更大的 Leader（通常发生在旧 Leader 网络分区问题恢复时）

Leader 选举

什么时候开始选举？

每个 Follower 会维护一个 选举计时器

如果选举计时器超时，那么该 Follower 认为 Leader 挂了，准备开始选举

Follower 此时会变成 Candidate：

  • 将自己的 Term 加一
  • 并给集群剩余的 Followers 发送 VoteRPC，要求 Followers 给自己投票

投票采取 FIFO 机制：每个 Follower 只有一票，收到一个投票请求，如果：

  • 自己有票
  • Candidate 的 Term 大于等于自己的 Term
  • Candidate 的 Log 比自己新或者一致

那么 Follower 会给该 Candidate 投票

如果某一个 Candidate 拥有超过半数（整个集群中）的票，那么该 Candidate 就升级为 Leader

某一轮选举可能失败（每个 candidate 都没有拿到半数以上的选票），怎么解决的？

如果选举的 candidate 同时 开启选票，可能出现选票被「瓜分」的情况

每个 Candidate 会在选举开始时启动一个 选举超时计时器

如果计时器超时，那么当前 candidate 会 重新开启 一轮新的投票

选举超时计时器的超时时间怎么确定的？

超时时间实际上是一个 随机值，范围在 [min,max] 之间，这样可以避免多次选举都失败的极限情况

范围怎么确定？

广播时间（broadcastTime） « 选举超时时间（electionTimeout） « 平均故障间隔时间（MTBF）

论文的解释是：

广播时间必须比选举超时时间小一个量级，这样 Leader 才能够有效发送心跳信息来组织 Follower 进入选举状态。再加上随机化选举超时时间的方法，这个不等式也使得无果选票（split vote）变得几乎不可能。而选举超时时间需要比平均故障间隔时间小上几个数量级，这样整个系统才可以稳定地运行。

翻译自 知乎

日志复制

为了保证集群的可用性，Leader 需要将客户端发来的 Command 同步给 Follower

在 Raft 协议中，将 Command 以及其它元数据封装成一个「日志」

一个日志包含以下内容：

  • Command
  • Term：收到该 Command 时，Leader 的 CurTerm

Term 的作用主要是用于检测 Follower 与 Leader 的 Log 是否一致，即 一致性检查

日志复制的过程

这里以「一个客户端请求执行的过程」来展示日志是如何在节点间复制的：

  1. 客户端向 Leader 发送一条 Command
  2. Leader 收到该 Command，将其封装成一个 Log
  3. Leader 向所有 Follower 发送 AE 请求，要求 Follower 将该 Log Append 到本地
  4. Follower 收到 AE 请求，执行 一致性检查 ，并返回结果给 Leader
  5. 当 Leader 收到半数以上的 Follower 的确认以后，可以认为这个 Command 在整个集群中被「Commit」，推进 CommitIdx，然后：
  6. Leader 本地执行 Command，推进 ApplyIdx，告诉客户端执行成功

Follower 看起来仅仅只是将 Log 存储在本地，还没有执行 Command？

下一次 Leader 向 Follower 发起 AE 请求时，会顺带上 CommitIdx

Follower 可以根据 CommitIdx，来判断哪些日志已经被提交，并执行这些已经提交的日志

这个特性，决定了 Raft 协议中，Follower 应用的数据 不总是最新的，因此，客户端实际的 读写操作应该都在 Leader 进行

Fail

Raft 通过在 AE 执行时的 一致性检查 来确保即使出现错误，也能保证数据的一致性

一致性检查，是在 Follower 执行的

具体来说，Leader 在发送 AE 请求时，会带上 前一个日志条目的索引位置和任期号

Follower 会检查自己的日志是否包含 Leader 发来的 前一个日志条目的索引位置和任期号，如果不包含，那么一致性检查失败

正常情况下，一致性检查不会失败，但是如果 Leader 挂了，就有可能出现检查失败的情况

image

当一个 Leader 成功当选时（最上面那条日志），Follower 可能是以下 (a-f)几种情况。每一个盒子表示一条日志条目，盒子里面的数字表示任期号。一个 Follower 有可能会缺失一些日志条目（a-b），一个 Follower 也有可能会有一些未被提交的日志条目（c-d），或者两种情况都有 (e-f)。例如，场景 f 有可能是这样发生的：f 对应的服务器在任期 2 的时候是 Leader，它追加了一些日志条目到自己的日志中，一条日志还没提交就宕机了，但是它很快就恢复重启了，然后再在任期 3 重新被选举为 Leader，又追加了一些日志条目到自己的日志中，在这些任期 2 和任期了的日志还没有被提交之前，该服务器又宕机了，并且在接下来的几个任期里一直处于宕机状态。

翻译自 知乎

在一致性检查失败时，Leader 会 强制 Follower 复制 Leader 的日志来解决一致性问题

具体来说，Follower 在一致性检查失败后，会给 Leader 一个 reply，告诉 Leader 一致性检查失败了

为了使 Follower 的日志跟自己（Leader）一致，Leader 必须找到两者达成一致的最大的日志条目索引，删除 Follower 日志中从那个索引之后的所有日志条目，并且将自己那个索引之后的所有日志条目发送给 Follower。

例如，对于上图中的 e，Leader 会告诉 Follower，删除 idx = 6 及后面所有的 Log，并发送自己 idx = 6 及后面所有的 Log 给 Follower 应用

如果一个 Leader 在发送 AE 给 Follower 前挂了，那么 Follower 怎么知道哪些 Log 已经被 commit？

对于这种情况，Follower 无需 知道哪些 Log 被 commit

怎么理解？

如果一个 Log 没有被 commit，并且 Leader 挂了，客户端后面会知道这个 command 执行失败了，那么这个 Log 丢了也无所谓

主要看 Log 被 commit 的情况

如果一个 Log（假设为 A）被 commit，那么意味着有 半数以上 的节点本地的 Log 列表中，都有 A

假设 Leader 挂了，自然需要选举一个新的 Leader 出来

根据前文提到的 Leader 选举过程中，Follower 投票规则：

  • 自己有票
  • Candidate 的 Term 大于等于自己的 Term
  • Candidate 的 Log 比自己新或者一致

前面提到了：半数以上 的节点（假设为集合 S）本地的 Log 列表中，都有 A

那么，根据投票规则，只有集合 S 中的节点，才有机会当选 Leader（不处于 S 中的节点，由于日志比较旧，不会得到大多数投票）

当选出一个新的 Leader 时，新的 Leader 可以 安全地 认为自己的 Log 都是已经 commit，立即发起一轮 heartbeat（AE）请求

这样，其它的 Follower 就知道哪些日志已经被 commit 了

是否存在数据丢失问题？

不会存在

原因和上面的问题类似：截断的 Log 是没有被旧 Leader 提交的 Log，这些 Log 即使丢了也无所谓，客户端是有感知的，后面重试即可

日志在 Raft 中的作用

参考 MIT-6.824，Lecture 6 中，Robert 教授的 讲解 ：

Log 是 Leader 用来对操作排序的一种手段

对于这些复制状态机来说，所有副本不仅要执行相同的操作，还需要 用相同的顺序 执行这些操作。而 Log 与其他很多事物，共同构成了 Leader 对接收到的客户端操作分配顺序的机制。

临时存放 Command

这个可以从 Leader 和 Follower 两个方面来理解：

对于 Leader 来说，如果同步 Command 给 Follower 时，网络出现问题，需要重传，那么缓存的 Log 就可以派上用场

并且，即使对于 Commit 后的 Command，还是有可能有一些 Follower 没有拿到这个日志，Leader 本地缓存的 Log 还可以用于 Follower 后续的数据恢复

对于 Follower 来说，即使同步到了 Command，也不知道这些 Command 有没有 Commit，只有 Leader 发来下一次 AE 请求，才知道哪些 Command 已经被提交

帮助重启的服务器恢复状态

所有节点都需要保存 Log 还有一个原因，就是它可以帮助重启的服务器恢复状态。对于一个重启的服务器来说，会使用存储在磁盘中的 Log。每个 Raft 节点都需要将 Log 写入到它的磁盘中，这样它故障重启之后，Log 还能保留。而这个 Log 会被 Raft 节点用来从头执行其中的操作进而重建故障前的状态，并继续以这个状态运行。所以，Log 也会被用来持久化存储操作，服务器可以依赖这些操作来恢复状态。

这样，服务器重启，就不需要在 Leader 拉取大量 Log，进一步减少网络压力

持久化

  • Logs
  • CurrentTerm
  • VoteFor

为啥要持久化这三个数据？

首先是 Logs，持久化 Logs，主要是帮助服务器重启时快速恢复状态，而不是让 Leader 给自己发送 AE RPC 全量同步，减少网络压力

其次是 CurrentTerm，如果重启的 Raft Server 不知道自己之前的 Term，可能会让 Raft 共识产生混乱

最后是 VoteFor，重启的 Raft Server 除了要知道自己的 Term 以外，还要知道自己在这个 Term 是否给其它 Server 投过票，避免重复投票，造成选举错误

为啥不持久化其它数据：commitIndex、lastApplied、nextIndex、matchIndex？

这几个 Index 都可以随着 Raft 共识协议的进行而自更新，无需持久化

谁来持久化？持久化的过程？怎么写磁盘更高效？

无论是 Leader 还是 Follower，都要持久化自己的数据到本地磁盘

如果 Leader 收到了一个客户端请求，在发送 AppendEntries RPC 给 Followers 之前，必须要先持久化存储在本地。因为 Leader 必须要 commit 那个请求，并且不能忘记这个请求。实际上，在回复 AppendEntries 消息之前，Followers 也需要持久化存储这些 Log 条目到本地，因为它们最终也要 commit 这个请求，它们不能因为重启而忘记这个请求。

一个简单的实现方式是：只要内存中，Logs、CurrentTerm、VoteFor 三者任何一个发生改变，就持久化，Lab3C 也是这样实现的

这种持久化方式合适吗？

很容易发现前面提到的持久化方式是不合理的，在实际生产环境显然不可用

因为无论哪个数据变化，都要做一次 整个数据 的持久化

数据持久化，是对 磁盘 进行 IO 操作的过程，而磁盘的速率很低，采取这种持久化方式，会产生性能问题

那应该怎么持久化？

我们可以 参考 Redis 的持久化方式：

将持久化分为两个文件：

  • metadata
  • logs.aof

其中，metadata 用于持久化 CurrentTerm 和 VoteFor，因为这两个数据很小，每次更改持久化，也没什么问题

而 logs.aof 用于持久化 Logs，每次客户端追加 Logs 时，我们只需要向 Logs 追加一条数据即可，这个是顺序 IO，性能较高

并且，可以引入 批量写入 的机制，具体来说，每次追加 Logs 时，不需要立即写磁盘，而是写到内存(rf.Logs)，然后后台启动一个 goroutine，做定时持久化操作，持久化的频率根据数据的可靠性来确定：

  • 如果要求比较高的可靠性，那频率应该更高，甚至，放弃批量写入机制，而是直接写入磁盘（write+fsync）

此外，写入磁盘，通常使用的是 write 系统调用，不会立即将文件写入磁盘，而是在 OS 层面做了一个 buffer，还是有数据丢失的风险

我们还可以再启动一个 goroutine，定期调用 fsync，控制文件真正写入磁盘的频率

日志压缩

为什么要创建快照？

随着上层服务不断的请求，Raft Server 存储的 Log 肯定会越来越多，此时，整个 Raft 的性能会受到影响

因此，需要在合适的时机对 Raft 做一次日志压缩

实现日志压缩最简单的方式之一就是创建「快照」，将当前 Raft 实例的状态完整记录下来：

image

可以发现，前五条日志条目经过「压缩」后，仅剩下 2 条，这个有点 类似 Redis 的 AOF 重写

快照包含了哪些内容？

从上图可以发现，快照包含了：

  • 压缩后的 Logs 列表
  • LastIncludedIndex
  • LastIncludedTerm

包含 LastIncludedIndex、LastIncludedTerm 的原因是为了 AE RPC 中做的 一致性检查

怎么创建快照？是否依赖客户端？

通常情况下，节点独立生成快照，并且快照的生成依赖于客户端（上层服务），因为 Raft 并不知道自己存储的 Logs 的定义是什么，只有客户端才知道如何做压缩

但是 Leader 不可避免偶尔需要发送快照给一些落后的 Follower。这通常发生在 Leader 已经丢弃了需要发给 Follower 的下一条日志条目的时候。幸运的是，这种情况在正常操作中是不会出现的：一个与 Leader 保持同步的 Follower 通常都会拥有该日志条目。

不过如果一个 Followe 运行比较缓慢，或者是它刚加入集群，那么它就可能会没有该日志条目。这个时候 Leader 会通过网络将该快照发送给该 Follower，以使得该 Follower 可以更新到最新的状态。

leader 使用 InstallSnapshotRPC 来发送快照给那些太落后的 follower

如果 Leader 发送 rf.Logs 的所有内容，Follower 还是拒绝了 Leader 的 AE 请求，说明 Follower 同步进度太慢，以至于 Leader 的 rf.Logs 中，没有 Follower 所需的日志（这部分日志由于快照的创建而被截断）

image

上面的图片展示了这种情况：

  • Follower 的同步速度很慢，即使 Leader 的 nextIndex=7，也无法被 Follower 接受

此时，Leader 需要发送自己的「快照」给 Follower，让 Follower 使用快照来覆盖自己本地的 Logs：

image

当然还有一种特殊的情况，即 Follower 收到了描述自己日志前缀的快照：

image

这通常是由于重传和错误产生的，对于这种「错误」的情况，Follower 需要：

  • 截断 被快照覆盖部分的日志
  • 使用该 Snapshot 作为自己的 Snapshot

image

集群成员变更

在某些时候，我们希望对 Raft 集群做 扩缩容，即向集群中添加或者删除若干个节点，此时应该怎么做呢？

直接更新 Config 有什么问题

你可能会想：扩缩容，直接修改每个节点的 config 不就好了吗？

然而，直接修改 config 存在一个问题：某一个 Term 内，集群存在两个 Leader，即脑裂

image

因为我们不可能同时修改每个节点的 config，这就意味着在某一时刻，一些节点使用的是旧的 config，一些节点使用的是新的 config

例如上图中，存在一个时间段，Server-1 与 Server-2 持有旧 config，Server-3、Server-4、Server-5 持有新的 config

如果在这个时间段内发生了 Leader 选举，那么：

  • Server-1 与 Server-2 之间会选出一个 Leader（其中一个获得两票，满足旧 config 的 majority）
  • Server-3、Server-4、Server-5 之间也会选出一个 Leader（其中一个获得三票，满足新 config 的 majority）

整个集群就出现了两个 Term 相同的 Leader，这违背了 Raft 协议

如何处理集群成员变更

停机，手动修改每个节点的 config

这种方式非常简单，但是存在一个问题：config 修改期间，整个集群是无法对外提供服务的

单节点变更

这种方式要求：一次性只能添加或删除 一个 节点，只有当新配置被 apply 以后，才能添加或删除下一个节点

为什么单节点变更，可以保证任意时刻，不会出现脑裂现象呢？

image

原有集群奇偶数节点情况下，分别添加和删除一个节点。在上图中可以看出，如果每次只增加和删除一个节点，那么 Cold 的 Majority 和 Cnew 的 Majority 之间一定 存在交集，也就说是在同一个 Term 中，Cold 和 Cnew 中交集的那一个节点只会进行一次投票，要么投票给 Cold，要么投票给 Cnew，这样就避免了同一 Term 下出现两个 Leader。

但是这种方式变更效率不高，一次只能变更一个节点，如果我们希望一次变更多个节点怎么办呢？

多节点变更：联合共识（joint consensus）

Raft 引入了 联合共识（joint consensus） 的概念来处理集群节点变更的情况

简单来说，除了旧配置 Cold 与新配置 Cnew 以外，还额外引入了一个 联合共识配置：C(old,new)

C(old,new) 是新旧配置的并集，例如：

  • Cold 中有 [A, B, C, D] 四个节点
  • Cnew 中有 [B, C, D, E] 四个节点

那么 C(old,new) 中有 [A, B, C, D, E] 五个节点

采用联合共识：

  • 日志条目被复制给集群中处于新、老配置的所有节点
  • 新、旧配置的节点都可能成为 leader
  • 达成一致（针对选举和提交）需要 分别得到在两种配置上过半的支持

当 Leader 收到客户端的集群变更请求后

  • 根据新旧配置生成一个联合共识配置
  • 采用日志复制的方式同步联合共识配置
  • 任何节点收到一个描述配置的日志条目时，无需等待提交，立即应用新配置
  • 当联合共识配置被 Commit 并 Apply 后，Leader 可以安全的生成新配置 Cnew
  • 采用日志复制的方式同步 Cnew
  • 当 Cnew 被 Commit 并 Apply 后，Cold 就没有作用了，此时集群完全采用新的配置

image

上图描述了使用联合共识更新配置文件的全过程，共分为三个阶段：

  • 阶段 1: C(old,new) 创建后，commit 前：此时只有处于 Cold 配置的节点可以当选 Leader（因为 Cold 是 majority）
  • 阶段 2: C(old,new) commit 后，Cnew commit 前：此时只有处于 C(old, new) 配置的阶段可以当选 Leader（因为 C(old, new) 是 majority）
  • 阶段 3: Cnew commit 后：此时只有处于 Cnew 配置的节点可以当选 Leader（因为 Cnew 是 majority）

可以发现：使用联合共识，可以保证任意阶段，最多只有一个 Leader，确保了配置更新的安全性

但是使用联合共识会引入额外的复杂度，带来一些问题：

新的节点需要追赶日志条目

引入新身份：Learner

新的节点可能在一开始并没有存储任何的日志条目。当这些节点以这种状态加入到集群中的时候，它们需要一段时间来更新自己的日志，以便赶上其他节点，在这个时间段里面它们是不可能提交一个新的日志条目的。

为了避免因此造成的系统短时间的不可用，Raft 在配置变更前引入了一个额外的阶段。在该阶段中，新的节点以 没有投票权身份（Leaner） 加入到集群中来（leader 会把日志复制给它们，但是考虑过半的时候不需要考虑它们）。

一旦新节点的日志已经赶上了集群中的其他节点，那么配置变更就可以按照之前描述的方式进行了。

Leader 有可能不是新配置中的一员

为了解决这个问题，Leader 一旦 提交 了 Cnew 日志条目，它就会退位为 Follower

移除的节点扰乱集群

新配置中，可能移除了部分节点，新的 Leader 不会给这些节点发送心跳

在这部分节点下线前，由于收不到 Leader 的心跳，会开始 Leader 选举过程

它们会发送带有新任期号的 RequestVote RPC，这样会导致当前的 Leader 回到 Follower 状态，然后选出一个新的 Leader。但是这些被移除的节点还是会收不到心跳，然后再次超时，再次循环这个过程，导致系统的可用性很差。

为了解决这个问题，一个节点在处理另一个节点的投票请求时，如果它认为已经有一个 Leader 存在，那么它会 忽略 投票请求

具体来说，如果一个节点在最小选举超时时间内收到一个 RequestVote RPC，它会忽略这个请求

这种方式有效避免了 Term 爆炸增长的问题

Raft 怎么处理脑裂的？=> 分布式系统应该如何应对脑裂？

脑裂主要是 网络分区问题 产生的

当旧 Leader 所在网络分区出现问题，无法与部分 Follower 建立心跳，那么这一部分 Follower 会开始选举

讨论两种情况：

  1. Leader 所在网络分区具有节点数大于 n / 2
  2. Leader 所在网络分区具有节点数小于 n / 2

对于第一种情况，Follower 的选举过程会失败，因为没有足够的票数，不存在脑裂

对于第二种情况，Follower 的选举过程也许会成功，假设成功，会出现脑裂吗？

如果选举成功，即旧 Leader 所在网络分区具有节点数小于 n / 2，那么客户端在 旧 Leader 的写入操作全部都会失败，只有在新的 Leader 上执行写操作，才有可能成功

当旧 Leader 所在的网络分区问题修复后，旧 Leader 以及 Follower 会收到新 Leader 的 AE 请求

由于新 Leader 的 Term 更大，因此，旧 Leader 会降级为 Follower，并从新的 Leader 同步丢失的 Log

Raft 就是通过 过半票决 + Term 这一规则来规避「脑裂」这一问题的

分布式系统应该如何应对脑裂

在以前，建立分布式系统时，应对脑裂主要有两种方式：

  • 建立 绝对可靠 网络：当网络不出现故障时，那就意味着，如果客户端不能与一个服务器交互，那么这个服务器肯定是关机了。可以安全选举出一个 Leader
  • 人工解决问题，不要引入任何自动化

类似 Raft 的 Term 机制，可以为集群的 Leader 引入 Epoch 的概念

集群中的每个角色都要维护自己 Leader 的 Epoch

一旦收到了比自己维护的 Epoch 大的，就更新；遇到比自己维护 Epoch 小的，就忽略

这样，基本可以规避「脑裂」带来的影响

例如，Redis Cluster 模式下，每个节点会维护一个 currentEpoch，选举 Leader 时，也需要得到绝大多数选票才可以晋升为 Leader

与 Raft 不同的是，向 Leader 写入数据，不需要同步给 n/2+1 个 Follower 以后，才执行写入，因此，如果客户端向旧的 Leader 写入数据，有可能出现数据丢失的问题

当旧的 Leader 网络分区恢复以后，会收到新的 Leader 的心跳，发现自己的 currentEpoch 还小，于是降级为 Follower，并主动从新的 Leader 拉取同步数据

Kafka 应对脑裂的措施：

Zookeeper quorum 需要多数派，所以如果 ZK 集群发生分区，最多只有一边会有多数派。

Controller 脑裂

要成为 Controller 需要与 ZK 保持一个活跃的会话（临时 znode 注册）。如果当前 Controller 被分隔到 ZK quorum 之外，它应该 自愿停止认为自己是 Controller。这应该最多需要 zookeeper.session.timeout.ms = 6000。仍然连接到 ZK quorum 的 Nodes 应该在他们之间选举一个新的 Controller。（基于这个：https://stackoverflow.com/a/52426734）

Partition Leader 脑裂

Partition 的 Leader 也需要与 ZK 保持一个活跃的会话。失去与 ZK quorum 连接的 Leader 应该 自愿放弃 Leader 身份。被选举的 Controller 将检测到旧 Leader 断开，然后由 Controller 执行新的 Partition Leader 的选举过程

那么，在 ZK 超时窗口期间，被分割的前 Leader 收到的 Producer 请求会发生什么？有几种可能性。

如果 Producer 的 acks = all 并且 Topic 的 min.insync.replicas = replication.factor，那么所有 ISR 应该 有完全相同的数据。前 Leader 最终会拒绝正在进行的写入，Producer 会重新尝试它们。新选出的 Leader 将不会丢失任何数据。另一方面，在网络分区修复之前它将无法处理任何写请求。是否拒绝客户请求或在后台尝试一段时间，将取决于 Producer。

否则，新的 Leader 很可能会缺失 zookeeper.session.timeout.ms + replica.lag.time.max.ms = 16000 毫秒的记录，这些记录在网络分区修复后将从前 Leader 那里被截断。

Follower 和 candidate 崩溃（Follower and candidate crashes）

Follower 和 candidate 崩溃，无需特别处理

当 Follower 或者 candidate 崩溃，发送给它们的 RPC 请求会失败，Raft 采取尝试重新发送来解决这个问题，因为 AE RPC 和 RV RPC 是 幂等 的

  • 多次发送相同的 AE 是无害的，Follower 收到重复的 AE 会直接忽略
  • 多次发送相同的 RV 是无害的，Follower 会记录当前 Term 投票的对象，不会存在对于相同 Term，某一个 Candidate 的投票，第一次成功，第二次失败的问题

总结

  • Raft 是一种 强一致性 的分布式共识协议，它以牺牲可用性和部分性能为代价，保证了数据的可靠性
  • Raft 的强一致性体现在 Leader 写入日志时，需要过半节点都写入以后，才写入
  • Raft 使用 过半票决 + Term 处理脑裂问题，过半票决思想在 Leader 选举、Append Entries 都有体现
  • 为了 Raft 的正确进行，以及宕机重启快速恢复状态，Raft 需要持久化一些元数据到磁盘
  • 随着日志条目的增加，日志维护成为额外的性能开销，Raft 通过日志压缩来解决这个问题

参考资料