iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 11
1

前言

前面提到的Paxos:

  1. Leaderless,每一個replica server都可以當Proposer去說服系統達成共識,決定最終的v值
  2. 保證「只要過半數」的servers都接受共識後,共識不會被破壞,最終系統每一個servers都會接受該共識

這是Lamport為了解決分散式系統,而一系列提出我們現在看到的Lamport Logical ClockBASE理念同時發展出為了來保證Consistency的Paxos Consensus Algorithm

但是就像在介紹CAP/ACID時說得,其實分散式系統的演化跟資料庫的演化是相輔相成的,因此在資料庫領域也有針對ACID與多個資料庫共同參與的Transaction保持Atomic與一致性,而設計出另一種一致性演算法,也就是 2 Phase Commitment,簡稱 2PC

2 Phase Commitment

單一個資料庫

我們前面提到資料庫的Transaction一般必須滿足ACID特性
ACID:

  • A-tomicity: 一個Transaction裡的所有動作要不全部成功或著失敗。
  • C-onsistency: 一個Transaction只能將資料庫從一個合法的狀態轉移到另一個合法的狀態,也就是Transaction結束後,所有的資料仍然符合資料庫定義的約束。
  • I-solation: 多個Transactions可能同時發生,保證這些Transactions的執行等價於就像他們是一系列的(sequencially)而非同時的,得到合理的結果,基本上就是讓同時發生的transactions處理(排序之類的)後,non overlapping的進行。
  • D-urability: 一個Transaction結束後,對數據的改動就是永久保存的,即使系統失效重啟。

而常見的Web系統串接資料庫時,一般常見都是下面的架構

  1. Client發起了一個會更動到儲存在資料庫中資料的請求(修改帳號、購物)
  2. Server可能自己處理或是藉由Library/Driver來保證ACID特性,對資料庫發起beginTransaction() -> Action on DB -> commit()來修改資料庫內容。

多個資料庫參與一筆Transaction

當業務變得複雜時,可能改動到的不只一個資料庫,比方說下面的情境。

一個購物過程:

  1. 後面的系統比須從倉儲資料庫減少該貨物庫存
  2. 另一方面在送貨資料庫上加入該貨物

此時如果中間因為網路掉封包或是延遲甚至斷線,導致只有一個資料庫執行了動作,另一個資料庫沒有更新到,那數據最終將會不合理。
(這邊就類似前面提到的分散式儲存的一致性特性)

為了保證ACID特性:

  1. Warehouse Management DB 和 Dispatch DB 要不都一起執行了更新,要不就一起沒有更新 - Atomic
  2. Dispatch 增加的貨物數量必須等於 Warehouse Management DB減少的貨物數量 - Consistency
  3. 在兩個DB都完成更新前,兩個DB的結果要是 不可見的 ,也不能有別的Transaction插入任一個DB執行 - Isolation
    E.g. Warehouse Management DB先完成更新了但是Dispatch DB還沒,這時不應該有任何一個Transaction可以執行在Warehouse Management DB上,因為Dispatch DB的更新可能失敗,而Warehouse Management DB上的結果應該要能夠rollbacks以保持Atomic

而這個情境下大部分是不允許Weak Consistency的,
因此2 Phase Commitment就是在這邊運作來達到Strong Consistency,
保證兩個DB都可以 commit actions或是abort actions

2PC 演算法

假設

  1. 在執行Transaction前參與者皆儲存原本的資料,以方便後續失敗時的rollbacks
  2. 因此當Transaction開始執行時,所有動作皆是執行在暫時的資料副本上
  3. 參與間的通訊不限定方法。

角色

  1. Coordinator: 負責發起與維護2PC流程,可能是Client或是Middleware,不會更換。
  2. Participant: 參與Transaction的DB或是儲存設備

流程

一樣分成兩個Phase

  1. Phase1:
    • Coordinator: 向所有人發送Prepare訊息
    • Participants: 先複製一份預計被更新的資料,接下來的操作將會先執行在副本上。向Coordinator回覆兩種訊息
      • Ready: 完成資料複製後回覆完成
      • Abort: 如果資料無法複製,原因可能為
        • data還在執行上一個transaction,被lock住(Isolation)

Note:

  • 如果Participants失效或是網路延遲,Coordinator有timeout機制。
  • 原本那一份備用作為rollbacks時用
  • 副本在確定2PC完成後就會commit到DB中
  1. Phase2:
    • Coordinator: 檢查是否從「所有」的Participants收到Ready訊息。
      • Ready: 向所有的Participants發送Commit訊息

        1. 被更新過的副本操作變成最新的資料
        2. Participants必須回覆Done訊息給Coordinator
        3. Distributed Transaction 完成
      • Abort: 只要有收到一個或是發生Timeout

        1. Coordinator發送Abort給所有的Participants
        2. 丟棄被更新的過的副本
        3. Distributed Transaction 失敗

圖解

1a). Coordinator向所有的Participants發送Prepare
1b). Participants複製資料後,回覆Ready或是Abort或是直接Timeout
2). 如果有任一個回覆Abort或是Timeout,就宣告Distributed Transaction 失敗。否則Distributed Transaction 完成
2). 成功,Coordinator發送Commit。失敗,Coordinator發送Abort

討論

2PC的優缺點非常直觀,因為本身的演算法可以說很簡單。

  • 優點: 簡單好實作
  • 缺點: 可以看到相比於Paxos只有一個Coordinator。如果Participants失效或是斷線,有Timeout機制。但是如果是Coordinator失效則Participants會因為每一個步驟是同步操作,在沒有收到回覆的情況下將會永久Block住,必須另外實作來對這種情況傳送Rollbacks或是Abort的訊息給Participants

因此明天我們將來看另一個演算法 - 3PC,如何解決2PC的問題。


上一篇
Day 10 - 共識演算法之虛構的希臘城邦 - Paxos(下)
下一篇
Day 12 - 共識演算法 - 3 Phase Commitment (3PC)
系列文
分散式系統 - 在分散的世界中保持一致30

尚未有邦友留言

立即登入留言