Raft算法第五节翻译

5 Raft一致性算法

  Raft是一种第2节中描述的用于管理复制日志的算法。图2总结了浓缩型式的算法供参考，图3列出算法的关键属性;这些元素将在本节的其余部分进行分段讨论。
  Raft通过首先选举一位领导者，然后让领导者完全负责管理复制的日志来实现一致性。领导者接受来自客户端的日志条目，在其他服务器上复制它们，并告诉服务器何时可以安全地将日志条目应用于其状态机。拥有领导者可以简化复制日志的管理。 例如，领导者可以在不咨询其他服务器的情况下确定在日志中放置新条目的位置，并且数据以简单的方式从领导者流向其他服务器。 领导者可能会失败或与其他服务器断开连接，在这种情况下会选出新的领导者。
  基于领导者的方法，Raft将一致性问题分解为三个相对独立的子问题，这些问题将在随后的小节中讨论：

• 领导者选举：当现有领导者失败时，必须选择新的领导者（第5.2节）。
• 日志复制：领导者必须接受来自客户端的日志条目并在集群中复制它们，从而强制其他日志与自己的日志一致（第5.3节）。
• 安全性：Raft的关键安全属性是图3中的状态机安全属性：如果任何服务器已将特定的日志条目应用于其状态机，则其他服务器不可以对同一日志索引应用不同的命令。 第5.4节描述了Raft如何确保这个属性; 解决方案包括对5.2节中描述的选举机制的一个额外限制。

  在介绍了一致性算法之后，本节将讨论可用性问题以及计时在系统中的作用。

5.1 Raft基础

  Raft集群包含多个服务器; 通常是5个，它允许系统容忍两个故障。在任何给定的时间，每个服务器处于三种状态之一：领导者，追随者或候选人。在正常操作中，只有一个领导者，所有其他服务器都是追随者。追随者是被动的：他们自己不发出请求，只是回应领导者和候选人的请求。领导者处理所有客户端的请求（如果客户端请求了一个追随者，追随者将其重定向到领导者）。第三个状态，候选者，被用于第5.2节描述的选出新的领导者。图4显示了状态及其转换; 转换过程将在下面讨论。
  Raft将时间划分为任意长度的时间周期，如图5所示。周期用连续的整数表示，每个周期从选举开始，一个或多个候选人试图成为领导者如5.2节所描述。如果一个候选人赢得选举，它就成为当前周期剩余时间的领导者。在某些情况下，选举将导致分裂投票。 在这种情况下，周期将以没有领导者的状态结束; 不久将开始一个新的周期（新的选举）。 Raft确保在一个周期内最多只有一个领导者。
  不同的服务器可能在不同的时间观察到周期的转换。在某些情况下甚至整个周期服务器都可能观察不到选举，周期在Raft中扮演一个逻辑时钟的角色，它们允许服务器检测过时的信息，例如旧的领导者。每个服务器都存储一个当前的周期编号，该编号随着时间的推移单调增加。每当服务器之间通信时，会交换当前的周期编号，如果一个服务器的当前周期编号小于另一个，它会将当前的周期编号更新为大的值。如果一个候选人或领导者发现当前周期已经超时，它会立即变为追随者的状态，如果服务器收到一个过期周期编号的请求，它将拒绝该请求。
  Raft服务器使用远程过程调用（RPC）进行通信，并且最基本的一致性算法仅需要两种类型的RPC。RequestVote（请求投票） RPC由候选人在选举期间发起（第5.2节），AppendEntries（追加条目）RPC由领导者发起用于复制日志条目并提供心跳的形式（第5.3节）。第7节添加了第三个RPC，用于在服务器之间传输快照。如果服务器未及时收到响应，则会重试RPC，并且会并行发起RPC以获得最佳性能。

