分布式系统时序基础

Question

本文是学习 Time, Clocks, and the Ordering of Events in a Distributed System 论文的总结，本文总结了提出了通过 total ordering events 来解决分布式系统的同步问题。

What is a distributed system

• 空间分离的进程合集，进程之间只能通过消息交换来通信
• 进程之间的消息通信耗费的时间要远远高于单个进程间的通信时间

The Partial Ordering

在讨论 Partial Ordering 之前，先复习下离散数学中关系的特性，其中二元关系<>是针对集合 A 的。

• 如果对于任意的 a 属于 A，满足 a<>a，则二元关系是自反的
• 如果对于任意的 a，b 属于 A，如果满足 a<>b，且同时也满足 b<>a，则二元关系是对称的
• 如果对于任意的 a，b，c 属于 A，如果满足 a<>b 且 b<>c，也同时满足 a<>c，则二元关系是可传递的
• 如果对于任意的 a,b 属于 A，如果满足 a<>b 且 b<>a，则 a=b,则二元关系是反对称的

一个 partitial ordering 关系满足的条件是自反的，对称的和可传递的，因此在 partitial ordering 中，可能有两个元素之间是不相关的。

一个 total ordering 关系满足的条件是自反的，对称的，可传递的和反对称的，因此在 total ordering 中，两个元素一定是有关系的，要么是 a<>b 或 b<>a。

在分布式系统中，一个进程包含一系列的事件，对于同一进程内的事件，如果 a happens before b，那么 a 发生在 b 之前。并且，假定收或发消息都是一个事件。

happens before 的定义如下（用->表示)

1. 如果 a 和 b 在同一进程中，并且 a 发生在 b 之前，那么 a->b
2. 如果 a 是一个进程发消息的事件，b 是另一个进程接收这条消息的事件，则 a->b
3. 如果 a->b 且 b->c，那么 a->c。
4. 如果同时不满足 a->b，且 b->a，那么说 a 和 b 是 concurrent

且假定对于任意的 a，都不满足 a->a，因为一个事件不可能发生在本身之前。因此可以看出 happens before 是不满足自反性的 partial ordering。

以一个例子来说明 happens before 关系，如上图，垂直线上代表一个进程，从下往上，时间依次增加，水平的距离代表空间的隔离。原点代表一个事件，而曲线代表一条消息。

从图中很容易地看出，如果一个事件 a，能通过进程的线（从下往上) 和消息线（从左往右)，到达 b，那么 a->b，例如，p1->r4。直观地角度看，如果事件 a 能最终导致事件 b 发生，则可以说明 a->b。

在图中，p3 和 q4 是并行的事件，因为，只有到了 p4 才能确定 q4 的发生，而 q3 也只能确定 p1 发生。

Logical Clocks

对于逻辑时钟，对于每个事件会分配一个数字，认为这个数字就是事件发生的时间。

时钟的定义如下

• 对于一个进程 i，Ci(a) 表示进程 i 中事件 a 的发生时间
• 对于整个系统来讲，对于任意的事件 b，其发生时间为 C(b)，当 b 为进程 j 的事件时，则 C(b) = Cj(b)

为了使得事件按照正确的排序，需要使得如果事件 a 发生在事件 b 之前，那么 a 发生的时间要小于 b，如下

为了使得事件按照正确的排序，需要使得如果事件 a 发生在事件 b 之前，那么 a 发生的时间要小于 b，如下

for any events a, b
if a->b then C(a) < C(b)

根据关系->的定义，我们可以得出

• 如果 a 和 b 都是进程 i 中的事件，且 a 发生在 b 之前，那么 Ci(a) < Ci(b)
• 如果事件 a 发送消息给事件 b，a 属于进程 i，b 属于进程 j，那么 Ci(a) < Cj(b)

在上图中，水平虚线代表一次时钟的 tick。为了满足上述第一个条件，那么同一个进程中的事件之间必须要有 tick 线隔开；为了满足第二个条件，那么消息线必须跨过 tick 线。

为了让系统满足上述条件，在实现中，需要满足以下原则

• 对于每个进程，相邻的事件的时钟要增加 1
• (a) 如果事件 a 是进程 i 发送消息 m 的事件，发送时带时间戳 Tm = Ci(a)，(b) 事件 b 是进程 j 接受消息 m 的事件，那么事件 b 的取值为 max(进程 b 的当前时钟，Tm+1)

Ordering the Events Totally

total order 的事件关系=>定义如下：

如果事件 a 发生在进程 Pi，事件 b 发生在进程 Pj，那么当满足下列两者条件之一时，a=>b

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

根据以上条件，对于任意的两个事件，都能判断出它们之间的关系，因此是 total ordering 的。

通过一个例子来说明 total ordering events 的用法。问题为 mutual exclusion problem，即一个由一组进程组成的系统，共享一个资源，该资源每次只能让一个进程使用，因此，需要进程间需要作同步防止冲突。需要找一个算法，满足以下条件：

• 某进程被分配了资源后，必须要等该进程释放该资源后，才能再把资源分配给其他进程
• 不同的资源请求会按照它们申请的顺序进行分配
• 如果每个被分配资源的进程最终都会释放，那么每个请求最终都会被分配资源

在设计算法前，假定系统满足如下条件：

• 对于任意两个进程 Pi 和 Pj，从 Pi 和 Pj 发送的消息，接受的顺序与发送的顺序一致
• 每个消息最终都会被接收
• 每个进程可以直接发送消息给其他进程

每个进程都维护自己的队列，并且其他进程无法访问。我们假定一开始队列里面包含请求 T0:P0，其中 P0 是最初被分配资源的进程，T0 比任意的时钟的初始值都要小。

该算法的 5 个原则如下

1. 为了请求资源，进程 Pi 发送消息 Tm:Pi 给所有的其他进程，并且把这个消息放到进程队列中，Tm 是消息的时间戳
2. 当进程 Pj 接收到了进程 Pi 的 Tm：Pi 请求后，会把它放到自己的请求队列，然后发送一个带时间戳的确认消息给 Pi
3. 为了释放资源，进程 Pi 移除所有 Tm:Pi 的请求消息，然后发送带时间戳的 Pi 释放资源请求消息给其他所有的进程
4. 当进程 Pj 接收到进程 Pi 释放资源的请求，它会移除队列中任意的 Tm:Pi 的资源请求
5. 当满足以下两个条件时，进程 Pi 会被分配该资源：a) 有一个 Tm:Pi 的请求，按照=>关系排在队列第一位；b)Pi 接收到了一个时间戳大于 Tm 的来自所有其他进程的消息

Anomalous behavior

上面章节描述的=>关系可能导致 Anomalous behavior，以一个例子来说明。

假如一个由互联的电脑组成的系统，其中有共享的资源。一个用户在电脑 A 上发送请求共享资源，然后他打电话给朋友然他在电脑 B 上发送请求 B 也来请求那个资源。

在电脑 B 上，如果请求 a 还未到达之前，已经产生了请求 b，那么，在电脑 B 上，b 排在 a 前面

在电脑 A 上，则是请求 a 排在请求 b 前面，这样就会造成冲突。

有两种方案解决上述冲突：

• 让用户来保证不发生该冲突。例如，当请求 a 生成后，用户需要分配时间戳给请求 a，当用户让他朋友发送请求 b 的时候，需要保证分配一个大于 a 的时间戳
• 假设 S 是系统中所有事件的组成，而 S‘是包含 S 且外部事件的组合。定义==>在集合 S’上的 happen before，则满足以下条件

for any events a,b in S : if a==>b then C(a) < C(b)