Trouble with Distributed Systems (2) – Unreliable Clocks

不可靠的時鐘 (Unreliable Clocks)

時鐘對應用程式來說很重要，它可以回答以下問題：

這個 request 該 timeout 了嗎？
服務的 99 百分位回應時間為何？
在前五分鐘的平均 QPS 多少？
使用者在我們網站會停留多久？
文章什麼時候發佈的？
Cache 什麼時候過期的？
log 裡的錯誤訊息是在什麼候發生的？

在分散式系統中，時間是一件棘手的事情，因為彼此的溝通可能會延遲且又不曉得延遲多久，更甚者，每台機器在硬體內都有自己的時鐘：石英振盪器 (quartz crystal oscillator)，此設備並不完全準確，所以每台機器都有自己的時間概念，這就代表了跟其他機器比起來可能有快有慢。

還好我們可以選擇使用 網路時間協定 (Network Time Protocol) NTP 來同步時鐘。

單調遞增時鐘 v.s. 日歷鐘 (Monotonic Versus Time-of-Day Clocks)

現代電腦有 2 個類型的時鐘： 單調遞增時鐘 (Monotonic Clock) 和 日曆鐘 (Time-of-Day Clock)，區分它們是很重要的，它們有不同的用途。

日曆鐘 (Time-of-Day Clock)

日曆鐘根據了 壁時計時刻 (wall-clock time) 回傳了掛上該時鐘開始到現在的時間，簡單說就是從 UTC 1970-01-01 開始到現在經過的秒數（或毫秒），不計算閏秒。相關函式有 Linux 的 clock_gettime(CLOCK_REALTIME) 和 Java 的 System.currentTimeMillis() 。

日曆鐘通常會使用 NTP 來同步時間，在特定情形中，如果本地時鐘超過 NTP 伺服器太多，它會強制重置且跳回先前的時間點，因為上述論點以及它們經常忽略閏秒的關係，日曆鐘比較不適合來測量執行時間。

單調遞增時鐘 (Monotonic Clock)

單調遞增時鐘就很適合來測量執行時間或間隔 (interval) 、timeout 或回應時間。它來自於系統啟動後流逝的時間，所以它保證時間會一直往前進，相關函式有 Linux 的 clock_gettime(CLOCK_MONOTONIC) 和 Java 的 System.nanoTime() 。

當 NTP 檢測到電腦的石英移動太快或太慢時，NTP 有可能會調整單調遞增時鐘向前移動的頻率（稱為 slewing the clock），預設是允許時鐘速率加快或減慢 0.05%，但 NTP 不會讓該時鐘往前或往後跳，這個特性讓大多數的系統能將執行時間等等的測量精確到奈秒等級。

時鐘同步和精度 (CLock Synchronization and Accuracy)

昨天講的 單調遞增時鐘 (Monotonic Clock) 不需要同步，而 日曆鐘 (Time-of-Day Clock) 就需要與 NTP 伺服器或外部時間資源做同步，但依舊很不幸的，你希望它應該是正確的時鐘並不是這麼可靠，以下是可能會發生的鬼故事：

電腦內的石英鐘不是那麼準確，它會因為溫度而漂移 (drifts)，Google 假設其伺服器的漂移為 200 ppm (百萬分之一 – parts per million)，這就代表了重新同步的時鐘每 30 秒會發生 6 毫秒 (ms) 的漂移，或每一天有17 秒的漂移。
NTP 伺服器可能意外地被防火墻檔住。
NTP 同步的效果跟網路延遲成正相關，一個實驗展示了透過網路進行同步時會有 35 毫秒 (ms) 的最小誤差，在網路壅塞的場景可能會到 1 秒以上。
閏秒會讓一分鐘只有 59 秒或 61 秒長，會讓一些設計不良，沒有考慮到閏秒的系統時序假設壞掉，事實上，閏秒曾讓許多大型系統死亡；最佳的解決方法就是讓 NTP 伺服器說謊，在一天中逐步地調整。
在虛擬機中，硬體時鐘也是虛擬的，因為 CPU 資源是與其他 VM 分享，暫時沒在執行的 VM 會暫停幾 10 毫秒，所以從應用系統的角度來看，時鐘就會發生瞬間往前進的情況。

雖然大多數人的公司都不太在意時間問題啦！但如果你的系統是跟投資相關，就會有法規要求你的時間精度，像 MiFID II （歐洲金融市場工具指令）就要求有高頻交易的金融機構，他們的時鐘不得與 UTC 時間有超過 100 微秒以上的誤差。

依靠同步化時鐘

強壯的軟體也是需要為了不準確的時鐘做準備！不準確的時鐘之影響是緩慢且巨大的，如果石英鐘有缺陷或 NTP 使用者端未設定好，應用系統大多數的工作依舊會正常運作，時鐘緩慢的漂移，慢慢的遠離真實時間，直到它發生了意想不到的故障。

因此，若你的應用系統會依靠同步化時鐘，必須要確保和檢測所有機器節點的時間偏移量，任一節點時間漂移過多要視為節點故障並從叢集中移除。

接下來就舉個依賴日曆鐘結果悲劇的例子吧！

順序性事件的時間戳記 (timestamp)

這裡有個 multi-leadar 分散式資料庫，資料庫會依靠事件的時間戳記 (timestamp) 做事情；若有 2 個用戶端同時往資料庫寫資料，如下圖 8-3， Client A 寫 x = 1 到 node 1，它複製資料到 node 2 和 3，Client B 往 node 3 對 x 累加 1（我們知道 x 應為 2）。

每個寫入都依據了日曆鐘標註了發生時的 timestamp，在這個例子中，node 1 和 node 3 的時間偏移小於 3 毫秒 (ms)，現在 node 1 x = 1 的 timestamp 為 42.004 秒，但 node 3 x 累加 1 的 timestamp 卻是 42.003 秒，node 2 同時接收到這 2 筆 replica，這就代表了若是使用 最後寫的是贏家 (last write wins) 策略，node 3 的寫入會被丟棄。

就算你使用了 NTP 同步日曆鐘，這種情況還是有可能會發生（如本篇文前半部份講的鬼故事），那這樣怎麼辦呢？我們可以使用一個累加的 counter 來取代日曆鐘解決事件的排序問題，也稱為 邏輯時鐘 (logical clocks)，它只關心事件的相關順序，也就是 happns-before 關係。