Physical clock vs logical Clock

less than 1 minute read

最近讀了幾篇老paper,包括Lamport clockClock vector這兩個著名的logical clock,還有一篇在講NTP出現以後,在實際系統中的應用。

Logical clock的目的是為了解決分散式系統中的common clock問題,也就是如果在系統中有個共用的clock,很多演算法的設計可以變得簡單。

不過NTP出現以後,因為每個process 都有synchronized clock,所以不就有一個common clock了嗎?為何現在的演算法還是會用logical clock

跟大神聊過以後,了解是correctnessperformance的trade off。在流量不大的情況下,我們可以無視每個process的time skew,但當流量大的時候,time skew會造成event order不正確,但是logical clock不會有這問題。

舉例來說,假設time skew是5ms。那如果我們每秒要處理超過2k的request,也就是平均每個request的處理時間低於5ms,這時候time skew造成的order問題發生頻率就會變高,基於physical clock設計的演算法就無法保證correctness

但如果是用在expiration相關的問題,physical clock就很好用了,一般來說expiration的單位至少是秒起跳,幾ms的time skew通常是可以容忍的,看到幾個lease相關的演算法就基於physical clock來設計。

Practical uses of synchronized clocks in distributed systems這篇paper,作者也提到用physical clock來設計演算法通常是處理performance問題,因為time skew的關係,在edge case的情況下無法保證correctness,因此系統會有問題。不過在一樣情境下,performance的degradation通常是可以接受的。

Updated: