硬核的分布式概念,有关时间时钟问题和算法的问题( 五 )


V[myId
 = V[myId
 + 1send(message V);

收到消息:
(message Vr) = receive();
for (i v) in Vr {    V[i
 = max(V[i
 v);
V[myId
 = V[myId
 + 1;[/i
[/i


该算法在1988年描述 , 后来在Dynamo论文中描述了使用矢量时钟在数据库中进行冲突解决 。
(与前面逻辑时钟计数器不同的是 , 向量时钟是逻辑时钟的列表 , 比如Alice[00
, 前面一个0是Alice的时间 , 后面的是Bob时间) , Alice通过这种列表跟踪她自己的时间计数器以及Bob的最后已知时间计数器 。 这样 , 当Alice向Bob发送消息时 , 他更新了他的计数器Alice[10
, 并且在冲突解决期间选择发送到数据库的下一个消息 , 而Bob的时间向量的每个分量都大于前一个向量的相应分量 。

【硬核的分布式概念,有关时间时钟问题和算法的问题】当存在真正的冲突时 , 矢量时钟可以帮助确定事件是否真正并发 。
比如两个节点都收到[0 1
和[0 1
, 这两个事件不能排序 , 在这种情况下 , 数据库可以保留这两个值 , 并在下次读取时返回它们 , 让Alice或Bob决定保留哪个值 , 以便数据不会丢失 。
但是 , 这些属性并非免费提供 。 需要与每条消息交换元数据 , 并且需要存储多个版本 。 毕竟 , 像Cassandra这样的一些数据库不会出于某种原因使用矢量时钟 。

推荐阅读