Post

基本Raft算法【第3章】

Posted Updated
By NINE
74 min read

本章介绍Raft算法。设计Raft的首要目标就是容易理解。本章的第一节讲述在实现“可理解性”方面的设计理念；接下来的几节将详细说明算法本身，并通过一些具体示例说明如何围绕“易理解”做出关键设计决策。

🌲 为可理解性而设计

在设计Raft时有多个目标：

  • 它必须为构建分布式系统提供一个完整且实用的基础，从而大幅减少开发者的工作量；
  • 它必须在各种条件下都能保证安全性，并在典型的运行环境下保持可用性；
  • 它在处理常见操作时必须具有高效性。

但在这些目标之中，最重要、同时也是最具挑战性的目标，就是“可理解性”：我们希望广大的读者群体能轻松理解Raft算法的原理与行为。

此外，我们还希望开发者能够在理解算法的基础上，逐步建立对其行为的“直觉”，这样在面对真实世界中不可避免的扩展需求时，系统构建者才能更自信地做出正确的修改与改进。

在Raft的设计过程中，我们遇到了许多需要在不同方案之间做出选择的情况。在这些场景中，我们将“可理解性”作为首要评估标准：每种方案有多难解释？它的状态空间是否复杂？是否存在难以察觉的隐含问题？读者能否轻松理解该方案及其后果？

我们也清楚，这样的评估带有相当程度的主观性。为尽量减少主观因素的影响，我们采用了两种普遍适用的策略：

第一种策略是众所周知的问题分解法：我们尽可能将复杂问题拆解为若干独立的子问题，每个子问题都可以被相对独立地解决、解释和理解。 例如，在Raft设计中包括了三个核心部分：

  • 领导人选举（leader election）
  • 日志复制（log replication）
  • 安全性保障（safety）

我们采用的第二种可理解性策略，是简化系统的状态空间：通过减少需要考虑的状态数量，使系统更具一致性，同时在可能的情况下消除非确定性。例如，Raft日志中不允许存在“空洞”（holes），并且限制日志之间出现不一致的方式。尽管我们在大多数情况下都试图消除非确定性，但在某些情形下，非确定性反而有助于提升可理解性。特别是，当我们采用随机化策略时，虽然引入了非确定性，但也减少了状态空间的复杂性，因为所有的选择都可以用类似的方式处理）。Raft就利用了这一点，通过引入随机化机制简化了领导人选举算法。

🌲 Raft总览

Raft是一种用于管理复制日志（replicated log）的共识算法，其目标与2.1节所描述的架构一致。图3.1概括性地展示了该算法的基本流程，图3.2则列出了算法的关键性质；后续各小节将对这些图中的要素逐一进行详细讲解。

Raft实现共识的方式是：首先选出一个服务器作为领导者（leader），然后赋予该领导者全权管理复制日志的职责。领导者接收客户端的日志请求，将这些日志复制到其他服务器，并在日志可以安全应用到状态机时通知各个服务器。引入领导者角色的好处在于：它简化了日志复制的管理流程。 例如，领导者可以直接决定新日志项应插入的位置，无需征求其他服务器的意见；同时，数据也可以从领导者单向地流向其他服务器，流程更加清晰。当然，领导者可能会故障，或因网络原因与其他服务器失联，此时需要重新发起领导人选举。

基于这种“领导者驱动”的架构，Raft将共识问题拆解成三个相对独立的子问题，后续小节将分别介绍：

  • 领导人选举（Leader election）：在系统启动时，或当现有领导者失效时，必须选出一个新的领导者；

  • 日志复制（Log replication）：领导者需接收来自客户端的日志条目，并将其复制到集群中的其他节点，迫使其他节点的日志与自己保持一致；

  • 安全性（Safety）：Raft的核心安全性属性是状态机安全性（State Machine Safety），如图3.2所示：

    如果某个服务器已将某条日志应用到其状态机中，则不允许其他服务器在相同的日志索引位置应用不同的指令。 第3.6节将详细介绍Raft是如何实现这一关键安全性的。

此图展示了Raft共识算法的整体结构（不包括成员变更、日志压缩以及与客户端的交互部分）。图中右下角的服务器行为被描述为一组彼此独立、可重复触发的规则。图中标注的章节号（如§3.4）对应了各功能在正文中具体讨论的位置。

选举安全性（Election Safety）

​ 在任意一个任期（term）中，最多只能选出一个领导者（Leader）。§3.4

领导者仅追加（Leader Append-Only）

​ 领导者不会覆盖或删除其日志中的任何条目，只会在末尾追加新条目。§3.5

日志匹配性（Log Matching）

​ 如果两个日志在同一索引位置拥有相同任期的日志条目，那么从头到该索引位置的所有日志条目在这两个日志中必然 完全一致。§3.5

领导者完整性（Leader Completeness）

​ 如果某条日志在某个任期内已被提交（committed），那么在所有更高编号的任期中，所有领导者的日志中都将包含 该条目。§3.6

