如何实现协同文档 - 理解Operational Transformation

[GarinZ]

Operational Transformation(OT)是一个应用于协同编辑领域的并发控制和冲突解决系统，要解决的是“多个用户对同一个文本域的同一个版本进行编辑时如何处理”的问题。下文中简称冲突问题。

整体来看，OT解决并发编辑冲突问题的思路有以下几步：

1. 定义原子操作类型：将用户在UI上触发的基于Event的操作抽象成由可枚举的N个原子操作类型组成的操作序列，这样一来复杂的UI界面操作的冲突就转换成了原子操作之间的冲突，同时也为多端数据同步定义了基本数据结构。
2. 设计冲突解决算法：在冲突问题发生时，通过冲突解决算法解决冲突。冲突解决算法要完成以下任务：
   • 通过算法能将冲突的2个操作序列转换成2个可以和原来冲突的操作序列串行执行的新操作序列。
   • 可串行的两组操作序列作用在文本后，产生的影响相同。
   • 串行后的操作需要保持原有语义
3. 多端冲突解决：通过向各端同步新的可串行操作序列完成冲突解决

接下来我使用ot.js的实现来详细解释一下冲突解决的思路

定义原子操作类型

我们先来看看没有原子操作的世界。对有状态的UI Component来说其实并没有操作类型的概念，每次UI操作只会生成newValue在浏览器端通过e.target.value获取。如果进行粗略的oldValue和newValue的diff，在浏览器文本框中，用户可以进行以下UI操作：

• 头部插入："a" => "ba"
• 尾部插入："a" => "ab"
• 中间插入："ab" => "acb"
• 删除并插入："abbbbb" => "ac"（选中bbbbb，输入c）
• 头部删除、尾部删除、中间删除、多个字符删除例子省略..

可以看到用户可在UI上操作种类太多、缺乏定义而且和UI组件绑定没有通用性。因此我们需要定义一些更简洁，更具有原子性的操作。在ot.js中定义的操作为：

• retain(Integer n): 保留n个字符，可以看作将字符串数组的指针移动到下标为n的位置
• insert(String str)：在当前位置插入str
• delete(String str)：删除当前位置后面的str

定义了原子操作之后，就可以将UI操作表示为由原子操作组成的操作序列了：

// 头部插入："a" => "ba"
insert("b");
// 尾部插入："a" => "ab"
retain(1).insert("b")
// 中间插入：`"ab" => "acb"`
retain(1).insert("c")
// 删除并插入：`"abbbbb" => "ac"`（选中bbbbb，输入c）
retain(1).delete("bbbbb").insert("c")

调用上面的原子操作后，在ot.js中操作序列会维护在一个称为TextOperation的类中

// 删除并插入：`"abbbbb" => "ac"`（选中bbbbb，输入c）
TextOperation to = new TextOperation().retain(1).delete("bbbbb").insert("c");
// to.ops = [Retain(1), Insert("bbb"), Delete("c")]

而TextOperation就是进行多端同步的最小单位，同时也实现了操作的可序列化

理解冲突问题

既然算法要解决冲突问题，先回顾一下什么是冲突问题：

冲突问题是：“多个用户对同一个文本域的同一个版本进行编辑时如何处理”的问题

先解释一下这里的关键词，正确理解冲突问题非常重要： 1、同一个文本域：对于不同的底层数据模型来说，“同一个文本域”的概念是不同的，对于<textarea></textarea>来说文本域的概念一定是这个文本框中的全部文本。但对于像Notion、Roam Research或者飞书这样的应用，它们的每一行都是一个Block，每个Block可以看做单独的textarea这时候“同一个文本域”这个概念也许就是文档中的每个Block，原子操作类型设计也会更加复杂（比如：Block的insert、move、delete，Block内嵌组件时，组件内如何协作），具体的定义还需要看应用的设计。但无论怎样，只有对同一个文本域进行的修改才是我们这里说的冲突。

2、版本：采用一个全局唯一且自增的数字标识，在协同编辑领域称为revision。生成新的TextOperation时，当前Client的revision加1。版本号一方面表示了文本所处的状态，另一方面也决定了操作是否可以应用于当前的文本上。（PS：之所以文本域的版本不采用字符串比较，避免ABA问题应该也是决定因素之一）。

