计算机处理时钟有两种方式，一种是物理时钟，包括NTP协议和TrueTime都属于物理时钟，另一种是逻辑时钟，包括Lamport逻辑时钟和向量时钟。这两种时钟有各自的优缺点。物理时钟的优点在于直观，就是真实世界的时间，使用方便，缺点在于无法做到绝对精确，成本相对高一些。逻辑时钟的优点在于可以做到精确的因果关系，缺点在于节点之间需要通信，而且使用上不如物理时钟直观。

本文介绍的混合逻辑时钟（HLC）将物理时钟和逻辑时钟结合起来。

HLC介绍

HLC由Sandeep Kulkarni, Murat Demirbas, Deepak Madeppa, Bharadwaj Avva, and Marcelo Leone在2014年的论文Logical Physical Clocks中提出。目的是为了填补理论（逻辑时钟）和实际（物理时钟）之间差距，支持因果关系，同时又有物理时钟的直观特点。

给分布式系统中每一个事件分配一个HLC，比如e事件的HLC记作l.e，HLC保证能够满足一下四个性质：

  1. 如果e事件发生在f事件之前（e happened before f），那么l.e一定小于l.f，也就是满足因果关系。
  2. l.e可以存储在一个整数中，不会随着分布式系统中节点数的增加而增加。（这点和向量时钟不一样，向量时钟会随着节点数的增加而增加）
  3. l.e的值不会无限增长。（这点和Lamport逻辑时钟不一样，Lamport逻辑时钟会无限增长）
  4. l.e的值个和e事件发生的物理时钟接近，| l.e - pt.e |的值会小于一定的范围。

第一版算法

Lamport逻辑时钟算法：

记事件j的逻辑时钟为l.j

1
2
3
初始化：l.j = 0
发生消息事件或者本地事件：l.j = l.j + 1
接受m消息事件：l.j = max(l.j, l.m) + 1

如果想在算法中引入物理时钟，最简单的做法是每次修改逻辑时钟的时候，比较逻辑时钟和物理时钟的大小，取最大的值。

记事件j发生时的物理时钟值为pt.j，算法变成了：

1
2
3
初始化：l.j = 0
发送消息事件或者本地事件：l.j = max(l.j + 1, pt.j)
接受m消息事件：l.j = max(l.j + 1, l.m + 1, pt.j)

从算法中可以很容易地看出满足上面说的HLC性质1和2。然而算法不满足性质3和性质4。举个例子：

图1

分布式系统中有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协议的物理时钟值。

对于事件j，本地物理时钟为pt.j，感知到的最大物理时钟为l.j，逻辑时钟为c.j，新的算法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
初始化：l.j = 0; c.j = 0
发送消息事件或者本地事件：
	if pt.j <= l.j
  	    c.j = c.j + 1
	else 
	    c.j = 0
  	    l.j = pt.j
接收m消息事件：
	// 如果j事件，m消息和本地物理时钟的值相同，增加逻辑时钟部分
	if l.j == l.m == pt.j
  	    c.j = max(c.j, c.m) + 1
	// 如果本地物理时钟没赶上HLC的物理时钟，并且j事件的逻辑时钟更大，更新逻辑时钟的值
	else if pt.j <= l.j and l.m <= l.j
  	    c.j = c.j + 1
	// 如果本地物理时钟没赶上HLC的物理时钟，并且m消息的逻辑时钟更大，更新HLC的逻辑时钟部分和物理时钟部分
	else if pt.j <= l.m and l.j <= l.m
  	    c.j = c.m + 1
  	    l.j = l.m
	else 
  	    c.j = 0
  	    l.j = pt.j

新算法执行的过程中，本地时钟的值通过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协议，这个误差值在局域网内大概1ms内，广域网可能达到100ms或更大。

使用新算法来分析第一版算法中的例子：

图2

上图中，如果消息只在节点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论文中给出了HLC的性能数据。

图3

上图中，4个节点组成的系统，NTP的平均误差值offset分别设为5毫秒和1.5毫秒两种情况。在这两种情况下，HLC的逻辑时钟部分的值c < 4，保持了一个很低的值。在offset为5ms的情况下，|l - pt|的最大差距是21.7ms，90%的差距值小于7.8ms，平均差距是0.2ms。

图4

如果把节点数变成16个，NTP的平均误差offset分别设为16ms和6ms两种情况。c < 8，依然保持了一个很低的值。从图中可以看出offset越小，c的值整体会更小。

HLC应用

HLC可以用于分布式数据库一致性快照读的处理中。很多系统都使用了HLC，比如HBase和CockRoachDB。

图5

比如，我们要获取t=10这个时间点的数据快照，也即HLC为(l=10, c=0)，拿这个HLC值去每个节点查找，可以得出上图中黑色的粗线，这条线对应的数据就是系统在t=10时的数据快照。

CockRoachDB在分布式事务中使用HLC。根据HLC的性质4，|l.e - pt.e|的值会小于一定的范围MaxOffset，CockRoachDB默认这个值为500ms，pt.e + MaxOffset一定是系统中最大的物理事件。启动事务时会获取本地的HLC值hlc.e，并且确定一个区间[hlc.e, hlc.e + MaxOffet]，然后发往其他节点执行快照读，如果节点上某个数据的HLC值为hlc.g，分三种情况考虑：

  1. 如果hlc.e + MaxOffset < hlc.g，即处于区间的右边，那么e事件肯定发生在g事件之前，不能读取这个数据。
  2. 如果hlc.e + hlc.g <= hlc.e + MaxOffset，即处于区间之中，由于物理时钟的不确定性，不能分辨出e事件和g事件的先后关系。这个时候需要重启事务，获取一个更大的hlc，相当于等待这个不确定的事件过去，推迟事务的执行。
  3. 如果hlc.g < hlc.e，那么g事件肯定发生在e之前，这时可以读取这个数据。

参考文献

[1] Logical Physical Clocks