Vector Clock/Version Clock

2023-10-11 21:44:04

physical clock

机器上的物理时钟，不同的机器在同一个时间点取到的physical clock不一样，之间会存在一定的误差，NTP可以用来控制这个误差，同一个机房内的机器之间的时钟误差可以控制在1us以内，
跨机房可以控制在几十ms。两个事件a和b，a在机器M1上physical clock为12点5分0秒6ms发生，b在机器M2上physical clock为12点5分0秒7ms发生，这并不代表a发生在b之前，因为两个机器上取到的physical clock和真实时间(这个时间就是国际标准时间UTC，可以通过原子钟，internet，卫星获得)之间都有误差。比如机器M1的physical clock比真实时间慢10ms，那么事件a实际上是在真实时间12点5分0秒16ms发生的，机器M2的physical clock比真实事件慢5ms，那么事件b的实际上是在真实时间12点5分0秒12ms发生的，显然，事件a发生在事件b之后。

Lamport's Logical Clock

单机系统容易给发生的所有事件定义一个全局顺序(total order)，但是分布式系统没有全局时钟，很难给所有事件定义一个全局顺序。所以，Lamport定义了一种偏序关系，happens-before.记作 ->

a->b意味着所有的进程都agree事件a发生在事件b之前。

在三种情况下，可以很容易的得到这个关系：

如果事件a和事件b是同一个进程中的并且事件a发生在事件b前面，那么a->b
如果进程A发送一条消息m给进程B，a代表进程A发送消息m的事件，b代表进程B接收消息m的事件，那么a->b(由于消息的传递需要时间)
->满足传递性，如果a->b AND b->c => a->c

Lamport's Logical Clock算法如下：

每个机器本地维护一个logical clock LC_i
每个机器本地每发生一个事件设置LC_i = LC_i + 1，并且把结果作为这个事件的logical clock。
当机器i给机器j发送消息m时，把LC_i存在消息里。
当机器j收到消息m时候，LC_j = max(LC_j, m timestamp)+1，结果值作为收到消息m这个事件的时间戳。

这个算法能够保证a->b，那么a事件的logical clock比b事件的logical clock小。反过来，通过只比较两个事件的logical clock不能得到a和b的先后。

Vector Clock

每个机器维护一个向量VC，也就是Vector Clock，这个向量VC有如下属性：

VC_i[i] 是到目前为止机器i上发生的事件的个数
VC_i[k] 是机器i知道的机器k发生的事件的个数(即机器i对机器j的知识)

每个机器都有一个向量(Vector)，每个向量中的元素都是一个logical clock，所以取名为Vector Clock。

通过如下算法更新Vector Clock

机器i本地发生一个事件时将VC_i[i]加1
机器i给机器j发送消息m时，将整个VC_i存在消息内
机器j收到消息m时，VC_j[k]=max(VC_j[k],VC_i[k]),同时，VC_j[j]+1

可以看出，Vector Clock是一种maintain因果关系(causality)的一种手段，Vector Clock在机器之间传递达到给对方传递自己已有的关于其他机器知识的目的。

Dynamo为什么需要Vector Clock(实际上是Version Clock)

Dynamo是一个分布式Key/Value存储系统，这个Value可以是一行，包含多个列，为了容错，每个Key/Value保存多副本，通常在不同的机器上，一般是3，后面以3为例。对外是一个最终一致性系统，即客户端A写入一个值返回成功后，在一定的时间内另外一个客户端可能读不到最新的值。通常，成功写入两个副本成功即返回给客户端成功，同时请求会异步的同步到第三个副本。然而，高可用是Dynamo的主要设计目标之一，即使在出现网络分区或者机器宕机时依然可读可写。

假设Key K有三个副本k1,k2,k3分别在M1，M2，M3上。

正常情况

M1处理写请求，M1将请求发往M2，M3，只要有一个返回，即返回客户端成功。

网络分区

如果M1和M2/M3之间网络都不通，k1被更新(持续高可用，依然给客户端返回成功)，随后，其他节点(集群中任意一个节点都可以接客户端请求，并且将请求路由到正确的节点上)路由了写请求给M2(假设其他节点和M1/M3之间网络不通)，k2被更新。这时，k1和k2数据不一样，最后网络恢复，三个副本进行同步时，应该保留哪个版本？如果只保留k2，即采用last write win机制，那么同步后，第一个客户端会发现它写的数据丢了。

这个时候就需要Vector Clock，更确切的说是Version Clock。

为了处理这种场景，Dynamo使用Version Clock来捕获同一个Object的不同版本之间的causality。每个Object的每个版本会有一个相关联的Version Clock, 形如[(serverA,counter),(serverB,counter),...], 通过检查同一个Object不同版本的Version Clock，可以决定是否可以完全丢弃一个版本，仅保留另外一个版本，还是需要将两个版本进行merge。如果Object的版本A的VC_A包含的每项(server, counter)在版本B的VC_B中都有对应项，并且counter小于等于版本B中对应项的counter(记作VC_Bdescends VC_A)，那么这个Object的版本A可以被丢弃，否则需要对两个版本进行merge。

回到刚才的例子，k1被更新，Version Clock(注:此处假设k1/k2/k3三个副本之前一模一样，那么就可以省略之前的Version Clock)为[(M1,1)],k2被更新,Version Clock为[(M2,1)]，随后k1/k2网络通了，他们通过比较两个Version Clock发现两个Version Clock存在冲突，不是descends的关系，那么就两个版本都保留，当客户端来读Key K的时候，两个版本的数据和对应的VC都返回给客户端，由客户端进行冲突合并，客户端进行冲突合并后写入Key K的时候，带着合并后的VC[(M1, 1), [M2, 1]]发到M1/M2，覆盖服务器版本，冲突解决。

可以看出，Vector Clock最初是为了给分布式系统的事件定序发明的，本质上是一种捕获causality的手段，只是他们捕获的是事件的关系。而Version Clock是捕获同一个数据的不同版本之间的causality.

Riak这个系统也使用了Vector Clock来做冲突合并，对Vector Clock的用法可谓比较深入，具体可以看最后两篇参考资料。