分布式数据库 MVCC 技术探秘（二）：混合逻辑时钟

上篇文章< 分布式数据库MVCC技术探秘 (1) > 介绍了 Snapshot Isolation 与 逻辑时钟 ，这篇文章介绍 混合 逻辑时钟 。

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

（1）

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

下面是这个算法的伪码表示，其中，混合逻辑时钟的时间戳使用两个值l,c来表示，物理时钟用pt表示：

该算法源自论文《 Logical Physical Clocks and Consistent Snapshots in Globally Distributed Databases 》。混合逻辑时钟实现了单向的因果检测和排序，同时能够修正时间不一致带来的偏差。我们再来看看论文中的一个例子：

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

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

（2）

接下来，我们看看混合逻辑时钟存在的问题。

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

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

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

如果把进程理解成系统的一个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 之间没有交互，两者之间的混乱逻辑时钟没有因果检测和修正时间，在物理时钟的偏差范围内就存在 Session2的开始时间要早于Session1的提交时间的可能 ）。

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

这带来一个新的问题：系统执行结果的正确性是否依赖事务之间的先后顺序（同一个session 之间的事务的先后顺序可以保证，但是不同的session之间的先后顺序无法保证）。那应该如何 保证不同的session之间的事务执行的顺序？两种可能的解决方法：

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

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

方法1虽然能解决问题，但对现有系统的入侵性太大，因此并不实用。方法2似乎只有Google True Time可以很好的解决。

总结

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