fast paxos_dubbo zookeeper原理_fast paxos是什么算法(3)

刘备呆了下：“这不废话吗？”

诸葛亮自信满满：“虽然是废话，但你想，保证了这第2条，是不是所有的政令都必须一致呀？”

刘备：“可是对决策者没指导意义呀。”

诸葛亮自信满满：“是的，所以，我们加强约束，三、如果一条法令批准后，之后每一个决策者如果关于这件事又通过法令，那这个法令还得是同一条。”

刘备傻了：“你说得是没错，可这有什么用呢？”

诸葛亮自信满满：“所以继续加强约束：四、如果一条法令被批准通过了，之后提议者关于这件事，又提新法令，必须还得是同一个法令。”

刘备怒了：“孔明我想揍你了，你说这些有个屁用啊！”

诸葛亮自信满满：“别急主公，现在我要祭出最强约束条件作为我的奥义了：五、每个提案都得有个独一无二的编号，如果编号N的提案通过了，那么大多数决策者们，要么从没接受者编号小于N的任何提议，要么最近一次批准通过的法令就是这个提案。”

刘备开始追打诸葛亮：“孔明你个坏人，你玩我呀！这屁话你对我说！”

诸葛亮边逃边喊：“wiki里就是这么解释的，哎，主公你不懂数学别打我嘛。Leslie的论文也是这么写的。。。”

4、paxos执行流程

刘备：“真爽，孔明你手感不错。说点实在的吧，不懂的东西少扯。”

诸葛亮：“主公，你不懂数学嘛。好吧，我来说说paxos算法的流程，就三段式，六个步骤而已。角色包括，提案者，决策者，书记官（学习政令的）。

一、提案者先从主公那里搞到个独一无二的编号，例如N。找到决策者们的多数派，就说五虎将吧，找到三个肌肉男先。假设，这个提案者来自成都，想提的是，外地蜀国将级官员不得无故进入魏国使者驻蜀驿馆。那么，提案者发给三个五虎将，提案中说，我现在有个编号N的提案，关于蜀国高级将领进出魏国使者驿馆的事，请回答我。”

四、同第二步骤一样，五虎将们根据二步骤的准则，选择通过还是不通过。

五、提案者如果发现多数决策者同意了，意味着法令通过，这时他要记录法令，同时告诉书记官们。

六、书记官们在羊皮纸上记录法令。“

5、paxos算法里的各角色该做的事

刘备搔搔头：“孔明，你再说说提案者，决策者要做的事吧，书记官的很简单，就不用说了。”

诸葛亮：“主公，书记官的工作不简单啊，信使会传丢消息的，书记官也会生病的。我们既要在法令通过时主动通知书记官，又要允许书记官在对法令不清楚时过来主动询问。不过，既然主公想多了解提案者和决策者的工作，我就来详细说说。

一、提案者。首先他得从主公那搞来一个独一无二的编号。”

刘备：“我很忙的孔明，我是一把手哎。”

诸葛亮有些无奈：“就光给编号也不干呀！那让他们自己维护自己的编号吧，遇到编号相同时，按级别排序，例如按关羽、张飞、赵云、马超、黄忠排序。然后要找到五虎将的多数派，例如关张赵这三人，发自己要决定的事以及编号过去。这是第一步。在第三步时，又到了提案者要做工作了。如果关羽又不响应自己了，那么再发给黄忠问问看。直到有大多数人响应自己。对于响应的处理，有以下情况：

A、这些响应中，如果有人明确拒绝，比如赵云说，关于驿馆事件，我已经批了编号大于N的提案，那么这次提案最好就放弃吧，或者加大自己的编号，重复第一步再提！

B、张飞说我可以通过，但是之前我批准过驿馆事件编号小于N的提案，内容是允许进入达到避难目的。那么，这次提案内容必须变更为张飞之前提交的方案。

C、所有人都无条件通过。继续正式提交自己的方案。

到第五步，如果多数派批准了，那么方案正式成为法令。提案者要告诉书记官记录哦。”

刘备：“你这么说我就明白了嘛。多简单？先前搞七搞八的说了一大通。”

诸葛亮：“唉，先前的证明嘛。当然，微软还搞了个两段式提交，号称fast paxos，那个雅虎的zookeeper也是的，其实也就对第五步做了优化。主公，不要打我，你不用管我刚才说了什么。我们继续说决策者的工作。

第四步决策者批准时也和上面一样。不过fast paxos等两段式的paxos改进算法，在这里决策者们已经可以记录法案了。”

刘备：“好孔明！我有些明白了，不过光说不练假把式，演习下吧。把五个肌肉男叫来，你我来提案，外加捣乱，你可以用你的跑车撞信使了，看看是否出现不一致。”

诸葛亮：“No problem。不过现在我口干舌燥，咱们下回再说吧。”（想从具体的演习，从时间和各种容错上看paxos的效用，敬请期待下篇《paxos算法如何容错的--讲述五虎将的实践》）

两人携手扬长而去。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-29391-3.html