2016年1月12日
第13卷，第9期

时间是幻觉

午餐时间更是如此。

—福特·普里弗克特对亚瑟·邓特在道格拉斯·亚当斯的《银河系漫游指南》中的对话

乔治·内维尔-尼尔

关于数字系统——特别是现代计算机——更令人惊讶的事情之一是它们在时间保持方面的糟糕表现。当大多数程序在单个系统上运行时，这对大多数软件开发人员来说并不是一个重要的问题，但是一旦软件进入分布式系统领域，这种不准确性就变成了一个重大的挑战。很少有程序员阅读过该领域最重要的论文，即莱斯利·兰波特的《分布式系统中的时间、时钟和事件排序》（1978年）²，只有少数人开始意识到一旦他们进入分布式系统的世界所面临的问题。

任何关于时间的讨论都应该围绕两个不同的测量展开：同步和整步。同步，粗略地定义，是指在任何特定时刻两个不同时钟彼此之间的接近程度。如果两个时钟或计算机声称在完全相同的时刻是 15:30，那么它们被认为是同步的。“完全相同的时刻”的定义是第一个困难出现的地方。您关心的是相同的分钟（15:30）、相同的秒（15:30:00）、毫秒、微秒、纳秒等吗？您希望达到的精度水平大致定义了实现它的难度水平。

整步是单个时钟的时间保持质量。人们可能会认为一秒始终是一秒，但实际上需要有一个物理系统作为基础，并从中导出时间。计算机使用石英晶体作为所有内部操作的基础。您的笔记本电脑或服务器中的 3 GHz CPU 能够以该速度运行，是因为在主板上的某个地方有一小块石英，当对其施加电力时，它会以已知的频率振动。然后，该频率被倍增和分割，以驱动系统其余部分的各个部分。如果晶体和其他硬件部件不受环境的影响，那么所有计算机都将具有完美的整步性。唉，这是现实世界介入的地方之一。晶体会经历热、功率和老化的变化，而且没有两个晶体完全相同，但它们会在制造商数据表中提供的经过测试的范围内振动。例如，当服务器升温时（因为服务器正在运行复杂的工作负载），晶体将振荡得更快，计算机的内部时钟将提前运行，或更快地发生偏差。偏差对典型服务器的影响如图 1 所示。如果空气变冷，则晶体将振荡得更慢，秒将持续更长时间，从而使服务器上的时间负向偏差。

使用特定晶体可以实现的整步水平也是一个经济问题。较便宜的晶体比更昂贵的晶体稳定性更差（即，更容易发生偏差）。所有商品硬件——从最昂贵的服务器到最便宜的平板电脑——都具有非常便宜、低质量的晶体，成本约为 10 美分。典型的笔记本电脑或服务器，如果在没有任何类型的外部时间调节的情况下，将在几分钟内失去同步，并且在几个小时后可能已经与其他系统良好同步相差几分钟。

为了纠正不良的整步性，操作系统有一组例程来控制时钟。如果系统运行得太快，那么例程会告诉它减速；如果运行得太慢，那么它会告诉它加速。这些控制输入必须在一段时间内缓慢应用，以避免将系统推入滞后状态，在这种状态下，时钟会在适当的整步性附近剧烈振荡，但永远无法真正实现稳定性。

为了为时钟提供适当的控制，系统需要了解什么是太快或太慢，为此，它必须具有正确的或至少更好的外部时间源。

大多数开发人员可能会在逻辑上认为解决方案是购买更好的机器，但直到今天，您也无法购买到内置晶体比市场上最便宜的晶体更好的商业服务器或笔记本电脑。也许随着时间的推移，随着越来越多的公司构建分布式系统，这种情况可能会改变，但在 2015 年，这不是一个实际的选择。为了获得更好的整步性，您可以购买 PCI（外围组件互连）附加板上的高质量、稳定的晶体。然后，系统时钟通过 PCI 总线从此卡进行调节。然而，每张卡大约 1,000 美元，这种解决方案仅适用于少量服务器，或预算无限的服务器。

调节服务器上时钟的另一种方法是通过串行总线分发外部晶体振荡器。通过串行线路将高质量的 10 MHz 信号注入服务器是为一组机器提供良好整步性的另一种方法。分发这样的信号对于少量机器（最多 48 台）是合理的，但随着连接数量和电缆长度的增加而崩溃。再次，为整个数据中心布线这样的信号既非常昂贵，又容易出现自身的一系列问题。

