[[357046]]

前言

《三國殺》是一款熱門的卡牌游戲，結(jié)合中國三國時(shí)期背景，以身份為線索，以卡牌為形式，益智休閑，老少皆宜。

東漢末年，袁紹作為盟主，匯合了十八路諸侯一起攻打董卓。

在講解之前，我們先聊下分布式協(xié)議和算法整體脈絡(luò)。

現(xiàn)在很多開發(fā)同學(xué)對(duì)分布式的組件怎么使用都有一定經(jīng)驗(yàn)，也知道 CAP 理論和 BASE 理論的大致含義。但認(rèn)真去看分布式算法的真的很少，原因有三：

擔(dān)心算法過于復(fù)雜，所以花的時(shí)間很少。

網(wǎng)上的資料能用大白話將分布式算法講清楚的比較少。

學(xué)習(xí)分布式算法沒有一條清晰的路線。

我會(huì)在后續(xù)的文章中用故事、大白話的方式來講解分布式算法的原理，以及學(xué)習(xí)路線到底是怎么樣的。

學(xué)習(xí)路線

學(xué)習(xí)分布式協(xié)議和算法的路線可以是先學(xué)習(xí)四大基礎(chǔ)理論，作為地基，再學(xué)習(xí)分布式協(xié)議和算法，就像是在地基上建房子。地基打好了，才能建更穩(wěn)固的高樓大廈。

四大基礎(chǔ)理論

• 拜占庭將軍問題
• CAP 理論
• ACID 理論
• BASE 理論

八大分布式協(xié)議和算法

• Paxos 算法
• Raft 算法
• 一致性 Hash 算法
• Gossip 協(xié)議算法
• Quorum NWR 算法
• FBFT 算法
• POW 算法
• ZAB 協(xié)議

因篇幅原因，本篇只涉及拜占庭將軍問題。

拜占庭將軍問題

大家可能聽過拜占庭將軍問題。它是由萊斯利·蘭伯特提出的點(diǎn)對(duì)點(diǎn)通信中的基本問題，

拜占庭位于如今的土耳其的伊斯坦布爾，是東羅馬帝國的首都。由于當(dāng)時(shí)拜占庭羅馬帝國國土遼闊，為了達(dá)到防御目的，每個(gè)軍隊(duì)都分隔很遠(yuǎn)，將軍與將軍之間只能靠信差傳消息。在戰(zhàn)爭的時(shí)候，拜占庭軍隊(duì)內(nèi)所有將軍和副官必須達(dá)成一致的共識(shí)，決定是否有贏的機(jī)會(huì)才去攻打敵人的陣營。但是，在軍隊(duì)內(nèi)有可能存有叛徒和敵軍的間諜，這個(gè)就是拜占庭容錯(cuò)問題。

實(shí)際上拜占庭問題是分布式領(lǐng)域最復(fù)雜的一個(gè)容錯(cuò)模型，一旦理解它，就能掌握分布式共識(shí)問題的解決思路，還能幫助大家理解常用的共識(shí)算法，也可以幫助我們?cè)诠ぷ髦羞x擇合適的算法，或者設(shè)計(jì)合適的算法。

為什么第一個(gè)基礎(chǔ)理論是拜占庭將軍問題?

因?yàn)樗芎玫爻橄蟪隽朔植际较到y(tǒng)面臨的共識(shí)問題。 上面提到的 8 種分布式算法中有 5 種跟拜占庭問題相關(guān)，可以說弄懂拜占庭問題對(duì)后面學(xué)習(xí)其他算法就會(huì)容易很多。

下面我用三國殺游戲中的身份牌來講解拜占庭將軍問題。

三國殺身份牌

三國殺中主要有四種身份：主公、忠臣、反賊、內(nèi)奸。每個(gè)游戲玩家都會(huì)獲得一個(gè)身份牌。主公只有 1 個(gè)。忠臣 最多 2 個(gè)，反賊最多 4個(gè)，內(nèi)奸最多一個(gè)。

