Time, Clock, and the Ordering of Events in a Distributed System
时间时钟和分布式系统中事件的顺序
背景
当消息传递的延迟是不能够被忽视的时候（相较于单机中进程的消息交换的延迟），我们就认为该系统是一个分布式系统。
在一个分布式系统中，有时候不太可能说两个事件中其中一个发生在另一个之前。这个“happen before”关系在事件中因此成了部分事件的顺序。
之前定义事件a发生在事件b之前使用的是时钟的概念，即物理时间的概念。但是即使这个系统中存在这样的物理时钟，但是由于时钟的精度和精确性问题，还是存在问题。（比如，a和b发生的时候，其物理时钟处在统一时刻，此时便不能分辨出两个事件的发生先后，精确性的问题在于分布式环境中存在时钟同步和跳变问题）
鉴于以上原因此时便不能再依赖于物理时钟。
逻辑时钟
我们定义一个 Clock Condition. 对于任意事件a, b:
if a -> b then C<a> < C<b>
可以很明确的发现，要想满足Clock Condition，需要满足以下两个条件：
- 如果a,b是在同一个进程Pi里的两个事件，并且a 在 b 之前，那么Ci<a> < Ci<b>
- 如果a是进程Pi发送出去的消息，而b是Pj接收到消息，那么Ci<a> < Cj<b>
若想保证系统的时钟满足Clock Condition，我们需要确保系统的时钟满足C1和C2.
C1比较简单，进程只需要满足以下的规则即可：
IR1. 每个进程Pi，在任意两个成功的事件之间自增自己的时钟Ci即可。
IR2.
a>. 如果事件a是一个消息发送事件是由进程Pi发起的，发送的消息为m，m中需要包含一个时间戳， Tm = Ci<a>
b>. 当Pj收到消息m，Pj设置自己的时钟大于或等于当前的值并且要大于Tm。
Lamport提出的逻辑时钟可以用来对分布式系统中的所有事件进行全序排列。这是一个很难得的进步。
当在排序的时候遇到时钟相等的事件的时候，可以按照预先指定的进程优先级顺序，打破平局。即优先级较高的进程，可以排序在与其逻辑时钟相同的事件前面。这样就能全部排序了。
使用这种全序关系实现的一个分布式锁。考虑一个系统由固定的进程数量组成，共享一个资源，每次只有一个进程可以使用该资源。所以进程必须同步他们自己状态，来保证没有冲突。我们希望存在一个算法，每次只给某一个进程赋予访问资源的权限。需要满足以下3个条件：
- 每个获取到资源的进程要授予其它进程访问资源权限时，必须先自己释放对资源的授权。
- 不同的授权请求，必须按照它们发起的顺序给于授权。
- 如果每个授权资源的进程最终释放了资源，那么它们最终都授权过。
我们假设资源最开始授权给了某一个进程。
必须意识到，通过一个中央的授权进程按照它收到的授权顺序进行授权是不够的。因为网络包可能并不是按照请求发起的顺序到达中央授权进程的。为了解决这个问题，我们实现一个系统的时钟，满足IR1和IR2。并且用它们来给所有的事件定义一个全局的顺序=>。这样就给所有的申请资源请求和释放资源请求都可以排序了。那么问题就在于只要确保了每个进程学习到了所有其它进程的请求了。
我们假设任意两个进程Pi和Pj，消息从Pi到Pj是按照发送的顺序到达的。更进一步，我们假设每个消息最终是送达的。我们同样假设进程可以直接给其它所有进程发送消息。
每个进程维护自己的一个发送队列，其不能被其它进程看到。并且假设请求队列里面初始化时存在一条消息，T0:P0请求，意味着，一开始资源是授权给了P0进程的。并且T0是小于所有进程的时钟的。我们定义一下5条规则：
- 要获取资源，进程Pi需要发送一个 Tm:Pi的请求到其它进程，发送之后将这条消息放置到自己的请求队列中。Tm是这条消息的是时间戳。
- 当进程Pj收到 Tm:Pi请求资源的消息后，它将其放置到自己的请求队列中，并且回复一个带时间戳的ACK消息给Pi。
- 当需要释放资源的时候，进程Pi从自己的队列中移除任何的 Tm:Pi请求，并且发送一个带时间戳的Pi释放资源请求给其它进程。
- 当Pj收到一个Pi释放资源的消息之后，它从自己的请求队列中移除任何的 Tm:Pi 请求。
- 进程Pi最终可以授权资源取决于如下两个条件满足：
a>. Tm:Pi 排在所有请求资源队列的队头（通过=>规则排序）
b>. Pi已经收到所有其它进程的大于Tm时间戳的消息。
（笔者：这就保证了其它进程已经学习到了Pi进程Tm:Pi的请求资源，不会去争抢）
这是一个分布式的算法，每个进程都是独立地运行这些规则，没有一个中央的节点或者存储来做同步。
这个算法的实现可以用来实现任何分布式多进程系统的期望的同步。
这个同步算法依托于一个状态机，由一个可能的命令集合 C，和一个可能得状态集合 S。
以及一个函数：e: C X S -> S。可以得到一个关系即：
e(C,S) = S'。这个关系意味着，在机器处于S状态的时候，可以执行命令C，进而使得状态机进入 S' 状态。
在我们的例子中，C 即是由所有的 Pi 的请求资源命令和释放资源命令组成。
状态由等待请求命令的队列组成，其中队列头部的请求是当前授予的请求。
执行请求命令将请求添加到队列的尾部（笔者：这里的尾部个人认为，应该是放在排序后合适的位置），执行释放命令将命令从队列中删除。
每个进程独立地模拟状态机的执行。同步是可以满足的。因为所有的进程对收到的请求中的时间戳都通过 => 关系进行排序。所以每个进程都会执行相同的顺序的命令。
一个进程可以执行时间戳为T的命令，当他已经学习到了所有的其它进程的小于等于T的命令。
这个方法允许在所有的分布式环境下实现任意一种形式的多进程间的同步。不过缺点也是很明显的，即，一个进程必须知道所有其它进程发起的命令。也就意味着每个参与者进程必须是活跃的。任何单个进程出问题，都会导致整个状态机无法向前推进。从而导致整个系统停滞。
（笔者：这是分布式中Liveness的保证，不在此篇的讨论范围内）。
系统要想理解（意识到）某个进程出现问题，必须引入物理时间的概念，因为只能通过长时间收不到请求来发现某个进程出现了failure。或者使用者从外部告诉系统。
（笔者：有了这种全序关系的之后，我们就可以实现我们自己的分布式复制状态机，即在每个逻辑时钟上达成分布式共识。新的较大的逻辑时钟ID，将基于小于其的ID对应的所有共识的状态基础上进行状态的叠加。（State Machine Replication））
异常行为（以下为简略总结）：
当仅仅使用逻辑时钟时，会出现一些异常行为。当外部系统（现实世界，即物理时间）干预到仅仅使用逻辑时钟的系统时，会出现一些异常现象，举例（注：这里的举例是笔者自己举的例子）：
进程Pi，对 变量 X的赋值序列如下：
C1: X = 1;
C2: X = 2;
C3: X = 3;
此时，外部系统看到了 X = 3，告知进程Pj，去查看一下X的值，对于外部系统来说，此时无论哪个进程去读取X的值，都应该得到 X = 3 这个事实。
Pj的逻辑时钟目前还是1，系统内部没有其它进程和Pj有过通信。所以其只能按照自己当前的逻辑时钟去读取X的值。
C1 只能读取到 X = 1 的状态。
此时对于外部系统（比如用户）而言，不能理解这个现象了。明明外部系统已经看到了Pi将 X 的值更新成 3。但 Pj 进程读取到的还是1。
这里Lamport使用狭义相对论的概念来进行解释了。（以下是笔者理解的）
对于系统内部的进程而言，Pj读取到 X 的值是1是再合理不过的，之所以系统外部的用户感到疑惑，是因为，外部系统所在的时空是物理世界，物理时空，可以想象他有一个隐形的单调递增的全局时钟。但是这个外部世界的时钟，系统内部是无法感知的。所以这个问题，仅凭系统内部的机制是无法解决的。既然引入了外部系统，则是视角变换了，系统内部必须引入外部世界的因素，来进行度量内部系统的行为。
在系统内部，Pi对X的修改之所以对于Pj无法感知，原因就是Pi和Pj之间没有发生任何的消息通信，即根据狭义相对论描述，Pj如果想要感知到Pi的变化，Pi必须传递点信息过去，并且，Pj发生读取的时刻，要处在Pi发送消息的未来光锥之内，Pj才能感知到Pi做的一些变化。如果Pj在消息还没有传递到它的时候已经发生了读取，则也是无效的。
所以，要解决上述问题，需要引入观察者系统的度量因素，重新对于事件进行排序。才能达到观察者想要的目的和效果。
因此需要引入现实世界的物理时间。
物理时间的引入，就需要解决时钟偏移和漂移的问题。漂移是单机的行为，可以通过硬件设计控制其只向大漂移。
偏移是多台机器之间的时钟不同步问题，要想将所有的事件按照现实世界的物理时间排序，就必须要做到系统中的时钟必须是强制同步的，只允许一个极小的误差 E，即同一时刻，不同进程的时钟必须将误差缩小在E之内。在引申一下也就是说，如果两个相关的事件A,B分别发生在不同的机器的进程Pi和Pj中，即使Pi向Pj传递消息的速度就是光速，也要保证两边的时钟不能出现相同的值。
上述的要求，对于分布式时钟的同步提出了相当严格的要求。Google的Spanner就根据Lamport的论文中的同步算法实现了全球范围内的物理时间同步。保证了线性一致性。
代价也是非常大的，需要铯原子钟级别的晶振误差。
Lamport的算法，对时钟同步的最小延时做出了明确的计算和规定。对于网络延迟的误差范围也给出了规定。对于时钟的晶振误差也给出了范围。
IR1和IR2的定义：
尽管规则是根据物理时间参数正式指定的，但是进程只需要知道它自己的时钟读数以及收到的消息的时间戳。为了数学上的方便，我们假设每个事件都在物理时间的精确时刻发生，这样相同进程中的不同事件在不同的时间发生。这些规则就是规则 IR1 和 IR2 的特化，因此我们的时钟系统满足时钟条件。真实事件具有有限的持续时间这个事实不会给算法的实现带来任何困难。在实现过程中，唯一真正关心的是确保离散的时钟“嘀嗒”足够频繁，以便保证满足 C1。
Um -> 最小延迟
U -> 实际最小延迟
E -> 不同节点间的时钟偏移的最大值
E' -> 表示不可预测延迟
T -> 表示每T秒发送一个消息
d -> 表示弧的长度
k -> 表示晶振的频率
最终的定理的结果即：
E 约等于 d(2kT + E') 其含义大致理解如下：
括号展开：E 约等于 2kTd + E'd
不同节点间能容忍的时钟最大偏移 约等于
每T秒钟一次消息所产生的时钟的误差 在 长度d的弧上的积 的两倍 与
不可预测延迟 在 长度d上的积 的 和。
（具体含义还是不太清楚，不过暂时也不打紧）
意味着，只要两个时钟在同一时刻的漂移差值 小于 上述结果，几满足了物理时钟的误差内同步，即可满足能够区分出相关因果事件在物理事件上的单调性。
结论
我们已经看到“先发生”这个概念定义了分布式多进程系统中事件的不变偏序关系。我们描述了一种用来将偏序扩展为有些随意的全序的算法，并展示了怎样使用全序来解决简单的同步问题。未来的论文将展示如果扩展这种方法来解决任意的同步问题。
该算法定义的全序有些随意。如果它与系统用户所感知的顺序不一致，则可能会产生异常行为。这可以通过正确使用同步的物理时钟来避免。我们的定义表明了时钟可以同步的误差程度。
在分布式系统中，重要的是意识到事件发生的顺序只是偏序关系。我们认为这种想法对理解任何多进程系统很有帮助。它可以帮助人们独立地理解多进程的基本问题以及用来解决它们的机制。
The End;
