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

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

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

环的问题

我们给每个节点一个 parent 属性,指向其父节点的 id。

比如修改父节点 A 为 B(这种操作我们称为 reparent),就实现了将一个节点从父节点 A,移动到另一个父节点 B 下的操作。

如果同步过来发现多个用户都在改同一个节点的 parent,使用 Last-Writer-Win 策略,应用最后写入的修改。

一切看起来如预期一样,貌似没啥问题。

直到一个用户把节点 A 的 parent 指向 B,然后另一个用户将节点 B 的 parent 指向 A,然后同步。

它们各自声称是各自的爸爸,于是他们就从树中脱离出来,成为一个环,我们 需要一种策略把环解开,让它们和树重新联通(reattach)

图片[1]-CRDT协同编辑:修改树的节点层级Mutable Tree Hierarchy-不念博客

Figma 使用过的一种做法是让服务端做判断。

解决方法是,最先改变父子关系,会作为最终状态。

假设用户 1 将 C 放到 B 下的操作先到服务器,服务器会应用它。此时服务器收到用户 2 把  B 放到 C 下的同步信息,服务器会将其驳回,带上真正的父节点 id。

在驳回前,用户 2 其实收到了用户 1 的操作,客户端此时会将 A 和 B 临时形成环,然后移出图形树,接着驳回的信息回来,客户端就能确定父节点,然后恢复到图形树中

缺点是,形成环的图形会消失一段时间,以及需要中心服务,并专门维护节点的父子关系。

CRDT算法

此外还有一个 CRDT 的去中性化的实现方式,也是本文要展开叙述的算法。

核心思路是 记录每个节点的历史父节点,在进行修改父节点操作后,找到脱离树的节点,对其做一个回滚操作,使其指回历史父节点中,最近的一个还在树上的节点

下面进行具体展开讲解。

每个节点需要额外记录 历史父节点

因为有点像图(指向其他节点且有权重值),我们称之为 edges。

edges 是一个映射表,的 key 为父节点引用,value 为一个计数器值 counter,越大表示越在近期成为父节点。

图片[2]-CRDT协同编辑:修改树的节点层级Mutable Tree Hierarchy-不念博客

对于上图的 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 节点),没有问题。

图片[3]-CRDT协同编辑:修改树的节点层级Mutable Tree Hierarchy-不念博客

再接着另一个用户把 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 修正操作就结束了。

图片[4]-CRDT协同编辑:修改树的节点层级Mutable Tree Hierarchy-不念博客

优先级问题

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

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

节点挑选最近历史父节点,优先级逻辑为:

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

图形树是这样的:

图片[5]-CRDT协同编辑:修改树的节点层级Mutable Tree Hierarchy-不念博客

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

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

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

图片[6]-CRDT协同编辑:修改树的节点层级Mutable Tree Hierarchy-不念博客

然后你发现,没有移动 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 }
}

具体的过程为:

图片[7]-CRDT协同编辑:修改树的节点层级Mutable Tree Hierarchy-不念博客

动图演示

下面是动图演示。

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

图片[8]-CRDT协同编辑:修改树的节点层级Mutable Tree Hierarchy-不念博客

优缺点

优点:

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

缺点:

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

结尾

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

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

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

© 版权声明
THE END
喜欢就支持一下吧
点赞63赞赏 分享
评论 抢沙发
头像
欢迎光临不念博客,留下您的想法和建议,祝您有愉快的一天~
提交
头像

昵称

取消
昵称代码图片

    暂无评论内容