OT冲突算法 - wangshengliang

读写锁
diff-patch方式
自动合并冲突算法
1. OT解决方案
2. CRDT解决方案

OT 算法的全称为 Operational Transformation，直接翻译就是 操作转换：

操作
转换

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

发展史

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

1. 操作#

这是 OT 算法中的第一个概念，准确的来说，其实是 针对操作的一种描述。文档的每一次修改都可以看作是一个 原子化的操作，然后通过某种方式去描述该操作。这里以 Quill 中的 Delta 为例：

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

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

插入一个加粗的 "Gandalf"
插入一个普通的文本，文本信息为 " the "
插入一个颜色为 #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

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

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

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

2. 转化#

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

一个转换的具体示例

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

现在假设有两个用户：

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

整个并发场景如下：

             初始状态
               ↓
        ┌──────────────┐
        │     abc      │
        └──────────────┘
            /       \
           /          \
A: Insert(1, 'X')     B: Insert(0, 'Y')
        ↓                    ↓
     文档 aXbc            文档 Yabc
        ↓                    ↓
  A 收到 B 的操作        B 收到 A 的操作
        ↓                    ↓
      OT 变换               OT 变换
        ↓                    ↓
应用 B' = Insert(0, 'Y')   应用 A' = Insert(2, 'X')
        ↓                    ↓
 ┌──────────────┐     ┌──────────────┐
 │   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 算法可视化工具，通过该工具，可以清楚的看到整个文本的变化步骤。

-EOF-