UTC 同步算法

简介

本页面定义并说明了 Timekeeper 用来在 UTC 架构中发挥核心作用的算法。

如果您正在使用时间系统，或者需要详细了解 Fuchsia 上 UTC 的内部机制，可能需要此信息。如果您只是想在 Fuchsia 上开发使用 UTC 的组件，请考虑改为阅读简短得多的 UTC 概览 和 UTC 行为页面。

时间源组件（如 HTTPSDate 时间源）也使用一系列特定于协议的算法来计算其时间样本；如需了解详情，请参阅每个时间源组件中的 README.md。

概览

Timekeeper 的操作分为以下 7 个不同的问题：

1. 是否可以接受时间样本？每次从时间源收到样本时，Timekeeper 就会决定是应该接受该样本（在此情况下，这可能会导致系统对 UTC 的理解发生变化）还是被拒绝（在这种情况下，会被舍弃）。
2. 应使用哪个时间源？Timekeeper 会维护主要 UTC 估算值，该估算值可能会受到主要时间源、回退时间源或门控时间源的时间样本的影响。如果安装了上述多个来源，Timekeeper 会决定在每个时间点应使用哪个来源。
3. 时间样本应如何改变估算的世界协调时间 (UTC)？Timekeeper 始终会维护最可能的 UTC 的估算值，以及此估算值的不确定性。每当时间源中的样本被接受时，Timekeeper 都会更新此估算值和不确定性。
4. 应使用什么策略来收敛报告的 UTC？每当估算的 UTC 因时间样本而发生变化时，Timekeeper 就会选择如何使用此新估算值来收敛针对客户端报告的 UTC。一种选择是立即单步调整报告的时间。另一种方法是在一段时间内以某种速率调整报告时间。
5. 一系列时间样本应如何改变估算频率？可以使用一系列时间样本来估算设备振荡器中的误差。更正这些频率误差可提高系统的准确度。
6. 如何限定时钟误差？UTC 时钟报告的时间不太可能与真实 UTC 完全一致。虽然确切错误未知，但 Timekeeper 可能会估算并发布该错误的边界。
7. 应更新哪些时钟？选择收敛策略后，必须通过对 UTC 时钟对象进行一次或多次更新来实现该策略。估算频率和错误边界更改也应更新 UTC 时钟对象。

在某些其他时间同步系统（例如 NTP）中，同一算法会用来回答其中的多个问题。这可能会使系统难以明确地推断特定功能的行为、避免功能之间的意外交互，或者难以根据新要求调整算法的组件。Timekeeper 会有意使用单独的算法来回答每个问题。这使得系统可以更轻松地开发、分析和调试，并且在支持各种不同产品时可以更灵活地更改或重新配置个别算法。

图 1 总结了这些算法之间的交互，其中黑色元素存在于所有配置中，灰色元素仅在存在可选的时间源角色时存在。

标记

以下部分有时使用等式来定义算法的某些部分。为了便于识别，这些等式采用 code font 格式并使用以下表示法：

• |x| x 的绝对值。
• sign(x) x 的符号。如果 x 为负数，则返回 -1；如果 x 为 0 或正数，则返回 +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 的时间样本被拒绝。由于时间源 bug，这会限制 Timekeeper 中的资源利用率上限。
2. 任何时间样本的 UTC 时间早于往返时间都会被拒绝。如果在往返时间之前接受样本，可能会导致 Timekeeper 将其 UTC 估算值早于往返时间。
3. 如果任何时间样本的单调时间离当前单调时间较远，则表示存在错误。如果单调时间是将来的时间或在过去 MIN_SAMPLE_INTERVAL 以上的时间样本，则会被拒绝。
4. 当 Timekeeper 配置了门控来源时，系统会从拒绝 |sample_utc - (gating_utc + estimated_frequency * (sample_monotonic - gating_monotonic))| > GATING_THRESHOLD 的非门控来源中任何时间采样。在此表达式中，gating_utc 和 gating_monotonic 是指来自门控来源最近接受的样本中的世界协调时间 (UTC) 和单调时间。此检查可确保所有其他来源与门控来源保持一致。