主公

主公身份牌

獲勝條件： 消滅所有反賊和內(nèi)奸

技巧： 以自己生存為首要目標(biāo)，分散反賊注意力。配合忠內(nèi)剿滅反賊并判斷誰是忠誰是內(nèi)。

忠臣

忠臣身份牌

獲勝條件：保護(hù)主公存活的前提下消滅所有反賊和內(nèi)奸。

技巧：忠臣是主公的屏障，威懾反賊和內(nèi)奸的天平。

反賊

反賊身份牌

獲勝條件：消滅主公即可獲勝。

技巧： 反賊作為數(shù)量最多的身份，需要集中火力猛攻敵人弱點(diǎn)。正確的思路是獲勝的關(guān)鍵。

內(nèi)奸

內(nèi)奸身份牌

獲勝條件： 先消滅反賊和忠臣，最后與主公單挑成為最后唯一生還者。

技巧：正確的戰(zhàn)術(shù)+ 冷靜的頭腦+ 運(yùn)氣。

還原拜占庭問題

東漢末年，袁紹作為盟主，匯合了十八路諸侯一起攻打董卓。把董卓定為反賊，袁紹定為主公，另外有兩個(gè)忠臣和一個(gè)內(nèi)奸，就選這三個(gè)風(fēng)云人物：曹操，劉備，孫堅(jiān)(孫權(quán)的爸比)，內(nèi)奸扮演的角色是忠臣，主公和兩個(gè)忠臣不知道內(nèi)奸的身份，都當(dāng)作忠臣對(duì)待了。

董卓是非常強(qiáng)大的，擁有精良的西涼兵，麾下還有戰(zhàn)神呂布。大家都知道三英站呂布的故事，呂布以一已之力對(duì)陣劉備、張飛、關(guān)羽三人。

要想干掉董卓，袁紹必須統(tǒng)一忠臣的作戰(zhàn)計(jì)劃，三位忠臣還不知道有什么其他花花腸子，有一個(gè)還是內(nèi)奸。如果內(nèi)奸暗通反賊董卓，給忠臣發(fā)送誤導(dǎo)性的作戰(zhàn)信息，該怎么辦?另外假定這幾個(gè)忠臣都是通過書信交流作戰(zhàn)信息，如果書信被攔截了或書信里面的信息被替換了咋辦?這些場景都可能擾亂作戰(zhàn)計(jì)劃，最后出現(xiàn)有的忠臣在進(jìn)攻，有的忠臣撤退了。那么反賊就可以乘此機(jī)會(huì)發(fā)起進(jìn)攻，逐一攻破。

袁紹本來就沒有曹操的機(jī)智，那他如何讓忠臣們達(dá)成共識(shí)，制定統(tǒng)一的作戰(zhàn)計(jì)劃呢?

上面的映射關(guān)系就是一個(gè)拜占庭將軍問題的一個(gè)簡化表述，袁紹現(xiàn)在面臨的就是典型的共識(shí)問題。也就是在可能有誤導(dǎo)信息的情況下，采用合適的通訊機(jī)制，讓多個(gè)將軍達(dá)成共識(shí)，制定一致性的作戰(zhàn)計(jì)劃。

一方選擇撤退

劉備、曹操、孫堅(jiān)通過信使傳遞進(jìn)攻或撤退的信息，然后進(jìn)行協(xié)商，到底是進(jìn)攻還是撤退。遵循少數(shù)服從多數(shù)，不允許棄權(quán)。

曹操疑心比較重，偵查了反賊的地形后，決定撤退。而劉備和孫堅(jiān)決定進(jìn)攻。

• 劉備決定進(jìn)攻，通過信使告訴曹操和孫堅(jiān)進(jìn)攻。
• 曹操?zèng)Q定撤退，通過信使告訴劉備和孫堅(jiān)撤退。
• 孫堅(jiān)決定進(jìn)攻，通過信使告訴曹操和劉備進(jìn)攻。

