逻辑时钟
分布式系统：Lamport 逻辑时钟 - 知乎 (zhihu.com)
分布式系统解决了传统单体架构的单点问题和性能容量问题，另一方面也带来了很多的问题，其中一个问题就是多节点的时间同步问题：不同机器上的物理时钟难以同步，导致无法区分在分布式系统中多个节点的事件时序。1978年Lamport在《Time, Clocks and the Ordering of Events in a Distributed System》中提出了逻辑时钟的概念，来解决分布式系统中区分事件发生的时序问题。
简介
什么是逻辑时钟
逻辑时钟是为了区分现实中物理时钟提出来的概念，一般情况下我们提到的时间都是物理时间，但实际上很多应用中，只要所有机器有相同的时间就够了，这个时间不一定要跟实际时间相同。更进一步，如果俩个节点之间不进行交互，那么它们的时间甚至都不需要同步。因此问题关键点在于节点的交互要在事件的发生顺序上达成一致。
综上，逻辑时钟指的是分别是系统中用于区分事件的发生顺序的时间机制。从某种意义上讲，现实世界中的物理时间其实是逻辑时钟的特例。
为什么需要逻辑时钟
时间是在现实生活中很重要的概念，有了时间我们就能比较事情发生的先后顺序。如果是单个计算机内执行的事务，由于它们共享一个计时器，所以很容易通过时间戳来区分先后。同理在分布式系统中通过时间戳方式来区分先后行不行？
答案是NO，因为在分布式系统中的不同节点间保持它们的时钟一致是一件不容易的事情。因为每个节点的CPU都有自己的计时器，而不同计时器之间会产生时间偏移，最终导致不同节点上面的时间不一致。也就是说如果A节点的时钟走的比B节点的要快1分钟，那么即使B先发出的消息（附带B的时间戳），A的消息（附带A的时间戳）在后一秒发出，A的消息也会被认为先于B发生。
那么是否可以通过某种方式来同步不同节点的物理时钟呢？答案是有的，NTP就是常用的时间同步算法，但是即使通过算法进行同步，总会有误差，这种误差在某些场景下（金融分布式事务）是不能接受的。
因此Lamport提出逻辑时钟就是为了解决分布式事务中的时序问题，如何定义a在b之前发生。值得注意的是，并不是说分别是系统只能用逻辑时钟来解决这个问题如果以后有某种技术能够让不同节点的时钟完全保持一致，那么使用物理时钟区分先后是一个更简单有效的方式。
NTF
网络时间协议NTF（Network Time Protocal）是TCP/IP协议族里面的一个应用层协议，，用来使客户端和服务器之间进行时钟同步，提供精准度的事件校正。NTP服务器从权威时钟源（例如原子钟，GPS）接受紧缺的协调世界时UTC，客户端再从服务器请求和接收时间。
NTP基于UDP报文进行传输，使用的UDP端口为123.
时钟层级
NTP允许客户端从服务器请求和接收时间，而服务器又从权威时钟源（例如原子钟、GPS）接收精确的协调世界时UTC。
NTP以层级来组织模型结构，层级中的每层被称为Stratum。通常将从权威时钟获得时钟同步的NTP服务器的层数设置为Stratum 1，并将其作为主时间服务器，为网络中其他的设备提供时钟同步。而Stratum 2则从Stratum 1获取时间，Stratum 3从Stratum 2获取时间，以此类推。时钟层数的取值范围为1～16，取值越小，时钟准确度越高。层数为1～15的时钟处于同步状态；层数为16的时钟被认为是未同步的，不能使用的。
NTP同步原理
NTP最典型的方式是Client/Server方式，如下图所示。
- 客户端首先想服务端发送一个NTP报文，其中包含了该报文离开客户端的时间戳t1；
- NTP请求报文达到NTP服务器，此时NTP服务器的时刻为t2,。当服务器收到该报文时，NTP服务器处理后，于T3时刻发出NTP应答报文。该应答报文中携带报文离开NTP客户端的时间戳t1、到达NTP服务器的时间戳t2、离开NTP服务器时间戳t3
- 客户端在接收到响应报文时，记录报文的返回时间戳t4
客户端用上述4个时间戳就能够计算出2个关键参数
如何实现逻辑时钟
时序关系相对论
通过前面的讨论我们知道通过物理时钟（即绝对参考系）来区分先后顺序的前提是所有节点的时钟完全同步，但目前并不现实。因此，在没有绝对参考系的情况下，在一个分布式系统中，你我㞏判断事件A是否发生在事件B之,除非A和B存在某种依赖关系,即分布式系统中的事件分布是有序的.
上面的结论跟狭义相对论有异曲同工之妙,在狭义相对论中,不同观察者在同一参考系中观察到的事件先后顺序是一致的,但是在不同的在不同的参考系中对俩个事件谁县发生可能具有不同的看法.当且晋档事件A是由事件B引起的时候,事件A和B才存在一个先后关系.俩个事件可以建立因果关系的前提是,俩个事件之间用等于或小于光速传递信息.值得注意的是这里的因果关系指的是时序关系,即时间的前后,并不是逻辑上原因和结果.
那么是否我们可以参考狭义相对论来定义分布式系统中两个事件的时序呢？在分布式系统中，网络是不可靠的，所以我们去掉可以和速度的约束，可以得到两个事件可以建立因果（时序）关系的前提是：两个事件之间是否发生过信息传递。在分布式系统中，进程间通信的手段（共享内存、消息发送等）都属于信息传递，如果两个进程间没有任何交互，实际上他们之间内部事件的时序也无关紧要。但是有交互的情况下，特别是多个节点的要保持同一副本的情况下，事件的时序非常重要。
Lamport逻辑时钟
分布式系统中按是否存在节点交互可以分为三类事件，一类发生于节点内部，二是发送时间，三是接受事件。
注意：以下文章中提及的时间戳如无特别说明，都指的是Lamport 逻辑时钟的时间戳，不是物理时钟的时间戳
逻辑时钟的定义：
Clock Condition.对于任意事件a, b：如果a -> b（->表示a先于b发生），那么C(a) < C(b), 反之不然, 因为有可能是并发事件 C1.如果a和b都是进程Pi里的事件，并且a在b之前，那么Ci(a) < Ci(b) C2.如果a是进程Pi里关于某消息的发送事件，b是另一进程Pj里关于该消息的接收事件，那么Ci(a) < Cj(b)
- 每个事件对应一个Lamport时间戳，初始值为0
- 如果事件在节点内发生，本地进程中的时间戳加1
- 如果事件属于发送事件，本地进程中的时间戳加1并在消息中带上该时间戳
- 如果事件属于接收事件，本地进程中的时间戳 = Max(本地时间戳，消息中的时间戳) + 1
假设有事件a、b，C(a)、C(b)分别表示事件a、b对应的Lamport时间戳，如果a发生在b之前(happened before)，记作 a -> b，则有C(a) < C(b)，例如图1中有 C1 -> B1，那么 C(C1) < C(B1)。通过该定义，事件集中Lamport时间戳不等的事件可进行比较，我们获得事件的偏序关系(partial order)。注意：如果C(a) < C(b)，并不能说明a -> b，也就是说C(a) < C(b)是a -> b的必要不充分条件
如果C(a) = C(b)，那a、b事件的顺序又是怎样的？值得注意的是当C(a) = C(b)的时候，它们肯定不是因果关系，所以它们之间的先后其实并不会影响结果，我们这里只需要给出一种确定的方式来定义它们之间的先后就能得到全序关系。注意：Lamport逻辑时钟只保证因果关系（偏序）的正确性，不保证绝对时序的正确性。
一种可行的方式是利用给进程编号，利用进程编号的大小来排序。假设a、b分别在节点P、Q上发生，Pi、Qj分别表示我们给P、Q的编号，如果 C(a) = C(b) 并且 Pi < Qj，同样定义为a发生在b之前，记作 a => b（全序关系）。假如我们对图1的A、B、C分别编号Ai = 1、Bj = 2、Ck = 3，因 C(B4) = C(C3) 并且 Bj < Ck，则 B4 => C3。
通过以上定义，我们可以对所有事件排序，获得事件的全序关系(total order)。上图例子，我们可以进行排序：C1 => B1 => B2 => A1 => B3 => A2 => C2 => B4 => C3 => A3 => B5 => C4 => C5 => A4
观察上面的全序关系你可以发现，从时间轴来看B5是早于A3发生的，但是在全序关系里面我们根据上面的定义给出的却是A3早于B5，可以发现Lamport逻辑时钟是一个正确的算法，即有因果关系的事件时序不会错，但并不是一个公平的算法，即没有因果关系的事件时序不一定符合实际情况。
上面的分析过于理论，下面我们来尝试使用逻辑时钟来解决分布式锁问题。
分布式锁问题本质上是对于共享资源的抢占问题，我们先对问题进行定义：
- 已经获得资源授权的进程，必须在资源分配给其他进程之前释放掉它；
- 资源请求必须按照请求发生的顺序进行授权；
- 在获得资源授权的所有进程最终是否资源后，所有的资源请求必须都已经被授权了。
首先我们假设，对于任意的俩个进程Pi和Pj，它们之间传递的消息是按照发送顺序被接收到的，并且所有的消息最终都会被接收到。每个进程会维护一个它自己对其他所有进程都不可见的请求队列。我们假设请求队列初始时刻只有一个消息（T0：P0）资源请求，P0代表初始时刻获得资源授权的那个进程，T0小于任意时刻初始值。
- 为请求该项资源，进程Pi发送一个（Tm:Pi）资源请求（请求锁）消息给其他所有进程，并将该消息放入自己的请求队列，在这里Tm代表了消息的时间戳
- 当进程Pj收到（Tm:Pi）资源请求消息后，将它放到自己的请求队列中，并发送一个带时间戳的确认消息给Pi。(注：如果Pj已经发送了一个时间戳大于Tm的消息，那就可以不发送)
- 释放该项资源（释放锁）时，进程Pi从自己的消息队列中删除所有的（Tm:Pi）资源请求，同时给其他所有进程发送一个带有时间戳的Pi资源释放消息
- 当进程Pj收到Pi资源释放消息后，它就从自己的消息队列中删除所有的（Tm:Pi）资源请求
- 当同时满足如下两个条件时，就将资源分配（锁占用）给进程Pi：
- 按照全序关系排序后，（Tm:Pi）资源请求排在它的请求队列的最前面
- i已经从所有其他进程都收到了时间戳>Tm的消息
下面我会用图例来说明上面算法运作的过程，假设我们有3个进程，根据算法说明，初始化状态各个进程队列里面都是(0:0)状态，此时锁属于P0。
接下来P1会发出请求资源的消息给所有其他进程，并且放到自己的请求队列里面，根据逻辑时钟算法，P1的时钟走到1，而接受消息的P0和P2的时钟为消息时间戳+1。
收到P1的请求之后，P0和P2要发送确认消息给P1表示自己收到了。注意，由于目前请求队列里面第一个不是P1发出的请求，所以此时锁仍属于P0。但是由于收到了确认消息，此时P1已经满足了获取资源的第一个条件：P1已经收到了其他所有进程时间戳大于1的消息。
假设P0此时释放了锁（这里为了方便演示做了这个假设，实际上P0什么时候释放资源都可以，算法都是正确的，读者可自行推导），发送释放资源的消息给P1和P2，P1和P2收到消息之后把请求(0:0)从队列里面删除。
当P0释放了资源之后，我们发现P1满足了获取资源的两个条件：它的请求在队列最前面；P1已经收到了其他所有进程时间戳大于1的消息。也就是说此时P1就获取到了锁。
值得注意的是，这个算法并不是容错的，有一个进程挂了整个系统就挂了，因为需要等待所有其他进程的响应，同时对网络的要求也很高。
总结
如果你之前看过2PC，Paxos之类的算法，相信你看到最后一定会有一种似曾相识的感觉。实际上，Lamport提出的逻辑时钟可以说是分布式一致性算法的开山鼻祖，后续的所有分布式算法都有它的影子。我们不能想象现实世界中没有时间，而逻辑时钟定义了分布式系统里面的时间概念，解决了分布式系统中区分事件发生的时序问题。