大家好，我是前端西瓜哥。今天我们就来说说什么是OT算法。OT的英文全称是Operationaltransformation，是一种处理协同编辑的算法。常用于实现协同文档的底层算法，支持多个用户同时编辑文档，不会因并发修改而产生冲突，导致结果不一致或数据丢失。冲突处理方式假设A和B同时在编辑同一个内容，我们处理冲突的方式是：加锁。用户A编辑时，文档被锁定，只有用户A可以更新。用户B不能编辑，或者编辑后提交的修改被服务器丢弃。覆盖。最后修改的人将完全使用他的修改，而其他人较早的修改将被丢弃。用户自己处理冲突。就像gitmerge引起的冲突一样，它会提示同时修改了哪个地方，让merge手动选择使用哪个修改。使用共识算法。比如我们要介绍的OT算法，可以让用户对算法处理进行编辑调整，在多个客户端上生成一致的修改结果。用于在线协作文档。加锁体验太差，一个人编辑还要等别人。覆盖导致用户的修改来回相互覆盖，辛苦编辑的内容突然被别人覆盖，心情郁闷。自己处理冲突需要额外的操作步骤和成本，实时性差，不适合高频同时修改的场景。共识算法是最好的选择，也是最人性化的，但它给实现带来了复杂性。一致性问题我们先来看一下不使用OT导致的冲突。假设用户A和用户B同时编辑同一个文档，文档内容为“12”。用户A在末尾添加一个字符“A”，这个修改先应用到本地，内容变成“12A”，然后客户端向服务端发送数据insert(2,“A”)，表示位置在位置2插入“A”。服务器会将修改消息推送给其他客户端，但这需要时间。用户B在收到推送消息之前，也在“12”的末尾添加了内容“B”，在本地变成了“12B”，并向服务器提交了修改后的insert(2,“B”)描述。用户B收到insert(2,"A")消息，应用后，“12B”变为“12AB”。用户A收到insert(2,"B")消息，应用后，"12B"变为"12BA"。结果，用户A看到的是“12BA”，用户B看到的是“12AB”，这是不一致的，也是出乎意料的。使用OTOT算法可以解决一致性问题，我们来看看OT是干什么的。同样，原始内容是“12”。用户A在末尾加上“A”，本地变成“12A”，发送insert(2,A)，这个操作算作OA。用户B在末尾加上“B”，本地变成“12B”，发送insert(2,B)，这个操作算OB。用户A收到OB，执行transform(OA,OB)，得到修正后的操作insert(3,B)，记录为OB'。与OB相比，它把插入位置从2修正为3，所以“12A”就变成了“12AB”。用户B收到OA，同样执行transform(OA,OB)得到校正操作insert(2,A)，记录为O1'，内容由“12A”变为“12AB”。转换方法产生OA'和OB'。最后，用户A和用户B看到的是同一个“12AB”。这里的核心在于transfer方法，可以修改操作。transform没有固定的实现方式，根据实际需要来实现。这是经典菱形的示意图。从起始版本T开始，它接受两个并发操作A和B。我们使用transform方法生成A'和B'。我们有：S+A+B'=TS+B+A'=T这样，从S得到相同的T，保证了一致性。下面使用ot.js库来演示从'12'到'12AB'的过程。consts='12';//原文(version1)//insert'A'atposition3constoA=newTextOperation().retain(2).insert('A');//经过以上操作得到结果'12A'(version2)constt1=oA.apply(s);//收到oB操作：在位置2插入'B'constoB=newTextOperation().retain(2).insert('B');//transform得到正确的[oA',oB']//我们只这里需要oB'，修正为在位置3插入'B'const[oAp,oBp]=TextOperation.transform(oA,oB);//ApplyoB'，结果为：12AB(version3)constt2=oBp.apply(t1);在线演示链接是：https://codesandbox.io/s/b8ds8h。transform操作发生在服务器端：它将一个基于某个版本的并发操作对象转换为一个串行操作。它也发生在客户端。本地修改还没来得及提交，就收到了服务器的推送。如果想深入研究OT算法，可以考虑参考ot.js库的代码实现，其中还自带了OT可视化过程。https://github.com/Operational-Transformation/ot.js/。结尾OT算法可以实时保证多个客户端数据的一致性，广泛应用于协同编辑场景。
