分散式系統對抗行程失效的第一道防線，是把行程複製並組織成群組（group）。本節依序討論行程群組的設計議題、容錯群組需要多少複本，以及當群組中有成員不可信時如何達成共識，最後談失效偵測。

設計議題#

容忍故障行程的關鍵做法，是把多個相同的行程組成一個群組。群組的核心性質是：送給群組的訊息，所有成員都會收到。如此一來，若群組中某個行程失效，其他行程有機會接手它的工作。

群組可以是動態的：可建立、可解散，行程可以在系統運行中加入或離開群組，也可以同時屬於多個群組。因此需要機制來管理群組與群組成員資格。引入群組的目的，是讓行程能把「一群行程」當成單一抽象來對待——送訊息給一組伺服器時，不必知道它們是誰、有幾個、在哪裡，而這些在每次呼叫之間都可能改變。

扁平群組與階層式群組#

群組的內部結構是重要的區分：

• 扁平群組（flat group）：所有行程平等，沒有老大，決策集體做成。優點是對稱、沒有單點失效——一個行程當了，群組變小但照常運作；缺點是決策複雜，動輒要投票，帶來延遲與額外負擔。
• 階層式群組（hierarchical group）：存在某種階層，例如一個協調者（coordinator）加上多個工作者（worker）。工作請求（無論來自外部客戶端或工作者）先送到協調者，由它決定最適合的工作者並轉發。性質恰好相反：協調者一倒全組停擺，但只要它還在，就能不驚動眾人地逕行決策。

群組成員管理#

管理群組的建立、刪除與成員進出，有兩種取向：

• 群組伺服器（group server）：所有請求送往一台伺服器，由它維護所有群組及其成員的完整資料庫。直觀、有效率、容易實作，但與所有集中式技術一樣有致命傷——單點失效。群組伺服器一當，群組管理隨之消失，多數群組恐怕得從頭重建，進行中的工作可能因此中斷。
• 分散式管理：若有（可靠）多播可用，外部行程可直接向全體成員多播「我要加入」的訊息；離開時理想上也是向所有人送一則告別訊息。

分散式管理有幾個棘手處：

• 在容錯情境下不能假設 fail-stop 語意——行程當機不會像自願離開那樣客氣地宣告。其他成員只能從「它對什麼都不再回應」實驗性地發現，確定它真的死了（而不只是慢）之後，才能將其移出群組。
• 進出必須與資料訊息同步：行程加入群組的那一刻起，必須收到所有送往該群組的訊息；離開之後則不得再收到群組訊息，其他成員也不得再收到它的訊息。一種做法是把加入／離開操作轉成一連串送往全群組的訊息，使其在訊息流中卡進正確位置。
• 若當機的機器多到群組根本無法運作，需要某種協定重建群組。總得有行程出面發起，但若兩三個同時發起呢？協定必須承受得住這種情況。

失效遮蔽與複製#

有了相同行程組成的群組，就能遮蔽群組內一或多個故障行程——用（容錯的）群組取代單一（脆弱的）行程。承接前一章，複製有兩種取向：

• 主導式協定（primary-based protocol）：容錯情境下通常是主備協定（primary-backup protocol），群組採階層式組織，由主行程協調所有寫入。主行程當機時，備援行程執行選舉演算法選出新的主行程。
• 複寫式協定（replicated-write protocol）：以主動複製（active replication）或以法定人數（quorum-based）協定的形式出現，對應扁平群組。優點是沒有單點失效，代價是分散式協調。

關鍵問題是：**需要多少複本？**若系統能承受 k 個元件故障仍符合規格，稱為 k 容錯（k fault tolerant）。

• 若行程沉默地失效（fail-silent）：k + 1 個就夠——k 個停了，剩下那個的答案照用。
• 若行程呈現拜占庭失效（帶病運作、送出錯誤或隨機回覆）：至少需要 2k + 1 個。最壞情況下 k 個故障行程可能（甚至蓄意）給出相同的錯誤答案，但其餘 k + 1 個也會給出相同的正確答案，客戶端或表決器相信多數即可。

理論上說「k 個會壞、k + 1 個不會壞」很容易，實務上卻很難有把握地劃出這條線，因此即使是容錯系統，也可能需要某種統計分析。另一個隱含前提是所有請求以相同順序到達所有伺服器（原子多播問題，atomic multicast problem）——雖然讀取不影響、部分寫入可交換而能略為放寬，一般性的問題仍在。

故障系統中的共識#

複製成群組能提升容錯，但前提是行程不會串通產出錯誤結果。許多場合需要群組達成共識（agreement）：選協調者、決定是否提交交易、分派工作、同步等等。通訊與行程都完美時共識通常不難；一旦不完美，問題就來了。

分散式共識演算法的目標：所有無故障行程在有限步數內對某議題達成一致。難處在於不同的系統假設需要不同解法，甚至可能無解。Turek 與 Shasha 區分了四個維度：

