1981 - 葛雷交易 ACID（容錯資料庫的理論基石）#

案件摘要#

1981 年，Jim Gray（1944–2007） 在 Tandem Computers 發表 The Transaction Concept: Virtues and Limitations—— 把「交易（transaction）」變成資料庫的核心概念，並定義了後世稱為 ACID 的四性：

\[ \boxed{\text{原子性 Atomicity・一致性 Consistency・隔離性 Isolation・持久性 Durability}} \]

Gray 的問題：磁碟會壞、系統會崩、併發會亂——

\[ \text{崩潰} + \text{併發} + \text{錯誤} = \text{資料一定會壞（除非有交易）}. \]

他的解法： - 交易日誌（write-ahead log, WAL）：先寫日誌，才能重做（redo）/復原（undo）； - 兩階段提交（two-phase commit, 2PC）：讓分散式交易原子性地「全成或全敗」。

\[ \text{WAL（日誌）} + \text{2PC（提交協議）} = \text{崩潰也壞不了的資料庫}. \]

1998 年，Gray 獲圖靈獎——表彰他在交易處理與資料庫 的奠基性貢獻。 2007 年，他在海上失蹤——駕帆船散撒母親骨灰， 至今下落不明。天才與大海，成了資訊科學最悲傷的懸案。

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

系統崩潰與磁碟錯誤的現實（1970s）： 1970 年代的資料庫（IMS、System R 原型、早期 Oracle V2）有個致命傷：

\[ \boxed{\text{「正在寫一半時崩潰」= 資料庫壞掉}} \]

轉帳：A 扣款成功、B 加款還沒寫——崩潰→錢消失了；
磁碟壞軌：寫到一半的資料殘缺不全。

\[ \text{轉帳兩步} \xrightarrow{\text{崩潰在中間}} \text{錢憑空消失}. \]

Gray 在 IBM（1971–1980）研究的就是這個—— 他主持 System R 的交易處理，提出「事務的原子性需要日誌」。 - Codd 的關聯式模型（1970）：關聯式資料庫（見 1970-科德關聯式資料庫.md）解決了「怎麼查」， 但沒解決「怎麼在崩潰中活下來」——

\[ \text{Codd（1970）：怎麼查} \xrightarrow{\text{Gray（1981）：怎麼不壞}} \text{完整的資料庫}. \]

併發的亂象（1970s）：多個用戶同時讀寫：髒讀（dirty read）、不可重複讀、幻影讀—— 需要隔離。Gray 把這些亂象系統化為隔離等級。
分散式的需求（1980）： Tandem 的 NonStop 系統（容錯電腦）需要跨機器的交易—— 一筆交易涉及兩台機器的資料：兩邊都要成功，否則都不算。

\[ \text{單機交易} \xrightarrow{\text{跨機器}} \text{需要提交協議（2PC）}. \]

Oracle V2 的商業化（1979）：見 1979-甲骨文ORACLE.md——商業資料庫誕生， 但它的交易處理簡陋——市場需要 Gray 的理論落地。
Gray 的洞察（1981）：

\[ \text{「交易是資料庫的 atom——四性缺一不可」} \]

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

第一條線索：ACID 四性的定義#

交易（transaction）：一組不可分割的操作， \(T = \{op_1, op_2, \ldots, op_n\}\) ：

\[ \boxed{ \begin{aligned} &\textbf{A}：\text{全部執行或全部不執行（all-or-nothing）}\\ &\textbf{C}：\text{從一個一致狀態到另一個一致狀態}\\ &\textbf{I}：\text{併發交易互不干擾}\\ &\textbf{D}：\text{提交後，崩潰也丟不了} \end{aligned}} \]

A（原子性）： \(\neg(\text{部分執行})\) ——轉帳的扣款與入款同進退；
C（一致性）： \(\Sigma(\text{餘額})\) 在交易前後不變；
I（隔離性）：併發執行的結果 \(\equiv\) 某種序列執行（serializable）；
D（持久性）：COMMIT 之後，停電也丟不了。

第二條線索：交易日誌（WAL）的不變量#

Gray 的核心：先寫日誌，再改資料（write-ahead）：

\[ \boxed{\text{WAL 不變量：日誌記錄必須先於資料頁落盤}} \]