5.2 领导者选举

  Raft使用心跳机制来触发领导者选举。当服务器启动时，它们以追随者的身份开始。只要服务器从领导者或候选者接收到有效的RPC，服务器就会保持追随者状态。领导者向所有追随者定期发送心跳（不带日志条目的AppendEntries RPC）以保持其领导。如果追随者在一段时间内没有收到任何通信被称为选举超时，则它假定没有可行的领导者并开始选举以选择新的领导者。
  为了开始选举，追随者增加其当前周期并转换到候选者状态。然后它投票支持自己并并行向集群中的其他服务器发起RequestVote RPC。候选人保持处于这种状态，直到发生以下三种情况中的一种：（a）它赢得选举，（b）另一个服务器将自己确立为领导者，或（c）一段时间过去而没有获胜者。这些结果将在下面的段落中单独讨论。
  如果候选人在一个周期内收到来自集群中的大多数服务器的投票，则该候选人将赢得选举。每个服务器将按照先来先服务的原则在一个周期内对最多一名候选人进行投票（注意：第5.4节增加了对投票的额外限制）。多数规则确保一个周期内只有一个候选人能够赢得选举（图3中的选举安全特性）。 一旦候选人赢得选举，它就会成为领导者。然后它向所有其他人发送心跳消息以建立领导并阻止新的选举。
  在等待投票时，候选人可能会从声称自己是领导者的另一台服务器收到一个AppendEntries RPC。 如果领导者的周期（包括在其RPC中）至少与候选人的当前周期一样大，那么候选人将领导者视为合法并返回到追随者状态。 如果RPC中的周期小于候选者的当前周期，则候选者拒绝RPC并继续处于候选状态。
  第三种可能的结果是候选人既不赢也不输选：如果有多个追随者同时成为候选人，投票被分割造成没有候选人获得多数票。 当发生这种情况时，每个候选者将超时然后启动另一轮RequestVote RPC，增大周期时间来开始新的选举。如果不采取额外措施，投票分割可能会无限重复。
  Raft使用随机的选举超时时间来确保投票分割很少出现并且可以快速解决。首先为了防止投票分割，从固定间隔（例如，150-300ms）随机选择超时选举时间。这使服务器的超时时间分散开来，在大多数情况下只有一个服务器超时; 它将赢得选举并在其他服务器超时之前发送心跳。相同的机制用于处理投票分割。每个候选人在选举开始时重新随机选举超时时间，并在开始下一次选举之前等待超时; 这减少了新选举中投票分裂的可能性。 第9.3节表明这种方法可以迅速选出领导者。
  选举的设计是一个可理解性如何指导我们在设计备选方案之间做出选择的例子。最初我们计划使用排名系统：每位候选人都被分配了一个独特的排名，用于在竞争候选人之间进行选择。如果候选人发现了另一个具有更高等级的候选人，那么它将返回到追随者状态，以便更高等级的候选人可以更容易地赢得下一次选举。我们发现这种方法在可用性方面产生了微妙的问题（如果排名较高的服务器出现故障，排名较低的服务器可能需要超时并再次成为候选者，但如果过早地这样做，它可能会重置选举领导者的进度）。 我们对算法进行了多次调整，但在每次调整后都出现了新的情况。 最后我们得出结论，随机重试方法更明白，更容易理解。

5.3 日志复制

  一旦领导者被选出，它就开始为客户端请求提供服务。每个客户端请求都包含一个需要由复制状态机执行的命令。领导者将命令作为新条目附加到其日志中，然后并行地向其他服务器发起AppendEntries RPC以复制条目。当条目被安全地复制时（如下所述），领导者将条目应用于其状态机并将该执行的结果返回给客户端。如果追随者崩溃或运行缓慢，或者网络数据包丢失，领导者将无限期地重试AppendEntries RPC（即使它已经响应客户端），直到所有追随者最终存储所有日志条目。
  日志的组织如图6所示。每个日志条目都存储着状态机命令以及领导者收到条目时的周期编号。日志条目中的周期数字用于检测日志之间的不一致，并确保图3中的某些属性。每个日志条目还有一个整数索引，用于标识其在日志中的位置。
  领导者决定何时将日志条目应用于状态机是安全的; 这样的条目称为已提交。Raft保证提交的条目是持久的，并且最终将由所有可用的状态机执行。一旦创建条目的领导者将其复制到大多数服务器上（例如，图6中的条目7），就提交日志条目。这也会提交领导者日志中的所有前面条目，包括由前任领导者创建的条目。第5.4节讨论了在领导者变更后应用此规则时的一些细微之处，并且还表明这种提交的定义是安全的。领导者跟踪它已知的需要被提交的条目的最高索引，并在未来的AppendEntries RPC（包括心跳）中包含该索引，以便其他服务器能最终找到。一旦关追随者得知日志条目被提交，它就会将该条目应用于其本地状态机（按日志顺序）。
  我们设计Raft日志机制以便在不同服务器上的日志之间保持高水平的一致性。这不仅简化了系统的行为并使其更具可预测性，而且它是确保安全性的重要组成部分。 Raft维护以下属性，它们共同构成了图3中的日志匹配属性：

