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

把层级建模成可复制的树

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

1 · 三条建模约定

后续四页共用同一套约定。虚拟根是一个永不被移动或删除的顶点,它把森林收成一棵树,顶层节点都挂在它下面。单亲性要求每个普通节点恰好有一个 parent,这是贯穿全系列的结构不变量。删除不做物理删除,而是把节点移到一个特殊的 trash 节点下;CRDT 里删除常用墓碑(tombstone),trash 就是它的可视化形态。

于是新增、移动、删除全部归一成唯一原语 move(child, newParent):移到虚拟根下即放到顶层,移到别的节点下即改父级,移到 trash 下即删除。整棵树的状态就是一张从 child 到 parent 的映射。

图 1-1 · 一切编辑皆 move 的示例层级。可选一个节点与它的新 parent 执行 move,或把节点移进 trash。把一个目录移到它自己的子节点下面会被拒绝,因为那会让树成环,检测逻辑见祖先检查一页。

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

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