每筆日誌記錄： \((T, \text{欄位}, \text{舊值}, \text{新值})\) ：

\[ \langle T_1, A, 1000, 700\rangle,\ \langle T_1, B, 500, 800\rangle \]

崩潰後的恢復： - redo（重做）：日誌裡有 COMMIT 記錄的交易——新值重放； - undo（復原）：沒有 COMMIT 的交易——用舊值回滚。

\[ \text{恢復} = \text{undo（未提交）} + \text{redo（已提交）} \]

為什麼日誌要先寫？

\[ \text{若資料先寫、日誌後寫} \xrightarrow{\text{崩潰在中間}} \text{改了資料卻沒日誌——無法復原！} \]

\[ \text{若日誌先寫} \xrightarrow{\text{崩潰在中間}} \text{日誌有舊值——可以 undo。} \]

第三條線索：兩階段提交（2PC）的狀態機#

分散式交易： \(T\) 涉及 \(k\) 台機器（participants），由協調者（coordinator）指揮：

\[ \text{協調者} \xrightarrow{\text{Phase 1: PREPARE}} \text{參與者們} \]

狀態機： - Phase 1（prepare）：協調者問「你準備好了嗎？」參與者寫好日誌、鎖住資源，回 YES / NO； - Phase 2（commit/abort）： - 全部 YES → 協調者寫 COMMIT 日誌 → 廣播 COMMIT； - 任一 NO（或逾時）→ 廣播 ABORT。

\[ \text{INIT} \xrightarrow{\text{PREPARE}} \text{PREPARED} \xrightarrow{\text{全部 YES}} \text{COMMITTED}；\quad \text{PREPARED} \xrightarrow{\text{任一 NO}} \text{ABORTED} \]

2PC 的保證：

\[ \boxed{\text{全部參與者要么都 COMMIT，要么都 ABORT——原子性跨機器成立}} \]

2PC 的代價：參與者在 PREPARED 狀態要等協調者（鎖住資源）—— 協調者掛了，全部卡住（Gray 指出的 limitation）—— 這個缺陷的解法要等 30 年後的 Spanner（2012，伏筆）。

Python：簡化版交易日誌模擬（銀行轉帳 + 崩潰 + 重播復原）#

# 1) 交易日誌（write-ahead log）：先寫日誌，才能重做（redo）/復原（undo）
import json

accounts = {"A": 1000, "B": 500}
log = []   # 交易日誌：每筆記錄 (交易ID, 帳戶, 舊值, 新值)

def transfer(tid, src, dst, amt):
    """轉帳：先寫 WAL，再改資料（WAL 不變量：日誌先落盤）"""
    old_s, old_d = accounts[src], accounts[dst]
    log.append((tid, src, old_s, old_s - amt))
    log.append((tid, dst, old_d, old_d + amt))
    # ——— 日誌已落盤（模擬 write-ahead）———
    accounts[src] = old_s - amt
    accounts[dst] = old_d + amt

def replay():
    """崩潰後重播日誌：依日誌把每個帳戶推進到最後的新值"""
    latest = {}
    for tid, acct, old, new in log:
        latest[acct] = new
    for acct, new in latest.items():
        accounts[acct] = new

print("轉帳前：", accounts)
transfer("T1", "A", "B", 300)
print("T1 轉帳 300（已寫 WAL 2 筆）：", accounts)
transfer("T2", "B", "A", 100)
print("T2 轉帳 100（已寫 WAL 2 筆）：", accounts)

# 2) 模擬崩潰：記憶體資料消失，只剩日誌（磁碟上的 WAL）
crashed = dict(accounts)
accounts.clear()
print("\n=== 系統崩潰！記憶體歸零，只剩交易日誌 ===")
for tid, acct, old, new in log:
    print(f"  日誌：{tid} {acct} {old} → {new}")

# 3) 重播日誌（redo）：資料庫恢復到崩潰前的狀態
replay()
print("重播日誌後復原：", accounts)
print(f"與崩潰前一致？{accounts == crashed}（持久性 Durability ✓）")
print(f"總額不變（1000+500=1500）？{sum(accounts.values()) == 1500}（一致性 ✓）")

輸出：

轉帳前： {'A': 1000, 'B': 500}
T1 轉帳 300（已寫 WAL 2 筆）： {'A': 700, 'B': 800}
T2 轉帳 100（已寫 WAL 2 筆）： {'A': 800, 'B': 700}

