外文翻译- Paxos Made Simple

2020/06/06 分布式

此文翻译的是大名鼎鼎的Leslie Lamport于2001年写的论文《Paxos Made Simple》


摘要

用英语描述Paxos算法是非常简单的。

1.引言

用来实现容错分布式系统的Paxos算法被很多人认为是难以理解的,也许是因为原始讲稿对于大部分读者来说太Greek了。事实上,Paxos算法是最简单并且最容易实现的分布式算法。Paxos算法的核心是共识算法-“synod”算法。下一章节会说明该共识算法基本上满足了我们的需求。最后一个章节会展示完整的Paxos算法,通过直接应用状态机来构建分布式系统—这种方法应该是众所周知的,在分布式系统中被最多引用的文章主题。

2.共识算法

2.1 问题

假设一些进程可以提出value(Paxos协议达成一致的过程:propose value)。共识算法保证了在所有提出的values中,最终只有一个value会被选中。如果没有提出任何value,那么一个都不会被选中。当一个value被选中后,其他进程可以学到所选的value。安全达成共识要求如下:

  • 只能选择提出的value
  • 只有一个value被选中
  • 一个进程只会学习已经被选中的value

我们不会尝试指定具体的要求。但目标是保证某一个提出的value被最终选中,而且如果这个value被选中,其他进程能够学习到这个value.我们把共识算法中的agent分为3类:proposers, acceptors和learners。在实际实现过程中,一个进程会扮演不止一个agent,但具体的agent到进程的映射在这里我们并不关心。

假设agent之间可以通过传输信息交流。我们通常使用异步的非拜占庭模型,其中:

  • Agents以任意速度运行,可能失败停止,可能重启。因为选中一个value后,所有的agents都可能因为失败而重启,所以agents需要能够记住信息,不然无法解决这个问题。
  • 传递的消息可以花费很长时间传递,可能重复,也可能丢失,但不会损坏。

2.2 选择一个Value

最简单的选择一个value的方法是只有一个acceptor agent。Proposer agent发起提案到acceptor,acceptor选择最早收到的一个value。虽然这种方法很简单,但这个解决方案不让人满意,因为acceptor的故障会导致后续所有操作都变成不可能。

因此我们需要尝试另外一个选择value的方法。我们使用多个acceptor agents替代单个acceptor agent。一个proposer发送value到多个acceptor agents。其中一个acceptor也许会接受这个value,当足够多数量的acceptor agents接受这个value后,这个value才被最终选定。为了保证只有一个value被选中,我们让多数的agents为超过半数的agents。因为任意2个多数的agents都会有一个公共的agent,当一个agent只选中一个value时,这个方法可行。

在没有故障或者消息丢失的情况下,我们想要只有一个value被选中,即使只有一个value被一个proposer提出。需要满足以下需求:

P1. 一个acceptor必须接受收到的第一个提案

但这个要求会产生其他问题。不同的proposers可能会同时提出不同的values,导致每个acceptor都接受了一个value,但没有一个Value是被多数接受的。即使只有2个提案的values,如果他们各自被一半的acceptors接受,那么任意一个acceptor的故障都会让我们无法学习到被选中的value。

P1和value只有被多数acceptor接受才算选中,暗示我们的acceptor必须允许接受多于一个提案。我们给每个提案一个提案号,因此每个提案由一个提案号和value组成。为了防止冲突,我们要求不同的提案拥有不同的提案号。我们仅仅在假设实现,具体实现可能有所不同。一个value被选中,当一个提案被多数acceptors接受。在这种情况下,我们说这个提案被选中。

我们允许选中多个提案,但必须保证所有选中的提案必须有一样的value。通过归纳提案号,可以保证:

P2. 如果一个value为v的提案被选中,那么被选中的提案号更高的提案也有value v。

因为提案号是有序的,条件P2保证了只有单一value被选中的特性。

为了被选中,一个提案必须被至少一个acceptor接受,所以我们可以通过满足以下条件满足P2:

P2a 如果一个value为v的提案被选中,那么被任意一个acceptor选中的具有更高提案号的提案都有value v。

我们仍然需要满足P1来保证提案被选中。因为消息传递是异步的,一个提案可能被一些没有接受过任意提案的acceptor c选中。假设一个proposer 恢复正常,并发送了一个带有不同value的具有更高提案号的提案

P1要求acceptor c接受这个提案,但这却违背了P2a。为了同时维持P1和P2a,我们需要加强P2a:

