Introduction

本文是学习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的定义如下(用->表示)

如果a和b在同一进程中，并且a发生在b之前，那么a->b
如果a是一个进程发消息的事件，b是另一个进程接收这条消息的事件，则a->b
如果a->b且b->c，那么a->c。
如果同时不满足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，如下

1 2	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个原则如下

为了请求资源，进程Pi发送消息Tm:Pi给所有的其他进程，并且把这个消息放到进程队列中，Tm是消息的时间戳
当进程Pj接收到了进程Pi的Tm：Pi请求后，会把它放到自己的请求队列，然后发送一个带时间戳的确认消息给Pi
为了释放资源，进程Pi移除所有Tm:Pi的请求消息，然后发送带时间戳的Pi释放资源请求消息给其他所有的进程
当进程Pj接收到进程Pi释放资源的请求，它会移除队列中任意的Tm:Pi的资源请求
当满足以下两个条件时，进程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，则满足以下条件

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

PS:
本博客更新会在第一时间推送到微信公众号，欢迎大家关注。

References

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