混合逻辑时钟

本文将首先依次简单介绍分布式系统下的物理时钟（Physical Time，也称PT），逻辑时钟（Logical Clock，也称LC），向量时钟（Vector Clock，也称VC），真实时钟（True Time，也称TT）的基本概念，然后着重笔墨介绍混合逻辑时钟（Hybrid Logical Clock，也称HLC）

物理时钟-Physical Time, PT

物理时钟即机器本地的时钟，而由于设备硬件不同，本身存在偏差，一天的误差可能有毫秒甚至秒级，所以需要对不同的机器时钟进行同步使得机器的时间进行相对统一。NTP是目前比较常用的同步时间的方式，其机制为CS架构，每台机器上存在一个NTP的客户端，与NTP的服务端进行同步，校准本地的时间。关于NTP具体的设计细节本文不做详细介绍，需要知道的是，由于NTP走网络传输，势必会导致同步后的物理时钟与远程NTP服务器的时钟存在一定的偏差。

逻辑时钟-Logical Clock, LC

在分布式场景下不同机器的时间存在不一致，那么跨节点的时间无法确定先后关系，所以Lamport提出了逻辑时钟（Logical Clock）的概念，通过happened-before（hb）关系确定事件的逻辑时钟，happened-before（hb）是基于信息传递而不是时间传递来定义的。

  • 如果事件A和事件B串行发生，且事件A在B之前发生，那么A happened before B
    • A hb B
    • A -> B
    • C(A) <C(B)
  • 如果事件A和事件B位于2个进程内，A是消息的发送事件，B是消息的接受事件。那么A hb B

对于捕获happened-before（hb），LC假设所有通信都发生在当前系统中，并且没有反向通道。

逻辑时钟存在的问题

逻辑时钟定义的是一个全序关系，没办法准确表示出并发关系
使用 Lamport 时间戳，只是比较事件a和b各自的时钟值，无法说明它们之间的关系，即如果 a -> b，那么 C(a) < C(b)，但是 C(a) < C(b) 并不能说明 a -> b。也就是说C(a) < C(b) 是 a -> b 的必要不充分条件，我们不能通过 Lamport 时间戳对事件 a、b 的因果关系进行判断。

在进程A中（如下图所示），我们无法知道进程B中的数据X的时钟已经高过了3，所以并不会主动让最后发生的数据更新事件A3有高于3的时间。
分布式数据库--混合逻辑时钟 - 图1
所以可以认为，因为进程无法记录其他进程内数据的时间版本，所以会造成这样的数据冲突。

  1. 假设进程B在完成B2事件后通知进程A：“进程B的数据X时钟变为了4”。那么进程A在完成A3之后就能感受到冲突。

向量时钟基于此思想，在一个进程内存储了所有其他进程的时钟备份，用于感受数据冲突

向量时钟-Vector Clock，VC

向量时钟（VC）是用来维持LC的向量化版本的。

向量时钟算法的内容：

在一个有 N 个节点的分布式数据库中，用一个 N 维的向量来表征时间，其中的某一个维表示一个节点的时间，这个时间向量按照以下规则进行处理：

  • 所有节点的初始时间向量都是0；
  • 每一次经历一个时间间隔，都要在各自的时间维度上加1；
  • 每次发送数据，都要将这个向量时间作为时间戳和数据一起发出去；
  • 每次节点收到了时间向量，都要比较该时间向量和自身时间向量，并取两者中每一维中的最大值，作为自身新的时间向量；
  • 当收到有冲突的更改时，比较这两次更改的时间向量：若存在偏序关系，则取偏序关系中时间向量较大的对应的值，并以此作为本节点新的时间向量；若不存在偏序关系，则不能合并；

其中的偏序关系是指：若A向量中的每一维都大于等于B向量，那么A，B向量之间存在偏序关系，否则不存在偏序关系。
举个例子：
A，B，C 三个节点的初始时间向量都是 (0,0,0)，该向量的一，二，三维分别对应 A，B，C 三个节点各自的时间。
4182554321-5874519bcd84b_fix732.png

  • A 作出更改 Key=Value1，时间向量变为 (1,0,0)；
  • A 的更改传输到了 B 处，B 处 Key=Value1， 且时间向量变为 (1,0,0)；
  • B 作出更改 Key=Value2， 将时间向量中自己对应的那一维加 1 变为 (1,1,0)；

  • B 和 A 的更改都同步到了 C 处。C 比较两者的时间向量 (1,0,0) 和 (1,1,0)，发现存在偏序关系，于是 C 的时间向量更新为 (1,1,0) 且 Key=Value2；

    向量时钟算法的实质

  • 将逻辑上可以合并的冲突成功合并；

  • 逻辑上无法合并的冲突依旧冲突；

真实时钟-True Time，TT

TrueTime由时钟硬件和算法组成。其中时钟硬件由GPS时钟和原子钟组成

TrueTime API

TrueTime提供了三个API来操作时间：

  • TT.now() 返回的是当前时间，由于时钟硬件误差的存在，这个当前时间存在一个不确定的范围(uncertainty time)，也即一个范围 [earliest, latest]，可以保证当前绝对时间一定在这个范围内，上面介绍过，这个间隔范围最大是7ms。
  • TT.after(t) 判断传入的时间戳是否已经是过去的时间，也即 t < TT.now().earliest。

  • TT.before(t) 判断传入的时间戳是否是未来的时间，也即 TT.now().latest < t。

    API 搭配的两个规则

  • Start： 提交事务Ti时，leader必须选择一个大于等于TT.now().latest的时间作为提交时间戳si。

  • Commit Wait： leader必须等待TT.after(si)为true后才能提交数据，也即必须等待si的绝对时间过去了才能提交数据。

