HLC 2014 — 把逻辑时钟和物理时钟合一，让普通服务器也能拍一致快照

是什么

HLC（Hybrid Logical Clock）是一篇 16 页论文，它告诉我们：不用原子钟，也能给跨数据中心的事务发一个既符合因果、又贴近真实时间的时间戳。日常类比：lamport-1978 那篇里大家只用”事件序号”排队，序号不知道现在是几点；spanner-2012 那篇里 Google 给每个机房装 GPS 加原子钟，把误差压到几毫秒。HLC 是中间道路——每张支票上同时写两个数字：一个是”墙上的钟看到几点”（物理部分 l），一个是”同一秒内你是第几张”（逻辑部分 c）。墙上的钟用 NTP 同步，可能差几十毫秒；逻辑序号补上这点偏差，让因果先后绝不颠倒。

更具体地说：每个事件的时间戳是 (l, c) 二元组。l 是这个进程见过的最大物理时间（自己的或消息带来的），c 是同一 l 下的递增计数器。三条更新规则保证两条性质同时成立：(1) 如果 a 因果在 b 之前（a→b），那么 hlc(a) < hlc(b)——继承 Lamport 时钟；(2) |hlc.l - pt| 不会比 NTP 偏差更大——继承物理时钟。整个时间戳能塞进 64 bit（48 bit 毫秒 + 16 bit 计数器），可以直接当 MVCC 版本号用。

10 年过去，CockroachDB / YugabyteDB / MongoDB 3.6+ / FoundationDB 这一波分布式数据库的”时间戳”几乎全是它的孩子。

为什么重要

不理解这篇，下面这些事都没法解释：

为什么 cockroachdb-2020 不需要 Google 那套 GPS + 原子钟硬件，也敢说自己能跨机房做 serializable 事务
为什么 MongoDB 4.0+ 的 causal consistency session 能让”在我读到的状态之上再写”这件事变得简单
为什么 NewSQL 这一波（CRDB / TiDB / YugabyteDB）能在公有云上跑——TrueTime 不可移植，HLC 是
为什么”AS OF SYSTEM TIME '-10s'”这种语法能精确读到 10 秒前的一致快照

核心要点

HLC 把”时钟问题”拆成 三件事，每件解决前一件留下的缺口：

物理部分 l 跟住 NTP：每次事件触发时，先把 l 更新成 max(l, pt)（pt 是当前墙上时间）。类比：你每次写支票前先抬头看一眼挂钟。这保证 l 不会比真实时间落后太多——只要 NTP 还在工作，|l - pt| ≤ epsilon（典型 100ms）。
逻辑部分 c 补 NTP 的偏差：当多个事件落在同一毫秒、或者收到的消息带着更大的 l，光靠 l 排不出先后。这时 c 上场——同一 l 内每次事件 c+=1；收消息时 c = max(本地 c, 消息 c) + 1。类比：同一分钟内来了三个客户，你给他们排 #1 #2 #3 的小票。这保证 a→b ⇒ (l_a, c_a) < (l_b, c_b)——继承 lamport-1978 的因果保序。
比较是字典序：(l1, c1) < (l2, c2) ⟺ l1 < l2，或者 l1 == l2 且 c1 < c2。类比：两张支票先比挂钟时间，挂钟时间一样就比小票号。

三条规则加起来，64 bit 装得下、O(1) 空间、跨机房广播只多 8 字节、还兼容 lamport-1978 的因果保序——这是它能在工程里铺开的根本原因。

实践案例

案例 1：CockroachDB 给跨机房事务发时间戳

事务 T 在东京机房启动
  → 协调者读自己的 HLC：(l=1717000000123, c=0)
  → 把这个时间戳作为事务的 commit ts 候选
  → 写入伦敦副本时，伦敦节点把 (l, c) 合并进自己的 HLC
  → 伦敦节点本地事件触发：c += 1 → (l=1717000000123, c=1)
  → 事务 commit 后，所有相关节点的 HLC 都 ≥ T.ts

后续任何读 T.ts 之前数据的事务，会等到本地 HLC 推进过 T.ts，再做 MVCC 快照读。

案例 2：一致快照 = 等所有节点的 HLC 越过 s

