2000 - 布魯爾 CAP 定理（分散式系統的三選二難題）#

案件摘要#

2000 年，Eric Brewer（1967–） 在 PODC（分散式計算原理研討會）的主題演講中提出 CAP 猜想：

\[ \boxed{C,\ A,\ P \text{ 只能三選二（網路分區時）}} \]

C（Consistency，一致性）：所有節點看到同一份資料；
A（Availability，可用性）：每個請求都得到回應；
P（Partition tolerance，分區容錯）：網路斷線（分區）時系統仍能運作。

Brewer 的洞察：在真實的分散式系統中，網路分區必然發生，所以 P 是必選項——真正的選擇是：

\[ \text{分區時：選 } C \text{（拒絕服務）} \quad\text{或}\quad \text{選 } A \text{（接受不一致）}. \]

2002 年，MIT 的 Seth Gilbert 與 Nancy Lynch 用嚴格證明把猜想變成定理—— 這是 NoSQL 運動的理論憲章： 在分散式世界裡，「完美」不存在，你必須選擇犧牲什麼。

前因 -- 為什麼會有這個案子#

交易的 ACID（1981）： Jim Gray 定義了交易（transaction）的 ACID 保證（見 1981-葛雷交易ACID.md）：原子性、一致性、隔離性、持久性—— 這是單機資料庫的黃金準則。

\[ \text{ACID（1981）：單機的完美} \xrightarrow{\text{分散式化}} \text{CAP（2000）：分區的取捨}. \]

分散式系統的興起（1980s–1990s）：資料量大到一台機器裝不下，資料必須複製（replication）與分片（sharding） 到多台機器——但網路會斷線，節點會當機。
蘭波特的邏輯時鐘（1978）： Leslie Lamport 證明分散式系統中沒有全域時間，只有事件序（happened-before） （見 ../資訊科學/1978-蘭波特邏輯時鐘.md）—— 「所有節點看到同一份資料」這件事，從數學上就很難。
Brewer 的戰場（1995–2000）： Brewer 創辦的 Inktomi（搜尋引擎，1996）經營數百台伺服器的叢集—— 他親眼看過無數次網路分區：

\[ \text{分區發生} \Rightarrow \text{要麼停機（保一致性）}\text{，要麼髒資料（保可用性）}. \]

學術界還在追求「完美一致性」，工程界早已在取捨中掙扎—— Brewer 把這個掙扎提煉成定理。 - Web 規模的壓力（1999–2000）： eBay、Amazon 的流量證明：可用性比一致性更有商業價值—— 「網站掛 5 分鐘」比「資料晚 5 秒同步」貴得多。

線索與推理 -- 數學式、程式、理論#

第一條線索：CAP 的形式化（Gilbert–Lynch, 2002）#

系統模型：資料複製在節點集合 \(\{n_1, \dots, n_k\}\) 上， - 一致性（C）：任何讀操作都回傳最近一次寫入的值（線性一致性，linearizability）； - 可用性（A）：每個收到（非當機）節點的請求必須回應； - 分區容錯（P）：網路可任意丟棄節點間的訊息（分區）。

定理（Gilbert–Lynch, 2002）：

\[ \boxed{\text{不存在同時滿足 } C \text{、} A \text{、} P \text{ 的分散式系統}} \]

第二條線索：分區時 C 與 A 不可兼得的證明直覺#

反證法（兩節點 \(n_1, n_2\) ，分區切斷兩者）： 1. 客戶端向 \(n_1\) 寫入 \(v = w_2\) （寫操作）；分區使 \(n_2\) 收不到這次寫入； 2. 客戶端向 \(n_2\) 讀取—— - 若系統選 A： \(n_2\) 必須回應，但它只有舊值 \(w_1\)

\[ \Rightarrow \text{回傳 } w_1 \ne w_2 \Rightarrow \text{違反 } C； \]

若系統選 C： \(n_2\) 拒絕回應（或回傳錯誤）

