前言 《三国杀》是一款热门的卡牌游戏,结合中国三国时期背景,以身份为线索,以卡牌为形式,益智休闲,老少皆宜。 在讲解之前,我们先聊下分布式协议和算法整体脉络。 现在很多开发同学对分布式的组件怎么使用都有一定经验,也知道 CAP 理论和 BASE 理论的大致含义。但认真去看分布式算法的真的很少,原因有三: 担心算法过于复杂,所以花的时间很少。 学习路线 学习分布式协议和算法的路线可以是先学习四大基础理论,作为地基,再学习分布式协议和算法,就像是在地基上建房子。地基打好了,才能建更稳固的高楼大厦。 四大基础理论 拜占庭将军问题 大家可能听过拜占庭将军问题。它是由莱斯利·兰伯特提出的点对点通信中的基本问题, 拜占庭位于如今的土耳其的伊斯坦布尔,是东罗马帝国的首都。由于当时拜占庭罗马帝国国土辽阔,为了达到防御目的,每个军队都分隔很远,将军与将军之间只能靠信差传消息。在战争的时候,拜占庭军队内所有将军和副官必须达成一致的共识,决定是否有赢的机会才去攻打敌人的阵营。但是,在军队内有可能存有叛徒和敌军的间谍,这个就是拜占庭容错问题。 实际上拜占庭问题是分布式领域最复杂的一个容错模型,一旦理解它,就能掌握分布式共识问题的解决思路,还能帮助大家理解常用的共识算法,也可以帮助我们在工作中选择合适的算法,或者设计合适的算法。 为什么第一个基础理论是拜占庭将军问题? 因为它很好地抽象出了分布式系统面临的共识问题。 上面提到的 8 种分布式算法中有 5 种跟拜占庭问题相关,可以说弄懂拜占庭问题对后面学习其他算法就会容易很多。 下面我用三国杀游戏中的身份牌来讲解拜占庭将军问题。 三国杀身份牌 三国杀中主要有四种身份:主公、忠臣、反贼、内奸。每个游戏玩家都会获得一个身份牌。主公只有 1 个。忠臣 最多 2 个,反贼最多 4个,内奸最多一个。 主公 主公身份牌 技巧: 以自己生存为首要目标,分散反贼注意力。配合忠内剿灭反贼并判断谁是忠谁是内。 忠臣 忠臣身份牌 技巧:忠臣是主公的屏障,威慑反贼和内奸的天平。 反贼 反贼身份牌 技巧: 反贼作为数量最多的身份,需要集中火力猛攻敌人弱点。正确的思路是获胜的关键。 内奸 内奸身份牌 技巧:正确的战术+ 冷静的头脑+ 运气。 还原拜占庭问题 东汉末年,袁绍作为盟主,汇合了十八路诸侯一起攻打董卓。把董卓定为反贼,袁绍定为主公,另外有两个忠臣和一个内奸,就选这三个风云人物:曹操,刘备,孙坚(孙权的爸比),内奸扮演的角色是忠臣,主公和两个忠臣不知道内奸的身份,都当作忠臣对待了。 董卓是非常强大的,拥有精良的西凉兵,麾下还有战神吕布。大家都知道三英战吕布的故事,吕布以一已之力对阵刘备、张飞、关羽三人。 要想干掉董卓,袁绍必须统一忠臣的作战计划,三位忠臣还不知道有什么其他花花肠子,有一个还是内奸。如果内奸暗通反贼董卓,给忠臣发送误导性的作战信息,该怎么办?另外假定这几个忠臣都是通过书信交流作战信息,如果书信被拦截了或书信里面的信息被替换了咋办?这些场景都可能扰乱作战计划,最后出现有的忠臣在进攻,有的忠臣撤退了。那么反贼就可以乘此机会发起进攻,逐一攻破。 袁绍本来就没有曹操的机智,那他如何让忠臣们达成共识,制定统一的作战计划呢? 上面的映射关系就是一个拜占庭将军问题的一个简化表述,袁绍现在面临的就是典型的共识问题。也就是在可能有误导信息的情况下,采用合适的通讯机制,让多个将军达成共识,制定一致性的作战计划。 一方选择撤退 刘备、曹操、孙坚通过信使传递进攻或撤退的信息,然后进行协商,到底是进攻还是撤退。遵循少数服从多数,不允许弃权。 曹操疑心比较重,侦查了反贼的地形后,决定撤退。而刘备和孙坚决定进攻。 刘备决定进攻,通过信使告诉曹操和孙坚进攻。 曹操决定撤退,通过信使告诉刘备和孙坚撤退。 孙坚决定进攻,通过信使告诉曹操和刘备进攻。 一方选择撤退 内奸登场-撤退 因为我们前期的设定,孙坚作为内奸,早已与反贼董卓私下沟通好了,不攻打董卓。 刘备决定进攻,通过信使告诉曹操和孙坚进攻。 曹操决定撤退,通过信使告诉曹操和孙坚撤退。 孙坚决定撤退,通过信使告诉曹操和刘备撤退。 内奸登场-撤退 内奸使诈-一进一退 内奸看了上述计划,发现忠臣都撤退了,并没有被消灭,就想通过使诈的方式来消灭其中一个忠臣。 刘备决定进攻,通过信使告诉曹操和孙坚进攻。 曹操决定撤退,通过信使告诉刘备和孙坚撤退。 孙坚作为内奸使诈,通过信使告诉刘备进攻,告诉曹操撤退。 内奸使诈-一进一退 刘备的票数为进攻 2 票,撤退 1 票,曹操的票数为进攻 1 票,撤退 2 票。按照少数服从多数的原则,刘备最后会选择进攻,而曹操会选择撤退,孙坚作为内奸肯定不会进攻,刘备单独进攻反贼董卓,势单力薄,被董卓干掉了。 从这个场景中,我们看到内奸孙坚通过发送误导信息,非常容易地就干扰了刘备和曹操的作战计划,导致两位忠臣被逐一击破。这个现象就是二忠一判难题。那么主公袁绍该怎么解决这个问题? 拜占庭问题解法 解法原理 我们来看下第一轮是怎么做的。 第一步:先发送作战信息的将军我们把他称为指挥官(袁绍),另外的将军我们称作副官(刘备,曹操,孙坚)。 第一轮 第一轮指挥官(袁绍)已经发送指令了,现在就需要刘备、曹操、孙坚依次作为指挥官给其他两位副将发送作战信息。 孙坚使诈 - 两撤退 如此看来,引入了一位指挥官后,确实可以避免孙坚使诈,但如果是孙坚在第一轮作为指挥官,其他人作为副官呢? 孙坚使诈 - 一进一退 第一轮 曹操向刘备和袁绍发送进攻指令。 第二轮 如果叛将人数为 m,将军数 n >= 3m + 1,那么就可以解决拜占庭将军问题。 比如上述的攻打董卓问题,曹操、刘备、孙坚三个人当中,孙坚是叛将,他可以使诈,使作战计划不统一。必须增加一位忠臣袁绍来协商共识,才能达成一致性作战计划。 拜占庭解法二-签名 那可以在不增加忠臣的情况下,解决拜占庭的二忠一判问题呢? 解法二就是通过签名消息。比如将军之间通过印章、虎符等信物进行通信。来保证这几个特征: 签名无法伪造,对签名消息的内容进行任何更改都会被发现。 总结 通过三国杀角色来讲解分布式中共识场景。那他们和分布式系统的映射关系是怎么样的呢? 将军对应计算机节点。 拜占庭容错算法还有 FBFT 算法,PoW 算法,当然不会在这篇中去讲这些算法,后续再讲解。一口吃不了大胖子~ 有了拜占庭容错算法,肯定有非拜占庭容错算法,顾名思义,就是没有发送误导信息的节点。CFT 算法就是解决分布式系统中存在故障,但不存在恶意节点的场景下的共识问题。简单来说就是可能因系统故障造成丢失消息或消息重复,但不存在错误消息、伪造消息。对应的算法有 Paxos 算法、Raft 算法、ZAB 协议。后续讲解~ 上面提到了 5 种算法,居然都是跟拜占庭问题有关,你说今天讲的拜占庭问题重要不重要? https://mp.weixin.qq.com/s/2slIJxMmLSoJkj-k5dFTmg 总结了一些2020年的面试题,这份面试题的包含的模块分为19个模块,分别是: Java 基础、容器、多线程、反射、对象拷贝、Java Web 、异常、网络、设计模式、Spring/Spring MVC、Spring Boot/Spring Cloud、Hibernate、MyBatis、RabbitMQ、Kafka、Zookeeper、MySQL、Redis、JVM 。 |
|