系统设计 / CRDT 可变树 · 多副本层级如何无冲突收敛 / 多副本与可控网络 待审核 5 / 5
replicas · 多副本模拟器

多副本与可控网络

前四页拼起来就是这一页:三个副本各持一棵树与一份 op log。在某个副本上发一个 move,它先本地生效,祖先检查在此把关,再把这条 op 连同它的时间戳投进网络缓冲区,等待送达其他副本。在途的 op 包可以按任意顺序投递,乱序、延迟乃至重复投递都可以,重复投递会被幂等忽略。无论怎么投,把缓冲区清空后三个副本都收敛到同一棵树。

1 · 亲手投递并观察收敛

时间戳用 Lamport 时钟:每个副本记一个计数器,本地发 op 时加一、收到 op 时取两者的较大值同步。互不知道对方的并发 op 计数器可能相同,由副本 id 打破平局,这就是并发 move 的 LWW 裁决。

图 1-1 · 三副本加可控网络的模拟器。可先种入一组并发冲突,再按任意顺序投递缓冲区里的 op 包,观察各副本的树在投递过程中的分歧与最终的收敛。

建议 · 这就是强最终一致性的含义:只要两个副本收到的 op 集合相同,它们的树就必然相同,与到达顺序无关,无需中心协调,离线也能改。三块保证缺一不可,单亲森林建模应用前祖先检查undo-do-redo 按时间戳重放

2 · 参考文献

  1. Kleppmann, M., Gomes, D. P., Mulligan, D. P., & Beresford, A. R. (2022). A highly-available move operation for replicated trees. IEEE Transactions on Parallel and Distributed Systems, 33(7), 1711–1724. https://martin.kleppmann.com/papers/move-op.pdf