世界標準時間同步演算法

說明

本頁定義並說明 Timekeeper 用來達成世界標準時間架構中核心角色的演算法。

如果您正在使用時間系統，或需要在 Fuchsia 瞭解 UTC 的內部詳細資訊，此資訊可能會感興趣。如果您只是想要開發使用世界標準時間的 Fuchsia 元件，請考慮改為閱讀更短、更簡單的 UTC 總覽和世界標準時間行為頁面。

HTTPSDate 時間來源等時間來源元件也使用特定通訊協定專屬的演算法計算時間樣本；詳情請參閱各時間來源元件的 README.md。

總覽

計時工具會分成七個不同的問題回答：

1. 是否應該接受時間取樣？每次從時間來源 Timekeeper 收到樣本時，都會決定是否應接受 (在這種情況下，可能會造成系統對 UTC 的瞭解) 或遭到拒絕 (在這種情況下，系統會捨棄樣本)。
2. 應使用哪個時間來源？時間維護者負責維護主要 UTC 預估值，且會受到主要、備用或限制時間來源的時間樣本影響。當安裝多個來源時，Timekeeper 會決定在每個時間點應使用哪個來源。
3. 時間取樣應如何變更預估 UTC？時間維護人員會隨時維護可能性最高的 UTC 預估值，以及此預估值的不確定性。每次從來源來源接受樣本時，時間維護人員都會更新這個預估值和不確定性。
4. 應採取哪種策略，用來整合系統記錄的世界標準時間？每次因時間樣本而變更 (世界標準時間) 時，時間守門員會選擇如何把回報的 UTC 匯進使用這個新預估值的用戶端。其中一種方法是立即加速回報時間。另一種做法是，以某些速率滑過回報時間一段時間。
5. 序列樣本應如何變更預估頻率？序列樣本可能會用於預估裝置調節器中的錯誤。修正這些頻率錯誤可提高系統的準確度。
6. 時鐘錯誤可如何界定？世界標準時間時鐘回報的時間不太可能與真實世界標準時間相符。雖然確切的錯誤不明，但時間 keeper 可能會估算並發布與錯誤相關的邊界。
7. 應更新哪些時鐘？選取收斂策略後，必須對世界標準時間時鐘物件做出一或多項更新，才能實作這項策略。預估頻率和錯誤邊界的變更也應該更新世界標準時間時鐘物件。

在其他某些時間同步處理系統 (例如 NTP) 中，系統會採用相同的演算法回答以上的問題。這可能使您難以明確瞭解特定功能的行為、避免功能之間意外互動，或根據新要求調整演算法元件。計時器會刻意使用 個別演算法來回答每個問題這會導致系統的開發、分析和偵錯作業更為簡單，且在支援多種不同產品時，可提供更多變更或重新設定個別演算法的彈性。

圖 1 匯總了這些演算法之間的互動情形，所有設定中都含有黑色元素，而灰色元素只有在選用的時間來源角色存在時，才會顯示。

符號

下列各節有時會使用方程式來定義演算法的某些部分。這些方程式的格式為 code font，以便識別，並使用下列標記法：

• |x|x 的絕對值。
• sign(x)x 的正負號。如果 x 為負值，則傳回 -1；如果為零或正數，則傳回 +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。這會限制因時間來源錯誤而導致 Timekeeper 中的資源使用率上限。
2. 如果任何時間樣本 (世界標準時間) 早於回溯時間，則遭到拒絕。若在回溯時間之前接受樣本，可能會導致時間維護工具將 UTC 的預估值設置在回溯時間之前。
3. 如果任何時間樣本的單調時間與目前單調時間相距很遠，就表示有錯誤。單調時間在未來或過去 MIN_SAMPLE_INTERVAL 以上的時間樣本將會遭拒。
4. 如果時間守門器設為管制來源，則來自非受限來源的任何時間樣本，且 |sample_utc - (gating_utc + estimated_frequency * (sample_monotonic - gating_monotonic))| > GATING_THRESHOLD 遭到拒絕。這個運算式中的 gating_utc 和 gating_monotonic 是指最近接受的受限來源樣本中的世界標準時間和單調時間。這項檢查可確保所有其他來源都與閘道來源保持一致。

