不可靠的时钟

在分布式系统中，时间是一件棘手的事情，因为通信不是即时的：消息通过网络从一台机器传送到另一台机器需要时间。收到消息的时间总是晚于发送的时间，但是由于网络中的可变延迟，我们不知道多少时间。这个事实有时很难确定在涉及多台机器时发生事情的顺序。应用程序以各种方式依赖于时钟来回答以下问题：

• 这个请求是否超时了？
• 这项服务的第 99 百分位响应时间是多少？
• 在过去五分钟内，该服务平均每秒处理多少个查询？
• 用户在我们的网站上花了多长时间？
• 这篇文章在何时发布？
• 在什么时间发送提醒邮件？
• 这个缓存条目何时到期？
• 日志文件中此错误消息的时间戳是什么？

而且，网络上的每台机器都有自己的时钟，这是一个实际的硬件设备：通常是石英晶体振荡器。这些设备不是完全准确的，所以每台机器都有自己的时间概念，可能比其他机器稍快或更慢。可以在一定程度上同步时钟：最常用的机制是网络时间协议（NTP），它允许根据一组服务器报告的时间来调整计算机时钟；服务器则从更精确的时间源（如 GPS 接收机）获取时间。

在现代计算机中，当我们提到时钟时，其往往指这两种不同的类型：时钟和单调钟；它们都能用于衡量时间，但是它们的目的却相去甚远。

时钟

时钟是您直观地了解时钟的依据：它根据某个日历（也称为挂钟时间（wall-clock time））返回当前日期和时间。例如，Linux 上的 clock_gettime(CLOCK_REALTIME) 和 Java 中的 System.currentTimeMillis() 返回自 epoch（1970 年 1 月 1 日 午夜 UTC，格里高利历）以来的秒数（或毫秒），根据公历日历，不包括闰秒。有些系统使用其他日期作为参考点。时钟通常与 NTP 同步，这意味着来自一台机器的时间戳（理想情况下）意味着与另一台机器上的时间戳相同。但是如下节所述，时钟也具有各种各样的奇特之处。特别是，如果本地时钟在 NTP 服务器之前太远，则它可能会被强制重置，看上去好像跳回了先前的时间点。这些跳跃以及他们经常忽略闰秒的事实，使时钟不能用于测量经过时间。

时钟还具有相当粗略的分辨率，例如，在较早的 Windows 系统上以 10 毫秒为单位前进。 时钟虽然看起来简单易用，但却具有令人惊讶的缺陷：一天可能不会有精确的 86,400 秒，时钟可能会前后跳跃，而一个节点上的时间可能与另一个节点上的时间完全不同。正如网络丢包与任意延迟包的问题，尽管网络在大多数情况下表现良好，但软件的设计必须假定网络偶尔会出现故障，而软件必须正常处理这些故障。时钟也是如此：尽管大多数时间都工作得很好，但需要准备健壮的软件来处理不正确的时钟。

单调钟

单调钟适用于测量持续时间（时间间隔），例如超时或服务的响应时间：Linux 上的 clock_gettime(CLOCK_MONOTONIC)，和 Java 中的 System.nanoTime()都是单调时钟。这个名字来源于他们保证总是前进的事实（而时钟可以及时跳回）。你可以在某个时间点检查单调钟的值，做一些事情，且稍后再次检查它。这两个值之间的差异告诉你两次检查之间经过了多长时间。但单调钟的绝对值是毫无意义的：它可能是计算机启动以来的纳秒数，或类似的任意值。特别是比较来自两台不同计算机的单调钟的值是没有意义的，因为它们并不是一回事。

在具有多个 CPU 插槽的服务器上，每个 CPU 可能有一个单独的计时器，但不一定与其他 CPU 同步。操作系统会补偿所有的差异，并尝试向应用线程表现出单调钟的样子，即使这些线程被调度到不同的 CPU 上。当然，明智的做法是不要太把这种单调性保证当回事。。如果 NTP 协议检测到计算机的本地石英钟比 NTP 服务器要更快或更慢，则可以调整单调钟向前走的频率（这称为偏移（skewing）时钟）。

