系统设计 / CRDT 可变树 · 多副本层级如何无冲突收敛 待审核 5 页

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

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

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

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

把层级建模成可复制的树

一个虚拟 root 把森林收成一棵树、每个节点恰好一个 parent、删除改为移进 trash，于是增删移全部归一成唯一原语 move。

 move · 三种并发畸变

move 原语与并发畸变

两个副本从同一棵树各发一个 move，朴素合并会拼出三类畸变：成环、双亲分歧与孤儿。本页把问题暴露出来，修法留给后两页。

 cycle · 祖先检查 = no-op

应用前的祖先检查

应用 move 前从新 parent 沿 parent 链上行，若撞到 child 或两者相同则必然成环，这步退化成 no-op：记进 log 但不改树。

 undo-do-redo · 乱序也收敛

undo-do-redo 重放

每个副本维护一份按时间戳升序的 op log。时间戳较小的 op 迟到时，先把更大的 entry 依次 undo、do 新 op、再按升序 redo 回来。

 replicas · 多副本模拟器

多副本与可控网络

三个副本各持一棵树与一份 log，op 先本地生效再投进网络缓冲区。无论按什么顺序投递，缓冲区清空后三个副本收敛到同一棵树。

它真实跑在哪里

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

原始论文与实现