咖啡伴侣

呆在上海
posts - 163, comments - 156, trackbacks - 0, articles - 2

paxos分布式一致性算法1

Posted on 2013-09-28 10:15 oathleo 阅读(198) 评论(0)  编辑  收藏

一日,诸葛亮找到刘备,突然献上一曲《独角戏》,而后放声大哭。刘备正沉醉于新曲,暗叹孔明大才,竟作得如此不凡仙乐,看到孔明忽而大悲,慌问:“水,何事悲恸?”
 
诸葛亮止住抽泣:“亮自主公三顾茅庐出山以来,蒙主公厚爱,自比如鱼得水,敢不尽力?然每日击鼓升帐,皆亮一人在上唱独角戏,众将在下唯唯诺诺,只是照亮的安排做事。如此下去,亮日后定会被司马懿那厮累死呀。”
刘备眨着充满问号的大眼睛:“孔明可是说曹贼丞相府小小的主薄司马懿?他有何德何能。。。”
诸葛亮慌打断:“亮心有些乱,且不提司马懿那小子。”
诸葛亮正襟危坐:“主公,我们要法制不要人制呀!万一哪天亮西去。。。”(刘备止含泪花握住孔明双手,孔明亦紧紧反握住刘备的大手)
半晌,诸葛亮续道:“岂不人亡政息?且主公百年后,阿斗与亮的关系又怎能比得如今亮与主公般相敬如宾?若亮在外争战,阿斗与亮政见不合要亮退兵,决策没有一致性,必将造成大错!如此,我大蜀何以恢复汉室江山呀?!”
刘备:“备深感如此。”
诸葛亮:“亮昨夜夜观天象。。。”
刘备大喜:“孔明可有良法?”
诸葛亮:“。。。亮昨夜夜观天象,竟然睡着,原来近日太耗心力。做一梦,数千年弹指间,亮醒来才觉泪流满面。梦中一帅哥自称陶辉,献上色目人大牛Leslie一法名paxos,或可解我等燃眉之急。”
刘备狂喜:“好!”继而搔了搔头:“先请孔明试言我大蜀帝国决策上有哪些问题?”
诸葛亮:“喏。”



1、蜀国现在决策制度的缺陷
诸葛亮:“主公,当下蜀国所有决策皆来自亮,这有两个问题,一、若亮身体有恙则政令必有耽误。二、随着汉中的收复,我们的地盘越来越大,事务也越来越多,目前亮乃五百年不世出奇才,尚能支撑,可若是将来收复长安,亮一人之力必不堪重负。请问主公有何策解此二难?”


刘备沉吟着:“可让法正法孝直,黄权黄公衡为你副手,平日助你共同议政决策,能帮你减负呀。孔明你老习惯在初一十五深入民间依红偎翠,那时他们都可暂时顶替于你,如此也不怕政令耽误了。”
诸葛亮咳嗽了下:“此二人皆治世之才!然,若子龙请求黄公衡允许蜀棉私营,而同时主公又请求亮加强垄断这有钱途的行业--禁止蜀棉私营,文武百官令行两出,或听亮的搞国家垄断,或听黄公衡的搞民营经济,百姓何以自处?”

刘备沉思半晌,方答道:“我们把决策分为两部分,一种是新增政策,如我正准备加税。另一种是下级官员请求政令的解释,比如马超出征归来时问伤兵抚恤金是多少等等。这样,孔明可处理所有新增决策,法正与黄权只负责解释已有决策。下面官员在执行时,任意找你三人中清闲者,就某个事件询问有何政令可指导,需要增加新的法令时,则只能找孔明你,孔明你决定新法令后,再通知法正和黄权这哥俩,这样法令就同步且一致了。当孔明不在时,由法正顶上这个决策位置;法正不在时,由黄权顶上。如此可好?”
诸葛亮惊喜道:“善!这可是master-slave设计呀!”
刘备也睁大了双眼闪着问号。诸葛亮咳嗽了下:“亮昨夜未睡好,失言了。”

