不同程序的事件可以有先後關係,卻不能只憑各自寫下的日期時間判斷;分散式系統需要區分經過時間、實體時間與因果順序。 這些工具回答不同問題,沒有一種時間戳能自動提供所有保證。
本文接續過載與時間預算,回到故障模型中的程序與訊息,為下一階段的一致性模型建立基礎。
查證日期:2026-11-04。Lamport clock 依 1978 年原論文;向量時鐘參考 Mattern 原論文,實體時鐘介面以 Linux man-pages 為產品例子。未執行計時、時鐘同步或故障實驗,事件與數值均為自創。
日期時間與等待時間要分開
實體時鐘(physical clock)試圖對應真實時間;程式讀到的 wall clock 常用來產生日誌的日期時間。但主機之間可能有偏差,時間同步與人工校正也可能影響讀值,所以「A 日誌顯示 10:00:01、B 顯示 10:00:00」不一定代表 B 的事件較早。
量測「這次已等待多久」通常需要適合量測區間的單調時鐘(monotonic clock)。以 Linux 為例,CLOCK_REALTIME 是可調整的系統實體時間;CLOCK_MONOTONIC 不受實體時間不連續跳動影響,但其速率仍可受漸進調整,且不計入系統休眠時間。需要包含休眠時間時有 CLOCK_BOOTTIME 等不同語意。這些是 Linux 介面行為,不能當成所有語言或作業系統同名函式的保證。參考 Linux man-pages:clock_gettime(2)。
本地單調讀值也不是全世界共用的座標。主機 A 的讀值 500 與主機 B 的讀值 700,未指定共同基準時不能拿來算跨主機時間差。這解釋了為何傳遞剩餘預算與直接傳遞本地時鐘值不是同一回事。
不依賴日期,也能定義「先發生」
Lamport 定義的 happened-before 關係,用 a → b 表示 a 在因果上先於 b。它從三條規則建立:
- 同一程序內,先發生的事件先於後發生的事件。
- 一則訊息的送出,先於該訊息的接收。
- 關係具有遞移性:若
a → b且b → c,則a → c。
這定義的是偏序(partial order)。如果既無 a → b,也無 b → a,兩個事件在這個模型中是並行(concurrent)的;它們不必在實體時間上剛好同時,只是沒有可由這些規則建立的因果順序。參考 Lamport(1978):The Partial Ordering。
例如呼叫端送出「建立匯出」,API 收到後建立工作,回覆識別,呼叫端收到後才送出「查詢該工作」。這些事件透過程序順序與訊息交換構成因果鏈。若另一名使用者同時更新另一個獨立工作,且沒有訊息或其他依賴連結,則不應只靠兩台主機的日期強行推定兩個操作的因果。
實際模型必須包含重要依賴:若有人看見畫面後打電話請另一人更新,純粹只記錄服務內訊息的模型可能漏掉這個因果來源。時間戳能表達的關係,仍取決於系統捕捉了哪些事件。
Lamport clock 保存一個方向的推論
Lamport clock 為每個程序保存一個邏輯計數器。採以下慣例:本地事件與送出事件先加一,訊息帶上送出時間戳;接收時設為 max(本地值, 訊息值) + 1。
自創歷程中,A 與 B 初值皆為 0:
| 事件 | 更新 | 時間戳 |
|---|---|---|
| A 建立匯出意圖 | A 從 0 加到 1 | 1 |
| A 送出請求 | A 加到 2,訊息帶 2 | 2 |
| B 收到請求 | B 設為 max(0, 2) + 1 | 3 |
| B 保存結果 | B 加到 4 | 4 |
這滿足 a → b 時 C(a) < C(b)。但反過來不成立:另一個從未與 A 或 B 通訊的程序 C,可以因自己的本地事件數較多而得到 100;這不表示 B 的事件造成了 C 的事件。較大的數字也不代表經過較多毫秒。
再加上程序識別作為平手規則,可以把事件排成符合上述因果關係的全序;這仍是所選規則決定的順序,不是量得的真實時間全序。參考 Lamport(1978):Logical Clocks、Ordering the Events Totally。
給事件全序標籤,也不表示各程序已知道哪些事件存在、何時可安全執行,更不會讓節點自動同意同一份日誌。這些是後續協調與共識要另外解決的問題。
向量時鐘能表達並行,但有模型與成本
若要分辨因果與並行,可以讓每個程序保存一個分量的向量時鐘(vector clock)。以下採固定成員、完整攜帶向量、事件先增加自己的分量,接收時先逐分量取最大再增加接收者分量的教學慣例。
只有 A、B 兩個程序且初值為 [0, 0] 時:A 的本地事件得到 [1, 0],B 的獨立本地事件得到 [0, 1]。兩者都不是逐分量小於等於另一個,因此可以辨認為並行。若 A 再送訊息,攜帶 [2, 0],B 接收後得到 [2, 2],則前述兩個事件都在這個接收事件之前。
向量比較的慣例是:V(a) < V(b) 表示每個分量都不大於,且至少一個分量嚴格小於。在上述完整追蹤事件的模型中,它能表達 happened-before;若兩向量互不小於等於,便表示並行。參考 Mattern:Virtual Time and Global States of Distributed Systems,§7。
這個簡化模型需要替成員保存分量,節點增加、離開、版本裁剪與儲存空間都有代價。產品中的 version vector、裁剪規則與衝突偵測,不一定等同這裡完整記錄所有事件的向量時鐘。也不能看到兩個版本並行,就自動知道哪個業務結果正確:合併仍需要應用規則。
先問時間戳要證明什麼
| 需求 | 適合的概念起點 | 不能直接推導的事 |
|---|---|---|
| 本次請求已等多久 | 語意符合需求的本地區間時鐘 | 另一台主機事件的先後 |
| 日誌對應哪個日期時間 | 實體時鐘、同步與誤差資訊 | 時間很接近就存在因果 |
| 是否可能沿訊息影響另一事件 | happened-before 與邏輯時鐘 | Lamport 值較小就必然是原因 |
| 哪些版本互為並行 | 模型完整時的向量關係 | 如何依業務要求解決衝突 |
| 所有副本同意同一份命令順序 | 需要額外協調協定 | 只產生可排序 ID 就已達成共識 |
現在回到「建立工作後查詢」:我們已能描述兩次操作的因果關係,但如果查詢被送到另一份資料副本,服務是否必須回傳剛建立的工作?這需要另外指定一致性契約,會在下一階段的「一致性模型與操作歷程」處理。
相關文件
- 部分失敗與故障模型:區分時間假設與故障觀測。
- 過載、時間預算與背壓:回查經過時間的用途。
- 分散式系統知識索引:查看待撰寫的一致性、複寫與協調主線。