逻辑时钟

逻辑时钟

为什么需要逻辑时钟？

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

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是逻辑时钟的一种形式。每个机器都维护一个向量，而不是单个值。这个向量记录下本地机器所了解的全局时钟信息。

Read full article from 逻辑时钟