首页 话题 library logo 文库 我的
更多
回到详情

逻辑时钟 - 如何刻画分布式中的事件顺序

出处：https://writings.sh/post/logical-clocks

逻辑时钟是描述分布式系统中时序和因果关系的一种机制。 由于网络延迟、时钟漂移等现实问题，我们无法建立一个全局物理时钟来描述时序， 因此区别于物理时钟的「逻辑时钟」机制应运而生。 第一个逻辑时钟算法是由分布式领域的大神Lamport在1978年提出的lamport时钟算法。

本文将从一个基础问题的讨论切入，逐步介绍：

  • 为什么需要逻辑时钟 – 物理时钟是否可行？
  • 相对论是带来了什么启示 – 事件的相对性
  • 最早期的逻辑时钟算法什么特点 – Lamport逻辑时钟
  • 后续改进的算法有哪些 – 「向量时钟」和「版本向量」等等

逻辑时钟的思想有趣而深刻，值得探究。

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

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

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

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

图1 - 由于网络延迟， 进程BB发出的消息晚于进程AA发出的消息到达进程CC

可以看到，在分布式通信中，由于网络延迟的不确定性， 仅仅以接收顺序作为整个分布式系统中事件的发生顺序是不可取的。

下面我们再观察一个稍微现实点的例子。

  1. 假设朋友圈有三个数据中心，分别在北京、维也纳和纽约。
  2. 北京小明在朋友圈中发了一张风景图，并问到「猜猜这里是哪里?」，这条消息被扩散到其他数据中心。
  3. 维也纳的小红看到这个消息后，回复说她知道。这条回复也被扩散到其他数据中心。
  4. 但是由于无法确定的网络延迟的原因，导致纽约的数据中心先收到小红的回复，而后收到了原始的提问消息。 这样，导致最终小李看到的问答顺序是不符合问答的因果一致性的。

图2 - 由于网络延迟，小李看到的事件顺序并不符合问答的因果关系

以上的例子，是腾讯微信朋友圈真实碰到并解决的问题。 详细的介绍见 微信朋友圈技术之道。

下面是微信朋友圈架构设计的两个关于因果一致性算法设计的PPT截图：

图3 - 《微信朋友圈技术之道》中分享的关于因果性的PPT

图4 - 《微信朋友圈技术之道》中分享的关于向量时钟的PPT

在腾讯的分享PPT中，提到了「向量时钟」， 不过我们稍后再揭开它的神秘面纱。

而这两个例子中，我们面临的要解决的问题， 其实是分布式系统中的因果一致性， 换句话说，就是如何准确刻画分布式中的事件顺序， 显然仅仅简单地依靠进程接收到的(看到的)事件发生顺序是不准确的。

§ 全局物理时钟

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

“If you have one clock, you know what the time is. If you have two, you are not sure.” – Anonymous

大家都清楚的一点是，不同节点的物理时钟其实是不一致的，而且无法做到精确一致。

其原因：

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

如此看来，寄希望于一个全局的时钟来对事件顺序做全局标定也是不现实的。

参考链接：

§ 全序和偏序

在数学上，「顺序」是如何描述的？

我们看下序理论中的两种序关系：偏序(partial ordering) 和 全序 (total ordering).

偏序： 假设 ≤≤ 是集合SS上的一个二元关系，如果 ≤≤ 满足：

  1. 自反性： 对SS中任意的元素aa，都有 a≤aa≤a.
  2. 反对称性： 如果对于SS中的两个元素 aa 和 bb， a≤ba≤b 且 b≤ab≤a，那么 a\=ba\=b
  3. 传递性： 如果对于SS中的三个元素，有a≤ba≤b 且 b≤cb≤c， 那么 a≤ca≤c

以上的数学内容其实不那么重要~ 关键理解： 偏序关系是一种序关系，但只是部分元素有序，并不是全部元素都可以比较。

全序则比偏序的要求更为严格一些， 在偏序的基础上，多了一个完全性的条件：

  1. 完全性： 对于SS中的任意aa bb元素，必然有 a≤ba≤b 或 b≤ab≤a.

