前语

《三国杀》是一款抢手的卡牌游戏，结合我国三国时期布景，以身份为头绪，以卡牌为方法，益智休闲，雅俗共赏。

东汉末年，袁绍作为盟主，集合了十八路诸侯一同进犯董卓。

在解说之前，咱们先聊下分布式协议和算法全体头绪。

现在许多开发同学对分布式的组件怎样运用都有必定经历，也知道 CAP 理论和 BASE 理论的大致意义。但仔细去看分布式算法的真的很少，原因有三：

忧虑算法过于杂乱，所以花的时刻很少。

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

学习分布式算法没有一条明晰的道路。

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

学习道路

学习分布式协议和算法的道路可所以先学习四大基础理论，作为地基，再学习分布式协议和算法，就像是在地基上建房子。地基打好了，才干建更安定的高楼大厦。

四大基础理论

• 拜占庭将军问题
• CAP 理论
• ACID 理论
• BASE 理论

八大分布式协议和算法

• Paxos 算法
• Raft 算法
• 共同性 Hash 算法
• Gossip 协议算法
• Quorum NWR 算法
• FBFT 算法
• POW 算法
• ZAB 协议

因篇幅原因，本篇只触及拜占庭将军问题。

拜占庭将军问题

咱们或许听过拜占庭将军问题。它是由莱斯利·兰伯特提出的点对点通讯中的基本问题，

拜占庭坐落现在的土耳其的伊斯坦布尔，是东罗马帝国的首都。由于其时拜占庭罗马帝国疆土广阔，为了到达防护意图，每个戎行都分隔很远，将军与将军之间只能靠信差传音讯。在战役的时分，拜占庭戎行内一切将军和副官有必要达到共同的共同，决议是否有赢的时机才去进犯敌人的阵营。但是，在戎行内有或许存有叛徒和敌军的特务，这个便是拜占庭容错问题。

实际上拜占庭问题是分布式范畴最杂乱的一个容错模型，一旦了解它，就能把握分布式共同问题的处理思路，还能协助咱们了解常用的共同算法，也能够协助咱们在工作中挑选适宜的算法，或许规划适宜的算法。

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

由于它很好地笼统出了分布式体系面对的共同问题。 上面说到的 8 种分布式算法中有 5 种跟拜占庭问题相关，能够说弄懂拜占庭问题对后边学习其他算法就会简略许多。

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

三国杀身份牌

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

主公

主公身份牌

取胜条件： 消除一切反贼和内奸

技巧： 以自己生计为首要方针，涣散反贼注意力。合作忠内歼灭反贼并判别谁是忠谁是内。

忠臣

忠臣身份牌

取胜条件：维护主公存活的前提下消除一切反贼和内奸。

技巧：忠臣是主公的屏障，震慑反贼和内奸的天平。

反贼

反贼身份牌

取胜条件：消除主公即可取胜。

技巧： 反贼作为数量最多的身份，需求会集火力猛攻敌人缺点。正确的思路是取胜的要害。

内奸

内奸身份牌

取胜条件： 先消除反贼和忠臣，最终与主公单挑成为最终仅有生还者。

技巧：正确的战术+ 镇定的脑筋+ 命运。

复原拜占庭问题

东汉末年，袁绍作为盟主，集合了十八路诸侯一同进犯董卓。把董卓定为反贼，袁绍定为主公，别的有两个忠臣和一个内奸，就选这三个风云人物：曹操，刘备，孙坚(孙权的爸比)，内奸扮演的人物是忠臣，主公和两个忠臣不知道内奸的身份，都当作忠臣对待了。

董卓是十分强壮的，具有精巧的西凉兵，麾下还有战神吕布。咱们都知道三英站吕布的故事，吕布以一已之力对阵刘备、张飞、关羽三人。

要想干掉董卓，袁绍有必要共同忠臣的作战方案，三位忠臣还不知道有什么其他花花肠子，有一个仍是内奸。假设内奸暗通反贼董卓，给忠臣发送误导性的作战信息，该怎样办?别的假定这几个忠臣都是经过信件交流作战信息，假设信件被阻拦了或信件里边的信息被替换了咋办?这些场景都或许打乱作战方案，最终呈现有的忠臣在进攻，有的忠臣撤离了。那么反贼就能够乘此时机建议进攻，逐个攻破。

