零基础入门分布式系统 3. Time, clocks, and ordering of events

s09g

发布于 2022-07-06 15:38:30

7780

发布于 2022-07-06 15:38:30

在本讲座中，我们将研究分布式系统中的时间概念。对时间的假设构成了分布式系统模型的一个关键部分。例如，基于超时的故障检测器需要测量时间以确定何时超时。操作系统依赖计时器和时钟，以便安排任务，跟踪CPU的使用，以及别的一些任务。应用程序经常希望记录事件发生的时间和日期：例如，当调试分布式系统中的错误时，时间戳对调试很有帮助，因为它们允许我们重建同一时间不同节点上发生事件的场景。所有这些都需要对时间进行精确测量。

分布式系统中的时钟和时间：

调度器、超时、故障检测器、重试定时器
性能测量、统计、分析
日志文件和数据库：记录事件发生的时间
有时间限制的数据（如缓存条目）
确定几个节点上的事件顺序

我们区分了两种类型的时钟

物理时钟：计算经过的秒数
逻辑时钟：计算事件，例如发送的信息

注意（NB. nota bene)：

数字电子学中的时钟（震荡器）≠ 分布式系统中的时钟（时间戳的来源）

3.1 Physical clocks

Physical clocks物理时钟 以秒为单位测量时间。它们包括基于钟摆或类似机制的模拟/机械钟，以及基于振动石英晶体等的数字钟。石英钟Quartz 存在于大多数腕表、每台电脑和移动电话、显示时间的微波炉以及许多其他日常用品中。

Quartz clock 石英钟的原理

石英晶体经激光修整，在特定的频率上产生机械共鸣
压电效应：机械力与电场相互转换
振荡器电路在谐振频率下产生信号
利用振荡周期数来测量经过的时间

石英钟很便宜，但它们并不完全准确。由于制造上的不完善，有些钟的运行速度比其他钟稍快。此外，石英振荡频率随着温度的变化而变化。典型的石英钟被调整为在室温下相当稳定，但明显较高或较低的温度会使时钟变慢。一个时钟运行快或慢的速度被称为漂移 drift。

drift 漂移 通过 **parts per million百万分率（ppm）**来衡量。1ppm = 1 microsecond / second = 86 ms / day = 32s / year。大多数计算机时钟漂移在50ppm以内。

当需要更高的精确度时，就需要使用原子钟。原子钟是基于某些原子的量子力学特性，如铯或铷。事实上，国际单位制 International System of Units（SI）中一秒钟的时间单位被定义为恰好是铯-133原子的一个特定共振频率的9,192,631,770个周期。

另一种获得高精度时间的方法是依靠GPS卫星定位系统，或类似的系统，如Galileo伽利略或GLONASS格洛纳斯。这些系统有数颗卫星在地球上方运行，并以非常高的精度广播当前的时间。接收方测量来自每颗卫星的信号到达时间，并以此计算与每颗卫星的距离，从而计算出自己的位置。只要接收器能够从卫星上获得清晰的信号，通过将GPS接收器连接到计算机，可以获得一个精确到微秒的时钟。数据中心通常有太多的电磁干扰，无法获得良好的信号，所以GPS接收器需要在数据中心的屋顶上安装天线。

基于原子钟（国际原子时 International Atomic Time，TAI）的时间测量系统运作一向良好，但它与我们日常的时间感知脱节。我们的时间感知是围绕着日出和日落的。地球自转一圈并不正好需要24小时。事实上，地球的旋转速度甚至不是恒定的：由于潮汐、地震、冰川融化和一些无法解释的因素的影响，它是波动的。现在问题是：我们有两个不同的时间定义——一个基于量子力学，另一个基于天文学——而且这两个定义并不精确匹配。

解决的方案是使用协调世界时（Coordinated Universal Time，UTC），它以原子时钟为基础，但考虑了地球自转变化的修正。在日常生活中，我们使用当地的时区，它被指定为UTC的偏移量。

UTC和TAI的区别在于，UTC包括闰秒leap seconds。而闰秒是根据实际需要添加的，以保持UTC与地球自转大致同步。

由于闰秒的存在，一个小时不总是3600秒一天也不总是86400秒。在UTC时间尺度中，由于闰秒的存在，一天可以是86,399秒，86,400秒，或86,401秒。这使得需要处理日期和时间的软件变得复杂。

在计算中，时间戳timestamp 是一个特定时间点的代表。有两种常用的时间戳表示法：Unix时间戳和ISO 8601。Unix时间戳中，0对应于1970年1月1日，被称为纪元epoch。这里有一些小的变种：例如，Java的System.currentTimeMillis()很像Unix时间戳，但使用毫秒而不是秒。

为了正确的计算，使用时间戳的软件需要知道闰秒的情况。比如，如果你想计算两个时间戳之间经过了多少秒，你需要知道这两个日期之间插入了多少个闰秒。

