编号守住因果，向量识别并发
一句话总结
在分布式系统里，决定“什么在先”的不是墙钟，而是消息。Lamport 时钟给出不违背因果的编号，向量时钟则更进一步，还能告诉你“这两个事件互不知晓（并发）”。如果不了解这个差别，LWW 会悄悄丢弃更新，各层各自加上的重试会以乘法膨胀。
为什么需要它
看两行日志的时间戳来决定顺序，是很常见的事。但如果这两行来自不同的服务器，这种比较就依赖于“两个时钟都是准的”这一假设。时钟为什么、偏差多少，以及 NTP，“日志来自未来”课程把它们作为一起起事故来讲。本模块从相反的问题出发——不去对时钟，对顺序能确定地说什么？
Lamport 在 Time, Clocks, and the Ordering of Events in a Distributed System（CACM 第 21 卷第 7 期，1978）中，不用物理时间，只用系统内部可以观察到的事件来定义“先发生（happened before，→）”。条件有三个：在同一个进程中，a 在 b 之前，则 a → b。如果 a 是某条消息的发送，b 是这条消息的接收，则 a → b。如果 a → b 且 b → c，则 a → c。并且，既不满足 a → b 也不满足 b → a 的两个不同事件，称为并发（concurrent）。论文强调，这种关系只是所有事件上的偏序。这意味着，从一开始就有无法确定顺序的事件对，而正是因为人们对这一事实没有充分意识，才会出问题。
工作原理
Lamport 时钟。 实现规则有两条。IR1——每个进程在两个连续事件之间让自己的时钟增加。IR2——消息上附带发送时刻 Tm，接收方把自己的时钟调整为“不小于当前值且大于 Tm”。常见的实现是接收时取 max(자기 값, Tm) + 1（占位符为自己当前的值）。如果在这里去掉 max，只做 +1，就会出现编号比发送还小的接收，规则就被打破了。
这条规则只保证 Clock Condition——如果 a → b，则 C(a) < C(b)——这一点。论文明确写道，不能指望逆命题成立。要让逆命题成立，两个并发的事件必须是同一个时刻，而这是不可能的。所以，看到 C(a) < C(b) 就说 a → b，是错的。论文用给进程任意排序的办法，把相同的编号分开，做出了全序，但那只是不违背因果的多种排列之一，并不能告诉你因果。
向量时钟。 如果连逆命题也需要，一个编号就不够了。Mattern 的 Virtual Time and Global States of Distributed Systems（1989）使用的向量，格子数与进程数相同。同一篇论文写道，Fidge 独立地提出了同样的想法。每个事件把自己那一格加 1，消息带着向量一起发送，接收方逐格取 max 合并。比较也是逐格进行：所有格都小于等于且两者不同，则 u < v；两个方向都不满足，就是并发（u ‖ v）。论文的 Theorem 10 说，e < e′ 与 C(e) < C(e′) 是等价的，e ‖ e′ 与 C(e) ‖ C(e′) 也是等价的。
| Lamport 时钟 | 向量时钟 | |
|---|---|---|
| 如果 a → b | L(a) < L(b) | V(a) < V(b) |
| 如果值较小 | 什么都不知道 | 就是 a → b |
| 能识别并发吗 | 不能 | V(a) ‖ V(b) |
| 大小 | 一个整数 | 与进程数相同 |
代价是大小。如果有 n 个进程，每条消息都要带着 n 格，而在参与者不断进出的系统里，管理这些格子本身就成了另一件事。
在现场相遇的样子
LWW 会丢弃更新。 Cassandra 文档写道，不同于最初的 Dynamo 论文用向量时钟来调和并发更新，Cassandra 使用更简单的 last-write-wins。每次变更都用客户端或协调者的时钟打上时间戳，最晚的值获胜。同一份文档说，正确性取决于那个时钟，所以一定要运行 NTP 之类的同步。这里藏着两层丢失。两个并发写入中，有一个会毫无报错地消失；还有，时钟偏快的副本的写入，会战胜看过它之后才写入的、时钟偏慢的副本的写入（因果倒置）。如果配上向量时钟，至少“这两者是并发的”这个事实会保留下来，是合并还是去问人，可以由应用来决定。
重试会相乘。 Google SRE 书中的 Addressing Cascading Failures 一章警告说，如果在多个层级重试，一个最顶层请求，最多可以产生各层尝试次数之积那么多的最底层调用。书里的例子是，DB 过载时，后端、前端、JavaScript 各自重试 3 次（共尝试 4 次），一个用户操作就会打到 DB 上 64 次。偏偏是在 DB 最脆弱的时候。在哪一层重试、重试预算、抖动、幂等键，由“幂等性 — 点两次也只扣一次款”课程从设计上讲；用编号来确立顺序的另一种装置——任期（term），由“当时有两个领导者”课程讲。
下一项实验要做什么
给四个进程的事件记录加上 Lamport 时钟，按定义判定 happened-before，看“编号小就在先”在哪些事件对上是错的。用向量时钟数出所有并发的事件对，在墙钟有偏差的三个副本对同一个键的写入中，找出冲突列表以及 LWW 悄悄丢弃的更新。最后计算在各层重试策略下 DB 调用会变成几倍，并写出综合报告。