这篇文章总结了迭戈·奥加罗（Diego Ongaro）和约翰·奥斯特豪特（John Ousterhout）在论文《寻找可理解的共识算法》中提出的Raft共识算法。所有拉引语均来自该论文。

在正常操作中，只有一个领导者，其他所有服务器都是跟随者。

追随者是被动的：他们自己不发出请求，而只是响应领导者和候选人的请求。

领导者处理所有客户请求（如果客户联系关注者，则关注者将其重定向到领导者）。

第三种状态，候选人，用于选举新领导人。

Raft把时间分成条款任意长度的每开始一个选举。

如果候选人在选举中获胜，则在剩余任期中仍将保持领导地位。

如果表决分裂，则该任期在没有领导人的情况下结束。

本项数单调增加。每个服务器存储当前的条款编号，该编号也在每次通信中交换。

如果一台服务器的当前期限小于另一台服务器，则它将其当前期限更新为较大的值。

如果候选人或领导者发现其任期已过时，它将立即恢复为关注者状态。

如果服务器收到带有过期条款编号的请求，则服务器将拒绝该请求。

Raft利用两个远程过程调用（RPC）来执行其基本操作。

  • 候选人在选举期间使用RequestVotes
  • 领导者将AppendEntries用于复制日志条目，并用作检测信号（检查服务器是否启动的信号-它不包含任何日志条目）

领导人选举

领导者定期向其追随者发送心跳，以保持权威。

当跟随者在等待领导者的心跳后超时时，将触发领导者选举。

该关注者转换为候选状态并增加其任期编号。

在为自己投票之后，它与集群中的其他进程并行地发出RequestVotes RPC。

可能有以下三种结果：

  1. 候选人从大多数服务器中获得选票并成为领导者。然后，它将心跳消息发送给群集中的其他人以建立权限。
  2. 如果其他候选人收到AppendEntries RPC，他们将检查学期号。如果术语数字大于自己的数字，则他们接受服务器作为领导者并返回跟随者状态。如果术语数量较小，则他们拒绝RPC，并且仍然是候选人。
  3. 候选人既不输也不赢。如果同时有多个服务器成为候选服务器，则可以在没有明显多数的情况下进行表决。在这种情况下，其中一名候选人超时后便会开始新的选举。

Raft使用随机的选举超时来确保分割票很少发生，并且可以快速解决。

为了避免首先产生多张选票，从固定的时间间隔（例如150-300毫秒）中随机选择选举超时。

这会分散服务器，因此在大多数情况下，只有一台服务器会超时。

它会赢得选举并在其他任何服务器超时之前发送心跳信号。

使用相同的机制来处理拆分投票。

每位候选人在选举开始时都会重新启动其随机选举超时时间，并等待该超时时间过去后才开始下一次选举。

这减少了在新选举中再次进行分裂表决的可能性。

日志复制

客户端请求现在被假定为仅写。

每个请求都包含一个命令，该命令理想地由所有服务器的复制状态机执行。

领导者收到客户请求后，会将其作为新条目添加到自己的日志中。日志中的每个条目：

  • 包含客户端指定的命令
  • 有一个索引来标识日志中条目的位置（索引从1开始）
  • 有一个术语号可以从逻辑上标识何时写入条目

它需要将条目复制到所有跟随者节点，以保持日志一致。

领导者将AppendEntries RPC并行发布到所有其他服务器。领导者将重试此操作，直到所有关注者安全地复制新条目为止。

当条目由创建它的领导者复制到大多数服务器时，就被视为已提交。

所有以前的条目，包括由早期领导者创建的条目，也都视为已提交。负责人一旦提交就执行该条目，并将结果返回给客户端。

领导者在其日志中维护它知道要提交的最高索引，并将其与AppendEntries RPC一起发送给其跟随者。一旦关注者发现条目已提交，它将按顺序将条目应用于其状态机。