状态机安全性（State Machine Safety）

​ 如果某台服务器已经将某条日志条目在某个索引位置应用到其状态机中，则其他服务器绝不会在该位置应用不同的日 志条目。§3.6.3

图3.2：Raft协议保证这些性质在任何时刻都成立。括号中的章节编号指出了每个性质的详细讨论位置。为了保证这些性质，Raft在选举机制中增加了一项额外的限制，详见第3.4节。

在介绍完一致性算法之后，本章还将探讨系统的可用性问题及系统中时间因素的作用（第3.9节），并介绍一个可选扩展：在服务器之间进行领导权转移（第3.10节）。

🌲 Raft基本原理

一个Raft集群由多个服务器组成；典型配置为5台服务器，这样可以容忍其中两台发生故障。任意时刻，每台服务器都处于三种状态之一：

  • 领导者（leader）
  • 跟随者（follower）
  • 候选者（candidate）

在正常运行时，集群中会有且仅有一个领导者，其余服务器均为跟随者。跟随者是被动的：它们不会主动发起请求，只响应来自领导者和候选者的消息。领导者负责处理所有客户端请求（如果客户端联系的是跟随者，跟随者会将其重定向至领导者）。第三种状态，候选者，是在选举新领导者时使用的，详见第3.4节。

图3.3展示了服务器状态及其之间的转换关系，后文将逐一说明这些转换过程。

Raft将时间划分为若干任期（term），每个任期的长度是任意的，如图3.4所示。任期编号是单调递增的整数。每个任期以一次选举开始，期间一个或多个候选者尝试当选为新领导者。如果某个候选者赢得了选举，它将在该任期剩余时间内担任领导者。如果选举出现了投票平局（split vote），则可能无法选出领导者，这种情况将在后文详细讨论。

图3.3：服务器状态

跟随者（Follower）仅响应来自其他服务器的请求。如果一段时间内未收到任何通信，它将转变为候选者（Candidate）并发起选举。候选者若获得超过半数服务器的投票，即成为新的领导者（Leader）。领导者通常会持续工作，直到发生故障为止。

图3.4：时间被划分为多个任期（Term），每个任期以一次选举开始。

选举成功后，将由一位领导者（Leader）负责管理整个集群，直到任期结束。某些选举可能失败，此时该任期结束但未选出领导者。由于服务器之间的通信延迟，不同服务器可能在不同时间感知到任期的变化。

如果选举失败，该任期将以“无领导者”状态结束，并很快开始一个新的任期（即重新发起一次选举）。Raft保证每个任期至多只能有一个领导者。

不同服务器可能在不同时间观察到任期的变更。在某些情况下，某些服务器甚至可能完全错过一次选举，或整个任期的变更。Raft中的任期扮演了逻辑时钟的角色，使得服务器能够识别过时的信息，例如已经失效的领导者。每个服务器都会维护一个当前任期号，该值随着时间单调递增。在服务器之间通信时，彼此会交换当前任期号；如果发现对方的任期更大，服务器会立即更新自己的任期号为较大的值。

如果某个候选者或领导者发现自己的任期已经过时，它会立即转为跟随者状态。如果一个服务器收到包含过期任期的请求，它将拒绝该请求。

Raft使用远程过程调用（RPC）进行服务器之间的通信。在基本的共识算法中，仅需要两种类型的RPC：

  • RequestVote：由候选者在选举过程中发起（详见§3.4）；
  • AppendEntries：由领导者发起，用于复制日志条目并作为心跳信号（详见§3.5）。

在领导权转移（§3.10）以及后续章节中描述的机制中，还会引入其他RPC类型，但基本算法只依赖上述两种。

我们选择将Raft的通信结构设计为RPC，是为了简化通信逻辑。每种请求类型都有对应的响应类型，这些响应同时也作为请求的确认。Raft假设网络中可能会丢失RPC请求或响应，因此请求方必须在超时后主动重试。为获得最佳性能，服务器会并行发送RPC，且Raft不假设网络能维持RPC调用的顺序。

🌲 领导者选举

Raft通过心跳机制来触发领导者选举。当服务器启动时，它们处于“跟随者”（follower）状态。只要跟随者收到来自领导者或候选者的有效RPC，它就会保持这一状态。领导者为了维持其领导地位会周期性地向所有跟随者发送心跳（即不携带日志条目的AppendEntries RPC）。如果一个跟随者在一段时间内（称为“选举超时”）没有收到任何通信，它会认为当前没有可用的领导者，然后发起选举以选出新的领导者。

为发起选举，跟随者会将当前任期号加一，并转换到候选者（candidate）状态。它首先会为自己投一票，同时并行的向集群中的其他所有服务器发送RequestVote RPC。候选者会持续处于该状态，直到以下三种情况之一发生：

（a）它赢得了选举；

（b）另一个服务器成为了新的领导者；

（c）再一次选举超时同时无人当选。

