现在的位置: 首页 > 综合 > 正文

对Vector+Clock算法的理解

2013年06月29日 ⁄ 综合 ⁄ 共 566字 ⁄ 字号 评论关闭

VectorClock算法(也称为Version Vector)是最为常见的用来进行副本管理和冲突发现的算法。

该算法使用所含元素个数与副本节点数相等的数组来记录每个数据对象在不同副本节点的变化。

每一个副本节点Si对应数组中的一个元素i,每个元素有一个计数器,用来记录在副本节点Si上对数据对象的变更次数。

对于每一个数据对象各个副本节点都有一个版本向量。如某个副本节点对某个数据对象存在如下版本向量{{1,1},{2,5}},版本向量的每个元素为{副本节点标示,变化计数器},故{{1,1},{2,5}}表示:副本节点1进行了1次修改,副本节点2进行了5次修改。

当进行两个数据对象同步时,通过比较两个版本向量来发现冲突。

如版本向量V1,V2。当V1中的每个元素的变化计数器的值都大于等于V2中对应元素的值, V1向量表示的数据对象较V2向量新,将V1向量表示的数据同步到V2上。

如果V1中有的元素变化计数器值小于V2中对应元素,有的元素变化计数器值大于V2,则更新冲突。

因Vector Clock算法需维护一个副本节点数长度的版本向量,造成对节点的动态加入不灵活,以及当副本节点不断增长时,进行副本管理的数据量也会不断增长。

为此Ratner[等人为减少副本管理的空间消耗,提出移除没有区分能力的节点信息,基于局部理论动态保存热点节点的方法。

抱歉!评论已关闭.