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

前言

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

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

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

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

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

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

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

1.学习路线

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

四大基础理论：

1. 拜占庭将军问题

2. CAP 理论

3. ACID 理论

4. BASE 理论

八大分布式协议和算法：

1. Paxos 算法

2. Raft 算法

3. 一致性 Hash 算法

4. Gossip 协议算法

5. Quorum NWR 算法

6. FBFT 算法

7. POW 算法

8. 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 票。按照少数服从多数的原则， 刘备最后会选择进攻，而曹操会选择撤退，孙坚作为内奸肯定不会进攻，刘备单独进攻反贼董卓，势单力薄，被董卓干掉了。

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

3.拜占庭问题解法

解法一原理

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

3.1 袁绍作为指挥官

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

1. 先发送作战信息的将军我们把他称为指挥官（袁绍），另外的将军我们称作副官（刘备，曹操，孙坚）。

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

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

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

第一轮

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

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

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

孙坚使诈 - 两撤退

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

孙坚使诈 - 两撤退

孙坚使诈 - 一进一退

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

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

孙坚使诈 - 一进一退

3.2 孙坚作为指挥官

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

第一轮

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

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

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

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

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

第二轮

3.3 小结

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

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

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

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

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

拜占庭解法二——签名

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

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

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

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

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

总结

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

• 将军对应计算机节点。

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

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

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

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

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

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

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

这么多算法该如何选择？

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