Raft 算法属于 Multi-Paxos 算法，它在兰伯特 Multi-Paxos 思想的基础上，做了一些简化和限制，比如增加了日志必须是连续的，只支持领导者、跟随者和候选人三种状态，在理解和算法实现上都相对容易许多。从本质上说，Raft 算法是通过一切以领导者为准的方式，实现一系列值的共识和各节点日志的一致。

Raft 算法是现在分布式系统开发首选的共识算法。绝大多数选用 Paxos 算法的系统（比如 Cubby、Spanner）都是在 Raft 算法发布前开发的，当时没得选；而全新的系统大多都选择了 Raft 算法（比如 Etcd、Consul、CockroachDB）。下面我们分别以领导者选举、日志复制、成员变更为核心，讲解 Raft 算法的原理。

领导者选举

假设我们有一个由节点 A、B、C 组成的 Raft 集群（如图所示），因为 Raft 算法一切以领导者为准，所以如果集群中出现了多个领导者，就会出现不知道谁来做主的问题。在这样一个有多个节点的集群中，在节点故障、分区错误等异常情况下，Raft 算法如何保证在同一个时间，集群中只有一个领导者呢？

Raft 算法支持领导者（Leader）、跟随者（Follower）和候选人（Candidate） 3 种状态。在任何时候，每一个服务器节点都处于这 3 个状态中的 1 个。

  • 跟随者：就相当于普通群众，默默地接收和处理来自领导者的消息，当等待领导者心跳信息超时时，就主动站出来，推荐自己当候选人。

  • 候选人：候选人将向其他节点发送请求投票（RequestVote）消息，通知其他节点来投票，如果赢得了大多数选票，就晋升当领导者。

  • 领导者：蛮不讲理的霸道总裁，一切以我为准，平常的主要工作内容就是 3 部分，处理写请求、管理日志复制和不断地发送心跳信息，通知其他节点领导者还活着。

需要注意的是，Raft 算法是强领导者模型，集群中只能有一个“霸道总裁”。

1. 选举领导者过程

首先，在初始状态下，集群中所有的节点都是跟随者的状态。
image.png
Raft 算法实现了随机超时时间的特性。即每个节点等待领导者节点心跳信息的超时时间间隔是随机的。通过上图可以看到，集群中还没有领导者，而节点 A 的等待超时时间最小（150ms），它会最先因为没有等到领导者的心跳信息，发生超时。这时，节点 A 就增加自己的任期编号，并推举自己为候选人，先给自己投上一张选票，然后向其他节点发送请求投票 RPC 消息，请它们选举自己为领导者。
image.png
如果其他节点接收到候选人 A 的请求投票 RPC 消息，在编号为 1 的这届任期内，也还没有进行过投票，那么它将把选票投给节点 A，并增加自己的任期编号。
image.png
如果候选人在选举超时时间内赢得了大多数的选票，那么它就会成为本届任期内新的领导者。
image.png
节点 A 当选领导者后，他将周期性地发送心跳消息，通知其他服务器我是领导者，阻止跟随者再发起新一轮的选举，篡权。
image.png
下面我们再来分析下，在领导者选举过程中的一些实现细节：

2. 选举领导者实现

2.1 节点间如何通讯？

在 Raft 算法中，服务器节点间的沟通联络采用的是远程过程调用（RPC），在领导者选举中，需要用到这样两类的 RPC：

  • 请求投票（RequestVote）RPC，是由候选人在选举期间发起，通知各节点进行投票；
  • 日志复制（AppendEntries）RPC，是由领导者发起，用来复制日志和提供心跳消息。

注意，日志复制 RPC 只能由领导者发起，这是实现强领导者模型的关键。

2.2 什么是任期？

我们知道，议会选举中的领导者是有任期的，领导者任命到期后，要重新开会再次选举。Raft 算法中的领导者也是有任期的，每个任期由单调递增的数字（任期编号）标识，比如节点 A 的任期编号是 1。任期编号是随着选举的举行而变化的。

  • 跟随者在等待领导者心跳信息超时后，推举自己为候选人时，会增加自己的任期号，比如节点 A 的当前任期编号为 0，那么在推举自己为候选人时，会将自己的任期编号增加为 1。

  • 如果一个服务器节点，发现自己的任期编号比其他节点小，那么它会更新自己的编号到较大的编号值。比如节点 B 的任期编号是 0，当收到来自节点 A 的请求投票 RPC 消息时，因为消息中包含了节点 A 的任期编号，且编号为 1，那么节点 B 将把自己的任期编号更新为 1。

