Lamport Clock 和 Vector Clock

Lamport Clock

本节来自于论文：Time, Clocks, and the Ordering of Events in a Distributed System。算是在看论文过程中对论文理解的记录吧。

介绍

In this paper,we discussthe partial ordering defined by the "happened before" relation, and give a distributed algorithm for extending it to a consistent total ordering of all the events. This algorithm can providea useful mechanism for implementing a distributed system.We illustrate its use with a simple method for solving synchronization problems. Unexpected, anomalous behavior can occur if the ordering obtained by this algorithm differs from that perceived by the user. This can be avoided by introducing real, physical clocks. We describe a simple method for synchronizing these clocks, and derive an upperbound on how far out of synchrony they can drift.

论文的内容组成如下：

讨论通过 “happened before” 定义出来 partial ordering；
给一个算法，从 partial ordering 扩展到能推到出系统内所有 event 的 total ordering；
通过解决一个同步问题作为示例，讲解如何使用这个算法；
这个算法可能有些异常行为，需要通过 physical clock 来解决；

The Partial Ordering

系统内有很多 Process，它们运行时会产生很多相互交织的 Event，它们之间的通信也是通过发消息也即 Event 来完成。Partial Ordering 就是从一个局部看，两个相关事件之间的先后顺序。Total Ordering 是一段时间内系统内所有 Event 之间的发生顺序。从论文介绍中就看到，本文的目标就是给出一个算法，满足一些要求之后，就能仅凭借 Partial Ordering 逐步推导出整个系统内所有 Event 的 Order。通过系统中一个个已经发生的事件，推导出系统整个运行状态是否正确。

Partial Ordering 是两个相关事件的 Order，通过 "happened before" 原则来定义，严格描述如下：

The relation -> on the set of events of a system is the smallest relation satisfying the following three conditions: (1) If a and b are events in the same process, and a comes before b, then a -> b. (2) If a is the sending of a message by one process and b is the receipt of the same message by another process,then a -> b. (3) If a -> b and b -> c then a -> c. Two distinct events a and b are said to be concurrent if a !-> b and b !-> a.

a !-> b 在论文中的描述符号是：

因为普通的 text 很难打出来这个字符，所以用 !-> 代替。

简单讲就是同一个进程内，a b 事件有严格的顺序，a 发生在 b 之前，那就有 Paritial Ordering： a -> b。如果是跨进程通讯事件，a 是一个进程发消息到另一个进程的事件，b 是收到消息的事件，那 a 一定在 b 之前发生，所以也有 Partial Ordering: a -> b。最后是 Partial Ordering 有传递性，如果有 a -> b, b -> c 则 a -> c。

Logical Clocks

这一节就开始介绍算法了。论文内称为 Logical Clock 但一般业内称为 Lamport Clock 因为这个 Clock 是论文作者 Lamport 提出来的。

分布式系统下物理时间并不可靠，比如不同的 Process 运行在相互隔离的机器上，他们对当前时间的认识是有偏差的，不可能有一个所有进程都能获取到的绝对的时间存在，即使是原子钟也有自己的偏差，NTP 对时更不可能做到所有进程一致且精准。而我们为了推导出 Total Ordering 又需要时间概念从而区分出 Event 之间的先后顺序，所以论文引入了一个新算法 Logical Clock (也即 Lamport Clock，后续还是写论文中的名字 Logical Clock)。它与物理时间无关，只跟强有力的 Partial Ordering 相关。这个新 Clock 它需要保证的是，比如用 C(a), C(b) 表示 a 或 b 事件发生时在 Logical Clock 的时间，如果有 a -> b (Partial Ordering) 那说明 b 的事件发生时间一定在 a 之后，则 C(a) < C(b)。这个就是对 Logical Clock 的要求。论文里描述为：

Clock Condition. For any events a, b: if a -> b then C(a) < C(b).

有了这么个 Clock，后续就能用它去推断整个系统内 Events 的 Total Ordering。因为这个 Clock 建立在可靠的 Partial Ordering 之上，而不是每个 Process 有不同认识的物理时间之上，所以它是可靠的。下面论文就是去介绍算法如何去实现这么个 Clock。

首先，系统内会有多个进程，每个进程会有自己的 Logical Clock，例如 i 进程 a 事件发生时 Logical Clock 得到的读数是 Ci(a)，j 进程 b 事件发生时得到的读数是 Cj(b)。为了满足上述 Logical Clock 要求，配合之前的 Partial Ordering 定义，有：

C1. If a and b are events in process Pi, and a comes before b, then Ci(a) < Ci(b). C2. If a is the sending of a message by process Pi and b is the receipt of that message by process Pj, then Ci(a) < Cj(b).

