搜尋文件

輸入關鍵字,搜尋標題與正文。

    分散式系統文件 04/08

    時鐘、事件順序與因果關係

    本文提要

    不同程序的事件可以有先後關係,卻不能只憑各自寫下的日期時間判斷;分散式系統需要區分經過時間、實體時間與因果順序。 這些工具回答不同問題,沒有一種時間戳能自動提供所有保證。

    18px · 寬鬆行距

    閱讀設定

    排版預覽 · 示範文字(可捲動)

    檔案與目錄

    Linux 以一棵從根目錄 / 開始的樹狀結構組織檔案。目錄用來整理檔案,也可以包含其他目錄。

    pwd
    ls -la /home
    18px

    16、18、20、22px;隨瀏覽器文字大小縮放。

    欄寬套用於背景文章;此處預覽字級與行距。手機正文自動配合螢幕。

    文件與本文目錄
    本主題文件

    不同程序的事件可以有先後關係,卻不能只憑各自寫下的日期時間判斷;分散式系統需要區分經過時間、實體時間與因果順序。 這些工具回答不同問題,沒有一種時間戳能自動提供所有保證。

    本文接續過載與時間預算,回到故障模型中的程序與訊息,為下一階段的一致性模型建立基礎。

    查證日期: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。它從三條規則建立:

    1. 同一程序內,先發生的事件先於後發生的事件。
    2. 一則訊息的送出,先於該訊息的接收。
    3. 關係具有遞移性:若 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:

    表格・3 欄 4 列
    事件更新時間戳
    A 建立匯出意圖A 從 0 加到 11
    A 送出請求A 加到 2,訊息帶 22
    B 收到請求B 設為 max(0, 2) + 13
    B 保存結果B 加到 44

    這滿足 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、裁剪規則與衝突偵測,不一定等同這裡完整記錄所有事件的向量時鐘。也不能看到兩個版本並行,就自動知道哪個業務結果正確:合併仍需要應用規則。

    先問時間戳要證明什麼

    表格・3 欄 5 列
    需求適合的概念起點不能直接推導的事
    本次請求已等多久語意符合需求的本地區間時鐘另一台主機事件的先後
    日誌對應哪個日期時間實體時鐘、同步與誤差資訊時間很接近就存在因果
    是否可能沿訊息影響另一事件happened-before 與邏輯時鐘Lamport 值較小就必然是原因
    哪些版本互為並行模型完整時的向量關係如何依業務要求解決衝突
    所有副本同意同一份命令順序需要額外協調協定只產生可排序 ID 就已達成共識

    現在回到「建立工作後查詢」:我們已能描述兩次操作的因果關係,但如果查詢被送到另一份資料副本,服務是否必須回傳剛建立的工作?這需要另外指定一致性契約,會在下一階段的「一致性模型與操作歷程」處理。

    相關文件