CRDT协同编辑：修改树的节点层级Mutable Tree Hierarchy(2)

CRDT协同编辑

优先级问题

这里有几个优先级的问题要注意。

首先是选择历史父节点的优先级的问题。

节点挑选最近历史父节点，优先级逻辑为：

1. 必须是 rooted 节点；
2. counter 大的优先；
3. 若多个父节点的 counter 相同（同步时可能出现），使用 Last-Writer-Win 策略选择最新的一个。

然后是子节点的处理顺序也需要符合特定优先级规则的，因为不注意顺序的话，先处理 A 和先处理 B 的这两者的结果是不同的。

前面我们是先处理 A，结果是 A 会在 C 下。但如果是先处理 B，那 B 会在 C 下，会出现最终数据不一致问题。

所以这里也要有优先级，比如让 id 小的 non-rooted 节点优先处理。

可以配合优先级队列数据结构使用。

固化新旧父节点路径

这里还有一个特殊场景要处理。

经过前面的操作，我们的 A 和 B 的 edges 是这样的：

{
  A: { C: 0, B: 1 },
  B: { C: 0, A: 1 }
}

图形树是这样的：

此时，我们再将 B 的 parent 指向 D。根据前面的逻辑，加上一个B: { D: 2 }， edges 变成这样：

{
  A: { C: 0, B: 1 },
  B: { C: 0, A: 1, D: 2 }
}

取 edges 中 counter 最大值为父节点，都是 rooted 节点，结果为：

然后你发现，没有移动 A，但 A 居然跑到 B 下面去了，这是不符合用户预期的。

为解决这个问题，我们需要做以下操作。

B 节点从原父节点 A 下移动到 D 下前，我们需要把父节点 A 进行固化操作，即把原父节点 A 的 edges 中当前真正的 parent，即 C，的 counter，设置为最大值的 counter 加一。

如果 counter 已经是最大值了，则不需要进行操作了。

这样是为了确保下次 reparent 时还是原来的 parent。

这里我们会额外多了个 A: {C: 2}，于是：

A: { C: 0, B: 1 }

变成了：

A: { C: 2, B: 1 }

原父节点 A 到根节点的所有节点都要进行这个操作，新父节点 D 到根节点的所有节点也要做同样处理。

修正后的 edegs 为：

{
  A: { C: 2, B: 1 },
  B: { C: 0, A: 1, D: 2 }
}

具体的过程为：