UTC 同步算法

简介

本页面定义了并解释了 计时器的作用是履行在 UTC 架构。

如果您正在使用时间系统或 需要详细了解 Fuchsia 上世界协调时间 (UTC) 的内部机制。如果您只是 希望在 Fuchsia 上开发使用世界协调时间 (UTC) 的组件，请考虑阅读大部分 UTC 概览和 UTC 行为更加简短易行 页面。

时间源组件，例如 HTTPSDate time source 还使用 特定于协议的算法来计算其时间样本；请参阅 README.md。

概览

Timekeeper 的操作分为回答 7 个不同的问题：

1. 是否应该接受时间样本？每次从 时间源 Timekeeper 会决定是否接受（在这种情况下） 可能会导致系统对世界协调时间 (UTC) 的理解发生变化）或拒绝（在 系统会将其舍弃）。
2. 应使用哪个时间源？计时工具 会保留一个主要的 UTC 估算值，该估算值可能会受到 主要、后备时间或关口时间源。如果其中不止一个 安装了来源时，Timekeeper 会决定每次应该使用哪个来源 。
3. 时间样本应如何更改估计世界协调时间 (UTC)？计时工具 始终维持对最可能 UTC 的估计，以及 不确定性。计时器会同时更新此估算值和 不确定性。
4. 应采用什么策略来收敛报告的世界协调时间 (UTC)？每次 估计 UTC 的变化（由于时间样本造成的），Timekeeper 会选择 使用此新估算值收敛向客户报告的世界协调时间 (UTC)。一种方法是 立即单步报告时间。另一种方法是 在一定时间内以某个速率运行
5. 时间样本序列应如何改变估算频率？答 时序样本可用于估算设备 振荡器。修正这些频率误差可提高 系统。
6. 如何限制时钟误差？UTC 时钟报告的时间是 不太可能与真实世界协调时间 (UTC) 完全匹配。虽然实际的错误并非 Timekeeper 可能会估算并发布该误差的边界。
7. 应进行哪些时钟更新？将收敛策略 必须通过对世界协调时间 (UTC) 进行一次或多次更新来实现 时钟对象。估算的频率和错误边界更改也应更新 UTC 时钟对象。

在其他一些时间同步系统（如 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 的所有时间 来自同一来源的已接受时间样本将被拒绝。这会限制 由于时间源 bug 而导致 Timekeeper 中的资源利用率上限。
2. 如果世界协调时间 (UTC) 早于退避时间，则任何时间样本都会被拒绝。正在接受 在回避时间之前取样可能会导致 Timekeeper 进行估算 世界协调时间 (UTC) 早于后退时间。
3. 单调时间远离当前单调时间的任何时间样本 表示出现错误。单调时间是未来的时间样本 或超过 MIN_SAMPLE_INTERVAL 的日期将被拒绝。
4. 当 Timekeeper 配置有门控来源时， 非门控来源，其中 |sample_utc - (gating_utc + estimated_frequency * (sample_monotonic - gating_monotonic))| > GATING_THRESHOLD 会被拒绝。在 此表达式 gate_utc 和 gating_monotonic 指的是世界协调时间 (UTC) 和 门控来源中最近接受的样本中的单调时间。 这项检查可确保所有其他来源都与控制机制保持一致 来源。

算法设计人员考虑是否拒绝 与当前的预计世界协调时间 (UTC) 不一致（早于当前 UTC 或 明显晚于当前世界协调时间 (UTC)），但我们认为这并不可取。任何系统 拒绝基于当前估算值的新输入 很容易永久性 如果估算结果不正确，并且当两个参数的 没有理由相信第一种输入比第二种更可靠。 即使错误代价大幅提升，也能从错误中恢复的系统 比不能做的更好。

应使用哪个时间源？

如 UTC 架构中所述，Timekeeper 可能 配置为使用四种不同的时间源角色， 任何指定商品都需要两个以上的属性。

主要来源、后备来源和控制来源（如果存在）可以分别 用于驱动主时间和外部可见时钟。 这些来源按优先顺序降序排列；通常是 时间来源会比后备来源更准确，但可用率更低 这反过来又比门控来源更准确，但可用性更低。答 需要对控制来源（如果 ），但在其他方面完全独立，各个时间之间 估算结果以及内部用户空间时钟，该时钟可与 外部可见时钟，用于评估监视时间源的性能。

时间源可能需要数分钟或数小时才能收敛到准确的解决方案 因此，在初始化 Timekeeper 时始终会启动时间源， 另一个时间源出现故障后触发。

计时器会根据报告的状态和是否存在 时间样本：

1. 如果主要时间源的最新状态良好且其 最近的有效样本位于 SOURCE_KEEPALIVE 内；
2. 否则，如果后备时间源的最新状态为 健康状况良好，且其最近的有效样本在 SOURCE_KEEPALIVE 内；
3. 否则，如果门控时间来源的最新状态为 健康状况。

