1、时钟同步的意义

我们通常所说的时间是物理时间,在计算机系统中,时间更多的应用场景是确认两个事件发生的先后顺序。在分布式系统中,两台计算机各自计算自己的时间,即使我们在初始配置时将两台计算机的时间调整为一致,由于受到物理环境的影响(气温、压强、湿度、晶体的寿命等),会导致晶振的频率产生差异,从而使得两台计算机仍然会出现时钟的差异。

时钟差异的产生从简单来理解,当我们分析一个问题时,从日志中无法分析出两台设备事件发生的先后顺序,进而对我们的分析产生干扰。如果时钟差异在多台设备之间是无法避免的,那么如何去区分多台设备之间事件发生的先后顺序,从而协调各设备完成分布式任务。所以如何保障系统的物理时钟尽可能的一致,是分布式系统需要解决的问题,如何保证多台设备之间事件发生的先后顺序,也是分布式系统需要去解决的问题。

这里需要引入两个概率,物理时钟与逻辑时钟。所谓物理时钟是指从系统时钟里获取的一个时间戳,而所谓逻辑时钟是指一个自定义的自增序列数值。下面分别介绍物理时钟同步与逻辑时钟的同步。

2、物理时钟同步

在计算机领域,常见的物理时钟同步的协议有如下几种:

  • NTP(Network Time Protocol--网络时间协议)
  • SNTP(Simple Network Time Protocol,简单网络时间协议)
  • PTP(Precision Time Protocol ,精准时间协议) IEC61588

这三种协议都是业界的标准,其主要应用场景和差异如下图所示:

3、逻辑时钟

    (1)Lamport时钟:Lamport 是美国的计算机科学家,他的成名代表作是PAXOS一致性协商协议。Lamport时钟的主要思路是:如果事件是发送消息,那么该事件的时间戳与消息一起发送。如果事件是收到消息,那么算法会比较进程的当前时间戳记计数器与接收到的消息中的时间戳。如果接收到的消息的时间戳大于或等于事件的时间戳,则当前时间戳记计数器会使用接收消息中的时间戳的值加1来更新。这确保接收到的事件的时间戳以及该进程上的所有其他时间戳将大于发送该消息的事件的时间戳,同时大于该过程中的所有先前消息的时间戳。

简单举例如下图所示:    应用Lamport时钟后,可以使得下面的结论成立:对于发生的两个事件, 当a < b,则L(a) < L(b),即确信两个因果关系事件将具有反映事件顺序的时间戳。可以看到Lamport时钟非常简单,如下图所示,事件h在Lamport因果意义上的事件m之前发生。因果事件链是 h → c, c → d和 d → m。由于发生之前的关系是可传递的,我们知道 h → m(h在m之前发生),Lamport时钟很好的反映了这一点。用于时间戳h(1)小于所述时间戳j(7)。然而,仅仅通过查看时间戳,我们不能断定在关系之前存在因果关系。例如,因为k(1)的时间戳小于i(3)的时间戳,并不意味着k在i之前发生 。这些事件可能是并发的,但我们无法通过Lamport时钟来辨别。此时,我们需要采用其他技术来做出决定,该技术就是向量时钟。

(2)向量时钟:

首先我们假设我们知道系统中总的进程数,那么向量时钟不是一个数字,而是一个数字向量,每个元素对应一个进程,每个进程都知道它在向量中的位置。例如,在下面的例子中,向量元素对应于进程(P 0,P 1,P 2)。

与Lamport算法一样,向量时间戳中的处理器对应的元素在将时间戳附加到事件之前递增。如果一个进程P 0有四个连续的事件a,b,c,d,它们将得到向量时间戳为(1,0,0),(2,0,0),(3,0,0),(4 ,0,0)。如果一个进程P 2有四个连续的事件a,b,c,d,它们将得到(0,0,1),(0,0,2),(0,0,3),(0 ,0,4)

如果事件是发送消息,则与该事件关联的整个向量与消息一起发送。当进程接收到消息时,接收进程将执行以下操作:

  • 增加向量中进程的计数器;
  • 将接收到的向量与进程的时间戳向量进行逐个元素的比较,将进程的时间戳记向量设置为更高的值;

并发:要确定两个事件是否并发,对相应的时间戳进行逐个元素的比较。如果时间戳V的每个元素小于或等于时间戳W的对应元素,则V因果关系位于W之前,并且事件不是并发的。如果时间戳V的每个元素大于或等于时间戳W的相应元素,则W因果关系在V之前,并且事件不是并发的。当这些条件都不适用,并且V中的某些元素大于W并且其他元素小于W中的相应元素,则两个事件是我们称之为是并发的。

回到开头的假设,实际系统中,我们可能不知道总的进程,即使我们知道,如果用一个超大向量来表示,没有任何意义,因为大多进程之间可能不会发送消息,于是我们的算法调整如下:

