標籤：

分散式事務提交協議: 2PC/3PC

04-04

分散式事務提交協議: 2PC/3PC

數據共享和並發編程是計算機應用中的普遍需求, 資料庫的事務機制, 能幫助backend程序員編寫正確的並發程序，並減輕心智負擔. 因為事務具有ACID特性[1]:

  1. Atomicity: 修改一組元素, 成功, 則所有元素的變更均生效; 失敗, 資料庫自動撤銷部分元素的變更, rollback到之前狀態. 用戶不必額外採取操作.
  2. Consistency: 事務執行成功與否, 資料庫始終處於一致狀態, 事務是將資料庫從一個一直狀態轉移到下一個一致狀態的基本操作單位. 用戶不必擔憂約束遭到破壞.
  3. Isolation: 事務並發執行以提高性能, 同時正確性能夠得到保障, 用戶不必擔憂衝突事務導致concurrent anomaly.
  4. Durability: 提交的事務對資料庫狀態的修改具有持久性, 未完成的事務不會修改數據的狀態, 即便出現升級重啟, 斷電, 故障或者服務崩潰. 資料庫能夠恢復到正確的狀態. 用戶不必擔憂異常事件造成數據丟失或者狀態不一致.

通常單機事務的操作只涉及單機節點上的若干元素, 如果操作涉及的元素橫跨多台機器, 比如Bob和Alice的賬戶信息分別存儲在機器A和B上的MySQL服務實例中, Bob向Alice轉賬. 通常這樣的事務稱之為分散式事務(distributed transaction). 一般地, 分散式事務做為global事務, 可以分解為若干操作本地資料庫的子事務; 子事務本身具有ACID特性, 但要為global事務提供ACID特性, 並非trivial problem[2]. 更一般地, NoSQL資料庫提供有限的事務支持, 比如Bigtable支持單行更新事務, 跨行操作的事務也屬於分散式事務的範疇[3]. 不難得出: 分散式事務是一種由若干修改本地狀態的子事務組合而形成的全局事務.

本文採用Database System Concepts中的定義, 但不夠合理. 在實際的應用中, 採用2PC的系統, 也可能沒有將全局事務分解為子事務. 所以2PC是:

2PC是一種能夠保證原子性和持久性, 操作涉及多個組件參與, 每個組件分別記錄各自操作日誌的, 分離式的記錄日誌的機制.

2PC沒有言及如何對事務做並發控制, 僅僅是有別於中心化WAL日誌記錄的一種機制. 不考慮性能的情況下, 完全可以通過中心化的TM記錄日誌, TM通過RPC向其他事務參與者, 發起redo和undo的操作.

分散式事務, 涉及多個局部事務. 網路斷開和進程崩潰等故障會導致部分局部事務提交, 部分失敗. 要保證Atomicity和Durability, 需要用到提交協議, 2PC和其變種是一種廣泛使用的提交協議.

單機事務: 假如採用WAL和DIRECT, STEAL/NOT-FORCE[4]. 事務開始先寫<START T> 日誌, 修改資料庫元素之前, 先寫redo日誌<T elem new_val>. 如果提交事務, 則寫<COMMIT T>日誌, 當日誌落盤後, apply日誌, 更新buffer pool中相應的page, dirty page不必及時寫會磁碟, 可以延遲落盤. 如果事務失敗, 則寫<ABORT T>日誌, 不apply日誌. 很顯然, 未完成事務或者夭折的事務, 不會修改資料庫的狀態, 恢復時直接跳過. 已提交的事務, 因為dirty page延遲寫回磁碟, 最近一次checkpointing的時間也可能早於dirty page落盤時間, 因此需要redo事務T日誌.

分散式事務: 本地資料庫有自己私有WAL日誌. 難以單方面做出rollback或者redo的決定.

Two-Phase Commit Protocol(2PC)[2]

在2PC中, 由一個coordinator和多個participant對分散式事務的提交進行協調. coordinator和coordinator寫各自WAL日誌, 便於故障重啟後, 對事務進行恢復. coordinator是2階段提交的發起者. 事務T的提交過程為:

  1. prepare階段: coordinator追加<prepare T>日誌記錄, 向事務T鎖涉及的participant發送消息prepare T； 收到消息後, participant判斷事務T是否可以提交(申請鎖, 衝突檢測). 如果可以提交, 則追加日誌<ready T>, 並向coordinator發送消息ready T; 如何無法提交, 則追加日誌<no T>, 向coordinator發現abort T.
  2. commit階段:
  • case 1: coordinator收到全體participant的ready T: coordinator追加<commit T>日誌, apply日誌; 然後, coordinator向全體participant發送commit T消息, 收到消息後, participant追加<commit T>日誌, apply日誌修改狀態.
  • case 2: coordinator收到任何participant的abort T : coordinator追加<abort T>日誌, 向全體participant發送abort T消息; 收到信息後, participant追加<abort T>日誌.

participant追加 <commit T> 或 <abort T>後, 向coordinator發送acknowledge T消息, coordinator收到所有participant發來的確認後, 寫日誌<complete T>, T結束.

事務的狀態

2PC可類比投票, 投票方均擁有一票否決權, 也可以棄權(網路錯誤和宕機等錯誤導致投票超時). 只要獲得全票通過, 事務才可提交(committed); 否則, 事務失敗(aborted).

  1. 當coordinator寫下<commit T>日誌後, 事務已提交(圖中綠色區域);
  2. 當至少有一個participant寫下<no T>日誌後, 事務失敗(圖中橙色區域).

