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

古城微笑少年丶 2022-12-28 01:51 102阅读 0赞

点击上方“**五分钟学算法**”，选择“星标”公众号

重磅干货，第一时间送达![format_png][]

![format_png 1][]

来源 | 悟空聊架构（ID：PassJava666）

##  ##

## **前言**    ##

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

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

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

*  担心算法过于复杂，所以花的时间很少。
 *  网上的资料能用大白话将分布式算法讲清楚的比较少。
 *  学习分布式算法没有一条清晰的路线。

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

## **学习路线**    ##

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

### **四大基础理论：** ###

1.  拜占庭将军问题
2.  CAP 理论
3.  ACID 理论
4.  BASE 理论

### **八大分布式协议和算法：** ###

1.  Paxos 算法
2.  Raft 算法
3.  一致性 Hash 算法
4.  Gossip 协议算法
5.  Quorum NWR 算法
6.  FBFT 算法
7.  POW 算法
8.  ZAB 协议

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

## **拜占庭将军问题**    ##

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

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

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

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

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

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

## **2.1 三国杀身份牌** ##

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

### **主公** ###

![format_png 2][]

主公身份牌

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

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

### **忠臣** ###

![format_png 3][]

忠臣身份牌

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

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

### **反贼** ###

![format_png 4][]

反贼身份牌

**获胜条件：消灭主公即可获胜。**

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

### **内奸** ###

![format_png 5][]

内奸身份牌

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

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

## **2.2 还原拜占庭问题**    ##

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

![format_png 6][]

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

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

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

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

## **2.3 一方选择撤退** ##

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

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

*  刘备决定进攻，通过信使告诉曹操和孙坚进攻。
 *  曹操决定撤退，通过信使告诉刘备和孙坚撤退。
 *  孙坚决定进攻，通过信使告诉曹操和刘备进攻。

![format_png 7][]

一方选择撤退

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

## **2.4 内奸登场-撤退** ##

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

*  刘备决定进攻，通过信使告诉曹操和孙坚进攻。
 *  曹操决定撤退，通过信使告诉曹操和孙坚撤退。
 *  孙坚决定撤退，通过信使告诉曹操和刘备撤退。

![format_png 8][]

内奸登场-撤退

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

## **2.5 内奸使诈-一进一退** ##

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

*  刘备决定进攻，通过信使告诉曹操和孙坚进攻。
 *  曹操决定撤退，通过信使告诉曹操和孙坚撤退。
 *  孙坚作为内奸使诈，通过信使告诉刘备进攻，告诉曹操撤退。

![format_png 9][]

内奸使诈-一进一退

那么结果是什么呢？

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

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

##     ##

## **拜占庭问题解法**    ##

### **解法一原理** ###

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

**3.1 袁绍作为指挥官**

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

1.  先发送作战信息的将军我们把他称为指挥官（袁绍），另外的将军我们称作副官（刘备，曹操，孙坚）。
2.  指挥官将他的作战信息发送给所有的副官。
3.  **每一位副官将从指挥官处收到的作战信息，作为自己的作战指令；假如没有收到指挥官的作战信息，将把默认的撤退作为作战指令。**

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

![format_png 10][]

第一轮

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

1.  第一轮指挥官（袁绍）已经发送指令了，现在就需要刘备、曹操、孙坚依次作为指挥官给其他两位副将发送作战信息。
2.  然后这三位副将按照少数服从多数的原则，执行收到的作战指令。

### **孙坚使诈 - 两撤退** ###

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

![format_png 11][]

孙坚使诈 - 两撤退

### **孙坚使诈 - 一进一退** ###

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

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

![format_png 12][]

孙坚使诈 - 一进一退

### **3.2 孙坚作为指挥官** ###

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

![format_png 13][]

第一轮

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

1.  曹操向刘备和袁绍发送进攻指令。
2.  刘备向曹操和袁绍发送进攻指令。
3.  袁绍向曹操和刘备发送撤退指令。

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

![format_png 14][]

第二轮

### **3.3 小结** ###

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