Raft维护以下属性，它们共同构成了Log Matching属性 如果不同日志中的两个条目具有相同的索引和术语，则它们存储相同的命令。 如果不同日志中的两个条目具有相同的索引和术语，则所有先前条目中的日志都相同。

发送AppendEntries RPC时，领导者会在新条目之前紧跟条目的术语号和索引。如果关注者在其自己的日志中找不到该条目的匹配项，它将拒绝添加新条目的请求。

通过一致性检查，领导者可以得出结论，只要AppendEntries成功从跟随者返回，它们就会拥有相同的日志，直到RPC中包含索引为止。

但是，面对领导者崩溃，领导者和追随者的日志可能会变得不一致。

在Raft中，领导者通过强迫追随者的日志重复自己的日志来处理不一致之处。

这意味着跟随者日志中的冲突条目将被领导者日志中的条目覆盖。

领导者试图找到其日志与追随者的日志匹配的最后一个索引，删除多余的条目（如果有），并添加新的条目。

领导者为每个关注者维护一个nextIndex，这是领导者将发送给该​​关注者的下一个日志条目的索引。

领导者首次掌权时，它将所有nextIndex值初始化为刚好在其日志中的最后一个索引之后的索引。

每当AppendRPC因跟随者失败而返回时，领导者都会递减nextIndex并发出另一个AppendEntries RPC。

最终，nextIndex 将达到日志收敛的值。

发生这种情况时，AppendEntries将成功执行，它可以删除无关的条目（如果有），并从领导者日志中添加新的条目（如果有）。

因此，来自跟随者的成功AppendEntries可以确保领导者的日志与之保持一致。

通过这种机制，领导者在上电时无需采取任何特殊措施即可恢复日志的一致性。

它只是开始正常运行，并且响应于Append-Entries一致性检查失败，日志会自动收敛。

领导者永远不会覆盖或删除其自己的日志中的条目。

安全

Raft确保某个术语的领导者已提交其日志中所有先前术语的条目。

这是确保所有日志一致并且状态机执行同一组命令所必需的。

在领导者选举期间，RequestVote RPC包含有关候选人日志的信息。

如果选民发现其日志比该候选人最新，则不会投票。

Raft通过比较日志中最后一个条目的索引和术语来确定两个日志中哪个是最新的。

如果日志中的最后一个条目具有不同的术语，则带有较新术语的日志是最新的。

如果日志以相同的术语结尾，则以更长的日志为准。

集群成员

为了确保配置更改机制的安全，在过渡期间必须没有任何可能在同一任期内选举两名领导者的意义。

不幸的是，任何将服务器直接从旧配置切换到新配置的方法都是不安全的。

Raft使用两阶段方法来更改集群成员。

首先，它切换到称为联合共识的中间配置。

然后，一旦提交，它将切换到新配置。

联合共识允许单个服务器在不同时间在配置之间转换，而不会影响安全性。

此外，联合共识允许群集在整个配置更改期间继续为客户请求提供服务。

联合共识将新旧配置组合如下：

  • 两种配置中的日志条目均复制到所有服务器
  • 任何新旧服务器都可以成为领导者
  • 协议需要将旧配置与新配置分开的多数

领导者收到配置更改消息时，将存储并复制用于加入共识C <old，n ew> 的条目。

服务器始终使用其日志中的最新配置来做出决定，即使未提交也是如此。

提交联合共识后，只有日志中_具有C <_旧，新>的服务器才能成为领导者。

现在，领导者可以安全地创建描述C 的日志条目并将其复制到集群。

同样，此配置将在每台服务器上立即生效。

当根据C 的规则提交了新配置时，旧配置将不相关，并且可以关闭不在新配置中的服务器。

可以在此处找到有关Raft工作原理的出色可视化效果。

可以在此处找到更多材料，例如演讲，演讲，相关论文和开源实现。

我只深入研究了构成Raft的基本算法及其提供的安全性保证的细节。

本文包含更多细节，并且由于作者的主要目标是可理解性，因此它非常容易上手。

我绝对建议您阅读它，即使您以前从未阅读过任何其他论文。