诸葛亮又说道:“可这样还有问题,日后若我们收复许昌洛阳建业后,那时新法令会更多,只允许一人处理新法令新决策,必然还会忙不过来!而且,人为的指定亮的第二顺拉继承者是法正,黄权为第三顺位,这样也不妥,在地位不平等时,若以后决策组又增加许多新人,或者同一时间多人一起吃酒吃坏肚子,都会非常麻烦。”

刘备拍案而起:“孔明你主张大家都是同样地位,没有主次之分?这样无论哪个人出问题了,都不会对蜀国有什么影响?而且多人之间信息共享后,不会因人废事,也不会有人亡政息之事了?”
诸葛亮:“Bingo! 全对!这是真正的分布式!”
刘备大声叫好:“分布式?好名字,和八阵图一样响亮呀!”
诸葛亮:“但这完全平等的分布式决策机制,仍然必须政令统一,不能有不一致的法令,例如黄权认为他昨天中午通过的法令是嚼口香糖者一律杖责十板,免得有人随地乱吐影响市容(好象他们还立法大便后必须冲马桶)。而法正却在昨天上午就接受番邦李光耀的提议,允许嚼外国进口环保口香糖,百姓到底听谁的呢?”
刘备:“我知道孔明你很讨厌威权国家,别老抱怨,新加坡又没碍你事。上面这就是一致性问题了。孔明别卖关子了,快说你的paxos解决方法吧。”



2、paxos需要解决的分布式问题
诸葛亮激动道:“paxos可是真正的民主呀,两千年后我们汉人仍然做不到,这不是汉人的劣根性(乌坎村都能办好的),实是历史遗毒呀。闲话少叙,我们先来看看除了能保持一致性,paxos能解决哪些问题吧。

一、决策委员会里缺了哪个人都可以,蜀国照常做出决策。

二、大家的办公地又不在一起,平时通过信使小吏们传递消息,若信使在路上传消息时被马车撞死,仍然不会有政令不一致。

三、若信使被马车撞伤了,医治后迟了几个月才送到某人(例如法正),还不会出现政令不一致。

四、若信使被马车撞失忆了,以为刚送过消息的黄权还没送过,又跑去告诉黄权一次,同样不会有不一致出现。”
刘备:“孔明,我知道你马车机关多,开名车也不用总提嘛!若是信使被曹操的间谍收买了也没事吗?”
诸葛亮尴尬道:“这个不行,我们还是要相信人性本善嘛。呃,蜀国大部分都是好人。嗯,好吧,我们国安局不是吃干饭的,信使可以丢失、重复传递、延迟,但是我们保证不会被收买的。”
刘备:“好吧,能解决这四个问题也很不错,基本异常都考虑到了。快说说这个paxos解决之道吧。”



3、paxos的约束条件
诸葛亮:“刚刚不是说了民主吗?民主是个宝呀,它能解决一切问题。决策者之间不分高下,所以既然想要他们保持一致,我们就要用投票,少数服从多数!”
刘备:“怎么个投法?”
诸葛亮:“如果主公手下五虎上将是五个决策者。。。”刘备:“那五个肌肉男?”
诸葛亮:“正是,这证明即使五个头脑简单的武夫也能做好。”(五虎将齐打喷嚏。)
诸葛亮:“谁提议新政令(提案者),谁就发起投票。我们保证,投票者必须是决策者中的大多数。”
刘备:“怎么定大多数呢?”
诸葛亮:“任意两次投票中,必须有重合的决策者,这就是大多数了。比如五虎将做决策者,每次政令通过中,必须有三个人或更多投票的人才能决定,这样两次投票中至少有一人都参加了,他就可以拍板!对提案者来说,如果大多数投票者都投赞成这个提议,法令就通过。”
刘备沉重地说道:“孔明,万一总是凑不成大多数,岂不是耽误我们的现代化进程?民主,对中国国情来说,太复杂了。”

