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

by Leslie Lamport

简介

本文是分布式系统理论的开山鼻祖、2013 年图灵奖获得者 Lamport 的成名作，也是分布式计算领域杰出论文最佳影响力奖 Dijkstra Prize 的第一篇论文，高达 11692 的引用量（截至 2019/12/08）也足以证明其广泛的影响力。

本文主要讨论 3 个话题：

  • 分布式系统中的事件顺序

  • 利用逻辑时钟确定事件全序关系

  • 利用物理时钟确定事件全序关系

事件顺序

生活中，当两个事件 A 和 B 发生时，我们可以利用其发生的物理时间来确定它们的先后关系，如：

A：2019-12-08T00:00:00+00:00 B：2019-12-07T08:00:00+00:00

我们能很容易地确定 B 在 A 之前发生。这主要是因为生活中的事件在时间上的粒度比较大，如吃饭、打球、看书，每个事件都可能持续数分钟、数小时，而事件信息的传播几乎就是一瞬间的事情，只要两个事件的发生时间在可信度量精度范围内的测量值不同，就能够确定它们的先后顺序。而在分布式系统中我们很难做到如此。

分布式系统

计算机系统的运行时由位于相同或不同空间上的进程集合构成，进程之间通过收发信息来通信。如果一个系统中消息传递延迟相对于事件间隔不可忽略，就可称之为分布式系统。在分布式系统中，我们还能准确地判断事件发生的先后顺序吗？

如上图所示，P1、P2 分别表示两个不同的进程：

  • 假设消息传递延迟相对于事件间隔可以忽略：P1 和 P2 能够通过通信确定 3 个事件的发生顺序

  • 假设消息传递延迟相对于事件间隔不可忽略：只能确定 E3 和 E2 在 E1 之后，因此以下事件顺序皆有可能：

    • E1 -> E3 -> E2

    • E1 -> E2 -> E3

只要事件 E1、E2 与 E3 之间没有任何因果关系（causal relation），即便无法准确判断 E1、E2 和 E3 之间的关系，对系统数据一致性也没有影响。但如果事件之间存在因果关系，就可能对系统产生负面影响，如下图所示：

假设 P2 为数据库，P1 和 P3 为应用程序：

  • P1 向 P2 写入数据 x = a，并告诉 P3

  • P3 知道 P1 写入 x = a 后，认为应该写入 x = b

  • 因为消息传递延迟相对于事件间隔不可忽略，P3 的写入请求可能在 P1 的写入请求到达之前到达 P2，从而导致最终的数据 x = a 而不是 x = b

因此，要保证分布式系统的数据一致性，就需要在系统范围内保持事件之间的因果关系。

偏序

为了更准确地讨论接下来的话题，我们需要更精确地定义分布式系统。假设分布式系统由一组进程构成，每个进程由一个事件序列构成。进程内事件的时间粒度由实际应用决定，大到执行一段子程序，小到执行单个机器指令皆可。在单个进程内部，事件具有全序，即任意两个事件的发生时间之间有绝对的可比性。

假设消息的发送和接收也是进程中的事件，那么我们可以定义一种先后 (happended before) 关系 “→\to ”：

  • 如果 a、b 是单个进程内部的两个事件，且 a 在 b 之前发生，那么 a→ba \to b

  • 如果进程 P1 向 P2 发送消息，a 为 P1 的发送事件，b 为 P2 的接收事件，那么 a→ba \to b

  • 如果存在 a→ba \to b 以及 b→cb \to c ，那么 a→ca \to c

一个能保持 “→\to ”关系的分布式系统，并不能将系统中所有事件排序，因此 “→\to ” 实际上是一种偏序。保持事件的 “→\to ” 关系是保持事件因果关系的充分条件。

逻辑时钟