我们稍后将回到如何将系统同步到外部时间源的问题，但首先我们必须解决程序如何找出它当前正在执行的系统上的时间的问题。

现在几点了？

对于大多数软件开发人员来说，“现在”的概念由单个系统调用 gettimeofday() 表示，该调用向调用者返回系统在调用时刻对时间的想法。这是否是有用的信息取决于所需时间测量的质量。如果系统只需要精确到秒级，那么 gettimeofday() 例程就足够了——而且它通常可以精确到毫秒级，尽管这可能会因操作系统中时间保持软件的质量而异。在决定如何在程序中获取时间时必须做出的权衡是在速度和精度之间。请求时间需要操作系统软件方面的大量工作，才能将准确的表示返回给用户程序。虽然 gettimeofday() 几乎可以在任何系统上工作，但 clock_gettime() 和 clock_getres() 例程为程序员提供了在处理时间时更大的灵活性。

具有 clock_* 例程的系统向用户程序公开了几种类型的时钟。例如，在 FreeBSD 操作系统上，时钟是 CLOCK_REALTIME, CLOCK_MONOTONIC CLOCK_UPTIME, CLOCK_VIRTUAL, 和 CLOCK_PROF。CLOCK_REALTIME 以挂钟相同的方式报告时间，是生成日志文件的系统最常用的时间源，因为这些日志文件将由想要知道事件发生时间的人类用户读取。其他时钟例程更专业，并在系统手册页中记录。

每个时钟都有两个变体：PRECISE，它获得尽可能精确的时间，但返回给调用者的时间最长；以及 FAST，它是最不准确的，但给出答案的速度最快。这两个变体很好地描述了基于计算机的时间保持中的一种紧张关系：您希望时间越精确，检索它所需的时间就越长。向底层硬件请求当前时间通常会返回最精确的答案，但它也需要时间，因为必须跨越保护边界，并且返回准确时间所需的机制本身也具有非零开销。

clock_gettime 和相关例程也存在于 Linux 上，但未出现在最新的 Mac OS X 版本（优胜美地）中。微软的 Windows 操作系统具有类似于 gettimeofday() 的功能，但名称完全不同，GetLocalTime()。

测量短暂的时间间隔——例如，几行 C 或 C++ 代码执行所需的时间——通常可以通过使用片上指令以更少的开销来完成。现代英特尔 CPU 有一个单条指令 rdtsc，它返回片上时间戳计数器。当程序希望测量两个本地、非网络事件之间的时间时，这是使用本地时间最快、最便宜的方式。

为特定应用程序选择正确的时钟选项非常重要。如果需要测量时间间隔，那么 rdtsc 或围绕它包装的库是最佳解决方案，而获取系统时间以用于日志文件可能应该使用带有 FAST 选项的 clock_gettime() 来执行；或者，如果 clock_gettime() 不可用，则使用 gettimeofday()。

寻找更好的时钟

现在我们知道如何让程序正确地向系统询问时间，以及如何测量本地时间间隔，我们可以回到将系统与某种形式的外部参考同步的问题。最常解决此挑战的方法是找到更好的时钟，定期向其询问时间，并调整系统的本地时钟以匹配外部参考。找到更好时间源的一种解决方案是使用网络，因为分布式系统中的所有系统在定义上都连接到网络。在 20 世纪 80 年代，一组研究人员定义了网络时间协议 (NTP)。³ NTP 首次记录于 1985 年，随后在 1988 年、1992 年和 2010 年进行了更新，是目前使用最成功的基于互联网的网络时间协议。

NTP 使用 UDP（不可靠数据报协议）实现为一个分布式系统，该系统具有质量较高和较低的时钟，形成一个层次结构，其中层级编号较低的时钟质量更高。层级 0 时钟被认为是参考时钟，包含高度稳定的晶体，例如基于铯或铷的晶体，或者它可以与 GPS（全球定位系统）同步，GPS 传输稳定可靠的时间信号。层级 1 系统通常通过直接电缆连接到层级 0 时钟；层级 2 时钟连接到层级 1；依此类推，这种时间参考链扩展到层级 15。对于任何特定层级时钟的时间质量都没有明确的标准，只有较低的数字预计具有更高的质量。在每一层都没有质量的硬性定义意味着技术的进步，即可以在较低（更好）的层级部署更准确的时钟，不需要重新编号当前系统。随着层级 0 和 1 时钟的改进，层级 2 及以上层级的可用时间也随之改进。

