Lib.rs

› 日期和时间
#拜占庭 #系统时钟 #网络 #时间 #byztime

bin+lib byztimed

拜占庭容错时间同步

作者：Daniel Fox Franke

3 个版本 (稳定)

2.0.1 2021 年 3 月 10 日
2.0.0 2021 年 2 月 25 日

#299 在 日期和时间

Apache-2.0 许可协议

205KB
4K SLoC

Byztime

Byztime 是一种 拜占庭容错 协议，用于在没有依赖任何外部时间权威的情况下同步一组对等体之间的时间。Byztime 保留的时间只是一个每秒递增一次的计数器，使得所有节点对其当前值的协议非常一致。Byztime 时间戳没有定义良好的纪元。如果所有节点在首次初始化时系统时钟都设置正确，那么 Byztime 将最初与 POSIX 时间相匹配，但最终会与其偏离，因为 1. 没有外部来源保持其同步，2. Byztime 的时间尺度缺乏闰秒。

Byztime 的算法专注于将其 最坏情况 错误（任何两个正确节点对当前时间估计的绝对距离）尽可能小。它通过仅使用每个对等体的单个最高质量时间样本来降低 典型情况 错误，而不是结合许多样本以平滑网络抖动来实现这一点。在最坏的情况下，两个正确节点时钟之间的差异将以 4δ + 4ερ 的速度收敛，其中 δ 是两个最远距离对等体之间的单向网络延迟，ε 是正确节点硬件时钟的（无量纲）漂移率，ρ 是轮询间隔。如果所有节点都诚实地行为，这个界限会改善到 2δ + 2ερ，并且将在协议的单轮中达到而不是收敛。

Byztimed完全独立于NTP运行，一个坏的NTP时间源不会干扰Byztime。但这有一个小警告：在守护进程关闭前，它会记录Byztime时间和系统时间之间的当前偏移量，并在重启后使用这个偏移量重新初始化其估计。这种情况只有在许多节点同时重启且网络失去多数时才特别重要。在这种情况下发生的事情取决于NTP和启动时的顺序。如果Byztime在NTP启动之前启动，并在NTP关闭之后关闭，那么Byztime时间尺度的连续性将和重启节点的RTC和CMOS电池一样好，但不会更好。另一方面，如果允许NTP在Byztime启动之前稳定系统时钟，那么Byztime时间尺度的连续性将和其NTP源一样好——这可能比你的RTC好得多，但如果NTP源有故障，可能会非常糟糕。再次强调，这只有在Byztime失去多数时才会成为一个问题，意味着网络中有1/3或更多的节点同时重启。

Byztime也目前依赖于系统时间来判断X.509证书是否已过期。一旦Roughtime成熟一些，我们可能会考虑将Roughtime客户端集成到byztimed中进行证书验证。

构建

Byztimed像任何标准的Rust crate一样构建。安装byztimed的最简单方法是使用crates.io通过cargo获取。

cargo install byztimed

如果你更喜欢检出和构建此存储库，请注意，byztimed包含作为子模块的libbyztime，因此请使用git clone --recurse-submodules进行克隆，或者如果你已经使用不带--recurse-submodules选项进行克隆，请运行git submodule update --init --recursive。

Byztimed针对Rust的稳定渠道进行了测试，但比当前稳定版显著更旧的编译器可能也能工作。已知不工作的最新版本是1.38（因为我们依赖于async/await，它在1.39中稳定）。

Byztimed目前仅在Linux上运行，并且仅在AMD64上进行了良好的测试。其他CPU架构应该也能工作；如果你遇到任何问题，请提交一个错误报告。我们希望最终支持更多的操作系统，但这将是一场艰难的战斗，因为Byztimed依赖于目前只有Linux提供的计时设施。提高可移植性的努力可能需要向其他操作系统内核贡献一些新的功能。

用法

使用byztimed <路径-到-配置-文件>运行byztimed。有关配置文件语法，请参阅CONFIG.md。

libbyztime是从byztimed消费时间的C客户端库。请参阅其byztime.h文件以获取API文档。此存储库中的byztime crate提供了对libbyztime的惯用Rust绑定，其文档可以在docs.rs上阅读。

协议概述

