title: Paxos vs Raft：分布式共识是否已达成一致？ author: - Heidi Howard, University of Cambridge, Cambridge, UK, first.last@cl.cam.ac.uk - Richard Mortier, University of Cambridge, Cambridge, UK, first.last@cl.cam.ac.uk abstract: | 分布式共识是构建容错、强一致分布式系统的基础原语。尽管已有多种分布式共识算法被提出，但生产系统中占主导地位的只有两种：传统的、久负盛名且精妙的 Paxos；以及较新的 Raft，它被定位为比 Paxos 更易理解的替代方案。
本文探讨的问题是：对于分布式共识，哪种算法是更优的解决方案——Paxos 还是 Raft？我们对二者进行分析，通过使用 Raft 的术语与务实的抽象来描述一种简化的 Paxos 算法，以精确地揭示二者的差异。
我们发现，Paxos 与 Raft 在分布式共识上采取了极为相似的方法，仅在领导者选举的策略上有所不同。最显著的差异在于：Raft 仅允许拥有最新日志条目的服务器成为领导者，而 Paxos 允许任何服务器成为领导者，只要该服务器随后更新其日志以确保其为最新。Raft 的方法在简洁之余出奇地高效，因为与 Paxos 不同，它无需在领导者选举过程中交换日志条目（log entries）。我们推测，Raft 的可理解性很大程度上来自于论文清晰的呈现，而非其底层算法本身的本质特征。
引言
状态机复制（state machine replication）[^1] 被广泛用于将一组不可靠的主机组合成单一可靠的服务，从而提供强一致性保证，包括线性一致性（linearizability）[^13]。因此，程序员可以将使用复制状态机实现的服务视为单一系统，从而便于对其预期行为进行推理。状态机复制要求每个状态机以相同顺序接收相同的操作，这可以通过分布式共识（distributed consensus）来实现。
Paxos 算法[^16] 是分布式共识的同义词。尽管 Paxos 取得了巨大成功，但它以难以理解著称，这使得对其推理、正确实现以及安全优化都变得困难。这一点从众多以更简洁方式解释该算法的尝试中可见一斑[^4][^17][^22][^23][^25][^29][^35]，也是 Raft[^28] 诞生的动机所在。Raft 的作者声称，Raft 与 Paxos 同样高效，但更易理解，因此为构建实际系统提供了更好的基础。Raft 试图通过以下三种截然不同的方式实现这一目标：
- 呈现方式：首先，Raft 论文引入了一种新的抽象，用于在状态机复制语境下描述基于领导者的共识。这种务实的呈现方式在工程师中广受欢迎。
- 简洁性：其次，Raft 论文将简洁性置于性能之上。例如，Raft 按顺序决定日志条目（log entries），而 Paxos 通常允许乱序决定，但因此需要一个额外的协议来填补可能由此产生的日志空缺。
- 底层算法：最后，Rft 算法在领导者选举（leader election）上采取了一种新颖的方法，改变了领导者的选举方式以及安全性的保证方式。
Raft 迅速流行起来[^30]。如今的生产系统分为两派：一派使用 Paxos[^3][^5][^31][^33][^36][^38]，另一派使用 Raft[^2][^8-10][^15][^24][^34]。
要回答 Paxos 还是 Raft 是分布式共识的更优解决方案这一问题，我们必须首先回答：这两种算法在共识方法上究竟有何不同？这不仅有助于评估这些算法，还可能使 Raft 受益于数十年来针对 Paxos 性能优化的研究[^6][^12][^14][^18-20][^26][^27]，反之亦然[^1][^37]。
然而，回答这一问题并非易事。Paxos 通常不被视为单一算法，而被视为解决分布式共识的一族算法。Paxos 的通用性（或称欠规约性，取决于视角）意味着不同论文中对该算法的描述各异，有时差异相当显著。
为解决这一问题，本文呈现一种通过对各种已发表的 Paxos 描述进行综述而得到的 Paxos 简化版本。该算法我们简称为 Paxos，比其最初描述[^16] 更贴近 Paxos 的当代使用方式。它在其他文献中被称为多决策 Paxos（multi-decree Paxos），或简称 MultiPaxos，以区别于单决策 Paxos——后者决定单个值，而非完全有序的序列
背景
本文在状态机复制（state machine replication）的语境下研究分布式共识。状态机复制要求将应用程序的确定性状态机复制到 $n$ 台服务器上，每台服务器都按相同顺序应用同一组操作。这通过复制日志来实现，由分布式共识算法（通常是 Paxos 或 Raft）进行管理。
我们假设系统是非拜占庭的（non-Byzantine）[21]，但不假设系统是同步的。消息可能被任意延迟，参与服务器可以以任意速度运行，但我们假设消息交换是可靠且有序的（例如通过使用 TCP/IP）。我们的正确性不依赖于时钟同步，但活性（liveness）需要时钟同步 [11]。我们假设 $n$ 台服务器各自拥有唯一标识 $s$，其中 $s \in {0..(n-1)}$。我们假设操作是唯一的，这可以通过向每个操作附加（序号，服务器标识）这一对信息轻松实现。
Paxos 与 Raft 的方法
包括 Paxos 和 Raft 在内的许多共识算法都采用基于领导者（leader）的方法来解决分布式共识问题。从高层来看，这些算法的运行方式如下：
在 $n$ 台服务器中指定一台作为领导者。所有针对状态机的操作都发送给领导者。领导者将该操作追加到自己的日志中，并要求其他服务器也执行同样操作。一旦领导者收到来自多数服务器对该操作已成功复制的确认，就在自己的状态机上应用该操作。此过程不断重复，直至领导者发生故障。当领导者失效时，由另一台服务器接替成为领导者。选举新领导者的过程至少需要多数服务器参与，以保证新领导者不会覆盖任何先前已应用的操作。
现在我们更详细地考察 Paxos 和 Raft。读者可以参阅附录 A 与 B 中提供的 Paxos 和 Raft 的概述以辅助理解。本文聚焦于 Paxos 与 Raft 的核心要素；受篇幅所限，我们不比较垃圾回收、日志压缩、读操作以及重配置算法。
基础
如图 1 所示，在任意时刻，一台服务器可以处于以下三种状态之一：
Follower（跟随者）：一种被动状态，仅负责回复 RPC。
Candidate（候选者）：一种主动状态，通过 RequestVote RPC 争取成为领导者。
Leader（领导者）：一种主动状态，负责使用 AppendEntries RPC 向复制日志中添加操作。
初始时，服务器处于 follower 状态。每台服务器保持 follower 状态，直至它认为当前领导者已经失效。此时该 follower 转变为 candidate，并通过 RequestVote RPC 尝试被选举为领导者。若成功，该 candidate 成为 leader。新领导者必须定期发送 AppendEntries RPC 作为心跳（keepalive），以防止 follower 因超时而转变为 candidate。
每台服务器保存一个自然数——任期号（term），它随时间单调递增。初始时，每台服务器的当前任期号为 0。发送方（后文简称"发送者"）的当前任期号会包含在每个 RPC 中。当一台服务器（后文简称"接收方"）收到 RPC 时，它首先检查其中包含的任期号。若发送者的任期号大于接收方的任期号，则接收方在回复 RPC 之前先更新自己的任期号，并且若接收方原本是 candidate 或 leader，则回退为 follower。若发送者的任期号等于接收方的任期号，则接收方照常回复 RPC。若发送者的任期号小于接收方的任期号，则接收方向发送者作否定回复，并在响应中附带自己的任期号。发送者收到这样的响应后，将回退为 follower 并更新自己的任期号。
正常运行
当领导者收到一个操作时，它将该操作连同当前任期号一并追加到自己日志的末尾。操作与任期号这一对称为一条日志条目（log entry）。然后领导者向所有其他服务器发送 AppendEntries RPC 以携带这条新的日志条目。每台服务器维护一个提交索引（commit index），用于记录哪些日志条目可以安全地应用到其状态机，并向领导者确认成功收到新的日志条目。一旦领导者收到来自多数服务器的肯定响应，便更新自己的提交索引，并在自己的状态机上应用该操作。领导者
1 2 3 4
1 2 3 4
4 C
s1 1 A
2 B
s1 1 A
4 B
2 C
2 C
s2 1 A
2 B
s2 1 A
2 B
s3 1 A
3 B
3 D
3 E
s3 1 A
3 B
3 D
3 E
(a) 选举新领导者之前的日志初始状态。
(b) 在获得来自 s2 的选票后，s1 成为 term 4 的领导者。
1 2 3 4
1 2 3 4
s1 1 A
2 B
s1 1 A
2 B
2 C
s2 1 A
2 B
5 D
5 E
s2 1 A
2 B
s3 1 A
3 B
3 D
3 E
s3 1 A
6 B
6 D
6 E
(c) 在获得来自 s3 的选票后，s2 成为 term 5 的领导者。
(d) 在获得来自 s1 或 s2 的选票后，s3 成为 term 6 的领导者。
随后在后续的 AppendEntries RPC 中包含已更新的 commit index。
只有当日志中某条（或某几条）日志条目之前的部分与领导者的日志完全一致时，follower 才会追加该条（或该组）日志条目。这保证了日志条目按顺序追加，防止日志出现空洞，并确保 follower 将正确的日志条目应用到其状态机。
3.3 处理领导者失效
上述过程会持续进行，直至领导者失效，此时需要建立新的领导者。Paxos 与 Raft 在此过程中采取了不同的做法，因此我们分别加以描述。
Paxos。 follower 在未能及时收到来自领导者的 AppendEntries RPC 后会超时。随后它转变为 candidate，并将其 term 更新为下一个满足 $t \bmod n = s$ 的 term，其中 $t$ 为下一个 term，$n$ 为服务器数量，$s$ 为该 candidate 的服务器标识。candidate 将向其他服务器发送 RequestVote RPC。该 RPC 包含 candidate 的新 term 以及 commit index。当某服务器收到 RequestVote RPC 时，只要 candidate 的 term 大于其自身的 term，它就会给出肯定的响应。该响应还包含该服务器在其日志中位于 candidate 的 commit index 之后的所有日志条目。
一旦 candidate 收到来自多数服务器的肯定 RequestVote 响应，在成为领导者之前，candidate 必须确保其日志包含所有已提交的条目。其做法如下：对于 commit index 之后的每个索引，领导者会审阅它在响应中收到的日志条目以及自身的日志。如果 candidate 看到了该索引对应的某条日志条目，则会用该条目及新的 term 更新自身日志。如果 leader 看到了同一索引处的多条日志条目，则会用来自最大 term 的那一条以及新的 term 更新自身日志。图 2 给出了一个示例。此后 candidate 便可成为领导者，并开始将其日志复制到其他服务器。
Raft。 在未能及时收到来自领导者的 AppendEntries RPC 后，至少会有一个 follower 超时。它将转变为 candidate 并递增其 term。candidate 将向其他服务器发送 RequestVote RPC。每条 RPC 包含 candidate 的 term，以及 candidate 的最后一条日志的 term 和 index。当某服务器收到 RequestVote 请求时，只要满足以下条件，它就会给出肯定响应：candidate 的 term 大于或等于其自身的 term、它在本 term 中尚未为任何 candidate 投票，以及 candidate 的日志至少与其自身一样新。最后一项条件可以通过如下方式检验：candidate 的最后一条日志的 term 大于该服务器的对应 term；若两者相同，则 candidate 的最后索引大于该服务器的对应索引。
一旦 candidate 收到来自多数服务器的肯定 RequestVote 响应，它便可成为领导者并开始复制其日志。然而，为了保证安全性，Raft 要求领导者在新 term 中至少有至少一条日志条目被提交之前，不得更新其 commit index。
由于在同一个 term 中可能存在多个 candidate，选票可能被瓜分，以至于没有任何 candidate 获得多数票。在这种情况下，candidate 会在超时后以更高的 term 开启新一轮选举。
3.4 安全性
两种算法都保证以下性质：
定理 3.1（状态机安全性，State Machine Safety）。 若某服务器已将给定索引处的一条日志条目应用到其状态机，则任何其他服务器都永远不会在相同索引处应用一条不同的日志条目。
由于每个 term 至多存在一名领导者，且领导者不会覆盖自身的日志，我们可以通过证明下述命题来完成证明：
定理 3.2（领导者完备性，Leader Completeness）。 若操作 op 由 term $t$ 中的领导者在索引 $i$ 处提交，则所有 term $> t$ 的领导者在索引 $i$ 处也将持有操作 op。
Paxos 的证明草图。假设操作 op 在任期 t 下被提交到索引 $i$。我们将对大于 $t$ 的任期进行归纳证明。
基础情形： 如果存在任期 $t+1$ 的领导者，那么它在索引 $i$ 处将拥有操作 op。
由于任意两个多数派仲裁集（majority quorum）相交，并且消息按任期有序，因此至少有一台在索引 $i$ 处拥有任期 $t$ 的操作 op 的服务器，曾对任期 $t+1$ 领导者发起的 RequestVote RPC 作出肯定回复。该服务器自任期 $t$ 的领导者之后，未对任何其他领导者的 AppendEntries RPC 作出肯定回复，因此既不能删除也不能覆盖此操作。由于该领导者不会收到任期大于 $t$ 的任何 log entry，它将选择操作 op。
归纳情形： 假设任期 $t+1$ 到 $t+k$ 的任何领导者在索引 $i$ 处都拥有操作 op。若存在任期 $t+k+1$ 的领导者，则它在索引 $i$ 处同样拥有操作 op。
由于任意两个多数派仲裁集相交，并且消息按任期有序，因此至少有一台在索引 $i$ 处拥有任期 $t$ 到 $t+k$ 的操作 op 的服务器，曾对任期 $t+k+1$ 领导者发起的 RequestVote RPC 作出肯定回复。原因是：该服务器除任期 $t$ 到 $t+k$ 的领导者之外，未对任何其他领导者的 AppendEntries RPC 作出肯定回复，因此既不能删除也不能覆盖此操作。根据归纳假设，所有这些领导者在索引 $i$ 处同样拥有操作 op，因此不会将其覆盖。只有当该领导者收到一条在索引 $i$ 处具有更高任期且包含不同操作的 log entry 时，它才可能选择另一条操作。根据归纳假设，所有任期 $t$ 到 $t+k$ 的领导者在索引 $i$ 处同样拥有操作 op，因此不会在索引 $i$ 处写入其他操作。
□
Raft 的证明采用同样的归纳方式，但由于 Raft 在 leader election 上采取了不同的策略，证明细节有所不同。
4 讨论
Raft 与 Paxos 在 leader election 上采取了不同的策略，概括于表 1 中。我们从可理解性和效率两个维度进行比较，以判断孰优孰劣。
可理解性。 Raft 保证：若两条日志包含同一操作，则该操作在两条日志中的索引和任期必然相同。换言之，每个操作都被赋予唯一的索引–任期对。然而在 Paxos 中并非如此——如图 2b 中操作 B 和 C 所示，一个操作可能被未来的领导者赋予更高的任期。在 Paxos 中，提交索引之前的 log entry 可能会被覆盖。由于被覆盖的 entry 只会由相同操作的 entry 取代，因此这是安全的，但相较于 Raft 的做法，Paxos 的方式不够直观。
反过来说，Paxos 使得"当 log entry 存在于多数服务器上即可提交"成为安全操作；而 Raft 并非如此，它要求领导者仅当 log entry 既存在于多数服务器上、且领导者已提交来自当前任期的后续 log entry 时，才能提交来自前一个任期的 log entry。
在 Paxos 中，领导者复制的 log entry 要么来自当前任期，要么已经处于已提交状态。从图 2 中可以看到，领导者上提交索引之后的所有 log entry 均具有当前任期。而 Raft 则不同：领导者可能正在复制来自先前任期、尚未提交的 entry。
总体而言，我们认为 Raft 的方式略优于 Paxos，但优势并不显著。
效率。 在 Paxos 中，若多台服务器同时成为候选人，则拥有更高任期的候选人将赢得选举。在 Raft 中，若多台服务器同时成为候选人，由于它们具有相同的任期，票数可能被分散，导致无人赢得选举。Raft 通过让 follower 在选举超时后再等待一段额外的时间（从均匀随机分布中抽取）来缓解这一问题。因此，我们预期 Raft 在 leader election 耗时上既更慢，方差也更大。
然而，Raft 的 leader election 阶段比 Paxos 更为轻量。Raft 仅允许日志足够新的候选人成为领导者，因此在 leader election 期间无需发送 log entry。Paxos 则不然：每条肯定的 RequestVote response 都包含 follower 在候选人提交索引之后的 log entry。虽然存在多种减少所发送 log entry 数量的方案，但若领导者的日志并非已是最新，最终总是需要发送部分 log entry。
Paxos 比 Raft 发送更多 log entry 的情形不止体现在 RequestVote response 中。在两种算法中，一旦候选人成为领导者，它都会将自身日志复制到所有其他服务器。在 Paxos 中，某条 log entry 可能已被领导者赋予了新的任期，因此领导者可能向已经拥有该 entry 副本的服务器再次发送同一 entry 的副本。Raft 则不存在此种情况：在 log entry 的整个生命周期内，其任期始终保持不变。
总体而言，与 Paxos 相比，Raft 的 leader election 方案以如此简单的设计实现了惊人的效率。
5 与经典 Paxos 的关系
熟悉 Paxos 的读者可能觉得我们描述的 Paxos 与此前公开发表的版本有所不同，因此下面概述本文中的 Paxos 算法如何与文献中的其他描述相对应。
角色。 Paxos 的某些描述将其职责划分为三种角色：proposer、acceptor 与 learner [@ref17]，或 leader、acceptor 与 replica [@ref35]。我们的表述仅采用单一角色，即 server，囊括所有角色。使用单一角色的表述也曾以 replica 为名 [@ref7]，
表 1 Raft 与 Paxos 在 leader election 上的对比
Paxos vs Raft
Paxos
服务器 $s$ 只能在满足 $t \bmod n = s$ 的任期 $t$ 中成为候选者。每个任期仅有一个候选者，因此每个任期至多产生一个领导者。
候选者在收到多数 follower 的 RequestVote 响应后，将其响应中所包含的最高任期 log entries 加入自身日志。
来自先前任期的 log entries 以当前领导者的任期追加至领导者日志。领导者随后像对待本任期条目一样复制这些 log entries。
Raft
follower 可在任何任期成为候选者，但每个 follower 在同一任期仅投票给一名候选者，因此仅有一名候选者可获得多数票并成为领导者。
仅当候选者的日志至少与 follower 同样新近时，follower 才授予其投票。这保证候选者仅在其日志至少与多数 follower 同样新近时才可成为领导者。
领导者保持原任期向其他服务器复制 log entries。直至其复制了一条来自本任期的新 log entry 之后，领导者才认为这些条目已提交。
表 1. Paxos 与 Raft 差异汇总
术语。Terms（任期）也称为 views、ballot numbers [35]、proposal numbers [17]、round numbers 或 sequence numbers [7]。本文中的 leader 也称为 master [7]、primary、coordinator 或 distinguished proposer [17]。通常，服务器处于候选者身份的阶段称为 phase-1，处于 leader 身份的阶段称为 phase-2。RequestVote RPC 常被称为 phase1a 与 phase1b 消息 [35]、prepare 请求与响应 [17] 或 prepare 与 promise 消息。AppendEntries RPC 常被称为 phase2a 与 phase2b 消息 [35]、accept 请求与响应 [17] 或 propose 与 accept 消息。
任期（Terms）。Paxos 仅要求任期构成全序，且每个服务器被分配互不相交的任期集合（以保证安全性），并允许每个服务器使用大于任何其他任期的值（以保证活性）。尽管部分 Paxos 描述采用与我们相同的轮询自然数 [7]，另一些则使用字典序的 (整数, 服务器 ID) 对，其中每个服务器仅使用包含自身 ID 的任期 [35]。
顺序（Ordering）。我们的 log entries 按顺序复制与决议。这虽非必需，但可避免填补日志空洞（log gaps）的复杂性 [17]。类似地，部分 Paxos 描述对并发决议数量施加限制，这在重配置（reconfiguration）场景下通常是必要的 [17, 35]。
图 1. Paxos 与 Raft 服务器状态之间的转换。蓝色转换专属于 Raft。
图 2. 运行 Paxos 的三台服务器的日志。图 (a) 展示触发 leader election 时的日志状态。图 (b—d) 展示已选出 leader 但尚未发送首个 AppendEntries RPC 时的日志状态。黑线表示 commit index，红色文字突出显示日志变更。
总结
Raft 算法被提出，旨在解决被广泛研究的 Paxos 算法长期存在的可理解性（understandability）问题。本文证明，Raft 在可理解性方面的优势主要源于其务实的抽象与出色的表述方式。我们采用与 Raft 相同的描述方式对简化的 Paxos 算法加以阐释后发现，两种算法的差异仅体现在 leader election 的处理方式上。具体而言：
(i) Paxos 在服务器之间划分任期，而 Raft 允许 follower 在任意任期成为候选者，但 follower 在每个任期仅投票给一名候选者。
(ii) Paxos 的 follower 可为任何候选者投票，而 Raft 的 follower 仅在候选者的日志至少与自己同样新近时才为其投票。
(iii) 若领导者拥有来自先前任期的未提交 log entries，Paxos 会在当前任期复制这些条目，而 Raft 则在其原始任期进行复制。
Raft 论文声称 Raft 在可理解性上显著优于 Paxos，并在效率上与之持平。然而，我们发现两者的可理解性并无显著差异，但 Raft 的 leader election 在与 Paxos 比较时出人意料地轻量。本文给出的两种算法在设计上均为朴素的（naïve by design），尽管常以增加复杂度为代价，但无疑可通过优化以提升性能。
致谢。本工作部分受 EPSRC EP/N028260/2 与 EP/M02315X/1 资助。
参考文献 {-}
[1] Arora, V., Mittal, T., Agrawal, D., El Abbadi, A., Xue, X., Zhiyanan, Z., and Zhujianfeng, Z. Leader or majority: Why have one when you can have both? improving read scalability in raft-like consensus protocols. In Proceedings of the 9th USENIX Conference on Hot Topics in Cloud Computing (USA, 2017), HotCloud'17, USENIX Association, p. 14.
[2] Atomix. htps://atomix.io.
[3] Baker, J., Bond, C., Corbett, J. C., Furman, J., Khorlin, A., Larson, J., Leon, J.-M., Li, Y., Lloyd, A., and Yushprakh, V. Megastore: Providing scalable, highly available storage for interactive services. In Proceedings of the Conference on Innovative Data system Research (CIDR) (2011), pp. 223–234.
[4] Boichat, R., Dutta, P., Frølund, S., and Guerraoui, R. Deconstructing paxos. SIGACT News 34, 1 (Mar. 2003), 47–67.
[5] Burrows, M. The chubby lock service for loosely-coupled distributed
systems. In Proceedings of the 7th Symposium on Operating Systems Design and Implementation (USA, 2006), OSDI ’06, USENIX Association, pp. 335–350. [6] Camargos, L. J., Schmidt, R. M., and Pedone, F. Multicoordinated
paxos. In Proceedings of the Twenty-Sixth Annual ACM Symposium on Principles of Distributed Computing (New York, NY, USA, 2007), PODC ’07, Association for Computing Machinery, pp. 316–317. [7] Chandra, T. D., Griesemer, R., and Redstone, J. Paxos made live:
An engineering perspective. In Proceedings of the Twenty-Sixth Annual ACM Symposium on Principles of Distributed Computing (New York, NY, USA, 2007), PODC ’07, Association for Computing Machinery, pp. 398–407. [8] CockroachDB. https://www.cockroachlabs.com. [9] Consul by hashicorp. https://www.consul.io. [10] etcd. https://coreos.com/etcd/. [11] Fischer, M. J., Lynch, N. A., and Paterson, M. S. Impossibility of dis-
tributed consensus with one faulty process. J. ACM 32, 2 (Apr. 1985), 374–382. [12] Gafni, E., and Lamport, L. Disk paxos. In Proceedings of the 14th In-
ternational Conference on Distributed Computing (Berlin, Heidelberg, 2000), DISC ’00, Springer-Verlag, pp. 330–344. [13] Herlihy, M. P., and Wing, J. M. Linearizability: A correctness con-
dition for concurrent objects. ACM Trans. Program. Lang. Syst. 12, 3 (July 1990), 463–492. [14] Kraska, T., Pang, G., Franklin, M. J., Madden, S., and Fekete, A.
Mdcc: Multi-data center consistency. In Proceedings of the 8th ACM European Conference on Computer Systems (New York, NY, USA, 2013), EuroSys ’13, Association for Computing Machinery, pp. 113–126. [15] Kubernetes: Production-grade container orchestration. https://kubernetes.io. [16] Lamport, L. The part-time parliament. ACM Trans. Comput. Syst. 16,
2 (May 1998), 133–169. [17] Lamport, L. Paxos made simple. ACM SIGACT News (Distributed
Computing Column) 32, 4 (Whole Number 121, December 2001) (December 2001), 51–58. [18] Lamport, L. Generalized consensus and paxos. Tech. Rep. MSR-TR-
2005-33, Microsoft, March 2005. [19] Lamport, L. Fast paxos. Distributed Computing 19 (October 2006),
79–103. [20] Lamport, L., and Massa, M. Cheap paxos. In Proceedings of the 2004
International Conference on Dependable Systems and Networks (USA, 2004), DSN ’04, IEEE Computer Society, p. 307. [21] Lamport, L., Shostak, R., and Pease, M. The byzantine generals
problem. ACM Trans. Program. Lang. Syst. 4, 3 (July 1982), 382–401. [22] Lampson, B. The abcd’s of paxos. In Proceedings of the Twentieth
Annual ACM Symposium on Principles of Distributed Computing (New York, NY, USA, 2001), PODC ’01, Association for Computing Machinery, p. 13. [23] Lampson, B. W. How to build a highly available system using consen-
sus. In Proceedings of the 10th International Workshop on Distributed Algorithms (Berlin, Heidelberg, 1996), WDAG ’96, Springer-Verlag, pp. 1–17. [24] M3: Uber’s open source, large-scale metrics platform for prometheus.
https://eng.uber.com/m3/. [25] Meling, H., and Jehl, L. Tutorial summary: Paxos explained from
scratch. In Proceedings of the 17th International Conference on Principles of Distributed Systems - Volume 8304 (Berlin, Heidelberg, 2013), OPODIS 2013, Springer-Verlag, pp. 1–10. [26] Moraru, I., Andersen, D. G., and Kaminsky, M. There is more con-
sensus in egalitarian parliaments. In Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles (New York, NY, USA, 2013), SOSP ’13, Association for Computing Machinery, pp. 358–372.
Heidi Howard and Richard Mortier
[27] Moraru, I., Andersen, D. G., and Kaminsky, M. Paxos quorum leases: Fast reads without sacrificing writes. In Proceedings of the ACM Symposium on Cloud Computing (New York, NY, USA, 2014), SOCC ’14, Association for Computing Machinery, pp. 1–13. [28] Ongaro, D., and Ousterhout, J. In search of an understandable
consensus algorithm. In Proceedings of the 2014 USENIX Conference on USENIX Annual Technical Conference (USA, 2014), USENIX ATC’14, USENIX Association, pp. 305–320. [29] Prisco, R. D., Lampson, B. W., and Lynch, N. A. Revisiting the paxos
algorithm. In Proceedings of the 11th International Workshop on Distributed Algorithms (Berlin, Heidelberg, 1997), WDAG ’97, SpringerVerlag, pp. 111–125. [30] The raft consensus algorithm. https://raft.github.io. [31] Ramakrishnan, R., Sridharan, B., Douceur, J. R., Kasturi, P.,
Krishnamachari-Sampath, B., Krishnamoorthy, K., Li, P., Manu, M., Michaylov, S., Ramos, R., and et al. Azure data lake store: A hyperscale distributed file service for big data analytics. In Proceedings of the 2017 ACM International Conference on Management of Data (New York, NY, USA, 2017), SIGMOD ’17, Association for Computing Machinery, pp. 51–63. [32] Schneider, F. B. Implementing fault-tolerant services using the state
machine approach: A tutorial. ACM Comput. Surv. 22, 4 (Dec. 1990), 299–319. [33] Schwarzkopf, M., Konwinski, A., Abd-El-Malek, M., and Wilkes,
J. Omega: Flexible, scalable schedulers for large compute clusters. In Proceedings of the 8th ACM European Conference on Computer Systems (New York, NY, USA, 2013), EuroSys ’13, Association for Computing Machinery, pp. 351–364. [34] Trillian: General transparency. https://github.com/google/trillian/. [35] Van Renesse, R., and Altinbuken, D. Paxos made moderately com-
plex. ACM Comput. Surv. 47, 3 (Feb. 2015). [36] Verma, A., Pedrosa, L., Korupolu, M., Oppenheimer, D., Tune, E.,
and Wilkes, J. Large-scale cluster management at google with borg. In Proceedings of the Tenth European Conference on Computer Systems (New York, NY, USA, 2015), EuroSys ’15, Association for Computing Machinery. [37] Zhang, Y., Ramadan, E., Mekky, H., and Zhang, Z.-L. When raft
meets sdn: How to elect a leader and reach consensus in an unruly network. In Proceedings of the First Asia-Pacific Workshop on Networking (New York, NY, USA, 2017), APNet’17, Association for Computing Machinery, pp. 1–7. [38] Zheng, J., Lin, Q., Xu, J., Wei, C., Zeng, C., Yang, P., and Zhang, Y.
Paxosstore: High-availability storage made practical in wechat. Proc. VLDB Endow. 10, 12 (Aug. 2017), 1730–1741.
Paxos 算法
本节给出我们简化后的、采用 Raft 风格的 Paxos 算法。 红色文字为 Paxos 所独有。
状态
所有服务器上的持久化状态：
（在响应 RPC 之前需在稳定存储上更新）
| 名称 | 说明 |
|---|---|
| currentTerm | 服务器已见到的最新任期（首次启动时初始化为 0，单调递增） |
| log[ ] | 日志条目（log entries）；每个条目包含状态机（state machine）命令，以及该条目被领导者接收时的任期（首个索引为 1） |
所有服务器上的易失状态：
| 名称 | 说明 |
|---|---|
| commitIndex | 已知已提交的最高日志条目的索引（初始化为 0，单调递增） |
| lastApplied | 已应用到状态机的最高日志条目的索引（初始化为 0，单调递增） |
候选者上的易失状态：
（选举后重新初始化）
| 名称 | 说明 |
|---|---|
| entries[] | 随投票一同收到的日志条目 |
领导者上的易失状态：
（选举后重新初始化）
| 名称 | 说明 |
|---|---|
| nextIndex[ ] | 对每台服务器，下一条要发送给该服务器的日志条目索引（初始化为领导者 commitIndex + 1） |
| matchIndex[ ] | 对每台服务器，已知在该服务器上已复制的最高日志条目索引（初始化为 0，单调递增） |
AppendEntries RPC
由领导者调用以复制日志条目（log entries）；也用作心跳。
参数：
| 名称 | 说明 |
|---|---|
| term | 领导者的任期 |
| leaderCommit | 领导者的 commitIndex |
| prevLogIndex | 紧接在新条目之前的日志条目索引 |
| prevLogTerm | prevLogIndex 条目的任期 |
| entries[ ] | 待存储的日志条目（心跳时为空；为提高效率可一次发送多条） |
结果：
| 名称 | 说明 |
|---|---|
| term | currentTerm，供领导者更新自身 |
| success | 若跟随者包含与 prevLogIndex 和 prevLogTerm 匹配的条目，则为 true |
接收方实现：
- 若 term < currentTerm，则回复 false。
- 若日志中不包含 prevLogIndex 处任期与 prevLogTerm 匹配的条目，则回复 false。
- 若已存在的条目与新条目发生冲突（same index（相同索引）但任期不同），则删除该已存在条目及其之后的所有条目。
- 追加任何日志中尚不存在的新条目。
- 若 leaderCommit > commitIndex：令 commitIndex = min(leaderCommit, 最后一条新条目的索引)。
RequestVote RPC
由候选者调用以收集选票。
参数：
| 名称 | 说明 |
|---|---|
| term | 候选者的任期 |
| leaderCommit | 候选者的 commitIndex |
结果：
| 名称 | 说明 |
|---|---|
| term | currentTerm，供候选者更新自身 |
| voteGranted | 表示候选者获得了该选票 |
| entries[] | 跟随者在 leaderCommit 之后的日志条目 |
接收方实现：
- 若 term < currentTerm，则回复 false。
- 授予选票，并发送 leaderCommit 之后的任何日志条目。
服务器规则
所有服务器：
- 若 commitIndex > lastApplied：递增 lastApplied，并将 log[lastApplied] 应用到状态机。
- 若 RPC 请求或响应中包含的任期 T > currentTerm：令 currentTerm = T，并转为跟随者。
跟随者：
- 响应来自候选者和领导者的 RPC。
- 若在未收到当前领导者的 AppendEntries RPC 且未向任何候选者授予选票的情况下选举超时到期：转为候选者。
候选者：
- 在转为候选者时启动选举：令 currentTerm 递增到满足 $t \bmod n = s$ 的下一个 t $t$，将 commitIndex 之后的任何日志条目复制到 entries[]，并向所有其他服务器发送 RequestVote RPC。
- 将从 RequestVote 响应中收到的任何日志条目添加到 entries[]。
- 若获得了来自多数服务器的选票：通过添加带有 currentTerm 的 entries[] 来更新日志（若同一索引存在多个条目，则使用任期最大的那个），并成为领导者。
领导者：
- 当选后：向每台服务器发送初始的、空的 AppendEntries RPC（心跳）；在空闲期间重复发送，以防止选举超时。
- 若从客户端收到命令：将条目追加到本地日志，在该条目被应用到状态机后响应客户端。
- 若某跟随者的 last log index ≥ nextIndex：以从 nextIndex 开始的日志条目向该跟随者发送 AppendEntries RPC。
- 若成功：更新该跟随者的 nextIndex 和 matchIndex。
- 若因日志不一致导致 AppendEntries 失败：递减 nextIndex 并重试。
- 若存在满足 N > commitIndex 且多数 matchIndex[i] ≥ N 的 N：令 commitIndex = N。
Raft 算法
这是 Raft 论文 [28] 中图 2 的再现。 红色文字为 Raft 所独有。
状态
所有服务器上的持久化状态：
（在响应 RPC 之前在稳定存储上更新）
currentTerm：服务器已知的最新任期（首次启动时初始化为 0，单调递增）votedFor：在当前任期内获得选票的candidateId（若没有则为 null）log[]：日志条目；每条条目包含应用于状态机的命令，以及条目被领导者接收时的任期（首条索引为 1）
所有服务器上的易失状态：
commitIndex：已知被提交的日志条目的最高索引（初始化为 0，单调递增）lastApplied：已应用到状态机的日志条目的最高索引（初始化为 0，单调递增）
领导者上的易失状态：
（选举后重新初始化）
nextIndex[]：对每台服务器，下一条要发送给该服务器的日志条目的索引（初始化为领导者最后一条日志的索引 + 1）matchIndex[]：对每台服务器，已知在该服务器上复制的日志条目的最高索引（初始化为 0，单调递增）
AppendEntries RPC
由领导者调用以复制日志条目；也用作心跳。
参数：
term：领导者的任期prevLogIndex：紧接在新条目之前的日志条目索引prevLogTerm：prevLogIndex条目的任期entries[]：要存储的日志条目（心跳时为空；为提升效率可发送多条）leaderCommit：领导者的commitIndex
结果：
term：当前任期，供领导者更新自身success：若跟随者包含与prevLogIndex和prevLogTerm匹配的条目则为 true
接收方实现：
- 若
term < currentTerm，回复 false - 若日志在
prevLogIndex处不包含任期匹配prevLogTerm的条目，回复 false - 若已存在的条目与新条目冲突（相同索引但任期不同），删除该已有条目及其后所有条目
- 追加日志中尚不存在的任何新条目
- 若
leaderCommit > commitIndex，则令commitIndex = min(leaderCommit, 最后一条新条目的索引)
RequestVote RPC
由候选者调用以收集选票。
参数：
term：候选者的任期candidateId：请求选票的候选者lastLogIndex：候选者最后一条日志条目的索引lastLogTerm：候选者最后一条日志条目的任期
结果：
term：当前任期，供候选者更新自身voteGranted：true 表示候选者获得该选票
接收方实现：
- 若
term < currentTerm，回复 false - 若
votedFor为 null 或为candidateId，且候选者的日志至少与接收方的日志一样新，则授予选票
服务器规则
所有服务器：
- 若
commitIndex > lastApplied：令lastApplied递增，将log[lastApplied]应用于状态机 - 若 RPC 请求或响应中包含的任期 T 大于
currentTerm：令currentTerm = T，并转换为跟随者
跟随者：
- 响应来自候选者和领导者的 RPC
- 若在选举超时时间内未收到来自当前领导者的 AppendEntries RPC，也未向任何候选者授予选票：转换为候选者
候选者：
- 在转换为候选者时开始选举：
currentTerm递增，投自己一票，重置选举计时器，并向所有其他服务器发送 RequestVote RPC - 若获得多数服务器的选票：成为领导者
- 若收到来自新领导者的 AppendEntries RPC：转换为跟随者
- 若选举超时：开始新一轮选举
领导者：
- 当选后：向每台服务器发送初始的空的 AppendEntries RPC（心跳）；在空闲期间重复发送以防止选举超时
- 若收到来自客户端的命令：将条目追加到本地日志，在条目被应用到状态机后作出响应
-
若对某跟随者而言，最后一条日志索引 ≥
nextIndex：发送从nextIndex开始的日志条目的 AppendEntries RPC -
若成功：更新该跟随者的
nextIndex和matchIndex - 若因日志不一致导致 AppendEntries 失败：递减
nextIndex并重试 - 若存在满足 $N > \texttt{commitIndex}$ 且多数
matchIndex[i] ≥ N，且log[N].term == currentTerm的 N：令commitIndex = N