#distributed-systems #基础理论
本页目录

时间与时钟

分布式系统没有全局时钟——两个节点上的时间戳不能直接比大小。从 Lamport 逻辑时钟(happens-before)到向量时钟(并发检测)到 TrueTime(GPS+原子钟),每一种"时钟"都在不同的代价点上逼近"事件先后"这个看似简单的问题。

问题: 没有全局时钟

单机上 gettimeofday() 可以比较两个事件 A 和 B 的先后。但在分布式系统中，A 在节点 1 上 12:00:00.000 发生，B 在节点 2 上 12:00:00.001 发生——你能确定 A 在前吗？不能，因为两个节点的时钟不可能完美同步。NTP 同步精度 ~1ms，意味着 1ms 内的事件顺序无法通过物理时间判断。

Lamport 逻辑时钟 (1978)

Leslie Lamport 的洞见：我们不需要物理时间来判断因果关系——只需要保证 happens-before 关系在时间戳中反映出来⁠。

算法

每个节点维护一个整数 counter C，初始为 0：

  1. 本地事件发生（包括发送消息）：C = C + 1，事件的时间戳 = C
  2. 发送消息时，附上本节点的当前 C
  3. 收到消息（时间戳 = C_msg）：C = max(C, C_msg) + 1，接收事件的时间戳 = C

性质：⁠如果 a happens-before b，则 C(a) < C(b)。但反过来不成立——C(a) < C(b) 不意味着 a → b（可能是并发事件恰好有不同 counter 值）。

分布式互斥算法 (Lamport Mutex)

用逻辑时钟实现无中心节点的互斥：

  1. 节点 i 要进入临界区：发 REQUEST(ts_i, i) 给所有节点
  2. 收到请求的节点 j：如果不在临界区也不打算进入，回复 REPLY 如果在临界区或不打算者且自己的请求优先级更高(ts_j < ts_i) → 延迟回复
  3. 节点 i 收到所有 REPLY 后 → 进入临界区
  4. 退出临界区 → 发 RELEASE 给所有节点

优点：无单点故障，完全分布式。缺点：3(N-1) 条消息，单节点故障会阻塞整个系统。

向量时钟

Lamport 时钟的局限：C(a) < C(b) 不能反推 a → b。向量时钟解决了这个问题。

数据结构

每个节点维护长度为 N 的向量 V[1..N]，V[i] = 该节点已知的节点 i 发生了多少事件。

V_a = [3, 5, 2]  表示: 节点 1 知道: 本节点 3 个事件, 节点 2 做了 5 个, 节点 3 做了 2 个

算法

  1. 本节点 i 上发生事件：V[i] = V[i] + 1
  2. 发送消息时，附上当前 V
  3. 收到消息（附带 V_msg）：V[k] = max(V[k], V_msg[k]) for all k，然后 V[i] = V[i] + 1

比较规则

  • V(a) < V(b) (a happens-before b): V(a) 的每个元素 ≤ V(b) 的对应元素，且至少一个严格小于
  • V(a) 与 V(b) 无法比较：存在 k,j 使得 V(a)[k] < V(b)[k] 且 V(a)[j] > V(b)[j] → 并发事件

实践应用

Dynamo/Riak KV 用向量时钟检测冲突：当 get(key) 返回 vector clock V_old，client 修改后 put(key, value, V_old)。如果 server 上的当前版本是 V_cur，比较 V_cur 与 V_old：

  • V_cur < V_old: 直接覆盖（client 看到了当前版本后修改的）
  • V_cur > V_old: 拒绝（client 基于过时版本修改）→ 需要 read-modify-write
  • 无法比较: 并发修改 → 需要冲突解决（应用层 merge 或保留多个版本 sibling）

Google TrueTime (Spanner)

最极端的工业实践：用原子钟 + GPS 为全球数据中心提供有界的时钟不确定区间。

TT.now() 返回区间 [earliest, latest]

保证：真实时间一定落在这个区间内。区间宽度通常 ~1-7ms（取决于 GPS/原子钟同步状态）。

Spanner 的 External Consistency

Spanner 的事务用 TrueTime 保证最强的外部一致性（比 linearizability 还强——跨数据中心的实时顺序）：

commit wait: 事务的 commit timestamp = TT.now().latest
              事务在 replica 上生效前, 等 TT.after(commit_ts) = True
              → 保证所有节点看到的 commit 顺序与真实时间一致

为什么需要硬件

软件不可能提供有界误差的时钟——NTP 只能估计误差，但网络延迟的非对称性和抖动使误差边界不可知。TrueTime 的保证来自于 GPS/原子钟的物理特性：原子钟的频率误差 < 10^-13。

NTP/PTP 实践

NTP (Network Time Protocol): 通过 UDP 包交换估算与 server 的时间偏差。精度 ~1ms (LAN)，~10ms (WAN)。问题：

  • 跳变⁠: NTP 突然修正大偏差 → 时钟往回跳 → CLOCK_MONOTONIC 暴露这个跳变，但挂钟时间倒流
  • 震荡⁠: NTP 在持续修正 → 时钟频率持续微小变化 → 依赖单调时间的 Prometheus TSDB 可能受影响（但 Prometheus 用 CLOCK_MONOTONIC 做 scrape timing）
  • 同步失败⁠: NTP server 不可达 → 时钟漂移累积 → 几小时/几天后误差可到秒级

PTP (Precision Time Protocol, IEEE 1588): 数据中心级时间同步，精度 ~100ns。需要硬件支持（网卡 timestamping）。用于金融交易（MiFID II compliance）和 Spanner 的备选 clock source。

参考

  • 论文⁠: "Time, Clocks, and the Ordering of Events in a Distributed System" (Lamport, 1978)
  • 论文⁠: "Spanner: Google's Globally-Distributed Database" (2012, TrueTime section)
  • 论文⁠: "Virtual Time and Global States of Distributed Systems" (Mattern, 1989 — 向量时钟)

Keywords: Lamport clock, vector clock, happens-before, TrueTime, Spanner, NTP, PTP, logical time

相关页面

© 2026 liz's doc