分布式系统中的时序——Lamport逻辑时钟

时间是我们考虑问题时使用的基本概念之一。在我们观察、理解或设计一个分布式系统/协议时，也常常使用这个概念。我们常常会说“在xxx时候做xxx”或者“在xxx之后做xxx”。事实上，在一个系统中，我们绝大多数时候并不关心某个事件发生的绝对时间，而是关心事件之间的相对时间，相对顺序。对系统中的时间做较早研究的一篇文章是Lamport在1978年发表的“Time，Clocks，and the Ordering of Events in a Distributed System”。昨天阅读了这篇文章。文章的表述很直白，概念也相对简单。但正是这种简单的概念，构成了系统时间的基础。

    在本文中，我们假设系统中的进程都是单线程的，这样，在一个进程中发生的所有事件，是有一个该进程可知的全序的。注意，这里“事件”的粒度是根据应用环境而定的，可以细到一条汇编，也可以大到“把1P的数据传输完”或“计算出这个1T*1T的矩阵求逆”。本文仅仅定义两个事件：消息的发送事件、消息的接收事件，其它具体的事件应该根据应用程序来定义。如果要把这些概念扩展到支持多线程的进程，方法十分直接。

    时间的概念是基于更加基础的“顺序”概念的。例如，我们说某事发生在3:15，指的是这件事发生在时钟读数在3:15之后，并且在时钟读数在3:16之前。如前文所说，很多时候，我们关心的只是事件发生的顺序。例如，当设计数据库的事务时，必须保证在一个进程发起的事务commit之后，别的进程的数据库访问才能“看到”这个事务的修改，在commit之前，别的进程完全不可知这个事务，而至于这个事务是几点commit的，我们并不是十分关心。基于对这种情况的理解，Lamport在本文中定义的一个最为基本的概念是一个偏序“happened before”（使用符号“->”表示）：

    “->”是在一个系统的事件集合E（假设a，b，c属于E）上定义的，满足以下三个条件的最小的关系：

    1. 如果a和b发生在同一个进程中，且在该进程中，a在b之前发生，那么：a -> b；

    2. 如果a是进程Pi发出消息m，而b是进程Pj接收到这个消息m，那么：a -> b；

    3. 如果a -> b， b -> c，那么：a -> c；

    注意，对于任何一个事件a，a -> a都是不成立的，也就是说，关系->是反自反的。有了上面的定义，我们也可以定义出“并发”(concurrent)的概念了：

    对于事件a、b，如果a -> b，b -> a两个都不成立，那么a和b就是并发的。

    直观上，上面的->关系非常好理解，即“xxx在xxx之前发生”。也就是说，一个系统在输入I1下，如果有a->b，那么对于这个系统的同一个输入I1，无论重复运行多少次，a也始终发生在b之前；如果在输入I1下a和b是并发的，则表示在同一个输入I1下的不同运行中，a可能在b之前，也可能在b之后，也可能恰好同时发生。也就是，并发并不是指一定同时发生，而是表示一种不确定性。->和并发的概念，就是我们理解一个系统时最基础的概念之一了。

    有了上面的概念，我们可以给系统引入时钟了。这里的时钟就是lamport逻辑时钟。一个时钟，本质上是一个事件到实数（假设时间是连续的）的函数。这个函数将每个事件映射到一个数字，代表这个事件发生的时间。形式一点来说，对于每个进程Pi，都有一个时钟Ci，这个时钟将该进程中的事件a映射到Ci(a)。而整个系统的时钟C=，对于一个事件b，假设b属于进程Pj，那么C(b) = Cj(b)。

    这里插一句，从这个定义也可以看到大师对分布式系统的理解。分布式系统中不存在一个“全局”的实体。在该系统中，每个进程都是一个相对独立的实体，它们有自己的本地信息（本地Knowledge）。而整个系统的信息则是各个进程的信息的一个聚合。

    有了时钟的一个“本质定义”还不够，我们需要考虑，什么样的时钟是一个有意义的，或者说正确的时钟。其实，有了前文的->关系的定义，正确的时钟应满足的条件已经十分明显了：

    时钟条件：对于任意两个事件a，b，如果a -> b，那么C(a) < C(b)。

    注意，反过来讲这个条件可不成立。如果我们要求反过来也成立，即“如果a -> b为假，那么C(a) < C(b)也为假”，那就等于要求并发事件必须同时发生，这显然是不合理的。

    结合前文->关系的定义，我们可以把上面的条件细化成如下两条：

    1. 如果a和b是进程Pi中的两个事件，并且在Pi中，a在b之前发生，那么Ci(a) < Ci(b)；

    2. 如果a是Pi发送消息m，b是Pj接收消息m，那么Ci(a) < Cj(b)；

    上面就定义了合理的逻辑时钟。显然，一个系统可以有无数个合理的逻辑时钟。实现逻辑时钟也相对简

单，只要遵守两条实现规则就可以了：

    1. 每个进程Pi在自己的任何两个连续的事件之间增加Ci值；

    2. 如果事件a是Pi发送消息m，那么在m中应该带上时间戳Tm=Ci(a)；如果b是进程Pj接收到消息m，那么，进程Pj应该设置Cj为大于max(Tm, Cj(b))。

    有了上面逻辑时钟的定义，我们现在可以为一个系统中所有的事件排一个全序，就是使用事件发生时的逻辑时钟读数进行排序，读数小的在先。当然，此时可能会存在两个事件同时发生的情况。如果要去除这种情况，方法也非常简单：如果a在进程Pi中，b在进程Pj中，Ci(a) = Cj(b)且i < j，那么a在b之前。形式化一点，我们可以把系统事件E上的全序关系“=>”定义为：

    假设a是Pi中的事件，b是Pj中的事件，那么：a => b当且仅当以下两个条件之一成立：

    1. Ci(a) < Cj(b)；

    2. Ci(a) = Cj(b) 且 i < j；

    在本文中Lamport给出了一个系统中时间的基本概念。这些概念是理解一个系统中的同步、一致性等问题的基础。在本文中，作者也提到了，如何在系统中同步一组物理时钟，以及同步的精度。这个部分还没有仔细看，以后有机会再看吧。