CRDT 协同编辑：修改树的节点层级 Mutable Tree Hierarchy
CRDT 协同编辑：修改树的节点层级 Mutable Tree Hierarchy
大家好，我是前端西瓜哥。
本文来讲讲一个 CRDT 协同算法：修改树节点层级的操作后，保持多人协作时的数据最终一致，且不会出现环。
算法来自 Figma 前 CTO Even Wallace 的文章：
《CRDT: Mutable Tree Hierarchy》 https://madebyevan.com/algos/crdt-mutable-tree-hierarchy/
应用场景有：网盘嵌套的文件夹以及目录，在线文档工具的目录树协同，图形编辑器的图形树协同等。
环的问题
我们给每个节点一个 parent 属性，指向其父节点的 id。
比如修改父节点 A 为 B（这种操作我们称为 reparent），就实现了将一个节点从父节点 A，移动到另一个父节点 B 下的操作。
如果同步过来发现多个用户都在改同一个节点的 parent，使用 Last-Writer-Win 策略，应用最后写入的修改。
一切看起来如预期一样，貌似没啥问题。
直到一个用户把节点 A 的 parent 指向 B，然后另一个用户将节点 B 的 parent 指向 A，然后同步。
它们各自声称是各自的爸爸，于是他们就从树中脱离出来，成为一个环，我们 需要一种策略把环解开，让它们和树重新联通（reattach）。
Figma 使用过的一种做法是让服务端做判断。
解决方法是，最先改变父子关系，会作为最终状态。 假设用户 1 将 C 放到 B 下的操作先到服务器，服务器会应用它。此时服务器收到用户 2 把 B 放到 C 下的同步信息，服务器会将其驳回，带上真正的父节点 id。 在驳回前，用户 2 其实收到了用户 1 的操作，客户端此时会将 A 和 B 临时形成环，然后移出图形树，接着驳回的信息回来，客户端就能确定父节点，然后恢复到图形树中。 缺点是，形成环的图形会消失一段时间，以及需要中心服务，并专门维护节点的父子关系。
CRDT 算法
此外还有一个 CRDT 的去中性化的实现方式，也是本文要展开叙述的算法。
核心思路是 记录每个节点的历史父节点，在进行修改父节点操作后，找到脱离树的节点，对其做一个回滚操作，使其指回历史父节点中，最近的一个还在树上的节点。
下面进行具体展开讲解。
每个节点需要额外记录 历史父节点。
因为有点像图（指向其他节点且有权重值），我们称之为 edges。
edges 是一个映射表，的 key 为父节点引用，value 为一个计数器值 counter，越大表示越在近期成为父节点。
对于上图的 A 和 B，初始化时父节点都是指向 C 的，它们的 edges 初始值为：
{
A: { C: 0 },
B: { C: 0 }
}
然后用户进行 reparent 操作，把 A 放到 B 下，我们会更新 edges，把新的父节点 B 加进去，其 counter 值为 edges 中的最大 counter 加一，即将 A: {B: 1} 合并到 edges 上。
于是变成：
{
A: { C: 0, B: 1 },
B: { C: 0 }
}
我们基于 edges 重新计算每个节点的 parent，取 edges 中 counter 最大的的节点作为父节点。
此时 A 和 B 的父节点分别取 edges 中的最大值 B 和 C，还是在树上的（即可以不断递归 parent 到达 root 根节点，我们将这种节点称为 rooted 节点），没有问题。
再接着另一个用户把 B 放在 A 下的操作同步过来，只同步单个 edge，即 B: {A: 1}。另外注意时序问题，同步时要确保父节点已经同步过去了，否则会出现父节点不存在的情况。
于是 edges 变成：
{
A: { C: 0, B: 1 },
B: { C: 0, A: 1 }
}
我们给每个节点取 edges 的最大值为父节点，此时出现了环：A 指向 B，B 指向 A。
我们需要找出所有的不在树下的节点（称为 non-rooted 节点），把它们恢复回树中。
这里只有 A 和 B。对于 A，取 counter 最大的 rooted 节点，即 C，将 A 的 parent 修正为 C，此时 A 也变成了 rooted 节点。
然后是 B，B 的最大 edge 是 A，A 已经变成 rooted 了，所以 B 的 parent 指向 A。
到这里我们的 reattach 修正操作就结束了。
优先级问题
这里有几个优先级的问题要注意。
首先是 选择历史父节点的优先级 的问题。
节点挑选最近历史父节点，优先级逻辑为：
- 必须是 rooted 节点；
- counter 大的优先；
- 若多个父节点的 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 }
}
具体的过程为：
动图演示
下面是动图演示。
我在算法出处文章网页提供的交互源码上做了简单修改。
优缺点
优点：
- 正统 CRDT 算法，不需要中心权威专门处理；
- 不像其他的方案，需要复杂高昂的回滚和重放步骤恢复原来的树结构状态；
- 需要保持历史父节点，看起来很耗费内存，但因为使用节点为 key，所以 edges 中元素数量不会和 reparent 操作次数呈正相关，只会维持较低的数量。
缺点：
- 理解和实现比较困难。
结尾
该算法只是修改树中节点的层级，还是需要另外配合顺序和增删一致性策略，才能完成一个完整的功能。
如果还没看懂，建议阅读开头提到的文章，尝试里面的交互，并阅读其源码实现。
我是前端西瓜哥，欢迎关注我，学习更多协同编辑知识。