分布式一致性算法Paxos详解

Paxos分析

最近研究paxos算法，看了许多相关的文章，概念还是很模糊，觉得还是没有掌握paxos算法的精髓，所以花了3天时间分析了libpaxos3的所有代码，此代码可以从https://bitbucket.org/sciascid/libpaxos 下载。对paxos算法有初步了解之后，再看此文的效果会更好；如果你也想分析libpaxos3的话，此文应该会对你有不小帮助；关于paxos的历史这里不多做介绍，关于描述paxos算法写的最好的一篇文章应该就是维基百科了，地址戳这里：http://zh.wikipedia.org/zh-cn/Paxos%E7%AE%97%E6%B3%95

在paxos算法中，分为4种角色：

  Proposer ：提议者

  Acceptor：决策者

  Client：产生议题者

  Learner：最终决策学习者

上面4种角色中，提议者和决策者是很重要的，其他的2个角色在整个算法中应该算做打酱油的，Proposer就像Client的使者，由Proposer使者拿着Client的议题去向Acceptor提议，让Acceptor来决策。这里上面出现了个新名词：最终决策。现在来系统的介绍一下paxos算法中所有的行为：

1. Proposer提出议题
2. Acceptor初步接受 或者 Acceptor初步不接受
3. 如果上一步Acceptor初步接受则Proposer再次向Acceptor确认是否最终接受
4. Acceptor 最终接受 或者Acceptor 最终不接受

上面Learner最终学习的目标是Acceptor们最终接受了什么议题？注意，这里是向所有Acceptor学习，如果有多数派个Acceptor最终接受了某提议，那就得到了最终的结果，算法的目的就达到了。画一幅图来更加直观：

为什么需要3个Acceptor？因为Acceptor必须是最少大于等于3个，并且必须是奇数个，因为要形成多数派嘛，如果是偶数个，比如4个，2个接受2个不接受，各执己见，没法搞下去了。

为什么是3个Proposer？ 其实无所谓是多少个了，1~n 都可以的；如果是1个proposer，毫无竞争压力，很顺利的完成2阶段提交，Acceptor们最终批准了事。如果是多个proposer就比较复杂了，请继续看。

上面的图中是画了很多节点的，每个节点需要一台机器么？答案是不需要的，上面的图是逻辑图，物理中，可以将Acceptor和Proposer以及Client放到一台机器上，只是使用了不同的端口号罢了，Acceptor们启动不同端口的TCP监听，Proposer来主动连接即可；完全可以将Client、Proposer、Acceptor、Learner合并到一个程序里面；这里举一个例子：比如开发一个JOB程序，JOB程序部署在多台服务器上(数量为奇数)，这些JOB有可能同时处理一项任务，现在使用paxos算法让这些JOB自己来商量由谁(哪台机器)来处理这项任务，这样JOB程序里就需要包含Client、Proposer、Acceptor、Learner这4大功能，并且需要配置其他JOB服务器的IP地址。

再举一个例子，zookeeper常常用来做分布式事务锁。Zookeeper所使用的zad协议也是类似paxos协议的。所有分布式自协商一致性算法都是paxos算法的简化或者变种。Client是使用zookeeper服务的机器，Zookeeper自身包含了Acceptor, Proposer, Learner。Zookeeper领导选举就是paxos过程，还有Client对Zookeeper写Znode时，也是要进行Paxos过程的，因为不同Client可能连接不同的Zookeeper服务器来写Znode，到底哪个Client才能写成功？需要依靠Zookeeper的paxos保证一致性，写成功Znode的Client自然就是被最终接受了，Znode包含了写入Client的IP与端口，其他的Client也可以读取到这个Znode来进行Learner。也就是说在Zookeeper自身包含了Learner(因为Zookeeper为了保证自身的一致性而会进行领导选举，所以需要有Learner的内部机制，多个Zookeeper服务器之间需要知道现在谁是领导了)，Client端也可以Learner，Learner是广义的。

现在通过一则故事来学习paxos的算法的流程(2阶段提交)，有2个Client(老板，老板之间是竞争关系)和3个Acceptor(政府官员)：

1. 现在需要对一项议题来进行paxos过程，议题是“A项目我要中标！”，这里的“我”指每个带着他的秘书Proposer的Client老板。
2. Proposer当然听老板的话了，赶紧带着议题和现金去找Acceptor政府官员。
3. 作为政府官员，当然想谁给的钱多就把项目给谁。
4. Proposer-1小姐带着现金同时找到了Acceptor-1~Acceptor-3官员，1与2号官员分别收取了10比特币，找到第3号官员时，没想到遭到了3号官员的鄙视，3号官员告诉她，Proposer-2给了11比特币。不过没关系，Proposer-1已经得到了1,2两个官员的认可，形成了多数派(如果没有形成多数派，Proposer-1会去银行提款在来找官员们给每人20比特币，这个过程一直重复每次+10比特币，直到多数派的形成)，满意的找老板复命去了，但是此时Proposer-2保镖找到了1,2号官员，分别给了他们11比特币，1,2号官员的态度立刻转变，都说Proposer-2的老板懂事，这下子Proposer-2放心了，搞定了3个官员，找老板复命去了，当然这个过程是第一阶段提交，只是官员们初步接受贿赂而已。故事中的比特币是编号，议题是value。

