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

CRDT协同编辑

今日小编为你讲解CRDT协同编辑方面的内容，下面IT袋网为您详细介绍

本文来讲讲一个CRDT协同算法：修改树节点层级的操作后，保持多人协作时的数据最终一致，且不会出现环。

应用场景有：网盘嵌套的文件夹以及目录，在线文档工具的目录树协同，图形编辑器的图形树协同等。

环的问题

我们给每个节点一个 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 修正操作就结束了。