前言《三国杀》是一款流行的卡牌游戏，结合中国三国时期的背景，以身份为线索，以卡牌、益智、休闲等形式，老少皆宜。东汉末年，袁绍作为盟主，召集十八位诸侯讨伐董卓。在讲解之前，先说一下分布式协议和算法的整体脉络。现在很多开发同学对如何使用分布式组件都有一定的经验，也知道CAP理论和BASE理论的大概意思。但是认真看分布式算法的人真的很少。原因有三：他们担心算法太复杂，所以用的时间很少。网上的资料可以用大白话把分布式算法解释清楚。学习分布式算法没有明确的途径。在后续的文章中，我会用故事和通俗易懂的语言来讲解分布式算法的原理和学习路线是怎样的。学习路线学习分布式协议和算法的路线可以是先学习四大基础理论作为基础，然后再学习分布式协议和算法，就像在地基上盖房子一样。只有打好地基，才能盖起更稳固的高楼。四大基本理论拜占庭将军问题CAP理论ACID理论BASE理论八种分布式协议和算法Paxos算法Raft算法共识Hash算法Gossip协议算法QuorumNWR算法FBFT算法POW算法ZAB协议由于篇幅原因，本文只涉及拜占庭将军问题。拜占庭将军问题您可能听说过拜占庭将军问题。它是由莱斯利·兰伯特(LeslieLambert)提出的，是拜占庭点对点通信中的一个基本问题，拜占庭是东罗马帝国的首都，位于现在的土耳其伊斯坦布尔。由于当时的拜占庭罗马帝国幅员辽阔，为了达到防御的目的，各支军队都隔得很远，将军们只能靠使者传递消息。战争期间，拜占庭军队中的所有将军和副官必须达成共识，决定自己是否有胜算，然后才能进攻敌方阵营。但是，军队中可能会有叛徒和敌方间谍。这就是拜占庭容错问题。事实上，拜占庭问题是分布式领域中最复杂的容错模型。一旦理解了它，就可以掌握分布式共识问题的解决方案。它还可以帮助您了解常用的共识算法，并帮助我们在工作中选择合适的算法。算法，或者设计一个合适的算法。为什么第一个基础理论是拜占庭将军问题？因为它很好地抽象了分布式系统面临的共识问题。上面提到的八种分布式算法中有五种与拜占庭问题有关。可以说，理解了拜占庭问题，对于后面学习其他算法来说会容易很多。接下来我就用三国杀游戏中的身份卡来解释一下拜占庭将军问题。《三国杀》中主要有四个身份：领主、忠臣、逆贼、知情人。每个游戏玩家都会收到一个身份徽章。主角只有1个。忠臣最多2人，叛逆者最多4人，奸臣最多1人。主公主身份卡获胜条件：消灭一切内奸和内奸技能：以自己的生存为首要目标，分散内奸的注意力。配合中内消灭叛军，判断谁忠心谁内幕。忠仆、忠仆身份证获得条件：在保护领主生存的前提下，消灭一切叛徒和内奸。技能：忠臣是君主的屏障，震慑叛逆的天平。防贼防贼身份卡获胜条件：消灭领主获胜。技能：叛军是数量最多的身份，他们需要集中火力攻击敌人的弱点。正确的思维是取胜的关键。汉奸身份证获得条件：先消灭汉奸忠臣，最后与领主单挑成为最后的幸存者。技能：正确的战术+冷静的头脑+运气。恢复拜占庭问题东汉末年，袁绍作为盟主，召集十八位诸侯讨伐董卓。定董卓为汉奸，袁绍为主，有两个忠臣一个汉奸，选择这三个有影响力的人物：曹操，刘备，孙坚（孙权的父亲），汉奸扮演忠臣大臣、君主和奸臣这两个忠臣不知道奸臣的身份，所以被当作忠臣对待。董卓非常强大，手下有优秀的西凉兵，还有战神吕布。吕布三营台的故事大家都知道。吕布以一己之力面对刘备、张飞、关羽。为了杀死董卓，袁绍必须统一忠臣的作战计划。三个忠臣不知道还有什么花招，其中一个还是内奸。如果汉奸暗中告密汉奸董卓，向忠臣发送误导性的作战信息怎么办？另外，假设这些忠臣之间通过信件来交流战斗信息，万一信件被截获或者信件中的信息被替换了怎么办？?这些场面可能会打乱作战计划，最后有的忠臣在进攻，有的忠臣在撤退。那么叛军就可以趁机发动进攻，一个一个突围。袁绍没有曹操的机智，如何让忠臣们达成共识，制定统一的作战计划呢？上面的映射关系是一个拜占庭将军问题的简化表述，而袁绍现在面临的就是一个典型的共识问题。即在可能出现误导信息的情况下，利用适当的沟通机制，让多个将领达成共识，制定一致的作战计划。一方选择退却。刘备、曹操、孙坚通过使者传出进攻或撤退的消息，然后商议进攻或撤退。服从少数，服从多数，不得弃权。曹操疑心重重，勘察了叛军的地形后决定撤退。而刘备和孙坚决定进攻。刘备决定进攻，并通过使者告诉曹操和孙坚进攻。曹操决定撤退，通过使者通知刘备和孙坚撤退。孙坚决定进攻，并通过使者告诉曹操和刘备进攻。一方选择撤退时曹操得到的信息：进攻2票，己方1票撤退，比较票数，进攻票：撤退票=2：1，按照以上原则投票少数服从多数，曹操还是要进攻。那么三方的作战计划都是进攻性的，所以是一致的作战计划。最后打败了董卓。汉奸登场——撤退因为我们之前的设定，作为汉奸的孙坚已经和汉奸董卓私下沟通过，不会对董卓下手。刘备决定进攻，并通过使者告诉曹操和孙坚进攻。曹操决定撤退，通过使者通知曹操和孙坚撤退。孙坚决定撤退，通过使者通知曹操和刘备撤退。内线出场-退刘备攻退各得一票，他选择退，所以刘备得票数为：攻：退=1：2，遵循少数服从多数的原则，刘备最后选择了撤退，那么三方的作战计划都是撤退，所以也是一致的作战计划。奸臣诡计——一进一退奸臣看了上面的方案，发现忠臣都退了，并没有被消灭，于是想用诡计除掉其中一个忠臣。刘备决定进攻，并通过使者告诉曹操和孙坚进攻。曹操决定撤退，通过使者通知曹操和孙坚撤退。孙坚作为知情人，通过使者通知刘备进攻，曹操撤退。内奸与欺骗——一进一退那么结果如何呢？刘备攻2票退1票，曹操攻1票退2票。按照少数服从多数的原则，最终刘备会选择进攻，而曹操则会选择撤退。孙坚绝对不会内线进攻。从这一幕我们可以看出，奸臣孙坚通过误传，非常轻易地干扰了刘备和曹操的作战计划，致使两位忠臣一一败下阵来。这种现象就是二忠一判断的问题。那么袁绍大人应该如何解决这个问题呢？解决拜占庭问题的原则是让袁绍参与投票，从而增加忠臣的数量。三忠臣一奸。然后4位将军约定，如果没有接到命令，就执行默认的命令，比如撤退。此外，还约定了一个进程来发送战斗信息以及如何执行战斗指令。该方案的关键在于执行两轮作战信息协商。让我们看看第一轮是如何进行的。第一步：最先发出作战信息的将领称为统帅（袁绍），其他将领称为副将（刘备、曹操、孙坚）。步骤2：指挥官将他的战斗信息发送给所有副官。第三步：每个副官将从指挥官那里得到的作战信息作为自己的作战指令；如果他没有收到指挥官的战斗信息，他将使用默认撤退作为他的战斗命令。我们用一张图来演示一下：袁绍作为主公，先下达作战信息，作战命令是进攻。曹操、刘备、孙坚奉命进攻。让我们看看第一轮发生了什么。第一局统帅（袁绍）已经下令，现在需要刘备、曹操、孙坚轮流担任统帅，向另外两位副将传送作战信息。随后三名中尉本着少数服从多数的原则，执行接到的作战命令。孙坚的诡计——两次撤退以孙坚诡诈为例，给曹操和刘备都发一个撤退的信息，如下图。随后刘备和曹操获得2票进攻，1票撤退。按照少数服从多数的原则，刘备和曹操最终实施了进攻，实现了作战计划的一致性。曹操和刘备联手打败了叛军董卓（即使孙坚没有参战。）而刘备一个进攻命令，那么刘备得到的作战信息是3票进攻，肯定会发动进攻，而曹操得到的作战信息是2票进攻，1票退却。最终曹操还是会进攻，所以刘备和曹操还是联手打败了奸臣董卓。从这一点来看，引入一个统帅之后，确实是可以避免孙坚的欺骗，但是如果孙坚是第一轮的统帅，其他人都是副官呢？孙坚的诡计——一进一退。在一个回合中，孙坚向他的一名副官袁绍发出了撤退命令，并向另外两名副官曹操和刘备发出了进攻命令。那么第一回合的结果如下：第一回合和第二回合，孙坚休息，其他副官开始按照孙坚发出的指令给其他副官下达指令。曹操向刘备、袁绍下令进攻。刘备下令进攻曹操和袁绍。袁绍向曹操、刘备下令撤退。如下图，最后曹操、刘备、袁绍接到指令，攻2票退1票。按照少数服从多数的原则，三人同时发起进攻。实施了一致的作战计划，确保了战斗的胜利。第二轮总结通过上面的演示，我们知道了如何解决拜占庭将军问题。事实上，兰伯特在他的论文中也提到了如何解决它。如果叛徒数量为m，将军数量n>=3m+1，那么拜占庭将军问题就可以解决。前提条件：叛军数量m相同，需要进行m+1轮战斗谈判。你只需要记住这个公式，过程可以参考论文。比如上述讨伐董卓的问题，在曹操、刘备、孙坚中，孙坚是叛将，可以作弊，使作战计划不一致。必须加一个忠臣袁绍，协商一致，才能达成一致的作战计划。拜占庭方案二——签名拜占庭如何在不增加忠臣的情况下解决二忠一判的问题？第二种解决方案是对消息进行签名。例如，将军通过印章和虎符等信物进行交流。为保证这些特性：签名不可伪造，签名消息内容的任何更改都会被发现。任何人都可以验证将军签名的真实性。限于篇幅，这里不再展开签名演示。有兴趣的@我，稍后再补充。综上所述，通过三国杀手的角色来说明分布式共识场景。那么它们与分布式系统的映射关系是怎样的呢？一般对应于计算机节点。忠诚的将军对应于正常运行的计算机节点。叛将对应于出现故障并发送误导信息的计算机节点。对应通讯失败，信息丢失，快递员被杀。被间谍取代的信使对应于被恶意攻击、伪造或劫持的通信。不要小看拜占庭问题，它是分布式场景中最复杂的故障场景。例如，这些知识点在数字货币的区块链技术中是有用的。并且必须使用拜占庭容错算法（即拜占庭容错，BFT）。拜占庭容错算法还包括FBFT算法和PoW算法。当然，这些算法本文不做讨论，后面会有说明。一口饭吃不下的大胖子~有了拜占庭容错算法，就必然有非拜占庭容错算法。顾名思义，没有发送误导信息的节点。CFT算法是为了解决分布式系统存在故障但不存在恶意节点场景下的共识问题。简单来说，就是系统故障可能导致消息丢失或重复，但不会有错误消息或假消息。对应的算法有Paxos算法、Raft算法、ZAB协议。后续解释~上面提到的5种算法其实都和拜占庭问题有关。你觉得今天说的拜占庭问题重要吗？这么多算法怎么选择？节点可信，选用非拜占庭容错算法。否则，使用拜占庭容错算法，例如区块链中使用的PoW算法。本文转载自微信公众号“悟空聊天结构”，可通过以下二维码关注。转载本文请联系悟空聊天架构公众号。