以下段落将分别讨论这些可能的结果。如果一个候选者在同一任期内获得了集群中多数服务器的投票，它就赢得了选举。每个服务器在一个任期内最多只会投票给一个候选者，且遵循“先到先得”的原则（注：第3.6节对投票还引入了额外限制）。“多数票”规则确保在任意任期中至多只有一个候选者能赢得选举（见图3.2中的“选举安全性”属性）。一旦候选者赢得选举，它就会成为领导者，并向所有其他服务器发送心跳消息，以确立其权威并阻止再次选举。

如果候选者在等待投票期间收到了另一个声称是领导者的服务器发送的AppendEntries RPC，那么它会根据该RPC中包含的任期号做出判断。如果这个领导者的任期号不小于（>=）候选者当前的任期号，候选者会承认其合法性，并退回到跟随者状态。反之，如果该RPC中的任期号小于候选者当前的任期号，候选者会拒绝该RPC并继续保持候选者状态。

第三种可能的结果是：候选者既没有赢得选举，也没有明确失败。当许多跟随者在大致相同时间内都成为候选者时，可能会出现投票分裂的情况，导致没有任何候选者获得多数票。一旦发生这种情况，每个候选者都会在超时后再次发起新一轮选举：增加任期号，并重新发送RequestVote RPC。但如果没有额外机制介入，这种票数分裂可能会不断重复，导致无法选出领导者。

为了解决这一问题，Raft使用随机选举超时来避免票数分裂的频繁发生，并在其发生时能迅速解决。为了尽量防止票数分裂，Raft从一个固定的时间区间（例如150–300毫秒）中随机选择每个服务器的选举超时时间。这种做法使得大多数情况下只有一个服务器最先超时，它因此能迅速赢得选举，并在其他服务器超时之前发送心跳，确立领导地位。同样的机制也用于应对票数分裂：每个候选者在发起选举时会重新随机设置自己的选举超时，并等待该超时结束后才再次尝试发起选举。这显著降低了新一轮选举中再次发生票数分裂的概率。

选举机制是Raft在设计过程中以“易理解性”为指导原则所做设计决策的一个典型例子。起初，我们曾计划使用一个排序系统：为每个候选者分配一个唯一的等级（rank），并用它在多个候选者之间进行优先级选择。如果一个候选者发现另一个候选者的等级更高，它就会退回到跟随者状态，以便让高等级的候选者更容易赢得下一轮选举。

但我们发现这种做法在可用性方面引发了许多微妙的问题——比如，如果高等级的服务器发生故障，低等级的服务器可能需要重新超时并再次成为候选者，但如果它动作太快，就可能重置选举进程，导致无法快速选出新领导者。我们为此对算法进行了多次调整，但每次修改都引入了新的边界情况。最终我们得出结论：基于随机重试的方式更加直观且易于理解，因此选择了这一方案。

💡 示例：

$S_4$，$S_5$几乎同时选举超时（$S_4$稍快）。

$S_4$，$S_5$首先给自己投票，然后并行的向其他服务器发送RequestVote RPC。

$S_4$的请求比$S_5$的请求先到达$S_1$服务器，$S_1$同意给$S_4$服务器投票同时重置了选举定时器。

$S_4$收到半数以上的票成为了领导者。

$S_4$发送AppendEntries RPC给其他服务器。

$S_5$收到了AppendEntry RPC回退到跟随者状态。

发送AppendEntry RPC给其他服务器同时丢弃掉$S_1$，$S_2$的响应。

收到$S_3$和$S_5$的回复，更新了commitIndex。

为什么领导者再次发送给$S_3$和$S_5$的commitIndex不同？

手动让$S_1$，$S_2$，$S_5$服务器选举超时，$S_1$拥有最大的任期号。

可以看到$S_5$拒绝了$S_2$的RequestVote请求，但是任期号更新了。

可以看到$S_1$，$S_2$其实是没有机会当选领导者的即使它们先发出了RequestVote请求。

🌲 日志复制

一旦领导者被选举出来，它就开始处理客户端请求。每个客户端请求都包含一个要由复制状态机执行的命令。领导者将该命令作为一个新的日志条目追加到自己的日志中，然后并行地向集群中的其他所有服务器发送AppendEntries RPC，以复制该日志条目。

当该条目被安全复制后（下文将解释“安全”的定义），领导者会将该日志条目应用到自己的状态机，并将执行结果返回给客户端。如果某些跟随者宕机、响应缓慢，或者网络包丢失，领导者会不断重试发送AppendEntries RPC，即使它已经向客户端返回了响应，也会持续尝试，直到所有跟随者都成功存储了所有日志条目。

图3.5：日志由多个条目组成，条目按顺序编号。每个条目包含其创建时的任期号（见每个方框中的数字）以及一个供状态机执行的命令。当某个条目已被确认可以安全地应用到状态机时，它就被视为已提交（committed）。