论文第 2 部分给的快照协议：协调者广播一个 snapshot 时间戳 s，每个节点等到 hlc.l ≥ s 才把截止 s 的所有已提交事务回放出去——拼起来就是一张全局一致快照。这正是 CockroachDB 的 AS OF SYSTEM TIME 查询底层。

-- CockroachDB
SELECT * FROM accounts AS OF SYSTEM TIME '-30s';
-- 引擎：在每个 range 的副本上等 HLC 推进过 (now-30s)，再快照读

对比 chandy-lamport-1985 的 marker 算法——HLC 不需要发 marker，“时间戳本身”就是同步信号。这是 HLC 在工程上最被低估的优势：快照变成了一个不需要协调的本地等待操作。

案例 3：MongoDB causal consistency session

// MongoDB 3.6+
const session = client.startSession({ causalConsistency: true });
db.coll.insert({x: 1}, { session });   // 服务器返回 cluster time T1
db.coll.find({}, { session });          // 客户端把 T1 带回，副本等 HLC ≥ T1 再读

cluster time 就是 HLC——客户端 session 携带 (l, c) 跨请求，让”读自己刚写的”在副本集里也成立。这套机制现在是所有支持 read-your-writes 的分布式数据库标配。

案例 4：和 fidge-1988 vector clock 的取舍

向量时钟能精确判定 a‖b（真并发），但空间 O(N)，跨机房广播代价高。HLC 是 O(1)，牺牲了”检测并发”的能力——它只能保证 a→b ⇒ hlc(a) < hlc(b)，反过来不成立。CockroachDB 的选择：用 HLC 给单个事务发时间戳，用 mattern-1989 的 virtual time 思想给冲突检测做兜底。

踩过的坑

NTP 跳变把 l 推回去？不会。HLC 保证 l 单调递增——即便 pt 突然回拨，max(l, pt) 还是取大的那个，l 只会停在原地等 pt 追上来。代价：在跳变期间 c 会涨得快一些。
c 会无限膨胀吗？不会。论文证明 c 的上界是消息广播图深度，工程上 16 bit (65535) 足够。但极端消息风暴下也得有降级——CockroachDB 实际配 24 bit logical 部分。
HLC 不等于 external consistency。spanner-2012 的 commit wait 保证”先 commit 的事务时间戳一定小”——这叫 external consistency。HLC 只保因果——如果客户端 A 在东京下单后立刻给客户端 B 打电话，B 在伦敦下单，B 的事务时间戳可能比 A 的小（NTP 偏差跨机房 50ms 是常事）。这一点是 HLC 相对 TrueTime 的本质让步，工程上靠”客户端 session 携带 HLC 上下文”补救。
NTP 完全失效（机器钟坏）会怎样？退化成 Lamport 时钟——l 卡住不动，c 一直涨。系统不会出错，但失去”时间戳贴近真实时间”这条性质，备份/恢复按时间筛事务就不准了。
远超 epsilon 的”未来时间戳”被丢弃。CockroachDB 工程实现里，如果收到的消息 l 比本地 pt 大超过 max_offset（默认 500ms），节点会拒绝消息并报警。这是为了防止”恶意/损坏节点把时间戳推到很远的未来”污染整个集群——HLC 不像 Spanner 有硬件可信源，必须靠这种”上界检查”做保护。

适用 vs 不适用场景

适用：

跨机房分布式数据库（cockroachdb-2020 / YugabyteDB / TiDB）的 MVCC 时间戳
一致快照、备份恢复（“恢复到 10 分钟前”这种语义）
causal consistency session（MongoDB 3.6+ 的 cluster time）
没有特殊硬件的公有云环境

不适用：

需要 external consistency / linearizability 的强一致场景 → 上 spanner-2012 TrueTime + commit wait
需要精确检测并发事件 → 用 fidge-1988 / mattern-1989 向量时钟
单机系统 / 不跨进程通信 → 直接用 wall clock 就够
完全无 NTP 环境（卫星离线 / 工业现场）→ HLC 退化成 Lamport，失去物理时间逼近这条优势

历史小故事（可跳过）

