← CRDT 可变树 · 多副本层级如何无冲突收敛 / move 原语与并发会制造的畸变 待审核 2 / 5
move · 三种并发畸变

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

建模那页把增删移都归一成了唯一原语 move(child, newParent)。原语只有一个,麻烦却恰恰从它来:两个副本从同一棵树出发,各自发一个 move,再把对方的 move 合并进来,会拼出几类畸变。本页用朴素合并(没有任何防护——每个副本按操作的到达顺序直接改 parent 指针)跑这些场景,把问题暴露出来;修法见祖先检查时间戳 LWW + undo-do-redo

每个场景里,两个副本 R1 / R2 从同一棵初始树出发。R1 先发自己的 op、再收到 R2 的 op; R2 则相反。两边到达顺序不同,朴素合并下就可能得到不同(甚至损坏)的树。

三类畸变各有归宿:

  • 成环是结构性损坏(整段子树脱离 ROOT)——靠应用前的祖先检查挡住,会成环的 move 退化成 no-op。
  • 双亲分歧是真正的「并发冲突」(两副本各执一词)——靠时间戳 LWW + undo-do-redo 让二者收敛到同一个赢家。
  • 孤儿是语义上的意外(节点被连带拖进 trash),朴素合并这里恰好已收敛——CRDT 的贡献是让它确定且可恢复(东西在 trash,没真丢)。