演算法設計人員會考慮拒絕與目前預估 UTC 不一致的時間樣本 (可能是在目前的世界標準時間之前，或在目前的 UTC 後大幅)，但結論是不適當的結果。如果系統根據目前預估值拒絕新輸入，就容易造成永久失敗，而且如果系統估算出現錯誤，且沒有理由認為第一個結果比第二個值更可靠，就很容易成為永久失敗。能夠從錯誤中復原的系統則傾向於無法負荷大幅變動的系統。

應使用哪個時間來源？

如世界標準時間 (UTC) 架構所述，計時器可以設定為使用四個不同的時間來源角色，但不太可能任何產品都要求超過兩個角色。

主要來源、備用來源和閘道來源 (如有) 都可用來驅動主要時間預估時間和外部可見時鐘。這些來源的偏好順序為遞減；一般來說，主要時間來源會比備用來源更為準確，但可用性較低。相較之下，備用來源的準確度會更高，但可用性卻不如限制來源。監控來源必須對閘道進行一致性檢查 (如果有的話)，但在其他方面則完全獨立，所以可以與外部可見的時鐘進行比較，據此評估監控來源的效能。

時間來源可能需要好幾分鐘或數小時才能趨於準確的解決方案，因此當時光機初始化時，一律會啟動時間來源，而不是只有在其他時間來源發生錯誤後才會啟動。

計時器會根據回報的狀態和是否存在時間樣本來選取時間來源：

1. 如果其最新狀態的健康狀態良好，且最新的有效樣本位於 SOURCE_KEEPALIVE，系統就會使用主要時間來源；
2. 否則，如果最近期的狀態為健康狀態良好，且最新的有效樣本位於 SOURCE_KEEPALIVE，系統就會使用備用時間來源。
3. 否則，如果閘道最近一次的健康狀態良好，系統就會使用限制時間來源。

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

演算法設計人員會考慮是否要在時間來源選取演算法中納入假設或失敗計數，但得出這個結果並不會增加足夠的價值來彌補額外的複雜度。許多失敗模式都設有時間來源的內部功能，因此完整時間來源失敗應該是罕見事件。

時間樣本應如何變更預估 UTC？

所選時間來源收到的每個有效樣本都應用於更新時間維護人員的世界標準時間預估結果。每個樣本都包含一些錯誤，且這項錯誤的大小會因樣本而異。世界標準時間預估值必須結合多個樣本的資訊，而不是盲目遵循最近的樣本。

在其他網域中使用 Kalman 篩選器，通常可以有效解決這種狀態估算問題。Timekeeper 定義了簡單的雙維度 Kalman 篩選器，藉此維持世界標準時間的預估值，其中兩個狀態是世界標準時間的時間與頻率，以每單位奈秒 utc 奈秒表示。請注意，頻率由「頻率校正演算法」外部保存；篩選頻率已從 Kalman 篩選器的評估模型中排除，且共變異數為零。

Kalman 篩選器中的參數如圖 2 所示。

請注意，由於固定頻率預估值和備用程序共變數矩陣，只有狀態共變數矩陣的左上方元素絕不會是零。這個值限制在 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，請在 MAX_SLEW_DURATION 期間內套用 (estimated_utc - clock_utc)/MAX_SLEW_DURATION 的頻率校正；
3. 否則，請在 |estimated_utc - clock_utc|/PREFERRED_RATE_CORRECTION 期間套用 sign(estimated_utc - clock_utc) * PREFERRED_RATE_CORRECTION 的頻率校正。

序列樣本應如何變更預估頻率？

裝置改進器可能會因製造瑕疵而發生一些固有頻率錯誤。預估調節器頻率來考量這個錯誤，可以提高世界標準時間時鐘的準確度，或降低必須進行時鐘調整的頻率。

演算法會與 Kalman 篩選器套用的頻率搭配運作，以單奈秒在一奈秒的 utc 時鐘上為奈秒。請注意，這個運算器的實體頻率 (即即時每奈秒的奈秒奈秒) 相反。運作速度快的調節器會在每奈秒即時產生超過一個單聲道滴答，因此 UTC 時鐘應在每單奈秒中午 12 點以下才能彌補。

Oscillator 錯誤受規範限制為些微數值 (通常為幾百萬分之一)，因此，即使無法使用頻率預估值，上述 UTC 預估演算法仍保持穩定且可靠。頻率預估值能夠強化效能，但並非必要。

