时间、时钟与因果序

2.1物理时钟为什么不能用来排序

服务器的 wall-clock 会漂移、会被 NTP 回拨、会因闰秒跳变，跨节点几十毫秒偏差是常态。

石英振荡器的频率误差约为 ±200 ppm，最坏情况下每天累积 17 秒偏差。NTP 修正这一偏差时有两种模式：slew（缓慢拉近，速率上限约 500 ppm）和 step（直接跳变）。step 向后跳时，同一进程内 end − start < 0 成立——时间倒流。闰秒（leap second）未被操作系统平滑时，秒计数会出现"23:59:60"或重复"23:59:59"，导致整秒级跳变。

在 LWW（Last-Write-Wins）语义下，时钟快的节点会静默胜出：它的写入时间戳更大，即便那次写入在因果上更早。时钟慢节点的写入被丢弃，没有任何报错。

2.2happens-before：唯一客观的顺序

a→b 当且仅当：a、b 同进程且 a 在前；或 b 收到了 a 发出的消息；或上述的传递闭包；否则 a、b 并发。

Lamport 1978 年给出的定义：关系 →（happens-before）是满足以下三条规则的最小关系：

1. 若 a 和 b 在同一进程，且 a 在 b 之前执行，则 a → b。
2. 若 a 是某条消息的发送事件，b 是该消息的接收事件，则 a → b。
3. 传递性：若 a → b 且 b → c，则 a → c。

当 a → b 和 b → a 均不成立时，a 与 b 并发（concurrent）。并发不是"同时"，而是"没有因果路径"——系统中没有任何机制能区分它们的先后。

因果序是偏序（partial order），不是全序。两个没有因果路径的事件，客观上没有先后，任何强加的顺序都是人为的选择，而非观察到的事实。这一点是理解本章所有后续机制的基础。

2.3Lamport 逻辑时钟

每进程一个整数计数器：本地事件 +1、发送带上当前值、接收取 max(本地, 收到)+1。

Lamport 时钟的更新规则（Clock Condition）：

• 进程 P 执行本地事件：L_P ← L_P + 1
• 进程 P 发送消息：带上 L_P，发出前执行上条规则
• 进程 P 接收消息（携带时间戳 m）：L_P ← max(L_P, m) + 1

这套规则保证：若 a → b，则 C(a) < C(b)。但反过来不成立：C(a) < C(b) 不能推出 a → b。原因是 max 操作会把并发事件的计数器"对齐"，两个完全无关的事件也会被赋予不同的 Lamport 值，看起来像有顺序，其实是人为的。

并发性在 Lamport 时间戳里不可见：工具提供了一个全序（通过打破平局）但丢失了"哪些事件其实并发"这个信息。

走查示例：进程 P1 和 P2 各自从 L=0 出发。P1 执行事件 a（L_P1=1），发出消息（带 L=1）给 P2；P2 接收后 L_P2 = max(0,1)+1 = 2，执行事件 d；P2 再执行事件 e（L_P2=3）；与此同时 P1 继续执行 b（L_P1=2）。此时 L(e)=3，L(b)=2，但 e 和 b 是并发事件——Lamport 给了它们不同的值，却无法告知这一点。

2.4向量时钟：看见并发

每节点维护长度 N 的计数器数组，只增自己那一格；两事件的向量谁分量全 ≥ 谁就是因果在后，互不支配则并发。

向量时钟 VC 是一个长度为 N 的整数数组（N = 节点数）。更新规则：

• 节点 P_i 执行本地事件：VC[i] ← VC[i] + 1
• 节点 P_i 发送消息：将当前 VC 附在消息上
• 节点 P_i 接收消息（携带向量 m_VC）：逐分量取 max，再自增本格：VC[j] ← max(VC[j], m_VC[j]) for all j，然后 VC[i] ← VC[i] + 1

比较规则：向量 A 支配向量 B（即 A 因果晚于 B），当且仅当 A 的每个分量都 ≥ B 对应分量，且至少一个 >。若 A 不支配 B 且 B 不支配 A，则两事件并发。

代价：每条消息要携带 O(N) 的数组。5000 节点的集群里，每个事件的向量时钟就是 5000 个整数。Amazon Dynamo 在商品推荐系统（购物车服务）中使用向量时钟，但向量过长时对其剪枝（按时间戳删除最老的条目），牺牲精确性换可用性——剪枝后会把并发误判为有序。

购物车示例：用户在客户端 A 加入商品 X，在客户端 B 加入商品 Y，两个写入并发发到服务器。若用 LWW，某一个写会被静默丢弃。向量时钟检测到两个版本并发（向量互不支配），将冲突交给应用层合并——购物车包含 X 和 Y，没有数据丢失。

2.5HLC 混合逻辑时钟

64 位时间戳 = 物理毫秒 l + 逻辑计数 c，同毫秒内的因果事件靠 c 区分，且 l 永不回拨。

HLC 由一对 (l, c) 组成，l 是毫秒级物理时间，c 是同一毫秒内的计数器。更新算法：

// 本地事件或发送消息前：
pt = 当前物理时间（毫秒）
l' = max(l, pt)
if l' == l:
    c = c + 1
else:
    l = l'
    c = 0

// 接收消息（携带 lm, cm）：
pt = 当前物理时间（毫秒）
l' = max(l, lm, pt)
if l' == l == lm:
    c = max(c, cm) + 1
elif l' == l:
    c = c + 1
elif l' == lm:
    c = cm + 1
else:
    c = 0
l = l'

关键性质：l 始终 ≥ 物理时间，且偏差有界——l 不会超过各节点物理时钟最大值加上最大时钟偏差 ε。因此在小偏差条件下，按 HLC 排序与按物理时间排序近似等价；同毫秒内回退到逻辑计数器 c 保持因果序；l 永不回拨，消除了 NTP step 向后的问题。

HLC 的物理时间部分不需要全序——它只需要是"偏差有界的物理时钟"，用 GPS 接收器或原子钟硬件（如 Google Spanner 的 TrueTime）能把 ε 压到微秒级，但普通 NTP 同步的数据中心（ε ≈ 10 ms）也够用。

2.6三种时钟机制对比

物理时钟、Lamport 时钟、向量时钟、HLC 各有适用边界——没有一种工具全能。