比特币价格·比特币行情
Ctrl+D收藏简单区块链

用三国杀讲分布式算法 太舒适了吧?

作者:

时间:2020/12/12 20:20:48

前言

《三国杀》是一款热门的卡牌游戏,结合中国三国时期背景,以身份为线索,以卡牌为形式,益智休闲,老少皆宜。

在讲解之前,我们先聊下分布式协议和算法整体脉络。

现在很多开发同学对分布式的组件怎么使用都有一定经验,也知道 CAP 理论和 BASE 理论的大致含义。但认真去看分布式算法的真的很少,原因有三:

担心算法过于复杂,所以花的时间很少。

网上的资料能用大白话将分布式算法讲清楚的比较少。

学习分布式算法没有一条清晰的路线。

我会在后续的文章中用故事、大白话的方式来讲解分布式算法的原理,以及学习路线到底是怎么样的。

1.学习路线

学习分布式协议和算法的路线可以是先学习四大基础理论,作为地基,再学习分布式协议和算法,就像是在地基上建房子。地基打好了,才能建更稳固的高楼大厦。

四大基础理论:

拜占庭将军问题

CAP 理论

ACID 理论

BASE 理论

八大分布式协议和算法:

Paxos 算法

Raft 算法

一致性 Hash 算法

Gossip 协议算法

Quorum NWR 算法

FBFT 算法

POW 算法

ZAB 协议

因篇幅原因,本篇只涉及拜占庭将军问题。

2.拜占庭将军问题

大家可能听过拜占庭将军问题。它是由莱斯利·兰伯特提出的点对点通信中的基本问题。

拜占庭位于如今的土耳其的伊斯坦布尔,是东罗马帝国的首都。由于当时拜占庭罗马帝国国土辽阔,为了达到防御目的,每个军队都分隔很远,将军与将军之间只能靠信差传消息。在战争的时候,拜占庭军队内所有将军和副官必须达成一致的共识,决定是否有赢的机会才去攻打敌人的阵营。但是,在军队内有可能存有叛徒和敌军的间谍,这个就是拜占庭容错问题。

实际上拜占庭问题是分布式领域最复杂的一个容错模型。一旦理解它,就能掌握分布式共识问题的解决思路,还能帮助大家理解常用的共识算法,也可以帮助我们在工作中选择合适的算法,或者设计合适的算法。

为什么第一个基础理论是拜占庭将军问题?

因为它很好地抽象出了分布式系统面临的共识问题。上面提到的 8 种分布式算法中有 5 种跟拜占庭问题相关,可以说弄懂拜占庭问题对后面学习其他算法就会容易很多。

下面我用三国杀游戏中的身份牌来讲解拜占庭将军问题。

2.1 三国杀身份牌

三国杀中主要有四种身份:主公、忠臣、反贼、内奸。每个游戏玩家都会获得一个身份牌。主公只有 1 个。忠臣最多 2 个,反贼最多 4个,内奸最多一个。

主公

主公身份牌

获胜条件:消灭所有反贼和内奸

技巧:以自己生存为首要目标,分散反贼注意力。配合忠内剿灭反贼并判断谁是忠谁是内。

忠臣

忠臣身份牌

获胜条件:保护主公存活的前提下消灭所有反贼和内奸。

技巧:忠臣是主公的屏障,威慑反贼和内奸的天平。

反贼

反贼身份牌

获胜条件:消灭主公即可获胜。

技巧:反贼作为数量最多的身份,需要集中火力猛攻敌人弱点。正确的思路是获胜的关键。

内奸

内奸身份牌

获胜条件:先消灭反贼和忠臣,最后与主公单挑成为最后唯一生还者。

技巧:正确的战术+ 冷静的头脑+ 运气。

2.2 还原拜占庭问题

东汉末年,袁绍作为盟主,汇合了十八路诸侯一起攻打董卓。把董卓定为反贼,袁绍定为主公,另外有两个忠臣和一个内奸,就选这三个风云人物:曹操,刘备,孙坚(孙权的爸比),内奸扮演的角色是忠臣,主公和两个忠臣不知道内奸的身份,都当作忠臣对待了。

董卓是非常强大的,拥有精良的西凉兵,麾下还有战神吕布。大家都知道三英站吕布的故事,吕布以一已之力对阵刘备、张飞、关羽三人。

