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的事件
client其拿到N1,N2,N3上的向量,通过比較可知,N1上的是旧数据,N2/N3版本号存在冲突,此时须要用户自己去解决冲突

上一篇:ITU-T Technical Paper: QoS 的参数(非常的全,共计88个)


下一篇:json方式的面向对象