『看看论文』是一系列分析计算机和软件工程领域论文的文章，我们在这个系列的每一篇文章中都会阅读一篇来自 OSDI、SOSP 等顶会中的论文，这里不会事无巨细地介绍所有的细节，而是会筛选论文中的关键内容，如果你对相关的论文非常感兴趣，可以直接点击链接阅读原文。
本文要介绍的是 2020 年 OSDI 期刊中的论文 —— Sundial: Fault-tolerant Clock Synchronization for Datacenters[^1]，该论文实现的 Sundial 可以在数据中心提供高精度的、容错的对时机制。在数据中心发生故障时，它也能够保证不同服务器的绝对时间差小于 ~100ns，比行业内的其他的系统好一到两个数量级，这里的 ~100ns 也被称为时间不确定性上限（Time-uncertainty Bound）。
我们在这里会先介绍论文中提到的时间不确定性上限，在最后会介绍 Sundial 的系统架构，包含对时频率和错误恢复两方面的设计。
时间不确定性上限是个非常有趣的概念，假设我们有以下两台服务器，两台服务器本地的绝对时间包含一定的差异，其中服务器 A 在 X 时间从数据库中使用时间戳 T 读取数据，而服务器 B 在随后的 Y 时间使用时间戳 T-1 向数据库写入数据：
图 1 - 时间不确定性上限
从整体上看，因为不同服务器绝对时间上的微弱差异，后发生的时间反而使用了更早的时间戳，这就带来了潜在的问题。但是如果我们能够确定不同服务器之间绝对时间的最大差值，让服务器在读取数据时等待一段时间，就可以保证读写操作时序的正确性，这里的等待时间就是上面提到的时间不确定性上限，该值越小，系统的响应速度也就越快。
很多系统都对时间不确定性上限有要求，例如：分布式的事务数据库、一致性快照、网络遥测、单向延迟和分布式日志等，它的值越小，系统就能提供更好的性能、更快的响应速度和更强的一致性。
Sundial 使用软硬件结合的方式设计，其中包含如下图所示的三个主要组件，它会在硬件中完成同步时间信息、检测系统中错误等重要功能，软件负责计算同步生成树并故障时触发错误恢复机制：
图 2 - Sundial 框架
Sundial 论文从软件和硬件的维度介绍它的设计与实现原理，不过这里从时钟同步和错误恢复的功能维度介绍该系统的设计，
Sundial 中的时钟同步机制与 SDN 的数据平面与控制平面很相似，其中作为控制平面的控制器会在初始化时计算所有服务器的之间的时钟同步关系以及备选的同步路径，而作为数据面板的服务器会负责同步时间。如下所示，在节点正常工作时，根节点 0 的时间会同步给节点 4 和节点 6，而节点 1 会从节点 4 获取最新的时间：
图 3 - 同步生成树
因为服务器本地用于计时的石英晶体谐振器（Crystal Oscillator）会受数据中心温度、电压变化的影响会变得不再准确，不同时钟的差异会变得越来越大，所以硬件需要每隔 100µs 触发时间同步，同步消息会沿着控制器计算的生成树同步向下传递，一旦收到时间同步消息就会发送给其他节点。
虽然同步的频率异常频繁并且该数据包的优先级非常高，但是因为每个数据包的大小只有 100 字节，所以这只会占用网络整体带宽的 0.01%，最多只会为其他数据包增加 10ns 的网络延迟。
为了发现同步生成树中的节点错误，Sundial 需要软件和硬件的一同配合，其中硬件会使用超时时间检测上游发送的同步数据包，一旦发生超时或者检测到上游发出的时间不在预期的范围之内，硬件就会触发软件的错误恢复处理机制。
sundial-spanning-tree-and-fault-tolerance
图 4 - 错误恢复
正如我们在上一节中提到的，中心化的控制器会为非根节点提供用于错误恢复的备选路径，在计算主要同步路径和备选同步路径时需要遵循多个条件以提高备选路径的可用性，这里就不展开介绍了，熟悉图算法并且感兴趣的读者可以直接阅读论文了解相关内容。上面所有的备选路径都是由中心控制器计算并且存储在硬件本地的，这样在发生故障时可以迅速从本地错误中恢复。
精确的绝对时间虽然看起来距离我们很远，但是实际上有非常大的作用，Sundial 论文提出的技术能够为数据中心的服务器提供更准确的绝对时间，更准确的事件和更低的时间不确定性上限让 Spanner 数据库的提交等待延迟降低了 70% ~ 80%，中位数从 211µs 降低到了 49µs，99 分位数也降低了 ~550µs：
Baseline
With Sundial
中位数
211µs
49µs
99 分位数
784µs
238µs
表 1 - Spanner 提交等待延迟性能提升
大多数系统中并不需要用到如此复杂的系统同步时间，我们只需要使用 RFC5905 中的 NTP 协议就可以获得毫秒级精度的时间[^2]，虽然这与纳秒级别的时间有几个数量级的差距，但是在多数场景下都可以满足需求了。
[^1]: Yuliang Li, Gautam Kumar, Hema Hariharan, Hassan Wassel, Peter Hochschild, Dave Platt, Simon Sabato, Minlan Yu, Nandita Dukkipati, Prashant Chandra, Amin Vahdat. 2020. Sundial: Fault-tolerant Clock Synchronization for Datacenters. In Proceedings of the 13th USENIX conference on Operating Systems Design and Implementation (OSDI'20). USENIX Association, USA, 1171-1186.
[^2]: RFC 5905 - Network Time Protocol Version 4 - IETF Tools https://tools.ietf.org/html/rfc5905