NTP 使用轮询机制来查询一组时钟上的时间，这些时钟用作算法的输入，然后该算法用于控制本地时钟。大多数操作系统都有某种版本的 adjtime() 系统调用，它允许 NTPd（网络时间协议守护程序）等外部程序根据需要加速或减慢系统时钟。像 NTP 这样的全球分布式协议必须充当良好的网络公民，避免用请求淹没网络。部分原因是 NTP 在互联网早期，当长、慢且不可靠的链路是常态时被指定，其默认轮询间隔为每 64 秒一次。由于这种较长的默认轮询间隔，新时钟可能需要数十分钟或更长时间才能与外部源同步；并且一旦达到某种程度的稳定，时钟仍然可能随着新的输入大约每分钟到达一次而漂移。

将轮询频率增加到最大值，即每 16 秒一次，可以提高时钟的精度和增加网络负载的成本，但仍然可能存在数毫秒的时间偏差，具体取决于环境和晶体的质量。正如本文第一部分所讨论的那样，NTP 的低轮询频率通常会阻止系统实现亚毫秒级同步。

数据中心时间

数据中心规模分布式系统的激增使得一个看似晦涩的协议，最初由 IEEE 在 2002 年定义，引起了更广泛受众的关注。精密时间协议 (PTP)¹ 最初旨在同步工厂自动化、发电和蜂窝网络中的系统，现在用于金融服务——特别是 HFT（高频交易）——以及其他需要亚微秒级同步的数据中心系统。

当查看所涉及的时间尺度时，工厂自动化、发电和蜂窝网络中亚毫秒级同步的需求显而易见。以每小时 30 英里速度移动的机器人手臂在一秒钟内移动 44 英尺，在这种速度下，与人类操作员或相邻机器人的碰撞将是灾难性的。以 60 Hz 交流电运行的电力网络需要使其所有共享组件同步；否则，将能量从一个模块传递到下一个模块可能会导致灾难性的、火灾性的故障。两个相邻电网的电流交替需要同步到远低于 10 微秒，典型额定值为 4.6 微秒。在蜂窝网络中，同步要求曾经只是处理移动设备在基站之间平稳切换所必需的，但现在通过多个基站提供高速数据服务，基站本身之间的同步要求为 +/- 1.5 微秒。IEEE 最初为这些应用设计了 PTP。

21 世纪的第一个十年见证了 HFT 的兴起，它将算法和高性能计算结合在一起，努力从数百万笔非常小的金融交易中提取大量价值。HFT 公司运营着成排的机器，这些机器都实时查看市场数据，然后根据股票和其他金融工具的感知价值之间的差异做出交易决策。HFT 世界受到对速度的需求的主导，但不可能在一台大型计算机上完成所有工作。为了实现规模，成排的服务器同时读取相同的数据并实时做出交易决策。这些交易决策需要知道事件的顺序——哪只股票在另一只股票下跌之前上涨。是 Mobil 在 Shell 下跌之前上涨，还是反过来？

这些金融交易发生的时间尺度首先移动到毫秒，然后是数十微秒，然后进入 1 微秒的范围——并且在某些应用中，甚至更小的范围也可能有用。HFT 市场不仅能够将 PTP 应用于其问题，而且其集体的金融实力意味着 PTP 功能开始出现在昂贵的——但仍然是商品——硬件中。许多网络接口卡和网络交换机现在直接支持 PTP 数据包的时间戳，或者将 PTP 守护程序版本作为选项包含在内。

PTP 在几个关键方面与 NTP 不同。PTP 专为少量主机而设计，例如工厂车间或一组蜂窝塔，旨在在单个网络上使用——事实上，大多数关于 PTP 的文档和论文都假设各个系统之间没有交换机或路由器跳。PTP 可以通过网络路由，但时间质量的损失足以阻止在大多数环境中使用它。想要可路由的、基于互联网的时间协议的人最好使用 NTP。

PTP 被设计为一种多播协议，其中有一个主时钟，PTP 中更好的时钟的名称，以及许多跟随主时钟的从时钟。主时钟每秒发送一次带有当前时间的 SYNC 数据包。从时钟定期发送多播 DELAY_REQUEST 数据包，主时钟使用 DELAY_RESPONSE 进行回复。DELAY_REQUEST/DELAY_RESPONSE 对允许从时钟确定自身与主时钟之间的单向延迟。如果没有此测量，从时钟就无法知道 SYNC 数据包实际何时在主时钟上发起的。总而言之，这些数据包允许从时钟根据更好时钟（主时钟）的时间更新自己的时钟，并在一定程度的抖动（主从系统之间数据包传输时间的小幅变化）的情况下这样做。

