lamport logical clock

发表于

对Lamport Logical Clock的理解

不合理的事件发生顺序

通常人们习惯使用物理时间来描述多个事件发生的前后关系，比如，event A发生的时间早于event B发生的时间，那么可以得出结论A happened before B，这似乎是一个简单得不值得探讨的问题。然而，对于生活中的大多数情况而言，event A和event B要么发生在同一个地点、基于的是同一个时钟，要么两个事件发生的事件间隔足够长，大于两地时钟的误差。事实上，当event A和event B基于的是不同的时钟，那么基于上述的判断原则可能会得出不合理的结论，除非保证不同时钟之间有足够高的时钟同步精度。比如node 1发送消息给node 2，node 1本地时钟当前时间为t1，node 2收到消息时根据本地时钟读出时间t2，如果时钟同步精度不够，误差较大，可能出现t2＜t1的情况，即node 2先收到消息，node 1后发送，这显然是不合理的（破坏了发送消息和接受消息两个事件之间的causality）。

Happened-Before关系

在分布式系统，多个node分处各地，互相通过网络交换消息，要通过提供高精度的时间同步机制来测量不同node上event发生的顺序十分困难。Lamport的<Time, Clocks, and Ordering of Events in a Distributed System>就是要找到一个不使用物理时间就可以在分布式环境下正确“测量”事件顺序的方法。其实从上面node 1向node 2传输消息的例子可以看出，即便我们不测量t1和t2，我们应该也能得出t2应该大于t1，这意味着某些事件之间本身就有着暗示顺序的信息，Lamport把这种信息称为happened-before关系：

定义：happened-before 关系”$\rightarrow$”满足：
（1）如果事件a和b发生在同一个进程，a先于b发生，那么a$\rightarrow$b
（2）如果事件a表示一个进程发送消息，事件b表示另一个进程接收这条消息，那么a$\rightarrow$b（因果性）
（3）如果a$\rightarrow$b并且b$\rightarrow$c，那么a$\rightarrow$c（传递性）

对于任何事件a，a$\nrightarrow$a（没有物理意义）
如果a$\rightarrow$b，那么事件a可能causally影响了事件b，如果a、b之间不存在happened-before关系，那么称他们之间是concurrency关系。

逻辑时间（logical clock）

为了避免依赖物理时间，可以设计一种仅仅依赖于事件happened-before关系的时间，然而happened-before关系是一种偏序关系，只能比较具有happened-before关系的事件顺序，对于非happened-before关系的事件无法比较，如果能将happens-before偏序关系扩展成全序关系，在使用中就能无差异地应用于任何两个事件，Lamport将这样的时间称为逻辑时间（将时间的概念抽象成一种对事件序号）。这种想法之所以可行是因为对于没有happened-before关系的两个事件，两者在真实的物理时间中发生的前后关系对系统的结果是没有任何影响的，而逻辑时间无非是给这样的非happened-before关系加了一个顺序，为的是对非happened-before关系和happened-before关系提供了统一处理的方法，设事件a的逻辑时间为C(a)，对于事件a和事件b，如果a happened before b，那么C(a)一定小于C(b)，如果a和b没有happened-before关系，那么C(a)和C(b)的大小是无所谓的。

Clock Condition. 对任意事件a、b，如果a$\rightarrow$b，那么C(a) < C(b)

（反之不成立，如果C(a) < C(b)，无法得到a$\rightarrow$b，否则必须保证concurrency时C(a) == C(b)）
所以可以得出，对于任意确定的、由happened-before关系描述的事件系统，其全序逻辑时间是不唯一的，因为其中的非happened-before关系的全序顺序是有多种选择的。
根据happened-before的定义，得出逻辑时间的设计要求：

C1. 如果事件a和b在同一个进程中，并且a先于b发生，那么C(a) < C(b)
C2. 如果事件a表示一个进程发送消息，事件b表示另一个进程接收这条消息，那么C(a) < C(b)

为了实现逻辑时间，根据C1和C2的要求分别构造规则：

IR1. 每个进程$P_i$在任意两个连续的事件之间要增加$C_i$
IR2. (a) 如果事件a通过进程$P_i$传递消息$m$，那么消息$m$携带了时间戳$T_m = C_i(a)$。(b)进程$P_j$根据收到的消息$m$的时间戳，设置$C_j$，保证该值大于等于它当前的时间且大于$T_m$

因为接收消息的进程逻辑时间点要满足C1和C2，必须保证该时间大于等于同进程之前的逻辑时间以及大于发送进程发送消息时的逻辑时间。根据IR1和IR2的规则生成的时间就是确保能满足Clock Condition的逻辑时间。

定义一种新的全序关系$\Rightarrow$：

