Time, clocks, and the ordering of events in a distributed system 阅读笔记

Posted on | In | 阅读

参考文献：Lamport L. Time, clocks, and the ordering of events in a distributed system[J]. Communications of The ACM, 1978, 21(7): 558-565.

一、基本问题

本篇文章所讨论的问题是分布式系统中事件发生的先后顺序的问题。在日常生活中，我们经常通过时间，也就是日期、时分秒等等概念来确定时间发生的先后顺序。虽然这样的解释在单机系统或者一个很小的空间范围内不会出现太大的歧义，但是，在复杂的分布式系统当中，由于不同进程或是不同主机之间用于规定时间的时钟无法保证实时同步以及传输过程中的时延问题，这样的规定也就变得无效。例如两个进程A、B分别要对一个共享变量进行修改，在实际时间上A要比B先发出请求，理论上应该先满足A所发出的请求，但是A进程的请求比B进程的请求晚到达，这就会导致变量最终与期望的值不同。作者在文中强调我们一定要意识到在分布式系统中事件发生仅仅存在偏序关系这一点。所以在分布式系统中需要定义一种新的时间发生“序”的概念，使得不同进程间时间发生的顺序能够得到确定。

二、主要贡献

本文定义了一个应用于分布式多进程系统中事件发生的一个偏序关系“happen before”，并提出了一个算法，将这样的偏序关系推广为全序关系，并将全序关系应用于一个同步问题。但是这样的全序关系还会遇到一种异常情况，作者又提出利用同步物理时钟 (physical clocks) 来避免这样的问题。

三、偏序关系

偏序关系与全系关系不同，全序关系具有反对称性，这也就意味着全序关系中，任何两个元素之间都可以有关系。但偏序关系不具有反对称性，故两个元素之间不一定具有关系。像前面所说的，很多人在描述事件发生先后顺序时，都隐含地运用了一个全序关系，也就是物理理论中的时间关系。但是分布式系统中很难保持一个统一的精确的时钟，也就是两个事件间可能无法确定先.后关系，所以，作者将事件发生的前后关系定义为一个偏序集，也就是“happen before”关系，记作”->”。“happen before”关系的定义如下：

  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​，那么可以说两个事件是并发的 (concurrent)

作者通过一张“空间-时间”表来解释偏序关系，例如Figure 1，横向为不同的进程，纵向向上表示时间的推移，注意时间的推移只在单个进程上是有意义的。进程上的点代表了发生的事件，而波浪线表示消息，箭尾代表一个消息的发送事件而箭头表示消息到达的事件。按照上面的定义，偏序关系只定义在波浪线从箭尾到箭头以及进程线从下到上，这样一条路径上的点对这条路径上后续的点之间存在“happen before”关系（如p1​与r4​），若无法找到这样一条路径连接的两个点，则是并发关系（p3​与q3​）。

四、逻辑时钟

为了与物理时钟进行区分，作者提出了逻辑时钟的概念，定义为：每个进程Pi都有一个时钟Ci，当b是进程j的一个事件的时候，系统全局时钟C给b分配的时间为C<b> = Cj<b>。

逻辑时钟的大小与物理时钟的先后没有关系，仅仅与时间发生的先后有关系，即定义时钟条件 (Clock Condition)

  • Clock Condition. 对于任意的事件a，b，如果a->b则C<a> < C<b>.

这个条件的逆命题不能够成立，即C<a> < C<b>不能够推出a->b。

根据时钟条件以及前面定义的“happen before”偏序关系可以很容易地得出下面两个条件：

C1. 在同一个进程i中如果a比b先发生，那么Ci<a> < Ci<b>

C2. 若进程i的事件a是给进程j发送一条消息并且b事件是进程j接收这条消息的事件，那么Ci<a> < Cj<b>

再引入一个逻辑时钟“滴答” (tick)的概念，根据上面两个时钟条件，逻辑时钟在同一个进程先后的两个事件之间至少存在一个时钟tick，而在进程之间消息发送与接收事件之间，也要存在一个时钟tick。在图上如果用虚线表示时间tick的连线，同个进程的两个点之间一定存在一条连线，而消息发送的波浪线一定会穿过至少一条的连线。同时，由于进程与进程之间的物理时钟并不影响逻辑时钟，所以可以将每个进程轴上的点的距离进行任意地拉伸，比如把对应的tick对齐，使得tick之间的连线相互平行并垂直于进程轴，方便观察，如Figure 3所示。

为了满足两个时钟条件C1和C2，就要遵守下面两个实现规则 (Implementation rule)：

IR1. 每一个进程中连续的两个事件之间时钟值C要递增。

IR2. 如果事件a需要发送一条消息，那么它需要在消息中包含自己的时间戳 (timestamp)，当b收到这个消息后，读取消息中的时间戳后，需要设置设置自己的时钟值，设置的值不能比当前自己的时钟值小并且要大于消息中的时间戳。

显然IR1保证了C1的满足，而IR2保证了C2的满足。可以想到的一种最简单的实现就是单个进程中的每个非接收消息的事件偏序时间都等于前一个事件偏序事件+1，若该事件接收消息，则需要设置为max(prev, Tm) + 1，其中prev是该进程前一个事件的逻辑时间，Tm是收到消息中包含的时间戳。

五、扩展为事件的全序

文中提出了一种简单的方法，将事件的偏序关系推广到了整个分布式系统中所有事件的全序关系，这种定义的方法任意定义了一个进程上的全序关系“prec”，即给进程定义一个优先级，默认按照逻辑时钟值来进行排序，当逻辑时钟值相同时，则按照进程的全序关系来进行排序。

定义系统事件的全序关系“=>”：

  1. Ci<a> < Cj<b>，或者
  2. Ci<a> = Cj<b> and Pi prec Pj

