系统设计 / CRDT 可变树 · 多副本层级如何无冲突收敛 / move 原语与并发畸变 待审核 2 / 5
move · 三种并发畸变

move 原语与并发畸变

建模一页把增删移都归一成了唯一原语 move(child, newParent)。原语只有一个,麻烦却恰恰从它来:两个副本从同一棵树出发各自发一个 move,再把对方的 move 合并进来,会拼出几类畸变。本页用朴素合并跑这些场景,即不加任何防护、每个副本按操作的到达顺序直接改 parent 指针,把问题暴露出来。

1 · 三类畸变

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

图 1-1 · 朴素合并下的三类并发畸变。可逐个选中场景,对照两个副本各自的到达顺序与最终得到的树。

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