• 如果不同日志中的两个条目具有相同的索引和周期，则它们存储相同的命令。
• 如果不同日志中的两个条目具有相同的索引和周期，则所有前面的条目中的日志都是相同的。

  第一个属性遵循以下事实：领导者在给定周期中创建最多一个具有给定日志索引的条目，并且日志条目永远不会更改它们在日志中的位置。第二个属性由AppendEntries执行一个简单的一致性检查保证。发送AppendEntries RPC时，领导者在其中包含日志中紧接在新条目之前的条目的索引和周期。如果追随者在其日志中找不到具有相同索引和周期的条目，则它拒绝新条目。一致性检查可以归纳为：日志的初始空状态满足日志匹配属性，一致性检查会在扩展日志时保留日志匹配属性。因此，每当AppendEntries返回成功时，领导者都知道追随者的日志与其自己的日志在添加新条目后相同。
  在正常操作期间，领导者和追随者的日志保持一致，因此AppendEntries一致性检查永远不会失败。但是，领导者崩溃可能会使日志不一致（旧的领导者可能没有完全复制其日志中的所有条目）。这些不一致可能会导致一系列领导者和追随者崩溃。 图7说明了追随者的日志可能与新领导者的日志不同的方式。追随者可能缺少领导者中存在的条目，也可能具有领导者不存在的额外条目，或两者都有。日志中缺少和多余的条目可能跨越多个周期。
  在Raft中，领导者通过强制追随者的日志复制自己的日志来处理不一致。这意味着追随者日志中的冲突条目将被领导者日志中的条目覆盖。第5.4节将表明，当再加上一个限制时，这是安全的。
  要使追随者的日志与其自身保持一致，领导者必须找到两个日志一致的最新日志条目，删除在该点之后追随者日志中的所有条目，并将该点之后向所有领导者的条目发送跟随者。所有这些操作都是在响应AppendEntries RPC执行的一致性检查时发生的。领导者为每个追随者维护下一个索引，该索引是领导者将发送给该追随者的下一个日志条目的索引。当领导者第一次获得领导权后，它会将维护的所有追随者的下一个索引值设置为它日志中最后一个条目的索引。如果追随者的日志与领导者的日志不一致，则AppendEntries一致性检查将在下一次AppendEntries RPC中失败。被拒绝后，领导者将减少索引值并重新发起AppendEntries RPC。最终，索引值将达到领导者和关注者日志匹配的点。发生这种情况时，AppendEntries将成功，这将删除追随者日志中的任何冲突条目，并从领导者的日志中添加条目（如果有的话）。一旦AppendEntries成功，追随者的日志与领导者的日志一致，并将在周期剩下的时间保持。
  如果需要，可以优化协议以减少拒绝的AppendEntries RPC的数量。例如，当拒绝AppendEntries请求时，关注者可以发送冲突条目的周期以及它为该周期存储的第一个索引。有了这些信息，领导者可以减少索引值以绕过该周期中的所有冲突条目; 每个具有冲突条目的周期都需要一个AppendEntries RPC，而不是每个条目一个RPC。 在实践中，我们觉得这种优化是不必要的，因为故障不经常发生，并且不太可能存在许多不一致的条目。
  使用此机制，领导者在开始领导时无需采取任何特殊操作来恢复日志一致性。它只是开始正常操作，在AppendEntries一致性检查的失败后日志会自动同步。领导者永远不会覆盖或删除其自己的日志中的条目（图3中的Leader Append-Only属性）。
  此日志复制机制展示了第2节中描述的期望的一致性属性：只要大多数服务器启动，Raft就可以接受，复制和应用新的日志条目; 在正常情况下，一次单轮的RPC就可以将新条目复制到群集的大部分机器; 一个慢的追随者不会影响性能。