頻率預估值的修正時間範圍比世界標準時間預估長上許多。這會讓兩個演算法的時間常數遠大，避免發生潛在的互動，並確保頻率演算法不會在裝置使用率偏低時追蹤暫時性錯誤，例如溫度驅動錯誤。這種時間很長的常數表示頻率錯誤會長期保留在系統中一段時間。從設計上來說，Timekeeper 不會改善頻率估算結果，因為這麼做會導致頻率預估值發生錯誤。

時間維護人員可以為每個 FREQUENCY_ESTIMATION_WINDOW 期間估算一段期間的頻率，且此期間符合下列所有條件：

1. 這段期間內接受至少 FREQUENCY_ESTIMATION_MIN_SAMPLES 個時間樣本。如果大部分的時間都無法使用，這可避免在少量樣本中加入過多權重。
2. 這段期間內沒有發生任何步數變更。步驟變更代表在步驟前後發生重大錯誤。這些期間並未用於避免納入這項錯誤。
3. 所有時段都不必在世界標準時間時間的 12 小時內發生，也就是可能有跳轉秒的時間點。某些時間來源會以瞬間滴水漏水，在 24 小時內 (而非步數變更) 造成重大頻率錯誤。這些期間沒有用於避免納入這項頻率錯誤。這會影響一年最多兩個 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) 計算，在所有情況下，最終預估頻率限制都限制在滲透誤差標準差為兩倍範圍內，因此沒有事件組合可能會導致頻率錯誤幾乎不準確，進而影響 Kaalman 濾鏡的正確性。即

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 裝置上，隨機選取的時間有 95% 的機率是 UTC 的真實值介於 reported_utc - error_bound 和 reported_utc + error_bound 之間。如果嘗試回報任何較高層級的信賴，將暗示時間維護人員無法提供資訊的不確定程度，因為某些時間故障模式不會造成時光平移。舉例來說，由於瑕疵導致本機調控器在指定的容忍度以外執行，或者遠端時間來源可能會因錯誤而傳送不正確的時間。

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

1. 目前回報的時鐘時間與 Kalman 篩選器世界標準時間 (UTC) 預估值的已知差異，目前仍在規劃運動。

   無論何時，目前時鐘值和世界標準時間 (UTC) 預估值都能輕鬆計算，因此計算差異十分簡單。錯誤範圍包括完整差異，但這是過於悲劇。

2. Kalman 篩選條件世界標準時間 (UTC) 與遠端時間來源使用的時間標準之間的不明差異。

   每個來源都會提供與時間樣本的錯誤標準差。這些錯誤的機率分佈不明，而且可能不同時間來源的差異。不過，根據中央限制定理，獨立隨機變數的正規化總和將接近常態分佈，即使原始隨機變數通常不會分佈。由於 Kalman 篩選器會平均計算輸入樣本 (儘管不相等)，因此當篩選器累積大量樣本時，Kalman 篩選器的錯誤分佈情形應會呈現常態分佈，其標準差是以共變數決定。此錯誤繫結包含在錯誤繫結錯誤邊界中共變數的兩倍平方根的字詞。對早期樣本而言，這可能是最佳式或悲觀性，而篩選錯誤則以來源從來源接收的未知機率分佈主要。

3. 遠端時間來源使用的時間標準與真實世界標準時間 (UTC) 之間的已知差異。

   有些來源 (例如 Google) 會在 24 小時內，刻意在回報時間內產生最多 500 毫秒的錯誤。這個演算法不會將這個錯誤記錄在錯誤邊界內，因此導致記錄分散錯誤的複雜性和計算成本無法為時間用戶端帶來好處。2000 年到 2020 年之間發生跳躍秒數的情況，導致此範圍內所有天數的 0.07% 發生隱形錯誤。不太可能這會導致最終繫結失敗 95% 的可信度條件。

簡單來說，錯誤範圍的計算方式如下： error_bound = 2 * sqrt(covariance[0,0]) + |estimated_utc - clock_utc|

在收到第一次樣本後，將 Kalman 篩選器初始化之前，錯誤範圍會設為 ZX_CLOCK_UNKNOWN_ERROR。這包括已從即時時鐘 (RTC) 初始化時鐘，但尚未取得網路時間的情況。