在 Raft 算法中约定，如果一个候选人或领导者，发现自己的任期编号比其他节点小，那么它会立即恢复成跟随者状态。比如分区错误恢复后，任期编号为 3 的领导者节点 B，收到来自新领导者的，包含任期编号为 4 的心跳消息，那么节点 B 将立即恢复成跟随者状态。此外，还约定了如果一个节点接收到一个包含较小的任期编号值的请求，那么它会直接拒绝这个请求。

2.3 选举有哪些规则？

在 Raft 算法中约定的选举规则，主要有这样几点。

  • 领导者周期性地向所有跟随者发送心跳消息，以阻止跟随者发起新的选举。
  • 如果在指定时间内，跟随者没有接收到来自领导者的消息，那么它就认为当前没有领导者，推举自己为候选人，发起领导者选举。
  • 在一次选举中，赢得大多数选票的候选人，将晋升为领导者。
  • 在一个任期内，领导者一直都会是领导者，直到它自身出现问题，比如宕机或网络延迟，其他节点会发起一轮新的选举。
  • 在一次选举中，每一个服务器节点最多会对一个任期编号投出一张选票，并且按照“先来先服务”的原则进行投票。
  • 日志完整性高的跟随者（也就是最后一条日志项对应的任期编号值更大，索引号更大），拒绝投票给日志完整性低的候选人。

其实在选举中，除了选举规则外，我们还需要避免一些会导致选举失败的情况，比如同一任期内，多个候选人同时发起选举，导致选票被瓜分，选举失败。那在 Raft 算法中如何避免这个问题呢？答案就是随机超时时间。

2.4 随机超时时间

在议会选举中，常出现未达到指定票数，选举无效，需要重新选举的情况。在 Raft 算法的选举中，也存在类似的问题，那它是如何处理选举无效的问题呢？其实，Raft 算法巧妙地使用随机选举超时时间的方法，把超时时间都分散开来，在大多数情况下只会有一个服务器节点先发起选举，而不是同时发起选举，这样就能减少因选票瓜分导致选举失败的情况。

在 Raft 算法中，随机超时时间是有 2 种含义的：

  • 跟随者等待领导者心跳信息超时的时间间隔，是随机的；
  • 如果候选人在一个随机时间间隔内，没有赢得过半票数，那么选举无效了，候选人发起新一轮的选举，也就是说，等待选举超时的时间间隔，是随机的。

Raft 算法和兰伯特的 Multi-Paxos 不同之处，主要有两点。首先，在 Raft 中不是所有节点都能当选领导者，只有日志较完整的节点（也就是日志完整度不比半数节点低的节点）才能当选领导者；其次，在 Raft 中日志必须是连续的。

日志复制

在 Raft 算法中，副本数据是以日志的形式存在的，领导者接收到来自客户端写请求后，处理写请求的过程就是一个复制和应用日志项到状态机的过程。那 Raft 是如何复制日志，又是如何实现日志的一致的呢？

1. 如何理解日志？

副本数据是以日志的形式存在的，日志是由日志项组成，日志项其实是一种数据格式，它主要包含用户指定的数据，也就是指令（Command），还包含一些附加信息，比如索引值（Log index）、任期编号（Term）。
image.png

  • 指令：一条由客户端请求指定的、状态机需要执行的指令，可以理解成客户端指定的数据。
  • 索引值：日志项对应的整数索引值，用来标识日志项的，是一个连续、单调递增的整数。
  • 任期编号：创建这条日志项的领导者的任期编号。

注意，一届领导者任期内，往往有多条日志项，而且日志项的索引值是连续的。

2. 如何复制日志？

你可以把 Raft 的日志复制理解成一个优化后的二阶段提交（将二阶段优化成了一阶段），减少了一半的往返消息，也就是降低了一半的消息延迟。那日志复制的具体过程是什么呢？

首先，领导者进入第一阶段，通过日志复制（AppendEntries）RPC 消息，将日志项复制到集群其他节点上。接着，如果领导者接收到大多数的“复制成功”响应后，它将日志项应用到它的状态机，并返回成功给客户端。如果领导者没有接收到大多数的“复制成功”响应，那么就返回错误给客户端。

领导者将日志项应用到它的状态机不需要通知跟随者应用日志项吗？