算法设计人员考虑了是否拒绝与当前估算的 UTC 不一致（无论是早于当前 UTC，还是明显晚于当前 UTC 时间）的时间样本，但认定这是不可取的。如果基于当前估算值拒绝新输入的任何系统，如果其估算值出现错误，并且存在两个不匹配的输入，则没有理由相信第一个输入比第二个更可靠。相较于无法正常工作的系统，最好能够从错误中恢复的系统，即使代价会大幅飙升。

应使用哪个时间源？

如 UTC 架构中所述，Timekeeper 可以配置为使用四个不同的时间源角色，但任何给定产品不太可能需要两个以上的角色。

主要来源、后备来源和门控来源（如果存在）可以分别用于驱动主要时间估算和外部可见时钟。这些来源按优先顺序降序列出；通常，与回退来源相比，主要时间来源更准确但可用性较低，而回退来源比门控来源更准确，但可用程度较低。监控源需要接受针对门控源（如果存在）的一致性检查，但在其他方面完全独立，从而驱动单独的时间估算和内部用户空间时钟（可与外部可见的时钟进行比较，以评估监控时间源的性能）。

时间源可能需要数分钟或数小时才能收敛于准确的解决方案，因此时间源始终会在 Timekeeper 初始化时启动，而不是仅在一些其他时间源故障后启动。

Timekeeper 会根据报告的状态和是否存在时间样本来选择时间源：

1. 如果主要时间源的最新状态为“运行状况良好”且最近的有效样本在 SOURCE_KEEPALIVE 内，则使用主要时间源；
2. 否则，如果其最新状态为“健康状况良好”且最近的有效样本在 SOURCE_KEEPALIVE 内，则使用回退时间源；
3. 否则，如果最新状态为“健康状况良好”，则使用门控时间源。

注意：自 2020 年第 4 季度起，系统尚不支持门控和回退源，因此尚未实现时间源选择算法。

算法设计人员考虑过是否在时间源选择算法中包含迟滞或故障计数，但得出结论，这不能增加足够的价值来弥补额外的复杂性。许多故障模式都纳入了时间源内部，因此完全时间源故障应该很少见。

时间样本应如何改变估算的世界协调时间 (UTC)？

从所选时间源接收的每个有效样本都应用于更新 Timekeeper 的 UTC 估算值。每个样本都存在一些错误，并且此错误的大小因样本而异。因此，UTC 估算值必须合并多个样本的信息，而不是盲目遵循最新的样本。

在其他领域中使用卡尔曼滤波器通常可以有效地解决这种状态估计问题。Timekeeper 定义了一个简单的二维卡尔曼过滤器，以保持 UTC 估算值（两种状态是 UTC 时间和频率），表示为每单调纳秒的 utc 纳秒。请注意，频率通过频率校正算法保持在滤波器外部；滤波器频率已从卡尔曼滤波器的测量模型中排除，且协方差为零。

卡尔曼滤波器中的参数如图 2 所示。

请注意，由于固定频率估计值和备用处理协方差矩阵的结果，只有状态协方差矩阵的左上角元素始终为非零值。此值不能超过 MIN_COVARIANCE 的下限，以防止过滤器在其内部状态上过度编入索引并拒绝新输入。

应使用什么策略来收敛报告的 UTC？

每次更新估算的 UTC 后，Timekeeper 都会决定是立即将用户空间时钟步调到新估算值，还是应用速率校正，将用户空间时钟逐步调整到新估算值。这些选项如图 3 所示。

步骤的时间变化可能会对时间客户端造成干扰，并可能导致计算出错，因此最好尽可能进行摆动。调整被限制为最大速率，因为以大体不切实际的速率进行摆动也会导致客户端出错；例如，以双实时方式进行摆动并非可取。每个滑动操作都受最大时长限制，以限制已知时钟不准确的时间；例如，在两周的时间内消除数小时的误差是不可取的。

对于小幅度的修正，只要修正需要，就会使用固定的小速率应用偏差。对于较大的修正，一旦倾斜时长达到某个最大值，系统便会使用实现修正所需的任意速率在固定时长内应用一个偏差。当频率超出某些最大 Timekeeper 时，就会使用时间步而非时间差。

总结：

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。

使用时间样本序列时，应如何更改估算频率？

