分布式算法 #04：向量时钟与因果一致性

分布式系统中没有全局时钟，节点间的事件顺序无法用物理时间判断。本文从 Lamport 时钟出发，推导向量时钟与版本向量，深入分析乱序消息、并发写冲突、网络分区恢复时的合并策略，以及与 HLC 的关系。

相关文章：Raft 共识算法 · CRDT（无冲突复制数据类型） · Hybrid Logical Clock（HLC）

目录

为什么物理时钟不够用

场景：两台服务器 A（时钟 10:00:00.100）和 B（时钟 10:00:00.050）

A 在 T=100ms 写入 key=X, value=1
B 在 T=80ms（但物理时间晚）写入 key=X, value=2

如果按物理时间排序：
  B 的写入（T=80）"先于" A 的写入（T=100）
  最终值 = A 的 value=1（后写覆盖）

但实际业务语义：
  B 的写入是在看到 A 写入之后发生的（因果上 A → B）
  按因果顺序，B 的 value=2 应该覆盖 A 的 value=1

物理时钟无法表达这种因果关系！

时钟偏差的现实：

NTP 同步误差：10ms ~ 100ms（网络环境差时更大）
石英晶体漂移：每天 ±1s
GPS 同步：<1μs（昂贵，需硬件支持）

即使使用 GPS 时钟，跨机房的网络延迟也会使"同时"变得模糊

Lamport 时钟

核心规则

每个节点维护一个整数计数器 LC，初始为 0

规则 1（本地事件）：
  执行本地操作前：LC += 1

规则 2（发送消息）：
  LC += 1
  消息携带当前 LC

规则 3（接收消息）：
  LC = max(LC, msg.LC) + 1
  // 确保接收事件的时间戳大于发送事件

因果关系（happens-before，→）

a → b 当且仅当以下任一：
  1. a 和 b 在同一节点，a 先于 b 发生
  2. a 是发送消息的事件，b 是接收该消息的事件
  3. 存在 c 使得 a → c 且 c → b（传递性）

Lamport 时钟保证：
  if a → b, then LC(a) < LC(b)

但反过来不成立：
  LC(a) < LC(b) 不意味着 a → b
  可能是并发事件（a 和 b 互不影响）

Lamport 时钟的局限：

节点 A: LC=1(写X)  LC=3(读Y)
节点 B: LC=2(写Y)  LC=4(读X)

LC(A.写X)=1 < LC(B.读X)=4，但 A.写X 和 B.读X 是并发的
无法区分"因果先后"和"并发"

向量时钟

数据结构与规则

每个节点 i 维护向量 VC[1..N]，初始全为 0
VC[j] 表示节点 i 知道的节点 j 已发生的事件数

规则 1（本地事件）：
  VC[i] += 1

规则 2（发送消息）：
  VC[i] += 1
  消息携带当前 VC（完整向量）

规则 3（接收消息）：
  for j in 1..N:
    VC[j] = max(VC[j], msg.VC[j])
  VC[i] += 1

因果关系的精确判断

向量时钟的比较：
  VC_a < VC_b（a 因果先于 b）：
    所有维度 VC_a[j] <= VC_b[j]，且至少一个维度严格 <

  VC_a == VC_b（完全相同）：
    所有维度相等（同一事件）

  VC_a || VC_b（并发，无因果关系）：
    既不是 VC_a < VC_b，也不是 VC_b < VC_a
    即存在 i,j 使得 VC_a[i] > VC_b[i] 且 VC_a[j] < VC_b[j]

具体示例：

三节点集群 {A, B, C}，初始 VC=[0,0,0]

A 写 X：
  A.VC = [1,0,0]，事件 a1

A 发消息给 B：
  消息携带 [1,0,0]

B 收到消息，写 Y：
  B.VC = max([0,0,0],[1,0,0]) + B自增 = [1,1,0]，事件 b1
  因果关系：a1 → b1（因为 [1,0,0] < [1,1,0]）✅

C 独立写 Z：
  C.VC = [0,0,1]，事件 c1
  a1 和 c1 并发？[1,0,0] vs [0,0,1]
  A维度：1 > 0，C维度：0 < 1 → 并发 ✅

B 发消息给 C：
  消息携带 [1,1,0]

