Skip to main content

OT 冲突算法

OT 冲突算法​

OT 算法的全称为 Operational Transformation，即 操作转换。

在 OT 算法中，每个用户对数据的操作(如修改、删除等)都被记录下来，并在其他用户的客户端进行相应的转换，从而实现多个用户对同一份数据的协同编辑。

发展史​

  • 1989 年，OT 算法被正式提出，标志协同编辑技术的进步。
  • 2006 年，Google 首次将 OT 算法应用于商业产品 Google Docs。
  • 2011 年，微软在 Office 365 中基于 OT 实现了协同编辑。
  • 2012 年，Quill 编辑器开源，其数据模型 Delta 基于 OT 算法设计，降低了协同编辑门槛，基于 Quill 可以很方便的实现协同 富文本编辑，随后被更多中小公司产品采用。
  • 2013 年，一款基于 OT 的流行的开源解决方案 ShareDB 开源。

操作​

操作是针对操作的一种结构化描述。文档的每一次修改都可以看作是一个原子化的操作，然后通过某种方式去描述该操作。

以 Quill 中的 Delta 为例：

{
  ops: [
    // 每一个对象就是对一个操作的描述
    { insert: 'Gandalf', attributes: { bold: true } },
    { insert: ' the ' },
    { insert: 'Grey', attributes: { color: '#cccccc' } }
  ]
}

在如上的操作描述中，提供了如下的信息：

  1. 插入一个加粗的 "Gandalf"。
  2. 插入一个普通的文本，文本信息为 " the "。
  3. 插入一个颜色为 #cccccc 的 "Grey"。

当前的文本如下：

Gandalf the Grey

除了 insert 以外，还包括 retain 以及 delete。

  • retain 表示保留接下来的若干字符，不做修改，如果加上了 attributes 属性，则表示保留这些字符的同时，应用指定的格式。如果 attributes 的某个键的值是 null，就表示移除该格式。
  • delete 表示删除接下来的若干个字符。
{
  ops: [
    // 保留接下来的7个字符（"Gandalf"），并去掉加粗，添加斜体
    { retain: 7, attributes: { bold: null, italic: true } },

    // 保留接下来的5个字符（" the "），不做修改
    { retain: 5 },

    // 插入字符串 "White"，并设置颜色为白色
    { insert: 'White', attributes: { color: '#fff' } },

    // 删除后面的4个字符（也就是删除原来的 "Grey"）
    { delete: 4 }
  ]
}

当前的文本如下：

Gandalf the White

上面的操作描述中，包含了如下的信息：

  1. retain: 7：跳过前 7 个字符，同时对这部分文字应用格式(加斜体、去掉加粗)。
  2. attributes: { bold: null }：加粗被移除。
  3. retain: 5：继续跳过' the '，保留原样。
  4. insert: 'White'：插入'White'，带白色字体。
  5. delete: 4：删除'Grey'。

除了 Quill 开源的 Delta 模型以外，有名的还有 slate 的 JSON 模型，通过 insert_text、remove_text 等操作描述信息来完成整篇文档的描述。

转化​

转换的过程通常在服务端完成。客户端将一个操作描述发送给服务端后，服务端对多个客户端的操作进行转换，并且对客户端操作中的并发冲突进行修正，确保当前操作同步到其他设备时得到一致的结果。因为对冲突的处理都是在服务端完成，所以最终客户端得到的结果一定是一致的，也就是说 OT 算法的结果是会保证强一致性。

不同位置​

假设初始状态如下：

Initial: |a|b|c|
Index:    0 1 2

有两个用户：

  • 用户 A ：在位置 1 插入 X。
  • 用户 B：在位置 0 插入 Y。

整个并发场景如下：

初始状态 abc

A 操作 Insert at 1 X

B 操作 Insert at 0 Y

文档变为 aXbc

文档变为 Yabc

A 收到 B 的操作

B 收到 A 的操作

OT 转换结果 Insert Y at 0

OT 转换结果 Insert X at 2

应用结果 YaXbc

应用结果 YaXbc

最终一致 YaXbc ✅

上面的例子是两个用户针对不同位置的操作，但是如果是两个用户针对同一个位置进行操作呢？

同位置​
  • 用户 A：在 abc 后面插入 X。
  • 用户 B： 在 abc 后面插入 Y。

这个时候要看 两个操作到达服务器的顺序。

假设顺序是用户A ➜ 用户B：

  • 首先应用用户 A 的操作 {insert: 'x', pos: 3}，这个操作被直接应用，整个文本变成 abcX。
  • 用户 B 的操作 {insert: 'y', pos: 3} 到达服务器，因为现在在文档 3 的位置已经有了 X，所以用户的操作会被进行转换，转换成 {insert: 'y', pos: 4}，最终文档变成 abcXY。

同理，如果到达的顺序是用户B ➜ 用户A，那么最终的文档就是 abcYX。

如果两个操作同时到达的服务端，且到达的时间戳都一样呢？

同时同操作​

这种情况下，需要看 OT 算法的实现。例如可以以用户 id 进行排序，id 小的排前面，id 大的排后面。总之，最终一定会找出一个能区分出先后顺序的字段。

OT 是一套 理论框架，它是有多种实现的，像如上提到的 Delta 和 ShareDB 就是这个理论的不同落地方式。

可视化工具​

OT 算法可视化工具，通过该工具，可以清楚的看到整个文本的变化步骤。

Last updated on