分布式系统的时间(2)

但spanner有一个最大的问题,TrueTime是基于硬件的,而现在对于很多企业来说,是没有办法搞定这套部署的。所以如果Google能将TrueTime的硬件设计开源,那我觉得更加造福社区了。

Hybrid Logic Clock

既然TrueTime这种硬件方案很多人搞不定,那么我们就采用软件方案了。

Cockroachdb使用了Hybrid Logic Clock(HLC)来解决分布式时间的问题。

HLC是基于NTP的,但它只会读取当前系统时间,而不会去修改,同时HLC又能保证在NTP出现同步问题的时候仍能够很好的进行容错处理。对于一个HLC的时间t来时,它总是大于等于当前的系统时间,并且与其在一个很小的误差范围里面,也就是 |l - pt| < ε。

HLC由两部分组成,physical clock + logic clock,l.j维护的是节点j当前已知的最大的物理时间,c.j则是当前的逻辑时间。那么判断两个事件的先后顺序就很容易了,先判断物理时间pt,在判断逻辑时间ct。

HLC的算法如下,在节点j上面:

初始化: l.j = 0, c.j = 0

给另一个进程发送或者处理自己的事件:

l'.j = l.j; // 跟当前系统时间比较,得到pt l.j = max(l'j, pt.j) // 如果pt没有变化,则c.j加1,如果有变化,因为这时候 // 铁定PT变大了,所以我们可以将ct清零 if (l.j = l'.j) { c.j = c.j + 1 } else { c.j = 0 } // Timestamp with l.j, c.j

接受某一个节点m的消息事件

l'.j = l.j; // 跟当前系统事件以及节点m的pt比较,得到pt l.j = max(l'.j, l.m, pt.j) if (l.j = l'.j = l.m) { // pt一样,获取最大的ct,并加1 c.j = max(c.j, c.m) + 1 } else if (l.j = l'j) { // 这里表明j原来的pt比m大,只需要增加ct c.j = c.j + 1 } else if (l.j = l.m) { // 这里表明m的pt比j原来的要大,所以直接可以用m的ct + 1 c.j = c.m + 1 } else { // pt变化了,ct清零 c.j = 0 } // Timestamp with l.j, c.j

具体的实现算法,可以看cockroachdb的HLC实现

HLC虽然方便,它毕竟是基于NTP的,所以如果NTP出现了问题,可能导致HLC与当前系统pt的时间误差过大,其实已经不怎么精确了,HLC论文提到对于一些out of bounds的message可以直接忽略,然后加个log让人工后续处理,而cockroachdb是直接打印了一个warning log。

Timestamp Oracle

无论上面的Ture Time还是Hybrid Logic Time,都是为了在分布式情况下获取全局唯一时间,如果我们整个系统不复杂,而且没有spanner那种跨全球的需求,有时候一台中心授时服务没准就可以了。

在Google Percolator系统这,他们就提到使用了一个timestamp oracle(TSO)的服务来提供统一的授时服务,为啥叫oracle,我猜想可能底层用的就是oracle数据库。。。

使用TSO的好处在于因为只有一个中心授时,所以我们一定能确定所有时间的时间,但TSO需要关注几个问题:

网络延时,因为所有的事件都需要从TSO获取时间,所以TSO的场景通常都是小集群,不能是那种全球级别的数据库。

性能,TSO是一个非常高频的操作,但鉴于它只干一件事情,就是授时,通常一个TSO每秒都能支持10w+以上的QPS,而这个对很多应用来说是绰绰有余的。

容错,TSO是一个单点,所以不得不考虑容错,而这个现在基于zookeeper,etcd也不是特别困难的事情。

所以,如果我们没法实现TrueTime,同时又觉得HLC太复杂,但又想获取全局时间,TSO没准是一个很好的选择,因为它足够简单高效。

我们现在的数据库产品就使用的是TSO方案,但也不排除以后为了支持全球同步,而考虑使用TureTime或者HLC的方案。

最后

在分布式领域,我们很自然的会想到用时间来解决事件的时序问题,但如何保证时间的获取是全局一致并且正确的,并不是一件容易的事情,笔者认为,只要能搞定时间问题,后面编写Linearizability的系统就比较容易了。当然,如果我们还需要支持分布式事务,还有更多的事情需要考虑的,如果后面有时间,在慢慢总结吧。

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/da9e862b38b6daec1d786a601e9ad142.html