Time-2-LamportClock

时间的误差

NTP协议存在误差，所以不能通过机器上的本地时间来确定顺序。Lamport逻辑时钟是解决这个问题的方法之一，这个方法是Lamport老爷子在1978年的论文《Time, Clocks, and the Ordering of Events in a Distributed System》提出的。

为什么需要顺序

首先解释下为什么分布式系统需要知道事件的先后顺序。举个🌰：分布式数据库中不同事务并发执行的时候，需要做事务隔离。隔离的一种做法是使用MVCC（Multiple Version Concurrent Control）多版本并发控制，根据数据的版本号来控制该版本数据的可见性。这时候就需要知道数据修改事件的先后顺序才能正确的实现隔离性。

偏序和全序

在介绍Lamport逻辑时钟前，需要先介绍两个数学概念：偏序（partial order）和全序（total order）。

偏序和全序是数学序理论中的概念，主要指集合中元素的顺序关系。

偏序的定义如下：

给定集合S，”≤“是S上的二元关系，若”≤“满足：

自反性：∀a∈S，有a≤a；

反对称性：∀a，b∈S，a≤b且b≤a，则a=b；

传递性：∀a，b，c∈S，a≤b且b≤c，则a≤c；

则称”≤“是S上的非严格偏序或者自反偏序。

偏序定规中最重要的是传递性，如果a < b并且b < c，则a < c。

全序和偏序相比，多了一个完全性，全序定义如下：

全序关系即集合上的反对称的、传递和完全的二元关系（一般称其为 ≤)。

若X满足全序关系，则下列陈述对于X中的所有a,b和c成立：

反对称性：若a ≤ b且b ≤ a，则 a=b；

传递性：若a ≤ b且b ≤ c则a ≤ c；

完全性：a ≤ b或b ≤ a

简单的说，偏序的意思是说集合中的元素是部分有序的，而全序的意思是集合中任意一对元素都是可以相互比较的，可以完全排序。

下面是一些例子：

自然数的集合是全序
整数的集合是全序。
复数的集合是偏序，1和100i是无法比较的，没有意义。

对于分布式系统来说，我们想知道事件的先后顺序，实际上就是希望创建一种全序的关系来描述事件的顺序。

Lamport逻辑时钟算法

既然物理时钟不可靠，那就人为构造一个递增的序列来为事件排序，这就是Lamport逻辑时钟的基本思想。

首先需要定义先后关系（happened before），我把事件a发生在b之前定义为a → b。以下下三种条件都满足a → b：

a和b是同一个进程内的事件，a发生在b之前，则a → b。
a和b在不同的进程中，a是发送进程内的发送的发送事件，b是同一消息接收进程内的接收事件，则a → b。
如果a → b并且b → c，则a → c。

如果a和b没有先后关系，则称两个事件是并发的，计作 a || b。

图1

上图中，有两个进程A和B，每个点表示一个事件，黑色点表示进程内的事件，蓝色点表示进程的发送消息事件，红色点表示进程的接收消息事件。可以从上图得出：

a → b → c → d
a → b → e
f → c → d
a || f
e || d
b || f
e || c

a → b除了可以表示两个事件的先后关系，也可以理解为两个事件的因果关系，a事件导致了b事件的发生，或者说a事件影响了b事件，而a || b也可以理解为两个事件没有因果关系，比如上图中，e和c两个事件就像是从b开始发展出了两个平行世界，相互不再受对方的影响。

我们引入逻辑时钟算法：

Lamport逻辑时钟算法

分布式系统中每个进程Pi保存一个本地逻辑时钟值Ci，Ci(a)表示进程Pi发生事件a时的逻辑时钟值，Ci的更新算法如下：

进程Pi每发生一次事件，Ci + 1；
进程Pi给进程Pj发送消息，需要带上自己的本地逻辑时钟Ci；
进程Pj接收消息，更新Cj = max(Ci, Cj) + 1。

图一的逻辑时钟值如下：

图2

从以上算法可以很容易得出下面两个结论：

同一进程内的两个事件a和b，如果a → b，那么Ci(a) < Ci(b)；
a是Pi进程的消息发送事件，b是Pj进程该消息的接收事件，那么Ci(a) < Cj(b)。

由以上两个结论又可以得出：

对于任意两个事件a和b，如果a → b，那么C(a) < C(b)。

问题来了，如果C(a) < C(b)，那么可以得出a → b吗？

答案是不能，举个反例，图二中C(e) = 2，C(d) = 3，虽然C(e) < C(d)，但并不能得出e → d，e和d实际上是并发关系e || d，也就是说由于并发的存在，导致反向的推论并不成立。

全序事件集

上面介绍的逻辑时钟算法构造的整个事件集合（happened before →）是一种偏序关系，只有部分事件可以比较大小。我们可以加入另外一个条件也就是判断两个进程号的大小，可以使整个事件集合变成一种全序关系。

