iT邦幫忙

2021 iThome 鐵人賽

DAY 19
0
AI & Data

資料工程師修煉之路 Part II系列 第 19

Consistency and Consensus (3-3) - Total Order Broadcast

[Day 19] Consistency and Consensus (3-3) - Total Order Broadcast

Day 18

Total Order Broadcast

雖然 昨天 講的 Lamport timestamp 能定義符合因果關係的全局順序,但它們不足以解決一些分散式系統中的常見問題,例如你的系統想要讓使用者名稱為唯一性限制,當有 2 個使用者並發 (concurrent) 同時申請帳號時,你得決定哪個使用者能申請帳號成功,Lamport timestamp 有全局順序,所以你可以去所有的節點匯總所有的使用者名稱,然後看誰先誰後就好了對吧!?

但這個難處就是你得立即決定誰申請成功,在那個當下你並不曉得其他節點操作為何,這些操作可能穿插在全局順序之中。

為了實現唯一性限制這種功能,只用全局順序是不夠的,你必須知道這個順序也是 最終 順序;就像你在建立使用者名稱時,知道了沒有其他節點聲明要在全局順序中使用該名稱,那麼你就能安全宣告你的操作能執行成功。

這個議題稱之為 全局順序廣播 (total order broadcast)

全局順序廣播的屬性 (the properties of total order broadcast)

全局順序廣播通常視為一種交換訊息用的協定,它需要滿足 2 個安全屬性:

可靠交付 (Reliable delivery)

​ 沒有訊息遺失:如果一封訊息可被交付於某節點,那麼它也要能交付於所有節點。

完全順序交付 (Totally ordered delivery)

​ 每一個節點的訊息順序都相同。

使用全局順序廣播 (using total order broadcast)

共識服務像 Zookeeper 就有實現全局順序廣播,所以它跟共識算法有很強的聯繫關係,我們會在 Day 21 介紹。

另外全局順序廣播正是資料庫做數據複製時必要的協定:如果任一訊息寫入至資料庫,其他副本也得用相同順序寫入,那麼副本間就能保持其一致性,該原則也稱為 狀態機複製 (state machine replication)

還有它能被用在序列化隔離 (serializable isolation) 上,如同 Day 6 討論的 連續執行 (Serial Execution) transaction,每一個 transaction 的預存程序 (stored procedures) 都能在所有節點用相同順序執行,故資料庫的每個分區跟副本也能保持一致性。

最後,全局順序廣播能用在提供 擊劍令牌 (Fencing token) 的鎖服務上 (Day 12),每一個 request 獲取鎖時也會附加訊息在 log 裡,所有訊息按順序編號,用作擊劍令牌;在 Zookeeper 中,該編號就是 zxid

全局順序廣播最強的面向是它固定了所有已交付訊息的順序,當後續的訊息抵達時,節點不允許往前面的位置回溯訊息,這事實也使全局順序廣播比 timestamp 排序還強。


上一篇
Consistency and Consensus (3-2) - Lamport Timestamp
下一篇
Consistency and Consensus (4-1) - Atomic Commit and Two-Phase Commit(2pC)
系列文
資料工程師修煉之路 Part II30

尚未有邦友留言

立即登入留言