可以看出，实际上， 全序就是在偏序的基础上，要求全部元素都必须可以比较。

总结来看，简短说： 偏序是部分可比较的序关系，全序是全部可比较的序关系。

举例来看：

  1. 自然数集合中的比较大小的关系，就是一种全序关系。
  2. 集合之间的包含关系，则是一种偏序关系（集合之间可以有包含关系，也可以没有包含关系）。
  3. 复数之间的大小关系，是一种偏序关系，而复数的模的大小关系，则是一种全序关系。

下面用简单的有向图(哈斯图)来描述下全序和偏序的区别：

图5中S1S1上的图示关系，描述的是整数之间的大小顺序，是一种全序关系，可以看到任意两个元素之间都可以比较顺序。

而S2S2上的关系，描述的是集合之间的包含关系，是一种偏序关系，其中 v2v2 和 v3v3 是不可比较的。

图5 - S1S1描述了全序关系； S2S2描述了偏序关系

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

§ 事件先后的相对性

逻辑时钟的概念是由著名的分布式系统科学家 Leslie Lamport (2013年图灵奖得主) 提出的， 在他的那篇著名的论文「Time, Clocks and the Ordering of Events in a Distributed System」 的介绍上，lamport提到了著名的狭义相对论：

Special relativity teaches us that there is no invariant total ordering of events in space-time; different observers can disagree about which of two events happened first. There is only a partial order in which an event e1 precedes an event e2 iff e1 can causally affect e2. – Leslie Lamport Time clocks and …

爱因斯坦的狭义相对论告诉我们，时空中不存在绝对的全序事件顺序， 不同的观察者可能对哪个事件是先发生的无法达成一致。 但是有偏序关系存在，当事件e2是由事件e1引起的时候，e1和e2之间才有先后关系。

对于「不同的观察者可能对哪个事件是先发生的无法达成一致」这个说法， 我们从同时的相对性开始说起：

根据狭义相对论，发生在空间中不同位置的两个事件，它们的同时性并不具有绝对的意义， 我们没办法肯定地说它们是否为同时发生。若在某一参考系中此两事件是同时的，则在另一相对于原参考系等速运动的新参考系中， 此两事件将不再同时。 – 维基百科【同时的相对性】

因为狭义相对论最基本的假设，光速不变原理： 无论在何种惯性参考系下，光在真空中的传播速度相对观察者都是一个常数。所以「同时」这个概念也是相对的。

关于同时的相对性，有一个著名的火车思想实验：

有一个观察者AA在移动的火车中间，有另一位观察者BB在地面上的月台上， 当两个观察者相遇时，一道闪光从火车的中央发出。

对于火车上的观察者AA而言，由于火车头和火车尾距离光源的距离是相同的， 因此观察到了光同时到达了车头和车尾。

但是对于月台的观察者BB而言，火车的尾部会迎向光移动，而车头会远离光移动， 而且光速是有限的，且相对于两个观察者都是相同的常数，所以BB认为光会先到达车尾，后到达车头。

图6 - 狭义相对论中著名的火车思想实验

这样，对于不同参照系的观察者而言，事件的顺序并没有一个一致性的结论。 之所以得出这样神奇的结论，仍然是因为关键的「光速不变原理」。 但是，这并不意味着发生了因果上的逻辑矛盾， 我们在这种情况下，只是无法在不同的参照系下观察到一致性的事件顺序。

我们经验上所说的「同时发生」，是因为光速太大，或者我们生活的尺度太小， 所以同时是一种近乎同时。

相对论告诉我们，光速是物质移动的最大速度，信息传播的速度不可能超过这个速度。 假如太阳消失了，地球上的我们也要在8分钟之后感知到太阳消失了。

也就是说，一个事件AA发生后， 载有这个事件信息的光（引力、无论什么，快不过光速）到达观察者之前， 观察者是无法没有任何感知的， 这时我们就无法定义事件的顺序。 而当信息最终传播到达观察者时， 这个事件也就对观察者发生了影响， 造成了一个新的事件BB，叫做「观察到了事件AA的事件BB」。 这时我们才有 AA happened before BB 的因果关系。

