共識演算法#

共識 (Consensus) 是分散式系統最核心也最困難的問題：讓一群可能故障、訊息可能延遲或遺失的節點，對某個值達成一致的決定。選主、唯一性約束、原子提交、分散式鎖，骨子裡都是共識問題。本章先說明為什麼樸素的兩階段提交不夠、為什麼理論上共識在純非同步下不可能，再看 Raft 如何在現實中繞過這道理論障礙。

本章補的是共識與原子提交的理論面。2PC / TCC / Saga 的工程落地（補償、冪等、業務改造）見 基礎理論 — 分散式事務 與第 11 章；本章只談它們為何在理論上不夠、共識如何補上。

2PC 的致命傷：協調者故障#

兩階段提交 (2PC) 是最直觀的原子提交協定：協調者先問所有參與者「能提交嗎」（Prepare），全數同意才下「提交」指令（Commit）。問題出在參與者一旦回覆「可以」，就進入不可逆的等待——它必須等協調者的最終裁決，不能自行決定。

stateDiagram-v2
    [*] --> Working
    Working --> Prepared: 收到 Prepare 且同意
    Prepared --> Committed: 收到 Commit
    Prepared --> Aborted: 收到 Abort
    Working --> Aborted: 拒絕
    Committed --> [*]
    Aborted --> [*]

    note right of Prepared
        危險區：已承諾不能反悔，
        若協調者此刻當機，
        參與者只能無限等待（阻塞）
    end note

2PC 的致命傷：當協調者在「參與者已 Prepared」之後、「下達最終決定」之前當機，所有參與者被卡在 Prepared 狀態——既不能提交（沒收到 commit）也不能中止（怕別人已 commit），只能無限期持鎖等待協調者復活。協調者是單點，整個事務的活性繫於它一身。

這不是實作 bug，而是 2PC 的結構性缺陷：它沒有容錯的協調者。要解決，協調者本身必須做成一個容錯的共識群組——這就把問題推回到共識。

FLP 不可能定理：理論的天花板#

為什麼 2PC 無法簡單修好？因為有一條根本限制：

FLP 不可能定理：在一個純非同步（訊息延遲無上界）系統裡，只要有一個節點可能故障，就不存在能保證「一定在有限時間內達成共識」的演算法。

直覺在於：純非同步下，你無法區分「一個節點當機了」和「它只是訊息很慢」。既然分不清，演算法要嘛冒著對方其實活著的風險逕自決定（可能不一致），要嘛永遠等下去（可能不終止）。安全性與活性無法同時保證。

用 timeout 轉入「部分同步」#

FLP 說的是純非同步。現實系統靠引入逾時 (timeout) 假設，把模型放寬成部分同步 (partial synchrony)：

純非同步：訊息可能無限延遲 → FLP 適用 → 共識不可解
        ↓ 加入 timeout 假設
部分同步：訊息「最終」會在某界限內送達 → 共識可解（如 Raft、Paxos）

代價是：逾時是一種「猜測」。猜對了系統往前推進；猜錯了（把慢節點當死節點）會觸發不必要的選主，但不會破壞安全性——這是 Raft/Paxos 的關鍵設計取捨：寧可偶爾犧牲活性（多選一次主），也絕不犧牲安全性（不產生兩個主）。

Raft：把共識拆成三件事#

Raft 的設計目標是可理解性 (understandability)。它把共識拆成三個相對獨立的子問題：

flowchart LR
    A["1. 選主<br/>Leader Election"] --> B["2. 日誌複製<br/>Log Replication"] --> C["3. 安全性<br/>Safety"]

    style A fill:#ffccbc
    style B fill:#fff9c4
    style C fill:#c8e6c9

• 選主 (Leader Election)：任一時刻最多一個 leader，所有寫入都經它。每個任期 (term) 是一個遞增編號（等同 fencing token）。
• 日誌複製 (Log Replication)：leader 把指令當成日誌條目複製給 follower，多數派落地後才算 committed，再套用到狀態機。
• 安全性 (Safety)：保證只有擁有所有已 committed 條目的節點才能當選 leader，於是 committed 的內容永不丟失、永不被覆蓋。

Raft 選主流程#

stateDiagram-v2
    [*] --> Follower
    Follower --> Candidate: 選舉逾時未收到 leader 心跳
    Candidate --> Leader: 取得多數選票
    Candidate --> Follower: 發現更高 term 的 leader
    Candidate --> Candidate: 票數分裂 → 隨機逾時後重選
    Leader --> Follower: 發現更高 term

    note right of Candidate
        隨機化選舉逾時
        降低同時參選導致
        反覆票分裂的機率
    end note

follower 在「選舉逾時」內沒收到 leader 心跳，就自增 term、轉為 candidate 並拉票；拿到多數票即成為 leader，開始發心跳壓制其他候選人。隨機化逾時是避免反覆平票的小而關鍵的設計。

Paxos vs Raft：優雅 vs 可理解#

兩者解決的問題相同、安全保證相同。差別在工程友善度——這也是 Raft 後來被廣泛採用（etcd、Consul 等）的主因。「正確且可被正確實作」往往比「理論最優」更重要。

多數決容錯與節點數取捨#

共識靠多數決 (majority / quorum)：任何決定都要過半數節點同意。任兩個多數派必然相交，於是不可能同時做出兩個矛盾決定——這就是安全性的數學保證，也是防腦裂的根本（見 複製模型 — split brain）。

一個 $n$ 節點的群組可容忍的故障數為：

$$f = \left\lfloor \frac{n-1}{2} \right\rfloor$$

3 vs 5 的取捨：3 節點便宜但只能容忍 1 故障——在滾動升級（已停 1 台）期間再掛 1 台就失去多數、整個群組停寫。5 節點允許「1 維護 + 1 故障」並存，是高可用的常見折衷。節點再多並非更好：偶數無助於容錯（多數派門檻更高），且節點愈多，每次寫入要等的多數派愈大、延遲愈高。共識群組通常維持在 3 或 5。

小結#

• 2PC 的致命傷是協調者單點：參與者 Prepared 後協調者當機就無限阻塞。
• FLP 定理指出純非同步下容錯共識不可能；現實靠 timeout 轉入部分同步繞過，代價是偶爾誤判而多選一次主，但絕不犧牲安全性。
• Raft 把共識拆成選主、日誌複製、安全性三件事，以可理解性取勝；與 Paxos 安全保證等價。
• 多數決保證任兩決定相交故不矛盾；$n=3$ 省成本，$n=5$ 容「維護 + 故障」並存，節點愈多延遲愈高——共識群組通常停在 3 或 5。