Vector Clock理解

背景
最近在重读“Dynamo: Amazon’s Highly Available Key-value Store”（经典好文，推荐！），文章4.4 中聊到了Data Version
为了提高可用性，Dynamo允许“更新”操作异步的传播到其他副本，当出现多个写事件并发执行时，可能会导致系统中出现多个版本的对象。
由于我们无法保证分布式系统中的多个结点的物理时钟是完美同步的，所以通过物理时钟来确定事件的时序是不靠谱的，但我们可以通过基于事件的逻辑时钟来构建部分有序的事件时序集合
Dynamo通过Vector Clock来构建同一对象多个事件的部分有序的时序集合
需要特别说明的是，Vector Clock能解决分布式系统多版本合并的问题，但是对于确实发生冲突的版本，它无法合并，而需要用户自己去做合并
另外，lamport大神写的“Time Clocks and the Ordering of Events in a Distributed System”可以认为是Vector Clock的理论基础，有兴趣同学可以看看

简述
Vector Clock是一个向量，向量的每个分量为（node，count），node即为分布式系统的节点，count为对应节点上的版本，在处理事件前count会对将该值递增，当它需要和其它节点进行同步的时候也会把count带上。
通过比较这些向量的大小，来确定事件发生的顺序。
假如一个向量的所有分享量的count值都小于或等于另一个向量，可以认为后者并前者更"新"
否则，存在冲突

示例

1.“用户A在N1节点上设置x=100”   ------------  节点N1生成向量<(N1,1)>
2.“用户A在N1节点上设置x=200”   ------------  节点N1生成向量<(N1,2)>
3.“N1将x=200传播到N2” -----------  节点N2生成向量<(N1,2)>
4.“N1将x=200传播到N3” -----------   节点N3生成向量<(N1,2)>
5.“用户A在N2节点上设置x=300”   ------------  节点N2生成向量<(N1,2), (N2,1)>
6.“用户B在N3节点上设置x=400”   -----------  节点N3生成向量<(N1,2), (N3,1)>

此时各个节点的向量
N1： <(N1,2)>
N2：<(N1,2), (N2,1)>
N3：<(N1,2), (N3,1)>

插入一个知识点Quorum NRW模型：
N: 复制的节点数量
R: 成功读操作的最小节点数
W: 成功写操作的最小节点数
只需W + R > N，就可以保证强一致性。

此处我们的N=3
当需要高可写的系统时，可以设置W=1 R=3
当需要高可读的系统时，可以设置W=3 R=1

假设此处R=3 W=1
7.有个读x的事件
客户端其拿到N1,N2,N3上的向量，通过比较可知，N1上的是旧数据，N2/N3版本存在冲突，此时需要用户自己去解决冲突

原文地址：http://blog.csdn.net/yfkiss/article/details/39966087