明确要求之后进入具体实现部分。为了实现这个 Logical Clock，要求每个进程有一个存放时间的寄存器，例如 i 进程的时间寄存器就是 Ci，其在 a 事件发生时的读数记做 Ci(a)。每次有事件发生时 Ci 会变化，改变 Ci 本身不算一个事件。这里 Ci 寄存器就是 i 进程的 Logical Clock，需要有一套改变 Ci 寄存器值的算法让 Ci 满足上述 C1 和 C2 条件，这样 Ci 寄存器就实现了 Logical Clock。改变 Ci 值的算法就是：

IR1. Each process Pi increments Ci between any two successive events. IR2. (a) If event a is the sending of a message m by process Pi, then the message m contains a timestamp Tm = Ci(a). (b) Upon receiving a message m, process Pj sets Cj greater than or equal to its present value and greater than Tm.

可以想象一下，这么实现下是满足 C1 和 C2 的，于是进而能满足 Clock Condition。这套算法实现的就是 Logical Clock。

有个很出名的图，截取自 File:Lamport-Clock-en.svg - Wikimedia Commons 很多地方都引用，但我找不到这个图最初的出处了。从这个图上能看出来 Logical Clock 工作原理。图上是 A B C 三个进程之间的交互，框内是它们各自维护的 C 寄存器的值。图上蓝色，红色，以及 cause, effect 字样因为找不到图的出处，所以不知道是什么意思。

应用 Logical Clock

接下来要使用 Logical Clock 去推断系统内所有 event 的 ordering，实现 total ordering，记做 => 例如 b 的 total ordering 在 a 之后，就记做 a => b。

因为每个进程的 C 寄存器独立修改，一定会出现两个进程的 C 寄存器相等的情况。为了实现 total ordering，我们需要在这种情况下规定出 event 的先后顺序，例如固定死认为当 Ci(a) = Cj(b) 时，a b 两个事件的 Total ordering 是 a => b。可以想到这里一个隐含条件是 a b 两个事件是无关的，如果有关系满足了 Partial Ordering 则不可能有 Ci(a) = Cj(b) 的情况。

啥时候会用到这个强制顺序呢。比如上面的图，如果去掉 A 进程 A1 之后的事件，B 进程去掉 B3 之后的事件，那 A1 和 B3 之间因为没有 Partial Ordering，所以要决定它俩顺序就只能通过这种强制进程序列方式决定 A1 和 B3 的顺序。回顾一下 Total Ordering 是说它能决定出系统内所有事件的先后顺序。

解决了进程间 C 的冲突后，Logical Clock 就从 Partial Ordering 推广到了 Total Ordering。接下来是用 Logical Clock 解决一个进程间协作的问题。问题要求如下：

(I) A process which has been granted the resource must release it before it can be granted to another process.
(II) Different requests for the resource must be granted in the order in which they are made.
(III) If every process which is granted the resource eventually releases it, then every request is eventually granted.

难点是第二个，怎么去保证资源必须按照请求顺序分配。假设有个中间进程 p0 专门负责分配资源，别的进程都发请求给它，先收到哪个进程的资源请求就分配资源给谁。但可能出现 p1 向 p0 请求资源后，又给 p2 发送了一条消息，p2 收到消息后也去 p0 请求资源，但是 p2 的请求先于 p1 到达 p0 进程，于是 p0 将资源分配给了 p2 而不是顺序上先发起请求的 p1。简单说就是仅凭请求到来顺序 p0 无法判断出两个请求的先后顺序，因为请求到达 p0 的次序并不一定是请求发出次序。

注意条件二用的词是 order 即资源要求是按请求资源的次序 (Order) 来分配，这里就隐藏要求了按 Partial Order 分配资源，而不是时间上的次序。上面给的简单解法的反例设计的比较贼，p1 请求完资源后是给 p2 发了一个消息后 p2 才也去请求资源的。如果 p2 请求资源操作和 p1 无关，只是恰好在 p1 后发出，则 p0 将资源分配给 p2 是满足上述三个要求的，因为 p2 虽然在 p1 后发出请求，但它俩是并发请求，没有 Order。

使用 Logical Clock 解决问题的算法规则如下:

Pi 要抢资源，就发送消息 TmPi 到所有其它进程，并保留此消息在自己的 Request queue 内。Tm 是这条消息的 Logical Clock 时间标记；
Pj 收到 Pi 消息后将 TmPi 消息放入自己的 Request queue，并回复 ack，ack 中也带着 Pj 的 Logical Clock；
假设 Pi 拿到了资源想要释放时，它先从 Request queue 内清理 TmPi 消息，再带着自己的 Logical Clock 发资源释放消息给所有进程；
Pj 收到 Pi 的资源释放消息后，将 TmPi 从 Request queue 内移除；
每个进程，例如 Pi，自己独立判断自己有没有获取到资源。判断方法是：
- 5.1 Pi 在 Request queue 内获取资源的 TmPi 消息在所有其它消息之前，即 TmPi => 其它所有消息；
- 5.2 Pi has received a message from every other process timestamped later than Tm

