慢慢的博客

计算机的时间奥秘

 Posts  2695  6 分钟

Rain is falling all around
it falls on field and tree
it rains on the umbrella here
And on the ships at sea

如何表示时间

我们现在看到的时间，是不是一个准确的时间？时间是一个非常抽象的问题，吸引着许多伟大的科学家、哲学家和物理学家花毕生精力去解释时间的本质。目前存在着两种时间计量系统：

  • 世界时（UT1）：基于地球自转的，它以地球的自转来计量时间。但由于地球自转速率正在变慢，所以世界时的秒长会逐渐变大，每天达到千分之几。
  • 原子时：取微观世界铯原子的两个超精细能级之间跃迁辐射的频率作为时间度量单位，精确度非常高，误差不超过千万分之一秒。 所以，原子时是度量时间均匀的尺度，但是与地球空间位置无关；世界时定义自转一周为一天，这对人们的日常生产生活非常重要，但是度量时间的均匀性不好。

为了统一原子时和世界时间的差距，产生了协调世界时（UTC）。其规定以原子时的秒长为基础，同时在时刻上要尽量接近于世界时。但是因为世界时会越来越慢，所以在 1972 年引入闰秒机制。规定 UTC 的时刻与 UT1 时刻之差保持在正负 0.9 秒之内，必要时用跃阶 1 整秒的方式来调整。这个1整秒的调整就是闰秒。UTC 从1972 年 1 月起正式成为国际标准时间。

计算机里的时间

在计算机的主板上，有一个石英晶体震荡器，其频率是 32768Hz/s。在通电的时候，石英晶体每震动 32768 次，就表示 1s 到了。但是石英晶体存在误差的情况，每天的误差在正负 1s，并且会随着温度的变化而变大。

同时，在计算机里存在着两种时间：system_clock 和 steady_clock：

  • system_clock：系统时钟，他与 UTC 时间同步，能够被修改、回退。
  • steady_clock：单调时钟，通过记录当前系统执行的总指令条数或者记录开机至今经过的总毫秒数来表示时间，相当于教练手中的秒表，只会增长。但也因其特性，比较不同节点上的单调时钟的值是没有意义的。

基于两者的特性，我们经常用 steady_clock 做定时器的时间步长，用 system_clock 做时间戳或集群间时间同步的标准。但是如何保证我们机器的 system_clock 是精准的？

时间同步方案

1. NTP 协议

NTP 协议的目标是将所有计算机的时间同步到几毫秒误差内。实际上广域网会达到几十毫秒的误差，局域网可以在一毫米内。NTP 协议是一种主从式架构协议，使用分层的时钟源系统，每一层称为 Stratum，阶层的上限是 15，阶层 16 表示未同步。

  • 阶层 0：基准时间服务器，主要是高精度计时设备，如铯原子时钟、铷原子时钟，GPS 时钟，无线电时钟等。他们生成非常精确的脉冲信号，触发计算机上的中断和时间戳；
  • 阶层 1：主时间服务器，与阶层 0 设备相连，在几微妙误差内同步。同层之间可以相互连接，进行完整性检查和备份；
  • 阶层 2：通过网络和阶层 1 同步，每个节点可以连接多个阶层 1 服务器，同阶层也可以相互连接；
  • ……

NTP 协议的时间校准：

根据上图，我们可以确定，A、B 之间的网络往返时间 RTT：T = (T4 - T1) - (T3 - T2)

假设 A、B 之间的误差为 θ，且网络往返的时间相同，则 B-T3 到 A-T4 的时间 = A-T3' 到 A-T4 的时间，所以 θ = T/2 - (T4 - T3)，知道误差后，A 就能进行校准。

2. Lamport 逻辑时钟

NTP 协议不是很精准，前面我们推导偏移公式时假设网络的往返时间是一样的，但是实际网络中，这两个阶段所造的路由，所花的时间可能不一样，计算的时间偏移也是不准确的。

