计算机的时钟（五）：混合逻辑时钟
本系列文章主要介绍计算机系统中时钟的处理。主要内容包含 NTP，Lamport 逻辑时钟，向量时钟，TrueTime 等。本文是第五篇，介绍混合逻辑时钟(Hybrid Logical Clocks)。
（封面图片来自 mana5280）
在本系列前面的文章中我们介绍了计算机处理时钟的两种方式，一种是物理时钟，包括 NTP 协议和 TrueTime 都属于物理时钟，另一种是逻辑时钟，包括 Lamport 逻辑时钟和向量时钟。这两种时钟有各自的优缺点。物理时钟的优点在于直观，就是真实世界的时间，使用方便，缺点在于无法做到绝对精确，成本相对高一些。逻辑时钟的优点在于可以做到精确的因果关系，缺点在于节点之间需要通信，而且使用上不如物理时钟直观。
本文介绍的混合逻辑时钟(HLC)将物理时钟和逻辑时钟结合起来，我们来看看它是怎么一回事。
HLC 介绍
HLC 由 Sandeep Kulkarni, Murat Demirbas, Deepak Madeppa, Bharadwaj Avva, and Marcelo Leone 在 2014 年的论文《Logical Physical Clocks and Consistent Snapshots in Globally Distributed Databases》中提出。目的是为了填补理论（逻辑时钟）和实际（物理时钟）之间的差距，支持因果关系，同时又有物理时钟的直观特点。
给分布式系统中每个事件分配一个 HLC，比如 e 事件的 HLC 记作 l.e，HLC 保证能够满足以下四个性质：
如果 e 事件发生在 f 事件之前（e happened before f），那么 l.e 一定小于 l.f，也就是满足因果关系。
l.e 可以存储在一个整数中，不会随着分布式系统中节点数的增加而增加。（这点和向量时钟不一样，向量时钟会随着节点数的增加而增加）
l.e 的值不会无限增长。（这点和 Lamport 逻辑时钟不一样，Lamport 逻辑时钟会无限增长）
l.e 的值和 e 事件发生的物理时钟值接近，| l.e - pt.e |的值会小于一定的范围。
第一版算法
回顾之前介绍过的 Lamport 逻辑时钟算法：
记事件 j 的逻辑时钟为 l.j
如果想在算法中引入物理时钟，最简单的做法是每次修改逻辑时钟的时候，比较逻辑时钟和物理时钟的大小，取最大的值。
记事件 j 发生时的物理时钟值为 pt.j，算法变成了：
从算法中可以很容易地看出满足上面说的 HLC 性质 1 和 2。然而算法不满足性质 3 和性质 4。举个例子：
分布式系统中有 4 个节点，每个矩形中左边的数字是本节点的物理时钟 pt，右边是本节点的逻辑时钟 l。消息从节点 0 依次到节点 1，节点 2，节点 3，再到节点 1。到了节点 1 的时候，从图中可以看到物理时钟和逻辑时钟的差距 |l - pt| 是 13。如果整个系统中事件发生的频率比较高，可以想象到，物理时钟和逻辑时钟的差距会越来越大。这违反了性质 3 和性质 4。
为什么会发生这个问题？原因是虽然在 Lamport 逻辑时钟的基础上引入了物理时钟，但是我们却不知道这个值究竟是物理时钟增长导致的还是逻辑时钟增长导致的。这样即使物理时钟的增长追赶上了逻辑时钟的增长，我们也没办法重置逻辑时钟部分的值。
第一版算法凉凉。
第二版算法
为了解决这个问题，很自然地想到把物理时钟和逻辑时钟分开来表示。我们把 HLC 分成两部分 l.j 和 c.j。l.j 表示事件 j 发生时所感知到的最大物理时钟值，c.j 是事件 j 的逻辑时钟部分，当几个事件在同一个物理时钟值内发生时，c 用于记录事件之间的因果关系。pt 依然表示本地 NTP 协议的物理时钟值。新的算法如下：
新算法执行的过程中，本地时钟的值通过 NTP 协议更新，HLC 的值并不会修改本地时钟的值。由于分离了物理时钟和逻辑时钟，新的事件发生时，如果物理时钟部分的值没增长，就只增加逻辑时钟部分的值。如果本地的物理时钟赶上了 HLC 的物理时钟部分的值 l.j，就可以重置逻辑时钟部分的值 c.j，并把 l.j 更新为新的本地物理时钟。这样就可以解决第一版算法中 HLC 无限增长的问题，也满足了性质 3 和性质 4 的要求。具体数学证明过程参考论文。
对于任何一个事件 j，pt.j <= l.j，也即 HLC 的物理时钟部分的值一定大于等于本地 NTP 的时钟值。假设整个分布式系统中，NTP 协议的时钟误差值为 ε。新算法中，对于任何一个事件 j，| l.j - pt.j | <= ε，也就是 HLC 物理部分的值和本地物理时钟值的差距不会超过 ε。根据前文计算机的时钟（一）：NTP协议的介绍，这个误差值在局域网内大概 1 毫秒内，广域网可能达到 100 毫秒或更大。
使用新算法来分析第一版算法中的例子：
上图中，如果消息只在节点 123 之间流动，HLC 的物理时钟部分 l.j 会一直保持为 10，c.j 部分会不断增长，直到节点 123 中任何一个的 NTP 时钟值超过 10，这时会将 c.j 重置为 0。
工程实现上，HLC 可以设置成 64 比特的整数，高位 48 比特是以毫秒为单位的物理时间。低位 16 比特是一个单调增长的整数，最大 65535。整体结构有点像雪花算法生成的唯一 ID。
HLC 的异常处理
如果某个节点的 NTP 物理时钟值出现了异常，比如变成一个极大的值，其他节点收到这个故障节点的消息，会导致其他节点的 HLC 值出现问题。为了阻止故障的扩散，可以设置 HLC 物理部分偏差的上限，如果收到的消息物理部分值的偏差超过上限，忽略这条消息，同时发送告警等待人工处理。
HLC 的性能数据
论文中给出了 HLC 的性能测试数据。
上图中，4 个节点组成的系统，NTP 的平均误差值 offset 分别设为 5 毫秒和 1.5 毫秒两种情况。在这两种情况下，HLC 的逻辑时钟部分的值 c < 4，保持了一个很低的值。 在 offset 为 5 毫秒的情况下，| l - pt | 的最大差距是 21.7 毫秒，90%的差距值小于 7.8 毫秒，平均差距是 0.2 毫秒。
如果把节点数变成 16 个，NTP 的平均误差值 offset 分别设为 16 毫秒和 6 毫秒两种情况。c < 8，依然保持了一个很低的值。从图中可以看出 offset 越小，c 的值整体会更小。
HLC 应用
HLC 可以用于分布式数据库一致性快照读的处理中。很多系统中都使用了 HLC，比如 HBase 和 CockRoachDB。
比如，我们要获取 t = 10 这个时间点的数据快照，也即 HLC 为(l = 10, c = 0)，拿这个 HLC 值去每个节点查找，可以得出上图中黑色的粗线，这条线对应的数据就是系统在 t = 10 的数据快照。
CockRoachDB 在分布式事务中使用了 HLC。根据 HLC 的性质 4，| l.e - pt.e |的值会小于一定的范围 MaxOffset，CockRoachDB 默认这个值为 500 毫秒，pt.e + MaxOffset 一定是系统中最大的物理时间。启动事务时会获取本地的 HLC 值 hlc.e，并且确定一个区间 [ hlc.e, hlc.e + MaxOffset ]，然后发往其他节点执行快照读，如果节点上某个数据的 HLC 值为 hlc.g，分三种情况考虑：
如果 hlc.e + MaxOffset < hlc.g，即处于区间的右边，那么 e 事件肯定发生在 g 事件之前，不能读取这个数据。
如果 hlc.e < hlc.g <= hlc.e + MaxOffs，即处于区间之中，由于物理时钟的不确定性，不能分辨出 e 事件和 g 事件的先后关系。这个时候需要重启事务，获取一个更大的 hlc，相当于等待这个不确定的时间过去，推迟事务的执行。
如果 hlc.g < hlc.e，那么 g 事件肯定发生在 e 之前，这时可以读取这个数据。（对于这点我有点疑问，由于不确定时间的存在，物理时间可能快，也可能慢，这个区间应该是[ hlc.e - MaxOffset, hlc.e + MaxOffset ]，为什么这里 hlc.g < hlc.e 就认为 g 在 e 前面？）
总结
整个系列一直在物理时钟和逻辑时钟之间打转。先介绍了最直观的 NTP 协议，由于 NTP 协议的不可靠性，引入了逻辑时钟，包括 Lamport 逻辑时钟和向量时钟，但是逻辑时钟只能确保因果关系，并且需要消息的传递，由此又引入了更精确的物理时钟 TrueTime，最后是把物理时钟和逻辑时钟结合起来的混合逻辑时钟。
参考
Logical Physical Clocks and Consistent Snapshots in Globally Distributed Databases
版权声明: 本文为 InfoQ 作者【ElvinYang】的原创文章。
原文链接:【http://xie.infoq.cn/article/71238dad20e6d880b4c26e39f】。
本文遵守【CC-BY 4.0】协议，转载请保留原文出处及本版权声明。
每个人的一生都是一次远行 2020.05.11 加入
喜欢天文历史滑雪潜水的程序员，个人博客地址 https://yang.observer
评论