1. 问题陈述

HLC（Hybrid Logical Clock，混合逻辑时钟） 的目标是提供类似 LC（逻辑时钟） 所提供的单向因果检测，维护时钟值永远接近物理/NTP时钟。HLC 的正式问题陈述如下：

给定一个分布式系统，为每个事件 e 分配一个时间戳 l.e，以使：

1. e hb f $\Rightarrow$ l.e < l.f ，
2. l.e 的空间要求为 O(1) 整数，
3. l.e 用有界空间表示,
4. l.e 接近于 pt.e ，例如 |l.e - pt.e| 是有界的。

2. 预备知识

一个分布式系统由数量可能随时变化的一系列节点组成。每个节点可以执行三种行为：发送行为，接收行为，和本地行为。时间戳算法的目标是为每个事件分配一个时间戳。使用全部大写字母的名称表示时间戳算法，由该算法分配的时间戳以相应的小写字母表示。例如，使用 LC 代表 Lamport 发明的逻辑时钟算法，用 lc.e 代表由该算法分配给事件 e 的时间戳。

Happened-Before 概念 hb 捕获系统中事件间的因果关系。使用 e hb f 表示事件 e 发生在事件 f 之前，它是一个遵循如下规则的传递关系：e 和 f 是发生在同一节点的事件，且 e 发生在 f 之前；或者 e 是发送事件，且 f 是相应的接收事件。使用 e||f , iff ¬(e hb f ) ^ ¬(f hb e) 表示 e 和 f 是并发事件。基于以上陈述，以下是正确的：

e hb f $\Rightarrow$ lc.e < lc.f
lc.e = lc.f $\Rightarrow$ e||f
e hb f $\iff$ vc.e < vc.f

3. 简易算法的描述

给定 l.e 应接近于 pt.e 的目标，简易算法以此规则开始：对任何事件 e ，l.e ≥ pt.e 。简易算法如图2所示。该算法的工作原理类似于 LC 。初始设置所有 l 为 0 。当在节点 j 上创建一个发送事件 f 时，将 f 设置为 max(l.e+1, pt.j) ，其中 e 是之前发生在节点 j 上的事件。这确保 l.e < l.f 。它也确保 l.f ≥ pt.f 。同样，当在节点 j 上创建一个接收事件 f 时，将 l.f 设置为 max(l.e + 1, l.m + 1, pt.j) ，其中 l.e 是发生在节点 j 上的先前的事件 e 的时间戳，l.m 是消息的时间戳（发送事件）。这确保了 l.e < l.f 和 l.m < l.f 。

很容易看出图2中的算法满足问题陈述中的前两个要求。然而，简易算法违反了第四个要求，这也导致它违反了第三个“有界空间”要求。为了展示如何违反第四个要求，在图3中指出一个反例，展示了|l.e - pt.e| 是如何以无界方式增长的。在节点1、2、3 之间的消息循环可以一直重复下去，每次循环逻辑时钟与物理时钟的偏移量会不断增长。

无界偏移问题的根源是因为简易算法使用 l 来同时维护至今已知的最大 pt 值和新事件导致的逻辑时钟增量。这导致时钟丢失信息：不确定新的 l 值来自于 pt（如从节点 0 到节点 1 的消息中所示 ）还是因果关系（其他消息也是如此）。因此，没有合适的位置来重置 l 值来限制 l - pt 差值的边界，因为重置 l 可能导致丢失 hb 关系，进而违反要求1。

请注意，即使要求节点的物理时钟在该节点上的任意两个事件之间至少增加一个，该反例仍然有效。然而，如果我们假设发送事件和接收事件的时间足够长，使得每个节点的物理时钟至少增加一个，那么图3中的反例失败了，简易算法将能够保持 |l - pt| 有界。然而，我们接下来展示了如何正确地实现有界 HLC 的正确性，而不是依赖于这样的假设。

4. HLC 算法

我们利用反例中的观察结果来开发正确的 HLC 算法。在该算法中，简易算法中的 l.j 被扩展到两个部分：l.j 和 c.j 。第一部分 l.j 被引入为间接级别，以保持迄今为止已知的 pt 信息的最大值，并且 c 仅用于在 l 值相等时捕获因果关系更新。

与在不违反 hb 的情况下没有合适的地方重置 l 的简易算法相比，在 HLC 算法中，当接收到最大 pt 的赶上或超过 l 的信息时，我们可以重置 c 。由于 l 表示节点之间接收到的最大 pt ，并且不会随着每个事件在有界时间内不断增加，以下任何一种情况都可以保证发生：1）一个节点接收到一个具有较大 l 的消息，其 l 被更新，c 被重置以反映这一点；或者 2）如果该节点没有收到其他节点的消息，则其 l 保持不变，其 pt 将赶上并更新其 l ，并重置 c 。

