分布式系统中的时间、时钟和事件的排序（一）
Time, Clocks, and the Ordering of Events in a Distributed System
是分布式理论中一篇非常经典也非常基础的论文，
这篇文章是该论文的阅读笔记，主要记录文章中关于逻辑时钟和分布式锁的实现算法。
论文还有一部分内容是介绍如何利用物理时钟在有外部系统参与的情况下解决分布式的同步问题。
我们可以通过时钟来知道时间。
那么时间和时钟的本质关系是什么？
当我们看到时钟上的读数便能了解当前的时间。
当时钟上读数显示某个数值时，这是一个特定的事件，本质上我们是通过一系列时间发生的顺序来了解时间。
分布式系统意味着多个节点参与，那么我们如何实现在分布式系统中的过程同步呢？
一种思路是通过时间来记录各个节点上事件发生的时间顺序，从而实现过程同步。
那如何记录事件发生的时间顺序呢？用物理时钟？
使用物理时钟的问题在于，每个节点上都需要一个物理时钟，
而我们很难保证不同物理时钟完全一致。
既然我们是通过事件来认识时间，那么我们也就可以摆脱物理时钟，用一些特定的事件取代时钟事件来认知时间。
这些事件可以形成分布式系统中的一个逻辑时钟。
首先我们来定义进程中时间发生的顺序关系，我们用 a -> b 表示事件 a 发生在事件 b 之前，
当满以下条件时我们认为 a -> b 成立：
- a、b 在同一个进程内部，a 发生在 b 之前
- a 是一条消息发送事件，b 相应的消息接收事件
可以看到这一关系具有传递性，暨如果 a -> b && b -> c => a -> c。
我们记录 C 为 a 事件发生的时间，那么如果 a -> b 则必然有 C < C，
但反过来不一定成立（a、b 可能是不同进程中并发执行的事件）。
可以看到这个关系只能给部分事件排序（无法给并发时间做排序），为了进一步得到所有事件的排序，
我们做一步简单的约定，对于并发事件直接根据进程编号来排序，如此一来我们就能给所有事件做排序，
而这些事件的排列变可以用来做我们在分布式系统中的逻辑时钟。
论文中定义了一种分布式锁的实现，它具有以下几个性质
- 持有锁的进程必须先释放锁其他进程才能获得锁
- 根据进程的请求顺序来分配锁
- 如果每个持锁的进程最终都会释放锁，那么每个锁的请求都能被满足
论文通过以下算法来实现所描述的分布式锁：
- 请求锁的进程在它维护的一个消息队列中放入一条请求锁消息 Pi:Tm（Tm为当前时间戳），并向其他所有进程发送这条请求锁的消息
- 在收到 Pi:Tm 消息后，Pj 进程向 Pi 发送带时间戳的确认消息；当 Pj 已经向 Pi 发送了时间戳大于 Tm 的消息后就不需要再发送确认消息了
- Pi 在释放消息时将 Pi:Tm 消息从它的队列中移除，并向所有其它进程发送带时间戳的锁释放消息
- Pj 在收到锁释放消息后，将 Pi:Tm 消息从它的队列中移除
- 当满足一下两种情况时，Pi 获得锁：
- 根据时间戳排序，Pi:Tm 排在队列中的首位
- Pi 收到所有其他进程的确认消息
论文假设进程间的消息收发的顺序和它被发送的顺序是一致的。
举个例子，假设进程 P1 按顺序给 P2 发送 m1、m2、m3 三条消息，
那么 P2 收到消息的顺序也是 m1、m2、m3。
可以很容易看出分布式锁的性质 1 和性质 3 可以满足，我们主要关注性质 2 的论证。
满足性质 2 需要理解以下两个关键点：
- 利用前文定义的时间排序算法，让各个进程内部都能看到一致的事件顺序（请求锁事件）
- 获得锁之前必须得到所有其他过程的确认，这确保请求锁的进程看到了其他过程在这条确认消息之前的所有消息（请求锁的消息）
第一点让各个进程内部看到一致的锁请求顺序；
第二点让确保 Pi 进程收到其他进程的锁请求，这些锁请求是其他进程在 Pi 在它发起锁请求之前发起的。
至于为什么收到确认消息（或者时间戳大于 Tm 的消息）就能认为这之前的消息都已经收到？
这一点是通过消息收发顺序的假设来实现的。