分布式算法 #09：Hybrid Logical Clock（HLC）

Hybrid Logical Clock（HLC）是 CockroachDB、YugabyteDB 等 NewSQL 数据库采用的时间戳方案，将物理时钟的直觉性与逻辑时钟的因果正确性融合在一起，在不依赖专有硬件（如 Google TrueTime）的前提下实现接近物理时间的事务排序。

相关文章：向量时钟与因果一致性 · Raft 共识算法 · Quorum 与 NWR 模型

目录

问题背景

物理时钟（NTP）的问题

问题1：时钟漂移
  NTP 同步误差 ±100ms（广域网环境）
  石英晶体每天漂移 ±1s
  → 两个节点的物理时间可能相差数百毫秒

问题2：时钟回拨
  NTP 同步时，如果本地时钟快了，NTP 会让时钟走慢或直接回拨
  → 时间戳不单调递增
  → 依赖时间戳排序的系统出现数据错乱

问题3：无法捕获因果关系
  A 在 T=100ms 写入，消息传播 50ms 后 B 在 T=90ms 处理
  按物理时间，B 的处理"先于"A 的写入（时钟偏差导致）
  → 因果关系倒置

Lamport 时钟的问题

优点：保证因果关系（a→b 则 L(a) < L(b)）
缺点：纯逻辑计数器，与物理时间完全脱节
     无法支持"读最近 10 秒内的数据"这类时间范围查询
     不同节点的逻辑时钟差距可能极大（没有上界）

Google TrueTime 的局限

TrueTime 提供不确定区间 [T-ε, T+ε]（通常 ε<7ms）
通过 GPS + 原子钟硬件保证

问题：
  1. 需要专有硬件（GPS 天线 + 原子钟），成本极高
  2. 只在 Google 数据中心内可用
  3. 开源系统无法使用

HLC 的目标：
  只用 NTP（廉价、普遍可用）
  提供与物理时钟接近的时间戳
  同时保证因果关系的正确性

HLC 数据结构

每个节点维护 HLC 时钟，由三部分组成：

HLC = (pt, l, c)

  pt: physical time      // 当前物理时钟值（毫秒/微秒）
  l:  logical component  // 逻辑部分：已观察到的最大物理时间
                         // l >= 当前节点的物理时钟（防时钟回拨）
  c:  counter            // 计数器：区分相同 l 下的事件顺序

比较规则（字典序）：
  HLC_a < HLC_b 当且仅当：
    l_a < l_b，或
    (l_a == l_b 且 c_a < c_b)

  即：先按 l 比，l 相同再按 c 比，c 相同则视为同一时刻（并发）

HLC 算法

// 初始化
state = {l: 0, c: 0}

// 本地事件（本地写入、本地操作）
function sendOrLocalEvent():
  pt = physicalClock.now()
  if pt > state.l:
    state.l = pt
    state.c = 0
  else:
    // 物理时钟没有前进（时钟回拨或同一毫秒内多次操作）
    state.c += 1
  return (state.l, state.c)  // 作为事件时间戳

// 接收消息（携带发送方的 HLC 时间戳 (l_m, c_m)）
function receiveEvent(l_m, c_m):
  pt = physicalClock.now()
  l_old = state.l

  state.l = max(state.l, l_m, pt)  // 取最大的 l

  if state.l == l_old and state.l == l_m:
    // 三者相等（本地 l == 消息 l）
    state.c = max(state.c, c_m) + 1
  elif state.l == l_old:
    // 本地 l 最大（物理时钟或之前的 l 最大）
    state.c += 1
  elif state.l == l_m:
    // 消息的 l 最大（发送方时钟更超前）
    state.c = c_m + 1
  else:
    // 物理时钟最大
    state.c = 0

  return (state.l, state.c)

具体示例：

节点 A（物理时钟 pt=10）：
  本地事件：
    pt=10 > l=0 → l=10, c=0
    时间戳：(10, 0)

