淺談分散式交易


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

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

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

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

常見的分散式交易有幾種協議,像是:

  1. 基於 X/Open 國際聯盟的 Distributed Transaction Processing Model (DTP),簡稱 XA,用來達到強一致性,符合 ACID 原則的協議:
    1. 二階段提交 (Two Phase Commit, 2PC)
  2. 三階段提交 (Three Phase Commit, 3PC)
  3. 另外就是屬於最終一致性、符合 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 的特性需求,但卻有以下問題:

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

2PC 相關議題

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

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

Three Phase Commit (3PC)

有一就有二,有二就有三。

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

  1. 超時機制
  2. 準備階段

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

  1. CanCommit: 類似於 2PC 的 Voting 階段
  2. PreCommit: 依據 參與者的回覆,決定預備的事物。
  3. 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 模式。

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


延伸閱讀

站內文章

參考資料

相關論文

相關書籍




Comments