Raft 一致性算法

分布式系统中，如何保证多个节点的状态一致？Raft 一致性算法与 Paxos 不同，号称简单易学，且已经广泛应用在生产中。例如 k8s 和 CoreOS 中使用的 etcd；tikv 中使用 Raft 做分布式同步；Redis Cluster 中使用的类似 Raft 的选主机制等等。今天我们来一探究竟吧。

复制状态机/Replicated state machines

复制状态机将服务器看成一个状态机，而一致性算法的目的是让多台服务器/状态机能够计算得到相同的状态，同时，如果有部分机器宕机，集群作为一个整体依然能继续工作。复制状态机一般通过复制日志（replicated log）来实现，如下图：

服务器会将客户端发来的命令存成日志，日志是有序的。而服务器状态机执行命令的结果是确定的，这样如果每台服务器的状态机执行的命令是相同的，状态机最终的状态也会是相同的，输出的结果也会是相同的。而如何保证不同服务器间的日志是一样的呢？这就是其中的“一致性模块”的工作了。

一致性模块（consensus module）在收到客户端的命令时（②），一方面要将命令添加到自己的日志队列中，同时需要与其它服务器的一致性模块沟通，确保所有的服务器将 最终 拥有相同的日志，即使有些服务器可能挂了。实践中至少需要“大多数(大于一半)”服务器同步了命令才认为同步成功了。

Raft 算法

接下去会从 3 个方面讲解 Raft 算法：

1. 选主（Leader Election）。Raft 在同一时刻只有一个主节点能接收写命令。
2. 日志复制（Log Replication）。Raft 如何将接收到的命令复制到其它服务器上，使其保持一致？
3. 安全性，为什么 Raft 在各种情况下依旧能保证各服务器的日志一致性？

基础概念

首先是节点的 3 种状态/角色：

• Follower/从节点不发起请求，单纯响应 Candidate 和 Leader 的请求
• Leader/主节点负责响应客户端发起的请求，如果客户端的请求发送到 Follower，请求会被转发到主节点
• Candidate/候选节点是一种中间状态，只在选主期间存在。

它们的转换关系如下：

其次是任期（term）的概念。Raft 将时间切分成多个 term，每个 term 以选主开始，选主期间各节点尝试当上主节点，选举结束后开始正常处理客户端的请求。如图：

Raft 会保证每一个 term 中至多只有一个 leader，如果选主时选票被分散导致没有节点获得多数票（如 t3），则会开始新一轮选举。

term 就像逻辑上的“时间”，用来记录和比较各节点的“进度”。如果某个节点收到信息时发现自己的 term 是落后的，它会立即将自己的 term 更新为更大的 term；同时节点不会理睬 term 比自己小的消息；另外如果主节点收到 term 比自己大的消息，则会立马进入 follower 的状态。

例如由于网络情况不佳，一个主节点 A 与其它节点失联，其它节点选了一个新的主节点 B，当网络恢复正常时，旧主节点 A 收到主节点 B 的消息时，它会判断新主节点 B 的 term 大于自己，说明自己错过了一些事件，因此选择放弃自己的主节点身份。

选主/Leader Election

节点启动时，默认处于 Follower 的状态，所以开始时所有节点均是 Follower，那么什么时候触发选主呢？Raft 用“心跳”的方式来保持主从节点的联系，如果长时间没有收到主节点的心跳，则开始选主。这里会涉及到两个时间：

• 心跳间隔，主节点隔多长时间发送心跳信息
• 等待时间(election timeout)，如果超过这个时间仍然没有收到心跳，则认为主节点宕机。一般每个节点各自在 150～300ms 间随机取值。

当一个节点在等待时间内没有收到主节点的心跳信息，它首先将自己保存的 term 增加 1 并进入 Candidate 状态。此时它会先投票给自己，然后并行发送 RequestVote 消息给其它所有节点，请求这些节点投票给自己。然后等待直到以下 3 种情形之一发生：

1. 收到大于一半的票，当选为主节点
2. 有其它节点当选了主节点，此时会收到新的主节点的心跳
3. 过了一段时间后依旧没有当选，此时该节点会尝试开始新一轮选举

对于第一种情形，Candidate 节点需要收到集群中与自己 term 相同的所有节点中大于一半的票数（当然如果节点 term 比自己大，是不会理睬自己的选举消息的）。节点投票时会采取先到先得的原则，对于某个 term，最多投出一票（后面还会再对投票加一些限制）。这样能保证某个 term 中，最多只会产生一个 leader。当一个 Candidate 变成主节点后，它会向其它所有节点发送心跳信息，这样其它的 Candidate 也会变成 Follower。

第二种情形是在等待投票的过程中，Candidate 收到其它主节点的心跳信息（只有主节点才会向其它节点发心跳），且信息中包含的 term 大于等于自己的 term，则当前节点放弃竞选，进入 Follower 状态。当然，如前所说，如果心跳中的 term 小于自己，则不予理会。