A 发消息给 B（携带 (l=10, c=0)）

节点 B（物理时钟 pt=8，慢了）：
  接收事件(l_m=10, c_m=0)：
    pt=8，l_m=10，l_old=0
    state.l = max(0, 10, 8) = 10
    state.l == l_m → state.c = c_m + 1 = 1
    B 的时间戳：(10, 1)
  
  B 的时间戳 (10,1) > A 的 (10,0) ✅
  因果关系：A 发消息 → B 收到，HLC 保证 B.ts > A.ts ✅

节点 B 随后本地写入：
  pt=8（仍然慢），l=10
  pt=8 <= l=10 → l 不变，c += 1 → (10, 2)

B 发消息给 C（携带 (10, 2)）
节点 C（物理时钟 pt=15）：
  接收事件(l_m=10, c_m=2)：
    pt=15 > l_m=10 → state.l = 15, state.c = 0
    C 的时间戳：(15, 0)

  (15,0) > (10,2)，因果关系正确 ✅
  且 C 的时间戳接近物理时间（15），直觉友好 ✅

异常场景分析

异常 1：时钟漂移（某节点时钟走快）

场景：节点 B 的物理时钟比实际时间快 500ms（pt_B = 真实时间 + 500ms）

B 本地写入时：l_B = pt_B = 真实时间 + 500ms

B 的消息传播给 A：
  A 的 l_A = max(l_A, l_m=真实时间+500ms, pt_A=真实时间)
  l_A 被 B 的 "未来" 时钟拉高！

后续影响：
  A 发出的时间戳 >= 真实时间 + 500ms
  其他节点收到 A 的消息后，l 也被拉高
  HLC 值 "传染" 了 B 的快时钟

HLC 的保护机制：
  设置 maxOffset（最大允许时钟偏差，如 500ms）
  if l - pt > maxOffset:
    拒绝接受该消息（告警：时钟偏差过大）
    触发 NTP 重新同步

实际 CockroachDB 配置：
  maxOffset = 500ms（默认）
  超过时 → panic 或 warning，阻止相关事务执行

异常 2：时钟回拨（NTP 修正导致）

场景：NTP 检测到本地时钟快了 200ms，将时钟回拨 200ms

物理时钟跳变：pt 从 1000 降到 800

HLC 处理：
  本地事件时：
    pt=800 <= l=1000（l 保留了之前的最大值）
    → l 不变，c += 1
    → 时间戳：(1000, 1)，单调递增 ✅

  物理时钟回拨不影响 HLC 的单调性！
  这是 HLC 相比纯物理时钟的核心优势之一

回拨幅度过大时：
  如果时钟跳回超过 maxOffset → 触发告警
  等待物理时钟追上 l 后再恢复正常递增模式

异常 3：节点宕机重启

场景：节点 A 宕机，重启后物理时钟可能落后（电池耗尽等）

问题：重启后 l 从 0 开始（内存丢失），可能小于宕机前的 l
     → 发出时间戳比宕机前更小，违反单调性！

解决方案：
  持久化 l 到磁盘（每次更新 l 时 fsync）
  重启后从磁盘恢复 l
  → 恢复后 l 不小于宕机前的值 ✅

  CockroachDB 的做法：
    每次写事务时，将 HLC 写入 RocksDB（WAL 保证持久化）
    重启后从 WAL 恢复最新的 HLC 值

异常 4：消息乱序（网络延迟导致）

场景：
  A 在 HLC=(100, 0) 发送 msg1
  A 在 HLC=(100, 1) 发送 msg2

  B 先收到 msg2(100,1)，后收到 msg1(100,0)

