Lamport逻辑时钟

本文是《如何学习分布式系统》中，关于时钟的相关介绍。

前言

《Time, Clocks, and the Ordering of Events in a Distributed System》是Lamport老哥的论文，这篇论文在1978年7月发表在《Communication of ACM》，于2000年获得了首届PODC最具影响力论文奖，于2007年获得了“ACM SIGOPS Hall of Fame Award”。这篇论文被多次进行引用，里面提出了分布式系统中的多个关键概念，例如：事件先后的happen-before，定义关联事件顺序的偏序关系，定义所有事件顺序的全序关系，逻辑时钟，物理时间的同步，分布式互斥算法，state machine等等。

本文中我们只涉及逻辑时钟相关部分。

这篇论文里的State machine经常被忽略，所以作者自己都出来声明了一下。
This is my most often cited paper. Many computer scientists claim to have read it. But I have rarely encountered anyone who was aware that the paper said anything about state machines. People seem to think that it is about either the causality relation on events in a distributed system, or the distributed mutual exclusion problem. People have insisted that there is nothing about state machines in the paper. I’ve even had to go back and reread it to convince myself that I really did remember what I had written.

狭义相对论

说出来你可能不信，计算机领域的论文里会出现相对论，但是实际上据说作者就是从物理学中获得的灵感。在狭义相对论中，认为随着参考系的变化，观测到的事件发生顺序有可能发生变化。比如下图中，有一辆运动的车辆，t=0时，车辆的中心向两边发射一束光线。在车上的人看来，光速到底两端的事件是同时的，在车下的人看来，光先到底车尾，后到达车头。

但是如果事件之间发生了关联，即两个事件有因果关系，那么因果关系会得到保留。

更多相关内容，请参考相对论相关文章。

在分布式的系统当中，很难取得精确的物理时间，作者提出了逻辑时钟来判断事件的因果关系，来决定事件的先后顺序。

happen before偏序关系

首先作者定义了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，也不存在b -> a，那么a和b是并发的。

作者用上面这个图片展示了时序关系，竖直方向代表时间，从下向上增长，圆点代表事件，波浪线代表发送消息。可以看出p1 -> r4，但是p3和q3是并发的。

逻辑时钟

定义C_i作为进程P_i的时钟，C_i(a)用来给事件a产生一个数字，代表事件的时间。
定义C作为系统的时钟，如果事件b属于进程P_i，那么C(b)=C_i(b)
系统内时钟条件如下：如果a -> b,那么C(a) < C(b)。
注意反之则不然，因为那样会推导出对于并发的两个事件a和b，存在C(a)=C(b)。上图中p2和p3都和q3并发，就意味着C(p2)=C(p3)，这显然不合理。

从->的定义可以推出如下结论：

1. 事件a和b在同一个进程P_i中发生，a在b之前发生，那么C_i(a) < C_i(b)
2. 事件a是进程Pi发送信息，事件b是进程P_j接收该信息，那么C_i(a) < C_j(b)

为了实现逻辑时钟，假设每个进程i有个变量C_i，用来产生事件的时间。C_i按如下规则变化：

1. 每个进程i在节点内事件发生时将C_i递增
2. 假设事件a是进程i发送消息m的事件，m需要携带时间戳t=C_i(a)；进程j接收到m之后，将C_j设置为比t大并且不小于Cj当前值的值

作为一个实现，我们设置Ci的初始值为0，并且：

1. 每个进程i在节点内事件发生时将C_i加1
2. 假设事件a是进程i发送消息m的事件，m需要携带时间戳t=C_i(a)；进程j接收到m之后，将C_j设置为max(t,C_j)+1

全序关系

有了逻辑时钟，我们可以定义所有事件的全序关系了。注意，因为存在两个事件的逻辑时钟一致的情况，所以这里在先任意的选择一个进程全序关系<-，例如我们可以将进程编号的大小关系作为<-。
进程i中的事件a和进程j中的事件b的全序关系=>定义为满足如下任意条件时，a=>b：

1. C_i(a) < C_j(b)
2. C_i(a) = C_j(b) 并且 Pi <- Pj

值得注意的是，这个全序关系不是唯一的，和<-的选择有很大的关系。

后记

在论文的后面，作者还介绍了用事件全序关系和state machine实现的分布式互斥算法和时钟同步算法，有兴趣的读者可以自行参阅。

更多相关内容，请参考系列文章《如何学习分布式系统》。