为了表示分布式系统及单个进程中的事件顺序，我们需要引入逻辑时钟的概念。假设每个进程 PiP_{i} 的逻辑时钟为 CiC_{i} ，那么对于PiP_{i}中的任意事件 a，其发生的时刻即为 Ci⟨a⟩C_{i}\langle{a}\rangle ；假设整个分布式系统的逻辑时钟为 CC ，进程 PjP_{j} 上的某事件 b 的发生时刻为 C⟨b⟩C\langle{b}\rangle ，且 C⟨b⟩=Cj⟨b⟩C\langle{b}\rangle = C_{j}\langle{b}\rangle 。以上讨论对时钟的绝对值不做任何假设，因此该时钟被称为逻辑时钟。

要满足系统的正确性、数据的一致性，逻辑时钟需要满足以下条件 (Clock Condition)：

对任意两个事件 a 和 b，如果 a→ba \to b ，那么 C⟨a⟩<C⟨b⟩C\langle{a}\rangle < C\langle{b}\rangle

即：

  • C1：如果 a 和 b 是进程 PiP_{i} 中的两个事件，且 a 先于 b 发生，那么 Ci⟨a⟩<Ci⟨b⟩C_{i}\langle{a}\rangle < C_{i}\langle{b}\rangle

  • C2：如果进程PiP_{i}向进程 PjP_{j}发送消息，a 表示发送事件，b 表示接受事件，那么 Ci⟨a⟩<Cj⟨b⟩C_{i}\langle{a}\rangle < C_{j}\langle{b}\rangle

要实现满足上述条件的逻辑时钟，只需要保证以下两点：

IR1：在单个进程内部，每发生一个事件，逻辑时钟绝对值增加 IR2：当进程PiP_{i}向进程 PjP_{j}发送消息时，假设发送事件为 a，那么消息中应包含 a 的当前逻辑时间戳 Tm=Ci⟨a⟩T_{m} = C_{i}\langle{a}\rangle ，当PjP_{j}收到消息时，需要取自身当前逻辑时刻与 TmT_{m} 中的最大值后自增，即 max(Tm,Cj)+1max(T_{m}, C_{j}) + 1

就能保证 C1 和 C2 成立。

全序

本节介绍如何利用逻辑时钟来实现分布式系统事件的全序。

对于不同的进程来说，一些事件没有先后顺序定义，举例如下：

图中进程 P1P_{1} 的起始逻辑时刻为 5；P2P_{2} 的其实逻辑时刻为 4。通过引入逻辑时钟，可以确定 E1→E2→E4→E6E_{1} \to E_{2} \to E_{4} \to E_{6} 以及 E1→E3→E5→E6E_{1} \to E_{3} \to E_{5} \to E_{6} ，但无法确定 E3E_{3} 、 E5E_{5} 与 E2E_{2} 、 E4E_{4} 之间的先后关系，即满足偏序的全序方案有很多种，现在需要从中确定地选择一种。一种简单、稳定的方法就是确定进程间的全序 ≺\prec ，如 P1≺P2...≺PiP_{1} \prec P_{2} ... \prec P_{i}

定义关系 “⇒\Rightarrow” 如下：假设 a 是进程PiP_{i}上的某事件，b 是进程PjP_{j}上的某事件，那么 a⇒ba \Rightarrow b 意味着以下两个条件的其中一个成立：

  • Ci⟨a⟩<Cj⟨b⟩C_{i}\langle{a}\rangle < C_{j}\langle{b}\rangle

  • Ci⟨a⟩=Cj⟨b⟩C_{i}\langle{a}\rangle = C_{j}\langle{b}\rangle 且 Pi≺PjP_{i} \prec P_{j}

假设 P1≺P2P_{1} \prec P_{2} ，就可以得到 E1→E2→E4→E3→E5→E6E_{1} \to E_{2} \to E_{4} \to E_{3} \to E_{5} \to E_{6} 的顺序，从而稳定地确定系统中事件的全序。

场景举例

能够获得事件的全序对于实现分布式系统来说十分有用。想象这样一个具体场景：一组进程需要排他地使用某个资源，该资源只能同时被一个进程使用。现在需要实现一个资源协调算法，满足：

  1. 资源必须在被当前进程释放之后才能分配给其它进程

  2. 资源必须按照请求的先后顺序（偏序）来赋予其它进程

  3. 只要保证每个进程在使用完资源后释放，那么每个请求最终都将被满足

