图解Raft算法

领导者选举

节点状态

在 Raft 中，节点有以下三种状态：

• leader（领导者）：接收 client （客户端）的所有请求，霸道总裁，一切以我为准。领导者平常的工作包括 3 个部分：处理写请求，管理日志复制，不断发送心跳信息通知其他节点”我是领导者，我还活者，你们现在不要发起新的选举“。Raft 保证任何时刻只有一个 leader
• follower（跟随者）：相当于普通群众，被动接收和处理来自领导者的消息。当领导者心跳超时时，就主动站出来，推荐自己当选候选人
• candidate（候选人）：用于选举出一个新的 leader。候选人向其他节点发送投票 （RequestVote，参考下文 Raft RPX 通信的描述）RPC 消息，通知其他节点来投票，如果赢得子大多数选票，就升级为领导者

节点状态转换示意图如下图所示：

任期

Raft 将时间划分为一个一个的任期（term），每个任期由单调递增的数字（任期编号）标识，例如，节点 A 的任期编号为 1。任期编号随着选举的举行变化而变化，即每个任期始于一个新的选举。

任期变化的示意图如下图所示：

从上图可以看出，任期一般包含两阶段，第一阶段是选举阶段，第二阶段为已选举出领导者的阶段。但任期也可能只包含选举阶段。可以看到 任期 3 由于并没有成功选举出领导者（即论文所说的 a split vote，两个节点同时成为候选人同时发起选举，导致无法成功选出领导者），只包含了选举阶段。接下来马上进入 任期 4，接着进行新一轮的选举。 Raft 保证在一任期内，最多只有一个领导者。

Raft 任期具有如下特点：

• 跟随者在等待领导者心跳消息超时后，推举自己为候选人时，会增加自己的任期编号，比如节点 A 的当前任期编号为 0，那么在推举自己为候选人时，会将自己的任期编号增加为 1
• 如果一个节点，发现自己的任期编号比其他节点小，那么它会更新自己的编号到较大的编号值。比如，节点 B 的任期编号为 0，当收到来自节点 A 的请求投票 RPC 消息，消息中包含节点的任期编号为 1，那么节点 B 将把自己的任期编号更新为 1
• 如果一个候选人或者领导者，发现自己的任期编号比其他节点小，那么它会立即恢复成跟随者状态（可以参考上面的节点状态转换示意图）。比如网络分区错误，导致出现两个领导者，当分区错误恢复后，任期编号为 3 的领导者 B 接收到领导者 A 任期编号为 4 的心跳消息，那么节点 B 将立即恢复成跟随着状态，接受节点 A 为领导者
• 如果一个节点接收到一个包含较小任期编号值的请求，那么它会直接拒绝这个请求。例如，节点 C 的任期编号为 4，接收到任期编号为 3 的 RPC 消息，那么节点 C 将拒绝这个消息

领导者选举

以三个节点的集群为例，说明 Raft 如何进行领导者的选举。

初始状态下，所有节点都是跟随者状态：

Raft 实现了随机超时时间的特性，上图可以看到，每个跟随者的等待超时时间是随机的。节点 A 跟随者等待超时时间最短为 150 ms，会最先发生超时，变成候选人。有关 Raft 超时时间的特性，下文会进行更详细的说明。

开始新的一轮选举后，节点 A 同时也增加自己的任期编号为 1，推举自己为候选人，并给自己投上一票，然后向其他节点发送请求投票 RPC 消息，请它们选举自己为领导者：

其他节点接收到候选人 A 的请求投票 RPC 消息，由于在任期编号为 1 的任期内，没有进行过投票，故都将选票投票给 A，同时更新自己的任期编号为 1:

候选人 A 在选举超时时间内赢得了大多数的选票，那么它将会成为本届任期内新的领导者：

节点 A 成为领导者后，会周期性地向其他跟随者发送心跳消息，通知其他节点我是领导者，以防止其他节点发起新的选举篡权：

选举规则

为了顺利选举出领导者，Raft 约定了选举规则：

• 领导者周期性地向所有跟随者发送心跳消息（心跳超时时间），用于通知大家我是领导者，阻止跟随者发起新的选举
• 如果在指定的时间内（选举超时时间），跟随者没有接收到领导者的消息，那么它就认为当前没有领导者，推举自己为候选人，发起新的选举
• 在一次选举中，赢得大多数选票的候选人，将晋升为领导者
• 在一个任期内，领导者会一直都是领导者，直到自身出现问题（例如节点宕机），或者出现网络延迟，其他节点发起新的一轮选举
• 在一次选举中，每个节点最多只能对一个任期编号投出一张选票，并按照先来先服务的原则进行投票。比如节点 C 的任期编号为 3，先收到节点 A 的投票请求，节点 A 的任期编号为 4；然后又接收到节点 B 的投票请求，节点 B 的任期编号为 4。那么，节点 C 会将任期 4 的唯一一张选票投给节点 A，当节点 C 再接收到节点 B 的投票请求时，节点 C 已经没有任期 4 的选票了
• 日志完整性高的跟随者（即，最后一条日志项对应的任期编号更高，索引号更大），拒绝投票给日志完整性低的候选人。例如，节点 B 的任期编号为 3，节点 C 的任期编号为 4，节点 B 最后一条日志项对应的任期编号为 3，节点 C 最后一条日志项对应的任期编号为 2。那么，当节点 C 请求节点 B 投票给自己时，节点 B 将拒绝投票。

