Movable Tree in CRDT
Tree Data Structures in Collaborative Applications
互联网使全世界的人们相互交流成为了可能，越来越多的公司通过支持远程的形式让世界各地的人才加入到自己的团队。实时协作或办公是异步协作办公变得更加普遍。远程协作办公变得如此热门除了网络基础设施越来越完善、网络传输速度越来越快之外，更加重要的一点是越来越多的基础软件支持了协作和跨端的功能，使得人们的工作流可以发生改变。
例如 Figma，Dropbox 和 Google Doc 等等，这些软件背后的协作算法让远程一起工作的人们无需考虑各方的数据是怎么达到一致的，无需小心地时刻和对方沟通避免产生编辑冲突。但目前的一些特殊场景下，人们的协作体验也不是期待中的丝滑便捷，不知道你是否遇到过 Dropbox 有时会多出几个有冲突的拷贝（A conflicted copy），在和团队成员一起使用 figma 移动了一些元素到其他层级时好像这些元素突然消失了一会。这是因为这些操作都是基于树结构进行建模的，但是使基于树结构的应用达到令人满意的协同效果是非常难的一件事情。
怎么处理层级关系
层级关系一般使用树或者森林的数据结构进行建模，对于树或者森林来讲，有三种常用操作
- 创建一个节点作为根节点或者某个节点的子节点
- 删除一个节点
- 移动一个节点作为另一个节点的子节点
这三种操作本质都可以被建模为相同的一种操作，move。
定义move(n, m)为移动 n 作为 m 的子节点。那么在森林中创建一个根节点就可以被表示为 move(n, none)，同时删除节点可以被表示为move(n, TRASH)。这里将TRASH定义为在森林之外的一个特殊的根节点，其后继都被表示为已删除。对于本地应用的移动操作，很容易发现可能会引起的问题，例如将a节点移动到它的子节点b的下面想成为b的子节点，操作发生时就会立刻被循环检测器检测到从而阻止此类操作并且通知给用户。但是在分布式系统下，会有很多不可预料的并行的操作发生，这可能导致树出现几种奇怪的状态。
- 并行地移动了同一个节点，但是设置了不同的父节点，导致要么在不同父节点中出现多个此节点的备份，要么结构不再是树而是有向无环图。
- 并行地移动了节点，造成了循环。
当前应用是如何处理异常状态的
在 Dropbox 早期，他们将移动定义为先删除原始位置，再在新位置创建，这很容易导致
Dropbox 是一个文件数据同步软件，当我们在多个终端移动文件时，如果产生了上述的异常状态时，Dropbox 会根据目录节点的关系保留全部的节点，所有重复的节点会创建多个副本提供给用户，让用户进一步操作 What's a conflicted copy
Figma 是一个支持实时协作的一款原型设计软件，他们认为树结构是协作系统中最复杂的一部分。他们为所有元素添加一个 parent 属性来表示父节点，中心化服务器在收到多端的更新时能够检测到操作是否会构成循环，如果会构成循环那么这个操作就会被服务器拒绝。但由于网络延迟等原因的存在，在客户端收到拒绝操作的消息之前还是可能收到来自其他端可能造成循环的操作更新。Figma 认为这是一个很少见的情况，所以使用一个简单而直接的方法，在收到服务器拒绝操作的返回之前，临时地保存这种状态，并且隐藏掉产生循环的这些元素。
Movable Tree in CRDT
除了以上中心化的方案之外，另一种面向树结构的协作方式就是使用 CRDT，在早期基于 CRDT 的算法实现起来复杂又有较大的额外储存开销，所以没有被在生产产品中使用。但不断地对算法进行优化和改进，有多种基于 CRDT 的树结构同步算法可以在一些生产场景下使用。我们选择了 Kleppmann et al 的 A highly-available move operation for replicated trees 算法集成到 Loro CRDT 框架中，因为他的算法足够简单也有着很高的性能。
这个算法的核心思路就是，在本地应用一个移动操作时我们可以通过检测循环来判断这个操作是否是安全的，进而忽略掉不安全的操作来保证树的结构正确。在分布式的情况下，我们可以仍沿用这样的思路，虽然多端产生的操作是存在并行的，但是我们可以通过添加特殊的逻辑时间戳，使得所有的操作是可以被线性排序的。对线性排序的序列依次进行应用时，不安全操作的处理就完全等同在本地依次应用这些操作一样。
基于上面的思路，那么树结构的同步一致性问题就变成以下两个问题：
如何为各端每一个操作赋予一个逻辑时间戳，使得这些操作是全局有序的
如何在已有序列中插入一个新操作
Lamport Timestamp
介绍一下
Insert a new operation
一个新操作是不是安全的，取决于应用这个操作时的树结构的状态，检测加入后是否会形成循环。所以在序列中插入一个新的操作就需要依次 undo 在末尾的操作直到可以应用新操作，之后再将 undo 过的全部 op 重新 redo 回来。
这整个过程又可以被分解为
如何 undo 一个操作
如何应用一个操作 （如何判断一个操作是否是安全的）
如何 undo 一个操作
我们已经将所有对树的操作都统一建模为 move 操作，undo 一个 move 操作也就是等同于将移动的节点移回旧父节点或者是删除掉这个节点。我们为了能够快速地进行 undo，所以应用每个 move 操作时都需要记录应用这个操作之前目标节点的旧父节点是哪个。
如何 apply 一个操作
在只有 move 操作的建模情况下，只有一种情况是不安全的，就是检测到新操作会造成节点之间产生循环。判断操作是否安全的方法也非常简单，因为树的定义其中一个条件就是每一个节点只有一条连通到根节点的路径。判断时我们可以通过递归地查询要移动到的父节点的前驱，如果要移动的目标节点是要移动到的父节点本身或者其前驱，那么就会产生循环，这个操作就是不安全的。
遇到不安全的操作，忽略这个操作造成的效果就不会产生循环。但是我们仍需要记录这个操作，因为一个操作是否是安全的是一个动态决定的，例如收到了排序在此操作之前的删除了造成循环的其他节点的更新，那么这个原本不安全的操作此时就是安全的了。同时我们需要标记这个操作是未生效的，因为我们在做 undo 操作时需要查询节点的旧父节点是哪个，也就是序列中目标节点是此节点的最后一个生效的操作的目标父节点。
如何完成 undo-do-redo 的过程
循环只会发生在收到来自其他端侧的更新时发生，所以 undo-do-redo 这个过程也在这时候需要进行。在接到一个新的更新时
- 如果新的操作是来自未来的片段那就需要缓存它，等到接受到缺失的部分时再进行应用。
- 新的操作和已有的全部操作比较，逻辑时间戳如果均大于已有的全部操作，那么就直接应用。也就是检测是否是安全的操作，如果是安全的那么就改变当前状态否则就忽略操作的影响。
- 如果新的操作的逻辑时间戳排序在已有序列的中间，那么就需要依次将操作从序列中 pop 出来，也就是需要移动回作为旧父节点的孩子撤销此操作造成的影响。直到新操作可以应用，新操作应用后再按序列顺序依次应用 undo 过的全部节点。