前言

在分布式系统中,如何确定两个事件发生的先后顺序是比较困难的。在不同机器上的物理时钟会有会有误差。Lamport在1978的文章Time, Clocks and the Ordering of Events in a Distributed System” (1978)提出了一种Logical Clock 来描述分布式系统中的先后顺序。论文中先是定义了一种偏序的happened before 关系,通过这种关系给出了logical clock的算法,最后用logical clock实现了全序的分布式算法。

Happened-before

Lamport提出用事件发生的先后因果关系来描述事件。若事件b依赖于a发生,则a happened-before b。定义如下。

  1. If a and b are events in the same process, and a comes before b, then a → b.
  2. If a is the sending of a message by one process and b is the receipt of the same message by another process, then a → b.
  3. if a→ b and b → c then a→c.

若相互之间没有依赖关系,可认为是并行的。并发说明这两个事件谁先发生并不重要,这其实逻辑时钟的重要思想。Logical clock只保证你的系统不出错(即不违反相互依赖关系),而不能保证事件发生的真实顺序。

Logical Clock

Logical Clock就是给事件打上时间戳(一般实现为递增的序号)。如果a happended before b, 那么a的时间戳就要小于b。时间戳的逻辑遵循下面的规则。

  • 在同一个进程中,每发生一个事件则时间戳+1
  • 不同进程中,进程A收到进程B的message, 其中包含B的时间戳为T, 则C(A) = max(T, C(A)) + 1

若a->b, 则C(a) < C(b), 但是反过来并不能成立。在并行的情况,时间戳的大小并不能反映事情发生的先后顺序,因为根本不重要。

Total Ordering

既然并行的情况,事件发生的顺序不重要。为了保证全局的顺序,就强制规定一种顺序,比如说机器编号,机器编号小的时间戳更小。由此,Lamport提出了基于Logical Clock的分布式算法。这个算法基于一个前提,message被一个进程发送给另一个进程,接收到的顺序是按照发出的顺序的。算法如下

首先,每个进程都维护一个request queue。

  1. 假设进程A发送request message(RQ) 给其他进程,包含暑假戳T_rq在message里面。并且将RQ入队
  2. 当其他进程收到R时,进程将RQ入队,并发送ack给进程A(也要包含时间戳)
  3. 当进程A需要release资源的时候,进程A删除在队列里的RQ message,并发送release message(RL)给其它进程
  4. 当收到RL时,进程删除队列里所有来自进程A的RQ

进程A只有满足以下条件才能获取资源:

  1. RQ是队里中的第一个request message,
  2. 进程A收到其它所有进程的message, 其中包含的时间戳>T_rq。

为什么这个算法可以work?通过上述两个条件,我们保证了所有进程都看到了RQ,并且按照前面的算法,RQ是按照Lamport Clock进行排序的。所有进程看到的都是同一个顺序。

这个算法也有一定的局限性,即需要所有进程参与,一旦某个进程挂掉了,整个system就不可用了。

Reference

[1] Time, Clocks and the Ordering of Events in a Distributed System