零基础入门分布式系统 6. Consensus

本章我们回到全序广播的问题。全序广播非常适合实现状态机复制。实现全序广播的一种方法是指定一个节点作为leader领导者，并通过它转发所有消息。然后领导者通过FIFO广播来分发消息，这就足以确保所有节点以相同的顺序传递相同的消息序列。

然而，这种方法的最大问题是领导者可能单点故障：一旦领导者不可用，整个系统就会停机。一个解决方法是人工干预：如果领导者变得不可用，立刻通知操作员，然后操作员重新配置所有的节点，使用一个不同的节点作为新的领导者。这个过程被称为failover 故障转移，事实上它被应用于许多数据库系统中。

在领导者有计划性的不可用时，故障转移是一个有效的办法。例如，当需要重新启动领导者来安装更新。然而，对于突发和计划外的领导者中断（例如，崩溃、硬件故障或网络问题），故障转移受制于这样一个事实：人类在执行手动切换的速度上是有限的。即使在最好的情况下，操作员也需要几分钟的时间来响应，在此期间，系统无法处理任何请求。

这就导致了一个问题：在旧的领导者不可用时，有没有办法把领导权从一个节点自动转移到另一个节点？答案是肯定的，这正是共识算法的作用。

6.1 Introduction to consensus

共识问题传统上被表述为：几个节点想就一个值达成协议agreement。一个或多个节点可以提出propose一个值，然后共识算法将决定decide这些值中的一个。该算法保证所选取的值是所提出的值之一，所有节点都决定相同的值（有问题的节点除外，它们可能无法做出决定），并且决定是最终的（一个节点一旦决定了一个值，就不会改变主意）。

已有正式证明，共识和全阶广播是相互等价的[Chandra and Toueg, 1996]。

• 为了把全序广播变成共识，某个想要提出数值的节点会进行广播，而全序广播传递的第一个信息被视为决定的数值。
• 为了把共识变成全序广播，我们使用一个单独的共识协议实例来决定要传递消息的轮次，如第一、第二、第三……一个想要广播消息的节点在这些轮次的共识中提出消息。然后，共识算法确保所有节点都同意要传递消息的顺序。

两个最著名的共识算法是Paxos[Lamport, 1998]和Raft[Ongaro and Ousterhout, 2014]。在Paxos最初的表述中，Paxos只提供对单一数值的共识算法，而Multi-Paxos算法是Paxos的一个通用形式，它提供FIFO-全序广播。此外，Raft被设计为提供"开箱即用"的FIFO-全序广播。

共识算法的设计主要取决于系统模型。Paxos和Raft假设系统模型具有公平损耗链路fair-loss links，崩溃-恢复crash-recovery节点行为，以及部分同步partial synchrony。

对网络和节点行为的假设可以弱化为拜占庭式Byzantine，这样的算法也被用于区块链中。然而，拜占庭式的容错共识算法比非拜占庭式的更复杂、更低效。我们先来研究公平损耗、崩溃恢复的算法，这些算法在许多实际环境中是有用的（如具有可信私有网络的数据中心）。

另一方面，部分同步的假设不能被弱化为异步。其原因在于，共识需要一个故障检测器failure detector，而这又需要一个本地时钟来触发超时[Chandra and Toueg，1996]。如果我们没有任何时钟，那么一个确定性的共识算法可能永远不会终止。事实上，我们已经证明，确定性异步算法不能在保证终止的情况下解决共识问题。这一结论被称为FLP不可能原理（FLP result），它是分布式计算最重要的定理之一，以其三位作者Fischer、Lynch和Paterson的名字命名[Fischer et al.，1985]。

我们可以使用非确定性（随机）算法来绕过FLP不可能原理。然而，大多数实际使用的系统通过使用时钟超时来避免non-termination非终止。回忆一下，在一个部分同步的系统中，我们不能假设有网络延迟或者节点执行速度的上下限。由于这个原因，共识算法需要保证其safety properties安全属性（即每个节点以相同的顺序决定相同的消息），无论系统中的时间安排如何，甚至即使消息被任意延迟。只有liveness活性（即消息最终被传递）取决于时钟和时间。

大多数共识算法的重点在于，当现有的领导者由于某种原因变得不可用时，如何选举一个新的领导者。算法之间的细节有所不同；在本章中，我们将集中讨论Raft所采取的方法，但Raft的许多经验也同样适用于其他共识算法。Howard和Mortier[2020]给出了Raft和Multi-Paxos的详细比较。