这种定义方法有点类似于拓扑排序，即定义好偏序关系后，通过定义一个任意的优先级，形成最终的序列，但是其中的偏序关系也得到了保留。在本文讨论的问题中，就是当a->b则a=>b。但是这种全序的定义时十分随意的，不同的逻辑时钟，即使满足前面提到的两个实现规则，最终会产生不同的全序关系，不同的进程全序关系，最终的序列也不同。

六、互斥问题的应用

我们希望一个给进程分配资源的算法需要满足以下条件：

I. 资源分配给其他进程之前，之前分配的进程需要先释放这个资源

II. 资源要按照请求的先后顺序来进行分配

III. 只要每个被赋予权限的进程最终都释放了资源，那么所有的请求最终都能够被赋予资源

这三点看来都是简单的要求，而在实际中却不那么好满足。例如，采用中心调度进程P0来进行资源分配时，进程P1先向P0申请资源，然后P1向P2发送消息，P2收到消息后，向P0发送一个资源申请的请求，显然P1的请求应该先被满足，但是我们无法保证P1的请求比P2先到达。

为解决这个问题，作者使用一个满足IR1、IR2的系统时钟，生成一个事件的全序关系，并假设两个进程间的通信不会丢失且按序到达，那么算法规则定义如下：

  1. 申请资源时，进程Pi会发送一个带有时间戳的消息Tm:Pi给其他进程，并把这条消息放入自己的请求队列 (Request queue) 中
  2. 进程Pj接收到Tm:Pi后，也放入自己维护的请求队列中，并发回一个带有时间戳的消息
  3. 释放消息时，进程Pi移除所有自己请求队列中的Tm:Pi，并将释放进程的消息和时间戳发送给其他进程
  4. 当进程Pj收到释放资源消息时，也移除掉自己请求队列中的Tm:Pi
  5. 只有Pi本地验证当以下两个条件都满足的时候，进程Pi才会被分配资源：
    • Tm:Pi存在于自己的请求队列中并且在规定的全序关系中排在最前面
    • 收到了其他所有进程发来的时间戳晚于Tm的消息

这样的算法满足了前面的条件I-III：

  • 通过3和4可以保证条件I
  • 由于满足了全序序列，同时也满足了所有偏序关系，所以偏序关系上后出现的请求的时间戳一定会比先出现的要高，根据规则5(i)就能够按序进行资源赋予，满足条件II
  • 规则2保证了规则5(ii)的触发，规则3将会移除自己进程中需要释放的请求，规则4将会移除在其他进程中记录的请求，这样，无论按照全序规则的下一个请求出现在哪个进程中，都能够满足，即触发了规则5(i)，满足了条件III

七、物理时钟

上面所设计的系统已经能够利用逻辑时钟生成的全序序列来完成一个进程资源分配算法了，但是，上述的系统当一个进程崩溃时就无法运行，因为请求资源的的进程将无法收到所有其他进程的确认信息，也就无法满足规则5(ii)。然而仅仅凭借逻辑时钟，很难确认一个进程是否已经崩溃或只是处于事件的间隙间。

再考虑一种情况，当用户A使用计算机发送一个请求，然后他打电话让B（系统并不知到电话里的信息）也发送一个请求，由于系统并不知道电话里消息所形成的一个偏序关系，所以如果先收到B的消息的话，仍然会先满足B的请求，这就造成了一个异常行为 (Anomalous Behavior)。

上面两个例子表明了，在分布式系统中引入物理时钟是有必要的，逻辑时钟无法处理Anomalous Behavior这样的又系统外部信息所照成的异常。假设系统中产生的事件集合为ψ，而并上外部事件后的集合为ψ, 在ψ上定义新的“happen before”强时钟条件关系“–>”:

  • Strong Clock Condition. 对于任意的事件a，b，如果a–>b则C<a> = C<b>.

现在引入系统中物理时钟条件，系统中需要保证每个进程之间的物理时钟相互接近并且改变的速度之间也要相互接近，所以要满足以下两个物理时钟条件：

PC1. 存在一个常数κ << 1，对于任意i: |dCi(t)/dt - 1|<κ.

PC2. 对于任意i，j: |Ci(t)-Cj(t)|<ε.

这两个物理时钟条件要保证不发生异常行为，需要对时钟同步的过程中的两个变量ε ， κ进行限制。要满足Ci(t+μ)-Cj(t)>0，其中μ是进程间通信的时延，也就是说，两个进程间的物理时钟相差不能超过物理时延，在物理事件上较晚开始的事务当其他进程的消息到达后，依然要拥有更大的时间戳。同时根据PC2可以得出Ci(t+μ)-Ci(t)>(1-κ)μ，可以推导出，要满足Ci(t+μ)-Cj(t)>0，就要满足ε/(1-κ)<= μ.这两个物理时钟条件要保证不发生异常行为，需要对时钟同步的过程中的两个变量ε ， κ进行限制。要满足

最后将实现规则IR1，IR2进行推广

IR1’. 当任意进程Pi如果在物理事件t没有收到消息，那么Ci在t处可微并且dCi(t)/dt > 0.

IR2’. (a) Pi在t时刻发送一个带有一个时间戳Tm=Ci(t)的消息m. (b) Pj在t’时刻收到消息m，Pj设置Cj(t’)为max(Cj(t’-0), Tm+μm).

其中μm是传输的最小时延，Cj(t’-0)是Cj(t)在t’处的左极限。

八、总结

本文定义了分布式系统中的偏序关系“happen before”，并将其扩展为了全序关系，展示如何解决同步问题。并且讨论如何引入物理时钟来避免异常行为以及同步物理时钟需要满足的条件。可以说这篇文章对分布式系统的发展起到了奠基的作用。