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) | 程式前沿

2023/02/13

Saga Pattern in Micro-service Architecture

saga 在 1987 年由 Hector Garcaa-Molrna Kenneth Salem 兩個人提出,是一種分散式交易架構,可在 micro-services 之間,提供跨service 的交易操作,以保障資料一致性。saga 是用一連串的交易方法,更新每一個服務並發布訊息觸發下一個交易,如果有某一個交易失敗,則進行補償。

saga 主要有 Choreography 及 Orchestration 兩種運作機制。

Choreography

沒有中央協調的角色,由每個服務執行完後主動發出狀態或是呼叫下一個服務。

Saga 模式會使用一連串的本機交易 (local transaction) 實作交易管理。 本機交易是 Saga 參與者所執行的不可部分完成工作工作。每個本機交易都會更新自己的資料庫,同時發布訊息或事件,觸發 saga 中的下一個本機交易。如果本機交易失敗,saga 會執行一系列 補償交易 ,以復原先前本機交易所做的變更。

這個方法的優點是個服務之間的資訊交換方法簡單容易理解,但如果某一個流程中間牽涉的微服務數量太多,就會讓架構變得複雜混亂。因為服務提供者的角色數量增加,導致每個服務都需要一個訊息通道,利用 publish-subscribe 機制,處理訊息交換的問題,但 subcriber 也可能發生意外,導致訊息沒有被處理的例外狀況發生。

Orchestration

有一個交易管理中心,掌管整個商業邏輯,知道如何呼叫微服務,處理整個流程,呼叫下一個服務,並在服務發生問題時,處理補償機制。所有服務都會跟這個中央集權式的交易管理中心溝通。

優點是 Choreography 服務之間的依賴度低,降低複雜度,比較容易處理 rollback,缺點是 Orchestration 實作本身會很複雜。

References

https://medium.com/skyler-record/微服務架的資料一致性-1-saga-pattern-cf05aed1307b

微服務瞎談(7) Saga Pattern - iT 邦幫忙::一起幫忙解決難題,拯救 IT 人的一天

Saga 模式 - Azure Design Patterns | Microsoft Docs

Patterns in Event Driven Architecture

Sagas

2023/02/06

Negative Testing

軟體測試有兩種策略:Positive 與 Negative Testing。Positive Testing 可測試軟體是否是依照預期的方式運作,Negative Testing 是確保軟體能處理 invalid input 及 unexpected user behavior,例如使用者在要輸入數字的欄位,填寫文字,正常的狀況是軟體要做警示,Negative Testing 是確保軟體在這些異常狀況下,能夠處理且不會 crash。

Negative Testing 就是刻意在測試中製造錯誤情境,利用這些製造出來的錯誤狀況進行測試,以確保軟體能夠持續運作。因為使用者在使用軟體的過程中,通常會對 crash 非常敏感,如果填寫或操作的錯誤,造成軟體直接中斷 crash,這時候的體驗印象會非常差,會因為這樣的中斷,填滿了整個體驗印象,不管其他地方做得再好都沒有用。但如果出錯了,出現警示,或是軟體沒有出現任何回應,這樣的狀況,還比較能忍受,不會直接因為 crash 被嚇到。

依照 Negative Testing 的定義,是要找出在一些特殊異常的使用狀況下,軟體會不會發生問題的測試,目的是希望軟體能夠更穩定,能夠應付各種特殊的狀況。

臉書APP超耗電不是錯覺!前員工爆料:Meta故意的 這邊提出了一個前 Meta 員工,因為拒絕做 Negative Testing 而被解僱的新聞。但很奇怪,似乎跟 Negative Testing 的用意初衷不一樣。測試也通常會在測試部門以測試手機去做,很少會直接用 end user 的手機做測試。唯一有可能的測試會是 A/B Test,就是實際用兩種不同的實作方式去實驗 end user 在 A/B 哪一種情境的使用下會比較順暢,但 A/B Test 應該不會跟 app 的耗電有關。

Ask HN: What is “negative testing” in a mobile app? | Hacker News 這邊有做討論,有人猜測,有可能是刻意用 user 的手機,測試在低電源的手機狀況下,app 還能不能運作。但就算要這樣測試,也不可能會先故意將 user 的手機電量消耗掉再做測試,這樣做太沒有效率。也有可能是報導內容誤植 Negative Testing 這個測試名詞。

References

Negative testing - Wikipedia

Negative Testing