【转】Paxos算法

作者: wiflish 分类: 算法 发布时间: 2014-06-09 21:27 ė 6没有评论

转自: http://zhan.renren.com/devops?gid=3602888497996645068&from=template&checked=true

Paxos算法是一种基于消息传递且具有高度容错特性的一致性算法,由莱斯利·兰伯特(Leslie Lamport,此人现在在微软研究院)于1990年提出。

1 问题的提出

设想一组可以提出决议(value)的process。一致性算法保证所有提出的决议中,有一个决议会被选择(chosen)。如果没有提出决议,那么将不会有选择。如果一个决议被选择,那么process最终都能知道这个被选择的决议。一致性的安全性包括:
——决议只有被提出后才可能被选择,
——只有一个决议被选择,并且
——process永远不会获知一个决议被选择了,除非这个决议确实已经被选择。
我们将不会特别明确精确的时间性要求。然而,其目标是最终有一个提出的决议被选择,并且process最终会获知被选择的决议,如果有的话。
我们为一致性算法划分3个角色,并分别以代理:proposer(提出者),acceptor(批准者)和listener(接收者)表示。实现中,允许一个process扮演多个代理,这里我们不关心从代理到process的映射。
假设代理之间用消息通信。我们采用异步、非拜占庭模型【拜占庭模型(Byzantine model),消息可能丢失、重复或者内容损坏。换而言之,非拜占庭模型就是允许消息的丢失或者重复,但是不会出现内容损坏的情况】:
——代理以任意的速度操作,可能会因为停机而失效,可能会重启。因为任一个代理都可能会在决议被选择后停机再重启,因此解决方案要求代理必须能够记忆某些信息,从而能在重启后重新载入。
——消息传送速度不可预测,可能会重复或丢失,但是内容不会损坏。

2 选择决议

最简单的方法就是用单个acceptor代理。Proposer发送议案(proposal)给这个acceptor,它选择最先收到的议案。尽管简单,但是如果acceptor停机了,那么系统就不能继续运行了,这个方案并不能满足要求。【明显的单点问题】
看来我们需要选择另外的方法,我们用多个acceptor代理,而非一个,proposer向一组acceptor提出议案。一个acceptor可能批准该议案,当有足够大的acceptor集合批准了这个议案时,决议【议案是一个{编号,决议}对】就被选择了。那么这个集合多大才足够呢?为了保证只有一个决议被选择,我们可以让这个集合包含多数的代理【后面也会称之为多数派】。因为任意两个多数派至少有一个相同的代理,如果一个acceptor最多只能批准一个决议,这就是可行的。
假设没有失败或者消息丢失,即使仅有一个proposer提出了一个决议,我们也希望能选择一个决议。这就导出了下面的需求:
P1. Acceptor必须批准它接收到的第一个决议。
但是该需求会导致一个问题。同时可能有几个proposer提出了几个不同的决议,从而导致每个acceptor都批准了一个决议,但是没有一个决议被多数派批准。即使只有两个决议,如果每个都被半数的acceptor批准,单个的acceptor失效也会导致不可能知道到底哪个决议被选择了。
一个决议要经过多数派的批准才能被选择,这个需求和P1暗示了acceptor必须能够批准多个议案。我们为每个议案分配一个编号来记录不同的议案,因此一个议案由编号和决议构成【也就是议案={编号,决议}】。为避免混淆,我们要求议案的编号是唯一的。这个取决于实现,我们假设可以做到这一点。如果一个议案{n, v}通过多数派的批准,那么决议v就被选择了。这种情况下,我们称议案(包括其决议v)被选择了。
我们允许选择多个议案,但是必须保证所有选择的议案包括相同的决议。对议案编号归纳,可以保证:
P2. 如果一个议案{n, v}被选择,那么所有被选择的议案(编号更高)包含的决议都是v。
因为编号是全序的,P2保证了“只有一个决议被选择”这一关键安全属性。议案必须至少被一个acceptor批准才可能被选择。因此只要满足下面的条件,就可以满足P2:
P2A. 如果一个议案{n, v}被选择,那么任何acceptor批准的议案(编号更高)包含的决议都是v。
我们依然保证P1来确认选择了某些议案。因为通信是异步的,在特殊情况下,某些acceptor c没有接收到过任何议案,它们可能会【错误的】批准一个议案。设想一个新的proposer“醒来”并提出了一个更高编号的议案(包含不同的决议)。根据P1的要求,c应该批准这个议案,但是这违反了P2A。为了同时保证P1和P2A,我们需要增强P2A:
P2B. 如果一个议案{n, v}被选择,那么此后,任何proposer提出的议案(编号更高)包含的决议都是v。
因为一个议案必须在被proposer提出后才能被acceptor批准,因此P2B包含了P2A,进而包含了P2。
如何才能满足P2B呢,让我们来考虑如何证明它是成立的。我们假设某个议案{m, v}被选择,然后证明任何编号n>m的议案的决议都是v。对n归纳可以简化证明,根据条件:每个提出的议案(编号从m到n-1)的决议都是v,我们可以证明编号为n的议案的决议是v。对于选择的议案(编号为m),必定存在一个集合C(acceptor的多数派),C中的每个acceptor都批准了该议案。结合归纳假设,m被选择这一前提意味着:
C中的每个acceptor都批准了一个编号在m到n-1范围内的议案,并且议案的决议为v。
因为任何由多数派组成的集合S都至少包含C中的一个成员,我们可以得出结论:如果下面的不变性成立,那么编号为n的议案的决议就是v:
P2C. 对于任意的v和n,如果议案{n, v}被提出,那么存在一个由acceptor的多数派组成的集合S,或者a) S中没有acceptor批准过编号小于n的议案,或者b) 在S的任何acceptor批准的所有议案(编号小于n)中,v是编号最大的议案的决议。
通过保持P2C,我们就能满足P2B。
为了保持不变性P2C,准备提出议案(编号为n)的proposer必须知道所有编号小于n的议案中编号最大的那个,如果存在的话,它已经或将要被acceptor的某个多数派批准。获取已经批准的议案是简单的,但是预知将来可能批准的议案是困难的。Proposer并不做预测,而是假定不会有这样的情况。也就是说,proposer要求acceptor不能批准任何编号小于n的议案。这引出了下面提出议案的算法【这就是两阶段提交了】。
1 proposer选择一个新编号n,向某个acceptor集合中的所有成员发送请求,【prepare请求阶段,n是prepare请求的编号,也是下面accept请求的议案编号】并要求回应:
a) 一个永不批准编号小于n的议案的承诺,以及
b) 在它已经批准的所有编号小于n的议案中,编号最大的议案,如果存在的话。
我把这样的请求称为prepare请求n。
2 如果proposer收到了多数acceptor的回应,那么它就可以提出议案{n, v},其中v是所有回应中编号最高的议案的决议,或者是proposer选择的任意值,如果acceptor们回应说还没有批准过议案。
一个proposer向一个acceptor集合发送已经被批准的议案(不一定是回应proposer初始请求的acceptor集合),我们称之为accept请求。
我们已经描述了proposer的算法。那么acceptor呢?它可以接收两种来自proposer的请求: prepare请求和accept请求。Acceptor可以忽略任何请求,而不用担心安全性。因此,我们只需要描述它需要回应请求的情况。任何时候它都可以回应prepare请求【本文中,回应就意味着接受了这个prepare请求和编号n】,它可以回应accept请求,并批准议案,当且仅当它没有承诺过【承诺批准或批准一个更高编号的议案】。换句话讲:
P1A. acceptor可以批准一个编号为n的议案,当且仅当它没有回应过一个编号大于n的prepare请求。
P1A蕴含了P1。
现在我们得到了一个完整的决议选择算法,并满足我们要求的安全属性——假设议案编号唯一。通过一些简单优化就能得到最终算法。
假设一个acceptor接收到一个编号为n的prepare请求,但是它已经回应了一个编号大于n的prepare请求。于是acceptor就没有必要回应这个prepare请求了,因为它不会批准这个编号为n的议案。它还可以忽略已经批准过的议案的prepare请求。
有了这些优化,acceptor只需要保存它已经批准的最高编号的议案(包括编号和决议),以及它已经回应的所有prepare请求的最高编号。因为任何情况下,都需要保证P2C,acceptor必须记住这些信息,包括失效并重启之后。注意,proposer可以随意的抛弃一个议案——只要它永远不会使用相同的编号来提出另一个议案。
结合proposer和acceptor的行为,我们将把算法可以分为两个阶段来执行。
阶段1. 
a) Proposer选择一个议案编号n,向acceptor的多数派发送编号也为n的prepare请求。
b) Acceptor:如果接收到的prepare请求的编号n大于它已经回应的任何prepare请求,它就回应已经批准的编号最高的议案(如果有的话),并承诺不再回应任何编号小于n的议案;
阶段2.
a) Proposer:如果收到了多数acceptor对prepare请求(编号为n)的回应,它就向这些acceptor发送议案{n, v}的accept请求,其中v是所有回应中编号最高的议案的决议,或者是proposer选择的值,如果回应说还没有议案。
b) Acceptor:如果收到了议案{n, v}的accept请求,它就批准该议案,除非它已经回应了一个编号大于n的议案。
Proposer可以提出多个议案,只要它遵循上面的算法。它可以在任何时刻放弃一个议案。(这不会破坏正确性,即使在议案被放弃后,议案的请求或者回应消息才到达目标)如果其它的proposer已经开始提出更高编号的议案,那么最好能放弃当前的议案。因此,如果acceptor忽略一个prepare或者accept请求(因为已经收到了更高编号的prepare请求),它应该告知proposer放弃议案。这是一个性能优化,而不影响正确性。