默认情况下，NTP 允许时钟速率增加或减慢最高至 0.05％，但 NTP 不能使单调时钟向前或向后跳转。单调时钟的分辨率通常相当好：在大多数系统中，它们能在几微秒或更短的时间内测量时间间隔。在分布式系统中，使用单调钟测量经过时间（elapsed time）（比如超时）通常很好，因为它不假定不同节点的时钟之间存在任何同步，并且对测量的轻微不准确性不敏感。

不准确的时钟同步

单调钟不需要同步，但是时钟需要根据 NTP 服务器或其他外部时间源来设置才能有用。不幸的是，我们获取时钟的方法并不像你所希望的那样可靠或准确：硬件时钟和 NTP 可能会变幻莫测。计算机中的石英钟可能会出现所谓的漂移（drifts）（运行速度快于或慢于预期），并且该现象取决于机器的温度。Google 假设其服务器时钟漂移为 200 ppm（百万分之一），相当于每 30 秒与服务器重新同步一次的时钟漂移为 6 毫秒，或者每天重新同步的时钟漂移为 17 秒。即使一切工作正常，此漂移也会限制可以达到的最佳准确度。

• 如果计算机的时钟与 NTP 服务器的时钟差别太大，可能会拒绝同步，或者本地时钟将被强制重置。任何观察重置前后时间的应用程序都可能会看到时间倒退或突然跳跃。
• 如果某个节点被 NTP 服务器意外阻塞，可能会在一段时间内忽略错误配置。有证据表明，这在实践中确实发生过。
• NTP 同步只能和网络延迟一样好，所以当您在拥有可变数据包延迟的拥塞网络上时，NTP 同步的准确性会受到限制。一个实验表明，当通过互联网同步时，35 毫秒的最小误差是可以实现的，尽管偶尔的网络延迟峰值会导致大约一秒的误差。根据配置，较大的网络延迟会导致 NTP 客户端完全放弃。
• 一些 NTP 服务器错误或配置错误，报告时间已经过去了几个小时。NTP 客户端非常强大，因为他们查询多个服务器并忽略异常值。尽管如此，在互联网上陌生人告诉你的时候，你的系统的正确性还是值得担忧的。
• 闰秒导致 59 分钟或 61 秒长的分钟，这混淆了未设计闰秒的系统中的时序假设。闰秒已经使许多大型系统崩溃的事实说明了，关于时钟的假设是多么容易偷偷溜入系统中。处理闰秒的最佳方法可能是通过在一天中逐渐执行闰秒调整（这被称为拖尾（smearing）），使 NTP 服务器“撒谎”，虽然实际的 NTP 服务器表现各异。
• 在虚拟机中，硬件时钟被虚拟化，这对于需要精确计时的应用程序提出了额外的挑战。当一个 CPU 核心在虚拟机之间共享时，每个虚拟机都会暂停几十毫秒，而另一个虚拟机正在运行。从应用程序的角度来看，这种停顿表现为时钟突然向前跳跃。
• 如果您在未完全控制的设备上运行软件（例如，移动设备或嵌入式设备），则可能完全不信任该设备的硬件时钟。一些用户故意将其硬件时钟设置为不正确的日期和时间，例如，为了规避游戏中的时间限制，时钟可能会被设置到很远的过去或将来。

如果你足够关心这件事并投入大量资源，就可以达到非常好的时钟精度。例如，针对金融机构的欧洲法规草案 MiFID II 要求所有高频率交易基金在 UTC 时间 100 微秒内同步时钟，以便调试“闪崩”等市场异常现象，并帮助检测市场操纵。使用 GPS 接收机，精确时间协议（PTP）以及仔细的部署和监测可以实现这种精确度。然而，这需要很多努力和专业知识，而且有很多东西都会导致时钟同步错误。如果你的 NTP 守护进程配置错误，或者防火墙阻止了 NTP 通信，由漂移引起的时钟误差可能很快就会变大。

