时间与时钟

系统里至少有三种不同的时间问题：现在是什么日期，某段操作经过了多久，两个分布式事件是否存在因果关系。它们不能靠同一个裸时间戳解决。

挂钟与单调时钟：日期和耗时分开测量

挂钟用于日志日期、业务日历和跨系统时间标记，通常参考 UTC。它可能因为校时或人工调整发生跳变，所以单机上连续两次 gettimeofday() 也不保证能正确测量经过时间。

在 Linux 上，CLOCK_MONOTONIC 不受挂钟的离散跳变影响，适合测量本机间隔与截止时间，但会受到渐进频率调整影响，且通常不计入系统挂起时间；CLOCK_BOOTTIME 包括挂起时间。选择取决于“超时应否计入休眠”。这些值也不能直接拿来比较不同机器的绝对时刻。Linux clock_gettime 手册

即使本机计时可靠，进程也可能暂停很久后才执行下一条指令。租约“还有 1 秒”不保证进程接下来一定能在 1 秒内完成外部写入。

Happens-before：从程序顺序与消息构造偏序

定义 a→b：同一进程中 a 在 b 之前；或者 a 是消息发送、b 是对应接收；再加上传递关系。若既无 a→b，也无 b→a，就称两者在该模型中并发。

并发不是说两个事件物理上恰好同一纳秒发生，而是当前模型没有建立可用的因果顺序。建模漏掉了一个外部通信渠道，推导出的“无因果关系”也可能与完整系统不同。

Lamport 时钟：因果先后蕴含计数先后

每个进程维护计数 C。本地事件与发送事件递增后取时间戳；接收携带时间戳 m 的消息时，更新为 max(C,m)+1。发送只为该发送事件递增一次，不应在“本地事件”和“发送”两条规则里重复计数。

性质是 a→b ⇒ C(a)<C(b)，反过来不成立。两个没有通信的进程可以分别积累到 100 和 3，100 不表示知道对方的前三个事件，也不代表实际发生得更晚。

把 (C, process_id) 按字典序排序，可以为事件构造与因果方向兼容的全序。这是确定性的排序规则，不是从数字中恢复真实世界唯一的完整先后。Lamport：Time, Clocks, and the Ordering of Events

向量时钟：保留各进程的已知进度

固定 N 个进程时，每个进程 i 保存向量 V。本地事件增加 V[i]；发送携带该事件的向量；接收先逐分量取最大值，再增加自己的分量。

对两个事件向量 v、w，若所有分量 vᵢ≤wᵢ 且至少一个严格小于，则记为 v<w。在完整遵守该事件模型与更新规则时，这对应因果先后。若一些分量大、另一些小，则不可比较。

例如 [2,0] 与 [1,1] 不可比较；[2,0] 与 [3,1] 可比较。不能通过总和、最大分量或字典序检测并发，因为那些做法会丢掉各进程的独立历史信息。

对象版本向量与事件向量时钟关系密切，但计数的对象和因果上下文可能不同。对象存储还要定义生成新版本、合并上下文和保留 siblings 的规则，不能简化成“旧上下文写入必然拒绝”。见冲突解决。

沿两次消息传播，观察已知进度如何增长

令向量分量依次代表 A、B、C。A 的第二个事件 a2 向 B 发消息；B 在 b2 接收，随后在 b3 向 C 发消息，C 在 c2 接收。在这段时间里，A 还发生了未发送出去的本地事件 a3。

c2 的第一个分量为 2，说明它的因果过去覆盖 A 的前两个事件；没有消息把 a3 纳入这条路径。虽然 C(a3)=3 < C(c2)=5，两者仍然并发。比较向量时，a3 的 A 分量更大，c2 的 B、C 分量更大，恰好暴露出这个区别。

下面同时从事件图求祖先集合、按前驱时间戳计算两种时钟，再检查所有事件对。输入按拓扑顺序列出，但列表中先出现不等于存在因果边；只有显式的程序顺序与消息边计入关系。

events = [
    ("a1", 0, ()), ("a2", 0, ("a1",)), ("a3", 0, ("a2",)),
    ("b1", 1, ()), ("b2", 1, ("b1", "a2")), ("b3", 1, ("b2",)),
    ("c1", 2, ()), ("c2", 2, ("c1", "b3")),
]
vectors, lamport, ancestors, last = {}, {}, {}, {}
for name, process, parents in events:
    assert name not in vectors and all(p in vectors for p in parents)
    assert process not in last or last[process] in parents
    vector = [max((vectors[p][i] for p in parents), default=0) for i in range(3)]
    vector[process] += 1
    vectors[name] = tuple(vector)
    lamport[name] = max((lamport[p] for p in parents), default=0) + 1
    ancestors[name] = set(parents)
    for parent in parents:
        ancestors[name].update(ancestors[parent])
    last[process] = name

def vector_before(a, b):
    return all(x <= y for x, y in zip(a, b)) and a != b

