續 Day 17

序列號排序 (Sequence Number Ordering)

使用 timestamp 是排序事件的好方法，我們曾在 2021 Day 11 - 順序性事件的時間戳記 看過用 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 的排序與因果關係一致。