向量时钟

概述

向量时钟（Vector Clock）是 Colin Fidge 和 Friedemann Mattern 于1988年独立发明的机制，解决了 Lamport 逻辑时钟不能完整捕获因果信息的局限。

关键内容

Lamport 时钟的局限

Lamport 时钟满足：a --> b 则 C(a) < C(b)。但逆命题不成立——C(a) < C(b) 不意味着 a --> b。两个并发事件也可能碰巧得到这样的时间戳。

向量时钟的改进

每个进程维护一个 N 维向量（N 为进程数），而非单个整数。向量时钟满足：

a --> b 当且仅当 VC(a) < VC(b)

实现了因果关系的完整捕获——既是必要条件，也是充分条件。

代价

• 空间开销：每个时间戳是 N 维向量，而非单个整数
• 在大规模系统中（数千个进程），向量可能变得很大

应用

• Amazon DynamoDB 使用向量时钟实现最终一致性
• 分布式调试和因果追踪
• CRDT 的冲突检测

来源

• raw/books/计算机科学/13-lamport-time-clocks.md

相关

• 逻辑时钟 — 被改进的对象
• happened-before 关系 — 完整实现
• 分布式系统 — 应用领域
• Lamport 逻辑时钟论文 — 启发的来源
• 分布式互斥算法 — 相关应用