事件和时间：Time, Clocks, and the Ordering of Events in a Distributed System 读后感

balabala

前言



Lamport老爷子在这篇著名的论文中探讨了分布式系统中事件和时间的关系，并且以数学家的最敏锐的嗅觉抓住了分布式系统中的本质问题，同时引入逻辑时钟，为以后的分布式系统设计点亮了指路明灯。

事件


事件是驱动万物演化的根本动力。事件包含其内在的一系列行为以及这些行为而产生的影响，而这些影响又可能触发下一个事件。在这绵延不断的事件链条中，周围的世界处于一刻不停的变化之中。一件极其微小的事件可能产生巨大的连锁反应，蝴蝶效应说的便是这个道理。

时间


时间是什么，没几个人真正理解。不妨将时间和事件联系起来，我们便会产生直观而具体的感受。我们是无法感受时间的，也无法测量时间，我们感知的时间其实是事件的流逝，比如看到太阳升起我们知道是早晨，而落日则意味着傍晚。

时间有众多的计量方法：比如古人的日晷，再到现在的原子时钟。所有计时方法的本质在于记事。因此，时间和事件本就合二为一。
分布式系统
在我看来，这个世界就是一个分布式系统。区别的只是系统的规模。

搞计算机的眼里几台服务器组成的系统就是分布式系统，生物学家眼里某个种群构成了一个分布式系统，而在外眼里，整个世界是一个分布式系统。

分布式系统最核心的问题是什么？信息交互！为什么在上面提到的不同的学者关注不同的分布式系统呢？这是因为这些系统之间难以存在信息流通。例如，目前阶段一台计算机很难和一头大象交流。而计算机之间则很容易信息交互。

信息又是什么？信息是载体，它是事件绵延不断传播的源动力。没有了信息，事件便成为孤单的粒子。因此，可以毫不夸张的说，信息是发展的源动力。

分布式系统的难点在于分布式。分布式带来的头疼问题是信息交互的延迟、丢失、乱序等一系列问题。受限于光速限制，任何信息的传播都需要一定的时间，哪怕再短。

而信息交互的延迟、丢失、乱序等问题则进一步体现在事件的影响上。信息的延迟可能导致事件发生的延迟，信息的丢失导致事件根本不会被处罚、信息的乱序则可能导致事件错乱。而这些看似偶然事件错乱则可能会给大千世界的演化带来极其深刻的影响。

事件序列


其实文章的核心在于讨论事件序列。事件序列指的是特定环境中的事件发生的先后顺序。时间只不过是事件序列的一种定义方法。即使是用时间来定义，也存在物理时间、逻辑时间等等方法。

一个分布式系统由众多独立的个体组成，称之为Process，每个个体的事件来源有两类：

• 内部事件：此类事件由个体内部产生，可以认为与其他个体不产生关联；
  
• 外部事件：此类事件由其他个体刺激本个体产生，这种刺激的表现形式是消息。
  

事件序列有两种：偏序事件序列和全序事件序列。

偏序

所谓的偏序指的是只能为系统中的部分事件定义先后顺序。这里的部分其实是有因果关系的事件。

例如，发生在个体PA的一个事件E1，该事件的影响是产生了消息M，M传播至个体B，进而导致事件E2的发生，即说明E1->E2：因为E1而导致了E2的产生。而对于两个相互独立的事件，我们无法从原理上判断孰先孰后。

偏序的严格定义，偏序以符号->代替：

• 在同一个Process内部，如果事件a早于事件b发生，称为a->b；
  
• 如果a和b是两个不同Process的事件，且b是a发送的消息的接收者，同样 a->b；
  
• 如果a->b，b->c，那么a->c。
  

这个定义很容易理解。

Lamport在论文中提出了一种利用逻辑时间设计的一种偏序系统方法：

• 每个Process存在独立的事件序列发生器，每次产生新的事件，该序列发生器自增1，并将结果赋予该事件；
  
• 如果Process的事件E需要向其他Process发送消息M，那么在M中携带E的序列号；
  
• 如果Process收到外部消息M，获取M中携带的序列号，与自身的事件序列发生器取最大值，然后自增1，赋给由于M而触发的新的外部事件。
  

