本文為 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)。
![](https://it-iron.s3.ap-northeast-1.amazonaws.com/2020/figure_5-14.png)
另一個大家更有感的例子就是 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 成為唯一。
![](https://it-iron.s3.ap-northeast-1.amazonaws.com/2021/figure_9-8.png)
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 排序還強。