关于javascript:OT算法浅析

协同编辑

当初的前端将来倒退得从陈词滥调的 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”，例如:

1. A: insert(1, ‘a’)，B: insert(0, ‘b’); 通过 transform 后产生 B ’: insert(0, ‘b’) , A’: insert(2, ‘a’); 最终达到统一的状态：“b1a23”
2. 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 算法在协同编辑中的利用