Time, Clocks, and the Ordering of Events in a Distributed System

宇宙中没有时间, 只有事件发生的顺序. 为了描述观测到事件的先后, 我们定义了时间.

40年前Lamport老爷子说墙上的钟不好使, 不准. 尤其是分布式环境下时钟没法对齐. 结果Google还是做了个Spanner, 然后一众厂商跟着抄, LOL……

首先定义 $\to$, 称之为 “happened befor”, $a \to b$即 $a$ 在 $b$之前发生.

我们现在在系统中引入时钟。我们从一个抽象的视角开始，其中一个时钟只是给事件分配一个数字的方式，这个数字被视为事件发生的时间。更准确地说，我们为每个进程 $P_i$ 定义一个时钟 $C_i$，它是一个函数，将进程中的任意事件 $a$ 分配一个数字 $C_i(a)$。整个时钟系统由函数 $C$ 表示，它将任意事件 $b$ 分配一个数字 $C(b)$，其中如果 $b$ 是进程 $P_j$ 中的事件，则 $C(b) = C_j(b)$。目前，我们不对数字 $C_i(a)$ 与物理时间的关系做任何假设，因此我们可以将时钟 $C_i$ 视为逻辑时钟而非物理时钟。它们可以通过计数器来实现，而不需要任何实际的计时机制。

对于所有事件 a 和 b: 若 $a \to b$ 则 $C(a) < C(b)$

Condition:

1. 若a, b是同一进程的两个事件, 且a发生在b之前,则有$C(a) < C(b)$;
2. 若a, b是不同进程的事件, 且a是一条发送消息的事件, b是接收这条消息的事件,则有$C(a) < C(b)$;

现在我们可以尝试在图一中划虚线, 每条线表示时钟走过了一个tick. 比如$C_i(a) = 4, C_i(b) = 7$, 两个事件之间时钟走过了5,6,7一共三个tick.

那根据上述两点 Condition 可以推断:

1. 同一进程的两个连续事件之间至少有一条虚线, 即它们之间时钟至少走过了一个tick;
2. 发送消息事件和它对应的接收消息事件的波浪线至少穿过一条虚线, 即消息送发出到收到时钟至少会走过一个tick才被收到.

然后把图二中这些虚线拉直就得到图三. 因为我们只讨论时间戳而非物理时间, 这两个图是完全等价的.

引入满足 Condition 的时钟(时间戳发放算法), 有两条实现规则:

1. 任何进程$P_i$在两个连续的事件$C_i$之间都是递增的, 这显然可以满足 Condition 1.
2. 为了满足 Condition 2, 我们需要每个消息$m$携带消息发送时间戳$T_m$; 在收到带有$T_m$的信息时, 进程把它的时间戳设为$T_m$之后 (大于$T_m$). 准确来说就是:
   1. 如果进程$P_i$的事件$a$发送消息$m$, 那消息$m$携带时间戳 $T_m=C_i(a)$;
   2. 进程$P_j$收到消息$m$时, $P_j$ 将 $C_j$ 设置为大于等于 $C_j$ 且 大于 $T_m$ 的值.

全序排列事件

我们可以使用满足时钟条件的时钟系统来对所有系统事件设定一个全序。我们只需按照事件发生的时间来排序即可。为了解决并列（即相同时刻发生的事件），我们可以使用任意一个进程的全序关系 $<$。更准确地说，我们定义一个关系 $\Rightarrow$ 如下：如果 $a$ 是进程 $P_i$ 中的事件，$b$ 是进程 $P_j$ 中的事件，则 $a \Rightarrow b$ 当且仅当满足以下任一条件：

(i) $C_i(a) < C_j(b)$，或
(ii) $C_i(a) = C_j(b)$ 并且 $P_i < P_j$。

可以很容易地看出这定义了一个全序，并且时钟条件意味着，如果 $a \to b$，则 $a \Rightarrow b$。换句话说，关系 $\Rightarrow$ 是一种将 “发生在之前” 的偏序关系扩展为全序关系的方法。

有了全序, 我们就能解决互斥分布式环境下的互斥问题, 实现任何分布式系统. 问题是, 老爷子提出的这玩意儿需要大量的进程间通信, 且没有容错. 老爷也说了这事儿很复杂是另一篇文章的工作.

异常和物理时钟

容错先不谈, 这里还存在一种异常情况: 说Alice先发送资源请求然后打电话和Bob聊天, 然后Bob也去发送资源请求. 因为打电话是一个系统外部的通讯, 这会导致系统不知道Alice给Bob打电话这个因果关系, 可能先把资源给到Bob. 这也不是什么无稽之谈, 毕竟一个系统不可能封闭起来自己玩儿自己的, 不同系统之间总是要互相交互的. 让一个系统知道其它可能与它交互的系统的信息也显然不现实. 于是解决方案又回到了某个所有系统都在用的东西: 墙表.

这里有必要先说说老爷子觉得很显然的相对论中的时空概念.

为了可视化我们描述了一个三维时空, 但四维时空也没差. 如图1在原点O有一个光源, 它发出的光会在平面上传播, 1s会覆盖半径300,000km的圆, 2s会覆盖600,000km的圆. 再加上时间轴, 我们可以看到光传播经过的时空变成了一个圆锥(图2). 那根据相对论, 信息传递的速度最快也就是光速. 那一件事O要对另一件事P产生影响, 至少要在P发生前, O的信息传播就经过了P. 从图2看就是, P在O的光锥里,P可能受O的影响(可能有因果关系); Q在O的光锥外, 绝不可能有因果关系. 这也就是老爷子提出的Strong Clock Condition $\mathbf{\rightarrow}$ (注意是加粗的箭头). 描述如下:

1. 对于任意事件a, b: 若 $a \mathbf{\rightarrow} b$ 则必有 $C(a) < C(b)$

如果墙表都好使, 不会因为温度电压等外部变化忽快忽慢且所有节点的时钟都对齐了, 那问题已经解决了. 或者说问题一开始就不存在.

当然完美对齐的时钟永远不可能做到, 但只要做到足够好, 把时钟的误差控制在信息传递可能的最低延迟以下, 还是可以满足Strong Clock Condition. (TrueTime 说你呢!) 论文最后一部分就是在论证这么个事儿.

读后感

其实我是某种自顶向下的学习方式,我先读了GFS, Spanner这种工业论文, 然后读了紧贴这些工业论文的指导理论相关的论文比如paxos made simple, raft, Snapshot Isolation等, 最后才是这些基础理论. 看完了发现自己还是啥也不会, 毕竟这种奠基性质的文章讲的都是距离实际工作很远的东西.

但读完这篇文章也多少能感受到它不愧是被cite了这么多次的文章, 直击分布式领域的根本问题, 就好像画了一条线在那儿.