跳转至

论文阅读 Time-Clocks

论文全称为 "Time, Clocks, and the Ordering of Events in a Distributed System"

阅读论文的起因：阅读 Raft 论文时，第二节讲述了共识算法的特性，其中一个特性是：“它们不依赖于时间来确保日志的一致性”。无法理解这句话，所以来阅读这篇论文。

偏序关系

为什么分布式系统中无法根据本地时钟定义事件顺序？

如果事件 a 发生的时间早于事件 b，那么事件 a 就发生在事件 b 之前。这句话的前提是事件 a、b 基于同一个时钟。

分布式系统中，不同节点上时钟的时间并不相同，所以无法根据本地时钟定义事件顺序。

如何定义事件间的偏序关系？

“偏序”意为“部分顺序”，本节并没有追求定义所有事件的顺序，而是讲解了如何定义存在因果关系的事件顺序。

如果事件 a 与事件 b 存在因果关系，那么将事件 a、b 的关系称之为 “Happened Before” 关系，a happened before b，使用 \(a \to b\) 表示。

判断两事件是否为 “Happened Before” 关系的定义：

  1. 如果 a、b 是同一进程中的事件，且 a 在 b 之前发生，则 \(a \to b\)。
  2. 如果 a 是一个进程发送消息的事件，b 是另一个进程接收消息的事件，则 \(a \to b\)。
  3. 如果 \(a \to b、b \to c\)，则 \(a \to c\)。

此外，如果 \(a \nrightarrow b\) 且 \(b \nrightarrow a\)，说明 a、b 间是并发关系。

相对论的启发

作者说创作这篇论文是受到了狭义相对论的启发。个人认为“狭义相对论”这种表述过于粗略，容易造成误解。更易理解的说法应当是：受到了光速不变原理的启发。

“相对性”是显而易见的基本原理。例如在一条线上等距离的 a、b、c、d 四个位置，a、d 同时发生了一件事，b、c 分别站着两个人，b 会认为事件顺序是 a 先于 d 发生，c 会认为事件顺序是 d 先于 a 发生。

“光速不变”意味着这种不一致的问题不可能被避免，思考避免该问题是徒劳的，应当思考如何解决它。这是我阅读论文后认为的作者所说的“启发”。

逻辑时钟

为系统引入时钟、时钟函数、时钟条件

时钟：从抽象的角度来看，时钟只是给事件分配一个数字的一种方式。基于上一节的论述，定义事件顺序无法使用本地物理时钟，所以需要自定义基于因果关系的逻辑时钟。

时钟函数：假如每个进程 \(P_i\) 维护一个逻辑时钟 \(C_i\)，\(C_i\) 就是一个函数，为进程中的事件 a 分配一个整数值 \(C_i(a)\)。

时钟条件：如果 \(a \to b\)，则 \(C(a) < C(b)\)。时钟条件定义了时钟的正确性，每个逻辑时钟必须满足该条件。

时钟条件的基础假设

根据 “Happened Before” 关系，为了使时钟条件成立，需要满足以下两个基本假设：

  1. 若 a 和 b 是进程 \(P_i\) 中的事件，且 a 发生在 b 之前，则 \(C_i(a) < C_i(b)\)。
  2. 如果 a 为进程 \(P_i\) 发送消息的操作，b 为进程 \(P_j\) 接收消息的操作，则 \(C_i(a) < C_j(b)\)。

如何实现时钟条件的基础假设

实现时钟条件的基础假设，需要使进程遵循以下两个规则：

  • IR1：每个进程在发生两个连续事件之间，递增逻辑时钟。
  • IR2：当进程 \(P_i\) 发送消息时，需要将当前逻辑时钟时间戳 \(T_m\) 附着在消息上。当进程 \(P_j\) 接收到消息时，需要将自己的逻辑时钟调整为大于 \(T_m\)。（论文中所说的时间戳 timestamp 是逻辑时钟的计数器，与物理时钟无关。）

举例解释 IR2：假如进程 \(P_i\)、\(P_j\) 分别发生了三个事件 a、b、c，时间戳由进程 ID 与递增数字组成。\(C_i(a) = i\_1\)，\(C_j(a) = j\_1\)。如果 \(P_i\ b \to P_j\ b\)，且 \(C_i(b) = i\_2\)，则 \(C_j(b)\) 中的递增数字必须大于 2，例如 \(C_j(b) = j\_3\)。

完全排序

如何构建全序关系？

很简单，基于偏序关系，对并发事件按照统一的规则排序，例如按照进程 ID 排序。

