分布式协议之 Raft 算法

Raft 是一种分布式共识算法。相对于之前的 Paxos 协议，它的设计易于理解。它解决了即使面对故障也使多个服务器在共享状态上达成一致的问题。共享状态通常是复制日志支持的数据结构。只要大多数服务器都处于运行状态，我们就需要系统能够完全运行。

Raft 通过选举集群中的一位 leader 来工作。leader 负责接受 client 请求并管理将日志复制到其他服务器。数据仅在一个方向上流动：从 leader 流向其他服务器。

Raft 将共识分解为三个子问题：

leader 选举：如果现有 leader 失败，则需要选举一名新 leader。
日志复制：leader 需要通过复制使所有服务器的日志与其自己的服务器保持同步。
安全性：如果其中一台服务器已在特定索引上提交了日志条目，则其他任何服务器都无法对该索引应用其他日志条目。

基础

每个服务器都处于以下三种状态之一：leader，follower 或 candidate。

oN6xZLkKQrVnaWWlp7I8w9aep2NNgMz5fR9D

在正常操作中，只有一个 leader，其他所有服务器都是 follower。follower 是被动的：他们自己不发出请求，而只是响应 leader 和 candidate 的请求。leader 处理所有客户请求（如果客户联系 follower，则 follower 将其重定向到 leader）。第三种状态，candidate，用于选举新 leader。

Raft 将时间分为任意长度，每个长度以选举开始。如果 candidate 赢得选举，则在剩余任期中仍将是 leader。如果表决分裂，则该任期在没有 leader 的情况下结束。

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

.. 如果一台服务器的当前期限小于另一台服务器，则它将其当前期限更新为较大的值。如果 candidate 或 leader 发现其任期已过时，它将立即恢复为 follower 状态。如果服务器收到带有过期条款编号的请求，则该服务器将拒绝该请求。

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

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

leader 选举

leader 定期向其 follower 发送心跳，以保持权威。当 follower 在等待 leader 的心跳后超时时，将触发 leader 选举。该 follower 转换为 candidate 状态并增加其任期编号。在为自己投票之后，它与集群中的其他进程并行地发出 RequestVotes RPC。可能有以下三种结果：

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

Raft 使用随机的选举超时来确保分割票很少发生，并且可以快速解决。为了避免一票分裂，首先从固定间隔（例如 150-300 毫秒）中随机选择选举超时。这样会分散服务器，因此在大多数情况下，只有一台服务器会超时；它会赢得选举并在其他任何服务器超时之前发送心跳信号。使用相同的机制来处理拆分投票。每位 candidate 在选举开始时都会重新启动其随机选举超时时间，并等待该超时时间过去后才开始下一次选举；这减少了在新选举中再次进行分裂表决的可能性。

日志复制

client 请求现在假定为仅写。每个请求都包含一个命令，该命令理想地由所有服务器的复制状态机执行。leader 收到客户请求后，会将其作为新条目添加到自己的日志中。日志中的每个条目：

包含 client 指定的命令
有一个索引来标识日志中条目的位置（索引从 1 开始）
有一个 term 号可以从逻辑上识别条目的写入时

它需要将条目复制到所有 follower 节点，以保持日志一致。leader 将 AppendEntries RPC 并行发布到所有其他服务器。leader 将重试此操作，直到所有 follower 安全地复制新条目为止。

当条目由创建它的 leader 复制到大多数服务器时，就被视为已提交。所有以前的条目，包括由早期 leader 创建的条目，也都视为已提交。负责人一旦提交就执行该条目，并将结果返回给 client。

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

Raft 维护以下属性，它们共同构成了日志匹配属性。

如果不同日志中的两个条目具有相同的索引和 term，那么它们存储的是同一个命令。
如果不同日志中的两个条目具有相同的索引和 term，那么在前面的所有条目中，日志是相同的。

当发送 AppendEntries RPC 时，leader 包括紧接在新条目之前的条目的 term 号和索引。如果 follower 在自己的日志中找不到与该条目匹配的条目，它就会拒绝附加新条目的请求。

这种一致性检查可以让 leader 得出这样的结论：每当 AppendEntries 从 follower 成功返回时，它们的日志都是相同的，直到 RPC 中包含的索引。

但是在面对 leader 崩溃的情况下，leader 和 follower 的日志可能会变得不一致。

在 Raft 中，leader 通过强制 follower 的日志复制自己的日志来处理不一致的情况。这意味着，follower 日志中的冲突条目将被 leader 日志中的条目覆盖。

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

leader 为每个 follower 维护一个 nextIndex，它是 leader 将发送给该 follower 的下一个日志条目的索引。当 leader 第一次上电时，它将所有的 nextIndex 值初始化为其日志中最后一条后的索引。

每当 AppendRPC 返回一个 follower 失败时，leader 就会递减 nextIndex，并发出另一个 AppendEntries RPC。最终，nextIndex 会达到一个值，在这个值上，日志会趋于一致。当这种情况发生时，AppendEntries 将会成功，它可以从 leader 的日志中删除无关的条目（如果有的话），并添加新的条目（如果有的话）。因此，从一个 follower 成功的 AppendEntries 可以保证 leader 的日志与它一致。

通过这种机制，leader 在上电时不需要采取任何特殊的操作来恢复日志一致性。它只需开始正常的操作，日志就会自动收敛，以应对 Append-Entries 一致性检查的失败。leader 从不覆盖或删除自己日志中的条目。

安全性

Raft 确保一个 term 的 leader 在其日志中承诺了以前所有 term 的条目。
Raft 确保一个 term 的 leader 在其日志中已经提交了以前所有 term 的条目。这是为了确保所有的日志是一致的，并且状态机执行相同的命令集。

在 leader 选举期间，RequestVote RPC 包含了 candidate 的日志信息。如果投票者发现它的日志比 candidate 的更新，它就不会投给它。

Raft 通过比较两个日志中最后条目的索引和 term 来确定哪个日志更及时。如果日志的最后条目有不同的 term，那么 term 较晚的日志更及时。如果两个日志的最后条目有相同的 term，那么哪个日志更长，哪个日志就更最新。

集群成员

为了使配置变更机制安全，在过渡期间必须没有任何一点可以让两个 leader 在同一 term 内当选。不幸的是，任何服务器直接从旧配置切换到新配置的方法都是不安全的。
Raft 使用了一个两阶段的方法来改变集群成员。首先，它切换到一个称为联合共识的中间配置。然后，一旦这一点被满足，它就会切换到新的配置。

联合共识允许各个服务器在不同的时间在配置之间转换，而不影响安全。此外，联合共识还允许集群在整个配置变化过程中继续服务于 client 请求。
联合共识将新旧配置结合起来，具体如下。