节点通信

在 Raft，节点之间采用 RPC 进行通信，且包含两类 RPC：

• RequestVote RPC：请求投票 RPC，候选人在选举期间发起，用于通知其他节点投票
• AppendEntries RPC：日志复制 RPC，由领导者发起，用于复制日志和提供心跳消息。其中，心跳消息即为不包含日志项的日志复制 RPC 消息

超时时间

在选举中，可能会出现这种情况：在同一个任期内，多个候选人同时发起选举，选票被瓜分，导致没有一个候选人获得大多数的选票成为领导者，选举失败，即出现所谓的 a split vote。

为了降低出现 a split vote 的概率，Raft 引入了随机超时时间的方法，把超时时间分散开来，大多数情况下只有一个节点发起选举，避免同时发起选举的情况出现。在 Raft 中，包含两种超时时间：

• election timeout: 选举超时时间，跟随者等待成为候选人的超时时间，即跟随者在一段时间内没有接收到任何消息，那么它就假定集群内没有领导者，并开始新一轮的选举。选举超时时间为随机值 150 ~ 300 ms
• heartbeat timeout: 心跳超时时间，领导者发送心跳的时间间隔

日志复制

复制状态机

在 Raft 集群中，每个服务器可以看成是一个复制状态机（Replicated State Machine），如下图。 复制状态机通常基于复制日志（replicated log）实现。每个服务器存储一个包含一系列指令的日志，并且按顺序执行指令。由于日志都包含相同顺序的指令，状态机会按照相同的顺序执行指令，由于状态机是确定的（deterministic），因此状态机会产生相同的结果。 保持这些日志的一致性（consistent）正是共识（consensus）算法的工作。

图：复制状态机工作过程：1. 客户端请求；2. 共识模块执行共识算法进行日志复制，将日志复制至集群内各个节点；3. 日志应用到状态机；4. 服务端返回请求结果

在 Raft 中，指令以日志形式进行复制。集群内只有领导者才能接收客户端请求，其他所有节点都接收来自领导者的复制日志，以达到所有节点日志的一致，并最终达到状态的一致。

Raft 日志

上面我们提到在 Raft 中，指令以日志形式存在。日志由日志项（log entry）构成。日志项包含日志项索引、任期编号以及指令：

• 指令：客户端请求状态机需要执行的命令，例如指令 x <- 3 表示将 x 变量赋值为 3
• 日志项索引：日志项对应的索引值，是一个连续的、单调递增的整型号码
• 任期编号：创建这条日志项的领导者的任期编号

在上图可以看到，在一届领导者任期内，往往有多个日志项，例如，任期 1 有三个日志项，其日志项索引值分别为 1，2，3。

在 Raft 论文 In Search of an Understandable Consensus Algorithm (Extended Version) 中，多次提到 commit 和 apply 两词。其中，commit （提交）或 committed （已提交）针对的是日志，即日志项被成功复制到集群中大多数节点后，日志项处于 committed 状态，例如上图中索引 1 - 7 的日志项均处于 committed 状态；apply （应用）或 applied （已应用）针对的是状态机，即节点将日志项应用到状态机，真正改变节点变量的值。

日志复制

领导者接收到客户端请求后，接下来会进行日志复制的操作，过程如下图所示：

1. 客户端发送请求，领导者接收到客户端请求，根据请求中的指令，创建一个新的日志项，并附加（append）到领导者日志中
2. 领导者通过日志复制 RPC（AppendEntries RPC），将新的日志项复制至其他节点
3. 当领导者将日志项成功复制至集群大多数节点的时候，日志项处于 committed 状态，领导者可将这个日志项应用（apply）到自己的状态机中
4. 领导者将客户端请求结果返回给客户端
5. 当其他节点，即跟随者，接收到领导者的心跳消息，或新的日志复制消息（该消息均会附上领导者最大已提交日志项索引），如果跟随者发现领导者已提交某日志项，而自己还没将该日志项应用至状态机，那么，跟随者就将该日志项应用至自己的状态机中

从上面日志复制的过程可以看到，日志复制过程有点类似我们熟悉的二阶段提交（2PC）过程。与 2PC 不同的是，领导者接收到集群内大多数节点响应后，领导者就可以直接返回结果给客户端。这个优化，降低了客户端请求的延迟，将二阶段提交优化为一阶段提交。

为什么可以做这样的优化呢？就像上面所说的，由于领导者与跟随者之间的 RPC 通信 AppendEntries RPC，包括日志复制 RPC 和心跳 RPC，都包含了领导者最大已提交日志项索引，通过此日志项索引，跟随者可以在知道领导者已提交日志项，然后将该日志项按顺序应用至自己的状态机中，达到最终一致性。

