uncategorized

Vector Clock

在一些分布式数据库中,如Dynamo,Project Voldemort,为了控制同一record的不同版本,常常会使用Vector Clock这样的概念。

向量时钟(vector clock)实际上是一个(node,counter)对列表(即(节点,计数器)列表)。 矢量锁是与每个对象的每个版本相关联。通过审查其向量时钟,我们可以判断一个对象的两个版本是平行分枝或有因果顺序。如果第一个时钟对象上的计数器在第二个时钟对象上小于或等于其他所有节点的计数器,那么第一个是第二个的祖先,可以被人忽略。否则,这两个变化被认为是冲突,并要求协调。例如假设该集群有A、B、C三个node,则我们的N是3。

我们先看看只写一份W=1,那么根据W+R>N有R=3。那么就有如下场景:

  1. 首先A将数据修改为4000。我们有了4000[A:1];
  2. 在数据被复制到B,C之前,A又把数据变成了4500.那么A上就有了4500[A:2],它覆盖了之前的[A:1]
  3. 随后这个数据被传到了B,C。那么B,C上也有了4500[A:2].
  4. 此时,B把数据修改为5000,那么B上就有了5000[A:2,B:1]
  5. 在B上的数据被复制到A,C之前,C又把数据该成了3000

经过上面这么一番折腾,C上有了3000[A:2,C:1],此时A上是4500[A:2],B上则是5000[A:2,B:1]。

三个node上数据全不一致!!!那如果这个时候有个D想查这条数据怎么办?看看vectorclock这时能起到什么作用?

由于我们的R=3,所以这三个节点上的数据都会被读到,那么4500、5000和3000哪个被返回呢?显而易见,A上的版本最低,应被舍弃,那么B和C呢?

D拿到3000[A:2,C:1]和5000[A:2,B:1]确实有点手足无措,但我们可以让它有个判断依据——比如时间戳——现在客户端看到B上的数据是最新的,那么结论就是5000.

既然已经有了结论,那就不能让之后的客户端再这么纠结,接下来就是要统一各个节点,合并vectorclock。这时候要做的事情就是通知A,现在数据是5000以及得到5000这个值所基于的vector clock。这样A上的数据就变成了5000[A:3,C:1, B:1]. 这样,再有读请求的话,我们可以毫不犹豫的选择A上的数据。

我们看看如果W=2,R=2的情况:

  1. A收到4000,但是只有这个数据也到达B,才算成功。所以我们有了A上的4000[A:1]和B上的4000[A:1]
  2. 在被复制到C之前,A把数据库改成了4500. 同上A和B上都会有4500[A:2]
  3. 数据被复制到C,C上也有了4500[A:2]
  4. 此时,B需要更新数据位5000,那么B上就有了5000[A:2,B:1]同1理,C上有了5000[A:2,B:1]
  5. 然后C又需要更新数据到3000!那么C上应该有3000[A:2,B:1,C:1].同1理,新数据的写也会到达A,A上的4500[A:2]看到3000[A:2,B:1,C:1]后,无条件接受被覆盖,因此也变成了3000[A:2,B:1,C:1]。

经过上面这么一番折腾,C上有了3000[A:2,B:1,C:1],此时A上是3000[A:2,B:1,C:1],B上则是5000[A:2,B:1]。这时D读取该数据库就不用纠结了。因为R=2,无论我们读哪两个,都将得到5000这个价格。

由此我们也可以看出提高W可以降低冲突,提高一致性。但代价也是显然的:写两份显然比写一份要慢,并且同时能写成功的概率也变低了——也就是Availability降低。