← CRDT 可变树 · 多副本层级如何无冲突收敛 / 收敛引擎:undo-do-redo 重放 待审核 4 / 5
undo-do-redo · 乱序也收敛

收敛引擎:undo-do-redo 重放

祖先检查保证了单次应用不成环,但分布式下操作会乱序到达。每个副本给操作打一个全序时间戳(Lamport: 计数器 : 副本 id,计数器相同再比副本 id 打破平局),并维护一份按时间戳升序的 op log。关键技巧是:当一个时间戳较小的 op 迟到,不能直接追加,而要先把 log 末尾所有时间戳更大的 entry 依次 undo 回去、do 这条迟到的 op、再按时间戳升序 redo 回来。

这样无论 op 以什么顺序到达,每个副本的 log 始终维持同一个 ts 升序序列,等价于「一次性按 ts 顺序从头重放」——于是结果只由这组 op 决定,与到达顺序无关(并发地 move 同一节点,就由 ts 最大者胜出,即 LWW)。下面有三组到达顺序作用于同一组 op,单步看 undo / do / redo,再核对它们的最终树是否一致。

为什么等价于「按 ts 顺序重放」? 归纳来看,每次 applyOp 结束时 log 都恰好是「已知全部 op 按 ts 升序」的序列,且树正好是把这个序列从头 doOp 一遍的结果。新 op 无论何时到达,undo-do-redo 都把它插回它该在的 ts 位置,并让它之后的 op 在新状态下重新 doOp——所以同一条 op 在不同重放里可能这次生效、那次因成环被拒 (no-op),但最终序列唯一 ⇒ 最终树唯一。这就是收敛 (strong eventual consistency)。

装进多个副本: 把祖先检查 + undo-do-redo 装进多个副本 + 一条可乱序的网络——多副本模拟器让你亲手投递、投递后观察收敛。