这个问题并不简单，使用唯一的进程作为调度中心无法解决。假设 P0P_{0} 是调度进程， P1P_{1} 先向 P0P_{0} 发送资源使用请求，然后向 P2P_{2} 发送一条消息， P2P_{2} 收到消息后向 P0P_{0}发送资源使用请求，因为网络传输的延迟问题，P2P_{2}的请求可能先于 P1P_{1}的请求到达P0P_{0}，从而违背第 2 点要求。

利用全序实现的方案，可以解决这个问题，因此我们提出以下算法，暂称之为分布式系统事件全序算法。该算法建立在 1 个假设和 5 条规则之上：

假设 1：对于任意两个进程 PiP_{i} 和 PjP_{j} ，从 PiP_{i} 发送到 PjP_{j} 的消息将按顺序到达

假设 1 仅仅是为了简化问题，它并不是最重要的，即使没有它，我们可以自行通过类似 tcp 的序列 id 和 ack 的机制实现它。

在每个进程中，维护着当前收到的请求队列以及其它进程的最大逻辑时间戳。当进程收到逻辑时间戳大于自身当前逻辑时间戳的请求或响应时，则及时对齐。

每个进程 PiP_{i}维持着一个逻辑时钟和收到的请求队列 (Request Queue)，如下所示：

我们提出的算法可以用以下 5 条规则来描述：

规则 1：需要请求资源时，进程 PiP_{i} 需要向所有其它进程 PjP_{j} 发送消息，消息中包含PiP_{i}的当前时间戳 规则 2：当进程 PjP_{j}收到请求后，将请求放入请求队列后，返回 ack 给 PiP_{i} 规则 3：当进程 PiP_{i} 要释放资源时，它需要从请求队列中移除相应的请求，其它进程 PjP_{j}发送释放请求 规则 4：当进程 PjP_{j} 收到释放请求时，从请求队列中移除相应的请求。 规则 5：当满足以下条件时，进程 PiP_{i} 被赋予资源的访问权：

  • 相应的资源请求位于请求队列的头（利用全序一节定义的 “⇒\Rightarrow” 关系排序）。假设该请求产生的逻辑时刻为 TmT_m

  • PiP_{i} 已经收到其余所有进程的时间戳大于 TmT_m 的消息

详细实现可参考这里。

证明

论文上有相关的证明推理过程，这里不再复述。但值得关注的是，确定全序的核心在于 “保证每个进程在做出占用或释放资源的决定之前已经充分了解到其它进程的信息”。

考虑一个小问题，如下图所示：

假设：

  • P1P_{1} 向 P2P_{2} 发送资源请求，后者尚未收到，此时 P1P_1 的时间戳为 1

  • P3P_{3} 向 P2P_{2} 发送资源请求，使得 P2P_2 的时间戳更新到 2

  • P2P_2 向 P1P_{1} 发送资源请求，使得 P1P_1 的时间戳更新到 3

问：这时 P1P_1 已经认为自己获得了 P2P_2 大于时间戳 1 的消息，那么它应该已经认为 P2P_2 已经同意了自己的资源请求，但实际上 P2P_2 尚未收到 P1P_1 的请求，那么 P1P_1 如果占有了资源，会影响系统运行的正确性吗？

仔细思考可以发现，在当前场景下，系统的最终目的是保证 P1P_1 在 P2P_2 之前使用资源。根据假设 1，P1P_1 发送到 P2P_2 的资源请求一定在 P1P_1 的 ack 响应之前到达 P2P_2 ，在前者到达后， P2P_2 就已经知道 P1P_1 在时刻 1 已经发送过资源请求，因此对于二者来说，资源获取的顺序都是先 P1P_1 后 P2P_2 。

外部事件

在上文的讨论中，实际上隐含着一个假设：

假设：所有的事件都发生在系统内部

