Skip to content

Dotted Version Vector

Dotted Version Vector · DVV · 点式版本向量

用版本向量表示连续因果前缀,并以额外 dot 精确标识前缀之外单个更新事件的逻辑时钟。

条目类型
定义

形式陈述

Dot 是唯一更新事件

d=(a,n),

其中 a 是不可复用的 actor ID,n 是该 actor 分配的持久递增序号。版本向量 v:AN 表示向下闭合前缀

v={(a,k):1kv(a)}.

一个 Dotted Version Vector 可写成 (v,d),代表事件集合

E(v,d)=↓v{d}.

向量部分是 causal context,额外 dot 是当前版本的身份。因果包含按所代表事件集合比较:若 E(x)E(y),则 x 不晚于 y;两边均不包含时并发。实现常把多个版本共享的 context 提到对象级,并保存若干 live dots,语义仍按事件集合解释。

一个 DVV 只表达一个连续前缀外加一个例外 dot。若状态有多个洞或多个 live 并发事件,需要 dot set、dot cloud 或先经同步把可连续部分压入前缀,不能让单个 dot 代表任意稀疏集合。合并时可将相邻 dots 折入前缀:已知 a:1,a:2 且前缀到一,就可提升为 v(a)=2;若只知 a:3,仍必须保留洞。

墙钟不参与比较。Actor 序号只负责身份唯一,因果来自客户端携带的 context;同一服务器先后接收两个没有共同 context 的请求,它们仍可并发。向量中缺失的 actor 分量统一且明确地按零解释。

直觉

普通版本向量的分量 a:7 意味着 a 的第一至第七个事件全都已见,无法表示“只见第七个,没见前六个”。DVV 把完整前缀和一个突出事件分开,既保持向量压缩,又不虚构中间因果。

Dot 像文件的唯一修订号,context 像作者写这版前读过的修订清单。服务器分配序号的现实先后不等于两个客户端相互观察;只有 context 明确包含某 dot,后写才覆盖前写。因果比较不能只看最大 counter:来自不同 actors 的 9 与 12 没有大小语义。

这种分离特别适合 MV-Register:每个候选值携带一个 dot,对象 context 记住已淘汰的 dots。值可删除,因果知识仍能压进连续前缀,阻止迟到版本复活。

例子与边界

事件历史

{a1,a2,b1,c1,c2,c3,c7}

可表示为

v={a2,b1,c3},d=(c,7).

若把它误压成普通向量 {a:2,b:1,c:7},就虚构已经观察 c4,c5,c6。若另有事件 c9 且仍缺 c4c8,单一 DVV 不够,需保存两个 dots 或更一般的 dot cloud。

再看同一服务器 S 收到两个独立客户端的空 context 写入。它依次分配 (S,1)(S,2),得到

(,(S,1)),(,(S,2)).

两事件集合互不包含,所以它们并发。把第二版写成普通向量 {S:2} 会错误声称它观察并覆盖第一版,仅因为序号由同一服务器稍后分配。

Actor 重启后若把 counter 清零,新的 (S,1) 与旧事件碰撞;版本比较可能把两次不同写当同一事件。持久 counter、incarnation ID 或受协调的 epoch 是安全前提。

推论与应用

DVV 让客户端携带紧凑 context,服务器可以准确区分“覆盖已读版本”和“与未知版本并发”。合并后,若已知某 actor 的 dots 构成连续前缀,就可折叠进向量;存在洞时必须保留显式 dots。

用于垃圾回收时,逐成员 acknowledgment 的最小前沿可证明某些 dots 已全局稳定,但这要求成员集完整且旧身份不能重入。DVV 只表达知识,不自动证明谁是“所有成员”。序列化格式还必须规范 actor 身份和 counter 宽度,避免跨语言比较或溢出把不同事件折叠。

参考资料
  • Nuno Preguiça, Carlos Baquero, Paulo Sérgio Almeida, Victor Fonte, and Ricardo Gonçalves, “Dotted Version Vectors: Logical Clocks for Optimistic Replication,” arXiv:1011.5808, 2010.
  • Colin J. Fidge, “Timestamps in Message-Passing Systems That Preserve the Partial Ordering,” Proceedings of the 11th Australian Computer Science Conference, 1988, pp. 56–66.
  • Friedemann Mattern, “Virtual Time and Global States of Distributed Systems,” Parallel and Distributed Algorithms, North-Holland, 1989, pp. 215–226.
关系图谱1 个相邻概念 · 1 类关系

拖动节点调整位置。

显示关系

显示:使用

类型化关系

被这些条目使用