摘要:论文研究在分布式系统中,事件发生先后顺序的概念,并展示了如何定义事件之间的偏序。论文给出了一种用于同步逻辑时钟系统的分布式算法,该逻辑时钟可用于对事件做全序排序。其中,全序是描述解决同步问题的一种方法。该算法专门用于同步物理时钟。

引入

时间的概念是我们思考的基础。而它源于事件发生顺序这一更基础的概念。当一件事情发生在时钟显示 3:15 且未到 3:16 之前,那我们就说它发生在 3:15。对事件的时间顺序概念遍布于我们对系统的思考。例如,我们在机票预定系统中发起的预定请求,如果它发生在航班订满之前,那就应该被接受。但在分布式系统中,我们会发现事件的时间顺序概念需要被重新审视。

分布式系统由空间上彼此分开的一组独立进程组成,进程间通过交换消息进行通信。计算机互联的网络,比如 ARPANET(阿帕网)就是一个分布式系统。一台集成了 CPU、内存、I/O 通道等独立处理单元的计算机也可以被视为分布式系统。如果相对于单进程中事件之间的时间,消息传输的延时大到不可忽略时,系统就是分布式的。

本文主要关注空间分离的计算机系统。但我们的诸多观点可以得到更普遍的应用。特别的,由于不可预知的事件发生顺序,单机上多进程系统也涉及到类似分布式系统中的问题。

在分布式系统中,有时候无法确定两个事件哪个先发生。「之前发生」(happened before)只是系统中事件之间的偏序(Partial Ordering)。我们发现,由于人们没有充分认知到这个事实和它的含义,导致问题的出现。

在本论文中,我们讨论由「之前发生」所定义的偏序,提供一个分布式算法来将其扩展成对所有事件一致的全序(Total Ordering)。该算法提供了实现分布式系统的有效途径。我们用解决同步问题的一个简单方法,来说明该算法的使用。然而,如果通过该算法获取的事件顺序和用户感知的不同时,会导致异常行为。这可以通过引入真实的物理时钟来规避。我们描述了一种用于同步这些时钟的简单方法,并推导了时钟同步漂移的误差上限。

偏序|The Partial Ordering

大部分人会认为,如果事件 A 发生的时间比事件 B 发生时间早,则事件 A 是在事件 B 「之前发生」。他们根据物理时间的理论来证明该定义的正确性。然而,如果系统要正确地满足一项规约,则该规约必须根据系统可观测的事件给出。如果规约是基于物理时间,那么系统必须要包含真实的时钟。即使包含了真实时钟,仍然存在时钟非完美精确和保持精准物理时间的问题。因此我们不使用物理时钟来定义「之前发生」这一关系。

我们从更精准的定义系统开始。假设系统由一组进程组成。每个进程包含了一系列事件。根据应用程序的不同,事件可以是执行子程序,或者是执行单个机器指令。我们假设一个进程中的事件组成一个序列,当ab「之前发生」,则事件序列里a就在b之前。换个说法,进程是一组全序事件的集合。这似乎也是通常意义上进程的含义。我们也可以把上述定义扩展到子进程,但没必要这么做。

假设发送或接受消息是进程中的事件。我们可以用符号->表示「之前发生」,如下所示:

定义。系统中一组事件之间的->关系,是满足以下三个条件的最小关系:

  1. 如果 a 和 b 是同一进程中的事件,且 a 在 b 之前,则 a -> b;
  2. 如果 a 是一个进程的消息发送事件,b 是另一进程的消息接收事件,则 a -> b ;
  3. 如果 a -> b 且 b -> c ,则 a -> c。如果两个独立事件满足 a !-> b 且 b !-> a ,则二者并行(concurrent);

假设任意事件 a,a !-> a(事件在自身之前发生的系统,并不存在物理意义)。这表明->表示的是,系统中事件之间非自反性的偏序关系。

结合下图 1 所示的时空图,可以帮助我们理解上述定义。其中横轴表示空间,纵轴表示时间——时间靠后则纵坐标越大。图中的点表示事件,竖向的直线表示进程,曲线表示进程间传递的消息。显而易见,a -> b 表示在进程间通过消息,从 a 到达 b。比如图 1 中有 p1 -> r4

space-time-fig-1