錯誤繫結計算請參考圖 5：

應更新哪些時鐘？

如果時鐘的速率和偏移量有所變更，可以直接選取收斂策略，並預估調節器頻率 (如先前的演算法所述)。先前演算法定義的錯誤界限是持續變動的值，必須定期在時鐘上發布。

當大筆進行中，雖然有大量的縫隙，時時時鐘都會持續接近 Kalman 濾網的預估範圍，因此錯誤界限會持續下降。為了限制資源使用率計時器，只有在需要其他時鐘更新，或上次回報值的錯誤超過 ERROR_BOUND_UPDATE 時，僅在暫停期間更新 zx_clock_details_v1.error_bound。

雖然檸檬未進行中，但錯誤邊界會不斷且逐漸增加，隨著 OS 頻率錯誤累積，緩解問題外，維護人員會以某個簡便的頻率更新 zx_clock_details_v1.error_bound，確保最近回報的值的錯誤不會超過 ERROR_BOUND_UPDATE。

總而言之，計時器會更新 UTC 時鐘，如下所示：

• 對時鐘進行的步驟變更一律視為單一時鐘更新實作。
• 時鐘轉折通常會實作為兩個時鐘更新：在開始滑動後，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)。這可用於確保較不信任的來源，與經過加密編譯且可驗證的時間來源廣泛保持一致。

單位	值	Rationale
奈秒	尚未執行	尚未執行

最短間歇訓練

最小取樣間隔會限制時間維護工具接受某個時間來源的新樣本，以限制計時器資源使用率。請注意，這很重要，因為在 fuchsia.time.external.PushSource 通訊協定中，這是決定產生時間樣本的時間來源。此值也用於對單調時間的存在時間設下上限。

單位	值	Rationale
奈秒	60,000,000,000 (即 1 分鐘)	一般而言，我們預期時間來源會在準確的時間合併時，降低樣本的頻率，而在經過妥善校正的系統中，時間樣本相隔了數十分鐘。每分鐘接受樣本的速度會比收斂後所需的速率快上許多，並大致反映了初始化後不久的預期速度。如果每個時間來源每分鐘處理一次一次樣本，仍代表時間維護人員只使用極一小部分的資源，而非經常在記錄中濫發垃圾內容。

來源：KEEPALIVE

來源保持運作可決定來源宣告自身健康狀態，需要產生範例的頻率，才能保持已選取。如果這個時間來源無法產生該時段的任何時間樣本，且來源位於主要 > 備用 > 限制階層中較低的來源，系統就會改用其他來源。除非已設定備用或限制時間來源，否則系統不會使用這個參數。

單位	值	Rationale
奈秒	3600,000,000,000 (例如 1 小時)	因為某些時間來源無法持續提供時間，所以應將自身狀態標示為不良。此參數應做為最後手段，在發生時間來源生命週期錯誤時啟用復原。我們挑選的數值應該比我們預期最慢的時間來源在健康 (並且因此必須根據時間來源設下最低頻率要求) 的值，但只要夠短，系統時鐘就不會因為偵測到錯誤的時間而有明顯差異。一小時的 25 ppm 振盪器可能分成 90 毫秒，因此我們會將其視為合理的初始值。

OSCILLATOR_ERROR_SIGMA

系統調節器頻率誤差的標準差，用於控制 Kalman 濾波器預測階段的不確定性變化。

單位	值	Rationale
無維度	0.000015 (例如 15 ppm)	最終應根據硬體規格，為每個主機板進行這項設定。目前我們採用的是低消費性硬體的一般值。

最低 COVARIANCE

最小共變數限制是 Kaalman 篩選條件中 UTC 預估值的最小不確定度。如此一來，篩選器在收到來自時間來源的不確定度較低之後，就不會自行喝水。

單位	值	Rationale
奈秒平方	1e12 (例如 1e-6 s^2)	此值代表經過修正後的標準差為 1 毫秒。這個值低於篩選器在網路時間來源中達成的目標，因此通常不會發生。如果日後使用 GPS 等非常高的時間點來源，建議您稍微降低這個值。

最高費率