5.4 安全

  前面的部分描述了Raft如何选择领导者并复制日志条目。但是，到目前为止所描述的机制还不足以确保每个状态机以相同的顺序执行完全相同的命令。例如，当领导者提交多个日志条目时，追随者可能不可用，然后它可以被选为领导者并用新的条目覆盖这些条目。
  本节通过添加对可以选择哪个服务器作为领导者的限制来完成Raft算法。该限制确保任何周期的领导者包都含先前周期中提交的所有条目（图3中的领导者完整性属性）。有了选举限制，我们会使提交规则更加准确。最后，我们提供了Leader完整性属性的简要证明，并展示了它如何保证复制状态机的行为正确。

5.4.1 选举限制

  在任何基于领导者的一致性算法中，领导者最终必须存储所有提交的日志条目。在一些共识算法中，例如Viewstamped Replication ，即使最初不包含所有提交的条目，也可以被选举为领导者。这些算法包含额外的机制来识别丢失的条目，并在选举过程中或之后不久将它们传送给新的领导者。不幸的是，这导致了相当大的额外机制和复杂性.Raft使用一种更简单的方法，它保证从选举之时起，每个被选出的新领导者都有之前周期中的所有已提交条目，而无需将这些条目转移给领导者这意味着日志条目仅在一个方向上流动，从领导者到追随者，并且领导者永远不会覆盖其日志中的现有条目。
  Raft使用投票过程来阻止其日志不包含所有已提交的条目候选人赢得选举。候选人必须联系群集的大多数才能被选举，这意味着每个提交的条目肯定至少存在于其中一个服务器中。如果候选人的日志至少与其他大多数机器的日志一样是最新的（下面精确定义的“最新”），则它将保留所有已提交的条目。RequestVote RPC实现了这一限制：RPC包含有关候选人日志的信息，如果其自己的日志比候选人的日志更新，则拒绝为其投票。
  Raft通过比较日志中最后一个条目的索引和周期来确定两个日志中哪一个更新。如果日志包含具有不同周期的最后一个条目，则具有较晚周期的日志将更新。如果日志以相同的周期结束，那么哪个日志记录更长是更新的。

5.4.2 提交之前周期的条目

  如第5.3节所述，领导者一旦知道当前周期的一个条目存储在大多数服务器上，就会提交该条目。如果领导者在提交条目之前崩溃，未来的领导者将尝试完成复制条目。但是，领导者无法立即得知储存在大多数机器上的之前周期的条目是否已经被提交。图8说明了当旧的日志条目存储在大多数服务器上但仍可被未来的领导者覆盖的情况。
  为了消除类似于图8中的问题，Raft从不通过计算副本数量来提交先前周期的日志条目。只有领导者当前周期的日志条目通过计算副本数量来提交; 一旦以这种方式提交了当前周期的条目，则间接地由于日志匹配属性所有之前的条目也都被提交了。在某些情况下，领导者可以安全地断定较旧的日志条目已经被提交（例如，如果该条目存储在每个服务器上），但Raft采用更保守的方法来简化。
  Raft在提交规则中引入了这种额外的复杂性，因为当领导者复制先前周期中的条目时，日志条目保留其原始周期编号。在其他一致性算法中，如果新领导者重新复制先前“周期”中的条目，则必须使用其新的“周期编号”。Raft的方法使得更容易推理日志条目，因为它们跨时间和日志保持相同的周期编号。此外，Raft中的新领导者发送的之前周期的日志条目少于其他算法（其他算法为了在提交之前重新编号必须发送冗余日志条目）。

5.4.3 安全论点

  鉴于完整的Raft算法，我们现在可以更准确地论证领导者完整性属性（这个论点基于安全性证明;参见第9.2节）。我们假设领导者完整性属性不成立，随后我们证明出了矛盾。假设周期T的领导者（领导者T）在其周期提交了日志条目，但该日志条目没有被未来某个周期的领导者存储。考虑最小的U> T，其领导者（领导者U）不存储该条目。