> 如果叛将人数为 m，将军数 n >= 3m + 1，那么就可以解决拜占庭将军问题。
> 
> 前提条件：叛将数 m 一致，需要进行 m + 1 轮的作战协商。

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

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

## **拜占庭解法二——签名** ##

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

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

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

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

##     ##

## **总结**    ##

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

*  将军对应计算机节点。
 *  忠臣的将军对应正常运行的计算机节点。
 *  叛变的将军对应出现故障并会发送误导信息的计算机节点。
 *  信使被杀对应通讯故障、信息丢失。
 *  信使被间谍替换对应为通讯被恶意攻击、伪造信息或劫持通讯。

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

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

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

这么多算法该如何选择？

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

[format_png]: /images/20221120/01a45e7ba13141daacc3b190a424895c.png
[format_png 1]: /images/20221120/181436a2d1e843b08acc313799716bb0.png
[format_png 2]: /images/20221120/7813fd4658a24ab9989acc76887d69af.png
[format_png 3]: /images/20221120/f3565b4ccde24fb7b7d1a77d6f3fe418.png
[format_png 4]: /images/20221120/cb591cf5fb6d4f09989d004558ddf054.png
[format_png 5]: /images/20221120/1f0254fb6c4144c392c34e625b6d2e82.png
[format_png 6]: /images/20221120/9758e3a7fc3d4347bbeb90a7ec781d1e.png
[format_png 7]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9TZkFITXVVeHFKM0Vwb25KVXZlY1FnMGdRMFptY3BnelFVTlBNTW5xMk1PSU1pYUhDZEQ2VUFqbDg5YW10VVRjVDByQ1p6SEJaYWd1V2ExNmJ6dDdOc2cvNjQw?x-oss-process=image/format,png
[format_png 8]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9TZkFITXVVeHFKM0Vwb25KVXZlY1FnMGdRMFptY3BnekUzdkRzN25ocEFNZlZjS2ljWjQyUE5NQ2FaY3ZaemljaWEzSjNwMXVhZmEyWGJZMG1TVU12OHZnZy82NDA?x-oss-process=image/format,png
[format_png 9]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9TZkFITXVVeHFKM0Vwb25KVXZlY1FnMGdRMFptY3BnemE0QnloRThLcEU5SUkxM25jR1FHQ0hIbFh0MTJpY2g4SUlSd09nUGNTcUtITG1NcFVMMzJlWncvNjQw?x-oss-process=image/format,png
[format_png 10]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9TZkFITXVVeHFKM0Vwb25KVXZlY1FnMGdRMFptY3BnekU0em5rZFppYWljZ21GMmF6NFhEQm4zS0xSdzJnV3VpYWNibnVJaWNrVjlyRDExcUpZUWljNkNUbkpnLzY0MA?x-oss-process=image/format,png
[format_png 11]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9TZkFITXVVeHFKM0Vwb25KVXZlY1FnMGdRMFptY3BnemljZTlQZElOSW0wSFA2bWNTUjNYRE1LRjRMU2liRDhQT3pXeGhaaGhwaWFlZmhQQXE2bnRvQnU3QS82NDA?x-oss-process=image/format,png
[format_png 12]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9TZkFITXVVeHFKM0Vwb25KVXZlY1FnMGdRMFptY3Bnem9IbTZEZTB6dFVPcDdiY0c5WmY4T3FTcHNDYlNvb0ZTWFRvOTBOdFdlM0dPM1EyR2N3M3FhQS82NDA?x-oss-process=image/format,png
[format_png 13]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9TZkFITXVVeHFKM0Vwb25KVXZlY1FnMGdRMFptY3BnemtlVjZjRjM0WWdGMWdtNk9TcVpscWd2M3BWS0JlU2tXckJGalNpYjZXc3ZpYWVPYjZMbkNEaWJTdy82NDA?x-oss-process=image/format,png
[format_png 14]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9TZkFITXVVeHFKM0Vwb25KVXZlY1FnMGdRMFptY3Bnem8wYWpCTmliVVp4YXI1cVRHS253ZFFMelduaWJmY0xmd0JBTzBGbFFFVU1GZllDdFBsejNnb0FBLzY0MA?x-oss-process=image/format,png