日志的结构如图3.5所示。每个日志条目记录一个状态机命令，以及该条目在被领导者接收时的任期号。日志条目中的任期号用于检测日志之间的不一致性，并用于确保图3.2中的一些关键属性。同时，每个日志条目还有一个整数索引，用于标识其在日志中的位置。

是否可以将日志条目应用到状态机，由领导者决定；被认定可以安全应用的条目称为已提交（committed）条目。Raft保证已提交的条目是持久的，并最终会被所有可用的状态机执行。

具体来说，某条日志条目一旦被创建它的领导者复制到大多数服务器上（例如图3.5中的条目7），它就被视为已提交。这一操作也会连带提交该领导者日志中所有它之前的条目，包括由前任领导者创建的条目。

第3.6节将讨论在领导者变更后应用该规则时的一些细节，并说明该提交定义是安全的。领导者会记录它已知的最大已提交索引，并在后续的AppendEntries RPC（包括心跳）中携带该索引，确保其他服务器最终也能获知哪些条目已提交。

一旦跟随者得知某条日志条目已提交，它就会按日志顺序将其应用到本地的状态机。

我们设计Raft的日志机制，目的是在不同服务器之间保持高度一致性的日志结构。这不仅简化了系统行为、提升可预测性，更是确保安全性的关键组成部分。Raft保证了以下两个特性，它们共同构成图3.2中所描述的日志匹配性（Log Matching Property）：

  • 如果两个日志中的条目具有相同的索引和任期号，那么它们保存的命令也完全相同。
  • 如果两个日志中的条目具有相同的索引和任期号，那么它们之前的所有日志条目也完全一致。

第一个性质源于这样一个事实：在一个任期内，领导者对某个特定的日志索引至多只能创建一个日志条目，而且日志条目的位置一旦确定就不会改变。 第二个性质则由AppendEntries RPC中的一致性检查机制所保证：领导者在发送AppendEntries RPC时，会附带新条目前一个日志条目的索引和任期号。如果跟随者在自身日志中找不到具有相同索引和任期号的条目，它就会拒绝接受这些新日志条目。（思考：为什么不是删除？）

这个一致性检查机制相当于一个数学归纳步骤：在系统初始化的空日志状态下，日志匹配性自然成立；之后，每次日志扩展前都会进行该检查，从而保持该性质不被破坏。因此，只要AppendEntries调用成功返回，领导者就可以确认该跟随者的日志与自己的日志在新增条目之前是完全一致的。

在正常运行期间，领导者与跟随者的日志保持一致，因此一致性检查一般不会失败。但在领导者发生崩溃的情况下，日志之间可能会产生不一致——例如，旧的领导者可能没有将所有条目完全复制出去。这种不一致可能在一系列的领导者和跟随者崩溃中积累加剧。

图3.6展示了新的领导者与跟随者之间日志可能出现的不同情况：

  • 跟随者可能缺少领导者已经拥有的日志条目；
  • 跟随者可能多出一些领导者所没有的条目；
  • 甚至可能同时出现上述两种情况。 这些多余或缺失的日志条目，可能跨越多个任期。

在Raft中，领导者通过强制跟随者的日志复制自己的日志来解决这种不一致性。这意味着跟随者日志中存在冲突的条目会被领导者的日志覆盖。第3.6节将进一步说明，只要结合特定的选举限制机制，这种覆盖操作是安全的。

为了使某个跟随者的日志与自己一致，领导者需要：

  1. 找到当前两份日志中最后一个一致的日志条目；
  2. 删除跟随者在此之后的所有日志；
  3. 将自己在该点之后的所有日志条目发送给该跟随者。

以上过程由AppendEntries RPC中的一致性检查触发和驱动。

此外，领导者为每个跟随者维护一个名为nextIndex的变量，它表示领导者下一次要发送给该跟随者的日志条目的索引。当领导者首次当选时，会将所有nextIndex初始化为自己最后一个日志条目的下一个索引值。

图 3.6：当最上方的领导者上任时，跟随者的日志中可能出现（a）至（f）中的任意一种情况。每个方框代表一个日志条目，框内数字表示该条目的任期号。跟随者可能存在缺失的条目（情况a和b），也可能包含未提交的额外条目（情况c和d），或者同时存在这两种情况（情况e和f）。例如，情况（f）可能发生在该服务器曾在第2任期担任领导者，向日志中添加了若干条目，但在提交任何条目前崩溃；该服务器快速重启，成为第3任期的领导者，又在日志中追加了几个条目；随后在第2和第3任期的条目都尚未提交时，该服务器再次崩溃，并在接下来的几个任期内一直处于宕机状态。

领导者在首次上任时，会将所有跟随者的nextIndex初始化为自己日志的最后一个条目之后的位置（如图3.6中的索引11）。如果某个跟随者的日志与领导者的不一致，则下一次发送的AppendEntries RPC中的一致性检查会失败。被拒绝后，领导者会将该跟随者的nextIndex减一，并重试AppendEntries RPC。最终，nextIndex会递减到领导者和跟随者日志匹配的位置。此时，AppendEntries请求会成功，这会删除跟随者日志中所有冲突的条目，并追加领导者日志中的新条目（如果有）。一旦AppendEntries成功，跟随者的日志就与领导者保持一致，并在本任期内持续保持这种一致性。

