协同编辑OT算法server端实现原理

OT算法解决协同编辑问题已经是一项较为常见的技术，OT算法本身很简单，客户端A对文档做了OP1操作，客户端B对文档做了OP2操作，OT算法提供一个函数transform，描述如下：

transform(OP1, OP2){
    ...
    return { OT(OP1, OP2), OT(OP2, OP1) }
}

OT(OP1, OP2)：对OP2的OT变换
OT(OP2, OP1)：对OP1的OT变换
使得 OP1 * OT(OP1, OP2) === OP2 * OT(OP2, OP1) 

那么，生产环境中OT算法是如何应用的呢？首先服务端对每个文档维护如下数据结构:

alt

维护一份当前文档内容，记录下对该数据结构初始化后所有的OP操作，记录下当前访问的用户，用户协同编辑的时序图如下：

alt

上诉时序图描述的是A客户端和B客户端对同一个版本的文档进行协同编辑，那如果A客户端对文档进行了多次编辑，B客户端因为网络原因没有及时同步到A客户端的OP操作，继续在老版本编辑并向服务端发送OP操作会出现什么情况呢？OT算法通过链式反应法则解决对老版本OP操作的问题，链式反应法则描述如下：

Vm: m版本文件内容
OPm: 服务器记录的对m版本的操作
BOPm: B客户端对Vm的修改
DOOP: 服务器OT变换后执行操作
REOP：B客户端OT变换后执行操作

Vm * OPm * OT(OPm, BOPm) = Vm * BOPm * OT(BOPm, OPm)
DOOP = OT(OPm, BOPm)
REOP = OT(BOPm, OPm)
{ Vm * OPm * DOOP * OT(DOOP, OPm+1) =
Vm * OPm * OPm+1 * OT(OPm+1, DOOP) =
Vm * BOPm * REOP * OT(DOOP, OPm+1) }
DOOP = OT(OPm+1, DOOP)
REOP = REOP * OT(DOOP, OPm+1)

OT算法有大量字符串拼接的操作，对较大的文档协同编辑存在一定的性能问题

alt