尽管它本质上是一个对等协议，Byztime使用客户端-服务器通信模式，每个节点对其他节点既充当客户端也充当服务器。还支持仅客户端的操作模式，其中节点与共识同步但不在其中投票。

Byztime使用网络安全时间 (NTS) 进行加密链路保护。每个客户端到每个服务器的通信从客户端发起TLS握手开始，然后使用NTS-KE协商共享密钥并获得NTS Cookie。NTS-KE完成后，TLS连接关闭，协议的其余部分通过UDP运行。NTS提供消息级别的认证加密。它为客户端提供重放保护，但不为服务器提供。服务器从不根据来自客户端的消息更新任何状态，因此处理重放无害。在本文档的剩余部分，我们将假设认证加密的抽象，并从我们的描述中省略与NTS相关的机制。

假设每个节点都配备了一个本地时钟，它计算从某个任意时刻（例如系统上次启动时）以来经过的时间。一个节点的本地时钟与另一个节点没有先验的已知关系。相反，这种关系是通过执行协议来发现的。节点寻求同步到的共享时间称为全局时钟。节点维护其全局偏移的估计，即全局时钟与本地时钟之间的差异。本地时钟永远不会收到任何调整；只有全局偏移会。

协议通过每个节点定期向其每个对等节点发送查询，并且对等节点发送响应，其中包含其本地时钟快照及其当前的全局偏移估计。每个查询/响应回合称为测量。

协议使用以下全局参数

  1. N：参与共识的节点数量。

  2. f：可以容忍的故障节点数量。f = floor((N-1)/3)。

  3. drift：一个无维数，给出一个正确节点本地时钟可能多快或多慢的上限。例如，如果drift是50e-6，则时钟每秒可能漂移高达50µs。

每个节点保留以下状态

  1. 其本地时钟的era。这是一个随机生成的标识符，如果本地时钟丢失状态（例如，在重启后），则更改。

  2. global_offset：节点对全局时钟与其本地时钟之间偏移的估计：local_clock() + global_offset == global clock estimate。

  3. error：上述全局时钟估计与其真实值之间的最大绝对差值。

  4. last_update：在哪个本地时钟时间global_offset和error被最后更新。

并且对于其每个对等节点

  1. peer.era：上次通信时对等节点的时钟时代。

  2. peer.local_offset：节点对其本地时钟与对等方本地时钟之间偏移的估计：local_clock() + peer.local_offset == 对等方本地时钟的估计。

  3. peer.global_offset：对等方对其本地时钟与全局时钟之间偏移的估计，这是在上次通信时。

  4. peer.rtt：当前“最佳”测量中对等方时钟的往返时间。这个测量值是peer.local_offset所基于的。

  5. peer.origin_time：导致当前最佳测量的查询发送时的本地时钟时间。

  6. peer.inflight_id：与当前等待响应的查询（如果有）关联的随机唯一标识符。

  7. peer.inflight_origin_time：当前在途查询（如果有）发送时的本地时钟时间。

与 NTS 相关的一些附加状态——cookie 和共享密钥的缓存——基本上与 NTP 相同，因此在本解释中我们将忽略它。

第一次运行时，节点初始化 global_offset，以便全局时钟与其实时时钟相匹配。它们定期检查两个时钟之间的偏移，并将此偏移持久化到磁盘。此持久化值用于在重新启动后恢复一个大致值以重新初始化 global_offset，但这种方式的偏移恢复误差界限被认为是无限的。

每个配置的轮询间隔期间，客户端向每个对等方发送一个包含仅随机生成的唯一标识符的查询消息。发送者更新 peer.inflight_id 和 peer.inflight_origin_time 以反映数据包的内容和发送时间。如果有其他查询正在进行，则假定旧的查询已被网络丢弃，新的 inflight_id 和 inflight_origin_time 值覆盖旧的值。

服务器立即对收到的任何查询做出响应。响应包含

  1. response_id：查询的唯一标识符的副本。

  2. response_local：服务器的本地时钟快照。

  3. response_era：服务器的 era。

  4. response_global_offset：服务器的 global_offset。

