分布式系统里，什么叫「先来后到」

1978 年那篇论文的开头，藏着一个打电话的例子。

假设有一个全国联网的系统。A 城的人在机器 A 上提交了一个请求，然后拿起电话，打给 B 城的朋友，让他在机器 B 上提交另一个请求。谁先谁后？任何人都会说：A 在前——电话那头的 B 之所以会发生，是因为 A 已经发生了。

可是系统可能给 B 一个更早的时间戳。因为在系统眼里，那通电话不存在：机器 A 和机器 B 之间没有任何消息往来，系统无从得知 A 和 B 有因果。这不是 bug，是分布式系统的本性——它只看得见自己内部的消息。

写这个例子的人叫 Leslie Lamport。这篇《Time, Clocks, and the Ordering of Events in a Distributed System》发表在 1978 年 7 月的 Communications of the ACM，八页，后来成为分布式系统的奠基文献之一。

不用钟表，用因果

要给「先来后到」下定义，最直觉的办法是看钟。但每台机器有自己的钟，走得快慢不一，两台机器对「现在几点」根本没有共识。Lamport 的做法是把钟扔掉，直接定义一个关系，记作箭头：a 发生在 b 之前。

规则有三条。同一条流水线上的两个动作，先做的在前。一台机器发出消息在前，另一台收到消息在后。如果 a 在 b 前、b 在 c 前，那么 a 在 c 前。

这个箭头叫「发生在之前」（happened-before）。它的麻烦在于：有些事件对，谁也不在谁前面。两台机器各干各的活，中间没传过消息——它们互不可比。物理世界里我们习惯说「同时」，在分布式系统里，「同时」这个说法干脆没有定义。Lamport 在论文里提醒：很多问题出在人们没有充分意识到这一点。

钟，其实是配菜

接下来是这篇论文名字的来历。它给这套关系配上数字：每个进程自带一个计数器，自己每做一个动作，计数器加一；发消息时把当前数字捎上；收到消息的进程，把自己的计数器拨到「自己的数和消息里的数取大者，再加一」。

这套数字叫逻辑钟。它有一条漂亮的性质：只要 a 在 b 之前发生，a 的钟一定小于 b 的钟。因为钟只增不减，消息只能把钟往前推——数字顺着因果的方向单调上涨。

一个数字序列比一张关系图好排得多。遇到两个互不可比的事件，就按进程编号排个先后，偏序补成全序。全序不唯一——换一套钟，并列者的次序可能不同——但不管哪一种，都严格顺着因果方向。排队这件事，从此有了统一规则。

论文用这个全序做了一个正经应用：互斥。多台机器抢一个资源，谁先进去？每台机器维护一个请求队列，按全序排队，申请资源时带上自己的时间戳广播一圈，收到所有机器的回应、且自己的请求排在自己队列的最前面，才进门。算法的代价不在算力，在消息——每一轮进出都要全网打招呼，机器越多，来回越多。慢，但对。

电话那头的麻烦

逻辑钟有一个天然的盲区，就是开头那个打电话的例子。它只顺着系统内的消息传播，系统外的因果，它一根线都看不见。

论文的最后两页处理这件事：把真正的物理钟搬回来，做同步。Lamport 推导出一个界。设 κ 是钟的漂移率（一秒的活，钟走了 1 加 κ 秒），μ 是消息在两台机器之间飞的最短时间，ξ 是同步之后两台钟还能差出的最大值。论文证明：只要 ξ/(1−κ) 不超过 μ，开头那种「电话颠倒因果」的反常行为就永远不会发生。

这个不等式值得停一下。钟越准（ξ 小），消息越快（μ 大），越安全。它把一个哲学问题——「分布式系统里时间是什么」——变成了一个工程参数：买多准的钟、接受多快的网络，就能让全系统对先来后到达成物理意义上的共识。

四十年后，Google 的 Spanner 数据库把这道不等式做成了基建：在全球数据中心里装 GPS 接收器和原子钟，把钟差压到几毫秒，再让事务在时间区间上等一等。那笔钱买的就是把 ξ 压小。

数字小，未必在前

逻辑钟的保证是单向的：因果在前，数字必小。反过来不成立——数字小的事件，未必是原因。它可能是另一台机器上一件毫不相干的旧事。

把反方向也补上的是向量时钟：每台机器不再记一个数，而是记一张表——「我眼中的每台机器各走到几号」。收消息时逐项取大。两张表一比，谁包含谁，因果立刻可见，连互不可比也能一眼认出来。这是 Mattern 和 Fidge 在 1988 年前后各自独立补上的。再往后，1985 年的分布式快照算法（Chandy 和 Lamport 合作）回答「如何给一个不停变化的系统拍一张全局照片」，用的还是同一个因果框架。

2013 年 Lamport 拿图灵奖，授奖词里点名了「causality and logical clocks」——因果和逻辑钟。这篇论文 2000 年拿了分布式计算方向的首届最具影响力论文奖，几年后这个奖改以 Dijkstra 命名，继续每年发。论文版权页上印着当年的售价：75 美分。