← CRDT 可变树 · 多副本层级如何无冲突收敛 / 把层级建模成可复制的树 待审核 1 / 5
model · 虚拟 root + 单亲森林 + trash

把层级建模成可复制的树

文件目录、大纲笔记的缩进、设计稿的图层面板、思维导图——大量真实数据是一棵会变结构的树。难点不在「读」,而在多个副本离线各自编辑再合并: 本地优先应用、协同编辑、多设备文件同步,都要让几份各改过的层级无冲突地收敛到同一棵树。要把这件事做对,先得把「层级」收敛成一个统一、规整的形状。

本系列的建模约定(后续四页共用):

  • 虚拟根 ROOT: 一个永不被移动 / 删除的顶点,把「森林」收成一棵树,顶层节点都挂在它下面。
  • 单亲性: 每个普通节点恰好有一个 parent。这是贯穿全系列的结构不变量。
  • 删除 = 移进 trash: 不做真正的物理删除,而是把节点 move 到一个特殊的 TRASH 节点下(CRDT 里删除常用「墓碑 tombstone」,trash 就是它的可视化形态)。

于是新增、移动、删除全部归一成唯一原语 move(child, newParent): 移到 ROOT 下 = 放到顶层,移到别的节点下 = 改父级,移到 TRASH 下 = 删除。整棵树的状态就是一张 childparentchild \to parent 的映射。

下面是一棵示例层级。选一个节点、选它的新 parent,点 move 把它挂过去;或点 删除 把它移进 trash。试着把一个目录移到它自己的子节点下面——你会看到这步被拒绝(它会让树成环,成环的检测与拒绝逻辑见祖先检查那页)。这里先建立「一切皆 move」的心智模型。

为什么非要一个虚拟 root + 单亲性? 有了它们,整棵层级就是一张「每个节点指向唯一 parent」的映射——一个极简、易复制、易比较的状态。所有编辑都化归为「改某个节点的 parent 指针」这一种 move,合并两份副本时只需调和这些 move。代价是必须时刻守住「单亲且无环」:并发畸变祖先检查多副本模拟undo-do-redo 正是在讲并发下如何守住它。

原语只有 move 一个,麻烦却恰恰从它来——两个副本并发地 move 会拼出环、双亲分歧、孤儿三类畸变。