图7 - 物理时空中因果关系建立了事件顺序

可以看到，时空对于描述事件顺序的「happened before」同样是偏序关系。

因为事件AA的发生， 造成了事件BB的发生（包括BB这种观察AA而发生的事件），那么AA和BB就存在因果关系。

Lamport受相对论中事件顺序的相对性的启发，创造了Lamport Logical Clocks。

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

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

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

下面，我们来看下，「通过通信创造因果关系」 这个设计对于刻画分布式系统中的事件顺序有多么重要。

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

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

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

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

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

现在，我们开始讨论Lamport的逻辑时钟算法。

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

那么，「事件」是如何分类的：

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

图9 - 分布式中事件的分类

我们上面有提到「happened before」的关系，我们知道，因果关系是推导「happened before」关系的重要一环：

if eiei causes ejej, then eiei must happen before ejej – Logical Time

道理是显然的：如果事件eiei导致了事件ejej，那么一定eiei发生在ejej之前。

我们现在给「happened before」这个关系一个记号： →→， 事件aa在事件bb之前发生则表示为 a→ba→b， 那么我们有：

  1. 如果 aa 和 bb 是同一个进程内的事件，并且 aa 在 bb 之前发生，则 a→ba→b。
  2. 如果事件 aa 是「发送了一个消息」，而事件 bb 是接收了这个消息，则 a→ba→b。
  3. 如果 a→ba→b 并且 b→cb→c ，那么 a→ca→c （即传递性）。

那么，是否存在两个事件并无顺序关系吗？ 经过前面的讨论，答案当然是肯定的。

如果两个事件无法推导出顺序关系的话，我们称两个事件是并发的，记作 a∥ba∥b。

这样，我们可以这样描述上面的图9中存在的事件顺序：

  • a→b→c→da→b→c→d
  • e→c→de→c→d
  • a∥ea∥e
  • b∥eb∥e

可以看出， 「 happened before」→→ 是一个偏序关系。

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

图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（严格小于）。

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

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

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

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

图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时钟的缺陷在于：如果两个事件并不相关，那么这个时钟给出的大小关系则没有意义， 这个缺陷其实恰好就是全序和偏序的不同点而已。

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

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

§ 向量时钟 (Vector Clocks)

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

对每个进程，定义一个向量 VCVC ，向量的长度是 nn， nn 是进程数目。

  1. 初始化各个进程 PiPi 的向量， 全部抹零： VCi\=[0,…,0]VCi\=[0,…,0]。

  2. 进程 PiPi 每发生一个事件时， 其向量的第 ii 个元素自增： VCi[i]+\=1VCi[i]+\=1。

  3. 当进程 PiPi 发消息给进程 PjPj 时，需要在消息上附带自己的向量 VCiVCi。

  4. 当进程 PjPj 接收到消息时，对齐对方的时钟，并在自己的时钟上自增：

    对 [0,n)[0,n) 上的任意一个整数 kk 执行 VCj[k]\=Max(VCj[k],VCi[k])VCj[k]\=Max(VCj[k],VCi[k])，

    接着，对应第2点： VCj[j]+\=1VCj[j]+\=1。

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

  1. 和lamport时钟算法示意图一样：（红色点、蓝色点、黑灰色点..）

  2. 图的右方部分，总结了这个算法对不同事件的操作：

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

图13 - 向量时钟示意图

可以发现，向量时钟和lamport的时钟算法结构一样， 不同的点在于： lamport时钟只是在对齐时钟的计数器， 而向量时钟是在对齐各自对整个系统的视角。

