Time, Clocks, and the Ordering of Events（逻辑时钟）

一句话

Lamport 指出：分布式系统里没有、也不该依赖统一的物理时钟；事件的先后应由「一个事件能否影响另一个」这条因果关系来定义。他给出 happens-before（先于）偏序、一套只用计数器就能实现的逻辑时钟（今称 Lamport 时间戳），再把偏序补成全序，从而让分散各地、各自独立的多台机器按同一顺序处理同一批命令、始终保持一致。这套复制状态机（state machine replication）思想，是后来 Paxos、Raft 乃至一切强一致分布式系统的根。

Glossary · 术语表

坐标

作者 Leslie Lamport，写于 Massachusetts Computer Associates，1978 年 7 月发表于《Communications of the ACM》。它把爱因斯坦狭义相对论里「事件先后并非绝对」的洞见搬进了计算机；下启向量时钟、Chandy–Lamport 分布式快照、Paxos、复制状态机一整条线，是 Lamport 2013 年图灵奖的奠基工作之一，也是被引最多的计算机论文之一。

问题与动机

在单机上，「谁先谁后」由 CPU 的时钟裁决，天经地义。可一旦把许多机器用网络连起来，麻烦就来了：每台机器有自己的石英钟，还都会漂移（走得有快有慢），网络传一条消息的延迟又忽长忽短。你怎么判断「机器 A 上的扣款」和「机器 B 上的查询余额」谁先发生？靠比两块表？——表本身对不齐，而想把物理时间对到足够齐，既贵又不可靠。

更根本的一层是：很多事件本就没有客观的先后，它们在各地独立、几乎同时发生，问「谁先」根本没意义。可是只要副本之间无法就「按什么顺序处理请求」达成一致，数据就会各说各话。Lamport 要解决的，正是这个「在没有共同时间的世界里，如何谈论顺序」的第一性问题。

核心思想 / 方法

其一 · happens-before：用因果定义先后

Lamport 换了个问法：别问「谁的表更早」，问「谁能影响谁」。他定义了一个「先于」关系 →，只用三条规则、完全不碰物理时间：① 同一进程内，先执行的事件 → 后执行的；② 一条消息的「发送」→ 它的「接收」（因为信息必须先发出才能被收到）；③ 传递性：a→b 且 b→c 则 a→c。若 a→b，就说明 a 有可能影响 b。

要害在于：这是偏序，不是全序。有些事件对之间谁也影响不到对方（消息传不过去），它们就叫并发（concurrent），无所谓先后。这正呼应相对论——对「并发事件」，不同观察者眼里的先后可以不同，硬排反而是错的。

其二 · 逻辑时钟：给每个进程一个号码牌

怎么让机器自动算出这套先后？给进程 Pi 配一个计数器 Ci，给每个事件 a 贴一个数 Ci(a)。目标是满足时钟条件：只要 a→b，就必须 C(a) < C(b)。用两条实现规则就能保证：

• IR1：本地每发生一个事件，计数器就 +1。——保证同一进程内后来的事件号更大。
• IR2：发消息时，把当前计数当「时间戳」捎在消息里；收消息时，把自己的计数跳到「比自己现在和捎来的都大」。公式即 Cj := max(Cj, Tm) + 1（Tm 是消息里带的发送方时间戳）——保证「接收」的号一定比「发送」的号大。

白话讲：这就是邮局的邮戳。寄信盖一个号，收信方一看信封上是 7 号，就把自己的柜台号推到 8 再往后走。请记住这不是钟、是号码牌——它只保证「有因果的事件号一定递增」，并不测量任何真实时间。

其三 · 补成全序：加一个平局裁判

逻辑时钟给的还是偏序——两个并发事件可能拿到相同的号。要让所有机器排出完全一致、唯一的一份顺序，再加一条平局规则：号相同时，就按进程编号大小分先后（比如规定 P1 < P2 < P3）。于是任意两个事件都能比出唯一先后，得到一个与因果不冲突的全序（记作 ⇒）。白话：先看号码牌，撞号看工号。

