分布式系统 • 时钟

为什么在分布式系统中时钟很重要

最简单的一个例子：一个读请求和一个修改请求（在外界观察者眼中）先后来到一个系统中的两个不同的节点上（假设所有节点的存储是通过某些“魔法”手段连在一起的），按道理由于读请求先发生，那么他不应当读到写请求写入的数据。但是如果两个节点上的物理时钟出了问题，处理读请求的时钟快了（认为请求到来时的时间戳比较大），而处理写请求的时钟慢了（认为请求到来时的时间戳比较小），此时按照时钟判断出的读写顺序就和实际不同了，这就会带来读写操作进行的顺序和预期不符。

即使是同一个节点上也会遇到时钟由于走的太快而被 NTP 这样的时间同步算法回拨，导致的时间戳不唯一的问题。

可见分布式系统中直接根据物理时钟决定事件发生的先后顺序是不可行的，原因是不同系统中的物理时钟其快慢是无法保证的。

而目前最好的时间校准算法 NTP 也无法很好的保证精度，网络这个东西实在是太不可靠了……

TSO

实际上我们可以确定的一种顺序就是同一节点上事件发生的顺序：

公理1：在同一节点上有序的两个事件在外界观察者眼中也有序

那么很简单的一个想法就是：在每次有请求来到系统时，都要经过一个负责分配单调递增的时间戳的节点，给这个请求分配时间戳

但是这样系统里面就出现了这么一个不能扩展的单点，而且这个节点理论上不能宕掉，否则就算是切换新的时间戳分配节点，这个新旧节点之间的时间戳的差异也会造成问题，至少也会引起一个等于“节点之间最大可能物理时间的差距”（通过物理时钟分配时间戳）或者“一个从某种持久化存储中读取数据”（使用累加计数器分配时间戳）的延迟。

通信和逻辑时钟

（两个节点之间的）通信必定有一个发送事件和一个接收事件，分别发生在两个节点上，而无论在任何观察者眼中发送一定先于接收，所以我们可以通过通信来确定一些事件的先后¹：

公理2：对于某个通信，在外界观察者眼中发送先于接收

结合公理1和公理2，有：

定理1：对于某个通信，"通信发送之前发生的事件"在外界观察者眼中发生在"通信接收之后发生的事件"之后

根据这一定理，我们可以通过这个逻辑时间戳建立事件间关于“happens before”的偏序关系，即我们可以比较一部分事件的先后关系。

由此 Lamport 创造了 Lamport 逻辑时钟算法：

• 每个节点初始时间戳都为0
• 每次发生消息交换之外的事件时，本地时间戳 +1
• 每次发送消息，本地时间戳+1，并带在消息里
• 每次接收消息，如果消息中的时间戳比本地时间大，那么本地时间戳 = 消息时间戳 + 1，否则正常本地时间戳 + 1‘

即每次发生事件，都保证 本地时间戳 = 节点看到过的最大时间戳 + 1

保证了什么

Lamport逻辑时钟保证了：

• 若系统外部观察者看到事件A在事件B前发生，则系统内部必有 事件A对应的时间戳<事件B对应的时间戳。

但反之则不一定成立，即时间戳的大小并不能决定事件的发生顺序。

全序化改进

可以暴力地给每个节点一个编号，把时间戳的定义改为 concat(原本的时间戳, 节点编号)，这样人为地通过时间戳之间的全序关系为事件定出一个全序关系。

虽然这个全序关系和事件在外界观察者眼中的顺序并没有绝对的关系，但是方便了我们进行一些应用。

应用：Lamport 锁

Lamport锁是一个经典的分布式锁算法，理论上可以在分布式系统中保证某一个资源同一时间只有一个访问者。

算法如下：

• 每个节点维护一个等锁队列

• 当一个节点想要锁上一个资源供自己访问时，发送一个请求锁的消息给所有节点，eg：

  Node A 想要锁上这个资源
  —— 发送于 时间戳 T
  

  并将这个请求消息放入自己的存储中

• 收到消息后，发送一个确认消息，eg：

  Node B 已收到 Node A 的请求
  —— 发送于 时间戳 T'
  

  由 Lamport 逻辑时钟算法，T' > T

  并将这个请求消息放入自己的存储中

• 如果某个节点

  • 存储里的所有消息中，来自自己的请求的时间戳是最小的
  • 从所有其他节点都收到过，时间戳大于上面说的这个请求的时间戳的消息

  那么它可以认为自己获取到了这个资源上的锁。

• 当节点用完资源准备释放时，删除自己的储存中所有来自自身的请求消息，然后发送删除自己的锁请求的消息：

  Node A 释放了这个资源
  —— 发送于时间戳 XXX
  

  其他节点收到后也从自己的存储中删掉所有来自这一节点的请求消息

以上就是 Lamport 锁算法。

TLA+ Proof

TODO

缺陷

Lamport 锁并没有任何容错机制，无论是网络不通还是节点挂掉，他一概防不出去。

向量时钟

向量时钟是对 Lamport 逻辑时钟的一种改进，Lamport 逻辑时钟里面拿到的时间戳……并没有什么卵用，因为凭时间戳的大小并不能确定其他节点上事件的发生顺序，这一情况的根本原因是这里的时间戳只能指示当前节点对自身事件推进的认识，而正如我们前面所述，同一节点上的时间戳可以确定出顺序，那么我们是不是能让每个节点上都有所有节点的时间信息？