在领导者发现两者日志匹配的位置之前，它可以只发送不携带日志条目的AppendEntries（即心跳）以节省带宽。当匹配索引刚好位于nextIndex的前一位时，领导者应开始发送实际的日志条目。

如果需要，该协议还可以通过优化减少被拒绝的AppendEntries RPC次数。例如，当跟随者拒绝AppendEntries请求时，可以携带冲突条目的任期号以及该任期中跟随者日志中存储的第一个索引。有了这些信息，领导者就可以直接将nextIndex调整到跳过该任期内所有冲突条目的位置；这样，每个存在冲突的任期只需发送一次AppendEntries RPC，而不是每个条目发送一次。另一种优化方式是，领导者使用二分查找的方法找到第一个不匹配的日志条目，这在最坏情况下的表现更好。实际上，由于失败情况较少且不一致的条目通常不多，我们认为这些优化并非必要。

通过这一机制，领导者在上任时不需要采取特殊措施来恢复日志一致性。它只需开始正常运行，日志会自动在AppendEntries一致性检查失败时逐步收敛。值得注意的是，领导者绝不会覆盖或删除自身日志中的条目（见图3.2中的“领导者仅追加”属性）。

这种日志复制机制具备第2.1节描述的理想共识特性：只要大多数服务器在线，Raft就能接受、复制并应用新的日志条目；在正常情况下，一个新条目只需一次RPC就能复制到多数节点；单个响应缓慢的跟随者不会影响整体性能。该日志复制算法也易于实现，因为AppendEntries请求的大小是可控的（领导者在单次请求中发送的日志条目从不超过一个，以保证进展）。相比之下，某些其他共识算法需要将整个日志通过网络传输，这对实现者来说增加了很大负担，需要开发复杂的优化手段才能实用。

🌲 安全性

前面章节介绍了Raft如何选举领导者以及如何复制日志条目。但到目前为止，所描述的机制还不足以保证每个状态机都以相同的顺序执行完全相同的命令。举例来说，某个跟随者节点可能在领导者提交了若干日志条目期间处于不可用状态，随后该跟随者又被选为领导者，这时它可能会用新的日志条目覆盖之前的内容，导致不同状态机执行的命令序列出现差异。

本节通过添加对可当选领导者服务器的限制，完善了Raft算法。这一限制确保任意任期的领导者都包含前几个任期中已提交的所有日志条目（即图3.2中的“领导者完整性属性”）。在选举限制的基础上，我们进一步明确了日志提交的规则。最后，我们给出“领导者完整性属性”的证明思路，并说明该属性如何保证复制状态机的正确行为。

🍃 选举限制

在任何基于领导者的共识算法中，领导者最终必须保存所有已提交的日志条目。在一些共识算法中，比如Viewstamped Replication，即使新领导者起初并不包含所有已提交条目，也能被选举产生。这些算法中通常包含额外机制，用于在选举过程中或选举后不久，将缺失的条目传输给新领导者。然而，这会带来较大的机制复杂性和额外开销。

Raft采用了更简单的方案，保证每个新领导者自选举之时起，日志中就包含了前任期所有已提交的条目，无需再将这些条目转移给领导者。这样，日志条目只沿一个方向流动——从领导者到跟随者，且领导者绝不会覆盖已存在的日志条目。

Raft通过投票过程阻止日志不完整的候选者当选。候选者必须获得集群中多数节点的支持才能成为领导者，而每个已提交条目至少存在于这多数节点中的一个节点的日志里。如果候选者的日志至少与这多数节点中任何一个的日志同样新（“新” 的定义详见下文），则它必然包含所有已提交条目。RequestVote RPC实现了这一限制：该RPC请求中包含候选者日志的信息，投票节点如果发现自己日志比候选者更新，则会拒绝投票。

Raft判断两个日志哪个更新，依据是比较日志末尾条目的任期号和索引。如果两日志末尾条目的任期号不同，则任期号更大的日志更新；如果任期号相同，则日志长的那个更新。

图3.7：时间序列示意图，展示了为什么领导者不能仅凭旧任期的日志条目来判断提交情况。

  • (a) 时刻，$S_1$是领导者，并部分复制了索引为2的日志条目。
  • (b) $S_1$崩溃，$S_5$以第3任期领导者身份当选，获得了$S_3$、$S_4$以及自身的选票，并接受了索引为2的不同日志条目。
  • (c) $S_5$崩溃，$S_1$重启并再次当选为领导者，继续进行日志复制。此时，第二任期的日志条目已经在多数服务器上复制，但并未被提交。
  • (d1) 若$S_1$再次崩溃，$S_5$可能再次当选（得到$S_2$、$S_3$、$S_4$的选票），并用第三任期的条目覆盖该日志条目。
  • (d2) 然而，如果在崩溃前，$S_1$在多数服务器上复制了当前任期的新条目，那么该条目即被提交（$S_5$无法赢得选举）。此时，日志中所有之前的条目也都被提交了。
