逻辑时钟

2015-05-28

为什么需要逻辑时钟?

在一个分布式系统中,没有一个全局的物理时钟可以依赖。各个机器上的时间都是不一致的。

happened-before的概念

  1. 在同一台机器上,如果事件A在发生在事件B之前,那么A happened-before B
  2. 假设某台机器上发送消息记为事件A,在另一台机器上收到这条消息记为事件B,那么A happened-before B
  3. 如果无法根据前两条规则判定A happend-before B,那么从逻辑时钟的角度,A和B是"同时发生"的

逻辑时钟就是利用这种事件发生的先后关系来表示时序。每个机器维护一个本地时钟(一个递增的计数器),每发生一个事件,计数器加加。事件可以是本机上的事件,或者收到消息等。如果收到的消息时钟大于本地时钟,则将本地时钟拉到消息时钟值。

如何解决消息时钟和本地时钟的值相等的情况?

为每个机器编号,添加一个机器id。假设机器为P1和P2,相应的本地时钟为C1和C2。那么逻辑时钟用一个对表示(C1,P1)。如果C1<C2,或者C1=C2 && P1<P2,那么(C1,P1) happened-before (C2,P2)。

e1和e2分别是两个事件,C(e1)和C(e2)表示事件发生时的逻辑时钟。若e1事件happened-before事件e2,那么逻辑时钟值C(e1)小于C(e2):

e1->e2 => C(e1)<C(e2)

但是过来不成立,逻辑时钟C(e1)比C(e2)小,不能推出事件e1是happened-before事件e2的。

happened-before跟物理时钟的关系:如果e1是happened-before e2的,那么物理时间e1肯定在e2前面发生。但是反过来却不能成立:即使物理时间上e1发生在e2之前,e1和e2也不一定满足happened-before关系。

理解逻辑时钟的关键,就是理解时间的先后是用事件之间的happened-before关系来表示的。不要让物理时钟的概念影响思维。嗯,就像光年不是时间单位。

vector clock是逻辑时钟的一种形式。每个机器都维护一个向量,而不是单个值。这个向量记录下本地机器所了解的全局时钟信息。

logical clock逻辑时钟