《大规模分布式计算深入解析》6.3 HLC 与 TrueTime:不确定区间与等待

给出 HLC 接收规则和 TrueTime 等待判据,解释为什么固定 2ε 只适合作为模型。

HLC 按事件推进

令 l,c 为本地 HLC,lr,cr 为收到的 HLC,p 为当前物理时钟。接收令 m=max(l,lr,p)。若 m 同时等于 l 与 lr,则新逻辑分量为 max(c,cr)+1,若只等于 l,则为 c+1,若只等于 lr,则为 cr+1,只有 p 最大时归零。本地事件和发送可忽略远端分量。HLC 保留因果顺序并在假设下接近物理时钟。48+16 的布局只是演示,溢出与超前传播由版本实现明确处理。

TrueTime 的等待

TrueTime 返回包含真实时间的区间,提交戳为 s 时,只要 TT.now().earliest > s 才知道它已经过去。固定 ε=7 ms、令 s 取第一次区间的 latest、端点按匀速前移时,初始两端相差 14 ms,跨过该间隔才满足严格不等式。实际剩余等待受已经耗去的时间、s 被其他约束抬高和 ε 变化影响,部分可与复制重叠。Spanner 的事务路径见 11.2 节 。

两种机制的决策边界

flowchart TD
    H["HLC 接收事件"] --> M["m 取本地 HLC、远端 HLC、物理时间的最大值"]
    M --> B{"哪些 HLC 的时间分量等于 m?"}
    B -- "两者" --> BOTH["取最大逻辑分量再加一"]
    B -- "只等于本地或远端" --> ONE["对应逻辑分量加一"]
    B -- "仅物理时钟更大" --> ZERO["逻辑分量置零"]
    T["TrueTime 提交节点,依协议选定 s"] --> A{"TT.now().earliest 已严格大于 s?"}
    A -- "尚未" --> W["等待,再测区间"]
    W --> A
    A -- "满足" --> C["时间屏障通过,仍需满足事务终局与持久化条件"]

验证

从卷七实验包 解包,运行 Java 的 TrueTime 严格边界与 HLC 向量练习,分别验证 earliest 等于和超过 s。

一手资料

卷七目录 · 系列导读与实验

继续阅读

探索更多技术文章

浏览归档,发现更多关于系统设计、工具链和工程实践的内容。

全部文章 返回首页

「books」更多文章

  1. 《大规模分布式计算深入解析》15.3 落地:从 Neo4j 到自研图引擎
  2. 《大规模分布式计算深入解析·图计算与图数据库内核》 · 目录与学习路径(45 篇)
  3. 《大规模分布式计算深入解析》15.2 十一卷主线:从切分到图