事務的最終狀態確定後, 事務尚未完成, 還有工作要做. 若事務committed, 還有繼續往前滾(roll forward), 通知participant執行commit和apply; 若事務aborted, 還要往回滾(rollback), 通知participant做rollback. 如果participant使用局部鎖表, 則完成本地事務之後, 需要釋放鎖, 容許其他事務被調度. 所以roll forward和rollback(在其他文獻[2]中提到redo和undo操作)是必不可少的.

事務提交或失敗後, 出現故障, 導致coordinator/participant不可用, 無法完成後續操作. 當coordinator/participant恢復可用, 對事務進行恢復時, 也要做rollback或者roll forward. 當然, 未完成的事務, 直接rollback即可.

事務進行恢復時, 如果信息有限, 無法裁決事務的最終執行狀態, 則事務處於in-doubt(懸而未決)的狀態(黃色區域).

容錯

  1. 網路錯誤: coordinator和participant之間出現networking partitioning, 互不可達. 普遍解決方法是: 重試+冪等+超時.
  2. coordinator/participant宕機崩潰: 服務要做到high availability, 普遍採用一主多備, 在服務崩潰時, 及時地failover. 比如多個coordinator構成RSM, 如Spanner中的Paxos group[5], 其他系統也可能採用Raft group.

恢復

coordinator恢復

coordinator掃描日誌:

  1. 只有<prepare T>記錄: 說明事務處於outstanding狀態, coordinator終止事務即可, 即從圖中C <abort T>做起.
  2. 有<commit T>但無<complete T>: 說明事務已經提交, 但可能尚未通知participant, 則從C <commit T>做起, roll forward, 通知全體participant做commit和apply.
  3. 有<abort T>但無<complete T>: 說明事務已經失敗, 從C <abort T>做起, rollback, 通知全體participant做終止事務.
  4. 有<complete T>記錄: 事務已經完成. 無需處理.

participant恢復

participant掃描日誌：

  1. 如果有<no T>或<abort T>記錄: 說明事務已經失敗, 則可以單方面rollback.
  2. 如果有<commit T>: 說明事務已經成功提交, 則做本地redo操作即可.
  3. 如果只有<ready T>: coordinator無法判斷事務的執行狀態, 當前事務處於in-doubt狀態. 見下文詳細描述.

In-doubt事務的恢復:

事務的狀態無非outstanding, committed, aborted, complete. 之所以處於in-doubt狀態, 是因為故障導致信息缺失, 無法判斷事務究竟處於三種狀態outstanding, committed, aborted中的哪一種.

  1. 在coordinator可用情況下, 首先詢問coordinator關於事務T的狀態. 如果T處於outstanding或aborted狀態, 則終止事務T, rollback.
  2. 在coordinator不可用情況下, 詢問當前可用的其他participant關於事務T的狀態. 如果事務T明確地處於committed或者aborted狀態, 則選擇roll forward或者rollback即可.
  3. 最糟糕的一種情況: coordinator不可用, 並且當前可用的participant日誌均只有<ready T>記錄. 此時無法採取行動, 因為:
  • 事務T可能處於committed狀態: coordinator不可用, 全體participant都投票<ready T>.
  • 事務T可能處於aborted狀態: coordinator和全體投反對票<no T> 的participant不可用.
  • 事務T可能處於outstanding狀態: coordinator不可用, 並崩潰之前, 並未寫下<commit T>或<abort T>.

這種情況下: 只有當coordinator恢復之後, 才能繼續推進. 如果系統中有其他的coordinator, 並且該coordinator上執行的事務和in-doubt事務有衝突; 則要麼自殺, 要麼等待in-doubt事務恢復後, 才能推進.

in-doubt事務, 充分地說明了coordinator的高可用至關重要.

Three-Phase Commit Protocol(3PC)[2]

2PC中, 採用單一的coordinator, 難以做到高可用. 3PC提出了一種解決方法: 增加備用coordinator, 提交事務時, 不只要將<commit T>寫入本地日誌中, 還要將提交信息複製到至少k個coordinator上. 如果主coordinator崩潰, 備用coordinator選出新任leader, 由它負責處理後續操作. 比如總共有5個coordinator, k=2. 可以容忍兩個coordinator故障.

RSM+2PC實現高可用

如下圖所示, coordinator採用Paxos實現RSM, 每次寫日誌時, 日誌被複制到Paxos group中. Log replication和Leader Election實現auto failover.

事務處理層和存儲層分離

比如在Percolator[3]中, 事務處理層over Bigtable, 可以做到stateless, 通過底層可靠的分散式存儲系統實現高可用.

參考文獻

[1] Gray J, Reuter A. Transaction processing: concepts and techniques[M]. Elsevier, 1992.

[2] Silberschatz A, Korth H F, Sudarshan S. Database System Concepts. McGraw-Hill Education, 2011.

[3] Peng D, Dabek F. Large-scale Incremental Processing Using Distributed Transactions and Notifications[C]//OSDI. 2010, 10: 1-15.

[4] Hellerstein J M, Stonebraker M, Hamilton J. Architecture of a database system[J]. Foundations and Trends? in Databases, 2007, 1(2): 141-259.

[5] Corbett J C, Dean J, Epstein M, et al. Spanner: Google』s globally distributed database[J]. ACM Transactions on Computer Systems (TOCS), 2013, 31(3): 8.


推薦閱讀：

※分散式系統數據層設計模式
※分散式事務解決方案與適用場景分析
※聊聊分散式

TAG:分散式事務 |