当其他节点怀疑当前的领导者已经失败时，（通常因为他们在一段时间内没有收到领导者的任何消息，）就会启动领导者选举。其他节点中的一个成为候选人candidate，并要求其他节点投票决定是否接受该候选人作为他们的新领导者。如果有quorum个节点投票赞成该候选人，它就将成为新的领导者。如果使用多数选票majority quorum，只要大多数节点（3取2，或5取3等等）在运行并能进行通信，就能执行投票。

如果有多个领导者，他们可能会做出违反全序广播安全属性的不一致决定（这种情况被称为脑裂split brain）。因此，我们对领导者选举的关键要求是，在任何时候都应该只有一个领导者。在Raft中，"在任何一个时间"的概念被表述为一个任期term。这个任期只是一个整数，在每次领导者选举开始时都会递增。如果一个领导者当选，投票算法保证它是那个特定任期内唯一的领导者。不同的任期可以有不同的领导者。

然而，在一个部分同步的系统中，基于超时的故障检测器可能是不准确的：它可能怀疑一个节点已经崩溃了，而事实上该节点运行正常，例如网络延迟产生的毛刺spike。上图中，节点1是term t的领导者，但它与节点2和3之间的网络暂时中断。节点2和3可能会检测到节点1已经失效，并在t+1任期选出一个新的领导者，即使节点1仍然正常运行。此外，节点1甚至可能没有注意到网络问题，它也还不知道产生了新的领导者。因此，我们会有两个节点都认为自己是领导者。

出于这个原因，即使在一个节点被选为领导者之后，它也必须谨慎行事。因为在任何时候，系统中都可能产生另一个它不知道的任期较晚的领导者。所以领导者单方面提交消息是不安全的。因此，每当领导者决定下一个被传递的消息时，它必须再次向quorum节点请求确认。

1. 在第一次通信中，由于其他两个节点的投票，左边的节点被选为领导者。
2. 在第二次通信中，领导者提出要传递的下一个信息，同时追随者确认没有已知的晚于t的领导者。
3. 最后，领导者实际递交了M，并将这一事实广播给追随者，以便他们照样执行。

如果另一个领导者已经当选，旧的领导者将从第二轮通信中的确认中得知，因为第二轮quorum中的至少一个节点必须投票给新领导者。因此，即使多个领导者可能同时存在，旧的领导者不能决定接下来的信息递交，保证了算法安全。

6.2 The Raft consensus algorithm

我们来看看完整的Raft算法。理解该算法，需要先牢记上图的状态机。一个节点可以处于三种状态之一：领导者leader, 候选人candidate, 或追随者follower。当一个节点开始运行时，或者当它崩溃并恢复时，它在追随者状态下启动并等待来自其他节点的消息。如果它在一段时间内没有收到来自领导者或候选者的消息，追随者就会怀疑领导者不可用，它可能会尝试自己成为领导者。领导者失效的超时检测是随机的，这可以减少几个节点同时成为候选人并竞争成为领导者的概率。

当一个节点怀疑领导者失效了，它就转入候选状态，增加任期号，并开始在该任期内触发领导者选举，要求其他节点为其投票。在这个选举过程中，如果该节点收到另一个具有更高任期的候选人或领导者的消息，它就会转回追随者状态。但如果选举成功，并且它收到了满足quorum的投票，那么该候选人就会过渡到领导者状态。如果在一段时间内没有收到足够的票数，选举就会超时，候选人就会以更高的任期重新开始选举。

一旦一个节点处于领导者状态，它会保持领导者的身份，直到被关闭或崩溃，或者直到它收到一个任期高于自己的领导者或候选人的消息。比如网络分区使领导者和另一个节点长时间无法沟通，以至于另一个节点开始选举新的领导者，这样就会产生更高的任期。当收到更高的任期时，前领导者就会下台，成为一个追随者。

上图展示了启动和开始选举的伪代码。在initialisation初始化块中定义的变量构成了一个节点的状态。其中四个变量（currentTerm, votedFor, log, and commitLength）需要保存在稳定的存储介质上（例如磁盘），这样它们的值在崩溃后不会丢失。其他变量可以放在易失性内存中，崩溃恢复会重置它们的值。每个节点都有一个唯一的ID，我们假设有一个全局常量nodes，包含系统中所有节点的ID集合。这个版本的算法不处理重新配置问题（在系统中增加或删除节点）。

