关于Delta-state Add-Wins-Observed-Removed Map的三个技术疑问

我找到一篇关于delta-state CRDTs的入门文章，该方案采用带根版本向量的映射，为每个key标记一个dot列表：

• 版本向量：标准结构，是从副本ID到版本整数的映射，每个条目汇总一系列编辑或dot
• dot：代表单次编辑，以(副本ID, 版本)对表示

计算差异的逻辑：副本将自身根版本向量发送给对等节点，对等节点遍历自身映射的每个key，检查其dot列表——若存在未被传入版本向量“覆盖”的dot，就把这些dot关联的key和值打包发送给对方。

该CRDT映射支持可组合性，具体value可基于LWW（最后写入获胜）寄存器、MVV寄存器、CRDT集合、另一CRDT映射等实现。

疑问与解答 #

1. 为何每个key使用dot列表而非单个dot？ #

假设条目为LWW CRDT，两个副本并发写入同一key后，同步时每个副本的dot列表会包含两个dot及对应值；读取时返回时间戳最大的dot关联值。为何不直接丢弃时间戳较早的dot并覆盖值？

这是因为分布式系统中副本同步不是全局原子一致的：根版本向量合并仅代表当前副本知晓了历史编辑，但其他副本可能还未同步到所有变更。如果本地丢弃旧dot，后续与未同步的副本交互时，就无法传递这些历史变更，会导致数据丢失或不一致。

另外，LWW的“最后写入获胜”是读取时的判断逻辑，而非写入时直接删除旧值——分布式场景下无法提前确定哪个是“最终的最后写入”，必须保留所有并发变更，直到所有副本完成同步后，才能安全压缩（这和第二个疑问相关）。

2. dot列表是否会被压缩？ #

是的，dot列表可以被压缩，但需要满足所有副本都已同步这些dot对应的变更，或者当某个key的所有dot都被根版本向量覆盖时，可将dot列表合并为对应的版本向量条目，甚至直接保留最新值+对应版本信息。

本地连续编辑同一个key时，生成的线性dot（比如(副本ID,1)、(副本ID,2)）可以直接压缩为该副本对应的版本号（比如版本2），因为它们没有并发冲突。但如果存在来自其他副本的并发dot，需要保留这些不同的dot，直到所有副本同步完成后再合并压缩。

3. 为何实现Add-Wins行为需要特殊处理？ #

Remove-Wins Map的墓碑用单个dot就能实现，因为移除操作优先级更高：当key的添加和移除并发时，移除获胜，只要标记墓碑的dot，同步时若该墓碑dot未被覆盖，就认为key被移除。

但Add-Wins的逻辑是添加操作优先级高于并发的移除操作，这需要更复杂的处理：

• 若一个key被添加（dot(A,1)），副本B并发移除它（dot(B,1)），按Add-Wins规则应保留该key。但仅用单个墓碑dot无法区分这个移除是在添加之前还是并发的——如果是添加前的移除，应保留墓碑；如果是并发的，需忽略墓碑保留key。
• 因此Add-Wins Map需要跟踪每个key的添加dot集合和移除dot集合，读取或同步时，需判断是否存在未被移除dot覆盖的添加dot：若有则保留key，否则才移除。
• 当多个添加、移除操作交叉并发时，需要更精细的dot对比逻辑，确保添加操作的优先级正确生效，这比Remove-Wins的单一墓碑dot逻辑复杂得多。

内容的提问来源于stack exchange，提问作者widavies