簡介
- 縱所周知分布式系統存在各種的問題, 比如機器宕機、網路例外、訊息丟失、訊息亂序、資料錯誤、不可靠的TCP、存盤資料丟失等故障行為 . 而著名的拜占庭將軍問題則描述的了一個最困難的，也是最復雜的一種分布式故障場景, 因為不僅可能存在故障行為，還存在惡意行為.
拜占庭將軍問題 講的是 有多個將軍(節點) 如何就某個作戰計劃(比如進攻或者撤退)達成共識(一致性)的問題, 將軍與將軍之間只能通過信使(訊息)來通信, 但是在互相通信的程序中可能存在信使被殺(通訊故障或者訊息丟失) , 信使被替換(訊息被劫持偽造) , 將軍叛變(節點被劫持發送錯誤資訊)等問題.
1.2 二忠一叛難題
忠誠的將軍的行為:發送給其他將軍的訊息是一致的叛變的將軍的行為:發送給其他將軍的訊息是不一致的或者相反的達成共識:只需要有半數以上將軍達成共識即可, 不需要全部.少數服務多數原則:一個將軍收到訊息后按照少數服務多數原則進行投票表決
假設現在只有3個將軍, 需要去互相通信統一作戰計劃達成共識, 并且A和B是忠誠的, C是叛變的情況下會存在什么樣的問題?
假設A和B先發送訊息, A決定進攻, B決定撤退
通信后A和B的投票比都是1:1, 這時如果C是忠誠的, 無論它決定進攻還是撤退, 最終A和B的票數比都是進攻[2] : 撤退[1]==》 決定進攻 或者 都是 進攻[1] : 撤退[2]==》 決定撤退, 即兩者的目標是一致沒問題. 但是如果C是叛變將軍, 然后它給A將軍發送撤退, 給B將軍發送進攻的訊息. 這時候問題就很大了, A收到了1個進攻兩個撤退最終決定撤退, 而B收到2個進攻, 1個撤退最終決定進攻. 兩者沒有達成共識, 然后B單槍匹馬去進攻被殲滅了.
1.3 二忠一叛難題的解法1: 口信訊息型拜占庭問題之解
- 通過增加額外的將軍參與討論,并且作為指揮官主導作戰指令, 并且增加多輪作戰討論去解決叛變將軍的資訊干擾
作戰規則:
- 1、增加將軍D, 大家事先約定如果沒有收到訊息，就執行預設的默認命令，比如"撤退".
- 2、進行兩輪作戰討論,
第一輪討論先發送作戰資訊的將軍作為指揮官，其他的將軍作為副官；指揮官先單獨將他的作戰資訊發送給每位副官； 每位副官，將從指揮官處收到的作戰資訊作為他的作戰指令；如果沒有收到作戰資訊，將把默認的“撤退”作為作戰指令，- 然后在
第二輪作戰討論中, 除了第一輪的指揮官外，剩余的3位副官互相給另外2位將軍發送作戰資訊； 然后，這3位副官按照“少數服從多數”，執行收到的作戰指令，
這時候作戰的討論情況就會出現兩種情況:
情況1:忠誠的將軍作為指揮官
第一輪作戰討論:
- 忠誠將軍作為指揮官發送一個進攻的指令給3個副官, 理想情況下副官會把該指令作為他的作戰指令
第二輪作戰討論:
- B、D、C互相給其他副官發送作戰指令. B和D按照指揮官的指令發送作戰指令, 這時得到的票數比都是
進攻[2] : 撤退[0], 這時候C作為叛軍, 無論它發不發指令, 或者給B和D都發送撤退或者給B發送進攻給D發送撤退都好, 它都無法影響B和D的最終決定并且達成共識(都是進攻). 成功解決叛軍的干擾.
情況2:叛變的將軍作為指揮官
第一輪作戰討論:
- 叛軍C作為指揮官給3個副官發送作戰指令. 如果C不發送指令, 最終ABD都執行默認撤退指令能達成共識. 如果C都發送進攻或者撤退指令這是忠誠將軍行為最終ABD也能達成共識. 最后一種情況就是發送不同的作戰指令給副官. 如給AD發送撤退指令, 給B發送進攻指令.
第二輪作戰討論:
- ABD按照接收到的指揮官的指令發送作戰指令, 最終都是決定撤退仍然能打成共識. 同理如果C第一輪發送兩個進攻1個撤退, 最終第二輪ABD依然能達成共識決定統一進攻.
口信訊息解決拜占庭將軍問題總結:
- 2忠1叛的共識討論就需要增加1位將軍參與討論, 并且變成2輪作戰討論. 根據
蘭伯特在論文中的推導,如果叛軍人數為m，將軍人數不能少于3m + 1, 作戰討論就要為m+1輪, 那么拜占庭將軍問題就能解決. 這個演算法前提得知道叛軍人數m是多少
1.4 二忠一叛難題的解法2: 簽名訊息型拜占庭問題之解
- 在不增加將軍的情況下, 通過訊息簽名的方式解決二忠一叛的難題.
- 通過簽名機制約束叛軍的叛變行為，任何叛變行為都會被發現，無論有多少忠誠的將軍和多少叛軍，忠誠的將軍們總能達成一致的作戰計劃，
作戰規則:
- 忠誠將軍的簽名無法偽造，而且對他簽名訊息的內容進行任何更改都會被發現
- 任何人都能驗證將軍簽名的真偽，
- 副官如果收到多條指令，將這些指令訊息按照一定順序排隊排序.最終大家按照約定只執行佇列的第一個或中間一個或最后一個作為自己的作戰命令.
這時候作戰的討論情況也會出現兩種情況:
情況1:忠誠的將軍作為指揮官
第一輪作戰討論:
- A作為指揮官對訊息進行簽名任何人對訊息的串改都會被發現, 然后發送進攻訊息給BC副官,
第二輪作戰討論:
- B遵從指揮官的指令發送進攻作戰指令給C, 如果C不發送指令給B, 最終B執行A的指令, AB能達成共識. 而如果C修改或偽造收到的A的作戰資訊給B, 則會被B發現并忽略. AB依然能達成共識. 即都是進攻
情況2:叛變的將軍作為指揮官
第一輪作戰討論:
- C作為指揮官給A和B發送不一致的訊息
第二輪作戰討論:
- B佇列的指令是[撤退,進攻]、A佇列里的指令是[撤退、進攻]. 取最后一個作為指令兩者仍然能達成共識
簽名訊息型解決拜占庭將軍問題總結:
- 無論有多少忠誠的將軍和多少叛將，忠誠的將軍們總能達成一致的作戰計劃
- 如果m個叛將，仍需要 執行
m+1輪作戰討論 - 它解決的是忠將們如何就作戰計劃達成共識的問題, 不在乎結果到底是進攻還是撤退，在乎的是忠將會不會達成一致而已.
總結
故障行為: 丟失訊息，或者有訊息重復惡意行為: 節點被劫持攻擊發送錯誤訊息, 偽造訊息
拜占庭將軍問題描述的是分布式系統的除了存在故障行為，還存在惡意行為的場景. 解決拜占庭將軍問題的演算法叫 拜占庭容錯演算法（Byzantine Fault Tolerance，BFT）, 比如PBFT演算法，PoW演算法
而非拜占庭容錯演算法 , 又名故障容錯演算法（Crash Fault Tolerance，CFT) , 它解決的是 分布式系統存在 故障行為 但不存在 惡意行為的共識問題, 常見的演算法有Paxos演算法、Raft演算法、ZAB協議
10、打賞
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/265677.html
標籤：區塊鏈
上一篇：golang面向物件編程—介面