寻找可理解的共识算法（扩展版）

论文地址：寻找可理解的共识算法（扩展版）

这里有一些值得感谢的东西：一个一致的算法，其主要目标是让人理解！作者还声称它为构建分布式系统提供了更好的基础（比以前的算法）。
Raft是一种管理复制日志的通用算法。它产生的结果相当于（多）PaxOS，它与PaxOS一样有效，但其结构不同于PaxOS，这使得RAFT比PAXOS更易于理解，也为构建实际系统提供了更好的基础。
Raft在精神上与Viewstamped复制最接近，但有几个新功能：

• 强大的领导能力，其中日志条目只能从领导流到其他服务器。
• 领导人选举期间的随机计时
• 管理成员变更的联合共识方法。
• 除了本文中的散文描述外，在TLA+中对其进行了形式化的描述，并证明了其协商机制的安全性。

Raft首先选举一位杰出的领导者，然后让领导者全权负责管理复制的日志，从而实现共识。leader接受来自客户机的日志条目，将它们复制到其他服务器上，并告诉服务器何时可以安全地将日志条目应用到其状态机。
Raft提供5项关键保证：

• 选举安全在一个特定的任期内最多只能选出一位领导人。
• Leader Append Only 领导者从不覆盖或删除其日志中的条目，它只追加
• 日志匹配如果两个日志包含一个具有相同索引和术语的条目，则在该索引之前，日志是相同的
• Leader完整性如果日志条目是在给定的期限内提交的，那么该条目将在leaders的日志中提交给所有编号更高的期限。
• 状态机安全如果服务器已将给定索引处的日志项应用于其状态机，则其他服务器将永远不会对同一索引应用不同的日志项。

Raft把时间分成若干个协议条件，每个协议条件都以选举开始。如果一个候选人赢得了选举，他们将在余下的任期内继续担任领导人。如果一次选举产生了分裂投票，那么任期结束时没有领袖，新的任期开始。术语数随时间单调增加，并在每次通信中交换。服务器可能处于以下三种状态之一：领导者、追随者或候选人。如果一个领导人或候选人确定他们自己的任期数字落后，它将立即恢复到追随者的地位。

Raft的基本一致性算法仅依赖于两种消息（RPC）类型：RequestVote和AppendEntries。RequestVote消息由候选人在选举期间发起，AppendEntries消息由领导人发起以传输日志条目，并作为心跳。第三种消息类型InstallSnapshot也用于在服务器之间传输快照。
完整的草稿纸可读性很强，长达18页。我将在这篇文章中重点介绍核心算法，但如果你有兴趣的话，可以继续阅读全文。

领导人选举

• 服务器以跟随者的身份启动，只要它们接收到定期的AppendEntries RPC（一个引导者可以发送一个没有日志项的AppendEntries RPC作为心跳）。如果某个跟随者在超过选举超时时间后没有收到任何通信，则该跟随者将开始选举。

• follower增加其当前项，转换为候选状态，并将RequestVote rpc发送到其他每个服务器。如果它在同一任期内获得大多数服务器的投票，那么它将转换为leader。然后，它将heartbeat消息发送到所有其他服务器以建立其权限。

• 处于候选状态的服务器还可以接收请求投票rpc。如果该术语小于服务器本身的术语，则拒绝该消息。否则，候选人承认领导人是合法的，并返回跟随国。
• 如果候选人既不赢也不输，它将超时并开始另一轮请求投票rpc。

当处于leader或follower状态之一的服务器接收到RequestVote RPC时，它将按如下方式响应：

• 如果投票中的任期少于自己的任期，它将拒绝上述投票。
• 如果服务器在这一任期内还没有投票给其他人，并且候选人的日志至少和自己的日志一样是最新的，那么它将授予投票权。

随机选举超时是用来确保分裂选票是罕见的，他们可以很快解决。每个候选人在每次选举开始时将其选举超时重置为某个固定间隔（例如150-300毫秒）的随机值。
领导人选举是Raft最关键的方面。只要系统满足以下定时要求，Raft将能够选出并保持稳定的领导者：广播时间≪选择超时≪MTBF。在这个不等式中，broadcastTime是一个服务器并行地向集群中的每个服务器发送rpc并接收其响应所需的平均时间。
Raft rpc通常需要0.5到20毫秒（包括将信息持久化到稳定存储所需的时间），因此选择超时可能在100到500毫秒之间。
选举就是一个例子，说明了可理解性如何指导我们在设计方案之间的选择。最初我们计划使用一个排名系统：给每个候选人分配一个唯一的排名，用于在竞争对手之间进行选择……我们对算法进行了多次调整，但每次调整后都会出现新的角点情况。最后我们得出结论，随机重试方法是更明显和可理解的。