🍃 提交前任期的日志条目

如第3.5节所述，领导者一旦确认其当前任期的某条日志已被多数服务器存储，就认为该条目已提交。如果领导者在提交条目之前崩溃，后续的领导者会尝试完成该条目的复制工作。

然而，领导者不能仅凭多数服务器存储了某条来自之前任期的日志条目，就立即断定该条目已提交。图3.7展示了这样一种情况：旧的日志条目虽然被多数服务器保存，但仍可能被未来的领导者覆盖。

为了避免类似图3.7中的问题，Raft规定只有当前领导者任期的日志条目才可以通过多数复制计数来提交。当前任期的条目一旦提交，依据日志匹配性质（Log Matching Property），所有之前的条目也间接被提交了。尽管在某些特殊情况下（例如某条日志被所有服务器保存），领导者可以安全地断定旧条目已提交，但Raft为了简化设计，采取了更为保守的策略。

这种复杂性源于Raft允许日志条目保持其原始任期号，即使领导者复制的是前任期的条目。而在其他一些共识算法中，若新领导者重新复制旧任期的条目，必须赋予它们新的任期号。Raft的做法让我们更容易理解日志条目，因为它们始终保持相同的任期号。此外，Raft中新领导者复制的旧任期日志条目比其他算法要少，因为其他算法需要额外复制并重编号日志条目才可提交；不过实际中这影响不大，因为领导者更替本应是罕见事件。

🍃 安全性论证

在完整的Raft算法框架下，我们可以更精确地证明“领导者完整性属性”成立（该论证基于安全性证明，详见第8章）。我们通过假设“领导者完整性属性不成立”，然后推导出矛盾来证明。

假设任期T的领导者（$\text{leader}\text{T}$）提交了某条日志，但某个未来任期$\text{U} > \text{T}$的领导者（$\text{leader}\text{U}$）并没有存储该日志条目。令U 是满足此条件的最小任期。

  1. 在$\text{leader}_\text{U}$当选时，该提交条目必然不在其日志中。
  2. $\text{leader}\text{T}$曾将该条目复制给集群多数节点，$\text{leader}\text{U}$又获得了多数节点的选票。因此，至少存在一个服务器（称为“投票者”），既接受了$\text{leader}\text{T}$的该条目，又投票给了$\text{leader}\text{U}$（见图3.8）。该投票者是矛盾推导的关键。
  3. 该投票者在投票给$\text{leader}\text{U}$之前，必然已接受该提交条目；否则它会拒绝$\text{leader}\text{T}$的附加日志请求（因为其任期号会更高于T）。
  4. 该投票者投票时仍保存该条目，因为所有中间领导者均包含该条目（假设成立），且领导者不会删除条目，跟随者仅在冲突时才删除。
  5. 该投票者支持$\text{leader}\text{U}$，因此$\text{leader}\text{U}$的日志至少与投票者一样新，这将导致以下两种矛盾之一：
  6. 如果投票者和$\text{leader}\text{U}$的最后日志任期相同，则$\text{leader}\text{U}$的日志长度至少和投票者一样，意味着$\text{leader}\text{U}$的日志包含投票者所有条目，而投票者含有该已提交条目，$\text{leader}\text{U}$却假设不含，矛盾。
  7. 否则，$\text{leader}\text{U}$的最后日志任期比投票者大，且大于T，因为投票者的最后日志任期至少是T（包含提交条目）。产生$\text{leader}\text{U}$最后日志条目的先前领导者必包含该提交条目（假设成立），根据日志匹配性质，$\text{leader}_\text{U}$的日志也必须包含该提交条目，矛盾。
  8. 由此得出矛盾，所有大于T任期的领导者必定包含任期T内提交的所有条目。
  9. 日志匹配性质保证后续领导者也包含间接提交的条目，比如图3.7(d2)中的索引2。

鉴于领导者完整性属性，我们可以证明状态机安全性属性（图3.2），即：如果某服务器已将某条日志条目应用到状态机，则不会有其他服务器在同一索引应用不同条目。因为服务器应用日志条目时，其日志必与领导者日志在该条目之前完全一致，且该条目已提交。考虑任期最低的服务器应用某索引条目，领导者完整性属性保证所有后续任期领导者都存储该条目，后续服务器应用时必是同一条目，保证状态机安全性。

最后，Raft要求服务器按日志索引顺序应用条目。结合状态机安全性属性，意味着所有服务器会以相同顺序执行完全相同的日志条目，保持状态机一致。

🌲 跟随者与候选者的崩溃

前面我们主要关注了领导者故障的处理。而相比之下，跟随者和候选者的崩溃要简单得多，而且这两类节点的故障处理方式是相同的。

