文献[1]在不使用物理时间的情况下，提出了一个happened-before模型，并采用逻辑时钟定义事件之间相关顺序的算法，解决了分布式系统中事件之间的排序问题，但是这个序是一个偏序关系（偏序关系可反映部分事件之间的因果关系），而不是一个全序关系。Lamport Logical Clocks（逻辑时钟，简写LC）算法定义的偏序关系能够正确地排序出具有因果关系的事件的次序（但是不能保证并发事件的真实顺序），这使得分布式系统在逻辑上不会发生因果倒置的错误。

然后，文献[1]基于偏序又引入物理时间戳，改进Logical Clock解决的问题，文献[1]找到一种方法，给分布式系统中所有事件排定全序。

因果（happened-before）模型

happened-before模型，定义两个事件如果符合下面的三个关系中的一个，则事件之间的时间就存在happened-before关系，即表明事件之间存在happened-before关系，也即表明事件之间的因果关系确定则其发生的时间关系是确定的：

1. 事件a和事件b在同一个进程发生：如果事件a在事件b之前发生，则事件a先于事件b，表示为：if  a -> b  then Ci(a) < Ci(b)，i表示同一个进程。其中C[1]表示与事件的函数关系，通常用时间（时间表达的顺序关系）映射此函数关系。

2. 事件a和事件b在不同进程发生：如果事件a在进程P1上被发出，然后在进程P2上被接收，作为事件b．则事件a先于事件b，表示为：if  a -> b then  Ci(a) < Cj(b) ，i、j表示不同进程。

3. 事件之间的传递关系：如果Ci(a) < Cj(b)、Cj(b) < Ck(c)，则Ci(a) < Ck(c)，这说明事件发生的顺序满足传递性。

其他任何不满足上述关系的事件，都被称为“并发事件”。

但是，如果Ci(a) < Cj(b)，并不能得到a -> b（前者是后者的必要不充分条件）。即如果时间戳大小不同，尚不能确定事件a和b两者间是否具有可能的因果关系。即“识别因果关系存在困难”。而happened-before模型表达的是“根据事件发生的真实情况生成因果关系是可行的”。请注意：这里强调的是“生成（产生）”和“识别（读取）”之间的差异。

Lamport根据该偏序关系提出了“Lamport Logical Clock”算法，最先抛弃将物理时钟作为时间戳，提出逻辑时钟作为时间戳。

逻辑时钟的实现

文献[1]同时给出了“Lamport Logical Clock”算法，该算法内容如下：

每个进程Pi维护一个本地计数器Ci，相当于logical clocks，按照以下的规则更新Ci：1. 单进程时钟处理规则：每次执行一个事件(如通过网络发送消息，或者将消息交给应用层，或者其它的一些内部事件)之前，将Ci加12. 多进程间时钟处理规则：  1）当Pi发送消息m给Pj的时候，在消息m上附着上Ci  2）当接收进程Pj接收到Pi的发送的消息时，更新自己的Cj = max{Cj,Ci}+1

逻辑时钟的缺点

《分布式原理（3）--依赖物理时间引发的问题》给出了一个典型的日志问题，这个问题可以延伸为如下问题：

例如，一个典型的分布式应用如下：

1. 那海蓝蓝、那天蓝蓝两人分别要在某电子商务网站上买书。

2. 假设某电子商务网站的后台架构为：

a) 前端代理服务器，负责接收用户购书请求。用户多，前端代理服务器有多个。

b) 购书服务器，负责存储、管理相关图书的数据等。

3. 假设某电子商务网站的后台情况为：

a) 那海蓝蓝的购书请求发给前端代理服务器A；然后，那天蓝蓝的购书请求发给前端代理服务器B。被购买的图书只有一本。

b) 前端代理服务器A的物理时间是10，前端代理服务器B的物理时间是5。

c) 此时，那天蓝蓝的购书时间5早于那海蓝蓝的购书时间10，则购书服务器支持了那天蓝蓝的购书请求。

d) 但实际情况是那海蓝蓝购书请求先发出却没有买到书，这似乎不公正。

Lamport Logical Clocks算法有其缺陷，如3.2.1节，其问题是：事件a和事件b实际发生的先后顺序不能仅仅通过比较Ci(a)和Cj(b)来决定。该算法不能很好的处理向外部传递的信息（如怎么从系统之外即用户的角度、从分布式系统外部的角度看到的数据满足线性一致性，所以Spanner系统使用分布的原子钟、GPS、一些事务处理规则，共同构成物理时间即Truetime机制对事务的提交进行全序排序）。

从系统之外看，基于逻辑时钟定义出的全序关系（下节讨论全序关系）与实际物理时间上的发生先后顺序在分布式系统下，会存在不一致的情况。例如：事务T1与事务T2，在逻辑时钟这个轴上，事务T1因先提交而获得一个逻辑时间戳值故逻辑上先发生，事务T2后提交故逻辑上后发生。但是，在物理时间上，事务T2提交先发生，事务T1后发生；这样逻辑时钟和物理时钟不能够对应，从系统之外看就会发现存在不一致的问题。

如何解决这个问题呢？3.3节将讨论Vector Clocks（向量时钟）算法、3.4节将讨论的HLC（Hybird Logic Clock，混合逻辑时钟）算法，对Lamport Logical Clocks算法进行了改进。

逻辑时钟论文的核心内容

文献[1]还定义了物理时钟和全序关系，通过引入物理时钟来排定事件之间的全序关系（只是这个全序关系定义的有点儿简单[2]随意了）。而使用全序解决了“同步问题[3]”（换言之，偏序关系在分布式系统中是不够表达事件之间的正确顺序的）。

所谓的同步问题，是分布式系统下必须要确认任何事件之间的发生顺序，即全序关系。事件的全序关系是分布式系统中必须明确的，明确后才不至于出现“逻辑错误”。

换言之，文献[1]的核心在于：通过定义happened-before模型确定偏序关系，为定义全序关系做一个基础铺垫。然后通过引入物理时间戳定义全序关系，目的是为了解决分布式系统下事件间的全序问题，避免分布式系统出现逻辑错误。这是文献[1]的价值所在（其价值并不是只提出一个“Logical Clocks”）。

脚注文献：

[1] 文献[1]：we define a clock Ci for each process Pi to be a function which assigns a number Ci(a) to any event a in that process. The entire system of clocks is represented by the function C which assigns to any event b the number C(b), where C(b) = Cj(b) if b is an event in process Pj.

[2] 作者认为：The total ordering defined by the algorithm is somewhat arbitrary.

[3] 文献[1]：We described an algorithm for extending that partial ordering to a somewhat arbitrary total ordering, and showed how this total ordering can be used to solve a simple synchronization problem.

引文文献：

[1] Leslie Lamport: Time, Clocks, and the Ordering of Events in a Distributed System. Commun. ACM 21(7): 558-565 (1978)

扫码加关注，知数行云，专业有深度

声明：本文禁止用于开发“任何软件程序,包括但不限于训练机器学习或人工智能(AI)系统”。