日志复制
当leader接收到一个客户机请求时，它将命令作为一个新条目附加到其日志中，然后发出AppendEntries RPCs，将该条目复制到所有其他服务器。当条目已安全地复制到大多数服务器时，引导程序将该条目应用于其状态机并将结果返回给客户端。leader无限期地重试AppendEntries rpc，直到所有followers最终存储所有日志条目。每个日志条目都存储一个状态机命令以及当领导接收到条目时术语的术语号。
提交一个条目还将提交领导日志中以前的所有条目，包括以前领导创建的条目。一旦一个跟随者知道一个日志条目已经提交，它就会将该日志条目应用到它的本地状态机（按日志顺序）。
Raft维护以下属性，这些属性共同构成日志匹配属性：（1）如果不同日志中的两个条目具有相同的索引和术语，则它们存储相同的命令；（2）如果不同日志中的两个条目具有相同的索引和术语，则前面所有条目中的日志都相同。
发送AppendEntries RPC时，前导符在其日志中包含紧跟在新项之前的项的索引和项。如果跟随者找不到匹配的条目，则拒绝新条目。
一致性检查充当一个归纳步骤：日志的初始空状态满足日志匹配属性，并且一致性检查在扩展日志时保留日志匹配属性。因此，当neverappendentries成功返回时，领导知道跟随者的日志与通过新条目进行的自己的日志相同。
Leader和follower崩溃会使日志处于不一致的状态，这可以通过强制follower s的日志复制Leader的日志来解决。

查找匹配的最新日志项的机制很简单：如果日志不匹配，跟踪者将拒绝AppendEntries RPC。然后，leader从其日志中前面的一个条目开始重试AppendEntries。最终，这个过程到达了日志匹配的点。
有了这个机制，当出现问题时，领导者不需要采取任何特殊操作来恢复日志一致性。它只是开始正常操作，日志会自动收敛，以响应附加条目一致性检查的失败。引线从不覆盖或删除其日志中的条目（leader Append Only属性）。
如果某个领导在提交条目之前崩溃，则未来的领导将尝试完成复制。然而，未来的领导者不能安全地得出这样的结论：一旦一个条目存储在大多数服务器上，它就会被提交（请参阅本文中的示例序列，以说明为什么会出现这种情况）。为了消除这些问题…
…Raft从不通过计算副本来提交以前术语中的日志条目。通过计算副本，仅提交来自领导者当前术语的日志条目；一旦以这种方式提交了来自当前术语的条目，则由于“日志匹配”属性，将间接提交所有以前的条目。

群集成员身份更改
为了确保配置变更机制的安全性，在过渡期间不应有两位领导人有可能在同一任期内当选的情况。不幸的是，任何服务器直接从旧配置切换到新配置的方法都是不安全的。不可能同时原子地切换所有服务器，因此集群在转换期间可能会分成两个独立的多数。
Raft通过一个称为joint consumonse的中间状态来处理这个问题，这个状态将新旧配置结合在一起。

• 日志项将复制到联盟中的所有服务器
• 两种配置中的任何服务器都可以作为领导者
• 协议要求从旧的和新的结构中分离出多数。
• 提交联合一致状态后，leader可以创建一个描述新配置的日志条目并将其复制到集群，从而完成转换。围绕这一切如何工作的规则可以在论文中找到，并且可能是整个协议中最微妙的部分。

为了使跟随者的日志与其自身的日志保持一致，领导者必须找到两个日志一致的最新日志条目，删除该点之后跟随者日志中的任何条目，并在该点之后将领导者的所有条目发送给跟随者。所有这些操作都是响应AppendEntries rpc执行的一致性检查而发生的。

奖励项目
本文的扩展版包含了关于日志压缩（使用InstallSnapshot RPC使落后于leaders快照点的follower恢复速度）和客户机交互的额外部分。
当一个跟踪者接收到这个RPC的快照时，它必须决定如何处理它现有的日志条目。通常快照将包含收件人日志中尚未包含的新信息。在这种情况下，跟踪者丢弃其整个日志；所有日志都被快照所取代，并且可能有与快照冲突的未提交条目。如果跟随者接收到描述其日志前缀的快照（由于重新传输或错误），则快照覆盖的日志条目将被删除，但快照之后的条目仍然有效，必须保留。
如果服务器在提交项目后，但在响应客户端之前崩溃（或回复丢失或延迟），则客户端可以重新提交请求。如果客户机为每个命令分配唯一的序列号，那么状态机可以跟踪这些序列号，并在看到重复的请求时立即响应，而无需重新执行请求。

最后，我们将指导如何确保线性化读取：
线性化读取不能返回过时的数据，Raft需要两个额外的预防措施来保证这一点，而不使用日志。首先，领导者必须拥有提交条目的最新信息。Leader完备性属性保证Leader拥有所有提交的条目，但是在其任期开始时，它可能不知道哪些条目是提交的。为了找出答案，它需要从它的术语中提交一个条目。Raft通过让每个领导在任期开始时在日志中提交一个空的no-op条目来处理这个问题。其次，在处理只读请求之前，领导者必须检查其是否已被废黜（如果最近的领导者已当选，则其信息可能已过时）。Raft通过让leader在响应只读请求之前与大多数集群交换heartbeat消息来处理这个问题。