Yang Liu's blog

分布式系统之逻辑时钟

逻辑时钟论文阅读笔记

一句话概括,时间不过是对系统内任意两个事件,在一个一维有序坐标上指明相对位置的函数。它可以但不必与真实世界的前后关系相对应。当不一定对应时,我们称它为逻辑时间;当完全对应时,我们称它为物理时间。

问题

定义分布式系统是一个由一系列由空间分隔开的不同进程,通过交换消息进行沟通的系统。如果消息在不同进程间传输的延迟,相比于消息在进程内部的传输延迟而言不可忽略,那么我们就说这个系统是分布的

约定:事件(event)的定义未严格给出,姑且可模糊认为是进程内部某一段的运算或操作。

定义:(happened before, thin arrow, $\to$)

  1. 若 a 和 b 事件都属于同一进程,a 比 b 先发生,则说 “a 在 b 之前发生 ($a \to b$)”。
  2. 若 a 是一个进程给另一个进程的发送事件,b 是另一个进程对应的接收事件,则说 “a 在 b 之前发生”。
  3. $\forall a, b, c, a \to b, b \to c \Longrightarrow a \to c$ (即“在……之前发生”的关系具备传递性(transitivity))

反之,若 $a \not \to b, b \not \to a$, 那么称 a 和 b 是并发(concurrent)的。

举例

简单给出并发事件的例子,进程 A 内事件 a1, s, a2 依次发生,进程 B 内事件 b1, r, b2 依次发生,其中 s 和 r 分别为 A 到 B 的发送事件和接收事件。那么我们有:

  • $a_1 \to s \to a_2$
  • $b1 \to r \to b2$
  • $s \to r$

由发生关系的传递性,我们可知:

  • a1,s 发生的比 r 及 r 的后续事件都要早
  • r,b2 发生的比 s 及 s 的前继事件都要晚

但 a1 与 b1,a2 与 b2,我们无法找出任何一个传递关系来明确谁先谁后,那么,它们便是两两互为并发的。

结论:由 $\to$ 只能确定一个部分有序的关系,其中依然有无法确定先后关系的并发关系存在。并发关系给多进程编程带来一个问题,即若两并发事件存在临界区域(cirtical area)的时候,两事件不同的执行顺序必然导致竞争条件(race condition)。

解决方案:定义一种使所有事件构成的集合 $\mathbb{E}$ 成为完全有序关系的方法。见下。

时钟约束

定义:定义为一个以事件为输入,输出为某个有序数的函数C。若对所有事件恒满足:
$$
\forall a, b \in \mathbb{E}, a \to b \Longrightarrow C(a) < C(b)
$$
则称该函数C满足时钟约束。

我们将C函数输出的有序数构成的先后关系,在逻辑上等同于物理时间,我们称由C实现的虚拟时钟为逻辑时钟

实现:该函数的实现非常直白:

  1. 在同一进程 $i$ 内,C 单调递增;
  2. 当一进程A向另一进程B发送消息时,如有必要,B将自身时刻向上调至大于A发送时刻的某个值。

可知,C 完全映射了 $\to$ 所表达的关系。

实现完全有序:在上述实现基础上,只需要添加一个任意的确定的完全有序关系,将 $C(a) = C(b)$ 的情况区分出先后来,我们即可将集合完全排序。这种完全有序的关系,我们定义为 (fat arrow, $\Rightarrow$)。

结论:$\to$ 关系确定了唯一的部分有序关系;而 $\Rightarrow$ 则是人为指定的完全排序关系,根据指定规则不同,$\Rightarrow$ 关系可以有无穷多个。(在单一操作系统内的一个最简单的指定规则就是,当两事件时刻相等时,用进程号来分出前后)

fault model:该结论建立在信息有序到达和信息始终可达的基础上。前者要求一个可靠的传输协议,后者则注定了该模型过于理想化,使得现实的可靠实现不能直接建立在该结论之上。

应用举例

此例子运用上述时钟函数,实现一种让多进程申请/释放共享资源的算法。简单解释如下:

当进程 A 需要申请时,向所有其他进程发送“A申请资源”的消息,所有收到信息的进程向A发送一个确认消息。当 A 是申请者里时间最早者,且 A 收到了所有的确认回复时,A 可安全获得该资源。

A 向其他进程的发送,使得“A希望申请”这一知识成为了所有其他进程的共有知识。而所有进程的确认,则确定了资源在该时间段的空闲,A 获得资源不会引发竞争条件。

按:但是,根据和 TCP 里的 Two Generals Problem 一样的结论,在不可信信道内的公共知识永远不可能具备 100% 置信度。因此,该模型的“信息始终可达”是一个不符合现实的强假设。在真实的分布式系统中依然需要考虑错误处理。

强时钟约束

在上述方案中,时钟约束只定义了系统内部的有序性(或称同步性),由于 $\Rightarrow$ 关系的任意性,系统内部的先后关系有可能和系统外部以真实时间为参考系的先后关系相互矛盾。为此,我们必须让系统也能模拟物理的时钟,从而将真实外部世界的先后顺序也考虑在内。处于系统外部的先后关系,我们定义为 (bold arrow, $\pmb{\to}$)。

定义:若对时钟函数C,满足:
$$
\forall a, b \in \mathbb{E}, a \pmb{\to} b \Longrightarrow C(a) < C(b)
$$
则称函数满足强时钟约束。

证明强时钟约束可保证时间上的先后关系

作者做了两个假设:

  1. 对所有的单个时钟,时钟的流动速度收敛在某个偏差为 $\kappa$ 的区间内。该假设符合石英钟的物理事实。
  2. 在任意一个时刻,系统内的任意两个时钟之间的读数误差不超过 $\epsilon$。

若在系统内部两进程的传输延迟最小为 $\mu$,那么,根据上述假设,只要:
$$
\frac{\epsilon}{1 - \kappa} \le \mu
$$
即可保证两事件在物理时间上的先后顺序和系统内的先后顺序关系一致。

因为假设1不证自明,现在问题缩小为,如何证明假设2。

设 $\xi$ 为最小延迟 $\mu$ 外的不可预知延迟。若时钟函数实现为:

  1. 当进程未接受消息时,时间流速 > 0;
  2. 当进程收到消息时,系统在有必要的情况下将时刻上调至不小于消息发送时间+$\mu$ 的时刻;

且系统满足:

每经过一段时间 $\tau$ ,进程向每一条消息通路发送一条时钟同步消息。

那么,可从数学上证明:
$$
\epsilon \approx d(2\kappa \tau + \xi)
$$
即假设2成立。同时,隐含地,$\mu + \xi \ll \tau$。即时钟同步的周期可以远大于消息延迟。

同样由于此隐含关系,可以看出,任一时刻内系统任意两进程的时间误差 $\epsilon$,正比于系统内网络最大距离 $d$,正比于时钟物理误差 $\kappa$,正比于时钟同步周期 $\tau$。根据系统的最小延迟 $\mu$,系统设计者可通过降低消息拓扑路径长度,使用精度更高的物理时钟,以及提高时钟同步频率来获得更高的系统同步精度。