2014/10/21图解分布式一致性协议Paxos-loopincodes
http://codemacro.com/2014/10/15/explain-poxos/1/7
Paxos协议/算法是分布式系统中比较重要的协议，它有多重要呢？
<分布式系统的事务处理>：
<大规模分布式存储系统>：
学习Paxos算法有两部分：a)算法的原理/证明；b)算法的理解/运作。
理解这个算法的运作过程其实基本就可以用于工程实践。而且理解这个过程相对来说也容易得
多。
网上我觉得讲Paxos讲的好的属于这篇：paxos图解及Paxos算法详解，我这里就结合wiki上的
实例进一步阐述。一些paxos基础通过这里提到的两篇文章，以及wiki上的内容基本可以理
解。
算法内容
Paxos在原作者的《PaxosMadeSimple》中内容是比较精简的：
图解分布式一致性协议Paxos
OCT15TH,201412:00AM
GoogleChubby的作者MikeBurrows说过这个世界上只有一种一致性算
法，那就是Paxos，其它的算法都是残次品。
理解了这两个分布式协议之后(Paxos/2PC)，学习其他分布式协议会变得相
当容易。
Phase1
(a)Aproposerselectsaproposalnumbernandsendsapreparerequest
withnumberntoamajorityofacceptors.
(b)Ifanacceptorreceivesapreparerequestwithnumberngreaterthan
thatofanypreparerequesttowhichithasalreadyresponded,thenit
2014/10/21图解分布式一致性协议Paxos-loopincodes
http://codemacro.com/2014/10/15/explain-poxos/2/7
借用paxos图解文中的流程图可概括为：
respondstotherequestwithapromisenottoacceptanymoreproposals
numberedlessthannandwiththehighest-numberedpro-posal(ifany)
thatithasaccepted.
Phase2
(a)Iftheproposerreceivesaresponsetoitspreparerequests(numbered
n)fromamajorityofacceptors,thenitsendsanacceptrequesttoeach
ofthoseacceptorsforaproposalnumberednwithavaluev,wherevis
thevalueofthehighest-numberedproposalamongtheresponses,oris
anyvalueiftheresponsesreportednoproposals.
(b)Ifanacceptorreceivesanacceptrequestforaproposalnumberedn,
itacceptstheproposalunlessithasalreadyrespondedtoaprepare
requesthavinganumbergreaterthann.
2014/10/21图解分布式一致性协议Paxos-loopincodes
http://codemacro.com/2014/10/15/explain-poxos/3/7
实例及详解
Paxos中有三类角色Proposer、Acceptor及Learner，主要交互过程在Proposer和
Acceptor之间。
Proposer与Acceptor之间的交互主要有4类消息通信，如下图：
2014/10/21图解分布式一致性协议Paxos-loopincodes
http://codemacro.com/2014/10/15/explain-poxos/4/7
这4类消息对应于paxos算法的两个阶段4个过程：
phase1
a)proposer向网络内超过半数的acceptor发送prepare消息
b)acceptor正常情况下回复promise消息
phase2
a)在有足够多acceptor回复promise消息时，proposer发送accept消息
b)正常情况下acceptor回复accepted消息
因为在整个过程中可能有其他proposer针对同一件事情发出以上请求，所以在每个过程中都会
有些特殊情况处理，这也是为了达成一致性所做的事情。如果在整个过程中没有其他proposer
来竞争，那么这个操作的结果就是确定无异议的。但是如果有其他proposer的话，情况就不一
样了。
以paxos中文wiki上的例子为例。简单来说该例子以若干个议员提议税收，确定最终通过的法
案税收比例。
以下图中基本只画出proposer与一个acceptor的交互。时间标志T2总是在T1后面。propose
number简称N。
2014/10/21图解分布式一致性协议Paxos-loopincodes
http://codemacro.com/2014/10/15/explain-poxos/5/7
情况之一如下图：
A3在T1发出accepted给A1，然后在T2收到A5的prepare，在T3的时候A1才通知A5最终结果
(税率10%)。这里会有两种情况：
A5发来的N5小于A1发出去的N1，那么A3直接拒绝(reject)A5
A5发来的N5大于A1发出去的N1，那么A3回复promise，但带上A1的(N1,10%)
这里可以与paxos流程图对应起来，更好理解。acceptor会记录(MaxN,AcceptN,
AcceptV)。
A5在收到promise后，后续的流程可以顺利进行。但是发出accept时，因为收到了(AcceptN,
AcceptV)，所以会取最大的AcceptN对应的AcceptV，例子中也就是A1的10%作为AcceptV。
如果在收到promise时没有发现有其他已记录的AcceptV，则其值可以由自己决定。
针对以上A1和A5冲突的情况，最终A1和A5都会广播接受的值为10%。
其实4个过程中对于acceptor而言，在回复promise和accepted时由于都可能因为其他proposer
的介入而导致特殊处理。所以基本上看在这两个时间点收到其他proposer的请求时就可以了解
整个算法了。例如在回复promise时则可能因为proposer发来的N不够大而reject：
2014/10/21图解分布式一致性协议Paxos-loopincodes
http://codemacro.com/2014/10/15/explain-poxos/6/7
如果在发accepted消息时，对其他更大N的proposer发出过promise，那么也会reject该
proposer发出的accept，如图：
这个对应于Phase2b)：
2014/10/21图解分布式一致性协议Paxos-loopincodes
http://codemacro.com/2014/10/15/explain-poxos/7/7
总结
LeslieLamport没有用数学描述Paxos，但是他用英文阐述得很清晰。将Paxos的两个Phase的
内容理解清楚，整个算法过程还是不复杂的。
至于Paxos中一直提到的一个全局唯一且递增的proposernumber，其如何实现，引用如下：
参考文档
paxos图解,http://coderxy.com/archives/121
Paxos算法详解,http://coderxy.com/archives/136
Paxos算法wiki,http://zh.wikipedia.org/zh-
cn/Paxos%E7%AE%97%E6%B3%95#.E5.AE.9E.E4.BE.8B
原文地址：http://codemacro.com/2014/10/15/explain-poxos/
writtenbyKevinLynxpostedathttp://codemacro.com
PostedbyKevinLynxOct15th,201412:00amnetwork
itacceptstheproposalunlessithasalreadyrespondedtoaprepare
requesthavinganumbergreaterthann.
如何产生唯一的编号呢？在《Paxosmadesimple》中提到的是让所有的
Proposer都从不相交的数据集合中进行选择，例如系统有5个Proposer，则
可为每一个Proposer分配一个标识j(0~4)，则每一个proposer每次提出决议
的编号可以为5i+j(i可以用来表示提出议案的次数)
|
|
