MVCC事务机制：混合逻辑时钟

在前篇文章《MVCC事务机制2：逻辑时钟》中讲到，逻辑时钟可能造成人在物理视角理解事务顺序的不一致性，而物理时钟虽然符合人的物理视角的一致性，但是没有办法保持整个系统（分布式）时钟的一致性。混合逻辑时钟则尝试着解决物理时钟和逻辑时钟存在的问题。

混合逻辑时钟算法

混合逻辑时钟为了解决逻辑时钟和物理时钟的问题，提供了单向的因果序列检测和排序能力（逻辑时钟能力），同时保持时钟接近物理时钟。在系统事件时间戳上描述采用了因果序列和物理时钟的组合，而不是单纯的物理时间或者单纯的因果序列。 其算法还是非常简单：

混合逻辑时钟的一个时间戳使用两个值来表示 l，c
 Initially l.j :=0; c.j:0
 Send or local event
    l’.j : =l.j
    l.j = max(l’.j, pt.j)
    if (l.j = l’.j) then c.j := c.j+1
    else  c.j = 0
    timestamp with = l.j c.j
   
Receive event of message m
   l’.j := l.j 
   l.j := max(l’.j, l.m, pt.j )
   if (l.j = l’.j = l.m) then c.j: max (c.j,c.m) +1
   else if (l.j =l’.j) then c.j := c.j+1
   else if (l.j = l.m) then c.j =c.m + 1
   else c.j := 0
   timestamp with l.j c.j
pt 为物理时钟

更多详细信息可以参考论文《Logical Physical Clocks and Consistent Snapshots in Globally Distributed Databases》。由上面算法可知，混合逻辑时钟实现了单向的因果检测和排序，同时能够修正时间不一致带来的偏差。我们来看一个论文中的例子：

从算法可以很清楚知道，它让混合逻辑时钟表示物理时钟的值尽量与本地节点的物理时钟保持一致，但是不依赖本地的物理时钟，同时不用担心本地时钟的回退，如果和NTP结合使用时，又不用担心NTP 跳变带来的问题；混合逻辑时钟表示的逻辑时钟值是一个绝对值。 与Google True Time相比，不存在 True Time的overlap问题。

于是在诸多好处前景下，混合逻辑时钟在很多数据库中和一些分布式系统中得到广泛的应用，比如CockroachDB，HDFS（一致性快照）。

我们再看看它的问题。

问题

由算法可理解，混合逻辑时钟算法其实只关心两种情况的先后顺序：

• 在同一个进程或者线程中发生的事件的前后顺序

• 进程之间发送消息与接收消息这两个事件的前后顺序

如果把进程理解成系统的一个session，它内部的逻辑时钟能够保证session内事件的顺序，比如在同一个session的先执行事务1，再执行事务2，我们会认为事务2一定是在事务1结束（提交或许abort）后开始执行的。 但是出现了跨session，特别是这个session 在系统外的节点（application 调用系统的接口）这个前后关系就很难得不到保证。举个例子：

• session1 session2 都在分布式系统内的节点，而Application部署在分布式节点之外的节点上。

• 在物理时间上：Application先在session1 执行txn1，Application接收到txn1 committed消息后，再在session2 上执行txn2. Application在物理视角看起来，txn2的开始时间一到晚于txn1的提交时间。

• 在逻辑时钟上， 完全有可能存在session2 的开始时间要早于session1 的提交时间。

混合逻辑时间可以让逻辑时钟的值尽量等于本地物理时钟的值，但是它从本质上还是逻辑时钟的算法，在物理时钟的偏差范围内，依然存在上述问题。

这带来一个新的问题：系统执行结果的正确性是否依赖事务之间的先后顺序（同一个session 之间的事务的先后顺序可以保证，但是不同的session之间的先后顺序无法保证）。

但是，如果要保证不同的session之间的事务执行的顺序，怎么办？两种可能的解决方法：

1. 把Application的节点包含在逻辑时钟的分布式系统之内。

2. 使用带时间窗口的混合逻辑时钟。

方法1对系统的入侵性太大，虽然能够解决问题，但是太不实用。方法2似乎只有Google True Time解决了，可惜没有开源。

总结

混合逻辑时钟可以保证同一个process内部事件的先后顺序，但是解决不了系统外事件发生逻辑前后顺序与物理时间前后顺序的一致性。即使存在这样的问题，Cockroach依然还在使用该机制，下篇文章讲介绍Cockroach mvcc实现流程。

本文源自：NoSQL漫谈(nosqlnotes.com)
除非特别注明，本站文章均为原创，未经授权，严禁转载。

推荐阅读：

MVCC事务机制：Snapshot Isolation

MVCC事务机制：逻辑时钟