根据上面的定义，我们可以得到如下结论：

• Process内部的事件均可以比较先后顺序；
  
• Process之间的因果事件可以确定先后顺序，而Process之间的独立事件则无法比较。
  

例如：
上图中的p1->r4成立，因为有：p1->q2，q2->q3，q3->q4，q4->r3，r3->r4。
而p3->q3则不成立。

真实世界其实是一个偏序系统，记住，物理时间是不准确的。

全序

全序是指所有的事件都可以区分先后顺序。无论是真实或是虚拟世界，这都是受欢迎的。因为，所有的事件都有了一个统一的评判标准，我们一直欢迎统一而拒绝分裂。

在偏序的基础上，Lamport定义了一种全序方案，在偏序的基础上有所增强：

每个事件表示为一个三元组：<E, C, P>

其中：

• E：代表事件；
  
• C：代表事件所发生的Process赋予该事件的序列号(逻辑时间)；
  
• P：代表事件所发生的Process的编号
  

有了该三元组后，定义事件先后的顺序就变成了：

如果C(i, a) < C(j, b)  
或者
  如果C(i, a) = C(j, b)并且P(i) < P(j)

通过事件序解决特定问题

做着费尽心思定义了偏序和全序，接下来就看它如何帮助解决实际问题。例如，有这样一个共享资源分配问题：

多个Process共享一个集中资源R，每个Process想使用R时必须申请，经过全部人同意后才可以使用，且使用完成后必须要释放R以供他人使用。且需要满足先申请先访问原则，还不能存在死锁的问题。

很容易想到的是使用协调者的解决方法：

• 存在一个至高无上的协调者管理资源分配；
  
• 协调者根据收到请求的先后顺序分配资源的使用顺序；
  

这个方案看起来一切正常，但是可能存在一个漏洞，假如：

• Process 1向协调者发起资源分配请求R1；
  
• Process 1向Process2发消息M；
  
• M触发Process 2产生事件，该事件也向协调者发起资源分配请求R2；
  
• R2先于R1到达协调者
  

于是就不满足上面的先申请先访问的原则了。

Lamport提出的方案：

• 去掉协调者，改用分布式协调方案；
  
• 每个Process均有一个队列维护资源申请的消息，成为RequestQueue
  
• P申请资源时，向其他Process广播该资源申请消息，该消息是一个三元组<T, P, Action>；
  
• P收到其他Process的资源申请消息时，将该消息放置于RequestQueue的尾部，并给申请者回复ACK消息；
  

而Pi判断某个消息(其实代表了一个事件，因为一般是事件申请资源访问，而消息只不过是代替事件去获得访问权限)能否获得资源的访问权限的条件：

• 该消息获得了所有节点的ACK；
  
• 在本地的消息队列中没有比该消息更早的消息。
  

我们仔细品味下这两个条件：

• 获得所有节点的ACK这个比较容易理解，只有大家都同意了才可以访问；
  
• 没有比该消息更早的消息则表示该消息是最早的申请者，注意，本地的消息队列中不仅有自己发出的资源申请访问的请求消息，还存有其他节点的资源申请访问请求；
  
• 如何判断两个消息先后顺序就采用了我们上面的全序定义方案，先判断T，相同时再判断P。
  

需要注意的是，本地的Request Queue中保存的请求消息可能会乱序，并非说队列头部是就是就旧的，队列尾部的就是最新的。因为多个节点之间存在消息传递上的延迟，先发出的请求有可能会后到达。因此，在判断时需要遍历队列上的所有消息。

物理时钟

论文的这部分未涉猎，因为涉及到很复杂的数学证明。

总结


如果将这篇论文当作纯技术论文来看，那就大错特错了，论文的背后其实包含了极其深刻的数学和哲学含义，作者看似在说分布式系统，其实可以将其推广到整个世界乃至宇宙。至少，老爷子的这篇文章触发了我重新审视时间和事件这两个概念，特整理出来，与大家分享，希望能互相交流。

原文地址：https://zhuanlan.zhihu.com/p/27503041