分布式系统2：分布式系统中的时钟
如果把一个分布式系统类比成现代社会的协作网络，那每一个分布式系统中的节点就是参与我们社会协作的每一个人，节点之间的通信就是人与人之间的沟通交流，节点完成自己的计算任务也可以类比成我们每一个人完成自己的本职工作。从这个意义上来说，现代社会协作网络的构建目标可以说和分布式系统有很多的一致的地方，比如我们希望社会运转更加高效（高效），我们希望社会是安全的（安全），我们希望社会更加包容和多元（异质性），我们希望社会的运转不会因为一部分人或者机构因故不能正常参与协作而产生问题（鲁棒性）等等。虽然不是非常的严谨，毕竟人类不是只会工作的劳动机器，但是我们或许可以借助这个类比思考一些分布式系统中的基本问题。
现代社会的协作网络之所以能够运转起来的最基础的保证是什么呢？我想一定是时钟的概念。人们上下班、与人约会等日常行为基本都起码要遵循一定范围内的同一个时钟，也是为什么一旦不同时区的人需要协作，就需要考虑时差的原因。同样地，在分布式系统中，每个独立的节点彼此之间需要合作，就需要遵循同一个时钟。在介绍分布式系统中的时钟之前，我们需要先介绍两种类型的分布式系统，因为时钟的概念在这两者之间有些微的差异。
同步系统和异步系统
分布式系统，根据节点之间通信的特点，可以分为同步系统（Synchronous Systems）和异步系统（Asynchronous Systems）。其中，同步系统对节点之间的通信的要求较为严格，要求节点之间的消息延迟必须有一个上限，这个上限可以很大，但是必须要有。相反，异步系统则更加接近真实世界，它不要求节点之间的消息延迟有一个确定的上限，甚至允许节点之间传递的消息可以丢失。
为什么要用节点之间的消息传递的特点来划分系统的类型呢？答案其实很简单，任何一个分布式系统都需要依靠节点之间的协作才能完成其使命，而节点之间协作的最根本的基础就是通信。可以说，没有节点之间的通信，分布式系统就不存在了。节点之间的通信是分布式系统中最重要的研究问题。
说回到同步和异步，通过这两类系统的定义不难发现，同步系统提供了很好的通信环境，这可以使得后续的很多问题的解决变得很简单。尽管同步系统的假设非常的美好，但是现实世界中构建的分布式系统很难保证节点之间消息传递延迟的上限，或者说构建一个这样的系统会有极高的成本，也就限制了同步系统的大规模建设。因此，世界上绝大多数研究分布式系统的工作都建立在异步系统的假设上。读者也不难发现，如果以同步系统作为假设，我们后续讨论时钟、快照和共识都可以用一个极为简单的算法完成，也只有在异步系统的假设下，上述三个问题才有了被讨论的价值。
分布式时钟——Lamport时钟和向量时钟
前文提到时钟是多个独立的节点之间能够相互协作的基础。那岂不是只需要为所有节点设置一个时钟就好了，这为什么会成为一个值得深入讨论的问题呢？的确，人与人之间的协作确实只需要遵循同一个时钟，比如统一遵循北京时间或者格林威治时间。但是这么做的前提是时钟的误差要远远小于人们使用时间的尺度。无论是上下班、开会还是赶高铁飞机，人们使用时钟的尺度大都在分钟这个级别，甚至用到秒这个级别的情况都很少。即便不考虑世界上误差最小的铝离子光钟（三百亿年累计的误差小于一秒），即便是目前智能手机里内置的时钟，也能够提供毫秒级甚至更加精细的计时，因此完全不需要考虑误差造成的影响。
然而，在分布式系统中则不同，在相互独立的节点之间维护一个统一的时钟是一个近乎不可能完成任务，没有人能保证一个分布式系统中的上百万个节点里的时钟都是从同一时刻开始，并且以相同速度计时。总的来说，物理时钟可能发生的两类误差是无法在分布式系统中被自动修复的，一个是时钟倾斜（clock skew），一个是时钟漂移（clock drift）。通俗来讲，如果节点A的时钟显示当前时间是当天的下午两点，而节点B显示的是当天下午三点，这就是时钟倾斜；而如果这个时候节点A的时钟计时的速度比B的快，比如节点A的时钟从两点到三点实际用了59分钟，而B则实际用了61分钟，这种现象叫做时钟漂移。无论是时钟倾斜还是时钟漂移，这两种误差都无法被分布式系统自动修复，一方面是因为不同节点的倾斜情况和漂移情况可能千奇百怪，另一方面则是如果通过通信的方式校正，那么消息传递的时间是无法被准确估算的，即当一个节点向另一个节点发送一条消息“我的当前时间为下午3点整”，那么另一个节点接收到这个消息的时候，发送消息的节点的当前时间一定实在三点之后了，而究竟是三点一刻还是三点一秒，没有人知道。
那该如何处理这个问题呢？如果仔细思考时钟在分布式系统中发挥的作用，就会发现其实并不需要一个真的显示当前时间的时钟。在分布式系统中，时钟的作用是为了记录不同节点之间发生事件的顺序，而顺序某种程度上可以反应事件之间的因果关系。明白了这个道理，时钟其实也不必非得是年月日时分秒的形式，只记录事件发生的顺序，就只需要为每一个事件分配一个序号即可。
最先意识到这个问题的是分布式系统领域的大咖Leslie Lamport。他是第一个提出在分布式系统中使用逻辑时钟（Logic Clock）来解决系统全局事件排序的问题的人。Lamport提出，在分布式系统的不同节点中发生的事件，在节点内是有着天然的顺序的（偏序），但是这个顺序不能推广到整个分布式系统中，节点之间既然需要相互协作，就必须知道节点内发生的事件在整个分布式系统中的顺序（全序）。然而前文已经描述过在一个异步系统中引入一个统一的时钟是行不通的。因此，Lamport则提出使用一种逻辑时钟来为事件标记顺序。
Lamport提出的方法也很简单，既然不能用绝对的物理时钟给事件排序，那就直接为事件赋予一个编号就可以了，节点之间进行通信的时候，只需要把当前的编号告知通信的对方即可。
具体的方式是这样的，在一个节点内发生事件的顺序是已知的，可以使用递增的编号来标记，当涉及到多个节点之间的通信时，发送消息的一方就需要把自己发送消息这个事件的编号告知接收消息的一方。显然，接收消息的一方接收消息这个事件的编号会有两种情况，一种是小于或者等于收到的事件的编号，一种则是大于。在逻辑上，一个消息只有先发送出去才能被接收到，所以当一个节点收到一个消息，发现收到的消息所携带的事件的编号大于自己当前的事件的编号，那么这显然是违反逻辑的，于是就需要把自己当前的时间编号设置为大于收到消息的编号，使之符合逻辑。这也不会引起节点内部事件顺序的混乱，因为改变编号的行为仍然是只增不减。如果所有的节点都遵循这样的准则，那么整个分布式系统中，只要涉及到通信的事件就一定有一个唯一的顺序，而至于那些没有参与到通信中的事件（并发事件），其实它们的全局顺序并不重要，因此只需要在节点内部保持递增即可。
上述过程中的事件的编号，就是大名鼎鼎的Lamport时钟。Lamport时钟保持了事件发生的因果关系，同时也知道了整个系统中事件的相对顺序。Lamport提出的逻辑时钟解决了分布式系统内部的事件全序问题，但是细心的读者会发现，这种时钟其实只能保证参与了节点之间通信的事件的顺序，而对于没有参与通信的并发事件，我们仍然不知道两个并发事件到底谁先发生谁后发生。其实就满足分布式系统的各个节点能够相互协作的需求而言，Lamport时钟就已经足够了，然而识别并发事件涉及到资源分配和调度等一系列问题，也是分布式系统中的一大课题，此时就需要用到Cristian等人提出了向量时钟（Vector Clock）。向量时钟可以用来识别分布式系统中的并发事件。
在向量时钟下，每个节点应当保存一个时钟向量，向量中的每个元素是当前节点已知的，每个节点最后一个事件的序号，因此向量的大小也应该是系统中参与通信的节点的数量。在通信过程中，每个节点之间发送和接收的时间戳，也不再是Lamport提出的事件序号，而是一个时钟向量，然后按照Lamport提出的更新原则更新这个向量，即对于时钟向量的每一个分量，将其更新为当前的最大值。有了这个时钟向量，我们可以通过比较两个时钟向量分量的大小来判断两个事件之间的关系，如果一个时钟向量的所有分量都大于另一个，那么这两个时钟向量之间就是具有因果关系的。只要有任何一个分量小于另一个向量中对应位置的分量，那么这两个事件就是并发的。
分布式时钟是分布式系统的基础，无论是Lamport时钟还是向量时钟，其意义不仅是解决了分布式系统中的基本问题，其设计的基本思路也是分布式系统中核心的思维方式之一。
总结
- 为什么不能引入统一时钟；
- 同步系统和异步系统；
- Lamport时钟和向量时钟