《云数据管理》 2.1 逻辑时间和Lamport时钟

本节书摘来自华章出版社《云数据管理》一书中的第2章，第1.1节，作者迪卫艾肯特·阿格拉沃尔，更多章节内容可以访问云栖社区“华章计算机”公众号查看   Lamport 于1978年在他的一篇代表性论文里提出了一个简单的分布式系统模型[Lamport, 1978]。该模型中，进程被建模成一个全序事件的序列。事件分为本地（local）事件、发送（send）事件和接收（receive）事件。发送事件负责发送消息，该消息由相应的接收事件接收。本地事件是非通信事件，如，内存读写、矩阵相乘等。图2-1展示了一个包括4个进程（p1、p2、p3和p4）的分布式系统示例。事件e2和e4在进程p1上执行，事件e1、e3和e9在进程p2执行，等等。事件e3是进程p2上的本地事件，而事件e1是一个发送事件，e2是相应的接收事件。

若两个事件e和f满足下列任一条件，则事件e发生在事件f之间，记作e→f：

1. 如果e和f是发生在同一进程内的两个事件，并且e发生在f之前，那么e→f；

2. 如果e代表了某个进程的消息发送事件send(m)，f代表另一进程中针对这同一个消息的接收事件receive(m)，那么e→f；

3. 如果存在一个事件g，满足e→g并且g→f，那么e→f。

 

图2-1　事件和消息

“发生在前”（happens-before）关系可以很好地反映任意两个事件之间的潜在因果依赖关系。并且，如果两个事件e和f既不存在e→f关系，也不存在f→e关系，那么e和f是并发的。在图2-1中，事件e4发生在事件e6之前，而事件e3与事件e2和e4都是并发的。

时间概念以及时间与事件之间的关系对很多分布式系统协议来说都是至关重要的。一般情况下，不一定需要实时时钟或近似实时时钟，只要有一个时间概念能够捕获潜在的因果关系就足够了。Lamport引入了一种可以捕获事件之间的潜在因果关系的逻辑时钟概念。逻辑时钟为每一个事件e赋一个值clock(e)，因此，对任意两个事件e和f，存在如下关系：

如果e→f，那么clock(e)<clock(f)。

为了能够实现这种逻辑时钟，Lamport为每一个进程设置了一个时钟计数器。该计数器在同一进程中的任意两个事件之间都必须是递增的，并且，每一个消息都携带了发送者的时钟值。当消息到达目的地之后，本地时钟计数器被设置为本地值的最大值，同时消息的时间戳加1。这种实现方式可以满足上述逻辑时钟的条件。

在图2-2中，使用与图2-1相同的例子，为系统中的所有事件都赋一个逻辑时间。

 

图2-2　Lamport时钟

因为“发生在前”关系是一个偏序，因此，多个事件可能被赋值相同的逻辑时钟。但是，在很多协议中，为每一个事件赋一个唯一的时间值更为方便。这种情况下，为了打破这种关系，时间值可以设置为<t, p>，其中，t是本地时钟计数器设置的逻辑时间，p是事件执行所在进程的进程标识。一般情况下，每一个进程都被赋值一个唯一的全序的进程标识，这些进程标识可以打破具有相同逻辑时间的事件之间的关系。