vlambda博客
学习文章列表

群雄当立,逐鹿分布(二)Paxos传说之败走拜占庭

荒岛传说

      相传在遥远的西方国度、海的另一边,有一无名群岛,一位最先发现群岛的叫做莱斯利·兰伯特的男人变成了岛主,为了凝聚起岛民的力量,抵御外侮,建立起了城邦,并把城邦,命名成Paxos,建立起了帮派。根据野史记载,Paxos是莱斯利·兰伯特闭关七七四十九天,参悟分布式天书所创,天书其威力之大竟恐怖如斯,同时座下有Basic,Multi和Fast三大镇派神器,古往今来,千难万险,魑魅魍魉,均没有撼动这三大神器的神威。凭借着三大神器和帮主的上下一心,在分布式江湖的共识一派,可算作是跺跺脚,江湖也要抖一抖的存在。

      岛主莱斯利·兰伯特,向往偶然听说过的《桃花源记》,于是致力于将岛屿打造成人人平等的桃花源,按照议会民主制的政治模式制定了岛规,对于在岛上生活的岛民足够的自由,在这里人民并不需要惧怕专制的管理,在号召的时候,没有出席的义务,也自然没有了出席的时间限制。

      在这样一个自由的城邦,一个个法令,是怎么在每一个居民里面达成共识的呢?

颁布法令

      如何解决颁布法令,将法令传给每一个成员,成了岛主需要立马解决的问题。在分布式天书里面有两种法令颁布,信息通信的方式,一种是共享内存,这个需要在城邦中心树立一个告示中心,法令只能由此颁布,并且各个成员需要来读取、修改共享的内容,在众多成员的情况下,先后顺序,时效性,信息的一致性这些无疑都是一个复杂的问题。

      另外一种是消息传递,飞鸽传书。此类方式讲究以发送和接受,以数据作为信息的载体以达成交换、同步,同时对于消息的送达,还通过是否等待结果反馈,一致性目标达成作为标准,把信息的传递分为同步和异步两种方式。不论是哪种方式,信息发布的方式都有可能因为成员、通信的各种问题,导致消息的延迟、丢失、重复、篡改等各种问题。

群雄当立,逐鹿分布(二)Paxos传说之败走拜占庭

      英明的岛主莱斯利·兰伯特,选用了消息传递这种方式,是因为他不仅仅想征服Paxos城邦,他相信总有一天,他的领土会扩散到整个分布式江湖。于是野心勃勃的开始成立议会,选举议员,作为决策团,但是噩耗随之传来。。。

