iT邦幫忙

2021 iThome 鐵人賽

DAY 4
0
Software Development

什麼都不會還敢說你是 RD 啊?畢業後的後端入職前準備系列 第 4

【Day 4】物理時間、happens-before 關係、causality

回家再修文,先發ㄌ
晚點要補一下前一篇的 failure detectors

介紹分散式系統中的時間,主要分為

  • physical clocks: count number of seconds elapsed
  • logical clocks: count events, e.g. messages sent

這篇筆記在物理時間 3.1 3.2 不做太多著墨,
只需要知道因為誤差的關係,
分散式系統間的訊息傳遞不能以物理時間當作時戳,
否則可能會有時空旅行的可能。

3.3 會介紹邏輯時間的數學關係,以迎接第 4 章: Logical clock。

3.1 Physical clocks

對於分散式系統來說,物理時間較少使用。

  • 石英 quartz clock: 便宜、不夠精確,容易因為溫度上升而失準。是現代電子錶最常使用的。
  • atomic clock: 貴

UTC

根據 atomic 時間,但會依據地球自轉而有所校正。

GMT

leap seconds

校正 UTC 來大致符合地球自轉。
每年可能 +- 1 秒,會提前公告。
而這個東西會造成很大的問題!!
通常程式會直接忽略 leap seconds,對於一些系統來說這是很嚴重的事情。

leap second smearing

3.2 Clock synchronisation

  • clock drift: 一個時鐘與精準時間的誤差
  • clock skew: 兩個時鐘在某時刻的差距

如果兩個時鐘都有各自的 drift,那他們的 skew 隨著時間增加,所以需要 sync。
i.e. a時鐘慢了1秒,b時鐘快了1秒,每秒這兩個時鐘差就多2秒。

Network Time Protocol (NTP)

clock server 的層級:

  • Stratum 0: atomic clock or GPS receiver
  • Stratum 1: synced directly with stratum 0 device
  • Stratum 2: servers that sync with stratum 1, etc.

Estimating time over a network

時間校正

根據 client 和 server 的時間差,調整 client 時鐘的策略有 3 種:

  • slew: 加快或調慢一點點比例。
  • step: 把 client 調為 server 時間。
  • panic: 差異太大了,不做任何事,交給人解決。

Physical clock 主要分兩種,用錯麻煩多

Time-of-day clock

  • 從固定日期開始計算的時間 (e.g. 1 January 1970 epoch)
  • 可能突然增加或倒退(NTP stepping)
    因為 leap second 調整
  • 不同 node 可用此 Timestamps 比較
    Java: System.currentTimeMillis()
    Linux: clock_gettime(CLOCK_REALTIME)

Monotonic clock

  • 從 arbitrary point 開始計算的時間 (e.g. 從機器開機開始計時)
  • 只會增加
    moves at a nearly constant rate
  • Good for measuring elapsed time on a single node
    Java: System.nanoTime()
    Linux: clock_gettime(CLOCK_MONOTONIC)

Summary

所以單個電腦上要對某個動作計時,應該使用 monotonic clock。
如果是分散式系統,不得已得用 physical clock 來比較不同電腦的時間,則用 time-of-day clock。

3.3 Causality and happens-before

為什麼分散式系統上不能用物理時間?

再怎麼努力與 NTP sync,每個電腦上的物理時間還是有可能會有一點點誤差。
若以物理時間來重新排序訊息,一個不小心就可能時空旅行。
time skew > one way network delay?? 不太懂 3:27

happens-before

定義 happens-before relation
a -> b 代表 a happens-before b iff:

  • a b 兩事件在同個 node 上發生,a 先執行,b 後執行。
  • a b 兩事件在不同 node 上發生,a 是 n1 的傳送事件,b 是 n2 的接收事件。這應該很好理解。
  • 遞移律:今天有的事件 c,a -> c,c -> b ,可以推得 a -> b。

happens-before 是個 partial order,
有可能 既不是 a -> b 也不是 b -> a,稱之 concurrent。
a || b。

什麼?為什麼可以不是 a-> b 也不是 b-> a?

這可能小小的違反我們的直覺,
但 happens-before 關係是一種相對關係,
而我們直覺是基於物理時間的。

在分散式系統上,
如果不能使用物理時間,
那若沒有訊息傳遞,例如兩個 nodes 之間完全不聯繫,
我們無從去比較出兩個 node 上事件的 happens before relation 的。

concurrent 不代表 spontaneous!!
只是這兩個 events 不知道對方先發生還是後發生、無法比較而已。

  • partial order: 能夠將一個 set 中的部分元素做排列
  • total order: 能夠將一個 set 中的所有與素做排列

因果關係 Causality

happens-before relation 是一種可以討論分散式系統上事件之間因果關係的數學關係。

a -> b: a 可能 have caused b
a || b: a 不可能 have caused b

causal order
是代表
若 a causes b, then a happens before b?

似乎是從物理借鏡來的概念。
如果今天兩個事件發生的「距離夠遠」,就算時間很相近,但他們卻不會有關係,a 不可能影響 b。
分散式系統注重訊息的順序,其中也有同樣的概念,就是如果 a 跟 b 沒有 causal 關係的話,或許我們並不是很在意他們實際是不是在差不多的時間發生。
a || b : a 不可能 have caused b!


上一篇
【Day 3】分散式系統模型、容錯、高可用
下一篇
【Day 5】邏輯時間與廣播
系列文
什麼都不會還敢說你是 RD 啊?畢業後的後端入職前準備31
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言