3 获知选择的决议
Learner必须找到一个被多数acceptor批准的议案,才能知道一个决议被选择了。一个显而易见的算法就是,让每个acceptor在批准议案时通知所有的learner。于是learner可以尽快知道选择的决议,但是要求每个acceptor通知每个learner——需要的消息个数等于learner数和acceptor数的乘积。
基于非拜占庭假设,一个learner可以从另一个learner得知被选择的决议。我们可以让acceptor将批准情况回应给一个主Learner,它再把被选择的决议通知给其它的learner。这增加了一次额外的消息传递,也不可靠,因为主learner可能会失效,但是要求的消息个数仅是learner数和acceptor数的总和。
更一般的,可以有多个主Learner,每个都能通知其它所有的acceptor。主learner越多越可靠,但是通信代价会增加【消息个数越多】。
由于消息丢失,可能没有learner知道选择了一个决议。Learner可以向acceptor询问批准的议案,但是由于acceptor的失效,可能难以得知多数派是否批准了一个议案。这样,learner只能在新的议案被选择时才能知道acceptor选择的决议。如果learner需要知道是否已经选择了一个决议,它可以让proposer根据上面的算法提出一个议案【提出请求就有回应,并且新的提案的决议就是当前选择的决议】。

4处理流程

很容易构造这样一个场景,两个proposer轮流提出一系列编号递增的议案,但是都没有被选择。Propoer p选择议案的编号为n1,并结束阶段1。接着,另外一个proposer q选择了议案编号n2>n1,并结束阶段1。于是p在阶段2的accept请求将被忽略,因为acceptor已经承诺不再批准编号小于n2的议案。于是p再回到阶段1并选择了编号n3 > n2,这又导致q第二阶段的accept请求被忽略,…
为了保证流程,必须选择一个主proposer,只有主proposer才能提出议案。如果主proposer和多数acceptor成功通信,并提出一个编号更高的议案,议案将被批准。如果它得知已经有编号更高的议案,它将放弃当前的议案,并最终能选择一个足够大的编号。
如果系统中有足够的组件(proposer,acceptor和网络)能正常工作,通过选择一个主proposer,系统就能保持响应。Fischer、Lynch和Patterson的著名结论[1]表明:选择proposer的可靠算法必须是随机的或者实时的——例如,使用超时机制。然而不管选择成功与否,安全性都能得到保证。

5 实现

Paxos算法[5]假设了一组网络进程。在其一致性算法中,每个process都同时扮演proposer、acceptor和learner的角色。算法选择一个leader,它就是主proposer和主learner。Paxos一致性算法就是上面描述的那个,请求和响应都用消息发送(响应会被打上对应议案的编号,以防止混淆)。使用持久化存储来保证acceptor失效后也能记起必要的信息。Acceptor在发送响应前必须持久化存储该响应。
接下来就是描述保证任何两个议案的编号都不相同的机制。proposer从互不相交的集合中选择议案编号,因此两个不同的proposer永远不会提出相同编号的议案。【假设有5个proposer,编号为0~4,可以使proposer i的议案编号选择序列为:5*j + i(j >= 0),就能保证永不重复,且递增】每个proposer都持久化保存它已经提出的编号最高的议案,并使用一个更高的议案编号来开始阶段1。

参考文献

[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 Computer Systems, 16(2):133–169, May 1998.

本文出自 Wiflish's Blog,转载时请注明出处及相应链接。

本文永久链接: http://wiflish.fyard.com/archives/243

发表评论

电子邮件地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Ɣ回顶部