要想干掉董卓,袁绍必须统一忠臣的作战计划,三位忠臣还不知道有什么其他花花肠子,有一个还是内奸。如果内奸暗通反贼董卓,给忠臣发送误导性的作战信息,该怎么办?另外假定这几个忠臣都是通过书信交流作战信息,如果书信被拦截了或书信里面的信息被替换了咋办?这些场景都可能扰乱作战计划,最后出现有的忠臣在进攻,有的忠臣撤退了。那么反贼就可以乘此机会发起进攻,逐一攻破。

袁绍本来就没有曹操的机智,那他如何让忠臣们达成共识,制定统一的作战计划呢?

上面的映射关系就是一个拜占庭将军问题的一个简化表述,袁绍现在面临的就是典型的共识问题。也就是在可能有误导信息的情况下,采用合适的通讯机制,让多个将军达成共识,制定一致性的作战计划。

2.3 一方选择撤退

刘备、曹操、孙坚通过信使传递进攻或撤退的信息,然后进行协商,到底是进攻还是撤退。遵循少数服从多数,不允许弃权。

曹操疑心比较重,侦查了反贼的地形后,决定撤退。而刘备和孙坚决定进攻。

刘备决定进攻,通过信使告诉曹操和孙坚进攻。

曹操决定撤退,通过信使告诉刘备和孙坚撤退。

孙坚决定进攻,通过信使告诉曹操和刘备进攻。

一方选择撤退

曹操收到的信息:进攻 2 票,自己的一张撤退票,票数一比,进攻票:撤退票 = 2 : 1,按照上面的少数服从多数原则进行投票表决,曹操还是会进攻。那么三方的作战方案都是进攻,所以是一个一致性的作战方案。最后战胜了董卓。

2.4 内奸登场-撤退

因为我们前期的设定,孙坚作为内奸,早已与反贼董卓私下沟通好了,不攻打董卓。

曹操决定撤退,通过信使告诉曹操和孙坚撤退。

孙坚决定撤退,通过信使告诉曹操和刘备撤退。

内奸登场-撤退

刘备收到进攻和撤退各一票,而自己又选择撤退,所以刘备得到的票数是:进攻 : 撤退 = 1 : 2,遵从少数服从多数的原则,刘备选择最后选择撤退,那么三方的作战方案都是撤退,所以也是一个一致性的作战方案。

2.5 内奸使诈-一进一退

内奸看了上述计划,发现忠臣都撤退了,并没有被消灭,就想通过使诈的方式来消灭其中一个忠臣。

孙坚作为内奸使诈,通过信使告诉刘备进攻,告诉曹操撤退。

内奸使诈-一进一退

那么结果是什么呢?

刘备的票数为进攻 2 票,撤退 1 票,曹操的票数为进攻 1 票,撤退 2 票。按照少数服从多数的原则,刘备最后会选择进攻,而曹操会选择撤退,孙坚作为内奸肯定不会进攻,刘备单独进攻反贼董卓,势单力薄,被董卓干掉了。

从这个场景中,我们看到内奸孙坚通过发送误导信息,非常容易地就干扰了刘备和曹操的作战计划,导致两位忠臣被逐一击破。这个现象就是二忠一判难题。那么主公袁绍该怎么解决这个问题?

解法一原理

就是将袁绍也参与进来进行投票,这样就‍‍‍‍‍‍‍‍‍‍增加了一位忠臣的数量‍‍‍‍‍‍‍‍‍‍。三个忠臣一个叛贼。然后 4 位将军做了一个约定,如果没有收到命令,则执行默认命令,比如撤退。另外约定流程来发送作战信息和如何执行作战指令。这个解法的关键点就是执行两轮作战信息协商。

3.1 袁绍作为指挥官

我们来看下第一轮是怎么做的。

先发送作战信息的将军我们把他称为指挥官(袁绍),另外的将军我们称作副官(刘备,曹操,孙坚)。

指挥官将他的作战信息发送给所有的副官。

每一位副官将从指挥官处收到的作战信息,作为自己的作战指令;假如没有收到指挥官的作战信息,将把默认的撤退作为作战指令。