诸葛亮又激动了:“主公,不复杂的,长远来看好处很明显,不要短视!如果能做到以个三个基本点,所有政令绝对不会出现不一致,而且不会出现无法进行下去的事。一、所有政令必须被提出后才能批准;二、一次提出政令的过程中,只能批准一条政令;三、书记官(负责永久记录政令的官员)只能学习已经批准的政令。只要做到这三点,肯定不会政令不一致!”
刘备:“可是孔明,你在说什么呀?我只想知道决策者该怎么做。”
诸葛亮自信满满:“别急主公,从数学上可以证明,只要满足上面三条,一定不会出现政令不一。当然,这三条太宽泛了,不能对决策者做出指导。我还有更加严格的约束。一、每个决策者必须接受他收到的第一个提议政令。”
刘备:“凭什么呀?”诸葛亮:“我们要假定提议者已经搞清楚了一切,肯定是好提案啦。这不是我们的重点,别打断我。”
诸葛亮:“二、一旦关于一件事,我们通过一条法令后,之后关于这件事通过的任何法令,都还得是这个法令。”
刘备呆了下:“这不废话吗?”
诸葛亮自信满满:“虽然是废话,但你想,保证了这第2条,是不是所有的政令都必须一致呀?”
刘备:“可是对决策者没指导意义呀。”
诸葛亮自信满满:“是的,所以,我们加强约束,三、如果一条法令批准后,之后每一个决策者如果关于这件事又通过法令,那这个法令还得是同一条。”
刘备傻了:“你说得是没错,可这有什么用呢?”
诸葛亮自信满满:“所以继续加强约束:四、如果一条法令被批准通过了,之后提议者关于这件事,又提新法令,必须还得是同一个法令。”
刘备怒了:“孔明我想揍你了,你说这些有个屁用啊!”
诸葛亮自信满满:“别急主公,现在我要祭出最强约束条件作为我的奥义了:五、每个提案都得有个独一无二的编号,如果编号N的提案通过了,那么大多数决策者们,要么从没接受者编号小于N的任何提议,要么最近一次批准通过的法令就是这个提案。”
刘备开始追打诸葛亮:“孔明你个坏人,你玩我呀!这屁话你对我说!”
诸葛亮边逃边喊:“wiki里就是这么解释的,哎,主公你不懂数学别打我嘛。Leslie的论文也是这么写的。。。”



4、paxos执行流程
刘备:“真爽,孔明你手感不错。说点实在的吧,不懂的东西少扯。”
诸葛亮:“主公,你不懂数学嘛。好吧,我来说说paxos算法的流程,就三段式,六个步骤而已。角色包括,提案者,决策者,书记官(学习政令的)。
一、提案者先从主公那里搞到个独一无二的编号,例如N。找到决策者们的多数派,就说五虎将吧,找到三个肌肉男先。假设,这个提案者来自成都,想提的是,外地蜀国将级官员不得无故进入魏国使者驻蜀驿馆。那么,提案者发给三个五虎将,提案中说,我现在有个编号N的提案,关于蜀国高级将领进出魏国使者驿馆的事,请回答我。”

二、五虎将们收到了关于使者驿馆事件的提案,编号是N。其中任一个决策者,比如赵云,他在收到N提案后,首先检查,之前关于魏国使者驿馆事件,有没有收到过提案啊?如果没收到,当然回复提案通过,同时赵云拿出自己的小本本记上,已经回复编号N的提案。如果收到过关于驿馆事件的编号M的提案,就检查编号M,如果M大于N,那么跟信使说,我拒绝这个提案。如果M小于N,回复通过,并且说,关于这事,上次我已经收到了编号M的提案了。

