“固定成员下,可让每个副本通过反熵同步确认因果前沿。若版本摘要为Dotted Version Vector或普通版本向量,逐 actor 取所有成员 acknowledgment 的下确界,得…”
形式陈述 ​
Dot 是唯一更新事件
其中
一个 Dotted Version Vector 可写成
向量部分是 causal context,额外 dot 是当前版本的身份。因果包含按所代表事件集合比较:若
一个 DVV 只表达一个连续前缀外加一个例外 dot。若状态有多个洞或多个 live 并发事件,需要 dot set、dot cloud 或先经同步把可连续部分压入前缀,不能让单个 dot 代表任意稀疏集合。合并时可将相邻 dots 折入前缀:已知
墙钟不参与比较。Actor 序号只负责身份唯一,因果来自客户端携带的 context;同一服务器先后接收两个没有共同 context 的请求,它们仍可并发。向量中缺失的 actor 分量统一且明确地按零解释。
直觉
普通版本向量的分量
Dot 像文件的唯一修订号,context 像作者写这版前读过的修订清单。服务器分配序号的现实先后不等于两个客户端相互观察;只有 context 明确包含某 dot,后写才覆盖前写。因果比较不能只看最大 counter:来自不同 actors 的 9 与 12 没有大小语义。
这种分离特别适合 MV-Register:每个候选值携带一个 dot,对象 context 记住已淘汰的 dots。值可删除,因果知识仍能压进连续前缀,阻止迟到版本复活。
例子与边界
事件历史
可表示为
若把它误压成普通向量
再看同一服务器 S 收到两个独立客户端的空 context 写入。它依次分配
两事件集合互不包含,所以它们并发。把第二版写成普通向量
Actor 重启后若把 counter 清零,新的
推论与应用
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.