頻率校正上限會限制最快速率，讓時間維護人員為了消去世界標準時間的錯誤而謹慎調整時鐘頻率。此次會連同任何時鐘頻率調整，用來彌補監管器頻率錯誤。

單位	值	Rationale
無維度	0.0002 (例如 200ppm)	200ppm 代表比一般運勢錯誤預期出現的錯誤率高低的一倍。我們認為大部分的客戶應該都能正確因應這樣的規模，而且在核心規定的 1000 ppm 限制範圍內十分舒適。這個值與 MAX_SLEW_DURATION 合併使用時，可確保以滾動方式移除 1 秒的錯誤。想要優雅地處理僅接收整數秒數的時間來源的可能構件，也是較理想的做法。

MAX_SLEW_DURATION

收合持續時間上限會限制最長持續時間，計時器將根據單一時間樣本套用時鐘頻率調整。連續時間樣本可能會產生每個錯誤觸發中斷的錯誤，因此，這個每取樣時間不會限制計時工具可能處於滑動切斷過程的總時間。

單位	值	Rationale
奈秒	5400,000,000,000 (例如 1.5 小時)	樣本之間的一般間隔為十分鐘。如果以 90 分鐘為限，表示在一個樣本中收到修正作業的片段可能會跨越下一小部分的樣本 (這些樣本也可能影響通道的修改)，情況合適。90 分鐘足以達成有效時間修正，但時間太短，導致使用者無法看見的異常點/時間錯誤在多個小時內出現。將這個值與 MAX_RATE_CORRECTION 合併使用時，可確保以滾動方式移除 1 秒的錯誤。想要優雅地處理僅接收整數秒數的時間來源的可能構件，也是較理想的做法。

偏好費率

當時間維護人員調整時鐘頻率來消除小型錯誤時，該速率會隨之調整，這是除了任何時鐘頻率調整外，用來彌補營運頻率錯誤。

單位	值	Rationale
無維度	0.00002 (例如下午 20 點)	下午 20 點與一般波動器可能觀察到的錯誤一致，因此必須適用於所有的客戶。採用較低速率的做法微乎其微。20ppm 足以在短時間內修正一般中等錯誤，如果 10 毫秒，則移除 50 秒的時間即可移除錯誤。

頻率

系統收集一組樣本以更新頻率預估值的時間範圍。

單位	值	Rationale
奈秒	86,400,000,000,000 (即 24 小時)	該值應為 24 小時的倍數，以免偏心週期中不同溫度的偏誤。時間範圍越長，就越有機會排除或未能完成特定時間範圍，導致頻率估算流程的可靠性也會因此下降。24 小時可提供足夠大量的樣本數，且足以與世界標準時間預估時間常數的偏遠。

頻率

必須在頻率預估期間內收到的樣本數下限，才符合預估頻率的資格。

單位	值	Rationale
無維度	12	在 SOURCE_KEEPALIVE 和 FREQUENCY_ESTIMATION_WINDOW 中，如果裝置的整個時間範圍內，時間來源均為良好狀態，樣本數量下限會設為 24。根據我們的規定，若要接收到這個數值的一半，意味著如果裝置運作的法定取樣率最高，且 24 小時期間內的一半，則必須連上網路。這個值可確保每個樣本對最終平均值的貢獻有限，因此可能符合少數離群值。

頻率

在指數加權移動平均頻率的期間，套用至目前週期的因素。

單位	值	Rationale
無維度	0.25	0.25 表示在 EWMA 計算期間，對歷史記錄的偏誤 (以及略為任意) 偏誤，歷來頻率的權重會高於目前經期頻率的三倍。這麼做可降低任何異常頻率期間造成的影響，進而提倡穩定的長期平均值。

ERROR_BOUND_更新

即使值沒有變更費率或偏移，這個值的最小變化情形，也會更新世界標準時間時鐘詳細資料中的錯誤範圍。這個參數可控制重大暫停執行時，時鐘的更新頻率。

單位	值	Rationale
奈秒	100,000,000 (即 100 毫秒)	錯誤繫結更新時間介於 100 毫秒，加上 OSCILLATOR_ERROR_SIGMA 的錯誤上限成長幅度為 30 下午，代表在發生速率上限時，每 10 分鐘需要一次修正錯誤繫結。這似乎是維持錯誤界限的低負擔。