由于制造缺陷，设备的振荡器可能会存在一些固有频率误差。通过估算振荡器频率来考虑此错误，可以提高 UTC 时钟的准确度，或降低必须进行时钟校正的频率。

该算法通过卡尔曼过滤器应用频率，即单调时钟上的 UTF 时钟每纳秒纳秒。请注意，这是振荡器的物理频率的反转（即单调时钟上的纳秒每纳秒实时）。快速运行的振荡器每纳秒会产生多个单调节拍，因此 UTC 时钟的每单调纳秒运行时间应小于 1 utc 纳秒以弥补。

振荡器误差根据规范限定为一个较小的值（通常是百万分之几十），因此即使无法获得频率估算值，上述 UTC 估算算法也稳定可靠；频率估算值是一种有益于性能的增强功能，但不是必要的。

频率估算值的优化时间要比 UTC 估算值更长。这样可以将这两种算法的时间常数分开，以避免潜在的交互，并确保频率算法不会在设备处于大量使用状态时跟踪瞬时错误，例如温度驱动的错误。这种高的时间常数意味着频率错误将在系统中保留很长时间，根据设计原则，Timekeeper 倾向于不提高频率估算，以免在频率估算中引入错误。

在满足以下所有条件的情况下，Timekeeper 会针对每个 FREQUENCY_ESTIMATION_WINDOW 周期估算周期频率：

1. 在该时间段内接受了至少 FREQUENCY_ESTIMATION_MIN_SAMPLES 个时间样本。这样可以避免在大部分时间段没有时间时为少量样本赋予过多的权重。
2. 该时间段内未发生时间上的变化。而步数变化则是该步骤前后出现重大错误的证据。这些句点不会用于避免纳入此错误。
3. 该时间段的任何部分都不在世界协调时间 (UTC) 时间可能出现闰秒的 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)。在所有情况下，最终估算频率都不得超出振荡器误差标准差的两倍以内，这样，没有事件组合会导致频率误差非常不准确，影响到卡尔曼滤波器的正确性，即

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 提供了一种简单的方法来混合多个时间段的数据，同时保持最低状态。

如何限定时钟误差？

对于 UTC 时钟，误差范围定义为 95% 置信区间的一半。换句话说，对于随机选择的紫红色设备上随机选择的时间，UTC 的真实值介于 reported_utc - error_bound 和 reported_utc + error_bound 之间的概率不低于 95%。尝试报告任何更高的置信度都意味着 Timekeeper 无法提供的确定程度，因为 Timekeeper 看不到某些时间故障模式。例如，本地振荡器可能会因缺陷而超出其指定公差范围，或者远程时间源可能会因 bug 而发送错误的时间。

UTC 时钟的错误由三部分组成：

1. 滚动过程中，报告的时钟时间和卡尔曼过滤器 UTC 估算值之间的已知差值。

   在任何时间点都可以轻松计算当前时钟值和世界协调时间 (UTC) 估算值，因此计算时差的影响微乎其微。误差范围包含完整的差值，不过，这种方法过于悲观。

2. 卡尔曼过滤器 UTC 估算值与远程时间源使用的时间标准之间存在未知的差。

   每次源都会提供错误标准差及其时间样本。这些错误的概率分布未知，并且可能因时间源而异。不过，根据中心极限定理，即使原始随机变量不是正态分布，独立随机变量的归一化总和也接近正态分布。由于卡尔曼滤波器会对输入样本求平均值（尽管不相等），因此当该过滤器累积大量样本时，预计卡尔曼滤波器的误差分布将接近正态分布，而标准偏差由协方差确定。该误差范围包含要解释该误差组成部分的错误所对应误差中协方差平方根的两倍项。对于早期的样本，这可能是乐观或悲观的，而过滤误差主要由从时间源收到的未知概率分布。

3. 远程时间源使用的时间标准与真实 UTC 之间的已知差值。

   有些来源（例如 Google）会故意在 24 小时内在闰秒前后的 24 小时内，在报告时间内引入最多 500 毫秒的错误来“掩盖”闰秒。此算法未记录该错误边界内的错误，其原因在于，记录模糊处理错误的复杂性和计算成本不值得为时间客户端带来好处。在 2000 年至 2020 年之间，闰秒出现了 5 次，导致此范围内所有天数的 0.07% 出现分布错误。这不太可能导致最终边界不符合 95% 置信度标准。

