向量时钟 (Vector Clocks)

引言：“时间”的问题

在单台计算机上，我们只有一个时钟。如果事件 A 发生在 10:00:01，事件 B 发生在 10:00:02，我们知道 A 先于 B。

但在 分布式系统 中，服务器的时钟 永远无法完全同步。如果服务器 1 认为现在是 10:00，而服务器 2 认为是 09:59，时间感就错乱了。如果两个人在不同的服务器上编辑同一个文档，我们怎么知道谁先谁后？还是他们是同时编辑的？

向量时钟 提供了一种在不需要中央时钟的情况下，追蹤 因果关系 (Causality) 的方法。

算法要解决什么问题？

• 输入： 发生在不同节点上的事件。
• 输出： 一个逻辑时间戳，用于确定一个事件是否“先于”另一个，或者它们是否是“并发”的（存在冲突）。
• 承诺： 在分布式数据库中实现可靠的冲突检测。

核心思想 (工作原理)

1. 向量： 每个节点都维护一个计数器列表（向量），系统中的每个节点对应一个位置：[节点A: 0, 节点B: 0, 节点C: 0]。
2. 更新： 每当一个节点执行操作时，它会增加向量中属于它 自己 的那个计数器。
3. 同步： 当节点 A 向节点 B 发送数据时，它会带上自己的整个向量。节点 B 接收后，会将对应的计数器都取 最大值 进行合并。

比较两个时钟：

• 先于 (Happened Before)： 如果向量 A 的每一项都 $\le$ 向量 B，则 A 先于 B 发生。
• 冲突 (Conflict)： 如果 A 的某些项比 B 大，而另一些项比 B 小，说明这两个事件是 并发 发生的。我们发现了一个冲突！

典型业务场景

• ✅ 协作编辑： 确定两个用户是否同时编辑了同一个段落（如 Figma 或 Google Docs 的底层逻辑）。

• ✅ DynamoDB / Riak： 这些追求高可用性的数据库使用向量时钟来检测同一条记录是否存在两个竞争版本，并要求用户解决冲突（读时修复）。

• ✅ 分布式版本控制： Git 使用类似的 DAG（有向无环图）概念来追蹤历史记录。

• ❌ 超大规模集群： 如果你有 10,000 个节点，向量就会变成 10,000 维，传输代价太重。此时通常改用 点式版本向量 (Dotted Version Vectors)。

性能与复杂度总结

• 空间： $O(N)$，其中 $N$ 是节点数量。
• 比较： $O(N)$。

小结：一句话记住它

“向量时钟是云端的‘逻辑计时器’。它允许我们在没有共享时钟的情况下，重建数据的故事，并准确识别出两个事件是在何时发生碰撞的。”