对该定义的另一种理解是,a -> b 表示事件 a 有可能导致事件 b 发生。当两个事件互相不为因果时,两者就是并行的。举例来说,图 1 里的事件 p3q3 是并行发生的,即使图中描述的情形是 q3 发生的物理时间是在在 p3 之前,但对进程 P 而言,在 p4 时间点收到消息之前,它无法得知进程 Q 在 q3 时在做什么。(在事件 p4 之前,进程 P 最多知道进程 Q 在 q3 时将要做什么)。

这个定义对于熟悉狭义相对论不变时空方程的读者,理解起来非常自然。现实中,通过可能被发送的消息来定义事件顺序。但是我们采用更加务实的办法,即只考虑实际被发送的消息。当系统知道明确已发生的事件,我们就可以确定系统是否正确运行,而无需知道那些可能发生的事件。

逻辑时钟|Logical Clocks

现在,我们引入时钟。从一个抽象的观点开始——时钟是为事件分配编号的方式,其中编号可看作为事件发生的时间。更精确的表述,对于任意进程 Pi,定义时钟 Ci,其中,Ci(a) 表示进程 Pi 中事件 a 的编号分配函数。整个时钟系统通过函数 C 来分配,如果事件 b 在进程 Pj 中,那么 C(b) = Cj(b)。到目前为止,我们没有做任何关于时钟 Ci(a) 和物理时间关系的假设,所以我们可以把 Ci(a) 看成是逻辑时钟而非物理时钟。逻辑时钟可以不通过真实的计时工具来进行计数。

我们现在来思考该时钟系统正确性的含义。我们不能把定义的正确性建立在物理时钟之上,否则会导致引入记录物理时间的时钟。逻辑时钟的定义必须基于事件发生的顺序。最合理的条件是,如果事件 a 发生在事件 b 之前,那么 a 的发生事件应该比 b 更早。通过下面的式子更正式的进行表达该条件:

时钟条件,对于任意事件 a、b:
            if a -> b then C(a) < C(b)

注意,上述式子的反推是不成立的(C(a) < C(b),不能反推出 a -> b),否则就意味着两个并行的事件必须发生在同一时间。在图 1 中,事件 p2p3 均和事件 q3 并行,如果要求它们必须和 q3 在相同时间发生,就和时钟条件 p2 -> p3 相矛盾。

从对->关系的定义中,容易得出,满足时钟条件需要符合以下两点:

  • C1: 当进程 Pi 中的事件 a 在事件 b 之前,则 Ci(a) < Ci(b)
  • C2: 当事件 a 是进程 Pi 的消息发送事件,事件 b 是进程 Pj 的消息接收事件,则 Ci(a) < Cj(b)

结合时间-空间图来分析时钟。我们想象一个进程的时钟会对每个数字做「滴答」,且「滴答」发生在进程中的事件之间。举个例子,如果进程 Pi 中的相邻事件 a 和 b,有 Ci(a) = 4 和 Ci(b) = 7,那么时钟会在这两个事件中间,依次滴答 5,6,7。我们把不同进程间连续的「滴答」用虚线连接,图 1 就变成如下图 2。条件 C1 意味着同一进程中任意两个事件必然存在一条「滴答」虚线;条件 C2 意味着任意消息线必然会穿过一条「滴答」线。通过对->关系的图示,很容易明白为什么满足上述两个条件 C1、C2 意味着时钟条件的成立。

space-time-fig-2

我们可以把「滴答」线作为时间-空间笛卡尔坐标系里的时间轴。将图 2 中的「滴答」线画直,就得到如下图 3。图 3 是图 2 所表达的事件系统的另一种表现形式。如果不引入物理时间(这会导致引入物理时钟),就无法决定哪个图示更好的表现了真实系统。

读者可能发现,如果把二维的网络进程可视化,构成一个三维的时间-空间图,会很有帮助。进程和消息仍然用线条表示,而「滴答」线则用二维平面来表示。

现在假设,执行过程就是算法,事件则表示执行的具体动作。我们会展示如何在进程执行过程中,引入满足时钟条件的时钟。进程 Pi 的时钟用寄存器 Ci 表示,因此 Ci(a) 表示事件 a 发生时,寄存器 Ci 的值。Ci 的值会在事件之间变化,因此变更 Ci 的值并不构成事件本身。

要保证这个时钟系统可以满足时钟条件,我们要确保其同时满足条件 C1 和 C2。条件 C1 很简单,只需要进程遵循下面的规则:

  • IR1. 进程 Pi 中, Ci 会在连续的事件中递增。