如果系统内部的两个事件 a 和 b 之间没有直接关系，但通过某外部事件产生了因果关系，那么对于系统本身，无论如何也无法通过逻辑时钟来捕捉到这一关系，保证数据一致性也就无从谈起了。

举例如下：假设 A 发送消息给 C，同时打了个电话给 B，让 B 也发消息给 C，B 的消息可能在 A 的消息之前到达，且打电话事件属于外部事件，系统并不知晓。

物理时钟

要解决外部事件引起的问题，就必须引入物理时钟。假设 Ci(t)C_{i}(t) 为物理时钟 CiC_i 在时间 t 上的绝对数值，且 Ci(t)C_{i}(t) 连续可导。真正的物理时钟应该保证稳定的速率、单调递增，即：

PC1：存在很小的常数 kk ，使得对于任意 i，有 ∣dCi(t)dt−1∣<k|\frac{dC_{i}(t)}{dt} - 1| < k 成立

通常石英钟的 k 能达到 k⩽10−6k \leqslant 10^{-6} 。

单个时钟的稳定还不够，不同的时钟应该尽可能同步，即：

PC2：存在很小的常数 ϵ\epsilon 对于任意 i, j，有 ∣Ci(t)−Cj(t)∣<ϵ|C_i(t) - C_j(t)| < \epsilon 成立

设 μ\mu 表示系统中跨进程消息传递的最小时长。事件 a、b 分别为不同进程上的两个事件，且 a 在 b 之前发生，如果 a 发生的时间为 t 那么 b 必然晚于 t+μt + \mu 发生。通过推导，要排除外部事件的干扰，必须满足：

Ci(t+μ)−Cj(t)>0C_i(t + \mu) - C_j(t) > 0

可以推导出：

ϵ/(1−k)⩽μ\epsilon / (1-k) \leqslant \mu

即，只要上述表达式成立，那么外部事件也将不会影响系统的正确性。从该表达式也可以看出：进程之间距离越近，即 μ\mu 越小，那么时钟误差 ϵ\epsilon 也必须越小，才能满足要求。

容忍外部事件的全序

接下来，我们将提出一个分布式系统事件全序算法的改进版本，它将保证 PC2 成立（PC1 通过物理时钟本身决定），从而在分布式系统中确定容忍外部事件的全序。

假设 μm\mu_m 为每个进程所知道的通信最小延迟，即对于某个消息的发送事件 tt 和接收时间 t′t' ，必有 t′−t⩽μmt' - t \leqslant \mu_m 成立。相对于逻辑时钟一节的实现 IR1 和 IR2，我们提出 IR1’ 和 IR2'：

IR1'：对于任意未接收消息的时刻 t，进程 PiP_i 的物理时钟 CiC_i 可导，且满足 dCi(t)dt>0\frac{dC_i(t)}{dt} > 0 IR2'： (a) 如果PiP_i在 t 时刻发送消息 m，那么 m 须包含当前时间戳 Tm=Ci(t)T_m = C_i(t) (b) 当 PjP_{j} 在时刻 t' 收到消息 m 后，将自身的物理时钟调整为 max(Cj(t′−0),Tm+μm)max(C_j(t'-0), T_m + \mu_m)

具体证明可自行翻阅论文附录。

小结

论文讨论了分布式系统中的事件顺序，只要满足偏序 “ →\to ”，就可以认为系统是正确的，数据是一致的。我们可以通过逻辑时钟确定这样的偏序，甚至可以通过给定进程的确定顺序来为分布式系统的事件赋予全序。当存在外部事件影响系统内部事件的先后关系时，逻辑时钟将无能为力。这时候理论上我们可以通过引入满足一定要求的物理时钟来解决这个问题。

但本文讨论的话题是建立在系统运行顺利的基础上，提出的算法不具备容错能力。但它是我们进一步研究分布式系统理论的基石，这篇文章对于正确理解分布式系统意义重大。

参考

PreviousLFU Implementation With O(1) Complexity (2010)NextDapper, a Large-Scale Distributed Systems Tracing Infrastructure (2010)

Last updated