软件中最常见的方法是直接忽略闰秒，假装它们不存在，并希望这个问题能以某种方式消失。Unix时间戳和POSIX的标准都采用了这种方法。对于只需要粗略时间的软件来说（比如四舍五入到最近的一天），这种方法很好，因为几秒钟的差别并不明显。

然而，操作系统和分布式系统经常依靠高精度的时间戳来精确测量时间，在这种情况下，一秒钟的差异都是非常明显的，忽略闰秒是非常危险的。例如，假设你有一个Java程序，在一个正闰秒内（即在时钟显示23:59:60时），相隔500毫秒两次调用System.currentTimeMillis()。这两个时间戳之间的差是多少？不是500，因为currentTimeMillis()时钟没有考虑到闰秒。时钟是否会停止，所以这两个时间戳之间的差是0？或者差值甚至可能是负的，所以时钟会短暂地往回跑？Java文档中没有明说这个问题。

2012年6月30日许多服务同时失效的原因就是对闰秒的处理不当。由于Linux内核中的一个bug，当运行多线程进程时，闰秒有很大概率触发livelock [Allen, 2013, Minar, 2012]。即使重启也不能解决这个问题，除非通过设置系统时钟重置内核的状态。

如今，部分软件会显示地处理闰秒，而其他程序依然会忽略它们。当前广泛使用的一个可行的解决方案是，当正数闰秒发生时，不是将其插入23:59:59和00:00:00之间，而是通过在这段时间内故意放慢时钟速度（或在负数闰秒的情况下加快时钟速度），将额外的秒数分散到该时间前后的几个小时。这种方法被称为smearing the leap second 涂抹闰秒（这并非没有问题）。这只是一个实用的替代方案，可以让所有的软件适应闰秒，但不总是可行方案。

3.2 Clock synchronisation and monotonic clocks

原子钟太过昂贵和笨重，无法内置到每台电脑和手机中，因此计算机采用石英钟来记录物理时间/UTC（自带电池，断电时能持续运行）。由于石英钟漂移，误差会逐渐积累，造成时钟偏移Clock skew (在一个时间点上,两个时钟之间的差)。最常见解决方案的是使用网络时间协议（Network Time Protocol，NTP），定期从拥有更精确时间源的服务器（原子钟或GPS接收器）获取当前时间。所有主流操作系统都有内置的NTP客户端。

由于随机网络延迟，时间同步是很困难的。网络延迟和节点的处理速度变化很大。为了减少随机变化的影响，NTP对时间测量进行多次采样，并应用统计过来消除异常值。

当客户端发送一个请求信息时，它包括根据客户端时钟的当前时间戳t1。当服务器收到request，在处理它之前，服务器根据服务器的时钟记录当前的时间戳t2。当服务器发送该request的response时，它返回request中的值t1，并且还在response中包括服务器的接收时间戳t2和服务器的响应时间戳t3。最后，当客户端收到response时，它根据客户端的时钟记录当前的时间戳t4。我们可以通过从客户端的角度计算往返时间（t4 - t1）并减去服务器上的处理时间（t3 - t2）来确定消息在网络上花费的时间。然后我们估计单程网络延迟为总网络延迟的一半。因此，当response到达客户端时，我们可以估计服务器的时钟已经走到了t3加上单向网络延迟。然后我们从估计的服务器时间中减去客户的当前时间t4，以获得两个时钟之间的估计偏移。

这种估计依赖于假设网络延迟在两个方向上大致相同。如果延迟是由客户和服务器之间的地理距离主导的，那么假设大概率成立。然而，如果网络中的排队时间是影响延迟的重要因素（例如，如果一个节点的网络链接负载很高，而另一个节点的链接有大量的空闲容量），那么请求和响应延迟之间可能有很大的差异。不幸的是，大多数网络没有给节点提供任何关于特定数据包所经历的实际延迟的指标。

一旦NTP估计出客户端和服务器之间的时钟偏移，下一步就是调整客户端的时钟，使其与服务器保持一致。根据时钟偏移的程度，将采取不同的方法。

当时钟偏移< 125 ms时，客户端轻微调整时钟速度，使其运行稍快或稍慢，在几分钟内(< 5 min)逐渐减少偏移。这个过程被称为时钟回转slewing。
如果偏移较大（125 ms ~ 1000s)，回转将需要太长的时间，所以NTP客户端反而会根据服务器的时间戳，强行将其时钟设置为估计的正确时间。这就是所谓的步进step时钟。任何在客户端观察时钟的应用程序都会看到时间突然向前或向后跳跃。
如果偏移非常大（默认情况下，超过15分钟），NTP客户端可能会认为一定有什么问题，并拒绝调整时钟，把问题留给用户或操作员来纠正。因此任何依赖于时钟同步的系统都需要监测时钟偏移：运行NTP，并不能保证时钟是正确的，因为它可能陷入panic状态，拒绝调整时钟。