2012 年：Google 发 spanner-2012 论文，TrueTime 让外界第一次见识”硬件解决时钟问题”的威力——但也让人意识到 GPS+原子钟在公有云不可复制。
2014 年：Sandeep Kulkarni 和 Murat Demirbas（布法罗大学）等人在 OPODIS 发表本文。论文动机就是”how to get Spanner-like guarantees without atomic clocks”。
2015 年：CockroachDB Labs 在博客明确说”我们用 HLC”，开源世界第一次有了 Spanner 的可工程对标。
2017 年：YugabyteDB 公开技术架构，把内部时间戳叫 Hybrid Time——本质同 HLC。
2018 年：MongoDB 4.0 加 cluster time（HLC 变体），让 causal consistency 落地。

10 年过去，HLC 这个 16 页的小论文，悄悄变成了所有”开源 Spanner”的时间地基。

三条更新规则的伪代码

逐字翻译论文 Algorithm 1 的核心三条：

// 本地事件 / 发送消息
on local_event_or_send():
  l_prev = l.j
  l.j = max(l_prev, pt.j)
  if l.j == l_prev:
    c.j = c.j + 1
  else:
    c.j = 0

// 收到消息 (l_m, c_m)
on receive(l_m, c_m):
  l_prev = l.j
  l.j = max(l_prev, l_m, pt.j)
  if l.j == l_prev == l_m:    c.j = max(c.j, c_m) + 1
  elif l.j == l_prev:         c.j = c.j + 1
  elif l.j == l_m:            c.j = c_m + 1
  else:                       c.j = 0

读完这 12 行就理解了 CockroachDB / YugabyteDB / MongoDB cluster time 三家的时间戳引擎。

学到什么

混合方案常常胜过纯方案——纯 Lamport 失去物理意义，纯物理时钟失去因果保证，两者结合反而都能拿到
64 bit 是工程的硬约束——HLC 能流行，很大程度是因为它能塞进现有 timestamp 字段，不改 schema
降级要优雅：NTP 失效时 HLC 退化成 Lamport 而不是崩溃，这是工程系统的关键素养
理论 → 算法 → 工程：lamport-1978 (1978) → HLC (2014) → CockroachDB GA (2017)，36 年才把”时间戳”这件事真正在生产系统里铺开

关联

lamport-1978 —— HLC 的 c 部分是 Lamport 时钟，因果保序由它继承
fidge-1988 —— vector clock 是 O(N) 路线，HLC 是 O(1) 路线，两者互补
mattern-1989 —— virtual time 框架；HLC 可以看成 virtual time 在 (物理, 逻辑) 二维上的特化
spanner-2012 —— HLC 的对照组：硬件方案（TrueTime）vs 软件方案（HLC）
cockroachdb-2020 —— HLC 最大的工业用户，整套 MVCC 都建立在它之上
chandy-lamport-1985 —— 经典一致快照算法；HLC 的快照协议是它的”时间戳化”简化

反向链接

chandy-lamport-1985 —— Chandy-Lamport 1985 — 分布式系统不停机也能拍一张全家福
cockroachdb-2020 —— CockroachDB 2020 — 没原子钟也能做全球强一致 SQL 数据库
fidge-1988 —— Fidge 1988 — 给每个进程一份”账本向量”，让因果关系变成可判定
lamport-1978 —— Lamport 1978 — 分布式系统里没有”绝对的同时”
mattern-1989 —— Mattern 1989 — 虚拟时间与全局状态：把分布式时钟变成 N 维笛卡尔积
mills-ntp-1991 —— NTP 1991 — 用四个时间戳和一棵服务器树，让全互联网的钟差几毫秒
ntp-mills-1991 —— NTP 1991 — 用四个时间戳和一组滤波器，让全网服务器的钟差几毫秒
percolator-2010 —— Percolator 2010 — 给 Bigtable 加分布式事务的客户端库
sequential-consistency-1979 —— Sequential Consistency 1979 — 多处理器内存模型的第一个正确性标准
sinfonia-2007 —— Sinfonia 2007 — 把分布式协议降级成数据结构操作
spanner-2012 —— Spanner 2012 — 用原子钟和 GPS 给全球数据库发时间戳