data-structures - 使用 2P CRDT 数据结构（例如 2P-set）时，如何释放空间？

Question

2P-set 允许从集合中移除元素，但不允许释放那些移除的元素占用的空间。事实上，删除一个元素会消耗空间，而不是释放它。为 2P 结构释放空间的算法是什么？

我试图了解在实践中我可以使用 CRDT 结构解决哪些问题。如果没有释放空间的方法，2P CRDT 结构在现实世界任务中的用途似乎非常有限。

Answer 1

虽然我不能为 2P-Set 说话——因为我还没有找到它的实际用例。但是通常我们可以应用一些技术：

1. CRDT 使用的元数据压缩：许多 CRDT 最初以非常简单的设计实现，后来经过优化以满足行业标准。这样的例子可以在虚线向量版本OR-Set之上重新实现。在这个实现中，您不需要将删除的元素保留在内存中：相反，我们可以使用最终可以压缩为矢量时钟的点来跟踪添加/删除的元素。在这里，我更详细地描述了这个问题。
2. 一旦不再需要某些副本，修剪可能很有用，例如。因为我们减少了一些节点或者这些节点不再可用。在这种情况下，我们可以将有效负载与元数据合并，就好像它是由另一个副本生成的一样。示例：给定G-Counter用 map{A:1,B:2,C:1}和一个死节点B（它不能再增加其状态）表示，我们可以通过将B的条目合并到 shape{A:3,C:1}来修剪它，从而减小它的大小，同时仍然保留正确的值。问题是剪枝算法必须保证所有副本必须独立地收敛到这个决定中。