分布式系统时钟
时钟
物理时钟
- 物理时钟：物理节点的系统时钟；
- 逻辑时钟：逻辑上表示事件顺序的方法；
Lamport 时钟
Leslie Lamport 在1978年提出逻辑时钟的概念，并描述了一种逻辑时钟的表示方法，这个方法被称为Lamport时间戳(Lamport timestamps)[3]。
Happened-Before（->） 规则
- 如果a、b是同一个进程中的事件，且a 先于 b 发生，则 a -> b;
- a、b不同进程，a发送，b接收，则 a->b;
- 如果 a->b 且b -> c, 则 a -> c;
Lamport 时钟规则
- 每个事件对应一个Lamport时间戳，初始值为0
- 如果事件在节点内发生，时间戳加1
- 如果事件属于发送事件，时间戳加1并在消息中带上该时间戳
- 如果事件属于接收事件，时间戳 = Max(本地时间戳，消息中的时间戳) + 1
顺序
- 偏序：假设有事件a、b，C(a)、C(b)分别表示事件a、b对应的Lamport时间戳，如果C(a) < C(b)，则有a发生在b之前(happened before)，记作 a -> b，例如图1中有 C1 -> B1。通过该定义，事件集中Lamport时间戳不等的事件可进行比较，我们获得事件的偏序关系
- 全序：如果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。
向量时钟
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) 没有因果关系、属于同时发生事件（Tb4[B]=4>Tc2[B]=3，Tb4[C]=1<Tc2[C]=2）。