定义全序 ⇒ 关系如下：Pi进程的事件a和Pj进程的事件b如果满足下面两个关系中的任何一个，则称a ⇒ b。

Ci(a) < Cj(b)；
Ci(a) = Cj(b) 并且Pi < Pj。

全序关系 ⇒ 把偏序关系 → 变成了任何两个元素都可比较的全序关系，而且有a → b，则a ⇒ b。

图二中假设A进程号为1，B进程为2，事件的全序关系如下：a ⇒ f ⇒ b ⇒ e ⇒ c ⇒ d。

图3

注意即使物理事件上e发生于d之后，但由于两个事件没有因果关系，所以排序时没有按照物理事件顺序也不会有问题。

真·分布式锁

全序关系 ⇒ 有什么用呢？

在论文中，Lamport老爷子举了一个分布式锁的例子来描述 ⇒ 的作用。这个分布式锁需要满足以下要求：

获得锁的进程必须释放锁后，其他进程才能获得锁，也就是一个互斥锁。
不同进程获得锁的顺序必须和请求的顺序一致。
如果每个进程最终都会释放锁，那么所有的进程发出的锁请求最终都能满足。

在常见的分布式锁实现中，大都有一个中心服务器来控制锁的获取和释放，但是中心服务器很容易遇到网络延迟问题导致违反要求2，举例如下：

图4

P0是中心进程，P1发送锁请求给P0，然后P1发送消息给P2，P2收到消息后，给P0也发送了锁请求，但是由于网络原因，P2的请求比P1的请求先到P0，导致P2先获得了锁。

Lamport老爷子提供了一种方案来解决这个问题，这种方案不需要中心服务器，可以说是真·分布式锁。方案中，每个进程保存了本地逻辑时钟 Ti，它的更新算法和前文介绍的Lamport逻辑时钟一样，同时保存了一个队列，队列中的每个元素是 Tm : Pi 。Tm 是消息发送时的本地逻辑时钟，Pi 是进程i的进程号。方案有个前提条件是两个进程间的消息可以有延迟，但最终一定能送达，而且两个进程间的消息是保序的。

Lamport真·分布式锁

如果进程 Pi 需要获取锁，发送 Tm : Pi 消息给所有其他进程。
进程Pj收到锁请求消息后，将 Tm : Pi 放入本地队列中，更新本地逻辑时钟 Tj，然后回复一个带 Tj 的 ACK 消息给 Pi 。
当以下两个条件满足时，进程 Pi 获得锁：

3.1 按照全序关系 ⇒ 排序后， Tm : Pi 在本地队列的队首。

3.2 进程 Pi 收到过其他进程发来的消息，消息中的时钟 Tj 大于 Tm 。
如果进程 Pi 需要释放锁，先从本地队列中移除 Tm : Pi ，然后给其他所有进程发送锁释放消息，消息中带上当前时钟 Ti 。
进程 Pj 收到锁释放消息后，从本地队列中移除 Tm : Pi 。

举个例子来描述：

图5

上图有三个进程P0, P1和P2。图中每个节点上的文字第一行数字表示本地逻辑时钟Ti，第二行方括号表示本地队列，第三行的字母表示节点名字。

首先P0发出获取锁请求给P1和P2，消息内容为[1:0]。
P1和P2收到后，返回ACK给P0，并带上各自的本地逻辑时钟值。
P0在g节点收齐ACK后，发现满足算法第3条中的两个条件，自己获得了锁。
P1在h节点也想获取锁，发送锁请求给P0和P2，消息内容为[4:1]。同时把[4:1]也插入本地队列中，但全序排序后，[1:0] < [4:1]，所以[4:1]排在[1:0]后面。
P0和P2收到后，返回ACK给P0，并带上各自的本地逻辑时钟。
P1在n节点收齐ACK后，虽然满足条件3.2，但不满足条件3.1，[4:1]没有排在队列的队首，还未获得锁。
P0释放锁，发送释放请求给P1和P2。
P1和P2收到释放锁请求后，把[1:0]从本地队列中删除。
P1发现此时[4:1]排在队首，满足条件，获得锁。

条件3.2中为什么要收到过Tj大于Tm的消息才行，如果Tj小于Tm能不能行？

答案是不能，因为Pi收到过其他进程发来的消息，说明Pi知道了其他进程的请求状态，如果其他进程发来的是加锁请求，并且Tj小于Tm，如果Pi此时认为自己获取锁，就和条件3.1矛盾了，[Tm:Pi]并没有排在队列的首部。

条件3.2中Pi收到过其他进程的消息，说明Pi知道了其他进程的请求状态，Tj 大于 Tm说明如果没有其他进程已经加锁的情况下，[Tm:Pi]排在队首。条件3.1说明当前没有其他进程加锁，综合这两个条件说明Pi获得锁。

再举个竞争条件的例子：