一方選擇撤退

曹操收到的信息：進(jìn)攻 2 票，自己的一張撤退票，票數(shù)一比，進(jìn)攻票：撤退票 = 2 : 1，按照上面的少數(shù)服從多數(shù)原則進(jìn)行投票表決，曹操還是會(huì)進(jìn)攻。那么三方的作戰(zhàn)方案都是進(jìn)攻，所以是一個(gè)一致性的作戰(zhàn)方案。最后戰(zhàn)勝了董卓。

內(nèi)奸登場-撤退

因?yàn)槲覀兦捌诘脑O(shè)定，孫堅(jiān)作為內(nèi)奸，早已與反賊董卓私下溝通好了，不攻打董卓。

• 劉備決定進(jìn)攻，通過信使告訴曹操和孫堅(jiān)進(jìn)攻。
• 曹操?zèng)Q定撤退，通過信使告訴曹操和孫堅(jiān)撤退。
• 孫堅(jiān)決定撤退，通過信使告訴曹操和劉備撤退。

內(nèi)奸登場-撤退

劉備收到進(jìn)攻和撤退各一票，而自己又選擇撤退，所以劉備得到的票數(shù)是：進(jìn)攻 : 撤退 = 1 : 2，遵從少數(shù)服從多數(shù)的原則，劉備選擇最后選擇撤退，那么三方的作戰(zhàn)方案都是撤退，所以也是一個(gè)一致性的作戰(zhàn)方案。

內(nèi)奸使詐-一進(jìn)一退

內(nèi)奸看了上述計(jì)劃，發(fā)現(xiàn)忠臣都撤退了，并沒有被消滅，就想通過使詐的方式來消滅其中一個(gè)忠臣。

• 劉備決定進(jìn)攻，通過信使告訴曹操和孫堅(jiān)進(jìn)攻。
• 曹操?zèng)Q定撤退，通過信使告訴曹操和孫堅(jiān)撤退。
• 孫堅(jiān)作為內(nèi)奸使詐，通過信使告訴劉備進(jìn)攻，告訴曹操撤退。

內(nèi)奸使詐-一進(jìn)一退

那么結(jié)果是什么呢?

劉備的票數(shù)為進(jìn)攻 2 票，撤退 1 票，曹操的票數(shù)為進(jìn)攻 1 票，撤退 2 票。按照少數(shù)服從多數(shù)的原則，劉備最后會(huì)選擇進(jìn)攻，而曹操會(huì)選擇撤退，孫堅(jiān)作為內(nèi)奸肯定不會(huì)進(jìn)攻，劉備單獨(dú)進(jìn)攻反賊董卓，勢單力薄，被董卓干掉了。

從這個(gè)場景中，我們看到內(nèi)奸孫堅(jiān)通過發(fā)送誤導(dǎo)信息，非常容易地就干擾了劉備和曹操的作戰(zhàn)計(jì)劃，導(dǎo)致兩位忠臣被逐一擊破。這個(gè)現(xiàn)象就是二忠一判難題。那么主公袁紹該怎么解決這個(gè)問題?

拜占庭問題解法

解法原理

就是將袁紹也參與進(jìn)來進(jìn)行投票，這樣就增加了一位忠臣的數(shù)量。三個(gè)忠臣一個(gè)叛賊。然后 4 位將軍做了一個(gè)約定，如果沒有收到命令，則執(zhí)行默認(rèn)命令，比如撤退。另外約定流程來發(fā)送作戰(zhàn)信息和如何執(zhí)行作戰(zhàn)指令。這個(gè)解法的關(guān)鍵點(diǎn)就是執(zhí)行兩輪作戰(zhàn)信息協(xié)商。

我們來看下第一輪是怎么做的。

