时钟

[BruceChen7]

资料来源

• https://writings.sh/post/logical-clocks?hmsr=toutiao.io&utm_medium=toutiao.io&utm_source=toutiao.io

如何确定分布式系统中事件的发生顺序

首先，我们来观察一个「如何确定分布式系统中事件的发生顺序」的问题：

在这个分布式系统中，有三个独立的进程A、B、C：

• 首先，进程A中发生了一个事件a，并把这个事件消息同步给另外两个进程B和C。
• B收到消息后，发生了一个事件b，并把这个事件消息同步给进程C。
• 但是由于无法确定的网络延迟原因，导致进程A发出的消息到达C晚于进程B发出的消息到达C，这样 进程C的视角上，最终看到的事件顺序是b, a，但是这与事实是相悖的。

要实现因果一致的系统，仅仅是依靠进程接收到时间发生的数据是不准确的。

全局物理时钟

对于上面提到的两个问题，我们试图解决的一个天然想法是， 记录每个分布式进程中发生事件的原始时间戳， 并把它连同事件本身扩散到其他节点，这样其他节点的视角上就可以观察到完整的因果顺序了。

问题是：不同节点的物理时钟其实是不一致的，而且无法做到精确一致。

原因

• 仍然是由于网络延迟的不确定，我们无法通过网络同步时间来获取一个全局一致的物理时钟。
• 现实中的多个时钟，即使时间已经调成一致，但是由于日积月累的计时速率的差异，会导致时钟漂移而显示不同的时间。

全序和偏序 全序就是在偏序的基础上，要求全部元素都必须可以比较。举例来说：

• 自然数集合中的比较大小的关系，就是一种全序关系
• 集合之间的包含关系，则是一种偏序关系
• 复数之间的大小关系，是一种偏序关系，而复数的模的大小关系，则是一种全序关系。

现在我们回头看，寻求全局时钟为分布式节点中的时间做顺序标定的方式， 其实是在寻求一种全序关系来描述分布式中的事件顺序， 而且是严格对齐真实的物理时钟的全序关系。

我们的分布式系统，和相对论有很多相似之处：

• 在物理时空中，信息是通过光速传播的，而在分布式系统中，信息是通过网络传播的。
• 在物理时空中，不同参照系下的观察者可能对于事件顺序无法达成一致， 而在分布式系统中，由于全局物理时钟无法实现，不存在进程拥有全局视角。 而如果进程间的事件没有因果关系，那么就无法达成顺序上的一致性。
• 在物理时空中，由于光速限制，观察者在观察到事件A的时候，才确定了事件B和A的因果关系。 那么在分布式系统中，我们同样可以通过消息传递来创造因果关系。

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

通过通信创造因果关系 这个设计对于刻画分布式系统中的事件顺序有多么重要。

Lamport Logical Clocks

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

事件的分类

• 进程内自发的事件（如下图中的红色标记的事件）。
• 发送一个消息，是一个事件（如下图中的蓝色标记的事件）。
• 接收一个消息，是一个事件 （如下图中的黑灰色标记的事件）

道理是显然的：如果事件e 导致了事件 j，那么一定e 发生在j的前面

Lamport时钟算法

• 每个进程P都维护在计数器C，初始为0
• 每执行一个事件，计数器自增1
• P给Q发消息是，需要带上P的计数器C

• 当Q，接受到消息时，需要更新自己的计数器D = max(C, D) + 1

  

实际上证明事件a发生在事件b之前，那么Ca < Cb，反之，则不成立。 因为a和b之间可能存在并发。

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

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

向量时钟

向量时钟，其实是对Lamport的时钟的一个延伸思考，算法结构一致，只是多传了一部分信息。

对每个进程，定义一个向量 VC，向量的长度是n， n是进程数目。具体的算法见图。

向量有序，则事件有序。（充要）向量平行，则事件并发（充要）。

下面图13是一个向量时钟算法的示意图：

和lamport时钟算法示意图一样：（红色点、蓝色点、黑灰色点..）图的右方部分，总结了这个算法对不同事件的操作：

• 对于红色和蓝色，也就是进程内自发性事件和发送消息的事件，向量内相应的计数器自增。
• 发送消息的时候，需要传播出去自己的整个向量（也就是广播自己对整个系统的视角）。
• 接收到消息的时候，也就是蓝色事件，需要对齐对方的向量，并应用第一条规则，即自己的向量内相应计数器自增。

不足

• 只考虑了固定数量的节点，没有考虑节点的动态添加和销毁。如果我们考虑用类似Hashtable而不是Vector的描述方式的话， 我们还需要事先给每个节点定义一个全局唯一标识。现代解决方案： 区间树时钟 - Interval Tree Clocks
• 假设节点数量是 N， 那么每个节点需要维护的空间复杂度是O(n)，通信的复杂度也是O(n)。

总结

• 现实中，无法构建精确的全局时钟来描述事件顺序。
• 向量时钟是一种对lamport时钟的延伸，以偏序关系准确刻画了事件的因果顺序。
• 因果关系是一种偏序关系