1、概述

同步化是分布式系统中的一个重要概念，同步化主要解决的是排序问题。例如：多个线程不能同时操作一个变量，而是将多个线程使用锁或无锁结构进行同步，同步的目的就是将多个线程排序为一个操作时序对这个变量进行操作。

在单个计算机中，时间是明确的。当进程想要获取时间时，进程就进行一次系统调用，然后操作系统内核就会返回时间给这个进程。
但是在分布式系统中，每台计算机的时钟可能是一致的也可能是不一致的。即使分布式系统中的每台计算机中的时钟是一致的，那么对于这个分布式系统而言这个时钟也不是全局的。不是全局的时钟那么在分布式系统中可能会产生问题。

注意

分布式系统中，一般用进程来抽象整个系统中的节点，一般理解为一个进程为一台计算机。

2、物理时钟

计算机中的时钟是一个物理硬件通常称为计时器，计算机的计时器通常是一个石英晶体管。石英晶体管以一定的频率振荡。然后有两个寄存器与每个石英晶体相联，一个是计数器，另一个是保持寄存器。石英晶体振荡使得计数器减1。当计数器为0时产生一个中断，然后计数器从保持寄存器中重新装入初始值。计数器产生的中断称为时钟滴答。当产生一个中断时，操作系统就会响应中断并调用中断处理程序将时钟存储器中的值加1。

时钟中断示意图（图片来源于网络-示意图显示的是增1）：

2.1、物理时钟的问题

一句话总结：单台计算使用物理使用没有问题，分布式系统中各个进程使用物理时钟大概率不准确从而造成问题。
计算中物理时钟的的主要问题是时钟偏移（clock skew）。通俗点描述时钟偏移就是钟摆摆动的偏移变慢或者变快或者时快时慢导致时钟不同步。

时间偏移对同一台计算机的进程的时间获取基本上没有影响，因为即使出现了时间偏移，不同进程的在不同时刻得到的时间还是不一样的，但是在分布式系统就会有问题。

在分布式系统中，进程分布在不同的计算机上，这时每台计算机的时钟都发生了偏移，那么整个分布式系统中的时钟就是不同步的。整个分布式系统中的时钟不同步的话会导致依赖时钟同步的程序有问题。

解决物理时钟不同步的方式主要是时钟同步算法。这些算法包括但不限于：网络时间协议、Berkeley算法、Critian算法。

注意：物理时钟同步有一个很重要的点就是即使当前计算机时钟大于标准时间或UTC时间，那么这台计算机的物理时钟也是不会回退的，因为回退会造成很多问题，甚至是致命的问题。通常的解决方式是如果物理时钟过快就增加保持寄存器的值从而增加了时钟的振荡周期；如果物理时钟国漫就减少保持寄存器的值从而减少了时钟的振荡周期；以上都是通过一个过渡期来慢慢调整物理时钟从而达到与标准时间或UTC时间一致的结果。

2.2、物理时钟同步-网络时间协议(NTP)

网络时间协议就是使用计算机与时间服务器进行计算机的时钟同步以达到高精准度的时间校正。

2.3、物理时钟同步-Berkeley算法

Berkeley 算法 适用于无线电时钟（radio clock）不可用的分布式系统，此类系统无法得知真实时间，只能通过维护一个全局的平均时间作为标准时间。一台时间服务器会周期性地获取各个客户端上的时间，将其平均处理后，回传每个客户端的时间与平均时间的偏移，以达到统一使用此平均时间的目的。此算法适用于不仅时间可能不一致，时钟速率也可能不一致的系统。如果一个客户端的时间偏移过大，超出了容忍值，则通常不会参与平均时间的计算。如此可以防止系统的时间被单个异常的时钟过度影响。

Berkeley时钟同步算法图：

2.4、物理时钟同步-Cristian 算法

3、逻辑时钟

