本文為 Design Data Intensive Applications 的書摘 + 個人心得。
順序這件事在 Design Data Intensive Applications 這本書中重複到提到了很多次，代表了它是重要的基礎知識，從以前到現在，我們總共討論過：
- Leaders and Followers：single-leader 類型的數據複製資料庫用 replaction log 記錄操作，讓 follower 節點能以同樣順序做副本。
- 序列化隔離 (serializable isolation)：在單一執行緒按照順序執行 transactions。
- 順序性事件的時間戳記
現在就讓我們深入探討、連結順序、線性一致性和共識的相關知識吧！
排序和因果關係 (Ordering and Causality)
排序這件事帶給我們最重要的啟發就是因果關係，其實我們已經展示了多個有關因果關係很重要的例子了：
- Leaders and Followers – 圖 5-5：答案比問題還早出現。
- Multi-Leader Replication – 圖 5-9：insert 比 update 還晚出現。
- Leaderless Replication – Happend before 關係：若 A 比 B 早發生，則 B 應該要知道 A；若是並發發生，則 A B 互相不知道對方。
- Snapshot Isolation：transaction 的資料來自有一致性快照中，而快照就等於 因果關係 (causality) 。
- Serializable Snapshot Isolation：序列化快照隔離能依不同 transaction 的因果關係檢測 write skew。
因導致果，而因果來自事件順序，如果系統之順序來自遵守因果關係，我們稱它為 因果一致性 (causally consistent)，就像快照隔離那樣，你看到的資料必定先於其他 transaction 操作而來。
因果順序不是全局順序 (the causal order is not a total order)
全局順序允許你比較任何 2 個元素的大小，像給它數字 5 跟 13，你能知道 13 比 5 大；然而若要你比較 2 個數學集合 {a, b} 和 {b, c} 哪個大呢？我們並不知道哪個大，因為 2 個集合彼此不是對方的子集合，視為 不可比 (incomparable)，這 2 個集合也是 部分順序 (partially ordered)。
全局順序和部分順序若反映在一致性模型裡就是以下這 2 個：
線性一致性 (Linearizability)
線性化系統是全局順序，因為資料只有一份且操作都是原子操作，所以我們可以很輕鬆知道 2 個操作誰先誰後，視覺化時序圖可參考 Linearizability 的圖 9-4。
因果一致性 (Causality)
2 個事件能排序代表他們有因果關係（一個發生在另一個之前），但如果他們是並發發生的話，則就是不可比，所以因果關係也等於是部分順序，非全局順序。
並發事件意味者時序會分支，然後在合併，不同分支的操作是不可比，我們可以來看一下 2020 Day 26 圖 5-14， 它並不是一條直線幹到底，而是並發的發生多個操作，然後合併，箭頭的指向關係也代表了 因果依賴 (causal dependencies)。
另一個大家更有感的例子就是 Git 啦！版本歷史就很像因果關係，一個 commit 必定發生在某 commit 之後，合併時會組合多個並發分支的 commit。
序列號排序 (Sequence Number Ordering)
使用 timestamp 是排序事件的好方法，我們曾在 Unreliable Clocks – 順序性事件的時間戳記 看過用 timestamp 做排序的例子，當時我們提到可以使用 邏輯時鐘 (logical clocks) 來取代 日歷鐘 (time-of-day)，邏輯時鐘通常就是使用 counter 針對每個操作做累加（也就是序列號），透過序列號或 timestamp 你很輕鬆的就能知道全局順序。
single-leader 類型的數據複製資料庫很好實作序列號，leader 就幫每個寫入計數就好了，那麼非 single-leader 類型的資料庫該怎麼辦呢？
非因果關係序列號產生器 (Noncausal sequence number generators)
在實務上替非 single-leader 資料庫（multi-leader, leaderless）建置序列號有以下 3 種方法：
- 每一個節點可以產生自已獨立的序列號，舉例來說若你有 2 個節點，節點 A 只產生單數，節點 B 只產生偶數這樣。
- 使用老方法幫每個操作加上來自日歷鐘的 timestamp。
- 預先分配序列號區塊，舉例來說節點 A 每次都是取得 1 ~ 1000 的序列號區塊，節點 B 取得 1001 ~ 2000 的序列號區塊，然後每個節點獨立的分配該區塊的號碼。
相比 single-leader 來看，這 3 個方法都有很好的可擴充性，然而，這些序列號不符合因果關係。
Lamport timestamp
救星來了，馬上要來介紹一個能在分散式系統產生有因果關係的序列號方法，Lamport timestamp，來自 1978 年由 Leslie Lamport 發表，這也是在分散式系統領域中被引用最多次的論文之一。
Lamport timestamp 提供有因果關係全局順序的方式如下圖 9-8， 每一個節點都有唯一的 ID，且每個節點都會計算已執行操作的數量，Lamport timestamp 資料就是個簡單的 (counter, 節點 ID)，2 個節點或許會有一樣的 counter，但是加入節點 ID 後，就能是該 timestamp 成為唯一。
Lamport timestamp 基本上跟日歷鐘沒啥關係，但它能提供全局順序，如果你想比較 2 個 Lamport timestamp 大小，首先就看 counter 誰大，倘若 2 個 timestamp counter 相同，就以節點 ID 大小為主。
另外每個節點跟 Client 都要追蹤最大 counter 值，所以每一個 request 都要包含目前所知的最大值，當一個節點接收 request 或回覆 response 時，若目前收到的最大 counter 值大於自已的值，要立馬對齊自己 counter 值至最大值。
如上圖 9-8， 當 Client A 從節點 2 接收到 counter 值為 5，然它會發送最大值 5 給節點 1，那時節點 1 counter 值 是 1， 所以它會加 5 變成 6，然後再回傳回去。
因為最大 counter 值會在每一個操作中被攜帶，所以該方案能確保 Lamport timestamp 的排序與因果關係一致。
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 就有實現全局順序廣播，所以它跟共識算法有很強的聯繫關係，
另外全局順序廣播正是資料庫做數據複製時必要的協定：如果任一訊息寫入至資料庫，其他副本也得用相同順序寫入，那麼副本間就能保持其一致性，該原則也稱為 狀態機複製 (state machine replication)。
還有它能被用在序列化隔離 (serializable isolation) 上，如同之前討論的 連續執行 (Serial Execution) transaction，每一個 transaction 的預存程序 (stored procedures) 都能在所有節點用相同順序執行，故資料庫的每個分區跟副本也能保持一致性。
最後，全局順序廣播能用在提供 擊劍令牌 (Fencing token) 的鎖服務上，每一個 request 獲取鎖時也會附加訊息在 log 裡，所有訊息按順序編號，用作擊劍令牌；在 Zookeeper 中，該編號就是 zxid。
全局順序廣播最強的面向是它固定了所有已交付訊息的順序，當後續的訊息抵達時，節點不允許往前面的位置回溯訊息，這事實也使全局順序廣播比 timestamp 排序還強。