我们用图来演示:袁绍作为主公先发送作战信息,作战指令为进攻。然后曹操、刘备、孙坚收到进攻的作战指令。

第一轮

再来看下第二轮是怎么做的。

第一轮指挥官(袁绍)已经发送指令了,现在就需要刘备、曹操、孙坚依次作为指挥官给其他两位副将发送作战信息。

然后这三位副将按照少数服从多数的原则,执行收到的作战指令。

孙坚使诈 - 两撤退

如果孙坚使诈,比如给曹操和刘备都发送撤退信息,如下图所示。那么刘备和曹操收到的作战信息为 进攻 2 票,撤退 1 票,按照少数服从多数的原则,最后刘备和曹操执行进攻,实现了作战计划的一致性,曹操和刘备联合作战击败了反贼董卓(即使孙坚没有参加作战。)

孙坚使诈 - 一进一退

假如孙坚使诈,给曹操发送撤退指令,给刘备发送进攻指令,那么刘备收到的作战信息是进攻 3 票,肯定会发起进攻了,而曹操收到的作战信息是进攻 2 票,撤退 1 票,最后曹操还是会进攻,所以刘备和曹操还是联合作战击败了反贼董卓。

如此看来,引入了一位指挥官后,确实可以避免孙坚使诈,但如果是孙坚在第一轮作为指挥官,其他人作为副官呢?

3.2 孙坚作为指挥官

第一轮孙坚向其中一个副官袁绍发送撤退指令,向另外两个副官曹操、刘备发送进攻指令。那么第一轮的结果如下图:

第二轮孙坚休息,其他副官按照孙坚发送的指令开始向另外的副官发送指令。

曹操向刘备和袁绍发送进攻指令。

刘备向曹操和袁绍发送进攻指令。

袁绍向曹操和刘备发送撤退指令。

如下图所示,最后曹操、刘备、袁绍收到的指令为进攻 2 票,撤退 1 票,按照少数服从多数原则,三个人都是发起进攻。执行了一致的作战计划,保证作战的胜利。

第二轮

3.3 小结

通过上面的演示,我们知道了如何解决拜占庭将军问题。其实兰伯特在他的论文中也提到过如何解决。

如果叛将人数为 m,将军数 n >= 3m + 1,那么就可以解决拜占庭将军问题。

前提条件:叛将数 m 一致,需要进行 m + 1 轮的作战协商。

这个公式,大家只需要记住就可以了,推到过程可以参考论文。

比如上述的攻打董卓问题,曹操、刘备、孙坚三个人当中,孙坚是叛将,他可以使诈,使作战计划不统一。必须增加一位忠臣袁绍来协商共识,才能达成一致性作战计划。

拜占庭解法二——签名

那可以在不增加忠臣的情况下,解决拜占庭的二忠一判问题吗?

解法二就是通过签名消息。比如将军之间通过印章、虎符等信物进行通信。来保证这几个特征:

签名无法伪造,对签名消息的内容进行任何更改都会被发现。

任何人都能验证将军签名的真伪。

限于篇幅原因,签名的演示这里就不做展开了。

通过《三国杀》角色来讲解分布式中共识场景。那他们和分布式系统的映射关系是怎么样的呢?

将军对应计算机节点。

忠臣的将军对应正常运行的计算机节点。

叛变的将军对应出现故障并会发送误导信息的计算机节点。

信使被杀对应通讯故障、信息丢失。

信使被间谍替换对应为通讯被恶意攻击、伪造信息或劫持通讯。

可不要小瞧拜占庭问题,它可是分布式场景最复杂的的故障场景。比如在数字货币的区块链技术中就有用到这些知识点。而且必须使用拜占庭容错算法(也就是 Byzantine Fault Tolerance,BFT)。

拜占庭容错算法还有 FBFT 算法,PoW 算法,当然不会在这篇中去讲这些算法,后续再讲解。一口吃不了大胖子~

有了拜占庭容错算法,肯定有非拜占庭容错算法,顾名思义,就是没有发送误导信息的节点。CFT 算法就是解决分布式系统中存在故障,但不存在恶意节点的场景下的共识问题。简单来说就是可能因系统故障造成丢失消息或消息重复,但不存在错误消息、伪造消息。对应的算法有 Paxos 算法、Raft 算法、ZAB 协议。后续讲解~上面提到了 5 种算法,居然都是跟拜占庭问题有关,你说今天讲的拜占庭问题重要不重要?