• 第一步：先發(fā)送作戰(zhàn)信息的將軍我們把他稱為指揮官(袁紹)，另外的將軍我們稱作副官(劉備，曹操，孫堅(jiān))。
• 第二步：指揮官將他的作戰(zhàn)信息發(fā)送給所有的副官。
• 第三步：每一位副官將從指揮官處收到的作戰(zhàn)信息，作為自己的作戰(zhàn)指令;假如沒有收到指揮官的作戰(zhàn)信息，將把默認(rèn)的撤退作為作戰(zhàn)指令。

我們用圖來演示：袁紹作為主公先發(fā)送作戰(zhàn)信息，作戰(zhàn)指令為進(jìn)攻。然后曹操、劉備、孫堅(jiān)收到進(jìn)攻的作戰(zhàn)指令。

第一輪

再來看下第二輪是怎么做的。

• 第一輪指揮官(袁紹)已經(jīng)發(fā)送指令了，現(xiàn)在就需要?jiǎng)?、曹操、孫堅(jiān)依次作為指揮官給其他兩位副將發(fā)送作戰(zhàn)信息。
• 然后這三位副將按照少數(shù)服從多數(shù)的原則，執(zhí)行收到的作戰(zhàn)指令。

孫堅(jiān)使詐 - 兩撤退

如果孫堅(jiān)使詐，比如給曹操和劉備都發(fā)送撤退信息，如下圖所示。那么劉備和曹操收到的作戰(zhàn)信息為 進(jìn)攻 2票，撤退 1 票，按照少數(shù)服從多數(shù)的原則，最后劉備和曹操執(zhí)行進(jìn)攻，實(shí)現(xiàn)了作戰(zhàn)計(jì)劃的一致性，曹操和劉備聯(lián)合作戰(zhàn)擊敗了反賊董卓(即使孫堅(jiān)沒有參加作戰(zhàn)。)

孫堅(jiān)使詐 - 兩撤退

孫堅(jiān)使詐 - 一進(jìn)一退

假如孫堅(jiān)使詐，給曹操發(fā)送撤退指令，給劉備發(fā)送進(jìn)攻指令，那么劉備收到的作戰(zhàn)信息是進(jìn)攻 3票，肯定會(huì)發(fā)起進(jìn)攻了，而曹操收到的作戰(zhàn)信息是進(jìn)攻 2 票，撤退 1 票，最后曹操還是會(huì)進(jìn)攻，所以劉備和曹操還是聯(lián)合作戰(zhàn)擊敗了反賊董卓。

如此看來，引入了一位指揮官后，確實(shí)可以避免孫堅(jiān)使詐，但如果是孫堅(jiān)在第一輪作為指揮官，其他人作為副官呢?

孫堅(jiān)使詐 - 一進(jìn)一退

孫堅(jiān)作為指揮官

第一輪孫堅(jiān)向其中一個(gè)副官袁紹發(fā)送撤退指令，向另外兩個(gè)副官曹操、劉備發(fā)送進(jìn)攻指令。那么第一輪的結(jié)果如下圖：

第一輪

第二輪孫堅(jiān)休息，其他副官按照孫堅(jiān)發(fā)送的指令開始向另外的副官發(fā)送指令。

• 曹操向劉備和袁紹發(fā)送進(jìn)攻指令。
• 劉備向曹操和袁紹發(fā)送進(jìn)攻指令。
• 袁紹向曹操和劉備發(fā)送撤退指令。

如下圖所示，最后曹操、劉備、袁紹收到的指令為進(jìn)攻 2 票，撤退 1 票，按照少數(shù)服從多數(shù)原則，三個(gè)人都是發(fā)起進(jìn)攻。執(zhí)行了一致的作戰(zhàn)計(jì)劃，保證作戰(zhàn)的勝利。

第二輪

小結(jié)

通過上面的演示，我們知道了如何解決拜占庭將軍問題。其實(shí)蘭伯特在他的論文中也提到過如何解決。

