clock

Vector clock 的發明時間軸

一樣是在 Hacker News 上看到「Who invented vector clocks? (decomposition.al)」這篇文章，在找出誰發明了 vector clock，原文在「Who invented vector clocks?」。

主要有兩個不同的時間點，一個是 vector clock 概念的提出，另外一個是第一次用到 vector 這個詞。

這篇讓我覺得有趣的地方是，vector clock 本來就是在處理分散式系統裡面事件順序的問題，而這篇文章則是在找出真實世界裡面這些發明的先後順序，而且也牽扯到了各種 citation (類比到分散式系統裡事件的 dependency)。

分散式系統的 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」這邊。

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

作者會整理這些資料的原因是因為在研究 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」被發揚光大，而且也算是還不錯的演算法？

Amazon EC2 上的 gettimeofday 與 clock_gettime 的效能

看到「Two frequently used system calls are ~77% slower on AWS EC2」這篇在講 gettimeofday 與 clock_gettime 的效能，另外搜資料時發現應該也是作者提問的「gettimeofday() not using vDSO?」這篇。

在 EC2 比較新的機器上用 tsc 應該是沒問題的 (在 2015 的時候官方就這樣建議了)：

it seems tsc support in Xen has improved with version 4.0 and with improved CPU support in Sandy Bridge+ platforms. Modern EC2 machines should be okay with tsc. Check Xen version using dmesg | grep "Xen version". Amazon recommended the tsc clocksource already in re:Invent 2015 (https://www.slideshare.net/AmazonWebServices/cmp402-amazon-ec2-instances-deep-dive). I'm not yet running to production with this, but the situation doesn't seem as bad as implied by packagecloud.

開了一台 t2.micro 看 /sys/devices/system/clocksource/clocksource0/current_clocksource 看起來目前是設成 xen：

ubuntu@ip-172-31-22-165:~$ cat /sys/devices/system/clocksource/clocksource0/current_clocksource
xen

在「(CMP402) Amazon EC2 Instances Deep Dive」這邊也可以看到一些資料 (page 24 與 page 25)：

CPU 指令的速度

在「Infographics: Operation Costs in CPU Clock Cycles」這邊看到張有趣的圖片：

文章大致說明了底層指令速度差異的由來，另外也提到了 C/C++ Function Calls、Indirect and Virtual Calls、Allocations、Kernel Calls、C++ Exceptions 以及 Thread Context Switches 這些高階面向的 CPU clock cycle 差異...

不過重點還是在這張圖 XD