分布式系统里的时间、时钟和事件顺序

Posted by cwen 2017-10-22

以往编写单机程序的时候,如何来判断先后顺序,第一个想到的就是分配一个唯一时间戳,然后根据时间戳的大小来判断事件发生的先后顺序, 但是放在分布式系统就不一定有效…

逻辑时钟和物理时钟

物理时间可以用严格的绝对时间来表示事件的发生顺序,但是在分布式的环境中,由于网络等因素无法做到完全的一致的时间,即使使用 NTP 时间,也是会有纳秒的误差。这样就导致在误差事件内发生的事件的先后顺序就很难判断了。

1978 年,Leslie Lamport 在 Time, Clocks and the Ordering of Events in a Distributed System 论文中提出了逻辑时钟的概念。在分布式环境中,通过一系列规则来定义逻辑时钟的变化。从而能通过逻辑时钟来对分布式系统中的事件的先后顺序进行判断。逻辑时钟本质上定义了一种 happen before 关系。

happen before 关系(偏序关系,部分有序)

在分布式系统中,一个进程 process 内的多个事件,自然地具备事件的先后顺序,或者说一个 process 本身就是一个有先验顺序的全序的事件集合。除了 process 内在的顺序,消息的发送和接收事件也是有因果序的。基于这两点,我们定义 happen-before 关系,写作 ->

定义: 是一个分布式系统中事件集合上满足如下条件的最小关系:

  1. 如果a和b是同一个process内的事件,且a在b之前发生,那么 $$a->b
  2. 如果a是一个process发送消息事件,b是另一个进程接收该消息的事件,那么$$a->b
  3. $$∀a,b,c,a→b,b→c⟹a→c (即“在……之前发生”的关系具备传递性(transitivity)) 如果 $$a↛b,b↛a, 那么称 a 和 b 是并发(concurrent)的。 根据定义,可以知道happen-before关系 -> 是一个系统所有事件集合之上的反自反偏序关系。

逻辑时钟

定义:定义为一个以事件为输入,输出为某个有序数的函数C。若对所有事件恒满足:

∀a,b\in E,a→b⟹C(a)<C(b)

则称该函数C满足时钟约束。

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

实现: 满足如下两条规则:

  1. 在同一进程内,C单调递增;
  2. 如果事件 a 是由进程 Pi发送一个消息 m , 消息 m 包含一个时间戳 T(m) = Ci(a), 进程 Pj 收到一个消息 m,这时候 Pj 设置 Cj 一定大于或等于之的时间,但是一定要比T(m) 大 。 函数 C 完全满足之前定义的偏序关系。

全序关系

如果$$C(a) = C(b),那a、b事件的顺序又是怎样的?假设a、b分别在节点P、Q上发生,Pi、Qj分别表示我们给P、Q的编号,如果 $$C(a) = C(b) 并且 Pi < Qj,同样定义为a发生在b之前,记作 $$a => b。假如我们对下图的A、B、C分别编号$$Ai = 1、Bj = 2、Ck = 3,因 $$C(B4) = C(C3) 并且$$Bj < Ck,则 $$B4 => C3

通过以上定义,我们可以对所有事件排序、获得事件的全序关系(total order)。

结论:→ 关系确定了唯一的部分有序关系;而 ⇒ 则是人为指定的完全排序关系,根据指定规则不同,⇒

关系可以有无穷多个。(在单一操作系统内的一个最简单的指定规则就是,当两事件时刻相等时,用进程号来分出前后)

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

强时钟约束

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

定义:若对时钟函数C,满足:

∀a,b\in E,a→→b⟹C(a)<C(b)

则称函数满足强时钟约束。

证明强时钟约束可保证时间上的先后关系略( 数学,有点看不懂,后面在细细研究 http://blog.yangliu.online/2016/09/10/logic-clock-md ) 分布式系统理论基础 - 时间、时钟和事件顺序

参考

  1. Time, Clocks and the Ordering of Events in a Distributed System
  2. 分布式系统之逻辑时钟
  3. 分布式系统理论基础 - 时间、时钟和事件顺序