当客户端收到响应时，它按照以下方式处理

  1. 将 now 设置为接收响应时的本地时钟快照。

  2. 验证 peer.inflight_id 非空且与 response_id 匹配。如果不匹配，则丢弃响应。否则，将 peer.inflight_id 设置为空并继续。

  3. 将 peer.global_offset 设置为 response_global_offset。

  4. 计算 rtt 为 now - peer.inflight_origin_time。

  5. 如果这是迄今为止从该对等方收到的第一个响应，或者如果 peer.era 与响应中包含的纪元不匹配，则跳到步骤 8。

  6. 计算从该对等方获取的当前最佳测量值的以下“下限越优”质量指标：Q = peer.rtt/2 + 2 * drift * (now - peer.origin_time)。这代表了在考虑网络不对称和时钟漂移的情况下，估计该节点本地时钟与对等方本地时钟之间偏移量的最坏情况误差。由于两个时钟可能各自朝相反方向漂移，所以漂移乘以2。

  7. 计算新测量的这个质量指标：Q' = rtt/2 + 2 * drift * (now - peer.inflight_origin_time)。如果 Q' > Q，则旧测量值优于新测量值，因此保留它并返回，不进行进一步处理。

  8. 将 peer.rtt 设置为 rtt，peer.origin_time 设置为 peer.inflight_origin_time，将 peer.era 设置为 response_era。

  9. 将 peer.local_offset 设置为 response_clock + rtt/2 - now。

现在使用从对等方新更新的时钟值，重新计算 global_offset 和 error

  1. 对于每个对等方 p，计算一个估计值 est = p.local_offset + p.global_offset 和误差 err = p.rtt/2 + 2 * drift * (now - p.origin_time)，得到一个区间 (est - err, est + err)。创建所有结果的最小值和最大值的列表。

  2. 如果我们自己也是共识的参与者，将 global_offset 插入最小值列表和最大值列表中。

  3. 对两个列表进行排序。丢弃最低的 f 个最小值和最高的 f 个最大值。让 min' 等于剩余的最小值，max' 等于剩余的最大值。让 global_offset' = (max' + min')/2。让 error' = (max' - min')/2。这种平均方法——丢弃最高和最低的 f 个值，取剩余范围的中点——源于 "A New Fault-Tolerant Algorithm for Clock Synchronization" (Welch and Lynch 1988)，对于实现拜占庭容错至关重要。

  4. 确定新的全局偏移和误差是否与旧值一致。让 age = now - last_update。让 min = global_offset - error，并让 max = global_offset + error。让 drift_limit = 2 * age * drift。现在检查 min' > min - drift_limit 和 max' < max + drift_limit。如果这个检查失败，则不进行进一步处理。（这一步对于确保同步不是必需的，但如果没有它，中间人攻击者可能会通过延迟查询消息但不延迟响应消息或反之，导致整个网络的时间过快或过慢地前进。）

  5. 将 last_update 设置为 now，global_offset 设置为 global_offset'，将 error 设置为 error'。

这完成了我们对该协议的描述。消费 Byztime 查询时间的应用程序查询 global_offset、error 和 last_update 的当前值。全局时间等于 local_time + global_offset，误差范围为 ±(error + 2*drift*(local_time - last_update))。

全局时间的估计不是频率稳定的：它们在每次更新时都会不连续地跳跃，并且可以后退。应用程序如何处理这一点取决于应用程序本身。《libbyztime》包括对连续调用 get_global_time() 的结果进行夹具支持，以使它们彼此一致。

注意事项

Akamai 自 2020 年初以来一直在关键业务应用程序中使用 Byztime，它对我们来说一直非常稳定。然而，直到两个具体问题得到解决，该软件应被视为测试版。

  1. 我们可能会对 Byztime 的网络协议进行一些不兼容的修改。Byztime 目前使用实验性使用范围内的 NTS-KE 码点；我们计划从 IANA 获取并使用永久分配。我们还可能会将 Byztime 的时间包格式从基于 Protobufs 的格式更改为定制的固定字段格式，以便使解析更加可预测，并使确保请求大小与响应大小相匹配变得更加容易。我们计划通过一次性的旗日版本发布，将所有这些更改同时进行，并在此之后承诺向后兼容。

  2. 由于它们依赖于 Akamai 内部基础设施才能运行，因此 Byztime 的一些统计和健康报告功能已被从本次开源版本中删除。我们计划围绕开放标准重新设计和实现此功能。

依赖项

~20–33MB
~646K SLoC