置信区间

您可能能够以微秒或甚至纳秒的分辨率读取机器的时钟。但即使可以得到如此细致的测量结果，这并不意味着这个值对于这样的精度实际上是准确的。实际上，如前所述，即使您每分钟与本地网络上的 NTP 服务器进行同步，很可能也不会像前面提到的那样，在不精确的石英时钟上漂移几毫秒。使用公共互联网上的 NTP 服务器，最好的准确度可能达到几十毫秒，而且当网络拥塞时，误差可能会超过 100 毫秒。因此，将时钟读数视为一个时间点是没有意义的——它更像是一段时间范围：例如，一个系统可能以 95％的置信度认为当前时间处于本分钟内的第 10.3 秒和 10.5 秒之间，它可能没法比这更精确了。如果我们只知道 ±100 毫秒的时间，那么时间戳中的微秒数字部分基本上是没有意义的。

不确定性界限可以根据你的时间源来计算。如果您的 GPS 接收器或原子（铯）时钟直接连接到您的计算机上，预期的错误范围由制造商报告。如果从服务器获得时间，则不确定性取决于自上次与服务器同步以来的石英钟漂移的期望值，加上 NTP 服务器的不确定性，再加上到服务器的网络往返时间（只是获取粗略近似值，并假设服务器是可信的）。

不幸的是，大多数系统不公开这种不确定性：例如，当调用 clock_gettime()时，返回值不会告诉你时间戳的预期错误，所以你不知道其置信区间是 5 毫秒还是 5 年。一个有趣的例外是 Spanner 中的 Google TrueTime API，它明确地报告了本地时钟的置信区间。当你询问当前时间时，你会得到两个值：[最早，最晚]，这是最早可能的时间戳和最晚可能的时间戳。在不确定性估计的基础上，时钟知道当前的实际时间落在该区间内。间隔的宽度取决于自从本地石英钟最后与更精确的时钟源同步以来已经过了多长时间。

如果依赖同步时钟

有序事件的时间戳

很多时候我们会依赖时钟在多个节点上对事件进行排序。例如，如果两个客户端写入分布式数据库，谁先到达？哪一个更近？下图显示了在具有多领导者复制的数据库中对时钟的危险使用，客户端 A 在节点 1 上写入 x = 1；写入被复制到节点 3；客户端 B 在节点 3 上增加 x（我们现在有 x = 2）；最后这两个写入都被复制到节点 2。

当一个写入被复制到其他节点时，它会根据发生写入的节点上的时钟时钟标记一个时间戳。在这个例子中，时钟同步是非常好的：节点 1 和节点 3 之间的偏差小于 3ms，这可能比你在实践中预期的更好。尽管如此，上图中的时间戳却无法正确排列事件：写入 x = 1 的时间戳为 42.004 秒，但写入 x = 2 的时间戳为 42.003 秒，即使 x = 2 在稍后出现。当节点 2 接收到这两个事件时，会错误地推断出 x = 1 是最近的值，而丢弃写入 x = 2。效果上表现为，客户端 B 的增量操作会丢失。

这种冲突解决策略被称为最后写入为准（LWW），它在多领导者复制和无领导者数据库（如 Cassandra 和 Riak）中被广泛使用。有些实现会在客户端而不是服务器上生成时间戳，但这并不能改变 LWW 的基本问题：

