上次我们讲解了顺序一致性算法Fractional Indexing。
这次我们来看看另一种方案,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 算法是用一棵树来记录列表顺序,其先序遍历的结果即列表的顺序。
优点为:
- 容易理解和实现(当然 Fractional indexing 更简单);
- 在同一个位置(从左往右)插入连续的节点时,不会出现交错现象(两用户分别输入 “123” 和 “ABC”,同步后如果得到 “1A2B3C”,我们称之为 “交错”),这点是适合文字协同的;
- 对比 Fractional indexing,不用考虑精度和 index 冲突问题,不需要中心服务。
缺点为:
- CRDT 特有的被删除节点不能进行垃圾回收,会留下冗余数据。
- 在同一个位置反方向(从右往左)插入连续节点,可能会出现交错现象,文字编辑不会出现这种操作。
- 在节点很多的情况下效率较低,需要保存大量元数据,需要针对实际场景进行内存优化。
暂无评论内容