#110 分散式系統 - 淺談拜占庭容錯

在上一篇文章 (#103 分散式系統的「開會」藝術 - 淺談共識演算法) 裡，我們聊到了 Raft 這一類的共識演算法．我們知道，分散式系統最頭痛的問題之一就是「節點會故障」，而 Raft 就是用來處理「當一群節點中有部分節點掛掉時，剩下的節點如何達成一致的決議」這樣的問題．如果你看過那一篇文章，你應該會對 Raft 的設計留下不錯的印象，畢竟它真的優雅而且實用．

不過，今天這篇文章我想要戳破一個 Raft 沒有處理的盲點．這個盲點在某些應用場景裡是天大的事情，特別是當我們把分散式系統用在生命攸關的場合，例如飛機的飛行控制系統．這個盲點就是：節點不一定都是誠實的．

Raft 沒處理到的問題

我們先回顧一下 Raft 處理的故障模型 (failure model)．Raft 假設一個節點如果出了事，它的表現方式就是「停下來」，可能是當機，可能是斷網，可能是處理速度慢到像沒在動．專業上我們稱這種故障型態為 crash failure 或是 fail-stop failure．

換句話說，Raft 對節點有一個基本的假設：只要這個節點還活著，它一定會誠實地按照協議來辦事．Raft 不會懷疑你傳過來的訊息是真是假，因為它假設你不會說謊．

但是，現實世界並沒有這麼天真．節點可能會「壞得很奇怪」，例如硬體出錯導致記憶體裡的數值被偷偷改掉．軟體有 bug 導致它送出錯誤但格式正確的資料．網路設備故障導致同一個訊息被改成兩個不同的版本送給不同的接收者．甚至更糟的，節點被惡意入侵後故意搞破壞．

想像一個情境：你有一個五個節點組成的 Raft 集群，其中一個節點故障了，但它沒有當機，反而還活得好好的，更糟的是，它會傳出錯誤但看起來合法的訊息．對 A 節點說「我的日誌是 X」，對 B 節點說「我的日誌是 Y」．這時候 Raft 就完全沒招了．Raft 的設計裡，誰選上 Leader 大家就聽誰的，Follower 不會去質疑 Leader 給的指令是否合理．如果 Leader 自己就是出問題的那個節點，它可以隨意指派錯誤的日誌給每個 Follower，整個集群的狀態就會變得一塌糊塗．

這種「節點不只會壞，還會用各種奇怪的方式壞」的故障型態，我們稱為 拜占庭故障 (Byzantine Failure)，能夠在這種情況下還可以正常運作的能力，就叫做 拜占庭容錯 (Byzantine Fault Tolerance, BFT)．

拜占庭將軍問題

「拜占庭」這個名字聽起來很有文學氣息，其實它來自一個有名的故事．這個故事是由 Leslie Lamport 等人在 1982 年提出的，論文標題為 The Byzantine Generals Problem，有興趣的讀者可以直接讀原文．

故事的內容是這樣：拜占庭帝國的軍隊要圍攻一座城市，幾個將軍各自帶著部隊駐紮在城市周圍不同的方位．將軍們必須要協調出一個一致的行動：要嘛大家一起進攻，要嘛大家一起撤退．如果只有一部分將軍進攻，沒有得到其他人的支援，那一定會被殲滅．

問題來了：將軍之間只能透過信差來傳遞訊息．更糟的是，將軍裡面也可能藏有叛徒，他可能對 A 將軍說「進攻」，對 B 將軍說「撤退」，藉此讓盟軍亂成一團．

請問：在這樣的情況下，誠實的將軍們有辦法達成一致的決議嗎? 我們先用一個最小的例子來看看這個問題有多麻煩．

三個將軍的故事 (為什麼會行不通)

假設我們只有三個將軍：將軍 A (司令)、將軍 B、將軍 C．我們的目標是「即使其中有一個是叛徒，誠實的將軍仍然能達成一致的行動」．先看看會發生什麼事．

情境一：司令 A 是叛徒

叛徒司令要搞破壞，於是他發出兩個矛盾的命令：

• A 對 B 說：「進攻」
• A 對 C 說：「撤退」

B 和 C 都是誠實的，但他們各自收到不同的命令，於是他們互相通報自己收到了什麼：

• B 告訴 C：「司令叫我進攻」
• C 告訴 B：「司令叫我撤退」

現在站在 B 的視角看：「司令叫我進攻，但 C 卻說司令叫他撤退．兩個訊息不一致，到底誰在說謊呢? 是司令騙我? 還是 C 騙我?」B 完全沒辦法判斷．

情境二：司令 A 是誠實的，但 C 是叛徒

誠實的司令發出一致的命令：

• A 對 B 說：「進攻」
• A 對 C 說：「進攻」

叛徒 C 收到「進攻」之後決定搞破壞，於是他對 B 說謊：

• B 告訴 C：「司令叫我進攻」 (誠實的)
• C 告訴 B：「司令叫我撤退」 (撒謊)

站在 B 的視角看：「司令叫我進攻，但 C 卻說司令叫他撤退．兩個訊息不一致，到底誰在說謊呢? 是司令騙我? 還是 C 騙我?」

關鍵來了：請仔細比較這兩個情境，B 在這兩個情境裡看到的訊息是一模一樣的! 「司令說進攻，C 說司令叫他撤退」．但這兩種情境的真相完全不同：一個是司令該被排除，一個是 C 該被排除．B 沒有任何辦法分辨自己處於哪一種情境，所以他無法做出正確的判斷．

這就是為什麼 3 個節點處理不了 1 個叛徒．不論你設計什麼樣聰明的協議，只要叛徒能巧妙地說謊，誠實的節點就會被資訊不對稱搞得無所適從．

四個將軍可以怎麼解決

那如果我們把將軍的數量增加到 4 個呢? 假設只有 1 個叛徒，狀況立刻不一樣了．

假設將軍 A、B、C、D，且只有 D 是叛徒．司令 A 把「進攻」這個命令傳給 B、C、D．然後 B、C、D 之間互相通報自己收到的命令：

B 收到的訊息：

• 司令 A 說：進攻
• C 說：「司令對我說的是進攻」
• D 說：「司令對我說的是撤退」 (叛徒在說謊)

B 看到三個訊息：進攻、進攻、撤退．用 多數決，「進攻」勝出，B 就決定進攻．C 也會看到類似的結果．這樣 B 和 C 兩個誠實的將軍就達成了一致．不論 D 怎麼搞破壞，他都無法讓 B 和 C 的決定不一致．

這個簡單的例子告訴我們一件事：拜占庭問題的解法核心，在於「同一個訊息要被多個來源確認，再用多數決排除說謊者」．這聽起來很直覺，但 Lamport 等人在他們的論文裡正式證明了一個更普遍的結論．

BFT 的數學門檻：3f+1

Lamport 的論文證明了一個很重要的結論：如果系統中可能有 f 個惡意節點，那麼總節點數至少要有 3f+1 個，才有可能達成共識．

換句話說，要容忍 1 個惡意節點，至少要 4 個節點 (這就是上面那個四將軍的例子)．要容忍 2 個惡意節點，至少要 7 個節點．要容忍 3 個惡意節點，至少要 10 個節點．這個條件比 Raft 嚴格很多，Raft 處理 crash failure 只需要 2f+1 個節點 (容忍 1 個故障節點只要 3 台就夠)．

為什麼一定要 3f+1 ? 我們可以這樣直觀地理解：我們需要排除掉 f 個惡意節點的影響，所以實際在做決議的「可信節點」至少要有 2f+1 個 (這樣即使有 f 個惡意節點混進來投票，誠實節點仍然會是多數)．加上原本可能有的 f 個惡意節點，總節點數最少就是 3f+1．

除了節點數的要求，BFT 演算法通常還需要更多輪的訊息傳遞才能確認結果．直觀上來想，每個節點不只要把自己的意見講出來，還要互相確認彼此聽到的內容是不是一致．這個「互相確認」的動作會讓訊息量大幅增加．

真實世界的 BFT：波音 777 的飛行控制系統

講到這裡你可能會想：這聽起來很學術，現實世界真的有人在用嗎? 答案是，當系統的失敗代價是人命的時候，BFT 就是必備的．接下來我們花一點時間仔細看一個經典範例：波音 777 的飛行控制系統．這是 BFT 在工業界最具代表性的應用之一，理解它，你就會看清楚 BFT 不只是學術概念，而是真的在保護人命的技術．

飛機其實也是個分散式系統

當你坐上一架 Boeing 777，你大概不會意識到，這架飛機上其實跑著一個非常複雜的分散式系統．飛機要穩定飛行，需要無數個感測器、致動器 (actuator)、和電腦彼此協調合作．感測器告訴電腦目前的姿態、速度、高度，飛行員給出操作指令，電腦做出計算，再把命令送到致動器來控制副翼、方向舵、升降舵等．這整個迴圈每秒要跑很多次，而且任何一個環節出錯都可能致命．

問題來了：要怎麼確保這個系統「絕對不會出錯」? 答案是不可能．硬體一定會故障，軟體一定會有 bug．我們要做的不是消除故障，而是即使故障發生了，飛機仍然能正常運作．這就是「容錯 (fault tolerance)」的概念．

三重三重備援的飛行電腦

波音 777 的飛行控制系統採用了一個叫做「triple-triple redundant」的架構，意思是：

• 主飛行電腦 (Primary Flight Computer, PFC) 一共有 3 個獨立通道．
• 每個通道內部又有 3 條獨立的運算管線 (computing lane)．
• 加起來總共有 9 個運算單元同時計算同一件事情．

更有趣的是，每條運算管線使用的微處理器是「dissimilar」的，也就是來自不同廠商、不同架構的晶片．為什麼要這樣做? 因為如果三條管線都用同一款 CPU，萬一這款 CPU 有設計上的瑕疵，那三條管線會同時算出同一個錯誤答案，多重備援就完全失效了．用不同廠牌的 CPU，可以避免這種「集體犯同一個錯」的風險．

這個設計很厲害，但還沒到 BFT．真正讓它變成 BFT 的，是把這些運算單元連起來的那條匯流排：SAFEbus．

關鍵問題：硬體不只會「壞掉」，還會「半死不活」

在進入 SAFEbus 的細節之前，我要先讓你理解一個非常重要的觀念，這個觀念就是 BFT 在飛機上不可或缺的根本原因．

我們設想一個非常具體的情境：飛行電腦的某個運算單元 X 算出來的飛行高度是 30,000 英呎．這個訊息要透過某個傳輸晶片送給其他電腦 B、C、D 來做後續比對．

如果這個傳輸晶片完全正常，事情很簡單：B、C、D 都收到 30,000，大家一致．

如果這個傳輸晶片完全壞掉 (例如電源沒了)，事情也好辦：B、C、D 都收不到任何訊息，大家可以馬上判斷它故障了，然後把它隔離．這種就是前面提到的 crash failure，是 Raft 那種演算法可以處理的．

但是，半導體元件的世界裡還有第三種狀態，那就是「半死不活」．這才是飛機上真正棘手的問題．

我來舉一個具體的例子．數位電路用電壓來表示 0 和 1，例如「0V 代表 0」、「5V 代表 1」．接收端會設定一個判斷閾值 (例如 2.5V)，低於閾值算 0，高於閾值算 1．

當一個輸出電路因為老化、輻射打到、或是電源不穩，導致它輸出的電壓飄到了中間值 (例如 2.4V)，會發生什麼事?

• 對接收端 B 而言，它的判斷閾值是 2.5V，所以 2.4V 被判讀成「0」．
• 對接收端 C 而言，它的閾值因為製造誤差稍微低一點，是 2.3V，所以同樣的 2.4V 被判讀成「1」．

請仔細看：同一個發送端，送出同一個訊號，但是不同的接收端讀到了不同的內容．這個情境是不是很眼熟? 沒錯，這就是我們前面講過的「拜占庭叛徒」! 一個壞掉的晶片，就像是一個對不同人說不同話的叛徒將軍．對 B 說的高度是 0，對 C 說的高度卻是某個截然不同的值．

這個現象在飛機上有很多來源：宇宙射線打到記憶體可能讓某個 bit 翻轉．閃電打到飛機可能讓電路產生暫時的雜訊．焊點老化可能讓訊號變得不穩定．溫度變化可能讓元件特性改變．這些故障的共同特徵就是「電腦沒當掉，但它送出來的資料對不同的接收者來說會不一致」．如果系統不處理這種拜占庭故障，後果可能是不同的副飛行電腦根據不同的高度判斷做出不同的控制決策，飛機就完蛋了．

這也是為什麼普通的故障容錯不夠用，飛機必須要有 BFT．

SAFEbus 怎麼解決這個問題

SAFEbus (正式名稱為 ARINC 659) 是 Honeywell 設計的一個匯流排，它把「四將軍解法」直接做進了硬體裡．關鍵設計如下：

• 每個運算單元連到 SAFEbus 的介面 (Bus Interface Unit, BIU) 是雙重備援．
• SAFEbus 本身有四條完全獨立的資料通道．
• 當一個訊息要傳送出去時，它會被同時送到這四條通道上．
• 接收端會收到四份副本，然後用多數決來決定真正的訊息內容．

回想一下我們前面講的「四將軍解法」：B 收到了司令、C、D 三個來源的訊息，用多數決排除說謊的那一個．SAFEbus 的設計理念完全一樣，只是把「將軍」換成了「資料通道」，把「叛徒」換成了「壞掉的硬體」．就算其中一條通道因為前面講的「半死不活」原因傳出怪訊息，剩下三條通道仍然會給出正確的結果，多數決就能把那條壞通道的影響排除掉．

而且 SAFEbus 厲害的地方是，這整個比對和投票的過程加起來只增加大約一微秒的延遲．對於要做即時飛行控制的系統來說，這是非常驚人的成就，這也是為什麼 BFT 能夠真的用在飛機這種對即時性要求極高的場景．有關以上 SAFEbus 的內容是簡化後的說明，我並不是航空方面的專家，所以無法解釋的太細節．

為什麼要這麼大費周章

可能你會想：飛機上裝這麼多備援是不是太誇張了? 答案藏在波音給 777 設計的目標裡．波音要求 777 的飛行控制系統「災難性故障」的機率要低於 10⁻¹⁰ (每飛行小時)．這個數字翻成人話就是：每 100 億飛行小時才允許出一次嚴重故障．要達到這個等級，沒有 BFT 就辦不到．

所以下次你坐 777 的時候，可以稍微回想一下：你頭頂上的設備櫃裡，正有 9 個獨立的運算單元，透過 4 條獨立的資料通道，互相用拜占庭容錯協議在「投票」，確保飛機正常運作．Lamport 那篇 1982 年的論文，就在你的頭上即時運行著．

經典的 BFT 演算法：PBFT

除了像 SAFEbus 這種專為航空設計的硬體層 BFT 之外，BFT 在軟體層也有經典的演算法．最有名的當屬 1999 年由 Castro 和 Liskov 提出的 PBFT (Practical Byzantine Fault Tolerance)．它把原本停留在理論階段的 BFT 概念，第一次做到了一個實用、可以真的部署的程度，這也是 "Practical" 這個字的由來．

PBFT 的核心想法簡化來說是：每一個指令都要經過多輪的投票確認，每個節點都要簽名表態自己看到了什麼，最後比對大家的簽名才能確認結果．這樣即使有惡意節點對不同的人傳不同的訊息，誠實的節點之間互相對照後，馬上就能發現不一致而排除這個叛徒．這個原理跟我們前面四將軍範例的想法是一致的．

PBFT 的特性大致如下：它仍然是一個有 Leader 的演算法 (在 PBFT 裡稱為 Primary)，但所有的決議都需要 2f+1 個節點同意才算數．每一輪共識需要 O(n²) 次的訊息傳遞，因為每個節點都要把自己的表態廣播給所有其他節點．這個特性讓它適合節點數較少 (幾十個以內) 的封閉系統．也許未來可以再寫另一篇文章來說明 PBFT 演算法．

BFT 的代價

看到這裡，你可能會問：如果 BFT 這麼強，為什麼不每個分散式系統都用 BFT 就好? 答案是成本．我們把 Raft 和 BFT 做個簡單的比較：

項目	Raft (Crash Fault Tolerance)	PBFT (Byzantine Fault Tolerance)
處理的故障	節點停止運作	節點停止運作 + 節點傳出錯誤訊息
容忍 f 個故障所需節點數	2f+1	3f+1
每輪訊息複雜度	O(n)	O(n²)
典型應用	etcd, Consul, 一般分散式資料庫	飛行控制系統, 跨組織信任系統

BFT 需要的節點數比較多，訊息傳遞量也大很多．對於一般的應用 (例如公司內部的分散式資料庫)，這樣的成本是浪費的，因為公司內部的伺服器不會故意說謊．但對於航空這類場景，BFT 的成本是必要的，因為失敗的代價遠遠高過運作的代價．

結語

Fault tolerance 是以前我在念書時相當感興趣的題目，不論是碩班學的分散式系統，或是博班時修的分散式演算法，我都是在這領域找題目來期末專題，甚至包含在選擇博班的研究題目時，也是在這出發尋找相關應用．從 Raft 到 PBFT，這個演進的脈絡其實反映了分散式系統設計者對「信任」這件事的不同假設．Raft 假設所有節點都是誠實的，只是可能會故障．PBFT 假設大多數節點是誠實的，但容許少數節點出現各種奇怪的故障，包含說謊．不同的假設，導致了完全不同的設計與成本．

每一種設計都有它適合的場景．如果你是在公司內部建一個分散式資料庫，Raft 就夠用了，沒必要花更高的成本去處理拜占庭問題．如果你是在做一個生命攸關的系統，那 BFT 就是必要的選擇．

工程的世界沒有銀彈，理解每個工具背後的假設與代價，比追求最 "潮" 的技術重要許多．這也是為什麼學分散式系統的人會說「先搞清楚你的故障模型」，因為一旦故障模型搞錯了，後面的所有設計都會出問題．

Hope it helps,