总而言之，错误边界的计算方式如下：error_bound = 2 * sqrt(covariance[0,0]) + |estimated_utc - clock_utc|

在接收第一次样本后，卡尔曼滤波器通过初始化进行初始化之前，错误边界会设置为 ZX_CLOCK_UNKNOWN_ERROR。这包括已根据实时时钟 (RTC) 初始化时钟但尚无网络时间的情况。

图 5 总结了误差范围计算：

应进行哪些时钟更新？

如之前的算法所述，选择收敛策略和估算振荡器频率会直接发生时钟速率和偏移量的变化。上一个算法定义的错误边界是一个不断变化的值，必须在时钟中定期发布。

当一个较大的偏差正在进行时，时钟不断接近卡尔曼滤波器估算值，因此误差范围不断减小。为了限制资源利用率，当需要进行其他时钟更新或上次报告的值中的错误数超过 ERROR_BOUND_UPDATE 时，Timekeeper 仅在调整期间更新 zx_clock_details_v1.error_bound。

当偏差没有进行中时，随着振荡器频率误差的积累，误差范围会持续而缓慢地增加。在调整之外，计时器会以适当的低频率更新 zx_clock_details_v1.error_bound，确保最后报告的值中的错误绝不会超过 ERROR_BOUND_UPDATE。

总的来说，Timekeeper 会对 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 的接近程度。这可用于确保可信度较低的来源与加密可验证的时间源大致一致。

单位	值	理由
纳秒	尚未实施	尚未实施

MIN_SAMPLE_INTERVAL

最小采样间隔限制了 Timekeeper 愿意接受来自时间源的新采样的最大速率，以限制 Timekeeper 资源利用率。请注意，这是相关的，因为在 fuchsia.time.external.PushSource 协议中，时间源决定了何时应生成时间样本。此值还可用于对时间样本的单调存在时间应用上限。

单位	值	理由
纳秒	60,000,000,000（即 1 分钟）	一般来说，我们希望时间样本因时间样本的收敛于准确的时间而降低频率，在校准良好的系统中时间样本相差几十分钟。每分钟接受一个样本的速度比收敛后所需的速率快得多，并大致反映了我们在初始化后不久就期望的最快速率。每个时间源每分钟处理一个时间样本仍然意味着，Timekeeper 会使用只占总资源的很小一部分资源，并且不会经常滥用日志。

SOURCE_KEEPALIVE

源 keepalive 决定了声明自身健康状况良好的来源需要生成样本才能保持选定状态的频率。如果时间源未能为此时间段生成任何时间样本，并且主要 > 回退 > 门控层次结构中较低的来源可用，则将改用其他来源。除非配置了回退或门控时间源，否则不使用此参数。

单位	值	理由
纳秒	3600,000,000,000（即 1 小时）	如果时间源持续无法提供时间，则应将自身标记为不健康。此参数应视为万不得已的情况下，可在发生时间源生命周期 bug 时启用恢复。我们选取的值要长于我们预计在运行状况良好时样本将采用最慢时间源的时间源（这样做时对时间源设置了最低速率要求），但要足够短，以便在检测到错误时系统时钟不会出现明显偏差。一个小时后，25ppm 振荡器可能会偏离 90 毫秒，因此我们将其用作合理的初始值。

OSCILLATOR_ERROR_SIGMA

系统振荡器频率误差的标准差，用于控制卡尔曼滤波器预测阶段不确定性增长。

单位	值	理由
无维度	0.000015（即 15 ppm）	最终，这应该可以按板进行配置，以反映硬件规格。目前，我们默认采用低端消费类硬件的典型值。

MIN_COVARIANCE

最小协方差限定了卡尔曼过滤器中 UTC 估算值的最小不确定性。这样，在从时间来源接收到不确定性极低的样本后，过滤器不会自行饮用洗浴水。

单位	值	理由
纳秒平方	1e12（即 1e-6 s^2）	该值表示一毫秒的校正后标准差。此值低于网络时间源所能实现的过滤条件，因此通常不会发挥作用。如果将来使用 GPS 等非常高的准确性时间源，则适当降低该值是合适的。

