多副本与可控网络
前四页拼起来就是这一页:三个副本各持一棵树与一份 op log。在某个副本上发一个 move,它先本地生效,祖先检查在此把关,再把这条 op 连同它的时间戳投进网络缓冲区,等待送达其他副本。在途的 op
包可以按任意顺序投递,乱序、延迟乃至重复投递都可以,重复投递会被幂等忽略。无论怎么投,把缓冲区清空后三个副本都收敛到同一棵树。
1 · 亲手投递并观察收敛
时间戳用 Lamport 时钟:每个副本记一个计数器,本地发 op 时加一、收到 op 时取两者的较大值同步。互不知道对方的并发 op 计数器可能相同,由副本 id 打破平局,这就是并发 move 的 LWW 裁决。
建议 · 这就是强最终一致性的含义:只要两个副本收到的 op 集合相同,它们的树就必然相同,与到达顺序无关,无需中心协调,离线也能改。三块保证缺一不可,单亲森林建模、应用前祖先检查与 undo-do-redo 按时间戳重放。
2 · 参考文献
- 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