淺談分散式交易

分散式交易 (Distributed Transactions) 指分散在各個運算單元的一系列任務操作 (Operations) 或任務 (Tasks)、有次序的 (Ordered)、且彼此是隔離 (Isolation)、最終達成一致的過程。達成一致 指的是全部動作都成功、或者全部動作都失敗，後者則透過 Rollback 還原。

分散式交易對應的就是單機交易，也就是在一個運算資源上，完成交易動作，電商最常見的案例就是：

1. 完成訂單 (含付款)
1. 完成扣庫存

這兩的操作 (Operations) 滿足次序性、最後達成交易，也就是關聯式資料庫常說的 ACID 原則。如果這個過程是在分散式系統，就必須有其他機制達到此需求。

常見的分散式交易有幾種協議，像是：

基於 X/Open 國際聯盟的 Distributed Transaction Processing Model (DTP)，簡稱 XA，用來達到強一致性，符合 ACID 原則的協議：
1. 二階段提交 (Two Phase Commit, 2PC)
三階段提交 (Three Phase Commit, 3PC)
另外就是屬於最終一致性、符合 BASE 原則的消息對列 (Message Queue) 方式。

本文整理 XA、二階段提交 (2PC)、三階段提交 (3PC)、TCC (Try-Confirm-Cancel) … 等基礎概念。文章資料主要參考自 Distributed Systems: Concepts and Design (5th Edition)、分佈式事務：All or nothing 兩篇的整理。

用詞

Transaction: 繁中叫做 交易，簡中叫做 事務，整理過程有時候覺得前者語意清楚，有時候覺得後者適當。所以下述的整理，依照狀況兩個詞彙交換使用。

概念

XA 協議

由 X/Open 國際聯盟提出的 Distributed Transaction Processing (DTP) 模型，簡稱 XA ，是一個分散式交易協議，此協議定義以下介面：

應用程式 (Application Program, AP)：定義交易邊界與特地動作
事務管理器 (Transaction Manager, TMs)：協調者，負責本地資源的 Commit 和 Rollback
資源管理器 (Resource Manager, RMs)：分散式交易的參與者，通常用資料庫實踐或者是資料存取驅動層 (ODBC、JDBC、ADO.Net)，像是 Oracle、DB2 都有實作 XA 協議。

整個 Model 概念如下圖：

出處：X/Open DTP Model

要注意的是，XA 不等於 2PC。

結構

分散式交易有兩種結構，如下圖：

出處：Distributed Systems: Concepts and Design (5th Edition), Page 729

Flat Transaction (扁平式交易結構)：執行在每台機器上物件的操作，通常 Client 要等單一機器上的物件動作完成執行後，才會往下一個做，也就是交易的動作是循序執行的。如果其中一台伺服器上的物件發生 Lock，那麼整個執行可能會因此受影響。