P2b. 如果一个value为v的提案被选中,那么每个proposer发出的具有更高提案号的提案必须拥有value v。

因为一个提案由proposer发出,因此满足P2b也就满足了P2a,也就满足了P2.

为了明白如何满足P2b,我们先对此进行证明。假设一个value为v,提案号为m的提案已经被选中,那么任何提案号n>m的提案也有value v。我们可以使用归纳法,归纳到n。假设提案号从m..n-1的提案都有value v,那么必然有大多数acceptor接受了这些提案,这些acceptor都接受了提案号在m..n-1,并拥有value v的提案。

因此我们可以通过满足一下条件来确保提案号为n的提案拥有value v:

P2c. 对任意的v和n,如果一个提案号为n并且value为v的提案被发出,那么存在一个由多数acceptor组成的集合S。那么S中没有acceptor接受过提案号小于n的提案,要么v是S中acceptor接受过的提案号小于n的最大提案的value。

因此我们可以通过满足P2c来实现P2b.

为了P2c的不变性,如果proposer想要发布一个提案号为n的提案,那么这个proposer必须获得提案号小于n中最大的提案,如果有这样的提案被多数选中了。学习已经被选中的提案是非常简单的,预测未来的接受情况是困难的。为了不用预测未来,proposer发出承诺不会有这样的案例。换而言之,proposer要求acceptors不接受任何提案号小于n的提案。这就导出了如下用于发布提案的算法:

1.一个proposer选择一个提案号n,并发送请求到大部分acceptors,要求它们回复:

(a) 承诺不再接收提案号小于n的提案

(b) 如果已经接收过了提案,返回小于n的最大提案号的提案。

我称这样的请求为提案号为n的prepare request。

2.如果proposer收到大部分acceptors的回复,那么它可以发送提案号为n,value为v—其中v要么是返回的提案号最高的提案的value,要么是proposer选中的value。

Proposer将提案发送给一些acceptors,并请求acceptors接收(这些acceptors并不一定和初始的acceptors是一样的)。我们称这样的请求为accept request。

这里描述的是proposer 的算法,那么acceptor呢?acceptor可以接收从proposers发出的2种请求:prepare requests 和 accept requests。Acceptor可以忽略任何请求而不影响安全性。所以,我们只讨论acceptor可以回复请求的情况。Acceptor永远可以回复prepare request。有时可以回复accept request,这代表接受提案,除非它没有承诺不这么做。换而言之:

P1a. 一个acceptor可以接受提案号为n的提案,如果它之前没有回复过提案号大于n的prepare request。

可以发现P1a包含P1。

现在我们有一个完整的算法来选择一个满足如下条件的value—假设提案号唯一。最终的算法是改算法的优化版本。

假设一个acceptor收到一个提案号为n的提案,但它已经回复了提案号大于n的提案的prepare request,那么它不会接受任何提案号为n的提案。Acceptor不会回复这个prepare request,因为它肯定不会接受这个提案。因此我们让acceptor忽视类似的请求。同样我们也让它忽视已经接受过的提案的prepare request。

通过这样的优化,一个acceptor需要记住它接受的提案的最高提案号以及它回复过的最高提案号的prepare request。

因为P2c要求即使发生故障,一个acceptor必须记住这些信息,即使发生了故障或者重启。需要注意的是proposer可以随时抛弃自己的提案—只要它不发生具有相同提案号的提案。

将proposer 和acceptor的行为放在一起,我们可以看到算法的执行分为2个阶段。

Phase 1. (a) 一个proposer选择一个提案号n,并向大部分acceptors发送提案号为n的prepare request

(b) 如果acceptor收到一个prepare request,并且提案号n大于任何它已经回复的prepare request的提案号,那么这个acceptor回复这个请求,并保证不再接收提案号小于n的提案。

Phase 2. (a) 如果proposer收到了大部分的acceptors 对prepare requests的回复,随后它将发送accept request到这些acceptors,带上提案号n和value v,其中v是收到的回复中提案号最大的提案的value,如果没有收到提案,这个value是自己选定的任意值。

(b) 如果 acceptor收到accept request,其中的提案号为n,并且它并没有回复过提案号大于n的提案,那么它应该接受这个提案。

一个 proposer 可以生成多个提案,只要它能满足算法的要求。Proposer可以随时在协议过程中抛弃提案。当其他proposer发出提案号更高的提案后,比较明智的做法是放弃当前提案。因此,如果一个acceptor忽视prepare request 或者accept request,因为它已经接受了提案号更高的提案,它应该通知对应的proposer放弃该提案。这是针对性能优化,并不影响正确性。

