Logical Clock

这里首先简单回顾下分布式系统以及分布式计算概念和特性。

什么是分布式系统？

image.png

假设多个系统分布在多台机器上，多台机器组成一个分布式系统。
官方介绍：简单来说就是一群独立计算机集合共同对外提供服务，但是对于系统的用户来说，就像是一台计算机在提供服务一样。
特点：
1.multiple machine services as one
2.one request cross multiple machine
3.each machine can talk to anyone

什么是分布式计算？

最直观的解释：将一个计算任务由管理节点拆分多个子计算任务分布在多机器组成的系统中，最后再将子计算结果进行汇总返回。
特点：
1.follow the master-slave mode possibly
2.master split and control job in term of sub tasks
3.subTask run on the slave
4.slave or sub task can communicate with each other
5.msg flow in subTask

如何决定分布式系统中事件的先后顺序？

在分布式系统中有一个特点是不同的机器或者不同的进程之间都会有相互传递信息的特点，那么由于物理时钟漂移以及网络延迟等问题，通过物理时钟来定义事件的先后顺序其实是一件不现实的事情。

我们来看一件简单的例子，假设微信朋友圈的数据中心在a,b,c三个城市，a城市的李雷同学分享一条消息，该消息从a数据中心分别扩散到b，c数据中心，b城市的韩梅梅收到以后进行来评论，随后评论以消息的形式同样被扩散到c城市，由于网络延迟等问题，c城市的小明同学首先收到的是b城市韩梅梅的评论消息，其次才是a城市的李雷的原始分享。那么最终c城市的小明观察到的时间顺序就是评论->分享，而不是正确的分享->评论。

因此对于分布式系统来说如何解决事件的先后顺序就变成了如何在分布式系统构建一种全局因果一致性。

分布式逻辑时钟

• 总体来说， 逻辑时钟尝试用「通过进程间创造通信以添加因果关系」的方式来对分布式中的事件顺序做描述。

观察下面图8中的两个图：

• 红色的点表示自发性事件。 黑色的表示『观察到其他进程事件』而发生的事件。
• 横向黑色实线代表物理时钟。
• 带箭头的线表示进程中一个事件发生时，向另外一个进程传播这个事件。

我们试着从每个进程的视角，依次对图S1S1和S2S2进行推导一下，会发现， 其实两个图所描述的事件顺序，在进程的相对视角中，是一样的。

img

图8 - 示例： S1S1和S2S2虽然在物理时序上不一样，但是在各个进程的视角上推导出来却是一样的

我们的逻辑时序应该越接近物理时序越好，然而两个图对时序的刻画， 出现了歧义（比如无法确定 a3a3 和 b2b2 的顺序）。 根本上是没有做充分的消息传递来添加因果关系。

首先我们需要明确一点： 逻辑时钟并不度量时间本身，仅区分事件发生的前后顺序。

Lamport的时钟算法：

1. 每个进程 PiPi 内维护本地一个计数器 CiCi ，初始为00.
2. 每次执行一个事件，计数器 CiCi 自增 （假设自增量为11）.
3. 进程 PiPi 发消息给进程 PjPj 时，需要在消息上附带自己的计数器 CiCi.
4. 当进程 PjPj 接收到消息时，更新自己的计数器 Cj=Max(Ci,Cj)+1Cj=Max(Ci,Cj)+1

下面的图10是这个算法的示意图，可以推算最后的时钟计数器的值：Ci=3Ci=3, Cj=5Cj=5

img

图10 - Lamport时钟算法

下面，将证明：如果 a→ba→b，那么一定有 Ca<CbCa<Cb。

1. 假设 aa 和 bb 发生在同一个进程内，显然 Ca<CbCa<Cb.

2. 假设 aa 和 bb 分别处在不同的进程内，如 PaPa 和 PbPb，
   根据事件先后的定义，必然存在一个不早于 aa 且 不晚于 bb 的由 PaPa 到 PbPb 的通信 （否则 a∥ba∥b ，矛盾）。

   那么假设两个进程在 aa 和 bb 之间最近一次通信是由 PaPa 向 PbPb 发送了消息 a→ba→b： 易得 a→c→d→ba→c→d→b (其中可能 a=ca=c 或者 d=bd=b) 。根据算法定义，得：

   1. Ca≤CcCa≤Cc (进程内计数器自增).
   2. Cd≤CbCd≤Cb (进程内计数器自增).
   3. Cc<CdCc<Cd (进程间通信，观察者事件已经严格大于发生者事件的计数器)。

   那么，最终推导出 Ca<CbCa<Cb（严格小于）。

   img

   图11 - 事件 aa 和 bb 在不同进程的情况下，中间一定有消息传递，否则两个事件并发

以上，得证 a→b⇒Ca<Cba→b⇒Ca<Cb。

但是，如果我们已知 Ca<CbCa<Cb 的话，是否可以推导出 a→ba→b 呢？

悲哀的是，不能。 下面的图12是个反例：

img

图12 - lamport时钟无法反向推导事件顺序的反例： 红色 aa 和蓝色 bb 是并发的

这样，我们反证了 Ca<Cb⇏a→bCa<Cb⇏a→b。

我们无法推导出 Ca<Cb⇒a→bCa<Cb⇒a→b 的原因，在于 aa 可能和 bb 并发。

但是， 如果 Ca<CbCa<Cb，一定不会有 b→ab→a 的关系存在。

Lamport的逻辑时钟算法构建了一个全序(total ordering)时钟来描述事件顺序， 但是我们知道「happened before」是一个偏序关系， 用全序关系的一维计数器来描述「happened before」的话， 就会导致无法等价化描述的结果， lamport时钟的缺陷在于：如果两个事件并不相关，那么这个时钟给出的大小关系则没有意义， 这个缺陷其实恰好就是全序和偏序的不同点而已。

所以，要准确描述事件顺序，我们终究要寻求偏序方法。

于是，我们继续探讨向量时钟。

逻辑时钟的不足

• 现实中，无法构建精确的全局时钟来描述事件顺序。
• 受狭义相对论的启发，我们用因果关系来描述事件顺序。
• 因果关系是一种偏序关系。
• Lamport时钟构造的计数器之间的大小关系是一种全序关系，无法准确刻画事件顺序的偏序关系。
• 向量时钟是一种对lamport时钟的延伸，以偏序关系准确刻画了事件的因果顺序。

此外，向量时钟给我一种感想，对每个分布式节点来说：

1. 我把我的视角分享给其他节点。
2. 我对齐我看到的其他节点的视角。

本质上，是在做 视角对齐。

参考