分布式数据库里的时间戳

我们知道CAP中的C就是指Linearizability，它用于决定分布式系统中事件到达的绝对顺序，而不需考虑这些事件来自分布式系统中的哪个节点。假设在某个时间点t我们写入了一条数据比如a=2，那么在t之后，所有读到的都应该是2，而不是a以前的值。在单机系统里，这很容易做到，但在分布式系统里，就是很难决定的设计了。

再来谈谈ACID中的Serializability，这是个跟Linearizability很相关但又不完全一致的概念，毕竟ACID跟CAP是两个领域的范畴。它的含义是确保并发事务中的读和写操作跟顺序化访问没有区别，也就是任何并发事务都不能读取到事务A的任何中间写入状态，也没有任何事务能够让A读取到中间状态值。在单机数据库中，这两者实际上是等价的。在分布式环境下，假定有两个节点node1和node2，两个事务A和B。node 1的时钟快100ms。事务A写入到node 1，提交的事务具有时间戳t=100ms。假定观察者看到A提交事务后在50ms后启动事务B。事务B写入到node 2并且伴随时间戳t=50ms，那么任何观察者都将看到相反的时序(既B写入发生在A写入之前)。因此在分布式数据库中，Serializability相比Linearizability，它的保证要弱一些，因为它并没有确保数据库事务的顺序是按照一个绝对时序来进行，而是可能有多个不同的全局顺序，所以Serializability并没有针对时序有任何约束。因此，很多分布式数据库所提到的Serializability其实是指Strong Serializability，也就是Serializability+Linearizability。

因此，时序对于分布式系统，特别是分布式数据库的设计是非常关键的因素。如何让分布式节点之间知晓事件的时序呢？最简单能想到的手段就是时间。由于不同机器的时间是不一样的，尽管能够通过NTP协议进行时间戳校对，但我们并不能使用系统时间来判断事件的先后顺序。

1978年Lamport发明了逻辑时钟的概念用来确认分布式系统的时序。逻辑时钟就是不断增长的数字，如果两个事件a，b的逻辑时钟clock(a)<clock(b)，那么a一定发生在b之前。例如：a在node 1发生，b在node 2发生，a发生之后，node 1会给node 2发送消息，同时会带上clock(a)，node 2接受到消息之后再处理b，如果node 2当前的逻辑时钟小于或者等于clock(a)，那么会将自己的逻辑时钟更新为大于clock(a)的值，比如clock(a) + 1。这时候再执行b，就一定是clock(b)>clock(a)了。

逻辑时钟的原理是非常简单的，但是它没有实际的物理时间概念，所以如果想根据真实时间来查询相关事件，就办不到了。

Google Spanner通过引入GPS+原子钟来对集群的机器进行校时从而做到Linearizability，精度误差范围控制在ms级别，通过一套TrueTime API给集群使用。Spanner是如何采用TrueTime来达到Linearizability的呢？非常简单——等待。在一个节点获得准许汇报一个事务已经提交之前，它必须等待7ms。因为系统中所有的时钟误差在7ms以内，等待7ms意味着没有其它事务能够以较早的时间戳提交。这么说有些难以理解，我们假设TrueTime的时间误差是ε，假设事务a发生的时间是t_a，那么t_a的偏差范围在Spanner中是[t_a-ε,t_a+ε]。对于另一个事务b，只要它的最小误差t_b-ε大于t_a+ε，那么就可以确定事务b一定发生在b之后，从而不会造成事务冲突。但Spanner的TrueTime是基于硬件的，对于很多企业来说，是没有办法搞定这套部署的。

CockroachDB蟑螂数据库采用混合逻辑时钟HLC来解决这个问题。HLC由两部分组成，物理时钟和逻辑时钟。l.j维护的是节点j当前已知的最大的物理时间，c.j则是当前的逻辑时间。那么判断两个事件的先后顺序就很容易了，先判断物理时间，再判断逻辑时间。HLC的算法如下，在节点j上面：初始化: l.j = 0，c.j = 0。给另一个进程发送或者处理自己的事件流程如下：

当CockroachDB开始事务时，它基于当前节点选取时间戳t，同时保有最大时钟偏移t+offset。当事务从不同节点读取数据时，只要没有碰到在该时间戳和最大时钟偏移内发生键值冲突的事务，就都很容易处理。因此这个最大偏移内的时间窗口内事务拥有冲突不确定性。当冲突发生时，事务需要重启，但重启后事务依据逻辑时间戳设置，而最大偏移t+offset值在事务重启后也保持不变，因此不确定的时间窗口会缩短，从多个节点读取键值的事务可能需要多次重启。跟Spanner相比，CockroachDB是在读取之前等待，而Spanner是在写入之后等待，并且Spanner等待很短的时间，而CockroachDB则可能在读取之前等待较长时间。HLC毕竟是基于NTP的，所以如果NTP出现了问题，会导致HLC与当前系统物理时间的误差过大，从而影响CockroachDB的响应延迟。

CockroachDB也提供命令行参数(--linearizable)来提供跟Spanner类似的等待机制实现Linearizability，对于采用NTP协议同步时间的硬件来说，这样做开销很大。未来如果Google开源其原子钟的硬件方案，也许可以造福众公司。

还有一种手段来确定全局时序，如果没有跨全球的要求，采用集中式的授时服务也可以起到类似的作用。这种思路在Google Percolator中采用，称为TimeStamp Oracle(TSO)，也就是说集群所有节点都从TSO获取时间戳，因此TSO本身在设计上需要高性能，以及考虑容错。目前Omid，Themis，TiDB等项目都是采用TSO手段来做全局时间戳服务，而其它大多数实现分布式事务的数据库，如AtlasDB，也大体上是类似的思路。

事务和时间戳的关系本号以前略有提及，比如原文链接，还有AtlasDB介绍等。更进一步的介绍未来再继续。