逻辑时钟：Lamport 时钟与向量时钟

本文基于模型知识整理（生成时未联网核对），关键结论建议对照经典文献复核。

一句话定义

逻辑时钟放弃"物理几点"的度量，改用消息传递关系定义事件先后：Lamport 时钟用一个单调递增整数给出满足因果的全序（可能把并发排错序），向量时钟用每节点一个计数器精确区分"先后"与"并发"。

为什么重要

事件排序是分布式正确性的根基：检测并发写冲突、判定因果依赖、实现因果一致性都依赖它。物理时钟不可信（kp-003），逻辑时钟提供了仅凭通信本身就能判定因果的机制——这是 Lamport 1978 年论文确立的范式转变，也是后来一切一致性理论的基石。

前置知识

kp-003（物理时钟不可信）；kp-001（消息传递模型）。

核心概念

• happens-before（→）：事件 a → b 当且仅当 a 与 b 在同一节点上先后发生，或 a 是某消息的发送、b 是该消息的接收（传递闭包）。不满足 a→b 也不满足 b→a 的两个事件互为并发。
• Lamport 时钟：每节点维护计数器 C；本地事件 C←C+1；发消息附带 C；收消息时 C←max(C本地, C消息)+1。保证：a→b ⇒ C(a)<C(b)。
• 向量时钟：每节点维护长度为 n 的向量 V，分量记录"该节点已看到的事件数"；本地/发送/接收规则与 Lamport 类似（接收时逐分量取 max）。比较规则：V(a) ≤ V(b)（所有分量）⇔ a→b；不可比 ⇔ 并发。

原理与机制

Lamport 时钟的局限：只有单向蕴含。C(a)<C(b) 推不出 a→b——两个并发事件可能拿到递增的编号，系统会为并发事件强行指定一个全序。适合"需要一个与因果一致的全序"的场景（如全序广播的思想源头）。

向量时钟的优势与代价：双向可判定——能精确回答"这两个事件是否并发"。代价是空间 O(n)（n 为节点数），节点多时元数据膨胀；Dynamo 类系统通常只保留有限长度并定期截断（见 kp-015 版本向量实践）。

公式或模型

• Lamport 更新：C_i ← C_i + 1（本地）；C_i ← max(C_i, C_m) + 1（收到消息 m）。
• 向量比较：a → b ⇔ V_a ≤ V_b 且 V_a ≠ V_b；a ∥ b ⇔ 存在分量 i: V_a[i] > V_b[i] 且存在分量 j: V_a[j] < V_b[j]。

直观类比

Lamport 时钟像"队列取号"：号码只保证后取的号更大，但两个不同窗口的号谁先谁后说不清（并发被强行定序）。向量时钟像"每人一张进度表"：对表时逐项比较，凡是互有领先的，就是真正的并行——谁也不包含谁。

实例或案例

• Amazon Dynamo：用（截断的）向量时钟识别并发写，检测到并发则保留多版本交由客户端/应用合并（见 kp-015）。
• Riak：同源思想，称之为 vclock；曾在文档中详细记录其截断与"sibling"机制。
• 因果一致性存储：COPS、Orbe 等系统直接以向量时钟追踪因果依赖来保证"先读后写"跨地域可见。

常见误区

• 误区一："C(a)<C(b) 说明 a 先发生"。只对 Lamport 时钟的反方向成立：a→b 保证编号小，编号小不保证先发生（可能是并发的定序产物）。
• 误区二："向量时钟是 Lamport 时钟的简单升级，免费获得"。它把判定能力换成了 O(n) 空间与合并开销，且节点成员变化时向量维度管理复杂。
• 误区三：把逻辑时钟当成可以"测时长"的工具。逻辑时钟只承载顺序信息，与真实耗时无关。

与其他知识点的关系

• kp-013：因果一致性、顺序一致性的定义直接建立在 happens-before 上。
• kp-015：版本向量/CRDT 的冲突检测使用向量时钟思想。
• kp-017：共识可以理解为"让全体节点就同一个 Lamport 式全序达成一致"。

自测题

1. Lamport 时钟保证什么、不保证什么？

答：保证 a→b ⇒ C(a)<C(b)；不保证 C(a)<C(b) ⇒ a→b（并发事件可能被任意定序）。

1. 两个事件的向量时钟互有分量领先，说明什么？

答：说明二者并发——谁也不因果依赖于谁，系统无法也不应强行排序。

1. 为什么向量时钟在超大规模集群中不直接可用？

答：向量长度随节点数线性增长，元数据与合并开销大；实践中要截断历史、只维护活跃子集，或改用更粗的因果追踪机制。

延伸阅读

• Leslie Lamport, "Time, Clocks, and the Ordering of Events in a Distributed System"（CACM 1978）。
• Colin Fidge / Friedemann Mattern 关于向量时钟的原始论文（1988）。
• Martin Kleppmann《DDIA》第 9 章关于 happens-before 的推导。