变量log包含一个条目数组array of entries，每个条目都有msg和term属性。每个数组条目的msg属性包含一个我们想通过全序广播传递的信息，而term属性包含它被广播的任期编号。log使用基于零的索引，所以 log[0] 是第一个日志条目，log[log.length-1]是最后一个。日志通过将新条目附加到末尾的方式增长，Raft在各节点间复制此日志。当一个日志条目（以及它的所有前身）被复制到满足quorum数量的节点时，它就被提交committed。当我们提交一个日志条目的时候，我们也将其msg递交给应用程序。在一个日志条目被提交之前，它还可能发生变化，但Raft保证一旦一个日志条目被提交，它就是最终状态，所有节点都会提交相同的日志条目序列。因此，从已提交的日志条目中按其日志顺序传递消息，就可以得到先进先出-全序广播。

当一个节点怀疑领导者失效时，它开始进行领导者选举，具体步骤如下：它增加currentTerm，它将自己设置为candidate，并通过将 votedFor 和 votesReceived 设置为自己的节点ID来为自己投票。然后，它向每个其他节点发送一个VoteRequest消息，要求它投票决定这个候选人是否应该成为新的领导者。该消息包含候选人的nodeId、它的currentTerm（增量后）、它的日志中的条目数、以及它最后一条日志的term属性。

上图展示了当一个节点收到来自候选人的VoteRequest消息时会发生什么。如果候选人的任期大于接收者的当前任期，接收者就会成为该任期的追随者（即使它在前一个任期是领导者）。然后，它检查候选人的日志是否至少与自己的日志一样是最新的；这样可以防止一个日志过期的候选人成为领导者，这可能会导致丢失已承诺的日志条目。如果候选人的最后一个日志条目的任期高于收到VoteRequest消息的节点上的最后一个日志条目的任期，那么该候选人的日志是可以接受的。如果任期相同，并且候选人的日志至少包含与接收人的日志一样多的条目，那么该日志也是可以接受的。这个逻辑反映在变量logOk中。

votedFor变量记录了当前节点在currentTerm中的投票。如果该候选人的任期是最新的任期，且如果该候选人的日志是最新up-to-date的，且我们还没有在这个任期内投票给其他候选人，那么我们就投票给该候选人，把它记录在 votedFor 中，并向该候选人发送一个包含 true 的 VoteResponse 消息（表示成功）。否则，我们将发送一个包含false的VoteResponse消息（表示拒绝投票给该候选人）。除了成功或失败的标志，响应消息还包含发送投票的节点的nodeId，以及投票的任期。

回到候选人身上，上图展示了处理VoteResponse消息的代码。我们忽略任何之前任期相关的响应（由于网络延迟，这些响应可能会延迟到达）。如果响应中的任期高于候选人的任期，候选人就会取消选举并回到追随者状态。但是，如果任期是正确的，并且成功标志granted被设置为true，那么候选人就会将投票者的节点ID添加到已收到的投票集合中。

如果这组投票构成了quorum，候选者就会过渡到领导者状态。成为领导者后，它先更新sendLength和ackedLength变量，然后对每个追随者调用ReplicateLog函数，来告知每个追随者新的领导者的情况。

在领导者节点上，sendLength和ackedLength是将每个节点的ID映射为一个整数的变量（非领导者节点不使用这些变量）。对于每个追随者F，sendLength[F]记录从日志的开始算起已经被发送到F的日志条目数量，而ackedLength[F]记录已经被F确认收到的日志条目数量。在成为领导者时，节点将sendLength[F]初始化为log.length（领导者假设追随者已经接受了整个日志），并将ackedLength[F]初始化为0（没有日志被确认）。这些假设可能是错误的：例如，追随者可能缺少一些领导者保存的日志条目。之后我们会讲解sendLength[F]如何进行修正。

上图展示了当应用程序希望通过全序广播来广播一个消息时，Raft如何将一个新条目添加到日志。领导者直接向日志添加一个新条目，而其他节点则需要通过FIFO链路（以确保FIFO-全序广播）由领导者为它追加。然后，领导者将自己在ackedLength中的条目更新为log.length，表明它已经确认了自己对日志的添加，并对其他节点调用ReplicateLog。

此外，即使没有新的信息，领导者也会周期性地对每个节点调用ReplicateLog。这有多个目的：它让追随者知道领导者仍然活着；它可以重新传输领导者和追随者之间任何可能丢失的信息；以及它会通知追随者哪些消息可以被提交。

上图说明，ReplicateLog函数的目的是将新的日志条目从领导节点发送到ID为followerId的追随者节点。它首先将变量suffix设置为从 sentLength[followerId]之后的日志（如果不为空）。也就是说，如果sendLength[followerId]是已经发送给followerId的日志条目数，那么suffix就包含尚未发送的剩余条目。如果sendLength[followerId]=log.length，那么变量suffix就是个空数组。

