物理时钟 vs 逻辑时钟

可能有人会问，为什么分布式系统不使用物理时钟(physical clock)记录事件？每个事件对应打上一个时间戳，当需要比较顺序的时候比较相应时间戳就好了。

这是因为现实生活中物理时间有统一的标准，而分布式系统中每个节点记录的时间并不一样，即使设置了 NTP 时间同步节点间也存在毫秒级别的偏差。因而分布式系统需要有另外的方法记录事件顺序关系，这就是逻辑时钟 (logical clock)。

Lamport timestamps

Leslie Lamport 在1978年提出逻辑时钟的概念，并描述了一种逻辑时钟的表示方法，这个方法被称为 Lamport 时间戳(Lamport timestamps)。

分布式系统中按是否存在节点交互可分为三类事件，一类发生于节点内部，二是发送事件，三是接收事件。

Lamport timestamps 原理如下：

每个事件对应一个 Lamport timestamps，初始值为 0。

• 如果事件在节点内发生，timestamp + 1 。
• 如果事件属于发送事件，timestamp + 1 并在消息中带上该 timestamp。
• 如果事件属于接收事件，timestamp = Max(本地 timestamp，消息中的 timestamp) + 1。

假设有事件 a、b，C(a)、C(b) 分别表示事件 a、b 对应的 Lamport 时间戳，如果 C(a) < C(b)，则有 a 发生在 b 之前(happened before)，记作 a -> b，例如图1中有 C1 -> B1。通过该定义，事件集中Lamport 时间戳不等的事件可进行比较，我们获得事件的偏序关系(partial order)。

如果 C(a) = C(b)，那 a、b 事件的顺序又是怎样的？