我们可以推导出来关于向量时钟比较大小的几个性质：

  1. 向量的各维相等，则向量相等。 这个是显而易见的。

  2. 向量时钟是有序的 (充要)，即：

    VCiVCi 的各维上的值不大于 VCjVCj 对应维上的值， 则认为 VCiVCi 不大于 VCjVCj。

  3. 向量时钟有序性质的进一步细化，定义了严格小于：

    如果 VCiVCi 不大于 VCjVCj ， 并且至少存在一个维，在这个维上 VCiVCi 的值严格小于 VCjVCj 在这个维上的值， 则认为 VCiVCi 小于 VCjVCj。

  4. 如果两个向量不存在大小关系，则认为两个向量平行，记作 VCi∥VCjVCi∥VCj.

这几个性质看起来复杂，其实都是在定义向量时钟之间的大小关系。 我们可以得出一个结论：

向量时钟之间的大小关系是一种偏序关系。

和lamport时钟一样，我们可以利用类似的推导方式，证明 a→b⇒VCa<VCba→b⇒VCa<VCb 。 这里不再描述证明思路。

我们接下来要花一定篇幅论证下 VCa<VCb⇒a→bVCa<VCb⇒a→b 。

  1. 如果 aa 和 bb 两个事件处在同一个进程中，显而易见 a→ba→b 。

  2. 假设 aa 和 bb 分别处在不同的进程内，如 PaPa 和 PbPb ，

    设 VCa\=[m,n]VCa\=[m,n] , VCb\=[s,t]VCb\=[s,t] 。

    因为 VCa<VCbVCa<VCb ，所以 m≤sm≤s， 所以必然在 不早于 aa 之前 和 不晚于 bb 之后的时间内， PaPa 向 PbPb 发送了消息 （否则 PbPb 对 PaPa 的计数器得不到及时刷新，ss 就不会不小于 mm ）。

    图14 - 中间必然存在PaPa向PbPb发送了消息

    实际上，可以分为以下几种情况：

    图15 - 可能出现的4种情况

    1. 当 a\=ca\=c 且 d\=bd\=b , 易得 a→ba→b.
    2. 当 a\=ca\=c 且 d→bd→b ，由传递性，得 a→ba→b .
    3. 同样对于 d\=bd\=b 且 a→ca→c 的情况.
    4. 当 a→ca→c 且 d→bd→b ，根据进程内的算法逻辑和传递性，也很容易得出结论。

综上： VCa<VCb⇒a→bVCa<VCb⇒a→b 得证。

进一步的，我们可以得出这样的结论：

  1. 向量有序，则事件有序（充要）：

    VCa<VCb⇔a→bVCa<VCb⇔a→b

  2. 向量平行，则事件并发（充要）：

    VCa∥VCb⇔a∥bVCa∥VCb⇔a∥b

是的，向量时钟可以准确刻画事件顺序。

其本质在于将lamport时钟的全序计数器的方式改造成向量时钟的偏序大小关系。

§ 向量时钟看前面的问题

现在我们回到文中一开始提到的问题。

由于网络延迟的不确定性， 我们在文章开始提出了一个AA, BB, CC三个进程中如何确定事件顺序的问题。

我们可以从下面的图16中看出， VCa<VCb<VCcVCa<VCb<VCc，那么可以确定 a→b→ca→b→c。 也就是我们找到了一种方法来描述这种情况下的事件顺序。 进程CC的视角下观察 aa 和 bb 的顺序的问题也有了明确的答案。

图16 - 用向量时钟的方法解答文章开始提出的问题

最后，我们回到朋友圈的例子。 下面图17中可以看出， VCa<VCb<VCc<VCd<VCeVCa<VCb<VCc<VCd<VCe， 显然可以确定 a→b→c→d→ea→b→c→d→e 。

在小李看到小明的朋友圈和小红的评论的时候，也收到了这两条数据的向量， 我们可以根据向量时钟来确定事件的先后关系，从而不会显示出因果矛盾。

图17 - 用向量时钟的方法看朋友圈问题

图17中还有一个事件 ff， 它的发生可能是小红又发了一条评论。 我们可以看到 VCf∥VCeVCf∥VCe。 这时候，无法确定事件 ff 和 ee 的先后关系，也就是说 f∥ef∥e。

