分散式系統的 clock

前幾天在 Hacker News 上看到「Clocks and Causality – Ordering Events in Distributed Systems (2022) (exhypothesi.com)」這篇，講分散式系統上 clock 的設計，作者也有跑出來在 Hacker News 上面跟大家聊一下 (帳號是 thoughtlede)，原文在「Clocks and Causality – Ordering Events in Distributed Systems」這邊。

文章裡面主要講空間是 的 Lamport timestamp 與空間是 的 Vector clock (這邊的 相對於節點數量)，以及這兩個對應的擴充版本：

作者會整理這些資料的原因是因為在研究 CRDT 的時候看到演算法中常常會需要處理分散式系統裡面事件的順序，所以花了一些時間整理常見的方式：

Author here. Pleasantly surprised to see the article here.

Some context behind the article. I studied CRDTs for a few months, and noticed that different CRDT designs use logical clocks in different and clever ways. And I haven’t seen anyone narrate all those ways of use in one article. My attempt with this article was to dredge up those flavors of logical clocks into one article and give them names for future reference.

(To respond to a couple of other comments, I ignored atomic (and gps-based) clocks in this discussion, as indicated in my footnote 3).

我記得還有一個 Interval Tree Clocks 可以參考 (在「Interval Tree Clocks」這邊講的比較清楚)，是針對節點的動態增刪而改善的演算法，但不確定有什麼比較有名的系統有用。

大多數應該都是用 Vector clock，畢竟是在 2007 年的「Dynamo: Amazon’s Highly Available Key-value Store」被發揚光大，而且也算是還不錯的演算法？

Read More