袁绍本来就没有曹操的机敏，那他怎样让忠臣们达到共同，拟定共同的作战方案呢?

上面的映射联络便是一个拜占庭将军问题的一个简化表述，袁绍现在面对的便是典型的共同问题。也便是在或许有误导信息的情况下，选用适宜的通讯机制，让多个将军达到共同，拟定共同性的作战方案。

一方挑选撤离

刘备、曹操、孙坚经过信使传递进攻或撤离的信息，然后进行洽谈，到底是进攻仍是撤离。遵照少数服从多数，不允许放弃。

曹操猜疑比较重，侦办了反贼的地势后，决议撤离。而刘备和孙坚决议进攻。

• 刘备决议进攻，经过信使告知曹操和孙坚进攻。
• 曹操决议撤离，经过信使告知刘备和孙坚撤离。
• 孙坚决议进攻，经过信使告知曹操和刘备进攻。

一方挑选撤离

曹操收到的信息：进攻 2 票，自己的一张撤离票，票数一比，进攻票：撤离票 = 2 : 1，依照上面的少数服从多数准则进行投票表决，曹操仍是会进攻。那么三方的作战方案都是进攻，所所以一个共同性的作战方案。最终战胜了董卓。

内奸上台-撤离

由于咱们前期的设定，孙坚作为内奸，早已与反贼董卓暗里交流好了，不进犯董卓。

• 刘备决议进攻，经过信使告知曹操和孙坚进攻。
• 曹操决议撤离，经过信使告知曹操和孙坚撤离。
• 孙坚决议撤离，经过信使告知曹操和刘备撤离。

内奸上台-撤离

刘备收到进攻和撤离各一票，而自己又挑选撤离，所以刘备得到的票数是：进攻 : 撤离 = 1 : 2，遵照少数服从多数的准则，刘备挑选最终挑选撤离，那么三方的作战方案都是撤离，所以也是一个共同性的作战方案。

内奸使诈-一进一退

内奸看了上述方案，发现忠臣都撤离了，并没有被消除，就想经过使诈的方法来消除其间一个忠臣。

• 刘备决议进攻，经过信使告知曹操和孙坚进攻。
• 曹操决议撤离，经过信使告知曹操和孙坚撤离。
• 孙坚作为内奸使诈，经过信使告知刘备进攻，告知曹操撤离。

内奸使诈-一进一退

那么成果是什么呢?

刘备的票数为进攻 2 票，撤离 1 票，曹操的票数为进攻 1 票，撤离 2 票。依照少数服从多数的准则，刘备最终会挑选进攻，而曹操会挑选撤离，孙坚作为内奸必定不会进攻，刘备独自进攻反贼董卓，势单力薄，被董卓干掉了。

从这个场景中，咱们看到内奸孙坚经过发送误导信息，十分简略地就搅扰了刘备和曹操的作战方案，导致两位忠臣被逐个击破。这个现象便是二忠一判难题。那么主公袁绍该怎样处理这个问题?

拜占庭问题解法

解法原理

便是将袁绍也参与进来进行投票，这样就添加了一位忠臣的数量。三个忠臣一个叛贼。然后 4 位将军做了一个约好，假设没有收到指令，则履行默许指令，比方撤离。别的约好流程来发送作战信息和怎样履行作战指令。这个解法的要害点便是履行两轮作战信息洽谈。

咱们来看下第一轮是怎样做的。

• 第一步：先发送作战信息的将军咱们把他称为指挥官(袁绍)，别的的将军咱们称作副官(刘备，曹操，孙坚)。
• 第二步：指挥官将他的作战信息发送给一切的副官。
• 第三步：每一位副官将从指挥官处收到的作战信息，作为自己的作战指令;假设没有收到指挥官的作战信息，将把默许的撤离作为作战指令。

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

第一轮

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

• 第一轮指挥官(袁绍)现已发送指令了，现在就需求刘备、曹操、孙坚顺次作为指挥官给其他两位副将发送作战信息。
• 然后这三位副将依照少数服从多数的准则，履行收到的作战指令。

