[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 排序還強。