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 修正操作就结束了。

优先级问题

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

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

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

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 }
}

具体的过程为：

动图演示

下面是动图演示。

我在算法出处文章网页提供的交互源码上做了简单修改。

优缺点

优点：

1. 正统 CRDT 算法，不需要中心权威专门处理；
2. 不像其他的方案，需要复杂高昂的回滚和重放步骤恢复原来的树结构状态；
3. 需要保持历史父节点，看起来很耗费内存，但因为使用节点为 key，所以 edges 中元素数量不会和 reparent 操作次数呈正相关，只会维持较低的数量。

缺点：

1. 理解和实现比较困难。

结尾

该算法只是修改树中节点的层级，还是需要另外配合顺序和增删一致性策略，才能完成一个完整的功能。

如果还没看懂，建议阅读开头提到的文章，尝试里面的交互，并阅读其源码实现。

我是前端西瓜哥，欢迎关注我，学习更多协同编辑知识。