分散式系統的共識協議: 2PC/3PC篇

04-25

2PC (兩階段提交)協議和3PC (三階段提交)協議本身其實很簡單. 我盡量通過少寫字, 多上圖的方法, 用一個coordinator和三個voter達成共識的例子來說明這兩個協議的想法.

2PC (兩階段提交)協議

2PC的原理

顧名思義, 2PC協議有兩個階段:Propose和Commit. 在無failure情況下的2PC協議流程的畫風是這樣的:

Propose階段:

coordinator: "昨夜驗人有驚喜, 今天都投票出六娃"
voter1/voter2/voter3: "好的女王大人!"

Commit階段

coordinator: "投六娃"
voter1/voter2/voter3: "投了女王大人!" (畫外音: 六娃撲街)

圖1: 2PC, coordinator提議通過, voter{1,2,3}達成新的共識

如果有至少一個voter (比如voter3)在Propose階段投了反對票, 那麼propose通過失敗. coordinator就會在Commit(or abort)階段跟所有voter說, 放棄這個propose.

圖2: 2PC, coordinator提議沒有通過, voter{1,2,3}保持舊有的共識

2PC的缺陷

2PC的缺點在於不能處理fail-stop形式的節點failure. 比如下圖這種情況. 假設coordinator和voter3都在Commit這個階段crash了, 而voter1和voter2沒有收到commit消息. 這時候voter1和voter2就陷入了一個困境. 因為他們並不能判斷現在是兩個場景中的哪一種: (1)上輪全票通過然後voter3第一個收到了commit的消息並在commit操作之後crash了, (2)上輪voter3反對所以乾脆沒有通過.

圖3: 2PC, coordinator和voter3 crash, voter{1,2}無法判斷當前狀態而卡死

2PC在這種fail-stop情況下會失敗是因為voter在得知Propose Phase結果後就直接commit了, 而並沒有在commit之前告知其他voter自己已收到Propose Phase的結果. 從而導致在coordinator和一個voter雙雙掉線的情況下, 其餘voter不但無法復原Propose Phase的結果, 也無法知道掉線的voter是否打算甚至已經commit. 為了解決這一問題, 3PC了解一下.

3PC (三階段提交)協議

3PC的原理

簡單的說來, 3PC就是把2PC的Commit階段拆成了PreCommit和Commit兩個階段. 通過進入增加的這一個PreCommit階段, voter可以得到Propose階段的投票結果, 但不會commit; 而通過進入Commit階段, voter可以盤出其他每個voter也都打算commit了, 從而可以放心的commit.

換言之, 3PC在2PC的Commit階段里增加了一個barrier(即相當於告訴其他所有voter, 我收到了Propose的結果啦). 在這個barrier之前coordinator掉線的話, 其他voter可以得出結論不是每個voter都收到Propose Phase的結果, 從而放棄或選出新的coordinator; 在這個barrier之後coordinator掉線的話, 每個voter會放心的commit, 因為他們知道其他voter也都做同樣的計劃.

圖4: 3PC, coordinator提議通過, voter{1,2,3}達成新的共識

3PC的缺陷

3PC可以有效的處理fail-stop的模式, 但不能處理網路劃分(network partition)的情況---節點互相不能通信. 假設在PreCommit階段所有節點被一分為二, 收到preCommit消息的voter在一邊, 而沒有收到這個消息的在另外一邊. 在這種情況下, 兩邊就可能會選出新的coordinator而做出不同的決定.

圖5: 3PC, network partition, voter{1,2,3}失去共識

除了網路劃分以外, 3PC也不能處理fail-recover的錯誤情況. 簡單說來當coordinator收到preCommit的確認前crash, 於是其他某一個voter接替了原coordinator的任務而開始組織所有voter commit. 而與此同時原coordinator重啟後又回到了網路中, 開始繼續之前的回合---發送abort給各位voter因為它並沒有收到preCommit. 此時有可能會出現原coordinator和繼任的coordinator給不同節點發送相矛盾的commit和abort指令, 從而出現個節點的狀態分歧.

這種情況等價於一個更真實或者更負責的網路環境假設: 非同步網路. 在這種假設下, 網路傳輸時間可能任意長. 為了解決這種情況, 那就得請出下一篇的主角: Paxos

總結

2PC使用兩個roundtrip來達成新的共識或維持舊有的共識. 其局限性在於不能保證有節點永久性崩潰(fail-stop)的情況下演算法能向前推進;
3PC擴展了2PC, 使用三個roundtrip達成共識. 其局限性在於不能保證在節點暫時性崩潰(fail-recover), 或是有網路劃分的情況下, 共識依舊成立.

分散式系統的共識協議: 2PC/3PC篇

2PC (兩階段提交)協議

3PC (三階段提交)協議

總結

推薦閱讀