这就是向量时钟的想法：

• 将原本 Lamport 时钟中每个节点上一个的时间戳改成 为每个节点（包括自己）都设立一个时间戳，这构成了一个时间戳向量
• 发生事件时更新（+1）时间戳向量中自己对应的那个元素
• 在发送消息时，发送整个时间戳向量
• 接收消息时，根据发来的时间戳向量更新自己的时间戳向量（对向量中的每个元素应用 Lamport 时间戳的更新算法）

使用向量时钟，我们可以确定部分事件的先后关系：

假设事件 x、y 分别发生在节点 A、B 上：

• 若事件x发生时的时间戳向量（自然是从 A 上取得）中，每个元素全部都小于等于事件 y发生时的时间戳向量的对应元素（从 B 上取得），则 x 早于 y 发生，反之亦然
• 若两个时间戳向量中的各个元素大小关系各有不同，则不能比较出其发生的先后，可以认为这两个事件是并发发生的。

这样，我们可以通过时间戳向量确定很大一部分事件的先后关系。

Hybrid Logical Clocks (HLC)

向量时钟这样的逻辑时钟虽然让我们能确定一部分事件的先后关系，但是其问题在于只在系统内部有用，而对于系统外部的时间一无所知。这在我们想要知道外部事件的先后顺序或者根据物理时间查询事件时非常不利，而物理时钟又是那么的不可靠。

于是就有了混合时钟这种试图把物理和逻辑时钟结合起来的方案。

实现

容易想到的方法是，每次发送和接收消息时，都在Lamport时间戳的基础上，再多做一个和物理时钟做max的操作，即：

• 发送消息前或者本地发生新的事件，时间戳 = max(时间戳+1, 物理时钟)
• 接收到消息后，时间戳 = max(本地时间戳+1, 消息时间戳+1, 物理时钟)

问题在于这样搞时间戳是可以比物理时间无限制地快下去的，例如所有请求都从某个节点非常快地进入系统，并广播到其他节点，其他节点也对每个事件发送了回复，那就会造成时间戳不断+1，导致时间戳远比物理时间大，此时时间戳相当于退化成了普通的逻辑时钟，让我们失去了对物理时间的感知。

我们可以看出这一实现主要的问题在于大量时间可能会造成时间戳过快的增长而物理时钟赶不上的问题，那我们能不能记录一下物理时钟落后了多少来修正这个问题呢？

这就是 HLC 算法的想法：

• HLC 时间戳分为两个部分，“物理”部分（常实现为一个变量的高位）和“逻辑”部分（常实现为一个变量的低位）
• 发送消息前或者本地发生事件
  • 若 HLC 时间戳“物理”部分小于现在的物理时钟，证明物理时钟已经赶上了事件发生的速度，此时只需把“物理”部分更新为新的物理时间戳，并将“逻辑”部分清0即可
  • 若 HLC 时间戳“物理”部分大于（物理时钟被回拨时会发生大于的情况）等于现在的物理时钟，证明物理时钟没有赶上了事件发生的速度，此时只需向“逻辑”部分加一即可
• 收到消息后：
  • 比较 本地 HLC 时间戳“物理”部分、消息 HLC 时间戳“物理”部分、本地物理时间戳 三者
    • 本地 HLC 时间戳“物理”部分和消息“物理”部分相等，同大于本地物理时间戳，证明本地物理时钟既没有赶上本地事件发生的速度，也没有赶上消息发送方上事件发生的速度，那么本地“逻辑”部分的值就可以更新为 max(本地“逻辑”部分, 消息“逻辑”部分) + 1
    • 本地 HLC 时间戳“物理”部分 是其中最大的，说明消息发送方的物理时钟落后于本地物理时钟，但由于 本地物理时间戳 仍然小于 本地 HLC 时间戳的“物理”部分 说明本地物理时间戳没有赶上事件发生的速度，需要向“逻辑”部分加一
    • 消息的 HLC 时间戳“物理”部分 是其中最大的（无论他与本地物理时间戳是否相等），说明本地 HLC 时钟完全落后于消息发送方，那么本地的时间戳就需要直接更新为消息的 HLC 时间戳再在“逻辑”部分加一的结果
    • 本地物理时间戳 是其中最大的，证明物理时钟已经赶上了本地和发送方事件发生的速度，此时只需把“物理”部分更新为新的物理时间戳，并将“逻辑”部分清0即可

简单的思考就是：

1. 为防止在物理时钟 回拨 或者 精度不足以区别事件先后 时物理时钟无法确定本地事件顺序的问题，增设了一个“逻辑”部分，用来
   • 在时钟回拨时让 HLC 时间戳“物理”部分不跟着回拨，而是通过这个逻辑部分确定先后，从而保证时钟的单调性
   • 在物理时钟精度不足时使用逻辑部分确定先后
   • 如果物理时钟比 HLC 时钟“走得快”，就相信物理时钟
2. 通信后，保证自己的 HLC 时间戳不比消息的 HLC 时间戳早

保证了什么

1. 对任何事件x和y，若x发生在y之前，则 x对应的 HLC 时间戳 < y 对应的 HLC 时间戳
2. HLC 时间戳对应的物理时间和节点实际的物理时间的差有确定的上限，这个上限基本上是 两倍的机器的时间和ntp server时间存在的 误差范围（ntp offset），平时这个 offset 一般都是几个 ms。

TLA+ Proof

TODO