HLC 算法的描述如图4所示。初始设置 l 和 c 的值为 0 。在节点 j 上创建一个新发送事件 f 时，设置 l.j 为 max(l.e, pt.j) ，其中 e 是发生在 j 上的先前事件。类似于简易算法，这确保 l.j ≥ pt.j 。然而，由于移除“+1”导致 l.e 可能等于 l.f 。因此引入了不断增长的 c.j ，以确保 (l.e, c.e) < (l.f, c.f) 在字典比较中为真。如果 l.e 不等于 l.f 则重置 c.j 。这确保 c.j 的值是有界的。创建一个新接收事件时，设置 l.j 为 max(l.e, l.m, pt.j) 。c.j 的值取决于 l.j 是否等于 l.e ，l.m ，二者全部，或都不等于。

字典比较方式
(a, b) < (c, d) iff ((a < c) ∨ ((a = c) ∧ (b < d)))

算法解释：

初始 l.j 、c.j 都等于 0 。
将之前的逻辑时间戳 l.j 赋值给临时变量 $l^{{}^{\prime }}.j$ ，$l^{{}^{\prime }}.j$ 的值可能为 0 （第一次运行）或 pt.j 。新发送或本地事件的逻辑时间戳 l.j 等于保存之前逻辑时间戳的临时变量 $l^{{}^{\prime }}.j$ 和 物理时钟 pt.j 中的最大值。
a) 第一次运行时，$l^{{}^{\prime }}.j$ = 0 , l.j = max($l^{{}^{\prime }}.j$, pt.j) = pt.j, c.j = 0 , (l.j, c.j) = (pt.j, 0) ；
b) 而后，如果节点 j 上暂未发生接收事件，则 $l^{{}^{\prime }}.j$ = l.j = pt.j_prior, l.j = max($l^{{}^{\prime }}.j$, pt.j) = pt.j, c.j = 0 , (l.j, c.j) = (pt.j, 0) ；
如果节点 j 上发生过接收事件，则 $l^{{}^{\prime }}.j$ = l.j = pt.j_prior, l.j = max($l^{{}^{\prime }}.j$, l.m, pt.j),
c) 如果此时 $l^{{}^{\prime }}.j$ = l.m = pt.j ，则证明接收消息的逻辑时钟 l.m = $l^{{}^{\prime }}.j$ > pt.j ，即已知的逻辑时钟等于接收到的消息的逻辑时钟，且大于此时的物理时钟。为了使接收事件的 HLC 元组 (l.j, c.j) > (l.m, c.m) ，则应设置 c.j = max(c.j, c.m) + 1 ；
d) 否则，如果 l.j = $l^{{}^{\prime }}.j$ ，则证明 $l^{{}^{\prime }}.j$ > l.m 且 $l^{{}^{\prime }}.j$ ≥ pt.j 。为了使接收事件的 HLC 元组 (l.j, c.j) > ($l^{{}^{\prime }}.j$ , c.j) ，则应设置 c.j = c.j + 1 ；
e) 否则，如果 l.j = l.m ，则证明 l.m > $l^{{}^{\prime }}.j$ 且 l.m ≥ pt.j ，为了使接收事件的 HLC 元组 (l.j, c.j) > (l.m, c.m) ，则应设置 c.j = c.m + 1 ；
f) 否则，即 l.j = pt.j ，则证明 pt.j > l.m 且 pt.j > $l^{{}^{\prime }}.j$ ，则此时应重置 c.j 为 0 ；
如果发生接收事件后，又发生了新的发送或本地事件，则
g) 此时 $l^{{}^{\prime }}.j$ > pt.j，所以 l.j = max($l^{{}^{\prime }}.j$, pt.j) = $l^{{}^{\prime }}.j$ ，为了使新的发送或本地事件的 HLC 元组 (l.j, c.j) > ($l^{{}^{\prime }}.j$, c.j) ，则应设置 c.j = c.j + 1 。

5. HLC 的优势

• HLC 可看做是 HT（HybridTime） 的逻辑时钟版本，HLC 对物理时钟（与 **PT（Physical Time）和TT（TrueTime）**类似）和逻辑时钟（与 LC 类似）进行组合、改进。HLC 维护它的逻辑时钟使其永远接近于物理/NTP时钟。因此，它可以在某些应用中用作物理/NTP时钟的替代，比如分布式键值仓库或数据库中的快照读。
• HLC 向后兼容 NTP，并适用于 64位 NTP 时间戳。
• HLC 对 NTP 扭结（kinks）和不确定性具有屏蔽容忍。HLC 也是自稳定容错的，并且对时钟变量的任意损坏具有迅速可恢复性。
• HLC 在识别分布式数据库中的一致性快照方面具有直接应用。它在许多分布式系统协议中也很有用，包括分布式系统中的因果消息记录、拜占庭容错协议、分布式调试、分布式文件系统和分布式事务。例如，Spanner 的开源实现 CockroachDB 使用了 HLC ，详见 https://github.com/cockroachdb/cockroach 和 https://www.cockroachlabs.com 。

6. 其他知识

有关 LC, VC（Vector Clock，向量时钟）, PT, TT, HT 的信息，请参考 HLC 和其他相关文献。