第三种情形一般发生在多个 Follower 同时触发选举，而各节点的投票被分散了，导致没有 Candidate 能得到多数票。超过投票的等待时间后，节点触发新一轮选举。理论上，选举有可能永远平票，Raft 中由于各个节点的超时时间是随机的，实际上平票不太会永远持续下去。

日志复制/Log Replication

Log Replication 分为两个主要步骤：复制/Replication 和 提交/Commit。当一个节点被选为主节点后，它开始对外提供服务，收到客户端的 command 后，主节点会首先将 command 添加到自己的日志队列中，然后并行地将消息发送给其它所有的节点，在确保消息被安全地复制（下文解释）后，主节点会将该消息提交到状态机中，并返回状态机执行的结果。如果follower 挂了或因为网络原因消息丢失了，主节点会不断重试直到所有从节点 最终 成功复制该消息。

日志结构示例如下：

日志由许多条目（log entry）组成，条目顺序编号。条目包含它生成时节点所在的 term （小方格中上方的数字），以及日志的内容。当一个条目被认为安全地被复制，且提交到状态机时，我们认为它处于“已提交（committed）”状态。

是否将一个条目提交到状态机是由主节点决定的。Raft 要保证提交的条目会 最终 被所有的节点执行。当主节点判断一个条目已经被复制到 大多数 节点时，就会 提交 /Commit 该条目，提交一个条目的同时会提交该条目之前的所有条目，包括那些之前由其它主节点创建的条目（还有些特殊情况下面会提）。主节点会记录当前提交的日志编号 (log index)，并在发送心跳时带上该信息，这样其它节点最终会同步提交日志。

上面说的是“提交”，那么“复制”是如何进行的？在现实情况下，主从节点的日志可能不一致（例如在消息到达从节点前主节点挂了，而从节点被选为了新的主节点，此时主从节点的日志不一致）。Raft 算法中，主节点需要处理不一致的情况，它要求所有的从节点复制自己的所有日志（当然下一小节会介绍额外的限制，保证复制是安全的）。

要复制所有日志，就要先找到日志开始不一致的位置，如何做到呢？Raft 当主节点接收到新的 command 时，会发送 AppendEntries 让从节点复制日志，不一致的情况也会在这时被处理（ AppendEntries 消息同时还兼职作为心跳信息）。下面是日志不一致的示例：

主节点需要为每个从节点记录一个 nextIndex ，作为该从节点下一条要发送的日志的编号。当一个节点刚被选为主节点时，为所有从节点的 nextIndex 初始化自己最大日志编号加 1（如上图示例则为 11 ）。接着主节点发送 AppendEntries 给从节点，此时从节点会进行一致性检查（Consistency Check）。

所谓一致性检查，指的是当主节点发送 AppendEntries 消息通知从节点添加条目时，需要将新条目 A 之前的那个条目 B 的 log index 和 term，这样，当从节点收到消息时，就可以判断自己第log index 条日志的 term 是否与 B 的 term 相同，如果不相同则拒绝该消息，如果相同则添加条目 A。

主节点的消息被某个从节点拒绝后，主节点会将该从节点的 nextIndex 减一再重新发送 AppendEntries 消息。不断重试，最终就能找主从节点日志一致的 log index，并用主节点的新日志覆盖从节点的旧日志。当然，如果从节点接收 AppendEntries 消息后，主节点会将 nextIndex 增加一，且如果当前的最新 log index 大于 nextIndex 则会继续发送消息。

通过以上的机制，Raft 就能保证：

• 如果两个日志条目有相同的 log index 和 term，则它们的内容一定相同。
• 如果两个节点中的两个条目有相同的 log index 和 term，则它们之前的所有日志一定相同。

安全性

要保证所有的状态机有一样的状态，单凭前几节的算法还不够。例如有 3 个节点 A、B、 C，如果 A 为主节点期间 C 挂了，此时消息被多数节点（A，B）接收，所以 A 会提交这些日志。此时若 A 挂了，而 C 恢复且被选为主节点，则 A 已经提交的日志会被 C 的日志覆盖，从而导致状态机的状态不一致。

选主的限制

在所有的主从结构的一致性算法中，主节点最终都必须包含所有提交的日志。有些算法在从节点不包含所有已提交日志的情况下，依旧允许它当选为主节点，之后从节点会将这些日志同步到主节点上。但是 Raft 采用了简单的方式，只允许那些包含所有已提交日志的节点当选为主节点。

注意到节点当选主节点要求得到 多数 票，同时一个日志被提交的前提条件是它被 多数 节点接收，综合这两点，说明选举要产生结果，则至少有一个节点在场，它是包含了当前已经提交的所有日志的。

因此，Raft 算法在处理要求选举的 RequestVote 消息时做了限制：消息中会携带 Candidate 的 log 消息，而在投票时，Follower 会判断 Candidate 的消息是不是比自己“更新”（下文定义），如果不如自己“新”，则拒绝为该 Candidate 投票。

Raft 会首先判断两个节点最后一个 log entry 的 term，哪个节点的对应的 term 更大则代表该节点的日志“更新”；如果 term 的大小一致，则谁的 log entry 更多谁就“更新”。