MAX_RATE_CORRECTION

最大速率校正功能限制了 Timekeeper 为消除 UTC 错误而有意调整时钟频率的最快速率。这是对用于补偿振荡器频率误差的任何时钟频率调整的补充。

单位	值	理由
无维度	0.0002（即 200ppm）	200ppm 代表比典型振荡器误差可能出现的错误率高出一个数量级。我们认为，大多数客户端应该能够正确适应这个大小，并且可轻松控制在内核规定的 1000ppm 限制内。当与 MAX_SLEW_DURATION 结合时，此值可确保通过调整可以消除 1 秒的误差。这种方法能够优雅地处理仅接收整数秒的时间源中的闰秒和潜在伪影。

最长 SLEW_DURATION

最大调整时长限定了 Timekeeper 应用时钟频率调整以响应单个时间样本的最长时长。连续时间样本可能会引入错误，并且每次都会触发偏差，因此每个样本的持续时间不会限制 Timekeeper 可能处于摇摆过程中的总时间。

单位	值	理由
纳秒	5400,000,000,000（即 1.5 小时）	时间样本之间的典型间隔为数十分钟。最长 90 分钟意味着在一次样本中收到一次更正可能会导致涉及接下来几个样本的偏差（每个样本都可能导致偏差修改），这感觉合适。90 分钟足以实现有意义的时间修正，但也要足够短，以至于与偏差或时间错误相关的任何用户可见的异常在数小时内都不会出现。当与 MAX_RATE_CORRECTION 结合使用时，此值可确保通过执行调整来消除 1 秒的误差。这种方法能够优雅地处理仅接收整数秒的时间源中的闰秒和潜在伪影。

PREFERRED_RATE_CORRECTION

这是对用于补偿振荡器频率误差的任何时钟频率调整的补充。

单位	值	理由
无维度	0.00002（即 20ppm）	20ppm 与典型振荡器可能观察到的误差一致，因此必须由所有时间的客户端处理；使用较低的速率几乎没有什么价值。20ppm 足够高，足以在几分钟内纠正典型的中度错误 - 10 ms 的误差需要 50 秒才能消除。

FREQUENCY_ESTIMATION_WINDOW

为更新频率估算值而收集一组时间样本的时间段。

单位	值	理由
纳秒	86,400,000,000,000（即 24 小时）	该值应为 24 小时的倍数，以避免白天周期内不同温度的偏差。周期越长，排除此时间段或无法完成该时间段的机会越多，因此频率估算流程的可靠性也会降低。24 小时提供了足够多的样本来求平均值，并且与 UTC 估算中的时间常数有足够距离。

FREQUENCY_ESTIMATION_MIN_SAMPLES

为符合频率估算条件，必须在频率估算时间范围内接收的最小样本数。

单位	值	理由
无维度	12	SOURCE_KEEPALIVE 和 FREQUENCY_ESTIMATION_WINDOW 将时间源在整个窗口中都正常的设备的预期时间样本数下限限制为 24。我们要求收到此数值的一半，也就是说，以最低合法采样率运行的设备必须在 24 小时内的一半时间内处于在线状态。此值可确保每个时间样本对最终平均值的贡献有限，因此可以容纳少量离群值。

FREQUENCY_ESTIMATION_SMOOTHING

在对频率进行指数加权移动平均值计算期间，应用于当前时间段的因数。

单位	值	理由
无维度	0.25	在计算 EWMA 时，0.25 会设置对历史记录的中等（有点任意）偏差，其中历史频率的权重是当前周期频率的三倍。这样可以降低任何异常频率周期的影响，并有助于保持稳定的长期平均值。

ERROR_BOUND_UPDATE

导致 UTC 时钟详情中的错误边界更新的值变化下限（即使不需要更改速率或偏移量）。此参数用于控制当发生显著偏差时时钟必须的更新频率。

单位	值	理由
纳秒	1 亿次（即 100 毫秒）	100 毫秒的错误边界更新加上 OSCILLATOR_ERROR_SIGMA 中的错误边界增长 30ppm，意味着在最大速率变化期间，每 10 分钟需要进行一次错误边界校正。这似乎是保持错误边界的较低负担。