物理时钟在计算机上并不可靠，甚至会出现时间回退的现象，给一些业务（如雪花算法等）造成严重的影响。为了保证时间不会回退，就需要人为的构造一个递增序列的逻辑时钟，这就是 Lamport 逻辑时钟的基本思想。了解 Lamport 需要了解两个数学概念：偏序和全序：

  • 偏序：给定集合 S，“≤” 是 S 上的二元关系，若 “≤” 满足：
    1. 自反性：∀a∈S，有 a≤a；
    2. 反对称性：∀a，b∈S，a≤b 且 b≤a，则 a=b；
    3. 传递性：∀a，b，c∈S，a≤b 且 b≤c，则 a≤c；
  • 全序：比偏序多了一个完全性：
    1. 完全性：∀a，b∈S，必有 a ≤ b 或 b ≤ a； 简单的说，偏序的意思是集合中的元素部分有序，而全序的意思是集合中的任意一对元素都是可以相互比较的。

假设我们把事件 A 发生在时间 B 之前定义为 A → B，则一下三种条件都满足 A → B：

  • A 和 B 是同一个进程内的事件，A 发生在 B 之前，则 A → B；
  • A 和 B 在不同的进程中，A 是发送进程内的发送事件，B 是同一消息接受进程内的接受事件，则 A → B；
  • 如果 A → C，C → B，则 A → B。

如果 A 和 B 没有先后关系，则称两个事件是并发的，即 A || B。

同时，我们对分布式系统中的每个进程 Pi 保存一个本地逻辑时钟值 Ci，Ci(a) 表示进程 Pi 发生事件 a 时的逻辑时钟值，Ci 的更新算法如下：

  • 进程 Pi 每发生一次事件，Ci++；
  • 进程 Pi 给进程 Pj 发送消息，需要带上自己的本地逻辑时钟 Ci；
  • 进程 Pj 接收消息后，更新 Cj 为 max(Ci, Cj) + 1；

上图的逻辑时钟算法构造的整个事件集合是一种偏序关系，只有部分事件可以比较大小。但如果我们另外加入一个条件：判断两个进程号的大小，就可以使整个事件集合变成一种全序关系。于是，在偏序的基础上，如果 Ci(a) == Ci(b)，若 b 的进程号大于 a 的进程号，则 a → b。则上图的全序关系可以表示为 a → f → b → e → c → d。

3. 向量时钟

Lamport 逻辑时钟存在的问题是不能描述事件的因果关系。如上图，C(e) > C(f)，但两种并不含有因果关系。向量时钟将两者的时间分割开来，通过向量的方式维护每个进程的时间。同时进程在通信时，除了同步本进程的时钟值，还同步自己知道的其他进程的时钟值。算法如下：

  • 分布式系统中每个进程 Pi 保存一个本地逻辑时钟向量值 VCi，向量的长度是分布式系统中进程的总个数，VCi(j) 表示进程 Pi 知道的进程 Pj 的本地逻辑时钟值，VCi 的更新算法：
  • VCi 初始值全为 0：VCi = [0, 0, ……, 0];
  • 进程 Pi 每发生一次时间，VCi[i]++；
  • 进程 Pi 给进程 Pj 发送消息，需要带上自己的向量时钟 VCi；
  • 进程 Pj 接收消息，需做下面两步操作：
    • 对应 VCj 向量中的每个值 VCj[k]，更新为 max(VCi[k], VCj[k])；
    • 将 VCj 中自己对应的时钟值加 1，即 VCj[j]++；

向量时钟的作用：

  1. 检测数据冲突。分布式数据库中数据存在多个副本，每个副本都可能提供写操作，如果两个副本都对同一个数据进行写操作，就可能造成冲突，向量时钟可以检测这种冲突（MVCC）。如上图，a → b → c → d → e 都有因果关系，不会产生冲突，但是 e 和 f 是并发关系 e || f，这两个会有数据冲突，向量时钟可以检测这种冲突。
  2. 确定事件间的因果关系。举个微信朋友圈的例子。

  • A 发了一条朋友圈，同步到了 B 和 C；
  • B 问 A 去哪玩，消息同步给 A 和 C；
  • A 回复长白山，消息同步给 B 和 C；
  • 由于网络原因，C 先收到了“长白山”，在收到了“去哪玩”时，通过向量时钟，发现其先于“去哪玩”，所以能自动排序。

参考文献：

updatedupdated2022-07-152022-07-15

相关文章：