58同城-OT算法在58云视中的应用

原创杨益良 58技术

导读

58云视是58自研的一款音视频通话系统，目前广泛应用在面试场景中，面试场景有一项重要功能是协同编辑，下面就让来分析一下协同编辑功能的实现方案和OT算法的应用。

协同编辑场景

协同编辑的场景是在同一房间内，所有人都可同时操作编辑器内容，关键是让所有人看到的内容是一致的，这里面涉及的技术就包括了web编辑器，消息的广播和保证内容一致的算法，我们今天讨论的是保证内容一致的算法。

让我们看下实现保证内容一致的一些思路：

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

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

OT算法

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

3.1 定义原子操作

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

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

每次对于整个文本的处理都可以用一个有上述3中原子操作的数组表示。下面我举一些直观的例子。

“” -> “A” ,操作数组为 [“A”] 只有一个Insert
“A” -> “AB” ,操作数组为 [1,“B”] 保持一个字符,然后插入B
“ABC” -> “AC” ,操作数组为 [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`之后达到相同的状态。这是最基本的一个版本冲突的菱形表示法，实际应用中会有更多的版本冲突，使用菱形表示法会把整个过程展示的很直观。