在协作编辑场景中，树形结构是最常用的数据组织形式之一 —— 从文件系统的目录层级到文档的大纲结构，再到任务管理的看板分类。当多个用户同时移动节点时，传统的乐观复制策略会面临一个棘手的问题：并发移动操作可能导致树结构出现循环，破坏树的基本不变量。本文将介绍 Amber Tree 的设计思路，以及 Rowan 红绿树如何通过中间状态表示来解决这一难题。
并发移动带来的循环困境
考虑一个简单的场景：节点 A 和节点 B 最初都挂载在节点 C 下。用户 1 将 A 移动到 B 下，同时用户 2 将 B 移动到 A 下。如果两个操作独立执行，最终会形成 A→B→A 的循环，这不再是一个合法的树结构。
传统的解决方案通常依赖中央服务器进行协调，或者要求所有操作按全局顺序执行。但在去中心化的协作场景中，这些方案要么违背 CRDT（Conflict-free Replicated Data Type）的设计初衷，要么引入不可接受的延迟。
Evan Wallace 提出的 Mutable Tree Hierarchy 算法为解决这一问题提供了思路：每个节点不再维护单一的父指针，而是维护一个边映射（Edge Map），记录该节点历史上所有的父节点关系，并为每条边分配一个单调递增的计数器值。
Amber Tree 的核心机制
Amber Tree 的核心数据结构可以表示为：
interface Node {
id: string;
edgeMap: Map<ParentId, Counter>; // 父节点 → 计数器
// 其他节点属性...
}
当将节点 X 设置为节点 Y 的子节点时，算法会在 X 的 edgeMap 中添加或更新条目 {Y: maxCounter + 1}。这里的计数器不仅标识操作的时序，更关键的是为冲突解决提供确定性的排序依据。
确定当前父节点的算法分为两个阶段：
-
初始选择：对每个节点，选择 edgeMap 中计数器值最大的条目作为其当前父节点（计数器相同时以父节点 ID 作为决胜条件）。此时，能够沿着父指针追溯到根节点的节点构成一棵有效树，其余节点则处于循环中。
-
重新挂载：对于处于循环中的节点，算法会寻找指向已挂载节点的边，并将其重新挂载到树上。选择策略是优先选择计数器值最大的边（新操作优先），辅以父节点 / 子节点 ID 作为决胜条件。
这种设计的精妙之处在于，"回退" 操作并不意味着删除 edgeMap 中的数据 —— 被回退的条目仍然保留，只是暂时不被视为有效边。这保证了所有副本最终能够收敛到一致的状态，而不会在网络中引发状态震荡。
Rowan 红绿树：中间状态的显式表示
在 Amber Tree 的基础上，Rowan 红绿树引入了中间状态的显式概念，将节点和边标记为 "红色"（冲突 / 临时状态）或 "绿色"（已确认状态）。这种可视化隐喻帮助开发者理解 CRDT 在收敛过程中的状态演化。
绿色状态表示该节点已通过验证，其父节点关系不形成循环，可以安全地参与后续操作。红色状态则表示该节点或其祖先处于循环检测的待定区域，正在等待冲突解决算法的处理。
中间状态的表示带来了几个工程优势：
首先，它允许 UI 层在数据尚未完全收敛时提供视觉反馈 —— 用户可以看到自己的操作已被接受（本地立即应用），同时也看到某些节点暂时处于 "待处理" 状态。这比传统的 "加载中" 或 "冲突已解决" 的二元状态更加细腻。
其次，中间状态为操作的原子性提供了边界。当用户执行一个复杂的批量移动操作时，可以将整个操作序列标记为一个中间状态单元，只有在所有子操作都通过验证后才整体转为绿色状态。
实现要点与可落地参数
在实际实现 Amber Tree/Rowan 红绿树时，以下参数和策略值得注意：
计数器溢出问题：虽然理论上计数器可以无限增长，但在实际系统中应考虑定期压缩或重置策略。一种可行的方案是在达到阈值（如 2^40）时触发全局快照，重置所有计数器。
边映射的内存管理：edgeMap 会随操作历史增长，但并非无限。当节点在两个父节点之间反复移动时，新的操作会覆盖旧的条目而非持续追加。实现时应确保重复操作不会导致内存泄漏。
重新挂载的优先级队列：为提高重新挂载阶段的效率，可以使用优先队列维护待处理边，按 (counter, parentId, childId) 的字典序进行排序。这保证了所有副本以确定性顺序处理冲突，是实现强最终一致性的关键。
与有序列表 CRDT 的组合：如果业务需要维护子节点的顺序（而不仅是父子关系），可以将 Amber Tree 与 Fractional Indexing 或 Tree-based Indexing 等有序列表 CRDT 结合。建议将顺序信息存储在 edgeMap 的值中，与计数器一起原子更新，确保父节点变更和位置变更的一致性。
网络同步策略：边映射的条目可以使用 Last-Writer-Wins 策略同步，但需注意 "同一节点的不同条目并发编辑" 不应被视为冲突 —— 这是 CRDT 设计的核心原则，允许不同父节点的操作并发进行。
局限与权衡
Amber Tree 方案并非没有代价。其最大的挑战在于实现的复杂性 —— 开发者需要仔细推理循环检测、重新挂载顺序、以及边界情况下的收敛行为。Martin Kleppmann 在 "CRDTs: The Hard Parts" 中指出，许多已发表的 CRDT 算法在某些场景下会表现出异常行为，树结构 CRDT 尤其容易隐藏 subtle 的 bug。
此外，虽然 edgeMap 不会无限增长，但在高频重排场景下元数据开销仍然可观。对于内存敏感的应用，可能需要引入垃圾回收机制，在确认某条边永远不会被重新启用后将其从映射中移除 —— 但这需要额外的协调来保证所有副本的一致性。
总结
Amber Tree 通过边映射和计数器机制，为 CRDT 树结构提供了一种优雅处理并发移动的方案。Rowan 红绿树的中间状态表示进一步增强了系统的可理解性和用户体验。在去中心化协作日益普及的今天，这种能够在无协调情况下保证最终一致性的数据结构，为实时协作应用提供了坚实的技术基础。
对于正在构建协作编辑、分布式文件系统或多用户任务管理应用的开发者，理解 Amber Tree 的设计原理有助于在面对复杂的数据一致性需求时做出更明智的架构选择。
参考来源
- Evan Wallace, "CRDT: Mutable Tree Hierarchy", madebyevan.com
- Martin Kleppmann, "CRDTs: The Hard Parts", Hydra Conference 2020
- maca/crdt-replicated-tree, GitHub
内容声明：本文无广告投放、无付费植入。
如有事实性问题，欢迎发送勘误至 i@hotdrydog.com。