MyBlog

【Paper】Lamport Logical Clock and Vector Clock

last modified: 2021-02-03 12:18

Lamport Logical Clock

Lamport Logical Clock要解决的是，如何判断分布式系统中两个事件a, b的时序。 原理如下：

Lamport Logic Clock

  1. 每个事件贴一个Lamport 时间戳(ts)，初始值为0
  2. 如果事件在节点内发生，本地进程中ts加1
  3. 如果事件属于发送事件，本地进程中ts先加1并在消息中带上该ts
  4. 如果事件属于接收事件，本地进程中ts = Max(本地ts，消息中ts) + 1

上图中，C1 happened before B1，记作：C1->B1， 则C(C1)>C(B1)，C()表示事件的Lamport 时间戳。 由该定义，可以通过比较事件的Lamport 时间戳，获得事件间的Partial order.

值得注意的是，通过C(B4)>C(A3)，并不能推出B4->A3；C(a)>C(b)是a->b的必要不充分条件。

当C(A3)=C(B5)，即Lamport 时间戳相等时，其实表示A3和B5一定不存在因果关系。如果需要整个系统中的事件Total order，则需要指定规则，比如节点或线程等级A>B>C，则C(A3)>C(B5)。

得到Total order: C1, B1, B2, A1, B3, A2, C2, B4, C4, A3, B5, C4, C5, A4

Total order里的因果关系是正确的，但却不能反应同时发生的事件时序情况，比如B5在A3前发生，但在Total order中A3却在B5前。

Vector Clock

Lamport Clock提供了一种，生成分布式系统中事件全序关系的算法。但却不能通过Lamport 时间戳对事件进行因果关系判断。因为C(a)>C(b)是a->b的必要不充分条件。

Vector Clock在Lamport Clock基础上演变而来，基于Vector Clock我们可以判断任意两个事件的因果关系（时序），要么有因果关系（先后发生），要么没有因果关系（同时发生）。

Vector Clock Example of a system of vector clocks. Events in the blue region are the causes leading to event B4, whereas those in the red region are the effects of event B5

假设分布式系统中有N个进程，每个进程都有一个本地的Vector时间戳Ti，Vector Clock算法实现如下：

  1. 对于进程i来说，Ti[i]是进程i本地的Vector时间戳
  2. 当进程i当有新的事件发生时，Ti[i]=Ti[i]+1
  3. 当进程i发送消息时将它的Vector时间戳(MT=Ti)附带在消息中。
  4. 接受消息的进程j更新本地的Vector时间戳：Tj[k]=max(Tj[k], MT[k]) for k = 1 to N。（MT即消息中附带的Vector时间戳）

因果判断逻辑

假设有事件a、b分别在节点P、Q上发生，Vector时间戳分别为Ta、Tb，

  • 如果Tb[Q]>Ta[Q]并且Tb[P]>=Ta[P]，则a->b，认为事件a、b有因果关系
  • 如果Tb[Q]>Ta[Q]并且Tb[P]>Ta[P]，则认为a、b同时发生

上图中节点B上的第4个事件(A:2，B:4，C:1) 与节点C上的第2个事件(B:3，C:2)没有因果关系，属于同时发生事件

Vector Clock的应用

Dynamodb使用Vector clock（Version vector）检测多副本数据冲突，

Dynamodb-vector-clock

D3([Sx,2],[Sy,1],[Sz,0])和D4([Sx,2],[Sy,0],[Sz,1]) 不存在因果关系，因此存在版本冲突。因此Sx返回给Client的数据，会带上Sz,Sy 2个冲突版本的数据，由Client自行解决冲突。