在讨论算法正确性之前有几个需要注意的：

在这个算法下每个进程独立判断能不能获取到资源；
为了专注介绍 Logical Clock 上述算法假设 Pi 给 Pj 发的消息是严格有序的，先发的消息一定先到；
假设所有 Pi 发的消息都最终能送达 Pj；
5.2 要关注一下。它要求的不是说 Pi 必须收到 Pi 向 Pj 请求 Resource 的响应，而是说只要收到 Pj 发来的任意一条消息，且这条消息的时间戳在 Tm 之后即可。比如 Pi 收到的 Pj 的消息时间戳是 Tm+1 ，那 Pi 就知道 Pj 进程之后的消息时间一定大于 Tm+1，而 Pi 请求资源的时间是 Tm，一定早于 Pj 之后任意一条消息，所以资源一定是 Pi 的。

算法正确性判断上最关键的就是算法的第 5 条，它保证了 Pi 在获取资源的时候一定已经跟其它进程都沟通过了，并且确认其它进程的消息时间都大于 Tm。从 Pi 的角度就是说它一定是最早请求资源的进程，所以能获取资源。对任意一个其它进程 Pj 来说，它可能收到了 Pi 的请求也可能没收到。如果收到了 Pi 的请求，因为 Pi 获取资源时，Pj 已经给 Pi 发过时间大于 Tm 的消息，所以 Pj 的时间是大于 Tm 时间的，所以资源无法被 Pj 获取。如果 Pj 没收到 Pi 发来的获取资源消息，且它认为自己的时间小于 Tm (比如 Pj 是个自己没产生任何事件，且未跟其它进程沟通过的进程，时间是 0)，此时 Pj 要获取资源需要先去跟 Pi 沟通，请求到达 Pi 后时间一定在 Tm 之后，Pj 收到的 Pi 的响应时间就至少是 Tm + 1，所以 Pj 不可能获取资源。

Physical Clock

上述算法讨论的所有事件都是在某一个系统内两个事件的关系。例如 a -> b 只能是在某个系统内下 a 事件发生在 b 之前但并不表示绝对意义上的 a 事件发生在 b 之前。比如系统内 A B C 三个设备组成的系统，A 设备给 C 发起请求，是事件 a。发完请求后 A 设备操作员通过另一个通道比如电话告诉 B 设备操作员去发起请求 b 给 C。结果 b 请求先于 a 到达 C。那在 A B C 设备组成的系统内，通过 Logical Clock 有 b 发生于 a 之前，但从绝对意义上来说本来 a 应该发生于 b 之前的。原因是 A B C 组成的系统没有包含电话这个途径。

所以可以跟进一步规范 Logical Clock 的定义，

Strong Clock Condition. For any events a, b in φ, if a -> b then C(a} < C(b).

这里 φ 是所有事件组成的全集，按上述场景则包含打电话的事件。a -> b 论文里是记做一个粗的箭头。

解决这个问题又需要 Logical Clock 变成一个通用的，所有系统都能同步的，误差在一定范围内的 Clock，这种 Clock 就是 Physical Clock。本文后续就是介绍怎么通过一个能定时同步且误差在一定范围内的 Physical Clock 去保证 Strong Clock Condition。但因为这块推论跟后续想继续了解的 Vector Clock 关系不大，且论文影响最深的是 Logical Clock，所以后续计算对这个 Physical Clock 的要求部分就不继续记录了。

Vector Clock

跟 Lamport Clock 很像的是 Vector Clock，Wiki 说明在：Vector clock - Wikipedia。

这个不贴论文了，直接贴 Wiki 上的图：

也是每个进程或者 Actor 有个 ID，并且自己维护一个 Logical Clock。进程之间通过消息来通信。Vector Clock 算法如下：

初始时每个 Clock 值都是 0；
每次有 internal event 时，进程只对自己的 Clock 做自增；
每次发消息时，进程先对自己的 Clock 做自增，再把整个 Vector 都拷贝一份发送到消息里；
收到消息后，首先将进程自己的 Clock 自增，再将消息内每个进程的 Clock 以取最大值的方式更新到当前线程为所有其它进程维护的 Vector Clock 内。

第四条好像比较模糊。拿上图来看吧，最后一条消息是 C 进程发给 A 的，消息内 Vector 是 A:2, B:5, C:5，A 收到消息前 Vector 是 A:3, B:3, C:3，收到消息后更新为 A:4, B:5, C:5。

Lamport Clock 是有什么问题非要进化为 Vector Clock 呢？