这么多算法该如何选择?

节点可信,选非拜占庭容错算法。否则就用拜占庭容错算法,如区块链中用到的 PoW 算法。

如果叛将人数为 m,将军数 n >= 3m + 1,那么就可以解决拜占庭将军问题。

ZEC跌破68美元关口:火币全球站数据显示,ZEC短线下跌,跌破68美元关口,现报67.95美元,日内涨幅达到0.53%,行情波动较大,请做好风险控制。[2020/11/23 21:44:47]

观点:中央“新西部大开发”文件出台 利好加密货币挖矿:5月17日,中共中央、国务院发布《新时代推进西部大开发形成新格局的指导意见》。西部主要包括四川、云南、广西、重庆、新疆、内蒙古、甘肃等省市自治区。其中四川、内蒙、新疆、云南也是加密货币矿场主要分布的省份。这份指导意见中关于能源的论述,将有利于地方政府更好地支持加密货币挖矿行业的发展。对于中国加密货币交易所、公链、金融机构而言,合规或许是最大障碍。但对于加密挖矿来说,合规已经不成为最大阻碍。最大的问题还是减半后币价并没有明显上升。今年丰水期第一次出现了矿场电力严重过剩、矿机开机不足的现象,行业的萎缩与洗牌或近在眼前。(吴说区块链)[2020/5/18]

ZBG Super Launchpad第五期项目KLB开盘最高涨幅超180%:据ZBG官网消息,ZBG Super Launchpad第五期项目—KLB已于5月13日16:00开放交易;开盘30分钟内涨幅超180%,申购价格0.014udst,最高价格0.04usdt。 \nSuper Launchpad是人人参与既有所得的全新模式;实际获得代币=(个人申购金额/全网总申购金额)X 代币销售总量。在ZBG实盘交易合约可获得10%的额外额度。 \n据悉,首期Super Launchpad项目(CRD)开盘30分钟涨幅超1600%,截止发稿涨幅超2699%。详情查看ZBG官网公告。[2020/5/13]

标签:

区块链热门资讯
DCEP≠区块链 别再误读了

2020年,全球央行数字货币发展驶入快车道。 央行数字货币的诞生极大的满足了人类社会日益发展的交易需求,不仅使交易更加便利,而且还极大的节约了制造成本,与此同时,科技力量的加持也使得数字货币有效防伪防丢。

2020/12/12 20:20:58
金色观察 | DeFi卷土重来 这次带来了应用场景

2020年,DeFi、流动性挖矿已经成为整个区块链行业最具有吸引力的故事。 无论是YFI在40天内暴涨一万倍的奇迹,还是Sushiswap的上演的流动性争夺战,亦或是后来Uniswap人均2000美元的空投,无不吸引着一大批投资者参与其中。输送了一个又一个的暴富故事,让 DeFi 圈子近乎疯狂。

2020/12/12 20:20:53
星展银行正式推出全方位数字交易平台

【新加坡2020年12月10日讯】今日,星展银行宣布正式推出数字交易平台,为机构客户和合格投资者打造全面的数字资产代币化、交易和托管生态系统。

2020/12/12 20:20:36
Token:区块链价值海洋里的一叶轻舟

区块链曾被《经济学人》喻为“信用的机器”,它真正解决的是数字世界的信任问题。那其究竟是通过什么方式解决信任问题,并让信任得以高效流通?答案很简单,那就是Token。 ❶ 什么是Token? Token,中文被译为“令牌”或“通证”,本质上是一种数字化可流动的价值载体,即权益证明。

2020/12/12 20:20:31
金色百科 | NFT是什么?一篇文章搞懂NFT的概念

NFT英文全称为Non-Fungible Token,翻译成中文就是:非同质化代币,具有不可分割、不可替代、独一无二等特点。 在区块链上,数字加密货币分为原生币和代币两大类。前者如BTC、ETH等,拥有自己的主链,使用链上的交易来维护账本数据;代币则是依附于现有的区块链,使用智能合约来进行账本的记录,如依附于以太坊上而发布的token。

2020/12/12 20:20:27
OKX