使用这两个规则可以保证：如果事务 T1 提交后 T2 才开始，那么 T2 的提交时间一定晚于 T1 的提交时间。也就是说事务的提交顺序一定和事务发生的绝对时间上的顺序一致。

混合逻辑时钟-Hybrid Logical Clock，HLC

HLC时钟建立了因果关系模型，同时保持了与物理时间的关系。这里提到的物理时间 (physical time)，是当前节点的本地物理时间，由NTP等授时服务进行校准。注意，它与HLC 时间戳中的Wall Time不完全相同(有关系，但意义不同)。

HLC基本原理

  1. ---l.j   表示J发生时所感知到的最大物理时钟值 (WallTime)
  2. ---l.m   表示j发生时本地（即接收方）的最大物理时钟值 （WallTime）
  3. ---c.j   表示事件j的逻辑时钟部分
  4. ---pt.j  表示j发生时本地NTP协议的物理时钟值
  6. 初始化：l.j = 0; c.j = 0
  7. 1.发送消息事件或者本地事件：
  8.   if pt.j <= l.j then c.j = c.j + 1
  9.   ---如果物理时间小于或等于WallTime，那么分配的HLC时间戳的WallTime取HLC时钟当前WallTime，并且LogicTime在原有基础上加1；
  10.   else c.j = 0; l.j = pt.j
  11. ---如果物理时间大于WallTime，那么分配的HLC时间戳的WallTime取节点当前物理时间，并且LogicTime归零。
  13. 2.接收m消息事件：
  14.   if l.j == m.j == pt.j then c.j = max(c.j, c.m) + 1
  15.   ---如果三者相等，那么当前节点(即接收方)的WallTime不变，并且取当前节点的LogicTime和对端LogicTime最大的那个值加一作为当前节点的LogicTime；
  16.   else if pt.j <= l.j and l.m <= l.j then c.j = c.j + 1
  17.   ---如果对端WallTime最大，那么当前节点(即接收方)的WallTime被设置为对端WallTime，并且其LogicTime取对端LogicTime加1；
  18.   else if pt.j <= l.m and l.j <= l.m then c.j = c.m + 1; l.j = l.m
  19.   ---若本地WallTime最大，那么当前节点(即接收方)的WallTime不变，并且本地LogicTime在原有基础上加一；
  20.   else c.j = 0; l.j = pt.j
  21.   ---如果当前节点 (即接收方) 本地物理时间最大，那么分配的HLC时间戳的WallTime取节点当前本地物理时间，并且LogicTime归零

对于任何一个事件 j，pt.j <= l.j，也即HLC的物理时钟部分的值一定大于等于本地NTP的时钟值。

HLC的四个性质

给分布式系统中每个事件分配一个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 |的值会小于一定的范围。

    算法示例：

    分布式数据库--混合逻辑时钟 - 图3上图中，如果消息只在节点123之间流动，HLC的物理时钟部分 l.j 会一直保持为10，c.j 部分会不断增长，直到节点123中任何一个的NTP时钟值超过10，这时会将 c.j 重置为0。 工程实现上，HLC可以设置成64比特的整数，高位48比特是以毫秒为单位的物理时间。低位16比特是一个单调增长的整数，最大65535。

    时钟同步：

    QianBase xTP 需要时钟同步以保持数据的一致性，因此，当集群中任一节点检测到其本地时钟与其本地时钟与集群中至少一个其他节点不同步，并且这种不同步达到了允许的最大偏移量的80%啥时（默认为500毫秒），节点会自动关闭。这个最大偏移量由—max-offset启动参数设置。
    尽管无论时钟偏差如何，都可以保持可串行化的一致性，但是，如果时钟偏差超过配置的最大偏差量，可能会导致因果相关事务之间的单键线性化（single-key linearizability）收到破坏，导致读取到过期数据和写偏斜。因此，通过在每个节点上运行NTP或其他时钟同步软件来防止本地时钟偏差太大是有必要的。

    设置时钟同步时注意事项：

  • 集群中的所有节点必须同步到同一时间源，或者同步到以相同方式实现闰秒涂抹(leap second smearing)的不同时间源。
  • 可以使用chrony并启用客户端闰秒涂抹。
  • 不要在运行QianBase xTP实例的虚拟机上运行多个时钟同步服务。
  • 增加最大偏移量的值将增加故障恢复时间以及基于不确定性读取重复的频率。并且此值在所有节点必须相同，并且无法通过滚动升级进行修改，修改此值，首先需要停止集群中的每个节点，然后一旦整个集群脱机，用新值重新启动每个节点（默认为500毫秒）。

    HLC特性：

    —-兼容NTP：HLC使用 64bit 的NTP时间戳。HLC叠加在NTP协议上（只读取物理时钟，不对其进行更新），所以HLC与使用NTP的程序并行运行，并且不会发生干扰

—-通用性：不要求 server-client 架构，支持基于WAN的对等节点传输，支持节点使用不同的NTP server

—-异常容忍：HLC可以容忍常见的NTP异常，同步异常也可以确定因果关系，并且HLC 是自我稳定的，并且对破坏也能弹性容忍。

HLC结合了LC&PT的优势，并克服了它们的缺点，可以捕获因果顺序，并能提供在时钟偏移范围内的逻辑事件，HLC是单调递增的；同时HLC在多版本全局分布的数据库中具有无等待事务排序和快照读取的优点。

总结：

整个系列一直在物理时钟和逻辑时钟之间打转，先介绍了最直观的NTP协议，由于NTP协议的不可靠性，引入了逻辑时钟，包括Lamport逻辑时钟和向量时钟，但是逻辑时钟只能确保因果关系，并且需要消息的传递，由此又引入了更精确的物理时钟TrueTime，最后把物理时钟和逻辑时钟结合起来的混合逻辑时钟。