谭浩的博客

Simple is beauty.

分布式系统——时序、时间和逻辑时钟

时序

时序是一种描述程序的正确性的简单方法(程序执行结果和在单机上的相同)。然而实际上一个分布式程序运行在多个节点上,需要绝对精确的时间或者某种形式的通信才能定义所有操作的全序关系。

全序和偏序

全序是一种二元关系,它定义了一个集合中每一个元素的顺序;偏序集合中只有部分元素可以相互比较,不能为每一个元素确定顺序。

全序和偏序都具有传递性和反对称性。

1
2
If a ≤ b and b ≤ a then a = b (antisymmetry);
If a ≤ b and b ≤ c then a ≤ c (transitivity);

全序具有完全性,即集合中任意两个元素是可以进行比较;偏序则只具有自反性,即集合中的任意元素a有a <= a。

git分支的偏序关系

git允许我们从一个主分支上创建多个分支。如下例中分支A和分支B来自共同的祖先,但是分支A和分支B之间不能定义一个明确的顺序(例如branch A (1,1,0) 和 branch B (1,0,1) ),他们代表着不同的版本历史。

1
2
3
[ branch A (1,2,0)]  [ master (3,0,0) ]  [ branch B (1,0,2) ]
[ branch A (1,1,0)] [ master (2,0,0) ] [ branch B (1,0,1) ]
\ [ master (1,0,0) ] /

时间

时序对于验证分布式程序的正确性至关重要,而时间正是时序的源头。通过给没有排序的操作记录时间戳最终能够定义操作顺序,但是这需要精确的时间,并不是任何地方的时间都是以相同的速度发展的。

  • 石英振荡器对温度、震动、辐射敏感
  • 网络消息可能异步到达甚至可能出现丢失的情况

时间同步

最简单的方案是考虑存在一个精确的时间服务器,各节点通过RPC请求获取时间。但是这个方案没有考虑网络延迟,消息延迟将导致服务器返回的答案过期。

  • Cristian’s algorithm
  1. 客户端发送请求数据包,并以其本地时钟T1加上时间戳
  2. 服务器以本地时钟T2记录收到了请求
  3. 服务器发送一个响应数据包及其本地时钟T3和T2
  4. 客户端收到响应数据,记录本地时间戳T4

因为两次传输延迟大致相等,则可以计算得到收到响应时的服务器时间。

  • Berkeley algorithm

单个时间服务器可能会出现故障,导致获取时间被阻塞。Berkeley算法是一种分布式算法。

  1. 假设所有的机器都有几乎精确的本地时钟
  2. 获取参与机器的时钟平均值并同步时钟

(a)时间守护程序向所有其他机器询问时间值 (使用Cristian’s algorithm)

(b)其他机器作出应答

(c)时间守护程序通知每台机器调整它们的时间

逻辑时钟

1978年Leslie Lamport提出了逻辑时钟,我们不需要关注精确的时间,时间之间的”happens before”关系才是真正需要关注的。

happens before(->)的定义:

  • 在同一个 Process 内部,如果事件 a 早于事件 b 发生,称为 a->b;
  • 如果 a 和 b 是两个不同 Process 的事件,且 b 是 a 发送的消息的接收者,同样 a->b;
  • 如果 a->b,b->c,那么 a->c。

Lamport Clock为每一个事件记录一个时间戳,如果a->b,则有C(a) < C(b)。

Lamport Clock算法

  1. 每个 Process 存在独立的事件序列发生器,每次产生新的事件,该序列发生器自增 1,并将结果赋予该事件;

  2. 如果 Process 的事件 b 需要向其他 Process 发送消息 M,那么在 M 中携带 b 的序列号;

  3. 如果 Process 收到外部消息 M,获取 M 中携带的序列号,与自身的事件序列发生器取最大值,然后自增 1,赋给由于 M 而触发的新的外部事件。

向量时钟

因为Lamport 时间戳不能捕获因果关系,所以Lamport Clock 可以保证a->b => C(a) < C(b), 但且不能保证C(a) < C(b) => a -> b。

向量时钟是一个整数向量,向量中的每一个元素代表一个进程,向量初始化为[0, 0, 0, 0…, 0]。每一个进程Pi维护一个向量时钟VC,VCi[i]代表本地进程时间戳,VCi[j]代表进程i了解的进程j上的最新事件。

更新规则:

  • 执行命令和发送消息之前将VCi[i]加1
  • 每一个消息包含了发送消息进程的向量时钟
  • 进程i接收到进程j的消息之后,更新VC,VCi[i] += 1; VCi[k] = max {VCi[k], VCj[K]} 1<= k <= n k!= i。

向量时钟的比较:

  • VCa = VCb when VCa[k] = VCb[k] for all k
  • VCa < VCb when VCa[k] < = VCb[k] for all k and VCa != VC[b]

因此向量时钟可以捕获因果关系,对于任意事件a,b,当VCa < VCb时有a ->b。