全局排序的作用：以分布式互斥算法为例

分布式互斥问题，与并发问题类似，不过引起并发的原因由单机多线程变为了多机单进程。最常见的解决方案是集中式的 Redis 的分布式锁。论文提供了分布式的解决方案。

分布式互斥算法的实现：

  • 每个进程维护一个队列，以时间戳为序。
  • 进程 \(P_i\) 请求资源时，\(P_i\) 向其他进程发送请求消息。
  • 进程 \(P_j\) 收到消息后：
    • 如果 \(P_j\) 已经请求到了资源，不回复确认；
    • 如果 \(P_j\) 正在请求资源，对比二者时间戳，小者获胜；
    • 如果 \(P_j\) 没有请求资源，回复确认。
  • 如果进程 \(P_i\) 收到了所有节点的确认消息，且 \(P_i\) 的请求消息在本地队列的最前方，则请求资源，否则阻塞等待。

正是因为有了全序关系，得以实现该分布式算法。该思想也可拓展至分布式系统中的任意同步问题。

异常行为

设想一个全国性的计算机互联系统。假设一个人在计算机 A 上发出请求 A，然后打电话给另一个城市的友人，让他在另一台计算机 B 上发出请求 B。请求 B 很有可能会获得更低的时间戳，并被安排在请求 A 之前。这种情况之所以会发生，是因为系统无法得知 A 实际上先于 B 发出，因为这种先后顺序信息是基于系统外部的消息。

问题的根源：系统只能感知内部事件，无法捕捉外部事件的因果关系。

解决方案：

  1. 将避免异常行为的责任交给用户。
  2. 构建一个物理时钟系统，满足强时钟条件：对于物理时空的任何事件，如果 \(a \to b\)，则 \(C(a) < C(b)\)。
    • 其中 \(\to\) 指的是狭义相对论定义的事件顺序。

物理时钟

兜兜转转又回到了物理时钟。物理时钟不准确，逻辑时钟无法顾及系统外因果关联。那就构建一个物理时钟同步系统，使分布式系统中所有机器上的物理时钟尽可能接近。既能确保“必然有因果关联”的事件顺序正确，又能确保“可能有因果关联”的事件顺序在一定误差之内。

物理时钟的基础假设

PC1：存在一个常数 \(\kappa\ll 1\)，使得对于所有 \(i\)：\(\left|\frac{d C_{i}(t)}{dt} - 1\right|<\kappa\)。

参数解释：

  • t 指的是理想、绝对的时间标准。
  • \(C_i(t)\) 是一个函数，指的是在绝对物理时间 t 这一刻，进程 \(P_i\) 本地时钟的时间。
  • \(\kappa\) 是时钟的最大漂移速率。

条件含义：该条件用于描述单个物理时钟的精确性，因为任何物理时钟必然会产生漂移。

例如对于典型的晶体控制时钟，\(\kappa \le 10^{-6}\)

PC2：对于所有 i、j：\(\left|C_i(t)-C_j(t)\right|<\epsilon\)。

参数解释：

  • \(\epsilon\) 是同步精度的上限。

条件含义：因为不同时钟漂移率不同，所以还需要描述多个时钟间的同步精度。

如何保证“必然因果关联”的正确性？

本段与偏序关系解决的是一个问题，“如何保证有因果关联的事件顺序”。不同之处在于本段基于物理时钟实现。

基本条件：如果 \(a \to b\)，则 \(C_i(a) > C_j(b)\)。

假设一个数 \(\mu\)，事件 a 发生在物理时间 t，且另一个进程中的事件 b 满足 \(a \to b\)，则 b 一定发生在 \(t + \mu\) 之后。根据该假设，\(\mu\) 即为进程间传输延迟的已知最小值。

要避免因果倒置的异常行为，必须满足：

\[ C_i(t + \mu) - C_j(t) > 0 \]

数学推导：

  • 根据 PC1 可知，时钟 i 从时间 t 到 \(t + \mu\) 的增量至少为 \((1 - \kappa) \mu\)，即：
\[ C_i(t + \mu) - C_i(t) > (1 - \kappa) \mu \]
  • 根据 PC2 可知，在时间 t，时钟 i 和 j 的读数相差小于 \(\epsilon\)，即：
\[ C_j(t) < C_i(t) + \epsilon \]
  • 将三个公式关联：
\[ C_i(t + \mu) - C_j(t) > [C_i(t) + (1 - \kappa) \mu] - [C_i(t) + \epsilon] = (1 - \kappa) \mu - \epsilon > 0 \]
  • 解得：