要满足条件 C2,我们要求任意消息 m 包含它被发送的时间戳信息 Tm。当另一进程接收到时间戳 Tm 的消息时,该进程必须将其时钟调整到大于 Tm。我们用下面的规则做更准确的描述:

  • IR2. (a) 如果事件 a 是进程 Pi 发送消息 m 的事件,而消息 m 包含了时间戳 Tm = Ci(a)。(b) 当进程 Pj 接收到消息 m 时,Pj 把 Cj 设置为大于或等于它当前的值,且大于 Tm

在规则 IR2(b) 中,我们认为接收消息 m 的事件发生在 Cj 被设置之后。很明显,规则 IR2 保证满足条件 C2。因此,规则 IR1 和 IR2 的实现,满足了时钟条件,从而保证正确的逻辑时钟系统。

全局事件顺序|Ordering the Events Totally

我们可以用满足时钟条件的时钟系统,给系统中所有事件设置全局的顺序。简单的通过事件发生的时间进行排序。为了打破平局,我们使用了进程间的任意的一个全序关系<。更准确的说,我们定义了一种关系=>:如果 a 是进程 Pi 种的事件,b 是进程 Pj 中的事件,则当且仅当满足以下任意条件时,a => b:

  • Ci(a) < Cj(b)
  • Ci(a) = Cj(b) 且 Pi < Pj

容易发现这定义了全序(Total ordering),且时钟条件表明如果 a -> b,则 a => b。换言之,=> 关系是把「之前发生」(happened before)的偏序关系补全成全序关系的一种方式。

全序关系=>依赖时钟系统 Ci,但并不唯一。选择不同的时钟,会产生不同的=>关系。给定任意一个由偏序关系->扩展而来的全序关系=>,都存在一个满足时钟条件的时钟,从而构成该关系。只有偏序关系->才是系统中的事件唯一确定的。

确定事件的全序关系,对实现分布式系统非常有用。实际上,实现逻辑时钟系统的目的就是为了获取全序关系。我们会通过解决版本互斥问题来描述事件全序关系的使用。对于由一组共享单一资源的进程所组成的系统,同一时刻只能有一个进程使用该资源,因此进程间必须同步以避免冲突。我们希望找到一种满足以下 3 个条件的资源分配算法:

  1. 进程要获取资源,必须要等待当前获取该资源的进程将其释放;
  2. 对资源的多个请求,必须要按其创建的顺序依次处理;
  3. 如果获取资源的进程最终都会释放掉资源,则所有对资源的请求都将最终成功;

我们假定单一资源初始时被授予单个进程。

这都是非常自然的条件。它们准确地说明了什么样的方案才是正确的。观察上述条件是是如何关系到事件顺序的。条件-2 没有说明对并发请求资源的授予顺序。

意识到这是一个关键问题很重要。通过中心进程同一分配资源的方式不可取,除非设定额外的假设。来看这样一个场景,P0 是做资源分配的中心进程。假设进程 P1 向 P0 发送资源请求,再向 P2 发送一条消息。在接收到信息后,P2向 P0 发送资源请求。P2 的请求可能会比 P1 先到达 P0,如果 P2 的资源请求被先授予,则违背了条件-2 的要求。

要解决该问题,我们实现了一个符合 IR1 和 IR2 的时钟系统,并且通过该时钟系统来定义所有事件的全序关系=>。这提供了所有资源请求和释放处理的全序关系。有了这个顺序,找到解决方案变得直观可行。只要确保每个进程知道所有其他进程的处理。

为了简化问题,我们做出一些假设。它们非必需,但它们的引入可以规避过多的细节。首先假设任意两个进程 Pi 和 Pj,Pi 发送到 Pj 的多个消息,会按照它们的发送顺序依次被接收。此外,我们假设所有消息最终都会被接收(避免引入消息序号和消息确认协议)。我们还假设进程可以直接向其他任意进程发送消息。

每个进程维护其请求队列,并对其他进程不可见。假设请求队列初始时包含一条资源请求消息 T0:P0,其中 P0 表示初始时获得资源的进程,T0 小于任意时钟的初始时间。

算法由以下 5 条规则定义。为了方便,假定每个规则定义的动作都构成一个事件。

  1. blah
  2. blah
  3. blah
  4. blah
  5. blah

space-time-fig-3

反常行为|Anomalous Behavior

结论


Lamport 论文链接