当一个跟随者或候选者发生崩溃（或者它与领导者之间的网络连接中断）时，后续发送给它的RequestVote和AppendEntries RPC都会失败。Raft的处理方式是无限重试：一旦该服务器重启，RPC就能够重新成功完成。

如果一个服务器在成功处理某个RPC后尚未发送响应就崩溃，那么在它重启后，会再次接收到相同的RPC。由于Raft的RPC是幂等的——也就是说，重复执行不会带来副作用——因此这种情况不会造成任何问题。

举例来说，如果某个跟随者收到一个AppendEntries请求，其中包含它日志中已经存在的条目，它会忽略这些重复的条目，不会做出任何改变。

🌲 持久化状态与服务器重启

Raft服务器必须将足够的状态信息持久化，以确保在服务器重启后仍能安全地恢复运行。具体来说，每个服务器需要持久化当前的任期（term）和投票信息。这是为了防止服务器在同一任期内重复投票，或者将来自已经失去领导地位的旧领导者的日志条目，替换掉来自更新任期领导者的条目。

此外，服务器还必须在日志条目被计入“已提交”之前先将其持久化。这样做可以防止在服务器重启后丢失已经提交的日志条目，或导致“已提交”状态被撤销。

其他状态变量在重启时丢失是允许的，因为它们都可以重新构建。一个特别有趣的例子是提交索引（commit index）。即使该值在重启后被重置为0，也不会影响系统安全。即便集群中的所有服务器同时重启，提交索引也只是暂时落后于实际值。一旦新的领导者被选出并提交了新的日志条目，它的提交索引就会前进，并很快将其传播给所有跟随者。

状态机既可以是易失性的（volatile），也可以是持久化的（persistent）：

  • 对于易失性状态机，在服务器重启后需要重新执行日志条目（通常是在应用最新的快照之后，详见第5章）。
  • 而持久化状态机在重启后多数条目已经被执行，为了避免重复执行，必须将上次执行到的日志索引（last applied index）也持久化下来。

如果服务器丢失了其持久化状态的任何一部分，那么它就无法以原有身份安全地重新加入集群。这种情况下，通常可以通过修改集群成员配置（详见第4章），以一个新身份将该服务器重新加入集群。

然而，如果大多数服务器同时丢失了其持久化状态，则可能会导致日志条目永久丢失，集群成员变更等操作也无法继续进行。此时，系统管理员需要接受数据丢失的可能性，才能让系统继续运行下去。

🌲 时序与可用性

Raft的一个基本要求是：系统的安全性不得依赖于时序（timing）。换言之，系统不能因为某些事件发生得比预期快或慢而产生错误结果。然而，可用性（即系统能否及时响应客户端请求）却不可避免地依赖时序。

例如，如果消息交换的耗时超过了服务器之间平均故障间隔时间（MTBF），那么候选人可能还没来得及赢得选举就已经崩溃。没有稳定的领导者，Raft将无法继续前进。

领导者选举是Raft中对时序最敏感的部分。为了让系统能够成功选出并维持一个稳定的领导者，必须满足以下时序条件：

1

broadcastTime << electionTimeout << MTBF

其中：

  • broadcastTime表示一个服务器并行向集群中所有其他服务器发送RPC请求并收到响应的平均时间；
  • electionTimeout是第3.4节中提到的选举超时时间；
  • MTBF是单台服务器的平均故障间隔时间（Mean Time Between Failures）。

该不等式的含义如下：

  • broadcastTime应远小于electionTimeout，这样领导者才能稳定地发送心跳消息，防止跟随者发起选举；再加上选举超时时间具有随机性，这也降低了出现投票分裂的可能性。
  • electionTimeout又应远小于MTBF，以便系统能够持续稳定地推进。当领导者崩溃时，系统的不可用时间大致等于一次选举超时的时长，我们希望这段时间占整个运行时间的比例尽可能小。

在这三者中，broadcastTime和MTBF是底层系统固有的性质，而electionTimeout是我们可以自行设定的参数。

Raft的RPC通常要求接收方将信息写入稳定存储，因此broadcastTime可能在0.5到20毫秒之间，具体取决于存储技术。因此，合理的electionTimeout一般会在10到500毫秒之间。而普通服务器的MTBF往往在数月甚至更长，这就很容易满足上述时序要求。

第9章将进一步讨论如何合理设置electionTimeout，以及这个参数对系统可用性与领导者选举性能的影响。

🌲 领导权转移扩展（Leadership Transfer Extension）