如果叛將人數(shù)為 m，將軍數(shù) n >= 3m + 1，那么就可以解決拜占庭將軍問題。

前提條件：叛將數(shù) m 一致，需要進(jìn)行 m + 1 輪的作戰(zhàn)協(xié)商。

這個(gè)公式，大家只需要記住就可以了，推到過程可以參考論文。

比如上述的攻打董卓問題，曹操、劉備、孫堅(jiān)三個(gè)人當(dāng)中，孫堅(jiān)是叛將，他可以使詐，使作戰(zhàn)計(jì)劃不統(tǒng)一。必須增加一位忠臣袁紹來協(xié)商共識(shí)，才能達(dá)成一致性作戰(zhàn)計(jì)劃。

拜占庭解法二-簽名

那可以在不增加忠臣的情況下，解決拜占庭的二忠一判問題呢?

解法二就是通過簽名消息。比如將軍之間通過印章、虎符等信物進(jìn)行通信。來保證這幾個(gè)特征：

• 簽名無法偽造，對(duì)簽名消息的內(nèi)容進(jìn)行任何更改都會(huì)被發(fā)現(xiàn)。
• 任何人都能驗(yàn)證將軍簽名的真?zhèn)巍?/li>

限于篇幅原因，簽名的演示這里就不做展開了，感興趣的@我，后續(xù)會(huì)加上。

總結(jié)

通過三國殺角色來講解分布式中共識(shí)場景。那他們和分布式系統(tǒng)的映射關(guān)系是怎么樣的呢?

• 將軍對(duì)應(yīng)計(jì)算機(jī)節(jié)點(diǎn)。
• 忠臣的將軍對(duì)應(yīng)正常運(yùn)行的計(jì)算機(jī)節(jié)點(diǎn)。
• 叛變的將軍對(duì)應(yīng)出現(xiàn)故障并會(huì)發(fā)送誤導(dǎo)信息的計(jì)算機(jī)節(jié)點(diǎn)。
• 信使被殺對(duì)應(yīng)通訊故障、信息丟失。
• 信使被間諜替換對(duì)應(yīng)為通訊被惡意攻擊、偽造信息或劫持通訊。

可不要小瞧拜占庭問題，它可是分布式場景最復(fù)雜的的故障場景。比如在數(shù)字貨幣的區(qū)塊鏈技術(shù)中就有用到這些知識(shí)點(diǎn)。而且必須使用拜占庭容錯(cuò)算法(也就是 Byzantine Fault Tolerance，BFT)。

拜占庭容錯(cuò)算法還有 FBFT 算法，PoW 算法，當(dāng)然不會(huì)在這篇中去講這些算法，后續(xù)再講解。一口吃不了大胖子~

有了拜占庭容錯(cuò)算法，肯定有非拜占庭容錯(cuò)算法，顧名思義，就是沒有發(fā)送誤導(dǎo)信息的節(jié)點(diǎn)。CFT 算法就是解決分布式系統(tǒng)中存在故障，但不存在惡意節(jié)點(diǎn)的場景下的共識(shí)問題。簡單來說就是可能因系統(tǒng)故障造成丟失消息或消息重復(fù)，但不存在錯(cuò)誤消息、偽造消息。對(duì)應(yīng)的算法有 Paxos 算法、Raft 算法、ZAB 協(xié)議。后續(xù)講解~

上面提到了 5 種算法，居然都是跟拜占庭問題有關(guān)，你說今天講的拜占庭問題重要不重要?

這么多算法該如何選擇?

節(jié)點(diǎn)可信，選非拜占庭容錯(cuò)算法。否則就用拜占庭容錯(cuò)算法，如區(qū)塊鏈中用到的 PoW 算法。

本文轉(zhuǎn)載自微信公眾號(hào)「悟空聊架構(gòu)」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請(qǐng)聯(lián)系悟空聊架構(gòu)公眾號(hào)。