　　　　这个过程保证了在某一时刻，某一个proposer的议题会形成一个多数派进行初步支持；

 ===============华丽的分割线，第一阶段结束================

　　5.　现在进入第二阶段提交，现在proposer-1小姐使用分身术(多线程并发)分了3个自己分别去找3位官员，最先找到了1号官员签合同，遭到了1号官员的鄙视，1号官员告诉他proposer-2先生给了他11比特币，因为上一条规则的性质proposer-1小姐知道proposer-2第一阶段在她之后又形成了多数派(至少有2位官员的赃款被更新了);此时她赶紧去提款准备重新贿赂这3个官员(重新进入第一阶段)，每人20比特币。刚给1号官员20比特币， 1号官员很高兴初步接受了议题，还没来得及见到2,3号官员的时候

这时proposer-2先生也使用分身术分别找3位官员(注意这里是proposer-2的第二阶段)，被第1号官员拒绝了告诉他收到了20比特币，第2,3号官员顺利签了合同，这时2，3号官员记录client-2老板用了11比特币中标，因为形成了多数派，所以最终接受了Client2老板中标这个议题，对于proposer-2先生已经出色的完成了工作；

这时proposer-1小姐找到了2号官员，官员告诉她合同已经签了，将合同给她看，proposer-1小姐是一个没有什么职业操守的聪明人，觉得跟Client1老板混没什么前途，所以将自己的议题修改为“Client2老板中标”，并且给了2号官员20比特币，这样形成了一个多数派。顺利的再次进入第二阶段。由于此时没有人竞争了，顺利的找3位官员签合同，3位官员看到议题与上次一次的合同是一致的，所以最终接受了，形成了多数派，proposer-1小姐跳槽到Client2老板的公司去了。

===============华丽的分割线，第二阶段结束===============

　　Paxos过程结束了，这样，一致性得到了保证，算法运行到最后所有的proposer都投“client2中标”所有的acceptor都接受这个议题，也就是说在最初的第二阶段，议题是先入为主的，谁先占了先机，后面的proposer在第一阶段就会学习到这个议题而修改自己本身的议题，因为这样没职业操守，才能让一致性得到保证，这就是paxos算法的一个过程。原来paxos算法里的角色都是这样的不靠谱，不过没关系，结果靠谱就可以了。该算法就是为了追求结果的一致性。

转载自：http://www.cnblogs.com/endsock/p/3480093.html

示例

假如有一群驴友要决定中秋节去旅游，这群驴友分布在全国各地，假定一共25个人，分别在不同的省，要决定到底去拉萨、昆明、三亚等等哪个地点（会合时间中秋节已经定了，此时需要决定旅游地）。最直接的方式当然就是建一个QQ群，大家都在里面投票，按照少数服从多数的原则。这种方式类似于“共享内存”实现的一致性，实现起来简单，但Paxos算法不是这种场景，因为Paxos算法认为这种方式有一个很大的问题，就是QQ服务器挂掉怎么办？Paxos的原则是容错性一定要很强。所以，Paxos的场景类似于这25个人相互之间只能发短信，为了这件事情能够达成一致，这25个人找了另外的5个人（当然这5个人可以从25个人中选，这里为了描述方便，就单拿出另外5个人），比如北京、上海、广州、深圳、成都的5个人，25个人都给他们发短信，告诉自己倾向的旅游地。这5个人相互之间可以并不通信，只接受25个人发过来的短信。这25个人我们称为驴友，那5个人称为队长。

先来看驴友的逻辑。驴友可以给任意5个队长都发短信，发短信的过程分为两个步骤：

第一步（申请阶段）：询问5个队长，试图与队长沟通旅游地。因为每个队长一直会收到不同驴友的短信，不能跟多个驴友一起沟通，在任何时刻只能跟一个驴友沟通，按照什么原则才能做到公平公正公开呢？这些短信都带有发送时间，队长采用的原则是同意与短信发送时间最新的驴友沟通，如果出现了更新的短信，则与短信更新的驴友沟通。总之，作为一个有话语权的人，只有时刻保持倾听最新的呼声，才能做出最明智的选择。在驴友发出短信后，等着队长回复。某些队长可能会回复说，你这条短信太老了，我不与你沟通；有些队长则可能返回说，你的短信是我收到的最新的，我同意跟你沟通。对于后面这些队长，还得返回自己决定的旅游地。关于队长是怎么决定旅游地的，后面再说。