逻辑时钟关注点在顺序一致，这个时间不一定与实际时间相同。
这里面关键点是时钟完全一致实在是太复杂了，所以人们才提出了逻辑时钟；如果物理时钟能够完全一致，那么就不需要逻辑时钟了。

3.1、Lamport逻辑时钟

Lamport逻辑时钟是一个happens-before关系，happens-before的意思是先发生（happens-before在Java/go内存模型也在使用）。happens-before关系使用表达式:a->b表示读作“a在b之前发生”，意思是所有进程一致认为事件a先发生，然后事件b才发生。
Lamport提出逻辑时钟就是为了解决分布式系统中的时序问题，即如何定义a在b之前发生。

逻辑时钟定义

1. 如果a和b是同一进程中的两个事件，且a在b之前发生，则a->b为真。
2. 如果a是一个进程发送消息的事件，而b为另一个进程接受这个消息的事件，则a->b为真。

先发生关系是一种传递关系，所以若a->b且b->c则a->c。如果时间x和y发生在两个互不交换消息的进程中，那么x->y不为真，y->x也不为真，我们就称这两个事件是并发的；按照这样理解，happen-before关系是一个偏序关系，分布式系统中的一主多备之间的时间关系是全序关系。

3.2 Lamport逻辑时钟实现

实现Lamport逻辑时钟，每个时钟进程Pi维护一个局部计数器Ci，计数器按照如下步骤进行更新：

1. 执行一个事件之前，P执行Ci=Ci+1；
2. 当进程Pi发送一个消息m给Pj,在执行1的步骤后，把m的时间戳ts(m)设置为Ci;
3. 在接收到消息m时，进程Pj调整自己的局部计数器为Cj=max(Cj, ts(m)),然后执行第一步，并把消息传送给应用程序。

Lamport逻辑时钟有一个重要前提是：两个事件不会完全同时发生。

3.3 Lamport时钟校正

3.4 时钟校正说明

图a和图b说明：

1. 图a和图b都有3个进程；
2. 图a说明了使用物理时钟得到的时间分配；
3. 图b说明了使用Lamport逻辑时钟得到的时间分配。
   

   3.4.1 图a-物理时钟

   图a中的三个进程P1、P2和P3各自运行在不同的计算机上，每台计算机都有自己的时钟，每台物理时钟都以不同的速率工作从而得到了不同的时间。

在时刻6,进程P1将消息m1发送给进程P2，当m1消息到达进程P2时，进程P2的时时钟值是16；进程P2发送消息m2和进程P3发送消息m3发送时间及时钟值都还在合理的时钟值范围内；但是在进程P3发送m3到进程P2并达到P2的时钟值就出现了问题，因为消息发送的时刻应该小于消息达到的时刻，而Lamport逻辑时钟就解决了这个问题（看图b）。

3.4.2 图b-Lamport逻辑时钟

Lamport逻辑时钟就是让事件遵循happen-before关系。因为消息m3在时刻60离开P2，那么消息m3到达进程P1的时刻应该在61时刻或者更晚。所以每个消息应该根据发送者时钟的发送时间来调整自己的时钟值。图b中进程P3在收到m3消息后发现自己的时钟小于m3消息的时钟，进程P2根据消息m3的时钟调整了自己的时钟为61,进程P1也做了同样的时钟值调整。

3.4.3 Lamport逻辑时钟在复制服务的应用

复制是提升可靠性和性能的重要手段，复制面临的主要问题就是一致性问题，所有副本要完全相同，一般利用全序多播来实现。全序多播就是一次将所有消息以同样的顺序传送给每个接收者的多播。全序多播是实现状态机复制的重要工具，一致性乱了天下大乱。

3.4.4 Lamport逻辑时钟集群复制

5、参考

1. 分布式系统原理与范型（第2版）
2. 时钟同步
3. 分布式系统：Lamport 逻辑时钟
4. 时钟同步
5. 分布式系统（6） – 同步化