注意：自 2020 年第 4 季度起，暂不支持设定门槛和后备来源， 因此尚未实现时间源选择算法。

算法设计人员考虑了要包括迟滞还是失败 但最终得出结论，这并不会增加 以便弥补这种额外复杂性。多种故障模式 位于时间源内部，因此发生时间源故障时 应该很罕见

时间样本应如何更改估计世界协调时间 (UTC)？

从选定时间源接收的每个有效样本都应用于 更新 Timekeeper 估算的世界协调时间 (UTC)。每个样本都存在一些错误 并且此错误的大小因样本而异。UTC 估算值必须 因此，您可以合并多个样本的信息， 。

这种状态估计问题通常可以使用卡尔曼 过滤器。计时器定义了一个简单的二维卡尔曼 过滤器以保持 UTC 估算值，其中两种状态是 UTC 时间， 频率，以每单调纳秒为单位，以 utc 纳秒为单位。请注意， 通过频率校正功能在滤波器外部维持频率 算法；过滤频率从卡尔曼范围中排除， 并且协方差为零。

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

请注意，由于固定频率估算和备用进程， 则只有状态协方差矩阵的左上角元素 始终为非零值。此值不得超过 MIN_COVARIANCE 到 以防止过滤器的内部状态过度索引，从而拒绝新的 输入。

应采用什么策略来收敛报告的世界协调时间 (UTC)？

每次更新估计 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) 时钟的准确性，或降低 需要进行哪些时钟校正。

算法按照卡尔曼应用频率的方式运作 过滤器，对于单调时钟，utc 时钟上的每纳秒为纳秒。注意事项 这是振荡器物理频率的倒数（即 实时的每纳秒单调时钟）。正在运行的振荡器 会在每纳秒内实时产生不止一个单调滴答声， 因此，UTC 时钟的运行速度应该小于每个单调 1 utc 纳秒 以纳秒进行补偿。

振荡器误差由规范限制在一个较小的值（通常 几千万分之几），因此上述 UTC 估算算法稳定且 即使无法估算频次，也仍然可靠；频次估算值 是一项对性能有益但不是必要的增强功能。

频率估算值的优化时间段要比世界协调时间 (UTC) 长得多 估算。这就使得两个算法的时间常数相距甚远， 避免潜在的互动，并确保频次算法不会跟踪 暂时性错误，例如设备处于 大量使用。如此长的时间常数意味着频率误差将保留在 长期以来。从设计理念来看，Timekeeper 注重 频次估算值未增加，导致在 频次估算值。

计时器会估算每个 FREQUENCY_ESTIMATION_WINDOW 的周期频率 同时满足以下所有条件的期限：

1. 期间至少接受了 FREQUENCY_ESTIMATION_MIN_SAMPLES 个时间样本 。这样可避免对少量网页 在大部分时间段都无法提供时间的情况下进行抽样。
2. 这段时间内时间未发生任何步数变化。阶梯变化即为证据 出现严重错误。这些经期 来避免合并此错误。
3. 该时间段的任何一个时间段均不在闰秒的世界协调时间 (UTC) 的 12 小时内 可能发生了第二秒。有些时间来源让人沉迷于闰秒弥补 它们在 24 小时内带来明显的频率误差 而不是步骤变化。这些时段旨在避免 出现这种频率错误。这样，每年最多只会影响两个 24 小时的时间段 则会减少。

周期频率的计算公式为线性最小二乘法的梯度 针对 如图 4 所示。

这是使用以下公式实现的：

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

其中 n 是该时间段内接受的样本数。请注意， MIN_SAMPLE_INTERVAL 用于为此值设置上限。总体频次 估算值的计算公式为： 周期频率。在所有情况下，最终估算频次都是 限制在振荡器误差标准差的两倍内 这样，事件组合就不会导致出现频率误差 严重不准确，以至于可能影响到 卡尔曼滤波器。即

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) 的真实值有 ≥ 95% 的概率 介于 reported_utc - error_bound 和 reported_utc + error_bound 之间。 如果尝试报告置信度较高，则意味着 由于有些时间故障模式 计时程序将看不到这些星球。例如，本地振荡器可能正在运行 由于缺陷或远程时间源导致的超出其指定容限 由于错误而发送错误的时间。

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

1. 报告的时钟时间和卡尔曼滤波器之间的已知差异 大扫除期间的世界协调时间 (UTC) 估算值。

   您可以在任意时间轻松计算出当前时钟值和世界协调时间 (UTC) 估算值 因此计算差值微乎其微。错误界限 包括完全的差别，但这过于悲观。

