协同编辑
现在的前端未来发展得从老生常谈的Vue, React等主流技术开始深入各种细分领域(webgl，视频剪辑，音视频直播等等)；而协同编辑也是一个比较火热的细分领域，面向企业用户很多时候业务场景都需要提供文档协同的能力，所以无论是使用开源的工具库或者自己实现，能够了解协同编辑的各种实现还是有不少的优势。
另外协同编辑确实也很有挑战性，毕竟多用户，实时，版本控制，操作回滚等这些词语堆在一起就已经头皮发麻；要设计一款高体验，高稳定的协同编辑绝对是有相当高的难度。
而目前主流协同编辑方案主要还是以OT或者CRDT方案为主；例如石墨文档、腾讯文档、飞书文档、Google Docs都是基于OT协同算法的，Atom编辑器使用的是CRDT协同算法；
剖析OT算法
一些思考
很多时候我在想类似git或者svn这些工具是否就是另外一种形式的协同编辑，只不过没办法那么实时，也没办法各种情况下都自动解决冲突，时常需要人工干预。
例如：
当远程和本地同时有一个commit的时候，我们大多时候就是要本地解决冲突，然后产生一个新的commit(补丁)，然后提交仓库，代码就到了一个大家都认可的一致状态（谁的代码逻辑都没有丢失，可喜可贺）。
假设有一个很智能的工具，能够在远端和本地也能自动合并解决任何冲突(无论提交之间的顺序如何)，而且跟你手动人工本地解决冲突后的代码也是完全的一致，那么：
哇塞，妈妈再也不用担心你跟别人的代码冲突了，世界瞬间美好了许多！甚至以后还能随时自动提交代码同步代码，这不就是实现一个简易版本的协同代码编辑了吗？
所以这个“某个智能合并工具”就是OT算法中，transform的核心，本质上也是遍历各种单个操作情况下如何自动合并，所以这个智能合并工具没有固定的实现的算法，真正的智能是靠我们开发去保证处理了所有的逻辑分支；而且也意味着只要不停有新的操作增加，整个“智能合并”的复杂度也会快速增加。
一般OT算法都是采用中央服务的处理方式，毕竟有中央服务器介入无论再多用户加入，都可以转变为Server和User的单对单交互，那么处理复杂度也会降低很多；
Transform
根据前面的思考，个人给transform下一个定义：
transofrm过程就是输入两个操作：A和B，并且会产出两个新的变形的操作A’，B’，两边分别应用A’，B’；能够让两边状态同步一致，无论这两个操作实际的先后顺序是怎样（因为直接应用操作十有八九出现冲突，就算不发生冲突也难以保证最后状态一致，所以trasform核心就是让原本的操作进行一些改变，而这种改变目标是可以让两个状态同步一致）。
而真实的核心公式：
A', B' = transform(A, B)
apply(apply(S, A), B') = apply(apply(S, B), A')用最简单的情况说明，对于文本字符串操作，可以简化为insert和del两个原子操作，如果加入一个nop就是3个原子操作，那么理解两两配对有9种方式组合。
假设原始字符串“123”，例如:
- A: insert(1, ‘a’)，B: insert(0, ‘b’); 经过transform后产生B’: insert(0, ‘b’) , A’: insert(2, ‘a’); 最终达到一致的状态：“b1a23”
- A: del(1)，B: insert(2, ‘b’) ; 经过transform后产生B’: insert(1, ‘b’), A’: del(1); 最终一致状态：“1b3”
还有其他7种情况，如果操作类型更多，这些组合更加多，大脑都要裂开。
但是至少这里可以明白transform操作实际就是一种自动解决冲突的方式，而且要保证双方应用修改后最终状态重归一致。
应用和交互
那么实际情况应该怎么应用OT算法，Client跟Server之间交互过程应该是怎样的，这里就参考ot.js来展开说说。
Client主要有三种状态：
有两个变量outstanding 和 buffer表示待确认的操作和缓存的本地操作
再举一个交互例子：
从全时序的操作：C -> A -> B -> D
但是服务端实际接收到的操作： A -> B，C的操作可能因为网络问题有延迟，所以实际服务器所看到的顺序跟全时序可能很不一样，但是仍然可以通过{A, B}和C上进行transform能够达到一个一致的状态:
A_, C_ = transform(A, C)
B_, C' = transform(B, C_)
applyServer(C')对于客户端在发送C操作后，连随又触发了D的操作，但是这个操作没有立即发送到服务端，因为C的操作要等待服务端的确认，也就是目前oustanding: C, buffer: D；
接着服务端A操作同步过来，在{C, D}和A基础上进行transform:
C_, A_ = transform(C, A)
D_, A' = transform(D, A_)
applyClient(A')这里客户端等效于同步了服务端S1版本的修改，客户端版本实际依据服务端版本同步进度来递增的。
核心菱形状态迁移图：
当在“S本地2”应用A”后，客户端就进入一个全新的状态St，这个时候等效服务端版本S1应用了Ct和Dt操作（红色路径）；所以在我们客户端版本号递增到S1后，原本的oustanding: C, buffer: D；也要替换为oustanding: Ct, buffer: Dt（感觉这一步最难理解）；所以下一次接收B操作，得跟{Ct, Dt}进行trasform。
而在发送本地操作的时候需带上客户端同步的版本，这样服务端才知道你本地当前同步的状态起点，才好对版本后续的操作进行transform。
Undo和Redo栈
对于操作的Undo栈，明显都要记录操作的逆操作，因为只要应用逆操作我们的状态就能回滚到上一个状态；但是在多人协作的环境下，有其他的新问题，例如：
- 我们能够Undo其他人操作吗？
无论在用户体验或者实现上，一般是不应该Undo其他人的操作，所以操作的Undo栈也都是只记录本地局部的操作即可。 - 来自服务端的操作对Undo和Redo栈的影响
对于本地操作直接把对应的逆操作加入Undo栈即可，但是对于来自服务端的操作得做更多的一些处理。
例如：
我们的本地Undo栈里面包含{C_r, D_r}，我们的状态会迁移到“S本地2”，当接收到服务端同步的A操作；“S本地2”的状态后应用A”，状态迁移到St；可以想象如果我们在St的状态使用undo操作，应该要沿着Dt_r -> Ct_r路线回滚到S1的状态才是合情合理的。所以我们undo栈里面的操作要从{C_r, D_r}转换为{Ct_r, Dt_r}。
所以这个时候就应该使用D_r 和 A”进行transform求得Dt_r，然后在此基础上跟C_r进行transform再获取Ct_r。
总结
目前还是纯理论上的分析，实际的工程上还有更多的问题，还需更多学习，下一遍探索多人协作的另外的解决方案–CRDT
参考
初探富文本之OT协同算法
On Consistency of Operational Transformation Approach
OT算法在协同编辑中的应用
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