HLC 处理（正确）：
  B 收到 msg2(100,1)：
    state = (max(state.l, 100), ...) → (100, 2)
  
  B 收到 msg1(100,0)（旧消息）：
    state.l = max(state.l=100, l_m=100, pt=...) = 100
    state.l == l_old == l_m → c = max(state.c=2, 0) + 1 = 3

  B 处理的两条消息都是合法的
  B 的本地 HLC 单调递增 ✅
  
  因果序不由 HLC 单独保证，需配合应用层判断：
  if msg.hlc < lastProcessed.hlc:
    "这是旧消息，可能乱序到达，需要幂等处理或丢弃"

异常 5：大集群中 l 不断膨胀

问题：每个节点在 receive 时取 max(state.l, l_m, pt)
     如果某节点时钟异常快，其 l 值会通过 Gossip 传染整个集群
     → 整个集群的 l 被拉高，远超真实物理时间

缓解方案：
  1. 严格的 maxOffset 检查（拒绝偏差过大的 l 值）
  2. 定期 NTP 同步校准物理时钟
  3. 监控告警：l - pt > threshold 时触发
  
  CockroachDB：
    默认 maxOffset = 500ms
    超过阈值 → 拒绝接受消息，打印 "clock skew" 警告
    如果 clock skew 持续 → 节点自杀（graceful shutdown），避免数据不一致

与其他方案的对比

HLC 在 CockroachDB 中的实践

CockroachDB 使用 HLC + MVCC 实现多版本并发控制：

写事务：
  获取 HLC 时间戳 ts = hlc.Now()
  写入数据时，key 的版本 = ts
  同一 key 可以有多个版本（不同 ts）

读事务：
  获取快照时间戳 snapshot_ts = hlc.Now()
  读取 key 时，返回 ts <= snapshot_ts 的最新版本
  → 一致性快照读（Consistent Snapshot）

因果一致性（外部一致性）：
  事务 T1 提交时，HLC = (l1, c1)
  客户端在 T1 提交后发起 T2（通过等待或传递 T1 的 HLC 给 T2）
  T2 的 snapshot_ts >= T1 的提交时间戳
  → T2 一定能看到 T1 的写入 ✅

时钟不确定性窗口（Uncertainty Interval）：
  问题：节点 A 写入 ts=100，节点 B 的物理时钟只有 95
  B 发起读事务，snapshot_ts=95，无法看到 ts=100 的写入！

CockroachDB 的解法（Uncertainty Restart）：
  读事务扫描时，如果发现 key 版本在 [snapshot_ts, snapshot_ts + maxOffset] 区间内
  触发 "uncertainty restart"：将 snapshot_ts 推进到该版本 ts，重试事务
  最多重试 maxOffset/RTT 次后，不确定性窗口消失

HLC 的局限

1. 无法精确检测并发
   HLC 只能判断因果先后（a→b 则 HLC_a < HLC_b）
   如果 HLC_a < HLC_b，不能断定 a→b（可能是并发但 a 时钟更慢）
   需要真正检测并发：仍需向量时钟（代价 O(N)）

2. 时钟偏差上界依赖 maxOffset 配置
   如果实际偏差超过 maxOffset，系统可能产生异常
   需要运维保证 NTP 同步质量

3. 不等价于 TrueTime 的外部一致性
   TrueTime 通过硬件保证 ε < 7ms，100% 确定
   HLC 通过 maxOffset 软性约束，极端情况下可违反
   金融级场景（如 Spanner 的外部一致性保证）仍需 TrueTime

4. 全球跨 Region 场景
   RTT > 100ms 时，uncertainty window 导致的重试代价较高
   Spanner 的 TrueTime ε < 7ms 使 uncertainty window 极小

参考资料

• Kulkarni, S. et al. (2014). Logical Physical Clocks and Consistent Snapshots in Globally Distributed Databases
• CockroachDB Architecture: https://www.cockroachlabs.com/docs/stable/architecture/transaction-layer.html
• 《Designing Data-Intensive Applications》Ch.8 — Clocks and Ordering of Events
• Corbett, J.C. et al. (2013). Spanner: Google's Globally Distributed Database