\[ \Rightarrow \text{違反 } A. \]

矛盾！分區時 \(C\) 與 \(A\) 不可兼得：

\[ \text{分區} \Rightarrow (C \wedge A) = \bot \quad\Rightarrow\quad \boxed{\text{選 } CP \text{ 或 } AP} \]

第三條線索：BASE——對 ACID 的叛變#

Brewer 的藥方：放棄 ACID，改用 BASE： - Basically Available（基本可用）； - Soft state（軟狀態：允許暫時不一致）； - Eventually consistent（最終一致性：分區癒合後收斂）。

\[ \text{ACID：每個時刻都一致} \quad\text{vs.}\quad \text{BASE：最終收斂}. \]

最終一致性的數學直覺：若分區期間節點各自累積寫入 \(\Delta_1, \Delta_2\) ，癒合後同步 \(\Delta_1 \cup \Delta_2\) ：

\[ \lim_{t \to \infty} \text{state}(n_1, t) = \lim_{t \to \infty} \text{state}(n_2, t) = \text{state}^{*}. \]

這是 2007 年 Amazon Dynamo 的設計藍圖（伏筆：2007-迪納摩Dynamo.md）。

Python：模擬兩節點分區時的取捨#

（同一個雙節點叢集，分區時分別走 CP（拒絕寫入，保一致）與 AP（各自接受寫入，最終收斂）兩種模式。）

import copy

class Node:
    def __init__(self, name):
        self.name = name
        self.data = {"x": "v1"}

class Cluster:
    def __init__(self):
        self.nodes = [Node("節點1"), Node("節點2")]
        self.partitioned = False

    def write(self, node, key, value, mode):
        """mode='CP'：分區時拒絕寫入（保一致性）；
           mode='AP'：分區時各自接受寫入（保可用性）"""
        if self.partitioned and mode == "CP":
            return f"  {node.name}：分區中，拒絕寫入 {key}={value}（保 C）"
        node.data[key] = value
        return f"  {node.name}：接受寫入 {key}={value}"

    def read(self, node, key):
        if self.partitioned:
            return f"  {node.name}：分區中讀 {key} → {node.data[key]}"
        return f"  {node.name}：讀 {key} → {node.data[key]}"

    def heal(self):
        """分區癒合：AP 模式下同步資料（最終一致性）"""
        merged = {}
        for n in self.nodes:
            merged.update(n.data)
        for n in self.nodes:
            n.data = copy.deepcopy(merged)
        self.partitioned = False

def demo(mode):
    print(f"\n===== 模式 {mode}P（分區時選 {'C 一致性' if mode == 'C' else 'A 可用性'}）=====")
    c = Cluster()
    print("正常狀態：")
    print(c.read(c.nodes[0], "x"))
    c.partitioned = True
    print("分區發生（節點1 與 節點2 斷線）：")
    print(c.write(c.nodes[0], "x", "v2", mode + "P"))
    print(c.write(c.nodes[1], "x", "v3", mode + "P"))
    print("分區中讀取：")
    print(c.read(c.nodes[0], "x"))
    print(c.read(c.nodes[1], "x"))
    if mode == "A":
        c.heal()
        print("分區癒合，同步資料（最終一致性）：")
        print(c.read(c.nodes[0], "x"))
        print(c.read(c.nodes[1], "x"))
    return c

# CP：分區時一致但拒絕服務
c1 = demo("C")
print("\nCP 結論：資料一致，但分區時寫入被拒（可用性受損）")

# AP：分區時可用但短暫不一致，癒合後收斂
c2 = demo("A")
print("\nAP 結論：分區時持續服務，但 v2/v3 暫時並存（一致性受損）")
print("→ CAP：分區必然發生，C 與 A 只能選一個 ✓")

輸出：

===== 模式 CP（分區時選 C 一致性）=====
正常狀態：
  節點1：讀 x → v1