我们可以用一组元组来替换向量,每个元组代表一个进程ID和它的计数器:

({P 0,6},{P 1,3},{P 2,2})

当一个进程发送一个向量时,它会发送它所拥有的整个元组集合。当它收到一个向量并进行比较时,它会比较每个相关的对。例如,P 0的值将与 接收向量中包含P 0的元组进行比较。如果其中一个集合中缺少任何进程标识,则会默认为0进行比较。结果向量包含所有元组的超集。

例如,如果一个进程的系统矢量时钟为:({P 0,6},{P 1,3},{P 2,2})

并收到一个值 ({P 1,1},{P 2,5},{P 3,8})

生成的向量将是所有进程ID及其最大值的集合:({P 0,6},{P 1,3},{P 2,2},{P 3,8})

4、Google TrueTime

区别于上面的解决方案,我们来看下google是如何解决时间的问题。Spanner 是Google的全球级的分布式数据库,其接入到了装有超精确原子钟或GPS天线(类似于智能手机上的那种)的服务器网络上,并利用这些计时器在这样庞大的网络上精确地同步发行数据。是的,谷歌将GPS天线和精确的原子钟装到了它的服务器中。传统的思路认为:在全球范围内像这样的时间同步是不现实的,但是Google做到了。

TrueTime就使用GPS天线和原子钟来维持谷歌整个网络的运行。GPS天线利用了全球定位系统(Global Position System),该系统利用一系列太空卫星来跟踪时间和地理位置,而原子钟则利用单个原子属性来保持准确的时间。解决分布式系统的时钟问题,谷歌不是着眼于改善服务器之间的通信,而是在其服务器网络上到处安装时钟。它将GPS天线或原子钟安装到各种不同的服务器上,与TrueTime API协同工作。最终,这些计时器保证了整个服务器网络同步运行。但是给服务器装上GPS和原子时钟,成本非常高昂,一帮不考虑全球化部署的服务是不会这样考虑去解决问题的。

TrueTime API很简单,只有三个函数:

Method Return
TT.now() TTinterval: [earliest, latest]
TT.after(t) true if t has definitely passed
TT.before(t) true if t has definitely not arrived

首先now得到当前的一个时间区间,spanner不能得到精确的一个时间点,只能得到一段区间,但这个区间误差范围很小,也就是ms级别,我们用ε来表示,也就是[t - ε, t + ε]这个范围,

假设事件a发生绝对时间为tt.a,那么我们只能知道tt.a.earliest <= tt.a <= tt.a.latest, 所以对于另一个事件b,只要tt.b.earliest > tt.a.latest,我们就能确定b一定是在a之后发生的,也就是说,我们需要等待大概2ε的事件才能去提交b,这个就是spanner里面说的commit wait time。

可以看到,虽然spanner引入了TrueTime可以得到全球范围的时序一致性,但相关事务在提交的时候会有一个wait时间,只是这个时间很短,而且spanner后续都准备将其优化到 ε < 1ms,也就是对于关联事务,仅仅在上一个事务commit之后等待2ms之后就能执行,性能还是很强悍的。

5、Google TSO

Google的分布式事务方案 Percolator 模型,依赖一个单点的授时服务 TSO 来实现单调递增的事务编号生成,提供Repeatable Read(SI)的隔离级别。TSO 的逻辑极其简单,只需要保证对于每一个请求返回单调递增的 id 即可,通过一些简单的优化手段(比如 pipeline)性能可以达到每秒生成百万 id 以上,同时 TSO 本身的高可用方案也非常好做,所以整个 Percolator 模型的分布式程度很高。

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

  • 网络延时,因为所有的事件都需要从TSO获取时间,所以TSO的场景通常都是小集群,不能是那种全球级别的数据库。
  • 性能,TSO是一个非常高频的操作,但鉴于它只干一件事情,就是授时,通常一个TSO每秒都能支持1m+ 以上的QPS,而这个对很多应用来说是绰绰有余的。
  • 容错,TSO是一个单点,所以不得不考虑容错,而这个现在基于zookeeper,etcd也不是特别困难的事情。

TSO不是一个一个分配时间戳的,他每次会分配一批timestamp出来,它只把值最大的timestamp写到磁盘上,剩余的都保留到内存中,这样能够减少写盘次数,提高性能,如果TSO宕机,重启之后或者由其他TSO接管之后,TSO能够从磁盘上获取最大的timestamp再次重新开始分配。

参考资料:

1、PTP时钟同步协议分析及应用探讨 http://www.docin.com/p-454710303.html

2、Lamport timestamps   https://en.wikipedia.org/wiki/Lamport_timestamps

3、分布式系统的时间 https://www.jianshu.com/p/8500882ab38c

4、快速理解 Omid: Yahoo在HBase上的分布式事务方案  https://blog.csdn.net/colorant/article/details/47296183

5、TSO参考实现:https://github.com/pingcap/tso