Replicated Growable Array | Codeboy's Blog

形式陈述

RGA 把序列表示为带永久身份的节点，而不是可变数组下标。每个节点包含

(\mathrm{id},\mathrm{value},\mathrm{anchor},\mathrm{visible}),

另有永不删除的头哨兵 $\mathsf{HEAD}$ 。Insert 操作指定已经存在的 anchor，并创建全局唯一、全序可比较的 ID，例如 $(\text{logical counter},\text{replica ID})$ 。因果交付保证 insert anchor 的操作先于依赖它的新 insert 到达；重复消息按 ID 去重。

对同一 anchor 的并发 children，所有副本使用相同 ID 顺序。本文采用 RGA 常见约定：较大 ID 更靠近 anchor；再按插入树的确定深度优先规则展开 descendants。局部“第 $k$ 个位置”只在 prepare 时解析成 anchor ID，不能在远端重新按当时数组下标解释。仅把所有节点按 ID 全局排序也不对：anchor 关系决定主结构，ID 只打破同 anchor 的并发 sibling 冲突。

Delete 指向目标 ID，把 $\mathrm{visible}$ 设为 false，而不立即物理移除节点。Query 按确定遍历顺序输出 visible values，跳过 tombstone 的值却继续沿其结构位置访问 descendants。删除操作因果后于目标 insert，因此每个副本执行时都认识该 ID。

安全压缩由CRDT 墓碑垃圾回收另行证明；仅知道值已删除，不足以证明节点不再是未来操作的 anchor。

直觉

数组下标会随他人插入漂移。RGA 让编辑说“把新字符放在我看到的节点 x 后面”，x 的稳定 ID 在所有副本都指向同一结构位置。若多人同时在 x 后插入，ID tie-break 给出统一 sibling 次序，无需猜测谁的网络包先到。

墓碑像被擦掉文字留下的定位孔。用户看不见它，但另一个离线用户可能已经以它为 anchor 创建后继；保留孔位使迟到操作仍能找到正确位置。物理删除若没有重定向，会把结构语义变成消息时序语义。

RGA 保证副本收敛，不保证所有并发编辑都符合人的意图。两个用户在同一句中不同语义位置输入字符，确定顺序可能读起来别扭；应用仍需光标模型、事务分组或语义层处理。

例子与边界

初态只有 HEAD。A 插入 x，ID 为 $(1,A)$ 、anchor 为 HEAD。A 的操作到达 B、C 后，B 与 C 并发在 x 后插入：

y:\ \mathrm{id}=(2,B),\qquad z:\ \mathrm{id}=(2,C).

设 $B<C$ ，所以 $(2,C)$ 较大并更靠近 anchor。无论两消息到达次序如何，三副本的可见序列都是

x,z,y.

随后 A 删除 x，节点 $(1,A)$ 变 tombstone，query 显示 $z,y$ 。x 的节点仍作 y、z 的 anchor；若某离线 D 早已创建 after-x 的 w，它重连后仍可按同一 sibling 规则插入。

若用“当前索引 1”广播 y，接收者在先收到 z 后会把索引 1 解析到另一元素，产生分歧。若并发 siblings 按本地到达顺序排列，B 得 x,y,z 而 C 得 x,z,y。若 ID 仅为本地 counter 2，B、C 又会碰撞，去重错误地丢掉一个节点。

把 x 物理删除并把现有 children 接到 HEAD，也不能自动保持未来迟到 insert 的位置；需要稳定证明、旧 ID 到新 anchor 的重定向或拒绝旧 epoch 操作。

推论与应用

RGA 可支持协作文档、列表和聊天顺序，插入与删除消息大小近似常数，但节点和墓碑数量随编辑历史增长。批量编辑可共享事务元数据，却必须保留每个结构身份或证明批表示具有等价遍历。移动元素若实现成 delete 加 insert，会获得新 ID，并与并发编辑产生不同于原子 move 的语义。

实现应持久化 ID counter、dedup set 和未交付因果依赖。快照恢复若只保存可见字符串，便丢失 anchors；新的副本必须从含结构元数据的 checkpoint 加后续日志引导。

参考资料

Hyun-Gul Roh, Myeongjae Jeon, Jin-Soo Kim, and Joonwon Lee, “Replicated Abstract Data Types: Building Blocks for Collaborative Applications,” Journal of Parallel and Distributed Computing 71(3), 2011, pp. 354–368.
Marc Shapiro et al., “A Comprehensive Study of Convergent and Commutative Replicated Data Types,” INRIA RR-7506, 2011, sequence CRDT discussion.
Martin Kleppmann and Alastair R. Beresford, “A Conflict-Free Replicated JSON Datatype,” IEEE TPDS 28(10), 2017, pp. 2733–2746.

形式陈述 ​

反向链接

形式陈述