分區發生（節點1 與 節點2 斷線）：
  節點1：接受寫入 x=v2
  節點2：分區中，拒絕寫入 x=v3（保 C）
分區中讀取：
  節點1：分區中讀 x → v2
  節點2：分區中讀 x → v1

CP 結論：資料一致，但分區時寫入被拒（可用性受損）

===== 模式 AP（分區時選 A 可用性）=====
正常狀態：
  節點1：讀 x → v1
分區發生（節點1 與 節點2 斷線）：
  節點1：接受寫入 x=v2
  節點2：接受寫入 x=v3
分區中讀取：
  節點1：分區中讀 x → v2
  節點2：分區中讀 x → v3
分區癒合，同步資料（最終一致性）：
  節點1：分區中讀 x → v3
  節點2：分區中讀 x → v3

AP 結論：分區時持續服務，但 v2/v3 暫時並存（一致性受損）
→ CAP：分區必然發生，C 與 A 只能選一個 ✓

結案 -- 後果與影響#

NoSQL 運動的理論基礎（2005–2010）：

\[ \boxed{\text{CAP 定理 = NoSQL 的「憲法」}} \]

Brewer 的演講為 NoSQL 運動提供了正當性：放棄部分一致性不是偷懶，而是數學上的必然——

\[ \text{CAP（2000）} \xrightarrow{\text{Dynamo（2007）}} \text{NoSQL 運動（2009–）}. \]

（分散式設計的細節見 2007-迪納摩Dynamo.md。） - CP vs AP 的陣營圖： - CP：HBase、MongoDB（多數配置）、ZooKeeper——分區時寧可停機； - AP：Dynamo、Cassandra、CouchDB——分區時寧可髒資料； - 單機 RDBMS（CA，見 1981-葛雷交易ACID.md）：分區直接整個系統失效。 - BASE 對 ACID（2000s）： 最終一致性成為 Web 規模系統的標準哲學—— Amazon 購物車、DNS、Facebook 的社會圖譜全部是 BASE 系統。 - 分散式系統設計的必修定理：

\[ \text{CAP（2000）} \xrightarrow{\text{教科書化}} \text{每個後端工程師的常識}. \]

後續發展：PACELC（Abadi, 2012）——即使不分區（Else）， 延遲（Latency）與一致性也要取捨。 - Brewer 的後續： Brewer 回到 Berkeley 後投入 MAP（2004）與 RISC-V（2010–）； 2002 年圖靈獎得主 Nancy Lynch（Gilbert–Lynch 證明的共同作者）是分散式計算理論的一代宗師。 - 歷史定位：Brewer 是分散式世界的 Gray 傳人—— Gray 定義了單機的完美（ACID），Brewer 定義了分佈的現實（CAP）；

\[ \text{ACID（1981）} \xrightarrow{\text{分散式}} \text{CAP（2000）} \xrightarrow{} \text{BASE + NoSQL（2009）}. \]

這一切的理论基礎仍源自圖靈機（見 ../資訊科學/1936-圖靈機.md），而蘭波特的邏輯時鐘（見 ../資訊科學/1978-蘭波特邏輯時鐘.md）是它的序章。

關鍵人物與文獻#

Eric Brewer：CAP 猜想（PODC 2000 演講）；Inktomi 創辦人；Berkeley 教授。
Seth Gilbert、Nancy Lynch：Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services（SIGACT News, 2002）——證明 CAP。
Jim Gray：交易 ACID（1981，見 1981-葛雷交易ACID.md）——單機的完美。
Leslie Lamport：邏輯時鐘（1978）——分散式時間的本質（見 ../資訊科學/1978-蘭波特邏輯時鐘.md）。
相關案件：1981-葛雷交易ACID.md、2007-迪納摩Dynamo.md（伏筆）、 2005-斯東布雷克柱狀儲存.md、1995-MySQL開源資料庫.md、 ../資訊科學/1978-蘭波特邏輯時鐘.md、../資訊科學/1936-圖靈機.md。