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

大家好，我是前端西瓜哥

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

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

算法来自 Figma 前 CTO 的这篇文章：

CRDT: Tree-Based Indexing https://madebyevan.com/algos/crdt-tree-based-indexing/

parent

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

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

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

counter

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

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

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

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

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

删除

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

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

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

结尾

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

优点为：

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

缺点为：

1. CRDT 特有的被删除节点不能进行垃圾回收，会留下冗余数据。
2. 在同一个位置反方向（从右往左）插入连续节点，可能会出现交错现象，文字编辑不会出现这种操作。
3. 在节点很多的情况下效率较低，需要保存大量元数据，需要针对实际场景进行内存优化。

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