C 收到消息：
  C.VC = max([0,0,1],[1,1,0]) + C自增 = [1,1,2]，事件 c2
  因果关系：b1 → c2（[1,1,0] < [1,1,2]）✅
  因果关系：a1 → c2（[1,0,0] < [1,1,2]）✅
  因果关系：c1 → c2（[0,0,1] < [1,1,2]）✅

版本向量

向量时钟用于追踪事件顺序，版本向量（Version Vector） 用于追踪数据对象的版本和冲突。

每个数据对象关联一个版本向量 VV，记录各副本的写入次数

副本 R_i 写入 key=X 时：
  VV_X[i] += 1
  保存 (value, VV_X)

读取 key=X，合并多个副本的版本：
  VV_a < VV_b → 使用 b（因果后续，a 是旧版本）
  VV_a || VV_b → 冲突！需要合并策略

示例：购物车冲突（Amazon Dynamo 真实场景）：

初始：cart={book}, VV=[0,0]

客户端 1（副本 A）：
  添加 phone：cart={book,phone}, VV=[1,0]

网络分区期间，客户端 2（副本 B）：
  添加 laptop：cart={book,laptop}, VV=[0,1]

分区恢复后，读取请求到达：
  副本 A 返回：(cart={book,phone}, VV=[1,0])
  副本 B 返回：(cart={book,laptop}, VV=[0,1])

  [1,0] vs [0,1]：并发冲突！
  合并策略（业务决定）：取并集 = {book,phone,laptop}
  新版本：VV=[1,1]

异常场景分析

异常 1：消息乱序

场景：
  节点 A 发送两条消息（因果相关）：
    消息1：VC=[1,0,0]，"用户注册"
    消息2：VC=[2,0,0]，"发送欢迎邮件"（因果上依赖消息1）

  节点 B 先收到消息2，后收到消息1

问题：B 先处理"发送欢迎邮件"，但此时"用户注册"还未处理
      → 用户不存在，发送失败

解决：因果消息传递（Causal Message Delivery）
  B 维护一个"等待队列"
  收到消息 m 时：
    检查所有 m 依赖的消息（VC 中标记的前因）是否已处理
    if 所有前因已处理:
      立即处理 m
    else:
      放入等待队列，等前因消息到达后再处理

  具体检查：
    m.VC[j] <= B已处理的VC[j]，对所有 j != sender
    m.VC[sender] = B已处理的VC[sender] + 1（严格连续）

异常 2：并发写导致冲突

场景：两个客户端同时修改同一个 key

客户端 C1 读取 x=1，VV=[2,0]
客户端 C2 读取 x=1，VV=[2,0]

C1 写入 x=2，副本 A 更新：VV=[3,0]
C2 写入 x=3，副本 B 更新：VV=[2,1]

后续读取时，合并副本 A 和 B：
  A: (x=2, VV=[3,0])
  B: (x=3, VV=[2,1])
  [3,0] vs [2,1]：并发冲突！

冲突解决策略（见下节）

异常 3：网络分区后版本向量爆炸

问题：每个写操作的 VV 都包含所有副本 ID，副本数多时 VV 很大
     频繁的客户端写入会产生大量 VV 条目

解决方案（Riak 的做法）：
  1. 使用 Server-side Vector Clock（服务端维护，客户端只传 context token）
  2. 定期 GC：去掉超过一定时间没有更新的条目
  3. 截断：只保留最近 N 个条目（牺牲部分精度）
  4. Dotted Version Vectors（DVV）：更紧凑的数据结构，避免 VV 膨胀

异常 4：节点 ID 变化（节点重启/替换）

问题：节点 N1 宕机后，新节点 N1' 使用不同 ID 加入集群
     VV 中 N1 的条目永远不会更新（N1 死亡）

解决方案：
  1. 使用持久化 Node ID（UUID 存磁盘，重启复用）
  2. 逻辑节点 ID 而非物理机 ID（与 IP 解耦）
  3. 旧节点 ID 的 VV 条目在 GC 时清理

冲突解决策略

实际应用

参考资料

• Lamport, L. (1978). Time, Clocks, and the Ordering of Events in a Distributed System
• DeCandia, G. et al. (2007). Dynamo: Amazon's Highly Available Key-value Store
• 《Designing Data-Intensive Applications》Ch.8 — Ordering Guarantees
• Preguiça, N. (2010). A commutative replicated data type for cooperative editing