\[ \frac{\epsilon}{1 - \kappa} \leq \mu \]

结论：分布式系统中，不同进程的时钟满足 \(\frac{\epsilon}{1 - \kappa} \leq \mu\)，即可确保有着因果关联的事件顺序正确。

更易于理解的解释：

对于 \(\frac{\epsilon}{1 - \kappa} \leq \mu\) ，其中 \(\kappa \ll 1\)、\(1-\kappa \approx 1\)，因此公式可近似为 \(\epsilon \leq \mu\)。

基于简化后的公式，理解的重点变为：为什么时钟间的同步精度差异 <= 进程间的最短延迟，即可确保有着因果关联的事件顺序正确？

假如事件 a 为进程 \(P_i\) 发送信息，事件 b 为进程 \(P_j\) 接收信息。考虑误差最大的情况，\(C_i(t) = t + \epsilon\)，\(C_j(t) = t\)，使用同步算法后，\(C_j(t + \nu) = t + \mu\)（\(\nu\) 为实际延迟）。事件 a 的时间戳为 \(t + \epsilon\)，事件 b 的时间戳为 \(t + \mu\)。由于 \(a \to b\)，所以必然会有 \(\mu \ge \epsilon\)。

如何缩小同步精度：物理时钟同步算法

时钟的漂移率 \(\kappa\) 存在差异，会导致同步精度 \(\epsilon\) 逐渐变大，因此需要一个算法来同步时钟以维持 \(\epsilon\)。

论文给出的物理时钟同步算法，实际是使进程遵循以下两个规则（基于实现逻辑时钟的两个规则而来）：

  • IR1'：在进程 \(P_i\) 未收到消息时，其时钟不断前进。
  • IR2'：
    • (a) 当进程 \(P_i\) 在时间 t 发送消息 m 时，需附带时间戳 \(T_m = C_i(t)\)。
    • (b) 当进程 \(P_j\) 在时间 t' 收到该消息时，它必须将本地时钟调整为：
\[ C_j(t') = max(C_j(t' - 0), T_m + \mu_m) \]

