世界標準時間同步演算法

簡介

本頁面定義並說明哪些演算法 計時員負責維護公司在 UTC 架構。

如果您是在時間系統上作業， 需要深入瞭解 Fuchsia 世界標準時間的內部結構。如果你是 希望在 Fuchsia 上開發使用世界標準時間的元件 更簡潔的世界標準時間總覽和世界標準時間行為 網頁。

時間來源元件，例如 HTTPSDate 時間來源也會使用 用於計算時間樣本的通訊協定專屬演算法；請參閱 各個時間來源元件中的 README.md，進一步瞭解詳細資訊。

總覽

「計時機」的操作分為下列七個不同問題：

1. 是否應接受時間取樣？每當系統從 時間來源 Timekeeper 會決定是否接受 (如果是的話) 可能會導致系統對世界標準時間有所改變，或者拒絕 (在 則會遭到捨棄)。
2. 應使用哪個時間來源？計時員 會維持主要世界標準時間預估值，該預估值可能會受到 主要、備用或管制時間來源如果這些超過一個 來源安裝的「Timekeeper」會判斷每個步驟要使用的來源 最終點子
3. 時間樣本對預估世界標準時間的變更方式為何？計時員 隨時取得可能性最高的 UTC 估計值，以及 預估結果的不確定度。計時員同時更新這項預估值和 不確定度。
4. 在配合世界標準時間，該採取哪種策略？每當 根據時間樣本所估算出的世界標準時間變更，Timekeeper 會選擇如何 ，以這個新的預估值整合向用戶端回報的世界標準時間。選項之一 立即逐步回報回報的時間另一個方式是清理 或維持中段時間
5. 一連串的樣本對預估頻率有什麼影響？A 罩杯 數列時間樣本可用於估計裝置裝置的錯誤 Scillator 值修正這些頻率錯誤可提高 以及系統
6. 如何限制時鐘錯誤？世界標準時間時鐘報告的時間為 不太可能與真實的 UTC 完全吻合。雖然確切錯誤 時間守則，可能會預估和發布錯誤相關邊界
7. 應該更新哪些時鐘？一旦採用收斂策略 選取這個變數，就必須對世界標準時間進行一或多項更新 物件。預估頻率和錯誤繫結變更也應一併更新。 世界標準時間時鐘物件

在其他某些時間同步處理系統 (例如 NTP) 中，將採用相同的演算法 來回答超過一個問題所以 可以清楚說明特定功能的行為，避免 功能間無意間互動的情況，或是調整 演算法以因應新的需求計時人員刻意使用 以不同演算法回答每個問題這樣可以產生 更易於開發、分析及偵錯 變更或重新設定個別演算法，以便支援更多 不同的產品

圖 1 摘要了這些演算法之間的互動， 所有設定都有黑色元素，且只有灰色元素 顯示選用的時間來源角色。

符號

以下章節有時會使用方程式來定義 演算法。這些方程式採用 code font 格式，以便 識別和使用以下標記法：

• |x|x 的絕對值。
• sign(x)x 的符號。如果 x 為負，則傳回 -1；如果 x 為零，則傳回 +1 正面影響。
• sqrt(x) x 的平方根。
• sum(x) 某些資料集內所有點的屬性 x 總和。
• clamp(x,y,z) 值 x 限制為不小於 y 且不大於 z 例如：clamp(x, y, z) = min(z, max(y, x))

UPPER_CASE_SNAKE_CASE 中的文字是指可設定的參數，用來控制 演算法的行為這些參數和預設值 一文，詳情請參閱「可設定的參數」一文。

詳細資料

是否應該接受時間樣本？

時間樣本接受簡單的有效性測試後，才能獲準：