时钟可能被NTP步进，即突然向前或向后移动，这对所有需要测量经过时间的软件都有影响。举一个Java的例子，我们想测量一个函数doSomething()的运行时间。Java有两个函数用于从操作系统的本地时钟获取当前时间戳：currentTimeMillis()和nanoTime()。除了不同的精度（毫秒和纳秒），两者之间的关键区别是它们在面对NTP或其他来源的时钟调整时的表现。

currentTimeMillis()是一个time-of-day时刻时钟（也被称为real-time实时时钟），它返回从一个固定的参考点（在这里是指1970年1月1日的Unix epoch）以来所经过的时间。当NTP客户端步进了本地时钟，time-of-day 时钟可能会跳时间。因此，如果使用这样的时钟来测量经过的时间，结束时间戳和开始时间戳之间的差可能比实际经过的时间大得多（如果时钟向前跳），或者甚至可能是负的（如果时钟向后跳）。因此，这种类型的时钟不适合用来测量经过的时间。

另一方面，nanoTime()是一个monotonic单调时钟，不受NTP步进的影响：它仍然计算经过的秒数，但保持向前移动。向前移动的速度可能会被NTP的回转所调整。这使得单调的时钟在测量经过的时间时更加稳健。缺点是，来自单调时钟的时间戳本身是没有意义的：它测量的是自某个任意参考点以来的时间，例如这台计算机启动以来的时间。当使用单调时钟时，只有来自同一节点的两个时间戳之间的差才有意义。在不同的节点之间比较单调时钟的时间戳是没有意义的。

大多数操作系统和编程语言都同时提供了time-of-day时钟和monotonic时钟。

3.3 Causality and happens-before

现在我们将继续讨论分布式系统中的事件排序问题，这与时间的概念密切相关。在这个情景中，用户A发表了一个声明m1，并将其作为消息发送给另外两个用户B和C。收到m1时，用户B向用户A和C发送回复m2。然而，即使我们假设网络链接是可靠的，reordering 重排也可能发送，所以如果m1在网络中稍有延迟，C可能会在m1之前收到m2。

从C的视角来看，消息顺序是混乱的。C首先看到的是回复，然后是它所回复的信息。这看起来就像B能够看到未来，并在A发言之前就预见到了A的声明。在现实生活中，这种对消息的重新排序是不会发生的，所以我们从直觉上也不希望它发生在计算机系统中。

作为一个更技术性的例子，考虑m1是一条在数据库中创建一个对象的指令，而m2是一条更新这个对象的指令。如果一个节点在m1之前处理m2，它将首先尝试更新一个不存在的对象，然后创建一个随后不会被更新的对象。只有当m1在m2之前被处理时，数据库指令才有意义。

C怎样才能确定信息的正确顺序？单调时钟是行不通的，因为它的时间戳在不同的节点之间是没有可比性的。第一个可能方案是，每当用户想发送消息时，从time-of-day时钟中获取一个时间戳，并将该时间戳附在消息上。在这种情况下，我们可以预期m2的时间戳晚于m1，因为m2是对m1的回应，所以m2一定发生在m1之后。

不幸的是，在一个部分同步的系统模型中，这并不可靠。由NTP和类似协议执行的时钟同步总是对两个时钟之间真实偏移的近似，尤其是如果两个方向的网络延迟是不对称的。因此，我们不能排除以下情况的发生：A根据时钟发送m1，时间戳为t1。当B收到m1时，根据B的时钟，时间戳为t2，其中t2<t1，因为A的时钟稍稍早于B。因此，如果根据time-of-day时钟的时间戳对信息进行排序，又会出现错误的顺序。

为了公式化"正确"顺序的含义，我们定义了happens-before relation。假设每个节点只有一个执行线程，所以对于一个节点的任何两个执行步骤，先后执行是很清楚的。更正式地说，我们假设在同一节点上发生的事件有一个strict total order严格全序。一个多线程的过程可以通过使用每个线程一个节点来进行建模。

然后，我们通过定义跨节点的顺序：一个消息应该先被发送，后被接收。我们假设每条发送的信息都是唯一的，所以当收到一条信息时，我们总是能明确知道该信息是在哪里和何时发送的。在实践中，重复的消息可能存在，但我们可以使它们唯一，例如在每个消息中包括发送者节点的ID和一个序列号。

最后，我们使用传递律transitive closure，得到happens-before relation。这是一个partial order偏序，也就是说，对于某些事件a和b来说，有可能既没有a在b之前发生，也没有b在a之前发生，在这种情况下，我们把a和b称为并发concurrent。请注意，这里的 "并发concurrent"并不是指 "同时at the same time"，而是指a和b是独立的，即不存在从一个到另一个的信息序列。