paxos算法是为了解决在分布式系统中,多个process有关某一个值达成一致决议的算法,即一种一致性算法(Consensus Algorithm)。Google的分布式锁Chubby和Yahoo的Zookeeper的实现中都采用了此算法思想,Lamport(此人的牛逼程度可以参看他发表的文章和被引用的次数)在《paxos made simple》的第二页给出的abstract就一句话:“The Paxos algorithm, when presented in plain English, is very simple.”,有关paxos发布的背后的事情还挺有趣的,paxos从提出到发布用了9年,<The Part-Time Parliament>,Lamport虚拟了一个希腊的城邦paxos,用该城邦的人如何就一条法令达到一致来描述了整个算法,但计算机界的N多人都不悲剧幽默感,Lamport就在2001年写了一篇相对简短的《paxox made simple》,估计也就是这句abstract的来由

paxos算法将分布式系统的process划分为三种角色,分别为proposer, acceptor以及learner,其中只有proposer和acceptor参加决议过程,learner只是了解决议被批准以后系统具体选择的决议值,整个算法采用基于消息的传递模型,假设整个系统是消息异步,并且没有拜占庭失效问题(non-Byzantine model),就是整个系统中的消息可以延迟到达,可以重复发送甚至可以丢失,但不能被篡改,允许系统中的节点失效和重启,但需要这些节点在失效到重启之间具有永久性存储介质用以记录信息。

整个paxos算法的过程是一个两段式提交,由proposer提出决议(value),acceptor接受并选择决议,用一个{n,v}来对传递的消息进行描述,n表示一个严格递增不重复的编号,有关这个编号的实现在paxos made simple中提到的是让所有的proposer都从不相交的数据集合中进行选择,例如系统有5个proposer,则可以为每一个proposer分配一个标识j(0~4),则每一个proposer每次提出决议的编号可以为5*i + j(i可以用来表示round),v表示value。

Phase 1a: proposer提出一个决议并选择一个编号N,发送message prepare(N)给大多数(Majority)的Acceptor。

Phase 1b: acceptor接受到prepare(N)的消息后,如果不违法自己给其他proposer的承诺,即没有收到过比N编号更高的prepare请求,则返回给proposer消息{n,v},n是自己上次批准的请求编号,v是自己上次accept的value。并承诺自己不再接受任何小于N的编号的prepare请求。如果acceptor之前已经收到过其他高于N的编号的prepare请求,则忽略prepare(N),也可以给一个deny反馈(出于效率考虑,不反馈不影响正确性)。

Phase 2a: proposer收到多数的acceptor的确认反馈后,即可以进入批准阶段,proposer选择一个value(V)(V所有acceptor回馈的消息中,编号最大的value),或者当任何acceptor都没有value反馈时,proposer可以自己任意选择value值,发送Accept(N,V)给所有的acceptor。

Phase 2b: 当acceptor接受到一个accept(N,V)的请求时,acceptor就批准这个请求,除非该acceptor之前收到了一个比编号N更高的prepare请求。

整个算法的执行过程中,proposer可以任何时间随意的抛弃一个proposal,不影响正确性。算法的执行图解如下(from wikipedia)

 Client   Proposer      Acceptor     Learner
   |         |          |  |  |       |  |
   X-------->|          |  |  |       |  |  Request
   |         X--------->|->|->|       |  |  Prepare(N)
   |         |<---------X--X--X       |  |  Promise(N,{Va,Vb,Vc})
   |         X--------->|->|->|       |  |  Accept!(N,Vn)
   |         |<---------X--X--X------>|->|  Accepted(N,Vn)
   |<---------------------------------X--X  Response
   |         |          |  |  |       |  |

Learner需要了解被选择了的value,从上图可以看出在Phase 2b阶段时,当acceptor接受了一个决议后,会给Learner发送消息通知learner,为了尽快的使得Learner了解到被选择的value,可以每一个Acceptor都发送消息给每一个Learner,这样会产生大量的消息,是Acceptor个数和Learner的乘积。另外一种是由于系统中没有拜占庭失效,可以采用一个主Learner接受Acceptor发送的决议并且通知其他的Learner,这样减少了消息总量但会引起单点失效和多一级的传递。因此可以在实践中做一个权衡,选一个主learner集合来对learner进行通知。

由于有可能存在活锁的情况,即两个proposer轮流的用更高的编号提出新的prepare请求,使得没有任何一方的决议能成功的被批准。因此会选择一个主proposer,只有该proposer才能提出决议,如果主proposer提出一个决议遇到了deny,即存在另外一个更高的编号决议,则直接选择一个足够大的编号进行提议。主proposer,即leader包括主learn的选择一般也采用paxos算法,zookeeper中leader的选择就采用了fast paxos算法。

虽然Lamport说paxos算法非常simple,然后文章也很简短,但跟所有学习者的感觉一样,远没有大师的智慧,不会觉得他特别simple,看了几天也还只了解大概,特别是在看到相关引申的各种文章后。有关paxos算法在实现角度的描述以及实现可以参考Lamport在2005年写的<Fast Paxos>,以及他人写的<Paxos Made Live – An Engineering Perspective>,和<Paxos在大型系统中常见的应用场景>。

Reference:

[1] http://en.wikipedia.org/wiki/Paxos_algorithm (对整个paxos系列描述的相当详细)

[2] http://zh.wikipedia.org/wiki/Paxos算法 (paxos made simple的简单译文)

[3] Paxos Made Simple

[4] Paxos Made Live – An Engineering Perspective