然后，ReplicateLog向followerId发送一个LogRequest消息，其中包含：suffix、领导者的ID、领导者当前任期、suffix之前的日志长度、suffix之前的最后一个日志条目的任期、以及commitLength（已经提交的日志条目的数量）。

当追随者收到来自领导者的LogRequest消息时，它将如上图所示处理该消息。首先，如果消息的任期晚于追随者，追随者会更新其当前的任期，并接受消息的发送者为领导者。消息的接收者也可能是同一任期的候选人，它同样也会成为追随者，并承认发送者为领导者。

接下来，追随者检查自己的日志是否与领导者的日志一致。prefixLen是LogRequest消息中包含的suffix之前的日志条目数量。追随者要求其日志至少与prefixLen一样长（即不遗漏任何条目），并且追随者日志的prefixLen中的最后一个日志条目的任期与领导者的同一日志条目的任期相同。Raft确保，如果两个节点在日志的同一索引处有相同的任期编号，那么它们的日志在该索引之前（包括该索引）是相同的。因此，如果logOk变量被设置为true，这意味着追随者的第一个prefixLen日志条目与领导者上的相应日志是相同的。

如果LogRequest消息是来自预期的任期，且logOk任期真，那么追随者会接受该消息并调用AppendEntries函数将suffix添加到自己的日志中。然后，它用一个LogResponse消息回复领导者，该消息包含追随者的ID、当前的任期、对收到的日志条目数量的确认、以及表明LogRequest成功的true值。如果消息来自一个过时的任期或者logOk为假，追随者就会用一个包含false的LogResponse来回复，以表示消息错误。

上图展示了AppendEntries函数，追随者调用该函数来用从领导者收取条目追加到自己的日志。prefixLen是suffix之前的日志条目数量。如果追随者的日志已经包含了log[prefixLen]及以后的条目，我们需要检查它们是否与suffix的日志条目匹配。我们选取领导者和追随者之间最后一个可比较的日志索引（要么是追随者日志中的最后一个条目，要么是suffix中的最后一个条目，以靠前者为准），并比较该日志索引的任期。如果不一致，我们就必须截断日志，只保留前prefixLen个条目，并丢弃其余。如果现有的日志条目来自旧的领导者，而现在产生了新的领导者，就可能发生这种不一致。

接下来，任何尚未出现在追随者日志中的新条目都被追加到日志中。在LogRequest消息被重复的情况下，这个操作是幂等的。

最后，追随者检查LogRequest消息中的整数leaderCommit是否大于本地变量 commitLength。如果是，这意味着新的记录已经准备好被提交并递交给应用程序。领导者将commitLength递增，并在对应的日志条目上全序广播递交消息。

从追随者的角度来看，算法已经执行完了。剩下的要切换回领导者视角，并分析它如何处理来自追随者的LogResponse消息。

收到LogResponse消息的领导者首先检查消息中的任期：如果发送者的任期晚于接收者的任期，这意味着新的领导者选举已经开始，因此这个节点从领导者过渡到追随者。任期过期的消息会被忽略。对于具有正确任期的消息，我们检查success字段，看追随者是否接受了日志条目。

如果success = true，领导者更新sendLength和ackedLength，来记录被追随者承认的日志条目的数量，然后调用CommitLogEntries函数。如果success = false，我们可以知道追随者没有接受日志条目，因为变量logOk值为假。在这种情况下，领导者会递减这个追随者的sendLength值，并在较早的日志条目上调用ReplicateLog来重新发送LogRequest消息。这种情况可能会发生多次，直到最终领导者将向追随者发送一个条目数组，成功追加到追随者的现有日志，此时追随者将接受LogRequest。(这个算法可以被优化，以减少重试次数）

上图显示了领导者如何确定哪些日志条目需要提交。由于commitLength包含了已经提交并递交给应用程序的日志条目的数量，所以log[commitLength]是第一个尚未提交的日志条目。如果该日志条目已经被majority quorum确认，那么它就可以提交了。由于ackedLength[node]存储的是各节点确认的日志条目数量，我们可以计算确认数量超过commitLength的节点数量。如果acks的数量构成了多数，我们就将log[commitLength]递交给应用程序，并递增commitLength。在领导者向追随者发送的下一个LogRequest消息中，将包括commitLength的值，使追随者提交并递交相同的日志条目。如果acks小于多数，我们就从循环中断开，等待进一步的LogResponse消息。