其四 · 杀手级应用：无中心互斥 = 复制状态机

有了全序，Lamport 给出一个完全没有中央协调者的分布式互斥算法（决定谁能用共享资源）：想用资源，就把一条带时间戳的「请求」广播给所有人、同时记进自己的一份队列；别人收到请求，入队并回一个带时间戳的确认；用完再广播「释放」，各方把该请求从队列删掉。规则是：当且仅当自己的请求排在（按全序 ⇒ 排好的）队列最前、且已收到每一个其他进程时间戳更晚的消息，才算轮到自己。

因为人人手里维护的是同一份、按同一个全序排好的队列，所有人对「现在轮到谁」的判断必然一致——不需要任何中心。把这层抽象出来，就是影响深远的复制状态机：把服务写成一台确定性状态机，让每个副本按同一个全序执行同一串命令；同样的输入、同样的顺序，必得同样的状态。这就是容错复制的通用配方。

诚实提示：这个互斥算法有前提——两进程间的消息不丢、且按发送顺序到达（FIFO 可靠信道），并且不容忍宕机。这些前提正是后来 Paxos 一类真正容错共识要补的洞。

其五 · 物理时钟的回归

逻辑时钟只看得见系统内部的消息。若两件事通过系统外的渠道产生了因果（比如一个人打电话通知另一地的人去操作），系统看不见这条因果，算出的全序就可能与现实相悖，这叫异常行为（anomalous behavior）。要堵这个漏洞，要么把外部顺序也喂进系统，要么改用同步得足够好的物理时钟。论文最后给了一个定理：物理钟需要同步到多准（取决于消息最短延迟）才能杜绝异常——推导从略，直觉是钟的误差不能大到让一条消息看起来「还没发就先到」。

关键结果

这是一篇理论论文，没有跑分。它的「结果」是几样此后成为地基的构造：happens-before 偏序、Lamport 逻辑时钟、把偏序补成全序的办法，以及一个可证明正确的分布式互斥算法（每次请求约 3(N−1) 条消息、全程无需中央节点），并由此坐实了复制状态机方法的可行；物理时钟一节则给出可证明的同步界。它的价值不在某个数字，而在第一次把「分布式系统里的时间与顺序」这件事讲清楚、并给出可实现的机制。

为什么重要 / 影响

它奠定了分布式系统的时间观。happens-before 与逻辑时钟成了教科书标配（业界直接叫「Lamport 时间戳」）；复制状态机成为容错的通用范式，直接通往 Paxos（同样出自 Lamport）、Raft、ZooKeeper 以及所有强一致数据库——Google Spanner 的 TrueTime，正是为回答本文最后那个「物理钟到底能同步到多准」而给出的工业级答案。它还催生了向量时钟、Chandy–Lamport 分布式快照、因果一致性等一整条研究线。被引数以万计，是 Lamport 2013 年图灵奖的核心贡献之一。

局限与批评

• 逻辑时钟是「单向」的：a→b 能推出 C(a)<C(b)，但反过来不成立——光看号小，不能断定两事件真有因果，也分不清它们是「并发」还是「有先后」。要精确捕捉因果，需后来的向量时钟（vector clock，Fidge / Mattern 1988）：a→b 当且仅当 V(a)<V(b)。
• 互斥算法不容错：它依赖收到「每一个」进程的消息，任一节点宕机就整体卡死；还要求 FIFO 可靠信道，消息量随进程数线性增长。真实系统需 Paxos / Raft 这类真正的容错共识来替代。
• 全序在并发事件间是任意的：一致但不「有意义」——它只保证大家排得一样，不保证符合任何现实语义。
• 物理时钟一节偏理论：真正的工程化时钟同步（NTP、GPS、原子钟、TrueTime）是几十年后的后话。

要点