这是 Raft 中的一个优化，领导者不直接发送消息通知其他节点应用指定日志项。因为领导者的日志复制 RPC 消息或心跳消息，包含了当前最大的，将会被提交（Commit）的日志项索引值。所以通过日志复制 RPC 消息或心跳消息，跟随者就可以知道领导者的日志提交位置信息，然后将这条日志项应用到它的状态机。这个优化，降低了处理客户端请求的延迟，将二阶段提交优化为了一段提交，降低了一半的消息延迟。
image.png

  • 接收到客户端请求后，领导者基于客户端请求中的指令，创建一个新日志项，并附加到本地日志中。
  • 领导者通过日志复制 RPC，将新的日志项复制到其他的服务器。
  • 当领导者将日志项成功复制到大多数的服务器上时，领导者会将这条日志项应用到它的状态机中。
  • 领导者将执行的结果返回给客户端。
  • 当跟随者接收到心跳信息或新的日志复制 RPC 消息后，如果跟随者发现领导者已经提交了某条日志项，而它还没应用，那么跟随者就将这条日志项应用到本地的状态机中。

上面是一个理想状态下的日志复制过程。在实际复制日志时，可能会遇到进程崩溃、服务器宕机等问题，这些问题会导致日志不一致。那么在这种情况下，Raft 算法是如何处理不一致日志，实现日志的一致的呢？

3. 如何实现日志一致？

在 Raft 算法中，领导者通过强制跟随者直接复制自己的日志项，处理不一致日志。也就是说，Raft 是通过以领导者的日志为准，来实现各节点日志的一致的。具体有 2 个步骤。

  • 首先，领导者通过日志复制 RPC 的一致性检查，找到跟随者节点上，与自己相同日志项的最大索引值。也就是说，这个索引值之前的日志，领导者和跟随者是一致的，之后的日志是不一致的了。


  • 然后，领导者强制跟随者更新覆盖的不一致日志项，实现日志的一致。

image.png

  • PrevLogEntry：表示当前要复制的日志项，前面一条日志项的索引值。
  • PrevLogTerm：表示当前要复制的日志项，前面一条日志项的任期编号。

从上面步骤中你可以看到，领导者通过日志复制 RPC 一致性检查，找到跟随者节点上与自己相同日志项的最大索引值，然后复制并更新覆盖该索引值之后的日志项，实现了各节点日志的一致。注意，跟随者中的不一致日志项会被领导者的日志覆盖，而且领导者不会覆盖或者删除自己的日志。

集群成员变更

假设我们有一个由节点 A、B、C 组成的 Raft 集群，现在我们需要增加数据副本数，增加 2 个副本（也就是增加 2 台服务器），扩展为由节点 A、B、C、D、E， 5 个节点组成的新集群：
image.png
那么 Raft 算法是如何保障在集群配置变更时，集群能稳定运行，不出现 2 个领导者呢？

1. 成员变更的问题

在集群中进行成员变更的最大风险是，可能会同时出现 2 个领导者。比如在进行成员变更时，节点 A、B 和 C 之间发生了分区错误，节点 A、B 组成旧配置中的“大多数”，也就是变更前的 3 节点集群中的“大多数”，那么这时的领导者（节点 A）依旧是领导者。另一方面，节点 C 和新节点 D、E 组成了新配置的“大多数”，也就是变更后的 5 节点集群中的“大多数”，它们可能会选举出新的领导者（比如节点 C）。那么这时，就出现了同时存在 2 个领导者的情况。
image.png
那怎样解决成员变更的问题呢？最常用的方法就是单节点变更。

2. 单节点变更

单节点变更，就是通过一次变更一个节点实现成员变更。如果需要变更多个节点，那你需要执行多次单节点变更操作。比如将 3 节点集群扩容为 5 节点集群，这时你需要执行 2 次单节点变更，就像下图的样子。
image.png
假设集群配置为 [A, B, C]，节点 A 是领导者，我们先向集群中加入节点 D，这意味着新配置为 [A, B, C, D]。成员变更，是通过这么两步实现的：

  • 第一步，领导者（节点 A）向新节点（节点 D）同步数据；
  • 第二步，领导者（节点 A）将新配置 [A, B, C, D] 作为一个日志项，复制到新配置中所有节点上，然后将新配置的日志项应用到本地状态机，完成单节点变更。

在变更完成后，现在的集群配置就是 [A, B, C, D]，我们再向集群中加入节点 E，步骤同上。这样一来，我们就通过一次变更一个节点的方式，完成了成员变更，保证了集群中始终只有一个领导者，而且集群也在稳定运行，持续提供服务。