Flabby

Paper -- Time, Clocks, and Ordering of Events in a Distributed System consensus

22 May 2017

Introduction

  • 这是Leslie Lamport在1978年发表的关于分布式系统中时间、时钟以及事件顺序的论文，可能是Lamport被引用最多次的论文。
  • 相对论告诉我们时空中不会有完全不变的全序关系；不同的观察者对两个事件“发生在之前”会得出不同的结果；分布式系统中很难判断事件的顺序，只有两个事件有因果关系时，才存在部分有序的关系。
  • 作者提出分布式状态机的概念：认为分布式系统是一种特殊序列的状态机（一个通过处理器组成的网络），因此能够排序所有事件的算法就可以实现分布式系统；
  • 本文也描述了逻辑时钟的同步问题。

我们说分布式系统，主要是消息传递延迟很大；而集中式系统的一个进程之间的传递延迟几乎可以忽略。

Partial Ordering

  • 首先，我们假设系统是由多个进程组成的。每个进程都是一个事件的序列，按照事件的发生顺序来组织；
  • 其次，发送或者接受消息也是一个事件；
  • 最后，我们不使用物理时钟;
  • 现在来定义“发生在前”这种关系：

“->”是事件之间的最小关系，其满足以下3种条件：

  • (1) a和b是同一进程中的事件，a早于b，则a -> b;

  • (2) 对于同一个消息，a是发送的事件，b是接受的事件，则a -> b;

  • (3) 如果a->b, b->c, 则a—>c; 两个不同事件a,b是并发的，当a -\-> b 并且b -\-> a

  • 另外，a -\-> a; 所以发生在前关系是一种非自反的偏序关系；

图1是一个时空图，水平方向是空间，竖直方向从下到上是时间顺序，点表示时间，波浪线表示发送消息。 图中可以看出p1->q2, q2->r3, 和p1->r4。也可以看出p3和q3是并发的，虽然从物理时间来看，q3早于p3；

Fig 1

Logical Clocks

  • 我们现在引入逻辑时钟。我们可以把时钟看做给一个时间赋一个数字，而这个数字就表示时间。
  • 准确来说，我们定义：

  • 每个进程Pi的时钟Ci，是一个给事件a赋值为Ci<a>的函数；

  • 整个系统的时钟为C，给事件b赋值C<b>；如果b是Pj进程的一个事件，则C<b> = Cj<b>

另外，我们现在不考虑物理时钟，因为更复杂；

逻辑时钟需要满足的条件Clock Condition

任意的事件a,b: 如果a->b, 则C<a> < C<b>

通过发生在前的定义，很容易得出如果以下两个条件成立，则clock condition成立。

  • C1. 如果a b是进程Pi的事件，a早于b， 则Ci<a> < Ci<b>;

  • C2. 对于一个消息，如果a是进程Pi的发送事件，b是这个消息在进程Pj的接收事件， 则Ci<a> < Cj<b>

我们在时空图的不同线程之间画出“时刻线”，C1要求同一进程线的任何两个事件之间要有时刻线；C2说明消息线要和时刻线交叉，得到图2。

Fig 2

当我们把时间作为坐标系的一个维度，可以得到图3. Fig 3

为了满足C1，C2, 实现这样的系统，我们需要遵守一些实现的原则：

  • IR1. 每个进程Pi，连续的两个事件之间需要增加Ci；

  • IR2. （我们给每条消息增加了发送的时间戳Tm）

    • (a) 消息m的发送进程Pi的发送时间是a，则消息m包括时间戳Tm = Ci<a>
    • (b) 消息m的接收进程Pj会设置Cj大于等于当前值，并且大于Tm；

Ordering the events totally

我们要根据逻辑时间对系统的所有事件排序了。用”<~”表示任意的全序关系。

我们定义”=>”:

进程Pi的事件a和进程Pj的事件b，a => b当且仅当

(i) Ci(a) < Cj(b) 或者 (ii) Ci(a) == Cj(b) and Pi <~ Pj

”=>”可以定义出全序关系，但是并不唯一。

Example: mutual exclusive

我们实现一个正确的逻辑时钟就是为了获得全序关系，从而实现分布式系统。我们通过一个互斥的问题来分析。假设固定进程的系统共享全局唯一的资源，每次只能有一个进程访问，因为需要同步这些进程。 算法应该3个条件：

(I) 已经授权访问的进程必须释放资源，以便能够授权给其他进程；

(II) 不同的访问请求要按照请求顺序来授权；

(III) 如果每个进程最终都释放资源，那么每个请求最终都能被授权；

为了简化问题，我们假设：不同进程之间的消息按照发送顺序被接收到；并且消息不会丢掉，进程之间全联通； 这样，每个进程维护自己的请求队列，初始包括一条消息T0:P0，表示进程P0初始化时被授权，T0是小于时钟初始值的一个值。

具体的算法可以分为5个规则：

  • 1 请求资源：
    • 进程Pi发送消息 Tm:Pi 给其他所有进程；
    • Pi把请求的消息加入自己的请求队列；
  • 2 接收请求资源的消息：Pj接收到Pi的请求消息Tm:Pi
    • Pj把消息加入自己的队列；
    • Pj给Pi回复一个带时间戳的ack消息；
  • 3 释放资源：
    • Pi从请求队列中删除Tm:Pi的请求消息；
    • Pi发送带时间戳的释放资源的消息给其他所有进程
  • 4 接收释放资源的消息：Pj接收到Pi释放资源的消息
    • Pj从队列里删除所有的Tm:Pi请求消息；
  • 5 Pi在以下两个条件成立时，可以被授权访问资源：
    • (i) Pi的队列里有一条Tm:Pi的请求，并且按照全序关系，是最早的一条消息；
    • (ii) Pi已经收到每一个其他进程的回复消息，时间在Tm之后；

这个分布式算法，不需要中心的同步线程或者同步存储。这就是一个分布式状态机。每个状态的输入就是进程的申请和释放资源的命令。每个进程独立的运行这个状态机。本文不讨论失败的场景。

Anomalous Behavior

”=>”这种全序关系会有一些这样的异常场景：比如A同学发出一个请求a，然后和遥远异地的B同学通电话，B同学发出请求b，很有可能请求b的逻辑时间戳更小。系统没办法知道a早于b，因为没办法使用系统之外的信息。

解决这一问题两种思路：一种是交给用户，让他们来给出不同的时间值；另一种就是构建出更强的时钟，能够加入物理时空，也就是使用物理时钟。

物理时钟

引入物理时钟很简单，直接用Ci(t)表示物理时间t的时钟读数。为了数学角度方便，假设时间是连续可导的，除了重置时间导致的一些跳跃。导数dCi(t)/dt就是时钟速率了。

物理时钟需要满足条件 dCi(t)/dt =~ 1；同时Ci(t) =~ Cj(t)。数学语言的表述就不展开了。

考虑到任意两个时钟速率不会完全一样，需要一些同步机制。假设消息m在物理时间t发出，在t’收到；并且接收进程知道最小延迟Um, 现在物理时钟的实现原则是：

IR1’. 如果进程Pi在时间t没有收到消息，Ci在t可导，dCi(t)/dt > 0;

IR2’. (a) 如果Pi在物理时间t发送消息m，m包括时间戳Tm = Ci(t); (b)在t’收到消息时，Pj设置Cj(t’) = max(Cj(t’ - 0), Tm + Um)。 其中Cj(t’ - 0)是一个极限。

参考

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

blog comments powered by Disqus