前言
《三國殺》是一款熱門的卡牌游戲，結合中國三國時期背景，以身份為線索，以卡牌為形式，益智休閑，老少皆宜，
東漢末年，袁紹作為盟主，匯合了十八路諸侯一起攻打董卓，
在講解之前，我們先聊下分布式協議和演算法整體脈絡，
現在很多開發同學對分布式的組件怎么使用都有一定經驗，也知道 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 演算法，
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 ，
獲取資料以上資料：關注公眾號：有故事的程式員，獲取學習資料，
記得點個關注+評論哦~
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/235664.html
標籤：其他