3.2　逻辑时钟

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

然后，参考文献[178]基于偏序又引入物理时间戳，给分布式系统中所有事件排定了全序。

3.2.1　因果（happened-before）模型

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

• 事件a和事件b在同一个进程中发生：如果事件a在事件b之前发生，则事件a先于事件b，这时可表示为if a -> b then Ci(a) < Ci(b)，其中i表示同一个进程；C[1]表示与事件的函数关系，通常用时间（时间表达的顺序关系）映射此函数关系。
• 事件a和事件b在不同进程中发生：如果事件a为数据在进程P1上被发出，而事件b为数据在进程P2上被接收，则事件a先于事件b，这时可表示为if a -> b then Ci(a) < Cj(b)，i、j表示不同进程。
• 事件之间的传递关系：如果由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 Clocks算法，该算法最先抛弃将物理时钟作为时间戳，提出将逻辑时钟作为时间戳。

3.2.2　逻辑时钟的实现

参考文献[178]给出的Lamport Logical Clocks算法的内容如下。

每个进程Pi维护一个本地计数器Ci，Ci相当于逻辑时钟，并按照以下的规则更新Ci：

• 单进程时钟处理规则：每次执行一个事件（如通过网络发送消息，或者将消息交给应用层，还可包括其他的一些内部事件）之前，将Ci加1。
• 多进程间时钟处理规则：
• • 当Pi发送消息m给Pj的时候，在消息m上附着上Ci。
  • 当接收进程Pj接收到Pi发送的消息时，更新自己的Cj=max{Cj, Ci}+1。

3.2.3　逻辑时钟的缺点

1.1.1节给出了一个典型的日志问题，这个问题可以延伸为如下问题。

那海蓝蓝、那天蓝蓝两人分别要在某电子商务网站上买书。假设该电子商务网站的后台架构为：

1）前端代理服务器，负责接收用户购书请求。因为网站的用户很多，所以有很多前端代理服务器。

2）购书服务器负责存储、管理相关图书的数据。

假设该电子商务网站的后台情况为：

1）那海蓝蓝的购书请求发给前端代理服务器A，之后那天蓝蓝的购书请求发给前端代理服务器B。两个人要购买同一本图书，但被购买的图书只剩一本。

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

3）因为那天蓝蓝的购书时间5早于那海蓝蓝的购书时间10，所以购书服务器支持了那天蓝蓝的购书请求。

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

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

从系统之外看，基于逻辑时钟定义出的全序关系（下节讨论全序关系）与实际物理时间上发生的顺序，在分布式系统下会存在不一致的情况。例如：事务T1与事务T2在逻辑时钟这个轴上，事务T1因先提交并获得一个逻辑时间戳值，故逻辑上先发生，事务T2后提交故逻辑上后发生。但是，在物理时间上，事务T2的提交可能先发生，事务T1的提交后发生；这样逻辑时钟和物理时钟不能对应，从系统之外看就会发现存在不一致的问题。如何解决这个问题呢？3.3节将讨论的Vector Clocks（向量时钟）算法、3.4节将讨论的HLC（Hybird Logic Clocks，混合逻辑时钟）算法，就是用于解决这个问题的，同时也是对Lamport Logical Clocks算法进行的改进。

3.2.4　物理时钟与同步问题

参考文献[178]还定义了物理时钟和全序关系，即通过引入物理时钟来排定事件之间的全序关系（只是这个全序关系定义的有些简单随意[2]了），然后通过全序解决同步问题[3]（换言之，偏序关系在分布式系统中是无法充分表达事件之间的正确顺序的）。

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

换言之，参考文献[178]的核心在于：通过定义happened-before模型确定偏序关系，从而为定义全序关系做好铺垫。然后通过引入物理时间戳定义全序关系，目的是解决分布式系统下事件间的全序问题，避免分布式系统出现逻辑错误。

---

[1]参考文献[178]中的原文为：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]笔者认为，该算法定义的总排序是比较随意的。

[3]参考文献[178]给出的原文为：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.（我们描述了一种将偏序扩展到任意的全序的算法，并展示了如何用这个全序来解决一个简单的同步问题。）