对于驴友来说，第一步必须至少有半数以上队长都同意沟通了，才能进入下一步。否则，你连沟通的资格都没有，一直在那儿狂发吧。你发的短信更新，你获得沟通权的可能性才更大。。。。。。

因为至少有半数以上队长（也就是3个队长以上）同意，你才能与队长们进行实质性的沟通，也就是进入第二步；而队长在任何时候只能跟1个驴友沟通，所以，在任何时候，不可能出现两个驴友都达到了这个状态。。。当然，你可以通过狂发短信把沟通权抢了。。。。

对于获得沟通权的那个驴友（称为A），那些队长会给他发送他们自己决定的旅游地（也可能都还没有决定）。可以看出，各个队长是自己决定旅游地的，队长之间无需沟通。

第二步（沟通阶段）：这个幸运的驴友收到了队长们给他发的旅游地，可能有几种情况：

第一种情况：跟A沟通的队长们（不一定是全部5个队长，但是半数以上）全部都还没有决定到底去那儿旅游，此时驴友A心花怒放，给这些队长发第二条短信，告诉他们自己希望的旅游地（比如马尔代夫）；

可能会收到两种结果：一是半数以上队长都同意了，于是表明A建议的马尔代夫被半数以上队长都同意了，整个决定过程完毕了，其它驴友迟早会知道这个消息的，A先去收拾东西准备去马尔代夫；除此之外，表明失败。可能队长出故障了，比如某个队长在跟女朋友打电话等等，也可能被其它驴友抢占沟通权了（因为队长喜新厌旧嘛，只有要更新的驴友给自己发短信，自己就与新人沟通，A的建议队长不同意）等等。不管怎么说，苦逼的A还得重新从第一步开始，重新给队长们发短信申请。

第二种情况：至少有一个队长已经决定旅游地了，A可能会收到来自不同队长决定的多个旅游地，这些旅游地是不同队长跟不同驴友在不同时间上做出的决定，那么，A会先看一下，是不是有的旅游地已经被半数以上队长同意了（比如3个队长都同意去三亚，1个同意去昆明，另外一个没搭理A），如果出现了这种情况，那就别扯了，说明整个决定过程已经达成一致了，收拾收拾准备去三亚吧，结束了；如果都没有达到半数以上（比如1个同意去昆明，1个同意去三亚，2个同意去拉萨，1个没搭理我），A作为一个高素质驴友，也不按照自己的意愿乱来了（Paxos的关键所在，后者认同前者，否则整个决定过程永无止境），虽然自己原来可能想去马尔代夫等等。就给队长们发第二条短信的时候，告诉他们自己希望的旅游地，就是自己收到的那堆旅游地中最新决定的那个。（比如，去昆明那个是北京那个队长前1分钟决定的，去三亚的决定是上海那个队长1个小时之前做出来的，于是顶昆明）。驴友A的想法是，既然有队长已经做决定了，那我就干脆顶最新那个决定。

从上面的逻辑可以看出，一旦某个时刻有半数以上队长同意了某个地点比如昆明，紧跟着后面的驴友B继续发短信时，如果获得沟通权，因为半数以上队长都同意与B沟通了，B必然会收到至少一个队长给他发的昆明这个结果，B于是会顶这个最新地点，不会更改，因为后面的驴友都会顶昆明，因此同意昆明的队长越来越多，最终必然达成一致。

看完了驴友的逻辑，那么队长的逻辑是什么呢？

队长的逻辑比较简单。

在申请阶段，队长只会选择与最新发申请短信的驴友沟通，队长知道自己接收到最新短信的时间，对于更老的短信，队长不会搭理；队长同意沟通了的话，会把自己决定的旅游地（或者还没决定这一信息）发给驴友。

在沟通阶段，驴友C会把自己希望的旅游地发过来（同时会附加上自己申请短信的时间，比如3分钟前），所以队长要检查一下，如果这个时间（3分钟前）确实是当前自己最新接收到申请短信的时间（说明这段时间没有驴友要跟自己沟通），那么，队长就同意驴友C的这个旅游地了（比如昆明，哪怕自己1个小时前已经做过去三亚的决定，谁让C更新呢，于是更新为昆明）；如果不是最新的，说明这3分钟内又有其它驴友D跟自己申请了，因为自己是个喜新厌旧的家伙，同意与D沟通了，所以驴友C的决定自己不会同意，等着D一会儿要发过来的决定吧。