Lamport Clock 从前一节的介绍能看到它主要是用来推论出系统内所有 Event 的先后顺序做到 Total Ordering，从而能推断系统运行状态是否正确，实现类似于进程间同步这种操作。而 Lamport Clock 没做到的是判断两个 Event 的依赖关系，是并发的完全没关系的 Event，还是说有依赖关系 (Causally Dependent)。

以下图来举例，i 和 j 是两个进程，i 对某个数据做了修改，想要同步自己的修改到 j 进程去，同时 j 也会对同一个数据做修改，修改完后也会同步给 i。于是会有两种时序：

j 收到了 i 的修改后，在 i 修改之上在做修改，再同步给 i；
j 还没收到 i 的修改就对数据做了修改，直接同步给 i，同步完成后才收到 i 之前的修改；

如果用 Lamport Clock 两种时序就分别对应下面两个图。方括号内是 Lamport Clock 的值。

于是对比上面两种时序可以清晰的看到，无论是时序 1 的 d 事件时序 2 的 f 事件，Clock 值都是 4，能通过 Clock 值判断出俩事件与 a 事件的先后顺序。但是收到 j 同步来的数据时，两种时序下 Clock 值都是 3，于是 i 进程是无法区分出两种时序差别的，即 j 同步来的数据 i 不知道是在自己修改基础上做的修改还是 j 自己独立的修改。这就是 Lamport Clock 的缺陷，或者说它本身并不致力于解决这个问题。

而如果是 Vector Clock，同样场景就能避免问题。使用 Vector Clock 在两种时序下的图如下：

看到 Vector Clock 上时序 1 的 c 事件和时序 2 的 d 事件是不同的，i 进程收到时序 1 的 c 事件时因为事件内有 i:1，所以 i 能知道 j 的修改是有看到 i:1 这个版本的修改的。而 i 进程收到时序 2 的 d 事件时，消息内没有 i:1 这个 Clock，说明 d 事件发出时，j 还未看到 i 的修改。

Vector Clock 的难点

Riak 有个文章介绍了实现 Vector Clock 的一个难点：Why Vector Clocks Are Hard – Riak。

简单说就是为了让 Vector Clock 能自动判断出请求的依赖关系从而自动解决冲突，Vector Clock 内的 ID 数量需要和可能被并发修改的 field 的并发度相同或相匹配。比如 A B C D 四个进程要修改某个 Field，Vector Clock 内 Actor ID 就可能是 4 个。如果会修改某个 Field 的 Actor 特别多，比如跟 Client 数量相同，这就导致 Vector Clock 可能变得很大，越大的 Vector Clock 越会占用更多资源，存储空间，每次传输数据的提及，合并冲突的速度等。所以需要有办法能控制 Vector Clock 内 ID 数量。

一个办法是给 Client 分组，比如强制任务 A B 一组，共用 Actor ID 是 X，C D 一组共用 Actor ID 是 Y。这个也有实际意义，比如 A B C D 是四个用户，X Y 是两个服务器，通过一些手段保证 A B 请求一定只发到 X 服务器，C D 只发到 Y 服务器，在 Vector Clock 中用服务器 ID 替代 Client ID。从而控制 Vector Clock 内 ID 数量，因为服务器数量有限且增长慢。

但它的问题在于 X 服务器需要负责 A B 两个 Client 的修改冲突。比如 A 做了改动，vclock 为 x: 1，发去 C 和 D，C 做了改动 vclock 为 x:1, y:1发去 B，B 收到以后做了改动再转发出去，vclock 是 x:2, y:1，D 根据 A 的改动做了改动 x:1, y:1 也发去 B，就相当于 B 收到两个相同的不是同一个 actor 发来的 vclock。B 就无法解决冲突了。

对这个问题 Riak 给的办法是定期的清理 vclock。在 Vector Clock 内除了记录 Actor ID 和 Logical Clock 外，再记录一个绝对的时间戳。绝对的时间戳不当做数据版本做任何比对，只在 vclock 太大时候做清理时候用。需要清理时候从 vclock 中找时间戳最早的记录清理掉，直到 vclock 满足大小要求位置。

比如 A 这个 Actor 每次修改数据除了记录 vclock 为 A: 1@1592895372，第二次 A 更新时候提升版本号并更新时间戳为 A:2@1592895373。清理的时候比如 vclock 是 A:2@1592895373, B:10@1592895370，就把 B 这个 Actor 的记录清理掉。

这种清理方式正常情况下都没问题，只有在一个 Client 很久很久没对某个字段做修改，这个字段并发度又非常高，很多 Client 去修改它，之后这个静默很久的 Client 又根据本地存的 vclock 做了修改再提交去服务器，此时服务器因为不记得它以前的版本是多少，可能无法做数据自动冲突解决，只能交付上层依赖其它机制去解决冲突。