Nested Transaction (巢狀式交易結構)：這種結構的上層較易運算單元，可以近一步分配工作給子運算單元。圖中 (b) 的 T1、T2 可以新增子交易 T11、T12、T21、T22，這四個交易跑在不同的運算資源。巢狀結構裡，同一階層的 T1、T2 為 同步執行 (Concurrence），因為它們兩個物件因為跑在不同的運算單元，所以是一種平行處理 (Parallel)。

註一：這裡的 Client 指的是需要執行交易的業務端應用程式。

註二：同步 (Concurrence) 與 平行 (Parallel) 表面上看起來都是同時做多個事情，同步指單一處理器 (Processor) 處理多個事情，而平行指多個處理器處理多個事情。前者資源是共用的，透過 Context Switch 切換 CPU，後者則沒有這問題。Concurrent 也常翻譯成 併發，通常指的是邏輯上概念的同時發生 (Simultaneous)，例如一個電商系統具備高併發能力，表示短時間之內、同時可以處理極高的交易與請求數量。

Scatter / Gatter Pattern

類似的結構與概念，在 Designing Distributed Systems 一書的第七章 Scatter / Gatter 也有提到，如下圖：

出處：Designing Distributed Systems, Page 74

這張圖講的是如何做分散式資料處理的概念，其中提到兩個核心概念：Scatter (分配)、Gatter (聚集)。前者是負責如何把工作拆分成多個任務，然後分配到各個運算單元執行，以平行運算 (Parallel) 執行。後者是如何各個運算節點的運算產出，匯集 (Aggregation) 最後的結果。

更進階的問題，就是每個運算單元的可靠性問題，通常會透過 Replication (複本)、Sharding (分片)、Partition (分區) 機制達到可靠性。

更多參閱：

分散式系統設計 - 正體中文版翻譯記事

可靠性工程

One Phase Commit？

談二階段提交之前，先往前思考：

有沒有一階段提交？

一個階段，代表著具備唯一性，也就是具備 原子特性 (Atomic)，稱為 one-phase atomic commit protocol。一階段提交從頭到尾，所有的操作 (Operations) 都是在同一個運算資源上執行。Client 從發送請求，最後只會收到成功或者失敗。這種協議不允許運算單元做單方面的決策，當 Client 希望放棄某一個操作。

Two Phase Commit (2PC)

二階段提交 (Two Phase Commit, 簡稱 2PC) 是基於 XA 協議的方法，也是最普遍的分散式交易演算法、協議。由 IBM 研究員 Jim Gray 在 1977 年的 Notes on Data Base Operating Systems 提出。

他有兩個角色：

Coordinator (事務協調者): 負責協調、分派工作給事務參與者。對應到 XA 協議的事務管理器。
Participants (事務參與者): 也就是實際執行工作的角色，通常是多個。對應到 XA 協議的資源管理器。

2PC 設計上，允許參與者可以放棄部分的交易，整個交易因為部分參與者放棄，所以整個交易也必須失敗。2PC 顧名思義分成兩個階段：

階段一：Voting Phase (投票階段)
1. 協調者發送 canCommit 請求給所有的參與者。
2. 當參與者收到 canCommit 請求，他會回復投票 (Vote) 結果 (Yes / No) 給協作者。參與者再回覆訊息之前，會準備相關的物件初始化。
階段二：Completion according to outcome of vote (Commit 提交階段)
1. 協調者搜集投票結果：
  a. 如果所有投票結果都是 Yes，協調者發送 doCommit 請求給每一個參與者
  b. 否則，協調者決定放棄交易，發送放棄 (doAbort) 請求給所有的投票給 Yes 的參與者。
2. 投 Yes 的參與者等待協調者的指令：doCommit 或者 doAbout。當參與者接收到 doCommit 訊息，最後會回覆 haveCommitted 給協調者做為確認。

這兩個階段的過程中包含以下動作：

canCommit(transId): 依據 transId，協調者詢問參與者能否提交交易，參與者回覆投票結果
doCommit(transId): 依據 transId，協調者告訴參與者執行提交部分的交易操作
doAbort(transId): 依據 transId，協調者告訴參與者放棄部分的交易操作
haveCommitted(transId, participant): 參與者告訴協調者，已經完成提交動作
getDecision(trans): 從參與者告訴協調者，詢問是否已經確認可否執行交易？通常是因為參與者因為一些因素，還沒有回覆協調者，導致訊息延後。

下圖是 2PC 協議的通訊過程：

出處：Distributed Systems: Concepts and Design (5th Edition), Page 734

底下是 完成交易 的循序圖：

底下是 放棄交易 的循序圖：

實務應用

Google 在 2011 年發表的分散式事務模型 Percolator，主要是為實現在海量資料集中 (數百個 PB)，更新少量增量 (incremental processing) 資料而建立的一個事務模型，透過此事務模型可以達到全局關的資料強一致性的目的。。參閱論文：Large-scale Incremental Processing Using Distributed Transactions and Notifications (pdf)
ZooKeeper Recipes and Solutions
TCC (Try-Confirm-Cancel)：算是 2PC 的變形, 由 Pat Helland 在 2007 的論文中提出
計算機科學家 Leslie Lamport 提出的 Paxos 演算法中的 Basic Paxos 也是一種 2PC 的實作。

2PC 的問題

2PC 的基本思路：

協調者發號施令給參與者，然後參與者們把結果回傳給協調者，由協調者進行下一步的決定ㄡ

這樣的概念滿足交易 ACID 的特性需求，但卻有以下問題：

單點故障 (SPOF): 如果過程執行協調者角色的事務管理器發生問題，那麼就會造成整個交易阻塞 (Blocking) 的問題。
同步阻塞問題：2PC 在執行過程中，參與者的節點都是阻塞型。一般來說，協調者這個角色會放在參與者的節點，換言之有可能因此
資料不一致：在提交階段，協調者發送 doCommit 之後，如果發生局部網路異常 (Partition Failure)，導致只有部分的參與者收到指令，完成交易，但是部分的就沒完成，最後出現資料不一致的問題。

2PC 相關議題

除了前述的問題，以下羅列其他 2PC 議題，以後繼續整理：

2PC 的巢狀交易結構 (Nested Transaction)
分散式交易的同步控制 (Concurrency Control in Distributed Transactions)
分散式死鎖 (Distributed Deadlocks)
交易還原 (Transaction Recovery)

Three Phase Commit (3PC)

有一就有二，有二就有三。

前面羅列 2PC 的問題，包含 同步阻塞 (Blocking)、資料不一致 (Consensus) ，三階段提交就是為了改善這些問題而衍生的演算法，主要加入以下特性：

超時機制
準備階段

在 2PC 的第一階段後，增加了一個 PreCommit 階段，變成如下：

CanCommit: 類似於 2PC 的 Voting 階段
PreCommit: 依據參與者的回覆，決定預備的事物。
DoCommit: 原本 2PC 的 Commit 階段

Sequence Diagram 如下圖：

問題

依舊沒有解決 2PC 資源阻塞的問題
依舊沒有解決 2PC 資料不一致的問題
因為增加一個 preCommit 階段，處理時間也延遲了。

結語

從上述的整理不難發現，2PC / 3PC 兩種一致性演算法好像都不是很完美，無法完全滿足分散式交易所需要的特性：

一致性
可用性

所以 Google Chubby 的作者 Mike Burrows 才說：

There is only one consensus protocol, and that’s Paxos, – all other approaches are just broken versions of Paxos.

意即世上只有一種一致性算法，那就是 Paxos。不過 Paxos 也是公認的複雜與難以理解，以至於後來才有衍生的 Raft 演算法。

在分散式系統已經成常態的現在，很多論文的方法不斷被提出來，像是著名的架構模式 Saga Pattern 主要適用在長時間交易 (long running transactions) ，在 AWS 則可以透過 Step Functions 實踐類似的概念。

回到分散式交易的特性，此模式依舊要達到考量的需求，也因此依照分散式交易的特性，又分成剛性事務與柔性事務，以下整理找到的資料：

剛性事務:
- 遵循 ACID 原則，具備強一致性，最常見的是 RDBMS 的交易。
- 實踐：XA 協議 (2PC、JTA、JTS)、3PC
柔性事務：
- 遵循 BASE 理論的原則，犧牲強一致性，保證最終一致性，因此獲得可用性。
- 實踐： TCC、Saga (狀態幾模式)、Message Queue 模式。

在實務的分散式架構中，跨服務的交易處理，往往是最棘手的問題，而大部分的實務應用，就仰賴這些基礎概念。當系統架構越龐大，越來越複雜，能否在複雜中看清楚本質就需要仰賴這些基礎概念的學習與實踐。

淺談分散式交易

用詞

概念

XA 協議

結構

Scatter / Gatter Pattern

One Phase Commit？

Two Phase Commit (2PC)

實務應用

2PC 的問題

2PC 相關議題

Three Phase Commit (3PC)

問題

結語

延伸閱讀

站內文章

參考資料

相關論文

相關書籍

Comments

About

著作

演講

Facebook

AWS Certifications