CRDT协同编辑:另一种顺序一致性算法Tree-Based Indexing

上次我们讲解了顺序一致性算法Fractional Indexing。

这次我们来看看另一种方案,Tree-Based Indexing,一种基于树结构的顺序一致性算法。

该算法使用树来表示列表顺序,树的先序遍历的结果即列表的顺序。

parent

每个节点除了保持自身的数据外,还会有一个 parent 指针,指向其父节点,且需要在创建时就指定一个已存在的父节点。

新节点插入到某个位置时,其 parent 节点指向它的在序列中左侧节点。

比较特殊的是,如果是在开始位置,parent 为 null 或者指向一个虚拟节点。

counter

对一个节点插入或重排时,新节点的 counter 属性记录此时起父节点下 子节点的数量

同层级节点的顺序为 counter 倒序排列,即 counter 大的放在靠左一侧。

图片[1]-CRDT协同编辑:另一种顺序一致性算法Tree-Based Indexing-编程社

上图中,末尾插入粉色节点时,counter 为 0。

插入中间的蓝色节点时,父节点已经有一个节点了,所以 counter 为 1,然后比紫色节点的 counter(为 0) 大,所以蓝色会放在左侧。

同步后 couter 可能会相同,对于该冲突会再基于 时间戳和客户端 ID 确定先后顺序,这个属于 CRDT 常规操作。

删除

对于删除和重排,原节点是不能从树中移除,进行垃圾回收的,只会被标记为 “已删除”。

这也是 CRDT 的特性,因为可能有另一个用户,正基于这个节点进行插入操作,删除会导致同步过来的插入操作找不到目标节点。

图片[2]-CRDT协同编辑:另一种顺序一致性算法Tree-Based Indexing-编程社

如果一个节点被同时移动到不同的父节点下,使用 last-writer-wins 策略,对比时间戳和客户端 ID 来解决冲突。

结尾

Tree-Based Indexing 算法是用一棵树来记录列表顺序,其先序遍历的结果即列表的顺序。

优点为:

  1. 容易理解和实现(当然 Fractional indexing 更简单);
  2. 在同一个位置(从左往右)插入连续的节点时,不会出现交错现象(两用户分别输入 “123” 和 “ABC”,同步后如果得到 “1A2B3C”,我们称之为 “交错”),这点是适合文字协同的;
  3. 对比 Fractional indexing,不用考虑精度和 index 冲突问题,不需要中心服务。

缺点为:

  1. CRDT 特有的被删除节点不能进行垃圾回收,会留下冗余数据
  2. 在同一个位置反方向(从右往左)插入连续节点,可能会出现交错现象,文字编辑不会出现这种操作。
  3. 在节点很多的情况下效率较低,需要保存大量元数据,需要针对实际场景进行内存优化。
© 版权声明
THE END
喜欢就支持一下吧
点赞90 分享
评论 抢沙发
头像
欢迎您留下宝贵的见解!
提交
头像

昵称

取消
昵称

    暂无评论内容