• 数据库写入可能会神秘地消失：具有滞后时钟的节点无法用快速时钟覆盖之前由节点写入的值，直到节点之间的时钟偏差过去。此方案可能导致一定数量的数据被悄悄丢弃，而未向应用报告任何错误。
• LWW 无法区分高频顺序写入（譬如客户端 B 的增量操作一定发生在客户端 A 的写入之后）和真正并发写入（写入者意识不到其他写入者）。需要额外的因果关系跟踪机制（例如版本向量），以防止因果关系的冲突。
• 两个节点可以独立生成具有相同时间戳的写入，特别是在时钟仅具有毫秒分辨率的情况下。为了解决这样的冲突，还需要一个额外的决胜值（tiebreaker）（可以简单地是一个大随机数），但这种方法也可能会导致违背因果关系。

因此，尽管通过保留最“最近”的值并放弃其他值来解决冲突是很诱惑人的，但是要注意，“最近”的定义取决于本地的时钟，这很可能是不正确的。即使用频繁同步的 NTP 时钟，一个数据包也可能在时间戳 100 毫秒（根据发送者的时钟）时发送，并在时间戳 99 毫秒（根据接收者的时钟）处到达——看起来好像数据包在发送之前已经到达，这是不可能的。

NTP 同步是否能足够准确，以至于这种不正确的排序不会发生？也许不能，因为 NTP 的同步精度本身受到网络往返时间的限制，除了石英钟漂移这类误差源之外。为了进行正确的排序，你需要一个比测量对象（即网络延迟）要精确得多的时钟。所谓的逻辑时钟是基于递增计数器而不是振荡石英晶体，对于排序事件来说是更安全的选择（请参见“检测并发写入”）。逻辑时钟不测量一天中的时间或经过的秒数，而仅测量事件的相对顺序（无论一个事件发生在另一个事件之前还是之后）。相反，用来测量实际经过时间的时钟和单调钟也被称为物理时钟。我们将在“顺序保证”中查看更多订购信息。

全局快照的同步时钟

快照隔离是数据库中非常有用的功能，它允许只读事务看到特定时间点的处于一致状态的数据库，且不会锁定和干扰读写事务。快照隔离最常见的实现需要单调递增的事务 ID。如果写入比快照晚（即，写入具有比快照更大的事务 ID），则该写入对于快照事务是不可见的。在单节点数据库上，一个简单的计数器就足以生成事务 ID。但是当数据库分布在许多机器上，也许可能在多个数据中心中时，由于需要协调，（跨所有分区）全局单调递增的事务 ID 可能很难生成。事务 ID 必须反映因果关系：如果事务 B 读取由事务 A 写入的值，则 B 必须具有比 A 更大的事务 ID，否则快照就无法保持一致。在有大量的小规模、高频率的事务情景下，在分布式系统中创建事务 ID 成为一个站不住脚的瓶颈。

我们可以使用同步时钟的时间戳作为事务 ID 吗？如果我们能够获得足够好的同步性，那么这种方法将具有很合适的属性：更晚的事务会有更大的时间戳。当然，问题在于时钟精度的不确定性。Spanner 以这种方式实现跨数据中心的快照隔离。它使用 TrueTime API 报告的时钟置信区间，并基于以下观察结果：如果您有两个置信区间，每个置信区间包含最早和最近可能的时间戳（$A = [A_{earliest}, A_{latest}]$，$B=[B_{earliest}, B_{latest}]$），这两个区间不重叠（即：$A_{earliest} < A_{latest} < B_{earliest} < B_{latest}$），那么 B 肯定发生在 A 之后——这是毫无疑问的。只有当区间重叠时，我们才不确定 A 和 B 发生的顺序。

为了确保事务时间戳反映因果关系，在提交读写事务之前，Spanner 在提交读写事务时，会故意等待置信区间长度的时间。通过这样，它可以确保任何可能读取数据的事务处于足够晚的时间，因此它们的置信区间不会重叠。为了保持尽可能短的等待时间，Spanner 需要保持尽可能小的时钟不确定性，为此，Google 在每个数据中心都部署了一个 GPS 接收器或原子钟，允许时钟在大约 7 毫秒内同步。