本节描述了Raft的一个可选扩展：允许某个服务器将其领导权主动转移给另一个服务器。领导权转移在以下两种场景中可能非常有用：

  1. 领导者需要主动下台时。 比如，为了维护需要重启，或者它即将被移出集群（详见第4章）。在当前Raft协议下，领导者下台后，整个集群将会在一个选举超时时间内处于空闲状态，直到其他某个服务器超时并赢得选举为止。这种短暂的不可用状态可以通过让当前领导者在下台前主动转移领导权来避免。
  2. 某些服务器比其他服务器更适合担任领导者时。 例如，负载较高的服务器不适合担任领导者；又如在广域网部署中，优先选择主数据中心的服务器作为领导者可以减少客户端与领导者之间的通信延迟。其他共识算法可能可以在选举阶段直接体现这些偏好，但Raft要求新的领导者必须拥有足够最新的日志，这个条件可能并不总能满足优选服务器。因此，Raft可以让当前领导者定期检查哪些追随者可能更适合领导集群，如果发现更合适的目标节点，则将领导权转移给它。（要是现实世界的领导人也这么通情达理就好了。）

为了在Raft中实现领导权转移，当前的领导者会将日志完整地同步到目标服务器，然后由目标服务器主动发起一次选举，无需等待超时。这样做可以保证目标服务器在新任期开始时拥有所有已提交的日志项。通过多数投票机制，仍然能确保Raft的安全性属性（如“领导者日志完整性”）得以维持。具体步骤如下：

  1. 当前领导者停止接收新的客户端请求；
  2. 当前领导者使用普通日志复制机制（见第3.5节），将目标服务器的日志更新至与自己一致；
  3. 当前领导者向目标服务器发送一个TimeoutNow请求。该请求的效果等同于目标服务器的选举定时器立刻触发：目标服务器立即发起选举（增加任期号，并转换为候选人）。

当目标服务器收到TimeoutNow请求后，它大概率会在其他服务器之前启动选举，从而成为新任期的领导者。随后它发送给原领导者的第一条消息中会包含新的任期号，原领导者据此识别到自己的任期已过期，并自动下台。此时，领导权转移完成。

如果目标服务器在转移过程中失败了，集群则需继续对客户端提供服务。如果在约一个选举超时周期内领导权转移没有完成，原领导者会中止转移过程并重新开始接受客户端请求。如果原领导者的判断有误（即目标服务器其实并未失效），最坏的结果也只不过是额外进行了一次选举，之后服务即可恢复。

这个领导权转移的方案始终在Raft协议的正常状态转换流程内运行，因此不会破坏系统的安全性。例如，Raft本身就能容忍任意快慢的时钟；当目标服务器收到TimeoutNow请求时，其效果等同于它的时钟突然快速前移——这是被Raft明确允许的。不过，目前我们尚未在实现中加入或评估这个领导权转移扩展。

🌲 结论

本章解决了基于共识系统的所有核心问题。Raft不仅仅是实现对单一值的共识（如单一决议的Paxos），它实现了对一条不断增长的命令日志的共识，这正是构建复制状态机所必需的。同时，Raft在达成共识后会将信息传播给其他服务器，使它们也能获知已提交的日志条目。Raft通过选举集群领导者，由领导者单方面做出决策，并且在新领导者上任时只传输必要的日志条目，来实现一种切实且高效的共识机制。我们已在LogCabin项目中实现了Raft的思想（该项目在第10章详细介绍）。

Raft使用的机制相当简洁，只用两个RPC（RequestVote和AppendEntries）便解决了完整的共识问题。值得注意的是，设计一个简洁紧凑的算法并非Raft的明确目标，而是我们专注于“易于理解”的设计理念的自然结果：每一条机制都必须有明确的动机和详尽的解释。我们发现冗余或绕弯子的机制难以自圆其说，于是自然在设计过程中被剔除。

除非我们确信某些问题会影响大多数Raft部署，否则不会特意在Raft中处理它们。因此，Raft某些部分看起来可能略显“幼稚”。例如，Raft中服务器检测“投票分裂”是通过等待选举超时来完成的；理论上，它们可以通过统计已授予的票数更早地检测甚至解决分裂投票，但我们没有实现这一优化，因为它增加了复杂度且实际收益有限——在配置良好的部署中，分裂投票非常罕见。Raft的其他部分则可能显得过于保守。比如，领导者只直接提交自己任期内的条目，尽管在某些特殊情况下它本可以安全提交先前任期的条目。如果采用更复杂的提交规则，虽然性能提升不明显，但会降低易理解性；而目前规则仅仅会导致提交略微延迟。与他人讨论Raft时，我们发现很多人都忍不住提出这些优化建议，但当设计目标是易理解性时，过早的优化应当被摒弃。

不可避免地，本章可能遗漏了一些在实际应用中有用的特性或优化。随着实现者对Raft的理解加深，他们会发现何时以及为何需要这些额外特性，并可能为某些实际部署实现它们。全章中，我们也提及了一些目前看来并非必需的可选扩展，但它们可为实现者在需要时提供指导。通过聚焦于易理解性，我们希望为实现者提供一个坚实的基础，使他们能够根据实际经验灵活调整Raft。由于Raft在我们的测试环境中运行良好，我们预计这些调整更多是直接的扩展，而非根本性的变革。

分布式
分布式 共识算法 Raft
This post is licensed under CC BY 4.0 by the author.