但是，这时候小李还没有看见这个事情。所谓「因果」：有因才有果。 看见也是一个事件的果。 这样说， ff 和 ee 没有因果关系， 因为小李还没有看见这个事件。 所以讨论也就没有意义。

§ 版本向量 (Version Vectors)

版本向量 Version Clocks 是一种工程上用来同步分布式数据的算法， 和向量时钟非常相似，以至于人们经常混淆这两种算法。 但是二者却有不同的地方 (Version Vectors are not Vector Clocks)。

我们注意到在向量时钟算法中， 消息传播后，发送方的向量一定会小于接收者的向量， 是因为接收者对齐了发送者的原因。

版本向量在此基础上，做了一点小的加强：

消息传播后，发送方也对齐接收者的向量， 也就是双向对齐，在版本向量中，叫做同步。

用数学语言描述的话，向量时钟算法的第三点，改成：

对 [0,n)[0,n) 上的任意一个整数 kk 执行 VCi[k]\=VCj[k]\=Max(VCj[k],VCi[k])VCi[k]\=VCj[k]\=Max(VCj[k],VCi[k])

除了这个关键性区别外， 版本向量还和向量时钟算法有一点细微的区别：

发送消息和接收消息的时候不再自增向量中的自己的计数器，而是只做双方的向量对齐操作。 也就是，只有在更新数据的时候做向量自增。

版本向量是针对数据的更新和同步的协调算法，那么我们把数据操作的事件分为以下两种：

  1. 更新数据的事件， 即图18中红色的点。
  2. 同步数据的事件， 发送数据 和 接收数据， 分别为蓝色和黑灰色的点。

图18 - 版本向量示意图

我们可以看到，在进行一次同步操作后，双方进程的版本向量会变成一样。

在我们熟知的网络通信方式上（比如TCP，UDP），同步操作可以做成原子的 ， 比如接收进程对收到的消息进行消息反写。

§ 向量时钟的不足

我们再次回到向量时钟，可以看出它的两点不足：

  1. 只考虑了固定数量的节点，没有考虑节点的动态添加和销毁。

    如果我们考虑用类似Hashtable而不是Vector的描述方式的话， 我们还需要事先给每个节点定义一个全局唯一标识。

    现代解决方案： 区间树时钟 - Interval Tree Clocks。 这个论文我没有看明白 T_T。

    大概是每个时间戳设定为 (Id,Event)(Id,Event)， 而 IdId 和 EventEvent 都用区间树的数据结构来做。 而区间树是可以在 [0,1][0,1] 实数域上无限二分的。

    文中建立了一个通用的时钟模型叫做「Fork-Event-Join Model」，

    新加入一个节点的时候，我们找一个节点进行 forkfork ， forkfork 则将当前节点的时间戳的 IdId 二分、 EventEvent 克隆，作为新节点的初始时间戳。

    当一个节点要移出的时候， 我们把它合并到一个其他节点， joinjoin 类似 forkfork 的一个 反向操作， 类似一个取最大者的方式进行合并。

    区间树时钟算法消去了向量时钟对全局唯一节点标识的依赖。

  2. 假设节点数量是 NN ， 那么每个节点需要维护的空间复杂度是 O(N)O(N)。 通信的信息量的复杂度也是 O(N)O(N) 。

    关于这个话题，有个文章可以看下： Causality Is Expensive. 文中提到：

    Causality can be characterized only by vector timestamps of size N.

    也就是这个 O(N)O(N) 的复杂度，不能再小了。

    2019年新鲜出炉的一个寻求优化时钟空间的算法，布隆时钟 - Bloom Clocks。

§ 总结与感想

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

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

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

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

这自然地，让我想起了Gossip谣言传播算法。 Gossip算法如其名，每个分布式参与者都在散播自己视角的信息，以达到谣言扩散的效果。 同样是在做 视角对齐。

对于分布式系统中的事件顺序的刻画，就讨论到这里。

– 毕 「逻辑时钟」

首页 - Wiki
Copyright © 2011-2025 iteam. Current version is 2.144.0. UTC+08:00, 2025-07-08 23:35
浙ICP备14020137号-1 $访客地图$