PTP 假定对称网络，其中数据包从主时钟传播到从时钟所花费的时间与从从时钟传播到主时钟所花费的时间相同。如果时间不对称，则客户端计算的偏移量可能会偏差几个微秒。开源 PTP 守护程序 PTPd 可以配置为考虑这种不对称性，但如果网络条件发生变化——例如，因为一个网络交换机被新的和不同的型号替换了——那么配置也必须更改。PTP 的大多数部署都不使用任何固定偏移量，而只是假设网络传播时间是对称的。

网络时间协议对抖动特别敏感。如果数据包始终需要恒定的时间才能从主时钟到达从时钟，那么可以在从时钟中编程一个简单的偏移量，并且它可以将此偏移量与 SYNC 数据包中的时间一起使用来控制其时钟。使用 ping 程序进行的简单测试将表明，数据包传输单个网段的时间会受到相当大的抖动的影响，这将阻止时钟同步到 10 微秒以内——当然也无法同步到 1 微秒以内。

当 PTP 用于实现良好的系统间同步时，抖动是一个重要的考虑因素。抖动的来源包括网络设备，包括接口、卡和交换机，以及软件，例如设备驱动程序和操作系统。当网络的竞争用户妨碍网络计时数据包时，网络交换机会引起抖动。所有关于 PTP 的文献以及来自硬件提供商的所有基准测试都描述了在其他方面未使用的网络上的条件。在自己的网络上运行计时协议是更可取的，因为它减少了网络本身引起的抖动。

