Vector Clock

Vector Clock是用来捕捉同一不同版本的对象的因果关系的一种算法。根据Dyanmo paper的描述,矢量时钟实际上是一个(node,counter)对列表(即(节点,计数器)列表)。矢量时钟是与每个对象的每个版本相关联。通过审查其向量时钟,我们可以判断一个对象的两个版本是平行分枝或有因果顺序。如果第一个时钟对象上的计数器在第二个时钟对象上小于或等于其他所有节点的计数器,那么第一个是第二个的祖先,可以被人忽略。否则,这两个变化被认为是冲突,并要求协调。

Vector Clock是逻辑时钟的一种实现方式 搜索 ,最早这个概念由Leslie Lamport (神一般的存在,最近一次图灵奖得主)在1978年发表的一篇论文《Time, Clocks, and the Ordering of Events in a Distributed System》(http://research.microsoft.com/en-us/um/people/lamport/pubs/time-clocks.pdf)提出的,目的是在不依赖于物理时钟确定在离散系统中各个events的发生次序(文中称为happen-before),并且基于这种两两event之间的先后次序推导出多个process上发生的各个event的整体次序关系(Total Ordering)。所以这种逻辑时钟实现同步的方式也叫Lamport Timestamp,区别于物理timestamp。

1. 概述

Vector_Clock.svg

2. 示例

上述说法有些抽象,举个例子:

2.1. W=1,R=3

2.2. W=2,R=2

微信在使用vector Clock的时候采用了简单的递增序列号来定义先后顺序。也可以用时间戳等。根据不同的业务需求可以自定义计算矢量关系的表示方法。

3. Reference


CategoryAlgorithm

MainWiki: Vector_Clock (last edited 2015-04-23 17:09:10 by twotwo)