回顧 Jim Gray 八篇交易論文，串起從 two-phase locking 到 Paxos Commit 的交易抽象建構史。
Philip Bernstein 回顧 Jim Gray 從 1976 到 2006 年的八篇交易論文，說明交易這個抽象是如何被一塊一塊拼起來的。1976 年他與 Eswaran、Lorie、Traiger 合寫的 CACM 論文把交易定義為保持一致性的工作單位，把 serializability 立為正確性目標，發明了 two-phase locking，並指出 phantom 問題；同年的鎖定粒度論文再補上 intention lock 與 degrees of consistency，後者日後被 SQL 改名為隔離等級。之後的論文把日誌與復原機制、atomic commitment 形式化，釐清交易 commit 問題與 Byzantine agreement 的差異，證明 ANSI SQL 的 SERIALIZABLE 其實不保證 serializable，量化了複製為何難以擴展，最後把 Paxos 與 two-phase commit 融合成 Paxos Commit。八篇連起來讀，正好走完這個領域從「並行到底怎樣才算正確」到「分散式交易要怎麼提交才不會卡住」的整段路。Bernstein 是以參與者的身分在寫：八篇之一有他的署名，他的職涯也一路跟著 Gray 的腳步走。
1976 年之前，大家已經知道對共用資料的並行讀寫會出事。兩支程式各自把共用變數 x 加 1，若兩者都在對方寫入前先讀了 x，其中一次更新就會不見；又或者一筆交易把 100 美元從帳戶 1 轉到帳戶 2，另一筆卻讀到轉帳前的帳戶 1 與轉帳後的帳戶 2，看到一個從未存在過的資料庫狀態。當時已知用鎖可以避免這些狀況，但設鎖與解鎖是應用程式自己的事，系統幾乎沒有告訴程式該鎖哪些東西、又該鎖到什麼時候。既沒有一個公認的名稱來指涉鎖所要保護的工作單位，也沒有對並行執行明確寫下的正確性準則，更沒有任何鎖定規則被證明達成了這個準則。當時的商用系統，例如 IBM 的 IMS/VS 與 UNIVAC 的 DMS 1100，各自有一套臨時拼湊的鎖定行為，Gray 的鎖定粒度論文最後一節正是在整理這些做法。
1976 年 Eswaran、Gray、Lorie、Traiger 的 CACM 論文把交易定義為一連串作用在共用狀態上的操作，該狀態由「entity」組成，例如檔案的紀錄或關聯的 tuple，並假設每筆交易單獨執行時會保持狀態的內部一致性。這個定義把設鎖的責任從應用程式開發者手上移交給系統：一旦讀寫被歸進一個有明確起點、以 commit 或 abort 收尾的一致性單位，系統就知道一把鎖該覆蓋多長的區間。1981 年的論文進一步把它類比為契約法中兩造締結的具約束力協議，並把交易性質列為 consistency、atomicity、durability，其中 isolation 被歸在 consistency 之下。commit 的意義正是交易放棄了「反悔丟棄更新」的權利，abort 則把更新全部丟掉。整個領域後續的一切，都建立在這個抽象上。
這篇論文的第二項貢獻，是明確說出並行到底怎樣才算正確：交錯執行只要與這些交易的某個序列（非交錯）執行效果相同，就算正確。這個準則之所以是對的，理由是可組合性。依假設，每筆交易單獨跑都會保持狀態一致，所以任何序列執行也一定保持一致；而實際執行若等價於某個序列執行，就免費繼承了這個保證。於是開發者永遠不必去推敲交錯的細節，只需一次思考一筆交易，而系統則可在協定容許的範圍內盡量放手交錯。
鎖定粒度論文注意到完整的 two-phase locking 往往比應用真正需要的隔離還要強，於是定義了一組較弱的鎖定協定階層，稱為 degrees of consistency，彼此的差別純粹在於讀鎖與寫鎖持有多久。十九年後 ANSI SQL-92 委員會因為必須讓非鎖定式實作也能符合規格，改以三種禁止行為來重新定義這些等級：dirty read、non-repeatable read 與 phantom。1995 年 Berenson、Bernstein、Gray、Melton 與 O'Neil 夫婦的批判論文指出，這個改寫不只是不夠優雅，而是錯的：禁掉這三種現象並不蘊含 serializability。snapshot isolation 這個真實而且流行的協定三種現象全都禁掉了，卻仍容許找不到等價序列順序的執行，因此規格中「SERIALIZABLE 等級的並行執行保證是 serializable」這句話為假。這個教訓不限於 SQL：用一張你想得到的異常清單來定義隔離，漏掉的一定是你沒想到的那些。
1981 年的論文是這個領域第一次誠實交代交易「做不到什麼」。它改以動作而非 entity 來分類：unprotected 動作在 abort 時不需要復原；real 動作，例如 ATM 吐鈔，電腦根本無法復原；只有 protected 動作才是 abort 時被復原、commit 後具持久性的。交易一旦提交，唯一能改變其效果的方式就是再跑一筆交易，這篇論文似乎是最早把它稱為 compensating transaction 的文獻。它同時比較了實作 atomicity 與 durability 的兩大路線：time-domain addressing（也就是今天的多版本，每次更新產生一個帶時間戳的新版本，時刻 t 的一致狀態由每個 entity 中時間戳不大於 t 的最大版本組成）與就地更新加日誌；最後點出三件當時仍超出技術水準的事：nested transaction、long-lived transaction，以及把交易整合進程式語言。這三項成了此後 25 年的研究議程。
1980 年的 ICALP 論文把數學部分整併起來。它依持久性把 entity 分成三類：real entity，其值無法被改變，例如已列印的輸出；stable entity，可改變且持久儲存，因此能撐過重新啟動；volatile entity，可改變但不持久，重啟即遺失。接著區分兩類失效：transaction failure，交易遺失自身狀態必須重跑；system failure，所有 volatile entity 包括每筆執行中交易的內部狀態全部遺失。把修改狀態的操作寫進日誌，復原程序就能 redo 這些更新，把系統帶回失效前不久的狀態；這篇論文是最早（甚至可能就是第一篇）形式化定義「檢查點狀態與 redo 動作必須滿足哪些條件才算復原正確」的文獻。同一篇還提出一個效能模型，顯示單一交易遇上死結的機率與並行度成線性關係，並形式化刻畫了 atomic commitment 問題，以及 Lampson 與 Sturgis 的 two-phase commit 為何滿足它。
atomic commitment 看起來像 Byzantine Generals 問題，其實不是。Gray 1986 年在 Asilomar 的短文釘出四點差異：commit 要求所有參與者做出相同決定，而不只是所有非故障者；commit 協定能容忍多種故障，包含未當機行程的訊息遺失，而 Byzantine agreement 需要 N 個行程中故障者少於 N/3；commit 協定永遠不會給出錯誤結果，Byzantine 協定一旦超過該界限就可能給錯；Byzantine 協定能在固定時間界限內給出答案，commit 協定可證明做不到，因為存活的行程可能根本不知道當機行程決定了什麼，而全體一致又是必要條件。2006 年與 Leslie Lamport 的論文則認真面對關係的另一半：既然 atomic commitment 是共識問題，就該用共識演算法來解。Paxos Commit 的洞見是，three-phase commit 其實內含兩輪共識，一輪用來得出 commit 決定，一輪用來讓該決定挺過後續失效；若改成對 prepare 決定達成共識而非對 commit 決定，這兩輪就能合而為一。
1996 年的論文攤開更新複製資料庫的四種做法，即 update-everywhere 與 primary-copy，各自搭配 eager 或 lazy 傳播，並指出其中三種擴展性都很差。update-everywhere 加 eager 傳播只要兩個節點同時更新同一筆資料就會死結，因為各自交易的遠端寫入都在等對方持有的本地鎖；決定性的比值是傳播延遲對衝突交易到達間隔，因此死結率會隨衝突率與複本數急遽上升。update-everywhere 加 lazy 傳播則把死結換成同樣頻繁的人工調解，它在 Lotus Notes 上行得通，只是因為 Notes 的更新大多是可交換的帶時間戳插入，而非覆寫。lazy primary-copy 靠 Thomas' Write Rule 收斂，只有當寫入的時間戳大於該複本已套用過的所有時間戳時才套用，但仍可能讓查詢讀到一個「較晚的寫入已到、較早的寫入未到」的節點。活下來的是 eager primary-copy，因為寫入會依 primary 的順序抵達每個複本，這也是今天分散式資料庫多半採用的做法。
交易必須在存取每個 entity 之前先取得其鎖；必須持有該鎖直到對該 entity 的存取完成之後；而且必須在釋放任何一把鎖之前取得所有需要的鎖。真正起作用的是第三條：它把每筆交易切成只取鎖的成長階段與只放鎖的收縮階段，協定的「兩階段」之名即由此而來。因為沒有交易能在放掉一把鎖之後再取新鎖，互相衝突的交易就可以依各自抵達 lock point 的時刻排序，而這個順序正是該執行所等價的序列順序。論文證明了這一點，也給了這個領域第一個並行控制協定的正確性定理。
經典反例用了 Accounts 表 [Account#, Location, Balance] 與 Assets 表 [Location, Total]，一致性條件是某地點所有帳戶餘額總和等於該地點的 Total。稽核交易 T1 鎖住所有 Location = 'Napa' 的 Accounts 列；T2 接著插入一筆新的 Napa 帳戶並把餘額加進 Napa 的 Total，提交後釋放鎖；T1 再鎖 Assets 那一列，卻發現總和對不上，儘管兩筆交易都遵守了 two-phase locking。解答是第一步裡藏著一個隱含操作，也就是 T1 用來判定哪些列屬於 Napa 的那個動作：可能是查索引，也可能是掃描整表一路讀到 end-of-table 標記。只要 T1 把那個資料項也鎖住，T2 的插入就非得更新它不可，因而會被擋下，異常也就不會發生。論文的一般解法是鎖住述詞，例如 Location = 'Napa'，或布林組合如 ((Location = 'Napa' 或 Location = 'Santa Rosa') 且 Balance < 200)，只有在同表上沒有其他交易持有與之互相可滿足的 predicate lock 時才准予；這個做法精確，但一般情況下計算代價極高。
可鎖定的 entity 被組織成階層，例如資料庫、區域（磁碟卷）、檔案、紀錄，對某層 entity 上鎖即隱含鎖住其所有後代。為了避免粗粒度的 S 或 X 鎖與別的交易在後代上的 X 鎖共存，協定引入 intention 模式：對 entity e 的 IS 鎖宣告持有者在 e 之下持有或將持有 S 鎖，IX 鎖則宣告 e 之下的 X 鎖。因此 e 上的 IS 與 X 不相容，IX 與 S、X 都不相容；想鎖紀錄的交易必須先對檔案上 intention 鎖，而任何想整檔上鎖的交易就在這一層被擋住。SIX 模式把對該 entity 本身的共享存取與對後代設 X 鎖的權利結合起來，正好是「讀完整個檔案、只更新其中一部分」這種交易所需要的。論文也處理階層是有向無環圖而非樹的情形，例如一筆紀錄既能靠掃描檔案取得、也能靠某欄位上的索引取得，並討論更新把紀錄從一個索引區間搬到另一個區間、因而可能製造 phantom 時該怎麼辦。
degree 0 只在執行更新的當下持有 X 鎖，屬於 short duration lock，提交前就放掉；這同時容許讀取與覆寫 dirty 資料，因此 T1 一旦 abort，讀過它的 T2 必須連帶 abort，而若 T2 已經提交就落入兩難：它的更新照理應永久生效，卻又因為讀到無效資料而該被撤銷。degree 1 把 X 鎖改為 long duration lock，持有到提交之後，阻止交易覆寫 dirty 資料，也免去同一 entity 上一長串未提交更新所需的複雜記帳。degree 2 再要求每次讀取前取得 short duration 的 S 鎖，確保只讀到已提交的資料，就是今天所稱的 Read Committed。degree 3 把該 S 鎖升為 long duration，此時交易完全符合 two-phase locking，因而（撇開 phantom 問題）是 serializable；在標準的命名裡它是 Repeatable Read，在 Gray 的說法裡則是 Serializable。
每筆交易開始時取得起始時間戳 st，若成功提交則取得大於先前所有已配發值的提交時間戳 ct，並附加到它寫過的每一個版本上。讀取某 entity 時取回提交時間戳不大於 st 之中最大的那個版本，因此交易看到的是一份凍結的已提交狀態快照，完全不受並行活動影響，這也是它能避開標準所定義的 dirty read、non-repeatable read 與 phantom 的原因。提交時系統檢查該交易寫過的每個 entity，只要其中任一個被某個提交時間戳大於 st 的交易更新過就令其 abort，這就是 first-writer-wins 規則，用來擋掉一般的遺失更新競態。真正漏網的是 write skew：T1 與 T2 從同一份快照讀了 X 和 Y，T1 寫 X、T2 寫 Y，誰都沒讀到對方寫的東西，兩者都提交；任何序列順序都重現不了這個結果，因為在序列執行中總有一方會讀到另一方的輸出。
1996 年論文針對離線運作提出的方案，把節點分成 base node 與 disconnected node：前者持有完整資料庫並彼此常時連線，後者通常只持有部分資料且僅偶爾連線。每個資料項都有指定的 primary copy，可能落在任一種節點上。disconnected node N 可以執行任何只讀寫 N 上資料的交易，但若該交易讀取的某項資料其 primary copy 不在 N，交易就以 Tentative Mode 執行。重新連線時，N 先丟棄由 Tentative 交易寫下的版本，反正調解後會重新更新；接著把 Tentative 交易與非 Tentative 交易的結果送給 base node，同時接收 base node 送來的複本更新，這些更新一律是非 Tentative 的。base node 收下後先把非 Tentative 的結果寫進自己的本地複本，再對 primary copy 重跑每一筆 Tentative 交易；只要新輸出與原本執行結果不同，就套用一個應用層自訂的驗收測試，通過就安裝更新並把結果回傳給 N，未通過則回傳診斷訊息。
傳統 two-phase commit 有 transaction manager（TM）與 resource manager（RM）：TM 對所有 RM 送出 Prepare-Request，每個 RM 把交易更新寫入持久儲存後回覆 Prepared，TM 再把決定寫入持久儲存並送出 Commit，無故障情況下共三個單向訊息延遲。three-phase commit 加入備援 TM，又多兩個延遲，因為主 TM 必須先通知備援並收齊確認才能告知 RM。Paxos Commit 改成讓每個 RM 各自擁有一個跑在共用 acceptor 集合上的 Paxos instance：leader 送出 Prepare-Request，每個 RM 把 Prepared 直接送給 acceptor，每個 acceptor 再把 Prepared 轉給 leader；當 leader 對每一個 RM 都收到過半數 acceptor 回報 Prepared，交易即告提交並送出 Commit。這樣只有四個訊息延遲，比 three-phase commit 少一個；而「過半 acceptor 接受了 Prepared」這件事取代了 TM 把決定寫入儲存，acceptor 本身則扮演備援 TM 的角色。由於每個 acceptor 同時參與所有 RM 的 instance，它可以批次處理，等收齊所有 RM 的 Prepared 後只送一個訊息給 leader；另一個最佳化是讓 acceptor 把 Prepared 送給所有 RM，由每個 RM 自行做出提交決定，以較多訊息換取少一個延遲。
多粒度鎖定成了幾乎每一套 SQL 資料庫系統的標準配備，而 degrees of consistency 則被改寫成 ANSI SQL-92 的隔離等級，Read Committed 與 Repeatable Read 的名字就是這樣來的。1995 年的批判論文改寫了該標準的名聲，也開啟了一條研究路線，最終在 2008 年由 Cahill、Rohm 與 Fekete 提出 serializable snapshot isolation，PostgreSQL 便以它實作 SERIALIZABLE 等級；相對地 Oracle 至今仍把純粹的 snapshot isolation 標示為 SERIALIZABLE，正是那篇論文預言的混淆。1981 年提出的 compensating transaction 在 Garcia-Molina 與 Salem 手中成為 sagas，如今是 workflow 引擎與微服務編排器的失效模型；ACTA 框架的 commit-abort dependency 則負責 workflow 內部步驟的順序約束。Gray 堅持交易應該進入程式語言，催生了 Barbara Liskov 的 Argus，以及很久之後的 transactional memory。Paxos Commit 把「每個 resource manager 進入 prepared 狀態」當作獨立共識問題的行程結構，是 MDCC、Replicated Commit、Carousel、TAPIR 的 inconsistent replication、Ocean Vista 與 Cornus 的直系祖先，也是 Google Spanner 在正式環境中以 Paxos 群組承載 two-phase commit 的思路來源。而在這一切背後，Gray 與 Reuter 1993 年的《Transaction Processing: Concepts and Techniques》至今仍是實作者動手打造這些機制時會翻開的那本書。
“With his many collaborators, Jim created transactions as one of the foundational abstractions of software.”
“This arises because T2 is a phantom row, i.e., it comes and goes like a ghost.”
“The insight in Paxos Commit is that these two consensus rounds can be combined into one by reaching consensus on the prepare decision rather than the commit decision.”