孙坚使诈 - 两撤离

假设孙坚使诈，比方给曹操和刘备都发送撤离信息，如下图所示。那么刘备和曹操收到的作战信息为 进攻 2票，撤离 1 票，依照少数服从多数的准则，最终刘备和曹操履行进攻，完成了作战方案的共同性，曹操和刘备联合作战打败了反贼董卓(即便孙坚没有参与作战。)

孙坚使诈 - 两撤离

孙坚使诈 - 一进一退

假设孙坚使诈，给曹操发送撤离指令，给刘备发送进攻指令，那么刘备收到的作战信息是进攻 3票，必定会建议进攻了，而曹操收到的作战信息是进攻 2 票，撤离 1 票，最终曹操仍是会进攻，所以刘备和曹操仍是联合作战打败了反贼董卓。

如此看来，引入了一位指挥官后，的确能够防止孙坚使诈，但假设是孙坚在第一轮作为指挥官，其他人作为副官呢?

孙坚使诈 - 一进一退

孙坚作为指挥官

第一轮孙坚向其间一个副官袁绍发送撤离指令，向别的两个副官曹操、刘备发送进攻指令。那么第一轮的成果如下图：

第一轮

第二轮孙坚歇息，其他副官依照孙坚发送的指令开端向别的的副官发送指令。

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

如下图所示，最终曹操、刘备、袁绍收到的指令为进攻 2 票，撤离 1 票，依照少数服从多数准则，三个人都是建议进攻。履行了共同的作战方案，确保作战的成功。

第二轮

小结

经过上面的演示，咱们知道了怎样处理拜占庭将军问题。其实兰伯特在他的论文中也说到过怎样处理。

假设叛将人数为 m，将军数 n >= 3m + 1，那么就能够处理拜占庭将军问题。

前提条件：叛将数 m 共同，需求进行 m + 1 轮的作战洽谈。

这个公式，咱们只需求记住就能够了，推到进程能够参阅论文。

比方上述的进犯董卓问题，曹操、刘备、孙坚三个人傍边，孙坚是叛将，他能够使诈，使作战方案不共同。有必要添加一位忠臣袁绍来洽谈共同，才干达到共同性作战方案。

拜占庭解法二-签名

那能够在不添加忠臣的情况下，处理拜占庭的二忠一判问题呢?

解法二便是经过签名音讯。比方将军之间经过印章、虎符等信物进行通讯。来确保这几个特征：

• 签名无法假造，对签名音讯的内容进行任何更改都会被发现。
• 任何人都能验证将军签名的真伪。

限于篇幅原因，签名的演示这儿就不做展开了，感兴趣的@我，后续会加上。

总结

经过三国杀人物来解说分布式中共同场景。那他们和分布式体系的映射联络是怎样样的呢?

• 将军对应计算机节点。
• 忠臣的将军对应正常运转的计算机节点。
• 反叛的将军对应呈现毛病并会发送误导信息的计算机节点。
• 信使被杀对应通讯毛病、信息丢掉。
• 信使被特务替换对应为通讯被歹意进犯、假造信息或绑架通讯。

可不要小瞧拜占庭问题，它但是分布式场景最杂乱的的毛病场景。比方在数字钱银的区块链技能中就有用到这些知识点。并且有必要运用拜占庭容错算法(也便是 Byzantine Fault Tolerance，BFT)。

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

有了拜占庭容错算法，必定有非拜占庭容错算法，望文生义，便是没有发送误导信息的节点。CFT 算法便是处理分布式体系中存在毛病，但不存在歹意节点的场景下的共同问题。简略来说便是或许因体系毛病形成丢掉音讯或音讯重复，但不存在过错音讯、假造音讯。对应的算法有 Paxos 算法、Raft 算法、ZAB 协议。后续解说~

上面说到了 5 种算法，竟然都是跟拜占庭问题有关，你说今日讲的拜占庭问题重要不重要?

这么多算法该怎样挑选?

节点可信，选非拜占庭容错算法。不然就用拜占庭容错算法，如区块链顶用到的 PoW 算法。

本文转载自微信大众号「悟空聊架构」，能够经过以下二维码重视。转载本文请联络悟空聊架构大众号。