设事件a属于进程$P_i$，事件b属于进程$P_j$，那么$a\Rightarrow b$，当且仅当：
(i) $C_i(a) < C_j(b)$，或者
(ii) $C_i(a) = C_j(b)$，且$P_i \prec P_j$

容易推得：

如果$a\rightarrow b$，那么$a\Rightarrow b$，同样，反之不成立

关系$\Rightarrow$是基于happened-before关系扩展出的全序关系

如何使用全序逻辑时间？

论文举了个例子: 实现一个分布式锁，要求满足:

I. 锁必须先被释放，其他进程才能获得
II. 某个进程中不同的请求得到锁的顺序和请求顺序一致
III. 如果得到锁的进程最终都会释放锁。那么所有要求获得锁的进程一定最终也会获得锁，即不会死锁

如果使用进程$P_0$作为调度进程，$P_1$发送请求给$P_0$，同时发送消息给$P_2$，$P_2$收到$P_1$的消息后发送请求给$P_0$，此时有可能出现$P_2$的请求在$P_1$请求之前到达，违反要求2。

假设：

  1. 对于任意进程$P_i$和$P_j$，$P_j$接收到从$P_i$发送的消息顺序和消息发送的顺序一致(先收到的一定是先发送的)
  2. 任何消息最终都能被接收到
  3. 每个进程能够直接向任何其他进程发送消息

每个进程都维护自己的请求队列（request queue），并只能看到自己的队列。假设请求队列初始包含一个请求资源消息$T_0:P_0$，其中，$P_0$表示最初获得资源的进程，$T_0$初始化为比任何进程当前逻辑时间都小的值。

算法根据以下5个规则：

  1. 为了请求资源，$P_i$向所有其他进程发送消息$T_m:P_i$，并将该消息放入自身的请求队列，$T_m$是该消息的时间戳
  2. $P_j$收到请求资源消息$T_m:P_i$后，将该消息放入自身的请求队列并发送一个携带时间戳的确认消息给$P_i$（注：确认消息的时间戳一定大于$T_m$，若$P_j$已经发送过时间戳大于$T_m$的请求给$P_i$，则无需发送确认）
  3. 为了释放资源，$P_i$从自身请求队列中移除$T_m:P_i$消息，并向其余进程发送一条携带时间戳的$P_i$释放资源消息
  4. $P_j$收到释放资源消息$P_i$后，从请求队列中移除$T_m:P_i$消息
  5. 当以下两个条件被满足时，$P_i$被认为获得资源：
    (i) 自身请求队列中存在一个$T_m:P_i$消息，这个消息按照$\Rightarrow$关系排在该队列之首
    (ii) $P_i$已接收到来自其余所有进程的消息（可以是请求，也可以是确认），并且这些消息携带的时间戳都在$T_m$之后

现在证明5个规则能够满足条件I-III,
首先，规则5(ii)和假设1、2能够推得，$P_i$被认为获得资源时，请求队列中已经包含了其余进程发送的、时间戳小于$T_m$的所有请求（这些请求一定在5(ii)收到的那些消息之前被收到），然而$T_m:P_i$根据$\Rightarrow$关系排在队列之首，说明没有来自其余进程小于$T_m:P_i$的请求，因为规则3、4是唯二从请求队列中移除消息的规则，因此条件I是成立的。
其次，若当前资源被释放，那么某个进程的请求队列之首会是来自自身的请求消息$T_n:P_j$，并且根据规则2，$P_j$请求队列中一定包含了所有其余进程发送的时间戳大于$T_n$的消息，满足5(ii)。这个顺序是以$\Rightarrow$的顺序为依据的，而$\Rightarrow$的顺序是对happened-before顺序的扩展，其并不会破坏事件发生的causality。所以按照$\Rightarrow$的顺序获得锁一定满足同一进程中请求的顺序，因此条件II满足。
最后，规则3和4暗示了每个进程最终会释放资源，释放后自然会有新的进程符合规则5，条件III成立。

从另一种角度去理解的话，逻辑时间使得不同进程对于整个分布式事件的顺序达成了一致，如果将每个进程看成一个状态机（State Machine），这些分布式事件构成了状态机的命令（Command），包括$P_i$请求资源、$P_i$释放资源。执行请求资源命令时，每个进程向自身的请求队列中添加消息（请求队列也是状态机的一部分），执行释放资源则移除消息。每个进程独立地执行状态机命令。之所以能够同步，是因为当进程在接收到所有其他进程发送的时间戳小于$T_m$的消息后，执行$T_m$消息的顺序就是确定的，并且对于每一个进程来说都是一致的。所以这种同步需要所有进程的参与，只要有进程失效，整个系统将无法正确工作。

参考资料：
[1] Lamport, L. 1978. Time, clocks, and the ordering of events in a distributed system.