对 IR2' 的解释：

  • 参数解释：
    • \(C_j(t'-0)\)：\(P_j\) 收到消息前一刻的本地时钟值。
    • \(\mu_m\)：消息 m 传输延迟的已知最小估计值。
  • 公式解释：
    • 假设对于进程 \(P_i\)、\(P_j\)，两进程间存在 \(a \to b\)，实际传输延迟为 \(\nu\)，\(C_i(t) = t + \epsilon\)，\(C_j(t + \nu) = t + \mu\)。易得 \(C_i(a) = t + \epsilon\)，\(C_j(b) = t + \mu\)。根据上一章节可知，系统需要保证 \(\epsilon \leq \mu\)。所以 \(C_i(a) \leq C_j(b)\)，因果关系正确。

性能度量：计算同步精度上界

结论

\[ \epsilon \lesssim d(2\kappa\tau + \xi) \]

参数解释

  • \(d\)：有向图的直径。表示“任意两个节点之间的最短通信路径所构成的集合”中的最大值。在分布式系统中，表示最坏情况下，进程间消息传递需要经过的节点数。在时钟同步中，意味着事件从出发到接收的过程中，需要经历的时钟同步次数。
  • \(\kappa\)：时钟漂移率。
  • \(\tau\)：同步消息间隔。分布式系统中，每隔一段时间，由于时钟漂移，时钟间会逐步产生误差。所以需要定时进行时钟同步。
  • \(\xi\)：消息的不可预测延迟。消息最大实际延迟 \(\nu_m\) 减去延迟最小估计 \(\mu_m\)，即 \(\xi_m = \nu_m - \mu_m\)。计算同步精度上限，网络的不确定性不可忽视。

公式解释

假设相邻进程同步，\(P_i\) 需要发送一条同步消息给 \(P_j\)，所有可能的误差如下：

  • 上一次同步距本次同步的误差 \(\kappa \tau\)
  • 本次同步可能产生的网络延迟 \(\xi\)
  • 本次同步后，距下一次同步的误差 \(\kappa \tau\)
  • 总误差为 \(2 \kappa \tau + \xi\)

最大误差为系统中相距最远的进程间的误差，即有向图的直径两端。

多次同步累计，总误差为 \(d(2\kappa\tau + \xi)\)，由此得出同步精度的上界。

（作者在附录中给出的公式证明过于复杂，我给略过了。）

重点梳理

分布式系统中，两个事件间的关联分为三种情况：必然有因果关联、可能有因果关联、必然无因果关联。

逻辑时钟与物理时钟

对于逻辑时钟，只关心事件的因果顺序。对于系统内并发的事件，按照任意规则确保事件顺序唯一即可，并不关系并发事件在物理时空中顺序。

对于物理时钟同步系统，根本目的是使分布式系统中所有机器上的物理时钟尽可能接近，为每个事件分配一个全局的、有意义的时间戳。

三种情况

必然有因果关联： - 对逻辑时钟来说，体现为两事件的“Happened Before”关系。 - 对物理时钟来说，体现为时钟同步系统是否能够满足 \(\frac{\epsilon}{1 - \kappa} \leq \mu\)。

可能有因果关联： - 对逻辑时钟来说，完全无法感知事件在系统外可能产生的因果关联。 - 对物理时钟来说，通过同步系统，能够将不同机器时钟分配的时间戳控制在一定误差之内。 - 如果两事件发生的时间差小于误差，那么两事件时间戳的大小无法确定，导致无法确保两事件最终顺序的正确性。 - 如果两事件发生的时间差大于误差，那么两事件时间戳的大小能够确定，时间戳的顺序即为事件在物理时空中的因果顺序。

必然无因果关联：由狭义相对论给出，如果两个事件是“类空事件”，那么判断两个事件的发生顺序是没有意义的。

其他

阅读论文过程中，对分布式系统与狭义相对论关联的思考。

记录自己的思考，很混乱，AI 总结：作者从论文中“受狭义相对论启发”的表述切入，认为“光速不变原理”是更精准的启发来源。他通过具体示例阐释“同时的相对性”如何类比分布式系统中的事件顺序问题，并区分了相对论中与论文相关和无关的部分。最后，他反思了专业细分知识体系在带来效率的同时，也可能限制了跨学科的联想能力。

接着【相对论的启发】章节讲述。

作者说收到了狭义相对论的启发，更精准的说法：受到了狭义相对论中：由 “光速不变原理” 得到的 “同时的相对性” 推论的启发。

对 “同时的相对性” 的解释：意思是同时发生的两个事件，根据观察者的不同，两个事件发生的顺序也会不同，且不可能避免，不可能存在一个全局顺序。

狭义相对论下如何判断“两件事的因果顺序” && 狭义相对论与分布式系统的关联：上面我的 a b c d 示例解释的很清楚了。“光锥”这一概念是对狭义相对论中“两个事件因果顺序”的可视化解释：只有一件事发生在另一件事的光锥内，才能说明两件事之间有因果关联；否则两件事的发生顺序完全无法判断，不同的观察者会有不同的结论，导致“同时的相对性”。类似这篇论文中所说的“并发”。

经典的“火车闪电思想实验”也是对“同时的相对性”的解释：火车头尾同时发生闪电，对于坐在火车中间的人来说，两次闪电有先后顺序，对于恰好在火车中点外静止的人来说，两次闪电同时发生。同时发生的两件事，不同位置的人观察到了不同的现象。（没有系统性的学习过这部分知识，导致自己刚开始完全不理解这个思想实验和狭义相对论有什么关系。）

我认为的狭义相对论最有趣的部分：基于光速不变原理和相对性原理，揭示了空间与时间的关联：“在同一个惯性参考系下，空间速度与时间流速成反比关系”。并以此得出很多有趣的推论，如“时间膨胀”、“长度收缩”、“质能等价”、“相对性质量”等。

记录上一段话的原因：这是我刚见到狭义相对论，联想到的部分。这些东西显然和这篇论文没什么关系，导致我产生了误解。思考并梳理了以上文字，记录下来。

思考链路：

  • 不理解分布式系统跟狭义相对论有什么关系，不就是光速不变导致一致性问题无法避免吗。
  • 复习了一遍“我认为的狭义相对论”：空间速度与时间流速成反比。
  • 复习过程中看到了“火车闪电思想实验”，不理解这个实验和狭义相对论有什么关系。
  • 总结了自己的疑惑，让 AI 解答。AI 回复说“同时的相对性”是狭义相对论根据“光速不变”的重要推论，我把狭义相对论的两个结论分离开了，实际上二者都属于狭义相对论。
  • 顿悟，梳理文字。

反思：回顾思考链路，感觉自己把“同时的相对性”推导了一遍，然后 AI 告诉我这是现有的科学结论。如果我是物理系学生，这些内容一定会被系统的学习过，但是不会留下深刻印象。我是计算机系学生，没有系统学习过这些内容，导致自己花了很多时间思考、梳理。这是专业细分的好处还是坏处？以更高的效率牺牲了一部分联想功能。