2023/02/20

2-phase, 3-phase commit

在分散式系統,2-phase 與 3-phase commit 是用來處理多個節點的 transaction 的演算法,3PC 是解決 2PC 的缺點而設計的。

ACID

資料庫管理系統 DBMS 在寫入/更新資料時,會確保單一交易 transaction 的正確性,規定一個交易必須滿足 Atomicity, Consistency, Isolation, Durability 四個特性。

  • Atomicity 原子性

    一個 transaction 裡面所有的資料操作,必須全部一起完成,或是全部一起失敗,在執行過程中如果發生任何問題,都必須 rollback 回到 transaction 一開始的狀態

  • Consistency 一致性

    在 transaction 開始前,以及結束以後,資料庫要保持完整性,兩個狀態都是資料庫的某一個合法的狀態

  • Isolation 隔離原則

    在多個 transaction 同時發生時,每一個 transaction 都必須各自獨立,即使對同一個資料進行異動,必須保證這幾個 transaction 之間不會互相影響,交查執行,而破壞了資料的一致性。

    隔離有不同的等級:read uncommitted, read committed, repeatable read, serializable

  • Durability 持久性

    當 transaction 結束後,對資料的修改必須是永久的,即使系統發生故障異常,也不會遺失資料

2-Phase Commit

在單一資料庫時,要維持 DBMS 的 ACID 原則比較簡單,但是如果商業邏輯牽涉了多個 DBMS,例如在購物時,必須同時異動倉儲管理及出貨管理兩個系統,這兩個系統的資料庫各自獨立。為了維持 ACID 原則,兩個 DBMS 必須同時異動,或是同時失敗,倉儲管理系統減少的商品數量 = 出貨管理增加的商品數量,2-Phase Commit 就是用來在分散式系統中達到 Data Stong Consistency 的方法。

角色

  1. Coordinator

    負責發起及維護 2PC 的流程,可能是 client 或 middleware,該角色不會異動到其他節點上

  2. Participant

    參與交易的 DBMS 或 Storage

假設

  1. 所有節點不會產生永久性破壞,異常後仍能恢復運作

  2. 交易的異動動作先放在預寫式日誌上,日誌會儲存在可靠的儲存設備上,即使節點被破壞,也不會遺失日誌資料

  3. 系統存在一個節點作為 coordinator,其他節點為 participants,不限制系統之間的通訊方法

方法

分為兩個 phase

Phase1 請求階段

  1. coodinator 向 participants 發送 "Prepare" 詢問是否可參與交易

  2. participants 執行詢問開始為止的所有 transactions,將 Undo, Redo 寫入日誌

  3. participants 響應 "Prepare" 詢問,先複製一份預計被更新的資料,並回復兩種訊息

    1. "Ready":可成功參與交易

    2. "Abort":失敗

Phase2 執行階段

Ready

當所有 participants 都回覆 Ready 時

  1. coordinator 向所有 participants 發送 "Commit"

  2. participants 完成交易,釋放整個交易期間佔用的資源

  3. participants 向 coordinator 發送 "Done"

  4. coordinator 收到所有 participants 回送的 "Done" 完成交易

Abort

當有任一個 participant 回覆 "Abort" 時,或是 coordinator 詢問 Timeout 無法取得回覆時

  1. coordinator 向所有 participants 發送 "Rollback"

  2. participants 利用先前的 "Undo" 執行 rollback,釋放整個交易期間佔用的資源

  3. participants 向 coordinator 發送 "Rollback Done"

  4. cooridator 收到所有 participants 回送的 "Rollback Done",取消交易

優缺點

優點:簡單,容易實作

缺點:

只有一個 coordinator,如果 coordinator 失效,則因為 participants 的同步呼叫操作,無法收到回覆而被 blocked,必須根據這種狀況另外實作 rollback 或是 abort 給 participants。

3-Phase Commit

為了解決 2PC 的問題,可使用 3PC

3PC 是一種 nonblocking 的協議。3PC 在 2PC 的第一階段與第二階段之間插入了一個準備階段,可解決在原先在 2PC 中,participant 在投票之後,由於 coordinator 發生崩潰或錯誤,而導致 participant 處於無法知曉是否提交或者中止的「不確定狀態」所產生的可能相當長的延時的問題。

3PC 將 Participants 改為 Cohorts

Phase1 CanCommit

跟 2PC 的 phase 1 一樣,coordinator 發送 "canCommit" 給所有 Cohorts。

Cohorts 收到 canCommit,如果可以執行 transaction,資料沒有被鎖定,就回覆 "Yes",否則就回覆 "No"

Phase2 PreCommit

coordinator 根據 cohorts 的回覆,決定是否繼續

A. 所有 Cohorts 都回覆 "Yes"

傳送預提交請求,coordinator 會傳送 "PreCommit" 給 Cohorts,進入 Prepared 階段

transaction 預提交,cohorts 接收到 PreCommit,執行 transaction,並將 Undo 與 Redo 資訊記錄到事務日誌中

B. 有任一個 Cohort 回覆 "No",或等待超時,沒有收到回覆

中斷交易,傳送中斷請求 "Abort" 給所有 cohorts

cohort 收到 "Abort" 時,或是 Timeout,就執行中斷交易

Phase3 DoCommit

進行真正的交易內容,分兩種情況

A. 執行提交

  1. 傳送提交請求

    coordinator 收到 cohort 的 "Ack",就會將預提交狀態改為提交狀態,並向所有 cohorts 傳送 "doCommit"

  2. 提交交易

    cohort 收到 "doCommit" 後,執行交易提交,並在交易完成後,釋放所有交易資源

  3. 響應回饋

    提交交易後,繪像 coodinator 發送 "Ack"

  4. 完成交易

    coordinator 收到所有 cohorts 的 Ack 後,完成交易

B. 中斷交易 transaction

coordinator 沒有收到 Ack (可能收到的不是 ack 或是 timeout),就會中斷交易

差異

在 2PC 只有 coordinator 有 timeout 機制,在 3PC,coordinator 與 cohort 都有 timeout 機制

PreCommit 是一個緩衝機制,確保最後提交階段前,各參與節點的狀態是一致的

缺點

進入 PreCommit 後,coordinator 發出 Abort,假設只有一個 cohort 收到並執行 abort,其他對於系統狀態未知的 cohort 會根據 3PC 選擇繼續 Commit,系統會進入狀態不一致的情況

Refereneces

二階段提交 - 維基百科,自由的百科全書

三階段提交 - 維基百科,自由的百科全書

Day 11 - 共識演算法 - 2 Phase Commitment (2PC) - iT 邦幫忙::一起幫忙解決難題,拯救 IT 人的一天

Day 12 - 共識演算法 - 3 Phase Commitment (3PC) - iT 邦幫忙::一起幫忙解決難題,拯救 IT 人的一天

Two Phase Commit

三階段提交(Three-phase commit) | 程式前沿

沒有留言:

張貼留言