乐趣区

关于javascript:OT算法在协同编辑中的应用

jiezi

1 背景

疫情的起因推动了在线面试的利用场景，除了音视频通话技术，对于 IT 行业的面试，必不可少的要写写代码，所以其中一项重要性能是协同编辑，上面就让来剖析一下协同编辑性能的实现计划和 OT 算法的利用。

2 协同编辑场景

协同编辑的场景是在同一房间内，所有人都可同时操作编辑器内容，要害是让所有人看到的内容是统一的，这外面波及的技术就包含了 web 编辑器，音讯的播送和保障内容统一的算法，咱们明天探讨的是保障内容统一的算法。

让咱们看下实现保障内容统一的一些思路：

  • 思路 1：全量笼罩
    这种办法就是简略粗犷，每次都把编辑器的内容全量播送给其他人，这样在多人同时操作的时候就会有互相笼罩的景象，导致无奈同时编辑，所以是不可取的。
  • 思路 2: 加操作锁
    既然同时编辑会有互相笼罩的问题，那就加个操作锁，每次扭转之前之前先抢一下锁，而后再扭转，这种思路不是实现同时编辑，而是强制不同时编辑，会导致体验很差，明明输出了然而因为没有抢到锁而不失效。
  • 思路 3: 增量操作
    既然全量传递会互相笼罩，那就增量的传递，只传递这次扭转了什么，比方我在第 2 个字符插入了 ’xx’ 等等，这样尽管不会全量笼罩了 然而同时操作会导致内容不统一，举例如下图：

两个用户，开始的内容都是 AAAZ，同时操作，通过传递和转换之后两端的内容就不统一了。
OT 协同算法的外围就是解决该问题。

3 OT 算法

OT 算法的关键技术点总结为四点：定义原子操作、版本确认机制、操作转换、客户端状态转移，上面就别离解说。

3.1 定义原子操作

OT 算法中对于内容的操作形象为三种：

  • Retain 放弃操作，用大于 0 的数字示意 记录要放弃的字符数量
  • Insert 插入操作，用插入的字符串示意
  • Delete 删除操作，用小于 0 的数字示意 - n 就是删除 n 个字符

每次对于整个文本的解决都能够用一个有上述 3 中原子操作的数组示意。上面我举一些直观的例子。

  • “” -> “A” , 操作数组为 [“A”] 只有一个 Insert
  • “A” -> “AB” , 操作数组为 [1,”B”] 放弃一个字符, 而后插入 B
  • “ABC” -> “AB” , 操作数组为 [1,-1,1] 放弃一个字符, 删除一个字符，而后再放弃一个字符

编辑器和服务端之间传输的就是这种操作数组，当收到之后会将其转换为操作对象，定义如下：

function TextOperation () {this.ops = [];
    this.baseLength = 0;
    this.targetLength = 0;
  }

其中除了 this.ops记录操作数组之外，还减少了两个属性 this.baseLength 和this.targetLength。

  • this.baseLength 示意该操作前文本的长度，会用于操作转换时的校验。
  • this.targetLength 示意该操作利用在文本后，文本的长度。

举个简单的例子：

  • “123456789” -> “123A89″ , 操作数组为 [3,”A”,-4,2], 转成的操作对象为

    {ops: [3,"A",-4,2],
baseLength: 9,
targetLength: 6
}

3.2 版本确认机制

在 OT 协同算法中，服务端作为一个记录文档内容和所有历史版本操作的核心，当有新的客户端建设连贯时首先进行一次同步，之后客户端每次发送一个操作时 还要同时发送本次操作时基于什么版本进行的更新，这样服务端会从该版本开始进行操作转换。客户端每次的操作不能间接批改以后的版本，而是要收到服务端的确认之后能力进行版本的更新，因为客户端不记录所有历史的操作和版本的对应关系，通过未确认的状态来判断是否须要操作转换。举例如下图：

3.3 操作转换

操作转换是 OT 算法的外围，它的外围公式是：

[A`,B`]  = transform(A,B)
    
apply(apply(S, A), B') = apply(apply(S, B), A')

A和 B 两个操作，通过转换之后生成A` 和B`, 使得对于雷同的内容 S 通过 A 和 B ` 的利用后果 等于 通过 B 和 A ` 的利用后果, 具体 transform 代码参见开源我的项目：ot.js。

这里有一个菱形表示法用于图形化的形容 OT 的操作转换过程：

咱们能够这样了解，每一个点是一个状态，每一条边是一个操作，右边的永远是客户端的操作，
左边的永远是服务端的操作，两者在雷同的状态下，客户端通过 A 和 B ` 之后和服务端通过 B 和 A ` 之后达到雷同的状态。这是最根本的一个版本抵触的菱形表示法，理论利用中会有更多的版本抵触，应用菱形表示法会把整个过程展现的很直观。

3.4 客户端状态转移

客户端每次操作不会立即减少版本，而是要期待服务端的确认后减少版本，同时客户端的操作在没有被服务端确认之前，是不会持续发送新的操作，而是将要发送的操作进行缓存，期待确认后再进行发送，这里客户端就保护了三种状态，除了客户端的发送之外，还可能从服务端承受操作，不通的状态客户端会有不同的解决。

  • Synchronized，曾经同步状态，客户端没有待确认的操作。
  • AwaitingConfirm，期待确认状态，客户端有期待服务端确认的操作。
  • AwaitingWithBuffer，期待确认状态，并且还有待发送的操作。

三种状态的转移如下图所示：

4 OT 场景剖析

以上解说了 OT 算法的关键技术，上面就针对须要进行 OT 操作的场景进行剖析。

4.1 客户端批改一次，服务端批改一次抵触

此时客户端的状态是 AwaitingConfirm，而收到了服务端下发的操作，菱形表示法如下：

解释：客户端进行了 A 操作，服务端先进行了 B 操作，客户端进行 OT 之后 利用B`, 期待的状态变为
A`, 而服务端收到 A 之后，同样与 B 进行 OT，而后利用A`。

4.2 客户端批改一次, 服务端批改屡次抵触

此时客户端的状态是 AwaitingConfirm，相比于 4.1 的状况，在收到批改确认之前，间断屡次收到服务端的下发，菱形表示法如下：

客户端先后 利用B1` 和B2`, 能够承受更多的批改。

对于服务端来说，当收到客户端的操作 A 时，是间断进行转换，菱形表示法如下：

让操作 A 间断的和操作 B1 和 B2 进行转换，最终利用A“。

4.3 客户端批改屡次, 服务端批改一次抵触

此时客户端的状态是 AwaitingWithBuffer，客户端变动的菱形表示法如下：

客户端进行了 A 操作后，还执行了 A2 操作，所以第一次 OT 之后 状态 C 不是最终状态，而是一种长期状态。B` 和 A2 就要持续 OT 计算，达到状态 D。同时留神这里从期待发送 A2 变成了期待放 A2`。
服务端则是先收到 A 操作后 利用A`, 而后收到A“。

5 总结

OT 算法和一整套残缺的设计，的确解决了协同操作的问题，本文通过剖析纯文本的协同，讲清楚最外围的关键技术点。对于更简单的场景则须要设计的原子操作和操作转换算法也会更加的简单。比方腾讯的在线文档，除了文本之外，还须要同步款式、图片元素等等。留一个问题：既然 OT 算法能够解决协同操作问题，为什么在应用腾讯在线 excel 的过程中发现多集体同时操作一个表格单元的时候，会呈现互相笼罩的问题？

如果感觉有播种请关注微信公众号 前端良文 分享前端开发中的干货知识点。

退出移动版