CRDTS：三角洲州添加-获胜-观察-删除地图

Question

我在这里找到了一篇关于 delta 状态 CRDT 的很好的介绍性文章。

他们的方法使用带有根版本向量的映射，并用“点”列表标记每个key。版本向量是标准的——从副本 id 到版本整数的映射。点代表单个编辑 - 由一对

(replica id, version)

表示。版本向量中的每个条目都总结了一系列编辑或“点”。我在各种研究论文中看到了其他几种方法，它们使用与此非常相似的方法。

为了计算差异，副本会将其根版本向量发送给对等点。对等方将遍历其映射中的每个键，查看每个键的点列表。如果此点列表中的任何点未被传入版本向量“覆盖”，则必须打包与这些点关联的键和值并将其发送到对等点。

CRDT 映射是可组合的，因此可以使用 LWW（最后写入获胜）寄存器、MVV 寄存器、CRDT 集、另一个 CRDT 映射等来实现特定的值。

有三件事我不清楚。

1. 为什么每个键都使用一个点list而不是一个单个点？该文章提到，由于并发写入同一键，因此存在多个点。我们假设该条目是 LWW CRDT。根据我对本文的理解，如果两个副本同时写入该键，则在同步后，每个副本最终都会得到一个包含“两个”点（以及与这些点关联的两个值）的点列表。当读取地图键时，返回与具有最大时间戳的点关联的值。为什么不从一开始就这样做呢？换句话说，为什么不丢弃具有较早时间戳的点并覆盖该值？根版本向量仍然被合并，因此我们知道地图已经合并了其历史记录中早期编辑的更改。我看不出有什么理由这行不通。 点列表是否缩小了？对我来说，似乎每个键的点列表最终都会衰减为完整版本的向量。我的直觉是，当副本进行本地编辑时，它会用一个新点覆盖点列表，但我不确定这一点。
2. 在文章的最后，作者提到：

[在]旧的移除胜利地图中，墓碑是一个点。使用“添加胜利地图”，情况会更加复杂，这就是我下一篇文章的主题！

尚不清楚为什么需要做任何特殊的事情才能获得添加获胜行为。在我看来，集合中的每个元素都将用一个点标记。当发生删除时，该项目会被标记为墓碑和一个点。因为版本向量和点会告诉我们何时发生并发更新和删除，所以我们可以简单地丢弃墓碑。

预先感谢您帮助解决这些问题。

Answer 1

他们用多个点显示的唯一示例实际上是计数器，而不是 LWW 寄存器。传统的基于状态的向量计数器始终存储每个副本的最新点。

1. 对于 LWW 寄存器，他们可能需要存储所有点才能正确处理删除。这绝对是 Add-Wins 删除的情况 [1]，但我不确定他们的 Remove-Wins 删除情况。

我同意，他们似乎正在使用因果覆盖规则（一个新点会覆盖之前的因果点）。否则，我希望每个图中的根包含树中出现的所有因果点。
Add-Wins 移除的传统算法是[2]：

3. 存储所有未被删除的事件的集合，加上全局版本向量。 （正如他们已经在做的那样。）
   • 当您从对等方收到事件时，仅当该事件未包含在您的全局版本向量中时，才将其添加到您的状态中。 （否则，你已经删除了它。）
   • 当您从对等方收到完整状态时，删除远程版本向量包含但不存在于远程状态中的任何事件。 （远程对等点必须目睹其被删除。）
   我想这就是你所得到的；也许作者只是认为它更复杂？或者，可能会出现涉及树结构/差异过程的复杂情况。

[1]“通过发布有缺陷的伪代码来评估分布式算法的可理解性”，Martin Kleppmann，

https://doi.org/10.48456/tr-969

[2]“优化的无冲突复制集”，Annette Bieniusa 等人，

https://arxiv.org/abs/1210.3368