三、提案者如果收到多数决策者的通过回复,就开始正式提议了。这时,先检查五虎将的回复,如果都简单的回复通过,那么就正式提议之前想提议的《蜀国将级官员不得无故进入魏国使者驻蜀国驿馆》提案。如果决策者们不是简单的回复通过,而是说:这次我赵云通过了,但是我曾经回复过编号M的提案。这样,提案者需要从这次决策者们的回复中,找出所有编号M中的最大值。假设就赵云复杂的回复了,其他四人都是简单的回复通过。那么,提案者这次不能正式提议自己原来想提的,而要提议编号M对应的提案。

四、同第二步骤一样,五虎将们根据二步骤的准则,选择通过还是不通过。
五、提案者如果发现多数决策者同意了,意味着法令通过,这时他要记录法令,同时告诉书记官们。
六、书记官们在羊皮纸上记录法令。“



5、paxos算法里的各角色该做的事
刘备搔搔头:“孔明,你再说说提案者,决策者要做的事吧,书记官的很简单,就不用说了。”
诸葛亮:“主公,书记官的工作不简单啊,信使会传丢消息的,书记官也会生病的。我们既要在法令通过时主动通知书记官,又要允许书记官在对法令不清楚时过来主动询问。不过,既然主公想多了解提案者和决策者的工作,我就来详细说说。
一、提案者。首先他得从主公那搞来一个独一无二的编号。”
刘备:“我很忙的孔明,我是一把手哎。”
诸葛亮有些无奈:“就光给编号也不干呀!那让他们自己维护自己的编号吧,遇到编号相同时,按级别排序,例如按关羽、张飞、赵云、马超、黄忠排序。然后要找到五虎将的多数派,例如关张赵这三人,发自己要决定的事以及编号过去。这是第一步。在第三步时,又到了提案者要做工作了。如果关羽又不响应自己了,那么再发给黄忠问问看。直到有大多数人响应自己。对于响应的处理,有以下情况:
A、这些响应中,如果有人明确拒绝,比如赵云说,关于驿馆事件,我已经批了编号大于N的提案,那么这次提案最好就放弃吧,或者加大自己的编号,重复第一步再提!
B、张飞说我可以通过,但是之前我批准过驿馆事件编号小于N的提案,内容是允许进入达到政治避难目的。那么,这次提案内容必须变更为张飞之前提交的方案。
C、所有人都无条件通过。继续正式提交自己的方案。
到第五步,如果多数派批准了,那么方案正式成为法令。提案者要告诉书记官记录哦。”
刘备:“你这么说我就明白了嘛。多简单?先前搞七搞八的说了一大通。”
诸葛亮:“唉,先前的证明嘛。当然,微软还搞了个两段式提交,号称fast paxos,那个雅虎的zookeeper也是的,其实也就对第五步做了优化。主公,不要打我,你不用管我刚才说了什么。我们继续说决策者的工作。
第二步,决策者开始工作了。例如还是说赵云,他在收到N提案后,首先检查,之前关于魏国使者驿馆事件,有没有收到过提案啊?如果没收到,简单的回复提案通过,同时赵云拿出自己的小本本记上,已经回复编号N的提案。赵云同时承诺,以后收到编号小于N的关于驿馆事件的提案,保证不批!如果收到过编号M的提案,检查这上次编号M,如果M大于N,那么跟信使说,我拒绝这个提案。如果M小于N,回复通过,并且说,关于这事,上次我已经收到了编号M的提案了。
第四步决策者批准时也和上面一样。不过fast paxos等两段式的paxos改进算法,在这里决策者们已经可以记录法案了。”
刘备:“好孔明!我有些明白了,不过光说不练假把式,演习下吧。把五个肌肉男叫来,你我来提案,外加捣乱,你可以用你的跑车撞信使了,看看是否出现不一致。”
诸葛亮:“No problem。不过现在我口干舌燥,咱们下回再说吧。”(想从具体的演习,从时间和各种容错上看paxos的效用,敬请期待下篇《paxos算法如何容错的--讲述五虎将的实践》


只有注册用户登录后才能发表评论。


网站导航: