先協商，再取鎖
Calvin 的核心動作，是把所有跨機器的協商都放在交易邊界之外完成，也就是在取鎖與開始執行之前。一旦各機器對於要執行哪些交易、以什麼順序執行達成共識，這個計畫就具有約束力：節點故障之類的非決定性問題不能造成中止，因為失敗節點可由執行同一份計畫的複本頂替，或事後重播計畫歷史。協商因此不再是持鎖期間必須繳的稅，而變成一個前置步驟，其延遲永遠不會進入 contention footprint。這正是 Calvin 能跨洲付出 Paxos 成本卻不損失任何交易吞吐量的原因。
一口氣講完 — 整篇論文的濃縮
分散式交易之所以昂貴，主因不在 CPU 或頻寬，而在於兩階段提交逼迫每個參與節點在數個網路來回期間持續握著鎖，因此少數幾筆熱門紀錄就足以扼住整個叢集的吞吐量。Calvin 的作法是把所有協商都移到取鎖之前：分散式的 sequencing 層以 10 毫秒為一個 epoch 收集交易請求、複寫這些輸入（非同步或透過 Paxos），並產生一個所有複本都遵循的全域序列。接著由分割式的決定性鎖管理器嚴格依該順序發放鎖，工作執行緒以五個階段執行、單向轉送遠端讀取結果，於是節點當機這類非決定性事件永遠不會迫使交易中止，也就不需要任何提交協定。由於只記錄並重播輸入，實體 REDO 日誌完全消失，checkpoint 也能非同步地對齊全域順序中的一個虛擬一致點來擷取。在 100 台 EC2 節點上，Calvin 跑出接近每秒五十萬筆的 TPC-C New Order 交易，與當時 Oracle 在高階硬體上創下的 504,161 筆世界紀錄相當。
在這篇論文之前 — 它所降落的世界
到了 2012 年，主流的擴展答案其實是放棄交易：Dynamo、MongoDB、CouchDB 與 Cassandra 完全不提供交易，Bigtable 只支援單列更新，Azure、Megastore 與 Oracle NoSQL Database 則把交易限制在資料庫的一小塊預先指定範圍內。少數保留完整 ACID 的系統如 VoltDB，作法是一旦交易跨越分割就停止或限制並行執行。真正需要跨分割原子性的人，只能回到 1980 年代 System R* 的設計：提交時所有參與者一邊握著全部的鎖、一邊跑兩階段提交。另一條並行的趨勢則以 CAP 為由弱化複寫一致性，不過這股潮流當時已在反轉，Megastore 與 IBM Spinnaker 都改採 Paxos 同步複寫。Calvin 的作者先前也做過決定性資料庫的原型，但那些原型仰賴單一節點的 sequencer，而且假設整個資料庫都放得進主記憶體。
問題 — 當時真正壞掉的地方
- System R* 式的分散式交易在提交時必須在所有參與者之間跑一套協商協定，而隔離性又要求所有的鎖都必須撐過整個協定期間。
- 兩階段提交需要所有參與機器之間多次網路來回，執行協定的時間往往遠超過真正跑完交易邏輯所需的時間。
- 論文把這個量稱為 contention footprint（競爭足跡）；當少數熱門紀錄反覆被分散式交易碰到，這些紀錄上多出來的持鎖時間會徹底摧毀整體吞吐量。
- 在悲觀並行控制下開放分散式交易，還會引入分散式死結，偵測後被迫中止與重啟，同樣拉高延遲、侵蝕吞吐量。
- 正因為代價如此沉重，多數可擴展系統乾脆拿掉交易支援，把原子性與隔離性丟回給應用程式開發者，換來的是複雜的程式碼與緩慢的用戶端排程。
- 先前的決定性資料庫原型以 echo server 形式實作單一節點 sequencer，既是單點故障也是固定的吞吐量天花板，而且只適用於完全放在主記憶體中的資料庫。
核心概念 — 主要貢獻，以及它們為何成立
決定性消滅了兩階段提交
兩階段提交存在的主要理由，是偵測某個參與者無法在本地提交，而原因可分為硬體故障這類非決定性事件，以及庫存歸零就中止這類決定性邏輯。如果有一個活躍複本正平行執行完全相同的交易序列，其他節點就不必等待當機節點復原，非決定性故障也就不再構成中止的理由。決定性中止同樣不需要完整的協商協定：每個節點只需等待所有可能決定性中止的節點送來一則單向訊息，收到後即可提交。拿掉這些來回之後，每筆分散式交易的 contention footprint 縮到大約只剩交易邏輯真正執行的時間。
保有並行度的決定性鎖定
先前主張決定性執行的作法，多半是在每個節點以單一執行緒序列化執行交易，只要有交易卡住，吞吐量就白白流失。Calvin 改用一個行為近似 strict two-phase locking 的鎖管理器，再加上兩條把衝突解決綁死在 sequencer 順序上的不變條件。由於互相衝突的交易只能依既定順序取得鎖，不衝突的交易則自由前進，執行結果在邏輯上等價於全域序列順序，同時仍有大量交易在工作執行緒池中並行執行。並行度被保留下來，被決定性化的只有衝突的解決方式。
複寫輸入，而非效果
因為排程是決定性的，兩個複本吃進相同的輸入序列就會走過相同的資料庫狀態序列，所以 Calvin 複寫的是成批的交易請求，而不是它們產生的寫入。這讓強一致複寫便宜得多：Megastore 與 Spinnaker 必須用 Paxos 複寫交易效果，Calvin 只需要對輸入達成 Paxos 共識。也因此，複寫模式的選擇純粹是延遲上的取捨——非同步 master-slave、資料中心內的 Paxos、或跨洲的 Paxos——對吞吐量完全沒有影響。而這些主動複寫的節點同時就是讓無中止執行成為可能的故障轉移機制。
sequencer／scheduler／storage 三層解耦
Calvin 把系統拆成三層：sequencing 層決定全域輸入順序並負責複寫與日誌，scheduling 層負責鎖定與執行的調度，storage 層則在單純的 CRUD 介面後面掌管實體資料佈局。三層都在 shared-nothing 節點上水平分割，任何提供類似 CRUD 介面的儲存引擎都能接上來。這種解耦的代價，是日誌與並行控制都必須是純邏輯的，只能引用紀錄鍵值，不能碰頁面或索引結構。而決定性正是讓這個代價可以承受的原因，因為記錄邏輯輸入就足以完全決定資料庫狀態。
把粗重工作搬到取鎖之前
決定性通常對磁碟型資料庫不利，因為卡住的交易會擋住順序在它後面的所有交易，而傳統系統可以繞過這個停頓重新排序。Calvin 貫徹自己的設計原則來化解：sequencer 一旦收到可能造成磁碟停頓的請求，就在轉交給 scheduler 之前插入一段人工延遲，同時要求相關儲存元件先把紀錄預熱進記憶體。只要延遲蓋得住讀取時間，交易真正執行時就只會碰到記憶體中的資料，端到端延遲不會比在執行期做 I/O 更差，但磁碟時間完全不落在 contention footprint 裡。同樣的原則也驅動了 OLLP：在交易進入序列之前，先把未知的讀寫集合解出來。
運作方式 — 具體的機制
sequencing 層：epoch 與批次
sequencing 層分散在所有複本上，並在每個複本內再分割到每台機器，藉此擺脫早期原型那個單一節點 echo server。時間被切成 10 毫秒的 epoch；在一個 epoch 內，每台機器的 sequencer 元件累積用戶端的交易請求，到了 epoch 邊界就把它們編成一個批次，接著進行複寫。複寫成功後，sequencer 會向同一複本內每個分割的 scheduler 送出訊息，內容包含該 sequencer 的節點 ID、epoch 編號（全系統每 10 毫秒同步遞增），以及該收件者需要參與的那些交易輸入。每個 scheduler 再以決定性的 round-robin 方式交錯所有 sequencer 在該 epoch 的批次，拼出自己對全域順序的視圖。
交易輸入的複寫
節點被組織成 replication group，每個群組包含某一分割的所有複本。非同步模式下有一個複本被指定為 master，請求直接送到它的 sequencer，各 master 編好批次後再轉發給群組內的 slave sequencer；延遲極低，但故障轉移相當複雜，因為存活節點必須就失效 sequencer 送出的最後一個有效批次、以及該批次確切包含哪些交易達成一致，而每個 scheduler 只看過屬於自己的部分視圖。同步模式下，replication group 內所有 sequencer 以 Paxos（實作在 ZooKeeper 之上）對每個 epoch 的合併批次達成共識。ZooKeeper 並非最有效率的 Paxos 實作，但由於這個步驟發生在取鎖之前，完全不會延長 contention footprint，交易吞吐量因此完全不受複寫模式影響。
決定性鎖管理器
鎖管理器分割在整個 scheduling 層上，每個節點的 scheduler 只負責鎖定存放在該節點 storage 元件中的紀錄，即使交易同時會存取遠端資料也一樣。它的行為近似 strict two-phase locking，但多了兩條不變條件：若交易 A 與 B 都要對本地紀錄 R 取得互斥鎖，而 A 在 sequencer 給定的順序中排在 B 之前，則 A 必須先提出鎖請求；而且鎖必須嚴格依請求順序發放，因此 B 要等到 A 取得鎖、執行完畢並釋放後才能拿到。Calvin 以單一執行緒序列化所有鎖請求來落實第一條：該執行緒掃描序列順序，逐筆為交易一次請求其生命週期中會用到的所有鎖。這也正是為什麼所有交易都必須事先宣告完整的讀寫集合。
五階段的交易執行
交易取得全部的鎖之後就交給工作執行緒，執行分為五個階段。第一階段分析讀寫集合，找出哪些元素在本地，以及哪些節點是 active participant（存有部分寫入集合）或 passive participant（只存有讀取集合元素）。第二階段執行本地讀取；第三階段把本地讀取結果轉送給每個 active participant 上的對應執行緒，passive participant 做完這一步就結束，永遠不必執行交易程式碼。第四階段由 active participant 收齊遠端讀取結果；第五階段執行交易邏輯並套用本地寫入，非本地寫入可以直接忽略，因為對應節點的執行緒會把它們視為本地寫入來套用。只要各參與者大致同時開始，所有讀取與所有結果傳遞都平行發生，執行期間沒有任何工作執行緒需要向別的節點索取資料。
不需協商協定的提交
整條流程中沒有任何類似 prepare 階段的東西。非決定性故障不會導致中止，因為有主動複寫的節點正在執行同一份計畫，其他節點可以改向它取得所需讀取，同時等待失效節點復原；交易憑著複本的完成即可提交。決定性中止（例如庫存會變成負數時就拒絕訂單的邏輯）則透過另一種方式處理：每個節點只需等待所有可能決定性中止的節點各送來一則單向訊息，收齊後即提交。當機機器的復原，就是還原到最近一次 checkpoint 再重播之後的交易輸入，過程中完全不涉及實體 REDO 日誌。
處理相依交易的 OLLP
有些交易必須先讀資料才能知道自己的讀寫集合，論文稱之為 dependent transaction（相依交易），這類交易無法被原生支援，因為鎖必須在執行前就請求。Optimistic Lock Location Prediction 的作法，是在這種交易之前先跑一個廉價、低隔離、不複寫的唯讀偵察查詢（reconnaissance query），把判斷完整讀寫集合所需的讀取先做掉。真正的交易再帶著這組預測出來的集合送進全域序列；執行時會重新檢查讀取結果，若偵察到的集合已失效，就以決定性的方式重啟該交易。實務上重啟預期相當罕見，因為相依交易通常依賴次要索引，而次要索引修改成本高，一般只建在變動不頻繁的欄位上；TPC-C 的 Payment 交易正是這種形態，而由於該基準測試從不修改它所依賴的索引，Payment 交易永遠不需要重啟。
對齊虛擬一致點的 checkpoint
由於只記錄輸入，Calvin 需要定期擷取整個資料庫的 checkpoint 以限制重播長度，並提供三種模式。最單純的同步模式會凍結整個複本並產生完整快照，客戶端看不到中斷，但該複本會落後許多且不易追上。第二種模式改編自 Cao 等人的 Zig-Zag 演算法：每筆紀錄保留兩份副本 AS[K]0 與 AS[K]1，另加 MR[K] 與 MW[K] 兩個位元，分別指定讀取時該用哪個版本、更新時該覆寫哪個版本；Calvin 的變體利用全域序列定義一個虛擬一致點（全域順序中預先指定的位置），因而不需要像原始 Zig-Zag 那樣讓資料庫靜止下來。此後每筆紀錄同時存在只能被虛擬一致點之前的交易更新的 before 版本，以及由之後交易寫入的 after 版本；當所有較早的交易都執行完畢，before 版本即成為不可變，非同步執行緒便可將其寫出，完成後再回收重複版本。第三種模式適用於儲存層支援完整多版本的情況，此時 checkpoint 就等同一次 SELECT * 查詢，只是把結果寫進磁碟檔案而不是回傳給客戶端。
論文證明了什麼 — 量測數據與證明
- 在只保留 New Order 交易的 TPC-C 上，每個節點存放 10 個 warehouse，且所有跨 warehouse 的訂單一定存取另一台機器上的 warehouse；超過 10 個節點後 Calvin 每節點穩定維持約每秒 5000 筆，並線性擴展到 100 節點、接近每秒五十萬筆——對照當時 Oracle 在高階許多的硬體上創下的每秒 504,161 筆 New Order 世界紀錄。
- 在微基準測試中，單機約可達每秒 27000 筆，加入分散式工作後每節點吞吐量下降 5 到 7 倍，落到 4 節點約 5000 筆、8 節點約 4000 筆；contention index 為 0.0001 時每節點吞吐量約在 10 台機器後就趨於平坦，contention index 為 0.01 時則下降得較緩慢，但各種設定都能擴展到 100 節點。
- 複寫模式只改變延遲、不改變吞吐量：每個複本 4 台 EC2 High-CPU 機器、共執行每秒 40000 筆微基準交易（其中 10% 為跨分割），無論是同一資料中心內的三複本 Paxos（ping 約 1 毫秒），或橫跨 Virginia、Northern California 與 Ireland 的三複本 Paxos（ping 100 至 170 毫秒），整體交易吞吐量都完全不受影響。
- 採用簡單的檔案系統式冷資料儲存時，只要不超過 0.9% 的交易（每台機器每秒 10,000 筆中的 90 筆）需要讀磁碟，吞吐量就不受影響，瓶頸來自商用硬體上本地磁碟的隨機存取吞吐量而非競爭；在 contention index 為 0.01 時需要 40 毫秒的人工延遲，才能讓 99% 讀磁碟的交易在預取完成後才被排程，而 contention index 小於等於 0.001 時，平均 5 毫秒的批次收集延遲就已足夠。
- 當冷資料改由另一台機器在可設定的延遲後才回應時，每台機器仍能維持每秒 10,000 筆交易，無論其中有多少比例存取冷資料，即使在 contention index 為 0.01 的極高競爭下亦然。
- 在 100% 跨分割的工作負載下，Calvin 的減速幅度遠低於 System R* 式系統的分析下界：給定 contention index C，這類系統每秒最多只能執行 1/(C * D_2PC) 筆交易，而由實測約 2 毫秒的單向執行緒間延遲推得 D_2PC 約為 8 毫秒；該模型還刻意忽略 CPU 成本、達成本地提交決定的延遲與執行進度偏斜，因此真實的 2PC 系統只會更差。
限制與取捨 — 論文自承的，以及後來被發現的
- 論文自承決定性鎖定協定要求每筆交易在執行前宣告完整的讀寫集合，這使相依交易無法被原生支援，只能倚賴 OLLP 這個折衷方案，而偵察查詢的結果可能過期並觸發決定性重啟。
- 論文量測到、卻無法消除禁止即時重排序所帶來的代價：任何一台機器都無法比其他機器領先或落後太多，因此速度較慢的 EC2 執行個體，以及來自執行緒排程與網路抖動的一般執行進度偏斜，都會拖垮整個叢集，且競爭愈高影響愈嚴重。後續的決定性系統，很大程度正是為了鬆綁這層耦合而生。
- 論文自承磁碟支援建立在兩個脆弱的前提上——一是必須準確預測磁碟延遲，高估會浪費延遲並讓記憶體塞滿等待中的冷紀錄，低估則會讓握著鎖的交易在執行中停頓；二是每個 sequencer 都必須追蹤全系統哪些鍵值仍在記憶體中，而論文明白指出這並不是一個可擴展的解法。
- 論文自承將儲存與交易管理解耦後，ARIES 式的 physiological logging 與 next-key locking 都變得不可行；要鎖定鍵值範圍並處理 phantom，必須引入可在邏輯上鎖定的虛擬資源，而該功能的實作仍屬未來工作。
- 論文自承故障轉移尚未做到無縫：當機的機器需從最近一次完整快照加上重播來復原，而由於同一複本內其他節點仰賴向它發出的遠端讀取，在復原完成之前，整個複本其餘部分的吞吐量往往會變慢甚至停擺。
它後來變成什麼 — 繼承這個想法的系統
Calvin 把決定性執行從一個奇想變成可信的架構，其「先定序、再執行」的流程也成為一整條系統脈絡的參考設計。FaunaDB 直接以 Calvin 那套「執行前先對全域輸入順序達成共識」的模型打造分散式交易引擎，CalvinFS 則把 sequencer／scheduler 的切分延伸到分散式檔案系統的 metadata 上。Yale 團隊的後續研究沿著 Calvin 留下的缺口推進：Bohm 與 PWV 等決定性多版本引擎針對執行順序的耦合下手，Aria 後來則拿掉了必須事先知道讀寫集合這個 Calvin 最尖銳的限制。與 Spanner 同年問世的 Calvin，也定義了分散式 SQL 領域長久的架構論辯——是在執行期付出 TrueTime 加 Paxos 加兩階段提交的代價，還是只對輸入日誌付一次共識成本、之後決定性地執行——這場辯論 Abadi 之後又持續書寫了多年。更廣義地說，Calvin 是把 state machine replication 套用到交易上最清楚的資料庫版本陳述，而這正是所有以有序、可重播事件日誌為核心的 log-first 設計背後的同一個模式。
論文原文 — 逐字引用
“when multiple machines need to agree on how to handle a particular transaction, they do it outside of transactional boundaries—that is, before they acquire locks and begin executing the transaction.”
“Since all Calvin nodes reach an agreement regarding what transactions to attempt and in what order, it is able to completely eschew distributed commit protocols, reducing the contention footprints of distributed transactions, thereby allowing throughput to scale out nearly linearly despite the presence of multipartition transactions.”
“move as much as possible of the heavy lifting to earlier in the transaction processing pipeline, before locks are acquired.”
術語 — 依本篇論文的用法
- contention footprint（競爭足跡）
- 一筆交易持有鎖的總時長，包含它必須執行的任何提交協定在內。Calvin 的核心主張是：兩階段提交之所以昂貴，主要在於它撐大了這個量，而不在於其 CPU 或網路開銷。
- deterministic locking（決定性鎖定）
- 一種近似 strict two-phase locking 的鎖定協定，但額外要求互相衝突的交易依 sequencer 的全域順序提出鎖請求，且鎖必須嚴格依請求順序發放。它讓每個複本的執行在邏輯上都等價於同一個序列順序，同時仍能並行執行大量交易。
- sequencing layer（定序層）
- 負責攔截用戶端交易請求、以 10 毫秒 epoch 成批收集、複寫這些批次，並發佈全域交易輸入序列的一層。它分散於所有複本、並在每個複本內再行分割，因此不存在單一節點 sequencer 的瓶頸。
- scheduling layer（排程層）
- 存放分割式決定性鎖管理器與交易執行緒池的一層。每個節點的 scheduler 只鎖定存放在本地的紀錄，即使該交易同時也會讀寫其他節點上的資料。
- epoch
- 長度 10 毫秒的時間窗，每個 sequencer 在此期間收集進來的交易請求，窗口結束時編成一個要複寫的批次。epoch 編號在全系統同步遞增，讓每個 scheduler 都能以決定性方式交錯所有 sequencer 的批次。
- active participant／passive participant
- 對某筆交易而言，存有其部分寫入集合的節點是 active participant，只存有讀取集合元素的節點是 passive participant。passive participant 轉送完本地讀取結果就結束，永遠不執行交易程式碼。
- Optimistic Lock Location Prediction (OLLP)
- 處理相依交易的機制：先以廉價、不複寫的唯讀偵察查詢找出交易的讀寫集合，之後真正的交易才帶著這組集合進入全域序列。執行時會重新檢查這項預測，若已失效則以決定性方式重啟該交易。
- contention index（競爭指數）
- 微基準測試的參數，表示每筆交易在一台參與機器上更新的熱門紀錄佔全部熱門紀錄的比例。指數 0.01 代表最多 100 筆交易可同時執行，指數 1 則迫使交易完全序列化執行。
- virtual point of consistency（虛擬一致點）
- 全域序列順序中預先指定的一個位置，作為 checkpoint 所擷取的邏輯時刻。它讓 Calvin 的 Zig-Zag 變體不必把資料庫靜止到某個實體一致點，就能取得一致的快照。
在時間軸上的位置 — 這篇論文在整段故事中的座標
年份2012
里程碑Calvin 決定性交易
解決的問題分散式交易的協調成本很高，跨分區發生競爭時尤其嚴重。
解決方式Calvin 以決定性（deterministic）交易排序來降低執行期協調的複雜度。
重要性影響了分散式 SQL 與決定性交易處理架構。
DDIACh. 8: Transactions Ch. 10: Consistency & Consensus