注意，加了这个限制后，选出的节点不会是“最新的”，即包含所有日志；但会是足够新的，至少比半数节点更新，而这也意味着它所包含的日志都是可以被提交的（但不一定已经提交）。

提交前一个 term 的日志

这里我们要讨论一个特别的情况。我们知道一个主节点如果发现自己任期（term）内的某条日志已经被存储到了多数节点上，主节点就会提交这条日志。但如果主节点在提交之前就挂了，之后的主节点会尝试把前任未提交的这些日志复制到所有子节点上，但与之前不同，仅仅判断这些日志被复制到多数节点，新的主节点并不能立马提交这些日志，下面举一个反例：

在 (a) 时，S1 当选并将日志编号为 2 的日志复制到其它节点上。在 (b) 时，S1 宕机，S5 获得来自 S3 与 S4 的投票，当选为 term 3 的主节点，此时收到来自客户端的消息，写入自己编号为 2 的日志。 (c) 期间，S5 宕机而 S1 重启完毕，它重新当选为主节点并继续将自己的日志复制给 S3，此时编号为 2 且 term 为 2 的日志已经被复制到多数节点，但它还不能被提交。如果此时 S1 宕机，如 (d) 所示，此时 S5 获得来自 S2 S3 S4 的投票，当选新的主节点，此时它将用自己的编号为 2，term 为 3 的日志覆盖其它节点的日志。而如果 S1 继续存活，且在自己的任期内将某条日志复制到多数节点，如 (e) 所示，则此时 S5 已经不可能继续当选为主节点，因此该日志之前的所有日志均可被提交（包括前任创建的，编号 2 的日志）。

上例中的 (c) 和 (d) 说明了，即使前任的日志已经被复制到多数节点上，它依然可能被覆盖。因此 Raft 并 不通过 计算前任日志的复制次数来判断是否提交这些日志， Raft 只对自己任期内的日志计数并在复制到多数节点时进行提交，且在提交这条日志的同时提交之前的所有日志。

Raft 算法会出现这个额外的问题，是因为它在复制前任的日志时，会保留前任的 term，而其它一致性算法会为这些日志使用新的 term。Raft 算法的优势在于方便推理日志的形成过程，同时新的主节点需要发送的前任日志数目会更少。

安全性说明

Raft 算法的安全性是经过理论证明的，这部分博主不熟悉相关领域，只得请大家自行看原论文了。

Follower 与 Candidate 宕机

这部分 Raft 的处理非常简单，如果 Follower 或 Candidate 宕机，主节点会不断进行重试，即不管挂不挂都照常发送 AppendEntries 消息。这样当 Follower 或 Candidate 恢复之后，日志仍能被正确复制。有时 Follower 会处理消息却在响应前宕机，此时由于 Raft 算法是幂等的，因此重复发送也没有关系。

算法伪代码

下图来源于原论文：

成员变更

假设已经有了一个 Raft 集群，现在要往集群中增加/移除若干个节点，要如何实现？

双多数派问题

一种方法是先停止所有节点，修改配置增加新的节点，再重启所有节点，但是这样服务起停时就会中断服务，同时也可能增加人为操作失误的风险。另一种方法配置好新的节点直接加入集群，这样也会出问题：在某个时刻使用不同配置的两部分节点可能会各自选出一个主节点。如下图：

图中绿色为旧的配置，蓝色为新的配置，在中间的某个时刻，Server 1/2/3 可能会选出一个主节点，而 Server 3/4/5 可能会选出另一个，从而破坏了一致性。

成员变更算法

原版论文 提出了一个比较复杂的算法，利用一个中间的过度状态来从 C_old 过度到 C_new （这里的 C_xxx 指的是成员的配置），在作者的 博士论文 中指出了一个更简单的方法。作者发现，如果一次只增加或减少一个节点，那么并不会出现上面说的两个多数派的问题。示例如下：

上图的 4 种情况分别代表原始节点数为奇数和偶数的情况下，添加或移除一个节点时可能产生的“大多数节点”的分组情况。注意到所有的分组都至少会一个节点会出现在两个分组中，那么，如果该节点是主节点，则其它所有节点均不可能当选主节点；如果该节点不是主节点，则它至少应该投票给其中一个分组中的其它节点，但这样一来另一个分组就达到不到票数来产生新的主节点了。因此在只增加/减少一个节点的情况下，不可能同时产生两个主节点。

当主节点收到对当前集群（C_old）新增/移除节点的请求时，它会将新的集群配置（C_new）作为一条新的日志加入到队列中，并用上文提到的机制复制到其它各个节点。当一个节点收到新的日志时，日志中的 C_new 会立即生效，即该节点的日志会被复制到 C_new 中配置的其它节点，且日志是否被提交也以 C_new 中指定的节点作为依据。这意味着节点不需要等 C_new 日志被提交后才开始启用 C_new，且每个节点总是使用它的日志中最新的配置。

当主节点提交 C_new 日志后，新增/移除节点的操作就算结束。此时，主节点能确定至少 C_new 中的多数节点已经启用了 C_new 配置，同时，那些还没有启用 C_new 的节点也不再可能组成新的“多数节点”。