在许多 PTP 部署中，当前最大的抖动贡献者是软件。当我们接管 PTPd 项目 (http://ptpd.sf.net)，PTP 的开源实现时，所有时间戳都是在用户空间中使用 gettimeofday() 在数据包通过设备驱动程序和操作系统的网络堆栈等多个软件层之后记录的。每个软件层都会引起一定程度的抖动，因为这些层由计时器驱动，并且数据包异步显示。我们的第一个改进是将时间戳移到内核中，使用 SO_TIMESTAMP 套接字选项记录时间戳。虽然这提高了同步质量，但这还不够，因此时间戳被移到了 BPF（伯克利数据包过滤器）中网络驱动程序代码的正上方。这使得在其他方面不繁忙的系统上实现了 10 微秒内的同步。PTP 在 HFT 世界中的激增，其中 10-Gb 以太网也很普遍，导致几家网卡提供商在其设备中添加了稳定的振荡器和时间戳硬件。至少有一家这样的供应商使用 PTPd，经过调整以适应供应商的硬件，在其他方面安静的网络上实现了 500 纳秒内与主时钟的同步。

测量中较少为人知的噪声贡献者来自现代 NIC（网络接口控制器）的构建方式。为了在网络接口中实现高带宽，重要的是将许多数据包批量处理在一起，然后再将它们作为一个组交给操作系统进行处理。如果 10-Gb 以太网网络上的每个数据包在到达时都生成中断，则将导致每秒 1480 万次中断，这在批量移动数据时是浪费的。任何支持 1 Gbps 或更高速度的 NIC 都将具有某种形式的 AIM（自适应中断调节），其中中断被收集起来，而设备不采取任何操作，直到到达一定数量为止。保留诸如 AIM 之类的选项会引入正弦波，其频率是中断调节率（在一个实例中，这是 8 KHz），进入测量，阻止系统实现良好的同步水平。

在为服务器提供准确时间的同时，还允许它们访问高带宽连接的一种解决方案是使用服务器的板载 1-Gbps 网络端口进行时间服务，并为数据提供单独的 1 或 10-Gbps 网络端口。为每台主机提供两个网络连接在许多数据中心中很常见，因为通常存在管理网络以及通向每台主机的数据网络。如果时间数据被搭载到管理网络上，那么 PTP 数据包应该放置在自己的虚拟 LAN 中，其服务质量高于管理数据。还需要注意避免大型数据副本，例如用于检索服务器日志文件的副本，因为这会将抖动引入时间流量。

在数据中心同步时间的常见做法是将主时钟设为基于 GPS 的时钟，并配备稳定的振荡器。虽然这样的时钟很昂贵，大约几千美元，但每个数据中心可能只需要一个，或者可能是两个用于故障转移，这比在每台服务器中放置稳定的振荡器卡要便宜得多。一个好的主时钟将在物理层之上完成其所有数据包的时间戳，就像昂贵的 NIC 所做的那样，以防止任何基于软件的抖动进入测量。

继续前进

在大量分布式主机之间实现亚微秒级同步是一项重大成就，但对于未来的应用，甚至需要更高水平的同步。10-Gbps 以太网在数据中心中的激增以及 25-、40- 和 100-Gbps 网络的 перспектива 将要求纳秒级的同步，以便确定数据包在主机 A 的到达是否发生在数据包在主机 B 的到达之前。在 10-Gbps 网络上，数据包只能间隔 67 纳秒到达；在更高的速度下，这个数字会小得多。

虽然第一个广泛应用 PTP 的数据中心在金融领域，但许多其他应用现在意识到需要比 NTP 能够实现的更高质量的同步。任何系统提出“谁对谁做了什么以及何时？”这个问题，并且需要精确到毫秒以内的答案的努力，都将希望找到一种集成 PTP 的方法。根据 IEEE 关于所有协议都应每五年审查和更新的要求，IEEE-1588 工作组目前正在讨论可能出现在协议版本 3 中的新功能。一旦新标准获得批准，硬件和软件供应商是否会跟进还有待观察。

1. IEEE 标准协会。1588-2008—用于网络测量和控制系统的精密时钟同步协议的 IEEE 标准； https://standards.ieee.org/findstds/standard/1588-2008.html。

2. Lamport, L. 1978. 分布式系统中的时间、时钟和事件排序。《通讯》21 (7): 558-565。

3. Mills, D. L. 1985. 网络时间协议。RFC 958。互联网工程任务组； https://tools.ietf.org/html/rfc958。

乔治·V·内维尔-尼尔 为乐趣和利润而从事网络和操作系统代码的工作。他还教授各种与编程相关的课程。他感兴趣的领域是代码探险、操作系统和重写您的糟糕代码（好吧，也许不是最后一个）。他获得了马萨诸塞州波士顿东北大学计算机科学学士学位，并且是、Usenix 协会和 IEEE 的成员。他是一位狂热的自行车爱好者和旅行家，目前居住在纽约市。

最初发表于 Queue vol. 13, no. 9—
在数字图书馆中评论本文

更多相关文章

马克·布鲁克, 安库什·德赛 - AWS 的系统正确性实践
构建可靠和安全的软件需要一系列方法来推理系统正确性。除了行业标准测试方法（例如单元测试和集成测试）之外，AWS 还采用了模型检查、模糊测试、基于属性的测试、故障注入测试、确定性模拟、基于事件的模拟以及执行跟踪的运行时验证。形式化方法一直是开发过程的重要组成部分——也许最重要的是，作为测试预言机的形式化规范，它为 AWS 的许多测试实践提供了正确的答案。正确性测试和形式化方法仍然是 AWS 的关键投资领域，这些领域已经看到的投资回报加速了这一进程。

阿基里斯·贝内托普洛斯 - 数据中心计算机的中间表示
我们已经达到了分布式计算无处不在的地步。内存应用程序数据大小正在超过单台机器的容量，因此需要将其在集群上进行分区；在线服务具有高可用性要求，这只能通过将系统部署为多个冗余组件的集合来满足；高持久性要求只能通过数据复制来满足，有时跨越广阔的地理距离。

大卫·R·莫里森 - 模拟：分布式系统中的一种未充分利用的工具
模拟在人工智能系统的发展中发挥着巨大的作用：我们需要一种高效、快速且经济高效的方式来训练人工智能代理在我们的基础设施中运行，而模拟绝对提供了这种能力。

马特·法塔，菲利普-约瑟夫·阿里达，帕特里克·哈恩，贝齐·拜尔 - 公司到云端：谷歌的虚拟桌面
超过四分之一的 Googler 使用内部、数据中心托管的虚拟桌面。这种本地部署的产品位于公司网络中，允许用户开发代码、访问内部资源以及从世界任何地方远程使用 GUI 工具。在其最显着的特性中，虚拟桌面实例可以根据手头的任务调整大小，具有持久的用户存储，并且可以在公司数据中心之间移动以跟随出差的 Googler。直到最近，我们的虚拟桌面都托管在使用名为 Ganeti 的自研开源虚拟集群管理系统的 Google 公司网络上的商用硬件上。今天，这项重要的且对 Google 至关重要的工作负载在 GCP（Google Compute Platform）上运行。