1. 在选举时领导者U的日志中必然没有该提交的条目（领导者永远不会删除或覆盖条目）。
2. 领导者T在大多数群集中复制了该条目，并且领导者U从群集的大多数群体中获得了投票。因此，至少一个服务器（“选民”）都接受了领导者T的条目并投票给领导者U，如图9所示。选民是达成矛盾的关键。
3. 在投票给领导者U之前，选民一定已经接受了领导者T的提交条目; 否则它会拒绝来自领导者T的AppendEntries请求（其当前周期高于T）。
4. 选民在投票给领导者U时仍然存储该条目，因为每个参与的领导者都包含该条目（假设），领导者从不删除条目，并且追随者只有在与领导者冲突时才删除条目。
5. 选民将其选票给了领导者U，因此领导者U的日志一定与选民一样时最新的。这导致了两个矛盾中的一个。
6. 首先，如果选民和领导者U的最后一个日志条目一样，那么领导者U的日志一定至少与选民的日志一样长，因此其日志包含选民的每个条目。这是一个矛盾，因为选民包含提交的条目，而领导者U假设没有。
7. 否则，领导者U的最后一个日志条目周期必须大于选民的。此外，它还大于T，因为选民的最后一个日志周期至少是T（它包含来自T的提交条目）。创建领导者U的最后一个日志条目的之前的领导者其日志中一定包含已提交的条目（假设）。根据日志匹配属性，领导者U的日志也一定包含已提交的条目，这是一个矛盾。
8. 上述矛盾表明所有大于T周期的领导者一定包含在周期T中提交的周期T的所有条目。
9. 日志匹配属性保证未来的领导者还将包含间接提交的条目，例如图8（d）中的索引2。

  鉴于领导者完整性属性，我们可证明图3中的状态机安全属性，该属性表明如果服务器已将给定索引处的日志条目应用于其状态机，则其他服务器将不会应用同样的索引处的不同的日志条目。在服务器将日志条目应用于其状态机时，其日志必须与领导者的相同，并且该条目必须被提交。现在考虑任一服务器应用给定日志索引的最低周期; 日志完整性属性保证所有较高周期的领导者将存储相同的日志条目，因此在之后应用该索引的服务器将应用相同的值。因此，状态机安全属性成立。
  最后，Raft要求服务器以日志索引顺序应用条目。 结合状态机安全属性，这意味着所有服务器将以相同的顺序将完全相同的日志条目集应用于其状态机。

5.5 追随者和候选人崩溃

  在此之前，我们一直关注领导者的失败。追随者和候选人崩溃比领导者崩溃更容易处理，并且它们都以相同的方式处理。如果追随者或候选者崩溃，则将来发送给它的RequestVote和AppendEntries RPC将失败。筏通过无限期重试来处理这些失败; 如果崩溃的服务器重新启动，则RPC将成功完成。Raf通过无限期重试来处理这些失败; 如果崩溃的服务器重新启动，则RPC将成功完成。如果服务器已完成RPC但在回复之前崩溃，那么它将在重新启动后再次收到相同的RPC。Raft的RPC是幂等的，所以这不会造成任何伤害。 例如，如果追随者收到其日志中已存在的日志条目的AppendEntries请求，则会忽略新请求中的这些条目。

5.6 时间和可用性

  我们对Raft的一个要求是安全性不能取决于时间：系统不能仅仅因为某些事件比预期更快或更慢地发生而产生不正确的结果。但是，可用性（系统能够及时响应客户端的能力）必然不可避免地取决于时间。例如，如果消息交换所需的时间超过服务器崩溃之间的时间，那么候选人将无法保持足够长的时间来赢得选举;没有稳定的领导者，Raft无法继续进行。
  领导选举是Raft对时间要求最严格的一个方面。只要系统满足以下时间要求，Raft就能够选择并保持稳定的领导者：

broadcastTime ≪ electionTimeout ≪ MTBF

  在这个不等式中，broadcastTime是服务器并行向群集中的每个服务器发送RPC并接收其响应所花费的平均时间; electionTimeout是第5.2节中描述的选举超时; MTBF是单个服务器的平均故障间隔时间。广播时间应比选举超时少一个数量级，以便领导者能够可靠地发送心跳消息阻止追随者开始进行竞选。鉴于用于选举超时的随机方法，这种不平等也使分裂投票不太可能。选举超时应该比MTBF少几个数量级，以便系统稳步前进。当领导者崩溃时，系统将由于选举超时不可用; 我们希望这只能代表整个时间的一小部分。
  broadcastTime和MTBF是底层系统的属性，而选举超时是我们必须选择的。Raft的RPC通常要求收件人将信息保存到持久存储，因此广播时间可能在0.5ms到20ms之间，具体取决于存储技术。因此，选举超时可能介于10毫秒到500毫秒之间。典型服务器MTBF可能几个月或更长时间，这很容易满足时序要求。