我的原创paxos 1.doc

PAXOS（帕克索斯算法）及技术范畴 1.1?基本定义 算法中的参与者主要分为三个角色，同时每个参与者又可兼领多个角色: ⑴proposer?提出提案，提案信息包括提案编号和提议的value; ⑵acceptor?收到提案后可以接受(accept)提案; ⑶learner?只能学习被批准的提案; 算法保重一致性的基本语义: ⑴决议(value)只有在被proposers提出后才能被批准， (未经批准的决议称为提案(proposal)); ⑵在一次Paxos算法的执行实例中，只批准(chosen)一个value; ⑶learners只能获得被批准(chosen)的value; 有上面的三个语义可演化为四个约束: ⑴P1:一个acceptor必须接受(accept)第一次收到的提案; ⑵P2a:一旦一个具有value?v的提案被批准(chosen)，那么之后任何acceptor?再次接受(accept)的提案必须具有value?v; ⑶P2b:一旦一个具有value?v的提案被批准(chosen)，那么以后任何?proposer?提出的提案必须具有value?v; ⑷P2c:如果一个编号为n的提案具有value?v，那么存在一个多数派，要么他们中所有人都没有接受(accept)编号小于n的任何提案，要么他们已经接受(accpet)的所有编号小于n的提案中编号最大的那个提案具有value?v; 1.2?基本算法(basic?paxos) 算法(决议的提出与批准)主要分为两个阶段: 1.?prepare阶段：? (1).?当Porposer希望提出方案V1，首先发出prepare请求至大多数Acceptor。Prepare请求内容为序列号SN1; (2).?当Acceptor接收到prepare请求SN1时，检查自身上次回复过的prepare请求SN2 a).?如果SN2SN1，则忽略此请求，直接结束本次批准过程; b).?否则检查上次批准的accept请求SNx，Vx，并且回复SNx，Vx；如果之前没有进行过批准，则简单回复OK; 2.?accept批准阶段：? (1a).?经过一段时间，收到一些Acceptor回复，回复可分为以下几种: a).?回复数量满足多数派，并且所有的回复都是OK，则Porposer发出accept请求，请求内容为议案SN1，V1; b).?回复数量满足多数派，但有的回复为：SN2，V2，SN3，V3……则Porposer找到所有回复中超过半数的那个，假设为SNx，Vx，则发出accept请求，请求内容为议案SN1，Vx; c).?回复数量不满足多数派，Proposer尝试增加序列号为SN1+，转1继续执行; ?????????(1b).?经过一段时间，收到一些Acceptor回复，回复可分为以下几种: a).?回复数量满足多数派，则确认V1被接受; b).?回复数量不满足多数派，V1未被接受，Proposer增加序列号为SN1+，转1继续执行; (2).?在不违背自己向其他proposer的承诺的前提下，acceptor收到accept?请求后即接受并回复请求。 1.3?算法优化(fast?paxos) Paxos算法在出现竞争的情况下，其收敛速度很慢，甚至可能出现活锁的情况，例如当有三个及三个以上的proposer在发送prepare请求后，很难有一个proposer收到半数以上的回复而不断地执行第一阶段的协议。因此，为了避免竞争，加快收敛的速度，在算法中引入了一个Leader这个角色，在正常情况下同时应该最多只能有一个参与者扮演Leader角色，而其它的参与者则扮演Acceptor的角色，同时所有的人又都扮演Learner的角色。 在这种优化算法中，只有Leader可以提出议案，从而避免了竞争使得算法能够快速地收敛而趋于一致，此时的paxos算法在本质上就退变为两阶段提交协议。但在异常情况下，系统可能会出现多Leader的情况，但这并不会破坏算法对一致性的保证，此时多个Leader都可以提出自己的提案，优化的算法就退化成了原始的paxos算法。 一个Leader的工作流程主要有分为三个阶段： (1).学习阶段?向其它的参与者学习自己不知道的数据(决议); (2).同步阶段?让绝大多数参与者保持数据(决议)的一致性; (3).服务阶段?为客户端服务，提议案; 1.3.1?学习阶段 当一个参与者成为了Leader之后，它应该需要知道绝大多数的paxos实例，因此就会马上启动一个主动学习的过程。假设当前的新Leader早就知道了1-134、138和139的paxos实例，那么它会执行135-137和大于139的paxos实例的第一阶段。如果只检测到135和140的paxos实例有确定的值，那它最后就会知道1