日志一致性

Raft 日志具体如下特性：（本文不作具体证明，有兴趣的可以参考 Raft 论文 $5.3 部分，读者可只记住结论即可。）

• 如果不同日志中的两个日志项具有相同的索引值和任期编号，那么这两个日志项具有相同的指令
• 如果不同日志中的两个日志项具有相同的索引值和任期编号，那么这两个日志项之前的所有日志项也全部相同

在 Raft 算法中，通过领导者强制跟随者复制自己的日志项，来处理不一致的日志。

具体包括两个步骤：

1. 领导者通过日志复制 RPC 的一致性检查，找到跟随者与自己相同日志项的最大索引值。即，在该索引值之前的日志，领导者和跟随者是一致的，之后的日志，就不一致了
2. 领导者强制将跟随者该索引值之后的所有日志项删除，并将领导者该索引值之后的所有日志项同步至跟随者，以实现日志的一致

因此，处理领导者与跟随者日志不一致的关键是找出上述的最大索引值。

Raft 引入两个变量，来方便找出这一最大索引值：

• prevLogIndex：表示领导者当前需要复制的日志项，前面那一个日志项的索引值。例如，下图，如果领导者需要将索引值为 8 的日志项复制到跟随者，那么 prevLogIndex 为 7
• prevLogTerm：表示领导者当前需要复制的日志项，前面一个日志项的任期编号。例如，下图，如果领导者需要将索引值为 8 的日志项复制到跟随者，那么 prevLogTerm 为 4

下面以上图为例描述领导者如何通过日志复制 RPC 的一致性检查，找到跟随者与自己相同日志项的最大索引值：

1. 领导者通过日志复制 RPC 消息，发送当前自己最新日志项给跟随者，该消息的 prevLogIndex 为 7，prevLogTerm 为 4
2. 由于跟随者在其日志中，无法找到索引值为 7，任期编号为 4 的日志项，即跟随者的日志和领导者的不一致，故跟随者会拒绝接收新的日志项，返回失败
3. 这时，领导者递减 prevLogIndex 值为 6，prevLogTerm 变为 3，重新发送日志复制 RPC 消息
4. 此时，跟随者在其日志中，找到了索引值为 6，任期编号为 3 的日志项，故跟随者返回成功
5. 领导者收到跟随者成功返回后，知道在索引值为 6 的位置之前的所有日志项，均与自己的相同。于是通过日志复制 RPC ，复制并覆盖索引值为 6 之后的日志项，以达到跟随者的日志与领导者的日志一致

领导者通过日志复制 RPC 一致性检查，找到跟随者与自己相同日志项的最大索引值，然后复制并覆盖该索引值之后的日志项，以实现集群内各个节点日志的一致。 需要指出的是，日志复制过程中，只有跟随者的日志项会被领导者的日志覆盖更新，领导者的日志从不会被覆盖或删除。

成员变更

考虑一种场景，原来 Raft 集群中存在三个节点，现在需要增加2 个节点。那么，在这种情况下， Raft 算法如何能保证同一个任期内，只有一个领导者呢？

由于集群存在多个节点，因此，一次性原子地更新所有节点的配置是不可能的，集群在更新配置的过程中，可能会出现新旧配置的两个大多数：

这显然是跟 Raft 算法的规定相悖的。

为解决成员变更时领导者选举的问题，Raft 作者提出了几种方法。例如，可以先将集群原来所有节点关闭，更新其配置后，再启动新的集群。由于所有节点的配置都是固定的，Raft 可以保证同一任期只有一个领导者。不过此方法会导致每次成员变更时都需要关闭集群，导致集群无法对外提供服务。

单节点变更，即每次只允许增加或者删除一个节点，如果集群需要增加或者删除多个节点，可以通过执行多步的单节点操作实现。例如，如果需要将集群节点数量从 3 调整到 5 ，可以执行 2 次单节点变更操作，先将节点数量从 3 调整到 4，再从 4 调整到 5。

为什么单节点变更方法可以解决成员变更可能带来的同一个任期存在多个领导者的问题呢？

这是由于，不管集群节点数量是偶数，还是奇数，不管是增加节点，还是删除节点，集群中新旧配置的大多数都会存在重叠的情况，如下图所示：

上图蓝色区域表示采用旧配置的大多数，红色区域表示采用新配置的大多数。对于单节点变更来说，新旧配置的大多数都会存在节点重叠的情况。在 Raft 中，节点在同一个任期只有一张选票，因此，重叠的节点在同一个任期内不会投出两张选票，这样就不会出现同一任期存在两个领导者的现象。

需要指出的是，在出现分区错误，节点故障的情况下，如果并发执行单节点变更，可能会出现一次单节点变更还没完成，新一次单节点变更已经执行，导致集群出现 2 个领导者的问题。 为解决此问题，可以在领导者启动时，创建一个 O_OP 志项，只有当领导者将 O_OP 日志项应用后，再执行成员变更请求。