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

是不是有点晕？为了理解，自己举了个例子：

现在有个手机商城，里面卖的iphone价格是瞬息万变的，有全国各地好几个编辑不停地更新自己那边iphone的价格。当然同时也不断有用户询问当前iphone的价格。

假设该商城有A、B、C三个node，则我们的N是3。

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

1. 首先A收到了iphone价格是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说iphone又涨了，变成了5000块，那么B上就有了5000[A:2,B:1]
5. 在B上这个价格被复制到A，C之前，又有个请求到C说iphone降价了，变成了3000块！

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

三个node上数据全不一致！！！有点儿乱啊~

根据墨菲定律——最不想发生的事情发生了——这时有人询问iphone的价格。

看看vector clock这时能起到什么作用？

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

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

既 然已经有了结论，那就不能让之后的客户端再这么纠结，接下来就是要统一各个节点，合并vector clock。这时候要做的事情就是通知A节点，现在iphone价格是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说iphone又涨了，变成了5000块，那么B上就有了5000[A:2,B:1] 同1理，C上有了5000[A:2,B:1]
5. 又 有个请求到C说iphone降价了，变成了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]。

这时读请求过来我们还纠结吗？虽然R=2，但无论我们读哪两个，都将得到5000这个价格，因为显然[A:2,B:1,C:1]要比[A:2,B:1]的更新鲜。上面这番折腾在W=2的情况下不需要协调。

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

关于向量时钟一个可能的问题是，如果许多服务器协调对一个对象的写，向量时钟的大小可能会增长。实际上，这是不太可能的，因为写入通常是由首选列表中的前 N个节点中的一个节点处理。在网络分裂或多个服务器故障时，写请求可能会被不是首选列表中的前N个节点中的一个处理的，因此会导致矢量时钟的大小增长。在 这种情况下，值得限制向量时钟的大小。为此，Dynamo采用了以下时钟截断方案：伴随着每个(节点，计数器)对，Dynamo存储一个时间戳表示最后一 次更新的时间。当向量时钟中(节点，计数器)对的数目达到一个阈值(如10)，最早的一对将从时钟中删除。显然，这个截断方案会导至在协调时效率低下，因为后代关系不能准确得到。不过，这个问题还没有出现在生产环境，因此这个问题没有得到彻底研究。