for a in vectors:
    for b in vectors:
        causally_before = a in ancestors[b]
        assert vector_before(vectors[a], vectors[b]) == causally_before
        if causally_before:
            assert lamport[a] < lamport[b]
assert vectors["c2"] == (2, 3, 2)
assert lamport["a3"] < lamport["c2"]
assert "a3" not in ancestors["c2"] and "c2" not in ancestors["a3"]

这里只模拟固定三个身份、不会丢失计数状态的进程。重启后把 A 的计数清零、复用旧身份，会破坏“分量代表该身份完整前缀”的解释。动态成员系统需要定义身份世代、状态恢复和元数据回收，不能仅把数组扩展或截断就认为问题已经解决。

消息携带的是发送时的知识

向量里的每个分量都有自己的归属，不能只看总和。最有辨识力的操作是：A 发送后再发生本地事件，然后把先前的消息递送给 B。B 得到的是发送时的快照，A 后来的事件并没有随同过去的消息一起传播。对照两边向量，能直接看出“数值更大”与“知道更多相关历史”的区别。

$$V_j\leftarrow \max (V_j,V_{\mathrm{msg}}),V_j[j]\leftarrow V_j[j]+1$$

逻辑互斥：排序只是协议的一部分

Lamport 的经典互斥算法在可靠 FIFO 通道等假设下使用带时间戳的请求队列。请求者广播 REQUEST；接收者将请求排队并回复；请求者确认自己的请求位于队首且收到其他进程的相应消息后进入临界区；退出时广播 RELEASE，让各队列移除该请求。

这与“按优先级延迟回复、退出后才补发”的其他互斥算法不同，不能把延迟回复规则与 Lamport 的 RELEASE 队列流程随意拼在一起。等待所有成员的方案还需要处理成员故障，否则一个永久不响应的成员就会阻止进展。

物理时间的不确定区间

如果已知事件 A 的真实时间在 [10,12]，事件 B 在 [13,15]，可以判断 A 先于 B；若 B 在 [11,14]，区间重叠，单凭这些边界无法判定。

NTP、PTP 的精度取决于同步源、路径不对称、硬件时间戳、负载和失联时间，没有普遍适用的“固定 1ms”或“固定 100ns”。软件能否给出可靠边界，取决于系统对延迟、振荡器漂移和故障的假设；不能笼统说软件永远无法建立边界。

同步停止后，误差预算不会停在最后一次测量

假设最后一次同步已经给出可靠的 ±2 ms 边界，之后振荡器相对理想时间的最大频率误差为 200 ppm，即每经过 1 秒最多额外积累 0.2 ms 误差。在没有再次校准、没有跳变且这些界限始终成立时，失联 Δt 秒后的保守边界是：

ε(Δt) = 2 ms + 0.2 ms/s × Δt。

因此 30 秒后是 ±8 ms，10 分钟后是 ±122 ms。它们是人为给定假设下的算例，不是 NTP 或任何具体晶振的默认性能。若两台机器各自具有 ±8 ms 误差，仅凭两个时钟相差 10 ms 还不能确定真实先后；两边的不确定性都要计入。

from fractions import Fraction

def error_ms(elapsed_s):
    assert elapsed_s >= 0
    return Fraction(2) + Fraction(200, 1000) * elapsed_s

def definitely_before(a_center, a_error, b_center, b_error):
    return a_center + a_error < b_center - b_error

assert error_ms(30) == 8
assert error_ms(600) == 122
assert not definitely_before(100, 8, 110, 8)  # [92,108] 与 [102,118] 重叠
assert not definitely_before(100, 8, 116, 8)  # 边界接触，仍不能证明严格早于
assert definitely_before(100, 8, 117, 8)

误差上界与时间戳显示精度也不同：打印到纳秒只说明数值格式细，不代表真实时刻误差小。失联、温度变化或同步源异常使原假设失效时，系统应扩大边界或停止依赖该边界作确定性判断，不能继续沿用旧的 ±2 ms。

TrueTime 把时间不确定性显式暴露为 [earliest,latest]。在其保证成立的条件下，系统通过等待 earliest 越过提交时间戳，使提交的实时顺序满足目标事务语义。等待与复制、事务并发控制共同作用，不是原子钟单独解决所有一致性问题。Spanner 与 TrueTime

跨地域本身不是“比线性一致性更强”的定义。Spanner 的外部一致性通常在事务层面讨论实时串行顺序；比较保证时应保持对象与事务的作用域一致。

混合逻辑时钟与选择速查

混合逻辑时钟 HLC 结合接近物理时间的分量与逻辑计数，帮助在保留因果方向的同时使时间戳易于与物理时间关联。它不自动提供全局真实时间的严格误差边界，也不替代共识或事务隔离。

参考

• Lamport 1978 论文。
• Linux clock_gettime。
• Spanner：TrueTime 与外部一致性。

Keywords: wall clock, monotonic clock, Lamport clock, vector clock, happens-before, TrueTime, HLC