CRDT 墓碑垃圾回收 | Codeboy's Blog

形式陈述

墓碑是“某 add、insert 或版本已经删除”的持久证据。这里先区分两种回收：把显式墓碑压缩进仍能拒绝旧版本的因果摘要，和彻底遗忘该删除的全部证据。后者至少要证明：

删除事件及其全部因果前驱已被当前成员集中所有正确副本持久吸收；
没有仍可加入同步的成员会重新发送被 $t$ 压制的旧状态；
若 $t$ 是结构 anchor，没有已生成但未交付、也没有协议仍允许新生成的操作引用它；
崩溃恢复、备份和新成员引导都从越过该稳定点的 checkpoint 开始。

固定成员下，可让每个副本通过反熵同步确认因果前沿。本页使用为每次 add 和 remove 都分配事件身份的连续前缀确认向量；它与仅为 add 分配 dot 的 OR-Set 摘要不是同一接口。逐 actor 取所有成员持久 acknowledgment 的最小值，得到稳定确认前沿。删除事件的身份及因果时间戳被该前沿支配，才表示删除及前驱均已持久吸收；确认被删 add 的 dot 不代表确认 remove。Dotted Version Vector 也必须先说明记录哪些事件。动态成员还需 epoch、受协调 retirement 或全量重新引导，禁止旧身份携陈旧磁盘状态任意重入。

对RGA，值删除稳定不等于节点可删。Tombstone 可能仍是迟到 insert 的 anchor；只有所有可能引用它的事件已交付，且客户端不能带旧 context 继续创建引用，才能物理删除或用保持遍历位置的稳定重定向替代。

TTL 不是稳定性证明。墙钟到期只说明等待了一段时间，不能证明离线副本、延迟消息和旧备份均已越过删除。上述确认还默认副本非 Byzantine；恶意或损坏节点伪造前沿时，需要认证、校验与另一套故障模型。

直觉

删除证据的任务是反驳旧副本：“你带来的 add 我早已见过并删除。”证据只有在世界上不可能再出现这类旧声明时才可丢弃。所谓“世界”必须由成员协议精确定义，而不是运维人员心中的常用节点列表。

添加身份为 A 的第 5 个事件，删除身份为 B 的第 1 个事件；C 未确认删除时不能丢弃证据，迟到结构引用也会阻止节点回收 — 删除确认与结构引用分别核对

所有成员已接收某事件，只是交付确认；它不自动排除此前生成、仍在途的并发事件。因果稳定更强：在指定节点，此后交付的事件都必须是该事件的因果后继（见参考资料 §5.2，定义 5.1）。结构 CRDT 还要核对引用稳定；节点虽然不可见，仍可能作为迟到操作的 anchor。不能只看本地向量或全体确认的最小值，就宣称所有未来引用已经排除。

垃圾回收因此是分布式协议，不是本地内存优化。单个副本看到 remove 后立即清 tombstone，可能在当前测试中省空间，却把下一次离线重连变成元素复活。

例子与边界

确认添加，不等于确认删除

固定成员 A、B、C，以下向量按 $(A,B,C)$ 排列。A 添加 $x$ ，add dot 为 $d=(A,5)$ ；三者都已持久接收它，向量为 $(5,0,0)$ 。B 随后产生独立删除事件 $r=(B,1)$ ，删除已见 tag 集 $\{d\}$ ，因果时间戳为 $(5,1,0)$ 。A、B 应用删除后，C 仍离线并持有 live pair $(x,d)$ ：

V_A=(5,1,0),\qquad V_B=(5,1,0),\qquad V_C=(5,0,0).

逐分量取最小得到

S=(5,0,0),\qquad S(A)=5\ \text{但}\ S(B)=0<1.

Add 已被全体确认，remove 却没有。若 A、B 丢弃压制 $d$ 的全部证据，再接受 C 的旧状态做集合并， $x$ 就会复活。这里讨论状态同步或可能重放的传输；不能把它与OR-Set页假设的逻辑恰一次因果 effector 交付混为一谈。

保留证据并同步 C 后，三者持久向量都支配 $(5,1,0)$ 。在成员、恢复和旧消息约束成立时，可压缩显式墓碑，但仍须保留拒绝旧 $d$ 的因果上下文或稳定拒绝前沿。事实上，状态型 OR-Set 可先把“已见 $d$ 、live 集无 $d$ ”编码进 causal context，安全替代逐项墓碑；这种表示压缩不必等待全局删除确认，也不等于遗忘全部删除证据。

若还有离线成员 D，不能把它排除在全体确认之外。必须等 D 确认、正式 retire D 并禁止旧身份重入，或要求其按新 epoch 全量引导。已确认的节点也不能从旧备份绕过这些条件恢复。

对 RGA，C 可能已在离线时生成“insert w after deleted x”。即使 x 的 delete 被三者确认，w 尚未交付前物理删 x 会让 anchor 消失。协议需等待操作稳定、保留 x，或把 x 的稳定位置映射到一个不会改变 sibling 顺序的替代 anchor。

推论与应用

安全 GC 可以批量按 stable frontier 删除整段操作日志、payload 与 tombstones，而不必逐对象等待独立确认。批量效率来自共同因果前缀，前提是所有对象使用相同成员 epoch 和持久确认语义。

若系统允许长期离线客户端，常见选择是保留墓碑、限制离线期限，或要求超期客户端丢弃本地状态并全量重新同步。三者是明确的存储—可用性权衡；静默采用超时删除却仍接受任意旧状态，没有一致性证明。备份恢复同样要携带 epoch：从稳定点之前的备份原地恢复，等同一个陈旧副本重新加入，必须被拒绝或重建。

参考资料

Carlos Baquero, Paulo Sérgio Almeida, and Ali Shoker, “Pure Operation-Based Replicated Data Types,” arXiv:1710.04469, 2017，§5.2，定义 5.1；因果稳定强于全体交付确认。
Hyun-Gul Roh et al., “Replicated Abstract Data Types: Building Blocks for Collaborative Applications,” Journal of Parallel and Distributed Computing 71(3), 2011, pp. 354–368.
Annette Bieniusa et al., “An Optimized Conflict-Free Replicated Set,” arXiv:1210.3368, 2012，§4、图 2；其 add 向量不可直接当作删除事件的确认向量。

形式陈述 ​

确认添加，不等于确认删除 ​

反向链接

形式陈述

确认添加，不等于确认删除