分散式系統 Distributed Systems_Time, clocks, and ordering of events_Week3筆記
時間、時脈與事件排序
分散式系統中時間的重要性-歷史重大事件
2012 年 6 月 30 日至 7 月 1 日（英國時間），全球許多線上服務和系統曾同時崩潰 (crashed simultaneously)，伺服器鎖定並停止回應。航空公司數小時無法處理預訂或登機手續。
時間測量的應用 (Clocks and time in distributed systems)
► Schedulers, timeouts, failure detectors, retry timers
► 效能量測、統計、效能剖析 Performance measurements, statistics, profiling
► Log files & databases: record when an eventoccurred
► Data with time-limited validity (e.g. cache entries)
► 跨多個節點判定事件的先後順序 Determining order of events across several nodes
時脈的區分，兩種時脈：
• 實體時脈 (physical clocks)：計算經過的秒數 (count number of seconds elapsed)。
• 邏輯時脈 (logical clocks)：計算事件數，例如發送的訊息數。(count events, e.g. messages sent)
注意：數位電子產品中的時脈（振盪器 (oscillator)） 並不等同於分散式系統中的時脈(時間戳記的來源 (source of timestamps))
1.石英時脈 (Quartz clocks)
->日常使用時鐘(手機、手錶、掛鐘、數位顯示器內建)
基於石英(二氧化矽)晶體經雷射修剪 (laser-trimmed)，以特定頻率機械共振 (mechanically resonate)
- 利用壓電效應 (Piezoelectric effect) : 一塊石英若用槌子敲打或稍微彎曲，會發出微小電脈衝。若施加一些電流，也類似讓其被彎曲或敲打般。
- 振盪器電路 (Oscillator circuit) 在共振頻率 (resonant frequency) 產生訊號，計算循環次數來測量經過時間。
- 就好比如手錶的心臟會跳動，但他是維持固定頻率震動，不像人心跳會加速、減緩。
- 像是手錶鐘裡的音叉十分小大概4毫米寬，如以下圖片顯示。當其震動時會發出非常高的音調。
- 然而這類高頻聲音不會被人耳感受到。被設計用於每秒震動32768次，時鐘內可去計數這些震動。然後會因為溫度壓力而有加速減速的潛在問題。
2.原子鐘Atomic clocks (much more accurate)->改良過的石英鐘
- 不具放射性、不危險
- 以單一銫(Cs,Caesium) 或銣(Rb,Rubidium) 來計時，將電子振盪器調諧至該共振頻率。
- Cs有懸浮在原子外的電子，會吸收特定頻率的光(也就是微波 約9,192,631,77GHz)
- Caesium-133 has a resonance (“hyperfine transition”) at ≈ 9 GHz
- 1 second = 9,192,631,770 periods of that signal
- Accuracy ≈ 1 in 10−14 (1 second in 3 million years)
3.GPS 作為時間來源 (GPS as time source)
- 由 31 顆衛星組成，每顆衛星攜帶一個原子鐘。
- 衛星會廣播目前的時間與位置。
- 依據衛星與接收器之間的光速傳播延遲來計算位置。
全球時間標準(Coordinated Universal Time, UTC)
- 格林威治標準時間 (Greenwich Mean Time, GMT, solar time):
太陽在格林威治子午線以南時為中午 - 以地球運轉週期計時的 “世界時”(Universal Time, UT)。，一秒是依據地球繞著軸自轉和繞太陽的公轉，以平均太陽日的1⁄86400來定義。
- 國際原子時間 (International Atomic Time, TAI)：
基於銫-133 的共振週期來定義一天
1 天 = 24 × 60 × 60 × 銫-133 的共振頻率 9,192,631,770 個週期。
問題：地球的自轉速度不是常數。
折衷：UTC = 以 TAI 為基礎，並加入對地球自轉的校正（用以補償自轉不均）。
時區(Time Zones)與夏令時間（daylight savings time）都是相對於 UTC 的偏移量。
Leap seconds閏秒調整（由天文學家決定）
日常生活的日曆時鐘需要增減一秒鐘。之所以需要閏秒，是因為地球相對太陽自轉的時間並不是永恆不變的，和目前的國際標準參考時間的原子鐘，一直會浮動地存在些許差異。
因此，每經過一段時間，就需要在日曆時鐘上增減一秒，來讓兩者不會越差越遠。
每年在 6 月 30 日 與 12 月 31 日 的 23:59:59 UTC，可能發生下列三種情況之一:
- 時鐘立即跳到 00:00:00，跳過一秒(負閏秒)。
- 時鐘如常，一秒後走到 00:00:00。
- 時鐘一秒後先到 23:59:60，再過一秒到 00:00:00(正閏秒)。
早期大多數應用於軟體迎面裡面其實是沒特別處裡Leap Seconds情境的，甚至直接忽略。
然後牽涉底層OS的系統則格外要求。以2012年歷史事件航班機議題就是因為Leap Seconds造成。
兩種最常見的時間表示法
- Unix time：自 1970-01-01 00:00:00 UTC（epoch）起算的秒數（不計入閏秒）。
- ISO 8601：以年、月、日、時、分、秒與相對 UTC 的時區偏移表示。
範例：2020-11-09T09:50:17+00:00
Clock synchronisation(電腦校時/時間同步)
電腦以石英時鐘追蹤實際時間／UTC（內建電池，斷電時仍持續運行）。由於時鐘飄移(clock drift)，時鐘誤差會逐漸增加。
時鐘偏差(clock skew):
同一時刻兩個時鐘之間的時間差 ⇒ 目標是盡可能把偏差降到最低。
同一時刻兩個時鐘之間的時間差 ⇒ 目標是盡可能把偏差降到最低。
解法:
週期性向擁有更精準時間來源的伺服器取得現在時間
例如：原子鐘或 GPS 接收器，並進行校時。
週期性向擁有更精準時間來源的伺服器取得現在時間
例如：原子鐘或 GPS 接收器，並進行校時。
協定：
- NTP(Network Time Protocol):由具精準時鐘的 NTP 伺服器提供時間，用戶端查詢伺服器並依收到的回應調整本機時間。
- PTP(Precision Time Protocol):精密時間協定，用於更高精度與更低延遲的校時需求（常見於資料中心／工業網路）。
NTP-Clinet/Server Request跟Response的評估耗時
Round-trip network delay 往返網路延遲(不含伺服器處理時間)
- t4 - t1 = 整趟來回時間
- t3 - t2 = 伺服器中途運算處裡耗時
- 相減之後就會近似為純網路之間往返延遲
Clock skew (用戶端相對於伺服器的時鐘偏移):
直觀上是「去程延遲估計」與「回程延遲估計」的平均
Happens-Before關係
把「事件之間能否互相影響（因果關係）」形式化，而不依賴物理時鐘。
event : 在某節點上發生的事（傳送/接收訊息，或本地執行步驟）。
a happens before b（寫作 a → b）若且唯若
- a 與 b 在同一節點發生，且 a 在該節點的本地執行順序上先於 b
- a 傳訊息 m ，b 接收m
- 存在事件 c 使得 a → c 且 c → b。
happens-before 關係是偏序
- 有可能既不是a -> b 也非b->a
- 在此情況a 與b屬於並發(concurrent)，寫作 a || b。
並發(concurrent)
- 不等於同時發生
- 意思是兩個事件在發生時彼此「不知道對方」，沒有因果關係(Causality)。
Ref:
多出的一秒鐘~閏秒(Leap second)
留言
張貼留言