2.3 学习选择的Value

为了学习已经被选中的value,learner必须先确定一个被大多数acceptor接受的提案。

一个显而易见的算法是每个acceptor接受一个提案后,向所有的learner发送这个提案。这样允许learner尽快发现被选中的value,但这样要求每个acceptor对所有的learner都进行回复-相当于回复acceptor数量与learner数量的乘积。非拜占庭式的失败假设允许一个learner从另一个learner那里学到已经被接受的value。

我们可以让acceptors把自己的接受情况发给一个主learner,让其他learner从主learner中学习哪些value被选中。这个方法需要所有的learner进行额外的一轮学习。同时这个方法也是不可靠的,因为主learner可能会发生故障。需要发生的回复数跟之前的一样多。

更一般些,acceptors可以发送接收情况给一个主learners的集合,其中任意一个都能够在value被选中时通知所有的learners。随着集合的变大,在通信的过程中拥有更高的可靠性。

因为存在消息丢失的情况,learner可能不知道一个value已经被选中。Learner可以直接询问acceptors接受了哪个提案,但acceptors的故障可能让我们无法知道一个提案是否被多数acceptors接受。在这种情况下,learner只有在新的提案被接受后才能知道value的值。如果一个learner想要知道哪个value被确认了,可以让proposer发起新的提案。

2.4 进展

很容易构建这样的场景:两个proposers持续发送比对方提案号高的提案,最终所有提案都没有被接受。Proposer p使用提案号n1完成阶段1,另一个proposer q使用提案号n2>n1完成阶段1. Proposer p在阶段2的accept request会被拒绝,因为acceptor承诺不再接受提案号小于n2的提案。所以Proposer p重新使用新的提案号n3>n2完成阶段1,导致proposer q的阶段2被终止。

为了流程的顺利进行,我们必须选出一个主proposer,只有它才能发送提案。如果主proposer可以跟大部分acceptors通信,然后选出一个最大的提案号,就能成功发送提案并被接收。通过放弃现存的提案,使用更高的提案号,主proposer会最终选择一个足够大的提案号。

如果系统足够多的部分可以正常运行,那么选举单一的主proposer就可以使系统正常运行。Fischer, Lynch, and Patterson有个注明的结论:实现一个选举proposer的可靠算法必须使用随机或者实时性-例如,超时。然而,无论选举是否成功,安全性都足以保证。

2.5 实现

Paxos算法假设一个进程网络。在共识算法中,每个进程扮演角色:proposer, acceptor和 learner。算法会选择一个leader担任主proposer和主learner。Paxos 共识算法如上面所述,请求和回复都是普通信息。我们需要持久性的存储来保证故障时acceptor能记住信息。Acceptor会在发送回复前记下信息。

接下来的内容是描述如何确保机器不会产生相同的提案号-对于不同的提案。不同的proposers会根据自己的集合选择不同的数字,所以不同的proposers永远不会产生相同的提案号。每个proposers会记住自己提过的最大的提案号,然后在阶段1时选择一个更大的提案号。

3.实现状态机

实现分布式系统最简单的方法是让clients向一个中央主服务器发送请求。主服务器可以被看作一个以一定顺序执行client命令的的确定性状态机。状态机拥有现在的状态,并根据输入产生输出,并移动到下一个状态。比如说分布式银行系统的客户端可能是柜员,并且状态机由所有用户的账户余额组成。取钱的操作通过执行状态机命令:当且仅当余额大于取的钱时,减少余额,输出新旧余额。

一种实现方法是使用单一的中央主服务器,如果主服务器发生故障,所有服务失败。因此,我们采用servers的集合,每个服务器单独实现自己的状态机。因为状态机是确定的,所以在执行完相同顺序的命令后,会产生相同的输出的状态结果。Client可以使用任何一个服务器返回的结果。

为了保证所有的服务器都执行同样顺序的状态机命令,我们事先一个序列的Paxos共识算法,第i 个实例选择的value作为第i个状态机的状态。每个server实例都运行所有role: proposer, acceptor和 learner。现在我们假设servers的集合是固定的,此共识算法的所有实例都是用同样的agents。

在平时的操作中,一个server被选举成为leader,并成为唯一的主proposer,在所有的共识算法实例中。客户端发送命令给leader,leader觉得这个命令应该放在序列中的什么位置。假设leader决定这个命令应该成为第135个命令,那么它会尝试把该命令变成第135个实例选择的value。这通常都会成功。但有可能失败,当发生故障时,或者另一个server以为自己是leader,然后对第135个实例进行另外的操作。但共识算法保证了只会有一个第135条命令。

