← 首页 / CRDT 可变树 · 多副本层级如何无冲突收敛 待审核 5 页

CRDT 可变树 · 多副本层级如何无冲突收敛

文件目录、大纲笔记的缩进、设计稿的图层面板、思维导图——大量真实数据是一棵会变结构的树: 不只叶子内容能改, 节点本身能换父节点 (move)。一旦这棵树要被多个副本离线各自编辑再合并 (本地优先 / 协同编辑), 普通的 last-writer-wins 就不够了: 两个副本并发地把对方移到自己下面, 朴素合并会拼出一个环, 树就不再是树。

本系列沿着 Kleppmann 等 2021 年的 move 算法, 把一棵可复制可变树拆开来看: 先把层级建模成「虚拟 root + 单亲森林 + trash」, 把增删移统一成唯一原语 move(child, parent); 再逐一演示并发会制造的畸变、应用前的祖先检查如何挡住成环、以及收敛引擎 undo-do-redo 如何让乱序到达的操作也收敛; 最后一页是可亲手投递的多副本模拟器。每页都能改输入、单步播放、随时校验。

model · 虚拟 root + 单亲森林 + trash

把层级建模成可复制的树

层级数据无处不在，难点不在「读」而在「多副本离线改了再合」。先把一棵层级建模成统一形状：一个虚拟 root 把森林收成一棵树、每个节点恰好一个 parent（单亲性）、删除不真删而是移进 trash。于是增 / 删 / 移全部归一成唯一原语 move(child, newParent)——亲手移几下、删几下，建立后续四页共用的心智模型。

 move · 三种并发畸变

move 原语与并发会制造的畸变

只有一个原语 move，却足以撑起增删移；也正因如此，并发的 move 才是全部麻烦的根源。两个副本从同一棵树出发各发一个 move，朴素合并（各按到达顺序应用）会拼出三类畸变：成环（互相移到对方下面）、双亲分歧（同一节点被移向两处，两副本各执一词）、孤儿（移进一个同时被对方删掉的节点）。逐个选中场景，观察朴素合并如何破坏树结构。

 cycle · 祖先检查 = no-op

不成环的关键：应用前做祖先检查

成环是可变树 CRDT 最硬的并发畸变，而挡住它只需一道祖先检查: 应用 move(child, parent) 前，从 parent 沿 parent 链上行，若撞到 child（即 child 是 parent 的祖先）或两者相同，这步会成环 → 直接退化成 no-op（记进 log 但不改树）。单步走一遍上行检查，对比一个安全的 move 与一个成环的 move，看 no-op 如何守住单亲森林永不成环。

 undo-do-redo · 乱序也收敛

收敛引擎：undo-do-redo 重放

祖先检查保证了单次应用安全，但分布式下操作会乱序到达。每个副本维护一份按时间戳（Lamport: 计数器 + 副本 id） 升序的 op log；当一个 ts 较小的 op 迟到，副本先把 ts 更大的 entry 依次 undo 回去、do 新 op、再按 ts 升序 redo 回来。单步看这套重放，理解为什么它等价于「一次性按 ts 顺序重放」，从而让并发 move 走 LWW、任意到达顺序都收敛。

 replicas · 多副本模拟器

把它跑起来：多副本 + 可控网络

收束成一个可亲手操作的多副本模拟器: 三个副本各持一棵树与一份 log，你在某个副本上发 move，它先本地生效、再把 op 投进网络缓冲区；你可以按任意顺序把在途 op 投递给其他副本，甚至乱序、重复投递。无论怎么投，全部投递完后三个副本收敛到同一棵树——这就是前四页拼起来的最终承诺。

它真实跑在哪里

本地优先 / 协同编辑: 大纲笔记、白板、设计稿图层面板这类可嵌套、可拖动改父级的结构, 多端离线编辑后要无冲突合并——正是可变树 CRDT 的主场 (Automerge 的 move、部分协同应用的 outline 模型)。 文件同步: 多设备各自移动 / 重命名目录后合并, 经典的并发 move 成环问题与这里同源。 它和谁是一族: 同属「多副本最终一致」家族, 与序列 CRDT (文本协同的 RGA / Yjs)、寄存器 CRDT (LWW) 互补——树 CRDT 难就难在结构 (parent 关系) 本身可并发改, 这是序列 / 寄存器 CRDT 不处理的维度。

原始论文与实现