把层级建模成可复制的树
文件目录、大纲笔记的缩进、设计稿的图层面板、思维导图,大量真实数据是一棵会变结构的树。难点不在读,而在多个副本离线各自编辑再合并:本地优先应用、协同编辑、多设备文件同步,都要让几份各改过的层级无冲突地收敛到同一棵树。要把这件事做对,先得把层级收敛成一个统一、规整的形状。
1 · 三条建模约定
后续四页共用同一套约定。虚拟根是一个永不被移动或删除的顶点,它把森林收成一棵树,顶层节点都挂在它下面。单亲性要求每个普通节点恰好有一个 parent,这是贯穿全系列的结构不变量。删除不做物理删除,而是把节点移到一个特殊的 trash 节点下;CRDT 里删除常用墓碑(tombstone),trash 就是它的可视化形态。
于是新增、移动、删除全部归一成唯一原语 move(child, newParent):移到虚拟根下即放到顶层,移到别的节点下即改父级,移到 trash 下即删除。整棵树的状态就是一张从 child 到 parent 的映射。
警示 · 虚拟根与单亲性不是可选的装饰。有了它们,整棵层级就是一张「每个节点指向唯一 parent」的映射,一个极简、易复制、易比较的状态;所有编辑都化归为改某个节点的 parent 指针这一种 move,合并两份副本时只需调和这些 move。代价是必须时刻守住「单亲且无环」,并发畸变、祖先检查、多副本模拟与 undo-do-redo 四页正是在讲并发下如何守住它。
原语只有 move 一个,麻烦却恰恰从它来:两个副本并发地 move 会拼出成环、双亲分歧、孤儿三类畸变。