逻辑时钟
逻辑时钟
什么是逻辑时钟
1978 年，Lamport 在 Time, Clocks, and the Ordering of Events in a Distributed System 中提出了逻辑时钟的概念，来解决分布式系统中区分事件发生的时序问题。
逻辑时钟指的是分布式系统中用于区分事件的发生顺序的时间机制。
为什么需要逻辑时钟
对于程序来说，时间维度非常重要，很多业务逻辑都依赖于时间。常见的场景有：
- 某个请求是否超时了？
- 某项服务 P99 的响应时间是多少？
- 在过去五分钟，服务平均每秒处理多少个查询？
- 用户在我们的网站上浏览花了多段时间？
- 这篇文章什么时候发表？
- 在什么时间发送提醒邮件？
- 这个缓存条目何时过期？
- 日志文件中错误消息的时间戳是多少？
为了让多节点的系统时间保持同步，需要有一个对表机制，来保证各节点的时间一致。一种常见方法是使用 NTP，它的工作机制是使用专门的高精度时间服务器来作为基准，调整服务器的本地时间。即使使用了 NTP，也难免存在微小的误差，在有些场景中（如金融）是不能接受的。
在分布式系统中，由于跨节点通信不可能即时完成，因此在多节点上难以确定事件的先后顺序。而逻辑时钟就是一种定义时序先后顺序的方案。
全序和偏序
全序和偏序是集合论中的概念，用于描述集合中元素之间的关系。
什么是偏序
偏序是指集合中的元素之间存在一种关系，使得任意两个元素之间可能存在比较，但不一定所有元素都可以相互比较。这种关系不一定是传递的或者反对称的。例如，集合中的子集关系就是一个偏序关系，因为不是所有的子集都可以相互比较。
设 R 是集合 A 上的一个二元关系，若 R 满足：
（1）自反性：对任意 x∈A，有 xRx；
（2）反对称性（即反对称关系）：对任意 x,y∈A，若 xRy，且 yRx，则 x=y；
（3）传递性：对任意 x,y,z∈A，若 xRy，且 yRz，则 xRz。
则称 R 为 A 上的偏序关系。
什么是全序
全序是指集合中的元素之间存在一种关系，使得任意两个元素都可以进行比较，且这种比较关系是传递的，反对称的。换句话说，任意两个元素都可以比较大小，并且不会出现无法比较的情况。例如，实数集合上的小于等于关系就是一个全序关系。
设集合 X 上有一全序关系，如果我们把这种关系用 ≤ 表述，则下列陈述对于 X 中的所有 a, b 和 c 成立：
如果 a ≤ b 且 b ≤ a 则 a = b（反对称性）
如果 a ≤ b 且 b ≤ c 则 a ≤ c（传递性）
a ≤ b 或 b ≤ a (完全性)
注意：
时序的关键
**两个事件可以建立因果（时序）关系的前提是：两个事件之间是否发生过信息传递。**在分布式系统中，进程间通信的手段（共享内存、消息发送等）都属于信息传递，如果两个进程间没有任何交互，实际上他们之间内部事件的时序也无关紧要。但是有交互的情况下，特别是多个节点的要保持同一副本的情况下，事件的时序非常重要。
逻辑时钟
分布式系统中按是否存在节点交互可分为三类事件，一类发生于节点内部，二是发送事件，三是接收事件。Lamport 时间戳原理如下：
- 每个事件对应一个 Lamport 时间戳，初始值为 0
- 如果事件在节点内发生，时间戳加 1
- 如果事件属于发送事件，时间戳加 1 并在消息中带上该时间戳
- 如果事件属于接收事件，时间戳 = Max(本地时间戳，消息中的时间戳) + 1
假设有事件 a、b，C(a)、C(b)分别表示事件 a、b 对应的 Lamport 时间戳，如果 a->b,则 C(a) < C(b)，a 发生在 b 之前(happened before)，例如图 1 中有 C1 -> B1。通过该定义，事件集中 Lamport 时间戳不等的事件可进行比较，我们获得事件的偏序关系(partial order)。
如果 C(a) = C(b)，那 a、b 事件的顺序又是怎样的？假设 a、b 分别在节点 P、Q 上发生，Pi、Qj 分别表示我们给 P、Q 的编号，如果 C(a) = C(b) 并且 Pi < Qj，同样定义为 a 发生在 b 之前，记作 a => b。假如我们对图 1 的 A、B、C 分别编号 Ai = 1、Bj = 2、Ck = 3，因 C(B4) = C(C3) 并且 Bj < Ck，则 B4 => C3。
通过以上定义，我们可以对所有事件排序、获得事件的全序关系(total order)。上图例子，我们可以从 C1 到 A4 进行排序。
向量时钟
Lamport 时间戳帮助我们得到事件顺序关系，但还有一种顺序关系不能用 Lamport 时间戳很好地表示出来，那就是同时发生关系(concurrent)(4)。例如图 1 中事件 B4 和事件 C3 没有因果关系，属于同时发生事件，但 Lamport 时间戳定义两者有先后顺序。
Vector clock 是在 Lamport 时间戳基础上演进的另一种逻辑时钟方法，它通过 vector 结构不但记录本节点的 Lamport 时间戳，同时也记录了其他节点的 Lamport 时间戳(5)(6)。Vector clock 的原理与 Lamport 时间戳类似，使用图例如下：
假设有事件 a、b 分别在节点 P、Q 上发生，Vector clock 分别为 Ta、Tb，如果 Tb[Q] > Ta[Q] 并且 Tb[P] >= Ta[P]，则 a 发生于 b 之前，记作 a -> b。到目前为止还和 Lamport 时间戳差别不大，那 Vector clock 怎么判别同时发生关系呢？
如果 Tb[Q] > Ta[Q] 并且 Tb[P] < Ta[P]，则认为 a、b 同时发生，记作 a <-> b。例如图 2 中节点 B 上的第 4 个事件 (A:2，B:4，C:1) 与节点 C 上的第 2 个事件 (B:3，C:2) 没有因果关系、属于同时发生事件。
版本向量时钟
基于 Vector clock 我们可以获得任意两个事件的顺序关系，结果或为先后顺序或为同时发生，识别事件顺序在工程实践中有很重要的引申应用，最常见的应用是发现数据冲突(detect conflict)。
分布式系统中数据一般存在多个副本(replication)，多个副本可能被同时更新，这会引起副本间数据不一致，Version vector 的实现与 Vector clock 非常类似，目的用于发现数据冲突。下面通过一个例子说明 Version vector 的用法：
- client 端写入数据，该请求被 Sx 处理并创建相应的 vector ([Sx, 1])，记为数据 D1
- 第 2 次请求也被 Sx 处理，数据修改为 D2，vector 修改为([Sx, 2])
- 第 3、第 4 次请求分别被 Sy、Sz 处理，client 端先读取到 D2，然后 D3、D4 被写入 Sy、Sz
- 第 5 次更新时 client 端读取到 D2、D3 和 D4 3 个数据版本，通过类似 Vector clock 判断同时发生关系的方法可判断 D3、D4 存在数据冲突，最终通过一定方法解决数据冲突并写入 D5
Vector clock 只用于发现数据冲突，不能解决数据冲突。如何解决数据冲突因场景而异，具体方法有以最后更新为准(last write win)，或将冲突的数据交给 client 由 client 端决定如何处理，或通过 quorum 决议事先避免数据冲突的情况发生(11)。
由于记录了所有数据在所有节点上的逻辑时钟信息，Vector clock 和 Version vector 在实际应用中可能面临的一个问题是 vector 过大，用于数据管理的元数据(meta data)甚至大于数据本(12)。
解决该问题的方法是使用 server id 取代 client id 创建 vector (因为 server 的数量相对 client 稳定)，或设定最大的 size、如果超过该 size 值则淘汰最旧的 vector 信息(10)(13)。
参考资料
- Time, Clocks, and the Ordering of Events in a Distributed System，译文，解读 - Lamport 介绍 happened before、偏序关系（partial ordering）、逻辑时钟（Logical Clocks）概念，提出解决分布式系统中区分事件发生的时序问题的方法。
- Virtual Time and Global States of Distributed Systems，解读 - 逻辑时钟无法描述事件的因果关系。本文提出了向量时钟，这种算法利用了向量这种数据结构将全局各个进程的逻辑时间戳广播给各个进程，通过向量时间戳就能够比较任意两个事件的因果关系。
- 分布式系统理论基础 - 时间、时钟和事件顺序