设计冲突解决算法

已经理解了什么是冲突问题，那么从ot.js来看就是有两个作用在相同revision的文本域上的TextOperation，每个TextOperation中都带着一组原子操作类型序列。那么我们应该如何处理这两个TextOperation才能让冲突自动解决呢？

• 解决冲突方法是：当原子操作作用在文本中的同一个位置时，我们通过增加新原子操作或拆分当前原子操作的方式让它可串行化
• 自动解决的方法是：将定义的可枚举的原子操作类型retain();insert();delete()排列组合，组成9种搭配。就相当于枚举了全部的冲突情况，针对每种情况设计解决方案后当冲突发生时算法就可以自动解决冲突。

接下来用具体的例子解释通过增加操作解决冲突方法，两个操作都对0这个位置进行操作，通过冲突解决算法operationA和operationB被串行化，operationA中的insert操作先执行，operationB通过新增一个Retain()操作从而保留A操作的影响。生成了两个新操作，新操作中newOperationA和原来一样，newOperationB多了一个院子操作。

// Text: ""
// opeationA: "" => "a"
operationA.ops = [Insert("a")];
// opeationB: "" => "b"
opeationB.ops = [Insert("b")];
// 冲突解决
transform(operationA, operationB)
// {newOperationA: [Insert("a")], newOperationB: [Retain(1), Insert("b")]}

假如我们只针对这一种情况编写transform方法的处理逻辑，代码可能会像下面这样

function transform(operationA, operationB) {
  // 等待构建和返回的新操作
  newOperationA = new TextOperation();
  newOperationB = new TextOperation();
  // operationA和operationB的原子操作序列
  opsA = operationA.ops;
  opsB = operationB.ops;
  // 遍历opA和opB的指针
  indexA = 0;
  indexB = 0;
  while (indexA < opsA.length && indexB < opsB.length) {
    if (opsA[indexA] instanceof Insert && opsB[indexB] instanceof Insert ) {
      op = opsA[indexA ++];
      newA.ops.push(op);
      // op.value = "a"
      newB.ops.push(new Retain(op.value.length));
      newB.ops.push(opsB[indexB ++]);
    }
  }
  return {newOperationA, newOperationB};
}

假如将操作应用到文本的方法我们定义为String apply(String str, TextOperation op)，经过冲突解决后生成的新操作可以达到：

apply(apply(str, operationA), newOperationB) === apply(apply(str, operationB), newOperationA)

通过分解原子操作和全部排列组合的transform方法代码可以参考:ot.js - text-operation.js

多端冲突解决

目前为止我们理解了什么是冲突、如何解决冲突。那么在具体的应用中，什么时候会发生冲突呢？这个问题其实和应用前后端数据流设计有关，在此我举出一个具体的例子进行讨论。 假如发生上面操作时，Client和Server的数据流设计方案如下所示：

在图中所有调用transform方法的地方都是冲突发生的地方。也就是说在实际的协同编辑应用中，冲突会在两种场景下发生：1）Server接收到Client上传的操作。2）Client接收到Server广播的操作。 在Client/Server协作时，还有几个事实我们需要意识到：

• Client和Server都需要进行冲突解决，那么两端需要配置同构的transform算法
• 由于冲突解决算法的串行化逻辑一定是有倾向的：在上文的实现对同一位置的相同操作，operationA要优先于operationB）。那么为了最终一致性，Client和Server端都必须偏向Server端。所以Client同步下来的操作必须放在operationA的位置，Server获取到的新操作必须放在operationB的位置

想要枚举并理解全部Case的话，查看Visualization of OT with a central server是最好的方式。

总结

整体来看，OT是一种基于阻塞同步的多版本并发控制方案。

• 阻塞同步：每次冲突解决时，只同步处理两个operation
• 多版本：Client/Server端同时存在从同一个版本衍生出的的修改，最终通过某种方式再次合并成一致的版本。 一说到多版本并发控制，让人立刻就会想到到InnoDB的MVCC，二者和其他的并发方案的对比会放在另一篇文章中细说。

[jiangwenhan]

Mark

[xinjiawei]

mark