败走拜占庭

      岛主莱斯利·兰伯特不仅仅有着Paxos城邦,同时还有着一支战无不胜的军队,很少有人能见到这样的一支王牌军队,据说见过的这只军队,都成了军队的刀下亡魂。只知道,这只军队,常年驻扎在Paxos城邦不远的拜占庭,没有人知道这只军队到底有多少人,也没有人知道这只军队有多少战无不胜的将军,人们只知道军队是拜占庭军队,将军是拜占庭将军

      岛主看中了NET城邦的石油,可是这个NET城邦,却拒绝无条件的将石油上供,于是不开心的莱斯利·兰伯特岛主,将手中端着的红酒杯狠狠的摔在了地上,并且向拜占庭将军下达了攻下NET城池的军令,要拜占庭立下军令状,保证NET城池不再有问题,不再是威胁。

      拜占庭军队里面的9个将军,对于岛主的这个命令,并不是所有的人都赞同,毕竟这种毫不顾忌的侵略者嘴脸,多少让军人感到了耻辱,并且NET城池,他们早早的就听说了,因为石油丰富,财富可倾天下,是一块难啃的骨头。但是军令如山,9个将军只好率领着各自的部下,分为多路进攻,以天亮为号,共同进攻,当然他们也做好了情势不妙之后战略性撤退的准备。

      在短暂的将军峰会之后,他们约定他们的攻城策略,只有两种进攻和撤退。并且由于兵力上并没有压倒性优势,所以多路进攻,让NET疲于应对,这些策略,缺一不可,所以他们必须通过投票来表决共同进攻,还是共同撤退,并且约定,少数服从多数的quorum原则,如果有5个以上的将军同意进攻就全员进攻,如果5个以上的将军同意撤退,就撤退,毕竟战场局势瞬息万变。因此他们分别在各自部下中选出了斥候,来互相联系,分九路进攻。岛主莱斯利·兰伯特对这样的战术,大为赞赏,并且大笔一挥,命名为九九归一战术,认为将士此去必定凯旋而归。

      可是岛主莱斯利·兰伯特,忽略了人为财死,鸟为食亡的道理,也忽视了NET城池雄厚的财力,他们买通了其中一名拜占庭将军,让他误导他们的投票,导致了拜占庭大败,岛主莱斯利·兰伯特更是下令将此段历史封存,不允许Paxos城邦的任何人提及。

      根据NET城池的官方史料记载,当时9个拜占庭将军来攻打NET城池,他们花了大价钱才买通了一个将军,当时有8位将军忠心耿耿,面对财富美女,毫不动摇,当时碍于NET城池的兵力,4位将军投了进攻的消息,4位将军投了撤退的消息,被收买的将军,向投进攻的4位将军,投了进攻消息,在这4位将军看来,他们会9路军队直捣黄龙。向投了撤退的4位将军投了撤退消息,在这4位将军看来,因为对方火力强大,他们得到了5票撤退,因此他们选择暂避锋芒。

      于是,4位投了进攻的将军及其部下被NET城池全俘。岛主莱斯利·兰伯特惨遭大败,并且下了最严酷的宪法,叛变是Paxos城邦的第一重罪,将会株连九族,因此世人均知道在Paxos城邦,拜占庭将军问题是不可提之殇,拜占庭将军问题是不可以被容忍的,在问题得到完美解决之前,拜占庭军队永不启用!!!反而人人开始向Paxos城邦涌来,因为他们知道,在Paxos不需要考虑拜占庭将军问题。

天价悬赏

      虽然这段历史被岛主封存了,但是在Paxos城邦大刀阔斧之初,出现了这样的噩耗,难免如鲠在喉,让岛主彻夜难眠,不眠不休的翻看着分布式天书,同时Paxos也发布了悬赏,只要能解决了拜占庭问题,无论出身如何,直接提拔为副城主,一人之下,万人之上。

      在分布式天书里,岛主莱斯利·兰伯特渐渐有着不同的思路来应对,只是解决方案并不完美,因此Paxos的重刑仍然是背叛。

      其中一个方案是多数原则。即使拜占庭将军里面有人被收买,只要背叛了的将军不是大多数,那么整个命令还是能达成共识的,因为在这种情况下,被收买的人很容易被查出来,并且Paxos的宪法对于被抓出来的叛徒是零容忍的,株连九族。假设被收买的将军,向将军A和将军B发送了不同的消息,那么A和B之间是很容易发现信息不一致,即使不能确认这个将军被收买了,因为A跟B也可能是被收买的将军,但是至少可以知道,这三个将军里面是有问题的。因此,只要拜占庭将军里面背叛的人少于三分之一,就认为拜占庭军队还是可靠的。

      另外,岛主为了应对,斥候被人劫杀,冒充,消息被人家劫去,并且谎报军情,因此给将军们的斥候,发布了数字签名令牌,防止消息被篡改。

      可是这些方案,总是不能让岛主高枕无忧,在迷迷糊糊的梦中他再次看见了那本分布式天书,天书散发着金光,上面飘渺的显现着一串串的箴言:FTMP,MMFCS,SIFT,PBFT.....

说明及预告

      下一期,我们探讨让Paxos城邦运转起来的basic,multi,fast 三大神器。

八佾Talk

子曰:“邦有道,危言危行;邦无道,危行言孙。” --有感于上海2022年04月21日

References

[1] The Byzantine Generals Problemhttp://lamport.azurewebsites.net/pubs/byz.pdf