2. 卡尔曼滤波 UTC 估算值与时间之间的未知差 与远程时间源所使用的标准时间相关联

   每个时间源都会为其时间样本提供误差标准差。 这些错误的概率分布未知，可能不同 不同时间源之间的数据。不过，根据中心极限定理， 自变量随机变量的归一化和接近正态 即使原始随机变量并非正常值， 分发。由于卡尔曼滤波器对输入样本求平均值（尽管 不均等），则卡尔曼滤波的误差分布应该在 接近正态分布，因为当过滤器积累大量数据， 其标准偏差由协方差决定。这个 错误边界包含协方差平方根的两倍的术语， 与此错误组件有关的错误。这可能是 对于早期样本使用乐观或悲观，而 主要由一段时间内收到的未知概率分布 来源。

3. 远程时间源使用的时间标准之间的已知差异 和真实的世界协调时间 (UTC)。

   某些来源（如 Google）,“smear”闰秒 在 24 小时内，引发最长 500 毫秒的误差 大约一闰秒。此算法不会将此错误记录在 能够遵循错误限制，因此，推理的复杂性和计算开销 记录弥补错误对于时间客户端来说并无价值。Leap 在 2000 年至 2020 年期间出现了五次，导致 此范围内所有日期的 0.07%。这不太可能导致 一定无法通过 95% 置信度标准。

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

直到在首次收到事件时， 则错误边界设置为 ZX_CLOCK_UNKNOWN_ERROR。这包括 其中时钟已经根据实时时钟 (RTC) 进行了初始化，但 还无法提供网络时间。

图 5 总结了错误边界的计算方法：

应该进行哪些时钟更新？

选择 收敛策略并估算振荡器频率，如 算法。上一个算法定义的错误边界 是一个不断变化的值，必须在 时钟。

在大批量进程期间，时钟始终接近 因此，错误边界不断减小。 限制资源利用率，仅通过 Timekeeper 进行更新 在切换时zx_clock_details_v1.error_bound 需要更新，或者上次报告的值中的错误超过 ERROR_BOUND_UPDATE。

虽然无法进行回转，但错误边界会持续且缓慢 会随着振荡器频率误差的累积而增加。在一轮变速的演变中 计时员在方便的时候更新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，则表示错误 bound。

可配置参数

前面的部分介绍了一些可用于 用于配置算法的行为。下表提供了 并证明输入初始值 。

GATING_THRESHOLD

门控阈值用于限制来自非门控来源的关闭时间抽样的时间间隔上限 与门控来源指示的世界协调时间 (UTC) 保持一致。这可用于确保减少 可信来源具有可加密验证的时间大致一致 来源。

MIN_SAMPLE_INTERVAL

最小采样间隔限制了计时器的最大频率 愿意接受来自时间源的新样本，以限制 Timekeeper 资源利用率。请注意，由于在 fuchsia.time.external.PushSource 协议是 确定何时应生成时间样本。该值还可用于 对时间样本的单调存在时间应用上限。

SOURCE_KEEPALIVE

源 keepalive 决定将自己 需要生成样本才能保持被选中状态。如果某个时间 来源无法为此时间段生成任何时间样本， 主要 >后备广告 >门控层次结构可用，其他来源将 。除非后备时间或门控时间，否则不会使用此参数 来源已配置

OSCILLATOR_ERROR_SIGMA

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

MIN_COVARIANCE

最小协方差限制了 UTC 估算值的最小不确定性 卡尔曼滤波器。这有助于过滤器在接收完设备后不会直接饮用自己的洗澡水 来自时间源的不确定性极低的样本。

MAX_RATE_CORRECTION

最大速率更正限制了计时程序执行的最大速率 刻意调整时钟频率以消除 UTC 错误。这个 不包括任何时钟频率调整，用于补偿 振荡器频率误差。

MAX_SLEW_DURATION

最大摆动时长限制了计时工具应用 时钟频率调整，以响应单个时间样本。连续时间 样本可能会引入错误，每个样本都会触发错综 每个样本的时长不会限制 Timekeeper 可能的总时间， 正处于摇摆过程中

PREFERRED_RATE_CORRECTION

计时器会调整时钟频率以减少幅度 这加上用于补偿偏差的任何时钟频率调整， 表示振荡器频率误差。

FREQUENCY_ESTIMATION_WINDOW

收集一组时间样本以更新 频次估算值。

FREQUENCY_ESTIMATION_MIN_SAMPLES

频率估算必须接收的样本数下限 满足使用频次估算值的条件。

FREQUENCY_ESTIMATION_SMOOTHING

指数加权期间应用于当前时间段的系数 频率的移动平均值计算。

ERROR_BOUND_UPDATE

导致 UTC 时钟详细信息中的错误边界 即使不需要更改费率或偏移量时也会进行更新。此参数 控制在出现大幅度变动时必须更新时钟的频率 进度。