1. 同步或非同步系統：同步意指行程以鎖步（lock-step）方式運作——存在常數 c ≥ 1，使得任一行程走了 c + 1 步時，其他每個行程至少走了 1 步。
2. 通訊延遲有界或無界：有界意指每則訊息保證在全域預定的最大時間內送達。
3. 訊息遞送有序或無序：同一傳送者的訊息是否依發送順序送達。
4. 訊息傳輸採單播（unicast）或多播（multicast）。

只有部分組合能達成共識，其餘情況可證明無解。實務上多數分散式系統假設行程非同步、單播傳輸、延遲無界，因此必須仰賴有序（可靠）的訊息遞送，例如 TCP 提供的保證。

拜占庭共識問題#

這個問題最早由藍波特（Leslie Lamport）等人研究，稱為拜占庭共識問題（Byzantine agreement problem）——典故是多支軍隊要在叛變的將軍、勾結的副官環伺下，對兵力等資訊達成一致。以下是 Lamport 等人描述的解法，假設：行程同步、單播且保序、延遲有界。設有 N 個行程，行程 i 要把值 vi 提供給其他人；目標是每個行程建出長度 N 的向量 V，使得只要行程 i 無故障，V[i] = vi（否則 V[i] 未定義）。假設至多 k 個行程故障。

以 N = 4、k = 1 為例，演算法分四步：

1. 每個無故障行程 i 以可靠單播把 vi 送給其他所有行程。故障行程可以亂送——甚至對不同對象送不同值。設 vi = i：行程 1 報 1、行程 2 報 2、行程 4 報 4，行程 3 則對三人分別謊報 x、y、z。
2. 每個行程把第 1 步收到的結果彙整成向量。
3. 每個行程把自己的向量轉送給其他所有行程。行程 3 再度說謊，捏造了 12 個新值 a 到 l。於是每個行程收到三個向量。
4. 每個行程逐一檢視收到向量的第 i 個元素：若某值佔多數，就放進結果向量；若無多數，標為 UNKNOWN。結果行程 1、2、4 對 v1、v2、v4 達成一致（正確結果），而對 v3 無法決定——但這無關緊要：拜占庭共識的目標只是對無故障行程的值達成共識。

若改成 N = 3、k = 1（兩個正常、一個故障），兩個正常行程對任何元素都看不到多數，全部標為 UNKNOWN，演算法無法達成共識。

Lamport 等人證明：有 k 個故障行程時，必須有 2k + 1 個正常運作的行程才能達成共識，總數即 3k + 1——換言之，超過三分之二的行程正常，共識才有可能。

共識還可能更絕望：Fischer 等人證明，在訊息無法保證於已知有限時間內送達的分散式系統中，只要有一個行程故障（即使是沉默地失效），共識就不可能達成。癥結在於：任意慢的行程與當掉的行程無法區分——你分不出誰死誰活。

還要注意，以上方案都假設節點要嘛拜占庭、要嘛合作。當行程來自不同管理網域時，「合作」未必成立——它們更可能表現出理性（rational）行為，例如謊報逾時比執行更新便宜時就謊報。處理這類情況並不簡單，初步的方向是 BAR 容錯（Byzantine, Altruism, Rationality），由 Aiyer 等人提出。

失效偵測#

要遮蔽失效，通常得先偵測到失效——這是分散式系統容錯的基石之一。歸根結柢：群組中的無故障成員必須能判定誰還是成員、誰已經不是。

偵測行程失效基本上只有兩種機制：主動向彼此發送「你還活著嗎？」訊息（並期待回覆），或被動等待其他行程的訊息進來。後者只有在行程間通訊量足夠時才合理，實務上多採主動 ping。

大量理論工作歸結起來就是：用逾時（timeout）機制判斷行程是否失效。現實中這有兩大問題：

• 誤報（false positive）：網路不可靠，ping 沒回音不代表行程死了。若誤報導致健康的行程被踢出成員清單，顯然是做錯了。
• 逾時太粗糙：如 Birman 所指出，幾乎沒有工作在建構「不只看單一訊息沒回覆」的正規失效偵測子系統——看看業界部署的分散式系統，這點更明顯。

設計失效偵測子系統時有幾個考量：

• 失效偵測可以透過閒聊（gossiping）進行——每個節點定期向鄰居宣告自己還活著；或者作為定期交換資訊的副作用，如 Obduro 系統：行程定期以 gossip 散播服務可用性資訊，最終每個行程都掌握足夠的本地資訊來判斷誰失效了——可用性資訊過舊的成員，推定已失效。
• 理想上應能區分網路失效與節點失效。一種做法是不讓單一節點自行判定鄰居已當機：ping 逾時後，先請其他鄰居試試能否連上該節點。正面資訊也可以分享——若節點其實還活著，這個訊息可轉知其他相關方（他們偵測到的可能只是往該節點的連線失效）。