Paxos共识算法的关键在于value的值在阶段2时才被确认。回想一下,在阶段1完成后,要么value的值已经被决定了,要么value的值可以自己随便选。

我现在要描述的是在正常运行时,Paxos的状态机如何运行。以及什么情况下会出现问题。比如说旧的leader刚刚发生故障,新的leader还没选出。

新的leader,也就是共识算法中的learner,应该知道大多数已经被选中的value。假设它知道命令1-134,138,139(接下来我们会知道空隙是如何产生的)。然后它执行实例135-137的阶段1,和所有大于129的实例。假设执行结果确定了实例135和140的value,但其他实例仍然未知。然后leader对实例135和140执行阶段2,从而选中了135和140的命令。

Leader和其他获得了leader知道的命令的服务器可以执行命令1-135.但仍然不能执行命令1138-140,因为命令136和137仍未被选中。Leader可以将接下来的2个命令填充到命令136和137中。但我们选择填充空指令到136和137中,这样状态机的状态不会改变。当空指令被选中后,命令138-140可以立即执行。

命令1-140都被选中。Leader完成了对于所有大于140的实例的阶段1,现在可以在阶段2中选择任意的value。然后分配命令号131给客户端发出的请求,并把值作为命令的值。随后把客户端的下一个请求作为命令142,如此以往。

Leader可以提出命令142在学习到命令141的value之前。可能命令141的数据发生丢失,命令142在其他服务器学习到命令141前被选中。当leader没有收到实例141的阶段2的回复后,它会重复发送消息。如果运行正常,发送的信息会被选中。但也有可能在一开始失败,留下一个空白的间隙。通常来说,假设leader可以提前获得a个命令—即在1-i已经被选中的情况下,提出i+1-i+a个命令。一个最多为a-1的空隙是有可能出现的。

一个新的leader可以执行无限多实例的阶段1-在上述场景中,实例135-137以及大于139的实例。对所有实例使用同一个提案号,这样一次消息传递即可完成。在阶段1中,如果acceptor收到阶段2的消息,那么acceptor会回复不仅仅是一个简单的OK。因此,server作为acceptor可以用一个简单的消息回复所有的实例。在无数个实例的阶段1中,这是没有问题的。

因为leader的故障和新leader的选举都是小概率事件,因此执行状态机有效花费—即,在命令/value上达成共识的开销—也就是阶段2的执行。可以看出Paxos共识算法在阶段2的过程中具有所有能达成共识的允许故障的算法中的最小开销。因此Paxos算法本质上是最优的。

对于系统正常运行的假设是单一leader,除了旧leader发生故障以及新leader选举的过程中。在异常情况下,leader的选举可能失败。如果没有服务器当leader,那么新的命令自然不能被执行。如果多个服务器任务它们是leader,那么它们可以在共识算法的同一实例中推出不同value,这会导致没有value被选中。但安全性是保留的—2个不同的服务器不会在第i个状态机命令上达成一致。选举单一leader只是为了确保流程顺利。

如果server的集合可以改变,那么必须有一种方法确定哪些服务器确定了共识算法中的哪些实例。最简单的方法是通过状态机本身。当前的server的集合可以作为状态的一部分,并被普通的状态机命令改变。我们允许leader提前获得a个命令,然后执行i+a的实例,在执行完第i个实例的情况下。这就是一种简单的实现对复杂的重新配置的算法。

4.参考文献

[1] Michael J. Fischer, Nancy Lynch, and Michael S. Paterson. Impossibility of distributed consensus with one faulty process. Journal of the ACM, 32(2):374–382, April 1985.
[2] Idit Keidar and Sergio Rajsbaum. On the cost of fault-tolerant consensus when there are no faults—a tutorial. TechnicalReport MIT-LCS-TR-821, Laboratory for Computer Science, Massachusetts Institute Technology, Cambridge, MA, 02139, May 2001. also published in SIGACT News 32(2) (June 2001).
[3] Leslie Lamport. The implementation of reliable distributed multiprocess systems. Computer Networks, 2:95–114, 1978.
[4] Leslie Lamport. Time, clocks, and the ordering of events in a distributed system. Communications of the ACM, 21(7):558–565, July 1978. [5] Leslie Lamport. The part-time parliament. ACM Transactions on Com- puter Systems, 16(2):133–169, May 1998.