1. 在前一個週期後，任何時間樣本都不到 MIN_SAMPLE_INTERVAL 來自相同來源的接受時間樣本遭到拒絕。這樣即可限制 因時間來源錯誤而造成「時光管理」資源使用率上限的情形。
2. 如果時間樣本的世界標準時間早於回溯時間，則系統會拒絕該取樣時間。正在接受 在倒停時間之前先取樣，這樣時間記錄器可能會針對該樣本進行預估 的結束時間之前，以世界標準時間為準。
3. 在目前單調時間之間有單調時間取樣的時間樣本，就是 表示發生錯誤單調時間未來的時間樣本 一律遭拒。
4. 如果計時工具設有管制來源，則 |sample_utc - (gating_utc + estimated_frequency * (sample_monotonic - gating_monotonic))| > GATING_THRESHOLD 遭到拒絕的非管制來源。於 gating_utc 和 gating_monotonic 運算式指的是 UTC， 識別來源中最近接受的樣本中的單調時間。 這項檢查可確保所有其他來源都符合管制規範 來源。

演算法設計人員考慮是否要拒絕那些 與目前的預估世界標準時間不一致 (無論是在目前世界標準時間之前或 但結果並非預期。任何系統 如果依據目前估算拒絕新的輸入內容，則無法復原 失敗的原因是 許多資料格式都沒有理由相信第一個檔案是否可靠。 即使發生大幅跳動成本，系統也能從錯誤中復原 最好能解決問題

應使用哪個時間來源？

正如世界標準時間架構所述，計時工具可以 並採用四種不同的時間來源角色 任何一項產品都需要超過兩個

主要來源、備用來源和管制來源 (如果有的話) 都可能各自 用於計算主要時間預估值和外部可見時鐘。 這些來源依偏好順序由高至低列出。通常是主要的 時間來源較準確，但比備用來源較不可用 因此，相較於約定來源，資料準確性會更準確，但可用的資料也較少。A 罩杯 監控來源需要對管制來源進行一致性檢查 (如果有 存在) 但完全獨立運作，因此需要安排個別時間 以及內部使用者空間時鐘可以與 外部可見時鐘，以評估監控時間來源的效能。

時間來源可能需要幾分鐘或數小時，才能找到準確的解決方案 因此，時間來源一律會在初始化時啟動，而非 除非其他時間來源都發生錯誤

計時員會根據回報的狀態和是否存在 時間樣本：

1. 如果最近一次狀態的健康狀態良好，並使用主要時間來源，系統就會使用主要時間來源 最新有效的樣本位於 SOURCE_KEEPALIVE；
2. 否則，如果最新的狀態是備用時間來源，系統就會使用備用時間來源 健康狀態良好，且最新有效的樣本是在 SOURCE_KEEPALIVE 內；
3. 否則，系統會使用管制時間來源 (如果最近的狀態是 健康狀態良好

注意：自 2020 年第 4 季起，系統目前不支援限制和備用來源， 因此尚未導入時間來源選取演算法。

演算法設計人員會考慮是否要納入同性戀者 但這不會導致 足以補償複雜程度。多種故障模式 但僅限於時間來源，因此完整的時間來源錯誤 應該是罕見事件。

時間樣本對預估世界標準時間的變更方式為何？

所選時間來源收到的所有有效樣本都應用於 更新 Timekeeper 的世界標準時間預估值。每個範例都包含一些錯誤 且這個錯誤的大小會因樣本而異世界標準時間估計值必須 因此，您可以合併多個樣本的資訊 的最新樣本。

這種狀態預估問題通常使用 Kalman 解決 篩選器計時器定義了一個簡單的二維卡爾曼 來保留世界標準時間估計值，其中兩個州別為世界標準時間，並 頻率，以單調奈秒為單位的 utc 奈秒表示。請注意， 透過頻率校正作業在過濾器外保持頻率 演算法；篩選器頻率不在卡爾曼內 篩選器的評估模型，且共變數為零。

圖 2 是 Kalman 篩選器中的參數。

請注意，為達成固定頻率預估值和備用程序的結果 共變數矩陣，只有狀態共變數矩陣的左上方元素是 都不是零這個值不可超過 MIN_COVARIANCE 以下 避免篩選器在內部狀態上過度索引，並拒絕新的 輸入內容

請問該使用哪種策略，串連出回報的世界標準時間？

每次更新到估計的世界標準時間 (UTC) 後，計時器會決定是否更新 立即將使用者空間時鐘計入新的預估值，或套用費率 ，以逐漸將使用者空間時鐘轉換成新的估計值。這些 圖 3 呈現這些選項。

逐步變更可能會對時間用戶端造成乾擾，並可能導致錯誤 因此在計算時優先採用揮桿為 受限於速率上限 速率也可能會引發用戶端錯誤例如以雙實實境秀移動 來回應使用者的需求每項拆分作業設有數量上限 持續時間，限制時鐘已知不準確的時間；的 例如，在兩週內，成功去除數個小時的錯誤 來回應問題

針對小幅修正， 才能完成修正的必要步驟如要進行更大範圍修正， 達到一定上限時，系統就會使用 以達到修正作業所需的速率。如果費率超過 像是部分計時機的計時方案，可採用時間步數而非

摘要 :

1. 如果是 |estimated_utc - clock_utc| > MAX_RATE_CORRECTION * MAX_SLEW_DURATION， 變更時鐘。
2. 否則，如果是 |estimated_utc - clock_utc| > PREFERRED_RATE_CORRECTION * MAX_SLEW_DURATION， 套用 (estimated_utc - clock_utc)/MAX_SLEW_DURATION 的房價修正 長達 MAX_SLEW_DURATION；
3. 否則，請將費率更正值 時間：sign(estimated_utc - clock_utc) * PREFERRED_RATE_CORRECTION (共 |estimated_utc - clock_utc|/PREFERRED_RATE_CORRECTION 個)。

時間序列樣本該如何改變預估頻率？

裝置振動器可能會發生暫時性頻率錯誤，這是因為 製造瑕疵。預估振盪器頻率 這項錯誤可能會提高世界標準時間時鐘的準確度，或降低 一定要修正哪些時鐘

演算法與卡爾曼套用的頻率類似 濾波器，單調時鐘上每奈秒單位為奈秒的時間。注意事項 是電梯體能頻率的反函式 (即 每奈秒即時的單調時鐘)。正在執行的振盪器 快速產生的每奈秒即時產生多個單調刻度 因此，世界標準時間每個單調的 utc 奈秒單位應小於一秒 奈秒才能彌補。

Oscillator 錯誤受到規格限制為某個小值 (通常是 因此上述 UTC 估計演算法保持穩定 可靠度，即使無法取得頻率預估資料也可靠頻率預估值 這項強化功能雖然有助於提高成效，但並非必要。

頻率預估值經過調整的時間比世界標準時間多很多 這會大幅提高這兩種演算法的時間常數 避免潛在的互動，並確保頻率演算法不會追蹤 暫時性錯誤，例如裝置處於低於狀態時因溫度引起的錯誤 會大量耗用資源這種時間固定的常數表示頻率錯誤會持續留在 長期使用這套系統基於設計理念，計時員傾向於 頻率預估值並未導致 頻率預估值。

計時器會估算每個 FREQUENCY_ESTIMATION_WINDOW 的經期頻率 滿足下列所有條件的期間：

1. 在下列期間至少接受 FREQUENCY_ESTIMATION_MIN_SAMPLES 個樣本 。這麼做可以避免對少量的 樣本。
2. 這段時間內未發生任何步驟變化。步數變化就是證據 就會發生一次重大錯誤這些經期不是 來避免整合這個錯誤
3. 這段期間內，所有經期均未落在世界標準時間發生跳躍時的 12 小時內 事件可能已發生。某些時間來源會衝破重尖的氣味 而且 24 小時內就會發生嚴重頻率錯誤 而不是步驟變更這些時段不會用於避免納入計算 卻發生這個頻率錯誤這會影響一年最多 2 24 小時 會減少系統追蹤是否有排定下一個閏秒的時間。

週期頻率的計算方式為最小正方形的漸層 (單調和 utc) 元組上的迴歸計算。 如圖 4 所示。

我們使用下列方程式進行實作：

period_frequency = {sum(utc * monotonic) - sum(utc)*sum(monotonic)/n}
                   / {sum(monotonic^2) - sum(monotonic)^2/n}

其中 n 是指定期間內可接受的樣本數量。請注意， MIN_SAMPLE_INTERVAL 為此值設定上限。整體展示頻率 估計值是指數加權移動平均值 (EWMA) 訂閱週期的頻率。在所有情況下，最終預估頻率為 僅限於振盪器錯誤標準差的雙倍 萬一沒有組合任何事件可能會導致頻率錯誤 可能會變得不準確 Kalman 濾鏡。即

estimated_frequency = clamp(
    period_frequency * FREQUENCY_ESTIMATION_SMOOTHING +
       previous_estimated_frequency * (1 - FREQUENCY_ESTIMATION_SMOOTHING),
    1 - 2 * OSCILLATOR_ERROR_SIGMA,
    1 + 2 * OSCILLATOR_ERROR_SIGMA)

EWMA 可輕鬆混合多個時段的資料，同時保留 狀態。

如何限制時鐘錯誤？

世界標準時間時鐘的錯誤界限定義為 95% 信賴水準的一半 間隔。也就是隨機選取的時間 Fuchsia 裝置中的實際 UTC 值有 95% 以上的機率為 介於 reported_utc - error_bound 至 reported_utc + error_bound 之間。 如果嘗試回報信賴水準較高，表示 因為有些時間故障模式 不會讓「計時者」看到。例如，局部調節器 因為瑕疵或遠端時間來源，而無法達到指定的容忍度 傳送錯誤的時間。

世界標準時間中的錯誤是由三個元件組成：

1. 已知時鐘時間與卡爾曼濾波器的已知差異 執行中分部作業時的世界標準時間預估值。

   無論目前時間值還是 UTC 時間， 因此在計算差值時會十分困難。錯誤界限 完整差異，但過度悲劇。

2. 卡爾曼篩選條件 (世界標準時間) 與時間之間存在不明差異 是遠端時間來源採用的標準

   每個時間來源都會提供錯誤標準差和時間樣本。 未知這些錯誤的機率分佈情形 相隔。然而，根據中央極限定理， 獨立隨機變數的正規化總和接近正常值 即使原始隨機變數通常不正常 發行。Kalman 篩選器會平均計算輸入樣本 則在正常情況下，Kalman 濾鏡才會出現錯誤分佈情形 等到篩選器累積大量 樣本，其標準差是由共變數決定。這個 錯誤界限包含共乘數的平方根 這項錯誤元件所繫結的錯誤。這可能是 提出樂觀或悲觀的早期樣本時，篩選錯誤功能 主要是 來源。

3. 已知遠端時間來源採用的時間標準之間的差異 和 true (世界標準時間)

   某些來源 (例如 Google) 和「smear」刻意促成的閏秒 導入 24 小時內回報時間 (最多 500 毫秒) 的錯誤 就在閏秒之前。這個演算法不會在 否則模型的複雜性和運算成本 記錄惡意錯誤對時間的客戶來說不划算。Leap 秒發生在 2000 到 2020 年之間出現五次變化，導致 這個範圍內全天的 0.07%。這不太可能是最終定案 可繫結至失敗 95% 的可信度條件。

總結來說，錯誤邊界的計算方式如下： error_bound = 2 * sqrt(covariance[0,0]) + |estimated_utc - clock_utc|

直到初次收到 Kalman 篩選器經初始化調整為止 樣本，錯誤界限設為 ZX_CLOCK_UNKNOWN_ERROR。這包括 用於從即時時鐘 (RTC) 初始化時鐘的情況，但 目前尚無法提供網路時間。

圖 5 匯總了錯誤限制的計算：

應更新哪些時鐘？

系統會直接從選取 並預估加速器頻率，如 先前的演算法前一個演算法定義的錯誤界限 是不斷變更的值，必須定期在 時鐘。

出現大爆裂縫時，時鐘會不斷接近 因為 Kalman 濾波器的濾網會不斷降低錯誤邊界 限制資源使用率計時更新 發生其他時鐘的情況時，zx_clock_details_v1.error_bound 必須提供更新，或是上次回報值的錯誤超過 ERROR_BOUND_UPDATE。

在進度沒有進展時，錯誤邊界會持續且緩慢 隨著振盪頻率錯誤累積而增加。在困境之外 計時器更新 zx_clock_details_v1.error_bound 很少方便 頻率，確認上次回報值中的錯誤絕對不會超過 ERROR_BOUND_UPDATE。

總而言之，Timekeeper 會依下列方式更新世界標準時間時鐘：

• 對時鐘的步驟變更一律視為一次時鐘更新。
• 時鐘時間通常實作為兩次時鐘更新：變更速率 開始滑行時 1/estimated_frequency + rate_correction 房價在延遲 slew_duration後變更為 1/estimated_frequency。 若在第二次時鐘變更前接受後續更新，則 則捨棄第二個時鐘的變更。
• 如果在沒有進行時鐘器的情況下計算新的頻率預估值， 時鐘速率已變更為 1/estimated_frequency (如果時鐘時間出現偏差) 進度，切換鈕結束時的時鐘會恢復到新的頻率 更新)。
• 如果是 |last_set_error_bound - error_bound| > ERROR_BOUND_UPDATE，代表錯誤 上下限已經更新。

可設定的參數

前幾節介紹了幾個參數，可用於 設定演算法的行為下表提供更多資訊 並列出每個參數的初始值

GATING_THRESHOLD

限制門檻會限制來自非管制來源的樣本的間隔時間 設為管制來源所指示的世界標準時間 (UTC)。這是為了減少 可信任的來源廣泛一致，而且經過加密編譯後 來源。

MIN_SAMPLE_INTERVAL

取樣間隔下限會限制計時器 願意接受某個時間來源的新樣本，以限制 計時工具資源使用率。請注意，這與 而是 fuchsia.time.external.PushSource 通訊協定的時間來源 會決定何時產生樣本這個值也會用於 對單調時間樣本套用上限。

SOURCE_KEEPALIVE

來源保持運作會決定來源宣告自身權限的頻率 產生樣本時必須產生樣本，才能保持選取狀態。如果指定時間 來源無法產生這段期間的任何時間樣本，而來源值低於 主要 >備用 >但其他來源會 除非是備用或管制時間，否則系統不會使用這個參數 已設定來源。

OSCILLATOR_ERROR_SIGMA

系統調節器頻率錯誤的標準差，用於控制 看看在卡爾曼濾波器預測階段期間，不確定性通常會增加多少

MIN_COVARIANCE

最小共變數值會規定 UTC 預估值的最小不確定度， Kalman 濾鏡。幫助過濾器在收到水份後不要喝水 從時間來源取得 非常低的不確定性樣本

MAX_RATE_CORRECTION

速率校正上限會界定出計時員 謹慎調整時鐘頻率，以縮小世界標準時間的錯誤。這個 並未採用任何用於補償 振動器頻率錯誤。

MAX_SLEW_DURATION

「最大」持續時間上限會界定計時器將為 調整時鐘頻率。連續時間 樣本可能會產生錯誤 每個取樣的時間長度並未限制 Timekeeper 總和 可能處於緩解階段

PREFERRED_RATE_CORRECTION

計時單位將時鐘頻率調整為縮小一點 這項數據並不包括任何用於補償的時鐘頻率調整 就會看到振盪器頻率錯誤。

FREQUENCY_ESTIMATION_WINDOW

收集一組時間樣本並更新 頻率預估值。

FREQUENCY_ESTIMATION_MIN_SAMPLES

系統估算頻率時必須收到的樣本數量下限 才符合頻率估算資格

FREQUENCY_ESTIMATION_SMOOTHING

依指數加權期間套用至目前期間的係數 移動平均頻率計算。

ERROR_BOUND_UPDATE

導致錯誤界限 (世界標準時間時鐘詳細資料) 的最小變化值 ，即使不需要變更費率或偏移。這個參數 控制出現重大偵察，需要更新時鐘的頻率 進度。