=== 系統崩潰！記憶體歸零，只剩交易日誌 ===
  日誌：T1 A 1000 → 700
  日誌：T1 B 500 → 800
  日誌：T2 B 800 → 700
  日誌：T2 A 700 → 800
重播日誌後復原： {'A': 800, 'B': 700}
與崩潰前一致？True（持久性 Durability ✓）
總額不變（1000+500=1500）？True（一致性 ✓）

結案 -- 後果與影響#

ACID 成為教科書標準：

\[ \boxed{\text{ACID（Gray 1981）：每本資料庫課本的必備詞彙}} \]

有趣的是：Gray 本人的論文裡沒有出現「ACID」這個縮寫—— 是 1983 年 Härder 與 Reuter 的論文把四性縮寫成 ACID—— Gray 提出概念，後人取了名字。 - WAL 成為一切容錯系統的基礎：

\[ \text{WAL（1981）} \xrightarrow{} \text{DB2・PostgreSQL・SQLite・Kafka・etcd} \]

日誌是真相（the log is the truth）—— 先寫日誌再改狀態的模式，從資料庫蔓延到一切分散式系統。 - 2PC 與分散式交易的基礎：

\[ \text{2PC（1981）} \xrightarrow{\text{XA 標準（1991）}} \text{分散式交易的工業標準} \]

2PC 的缺陷（協調者單點卡住）啟發了後續研究—— 三階段提交（3PC）、Paxos（Lamport）、Raft—— 最終的答案之一是 Google Spanner（2012，伏筆）：用 GPS 時鐘與 Paxos 做全球分散式交易—— 見 2012-谷歌Spanner全球資料庫.md（稍後建立）。 - 圖靈獎（1998）：

\[ \text{交易處理（1970s–1981）} \xrightarrow{\text{1998}} \text{圖靈獎} \]

表彰：資料庫與交易處理研究的開創性貢獻—— Gray 是繼 Codd（1981，見 1970-科德關聯式資料庫.md）之後資料庫界的第二位圖靈獎得主。 - 大數據的先知（1985–2007）： Gray 晚年提出第四範式（data-intensive science）——

\[ \text{實驗・理論・模擬} + \boxed{\text{資料密集科學（第四範式）}} \]

他主導的 SkyServer（SDSS 天文資料庫）是科學大數據的先驅—— 把資料庫技術還給了科學。 - 海上失蹤（2007）： 2007 年 1 月 28 日，Gray 獨駕 40 呎帆船 Tenacious，從舊金山出海散撒母親的骨灰——從此人間蒸發。 - 海巡隊搜救 4 天（面積數十萬平方公里）——無果； - 同僚動用衛星影像搜尋（Amazon Mechanical Turk 眾包）——無果；

\[ \text{資料密集科學的先知} \xrightarrow{\text{被自己的技術搜尋}} \text{大海無言}. \]

至今下落不明——帆船殘骸 2009 年被發現，但人未尋獲。 這是資訊科學最悲傷的懸案之一。 - 理論的迴響：

\[ \text{圖靈機（1936）：可計算} \xrightarrow{} \text{Codd（1970）：可查詢} \xrightarrow{} \text{Gray（1981）：不會壞} \xrightarrow{} \text{Spanner（2012）：全球分布}. \]

每個時代的問題都不同——但答案都疊在前人的答案上。

關鍵人物與文獻#

J. Gray：The Transaction Concept（1981）；WAL 與 2PC（1970s–1981）； The Fourth Paradigm（2009，遺作）；1998 圖靈獎；2007 海上失蹤。
E. F. Codd：關聯式模型（1970）——1981 圖靈獎（Gray 的前輩）。
A. Reuter & G. Härder：Principles of Transaction-Oriented Database Recovery（1983）——ACID 縮寫的誕生。
Tandem Computers：NonStop 系統——2PC 的工程搖籃。
J. Helland：Gray 在 Tandem/Microsoft 的同事——分散式交易的後續傳承者。
相關案件：1979-甲骨文ORACLE.md、1970-科德關聯式資料庫.md、 2012-谷歌Spanner全球資料庫.md（稍後建立）、../資訊科學/1936-圖靈機.md。