初探富文本之OT协同算法.md

初探富文本之OT协同算法

OT的英文全称是Operational Transformation，是一种处理协同编辑的算法。当前OT算法用的比较多的地方就是富文本编辑器领域了，常用于作为实现文档协同的底层算法，支持多个用户同时编辑文档，不会因为用户并发修改导致冲突，而导致结果不一致甚至数据丢失的问题。

描述

从名字就可以看出来，OT协同算法的重点在于操作Operation与转换Transformation，简单来说，操作Operation指明了所有的操作必须原子化，例如在第N个位置插入了某个字符，在第M个位置删除了某个字符，类似于这样的所有的操作必须能够原子化地表示，转换Transformation指明了所有的操作必须要有转换的方案，例如我在第N个位置插入了字符，你在N+2个位置同时插入了字符，假设我的操作比较靠前，由于需要同步操作，那么在我本地执行你的Operation时就必须将其转换，插入的位置就必须增加我插入字符的长度，这就是大概的OT所需要的条件，当然具体的算法要远远比这个复杂，并且存在例如同步调度、Undo/Redo、光标、稳定性、可溯源等等问题需要一并解决。本文不涉及具体的协同算法，只是探讨了OT协同算法的基本思路，当前也有比较成熟的OT协同框架例如ShareDB等，可以相对简单地接入，当然只是相对而言，成本也是不低的。

在讨论具体的协同算法之前，我们探究一下为什么要有协同算法，如果没有协同算法的话会出现什么问题，以及具体会出现问题的场景。那么假如我们有一个在线的文档应用，而我们是一个团队，我们有可能对同一篇文档进行编辑，既然我们会同时编辑，那么就有可能产生冲突。假设文档此时的内容为A，此时U1和U2两位用户同时在编辑，也就是说这两位都是从文档的A状态开始编辑，当U1编辑完成之后，文档状态是B，U1对文档进行了保存，此时U2也写完了，文档状态是C，U2也对文档进行了保存，那么此时文档的状态就是C了，由U1编写的A -> B状态的内容修改便丢失了，为了解决这样的问题，通常有以下几个方案。

乐观锁

乐观锁，主要就是一种对比于悲观锁的说法，因为乐观锁的操作过程中其实没有没有任何锁的参与，严格的说乐观锁不能称之为锁。乐观锁总是假设最好的情况，每次去拿数据的时候都认为别人不会修改，所以不会上锁，可能需要在更新的时候会判断一下在此期间别人有没有去更新这个数据提示一下，或者干脆不会给予任何的提示信息。

那么具体到文档编辑上边，我们可以乐观地认为永远不会有两个人同时编辑同一篇文档，现实中也可能有这种情况，比如团队中每个人只负责几篇文档，其他人不需要也没有权限去编辑自己负责之外的文档，那么基于这种要求，我们可以乐观地认为永远不会出现冲突的问题，那么自然也就不需要对文档的管理做任何限制了，只需要完整地提供编辑能力即可。

悲观锁

悲观锁，顾名思义是基于一种以悲观的态度类来防止一切数据冲突的方式，其以一种预防的姿态在修改数据之前把数据锁住，然后再对数据进行读写，在其释放锁之前其他的任何人都不能对数据进行操作，直到前面一个人把锁释放后下一个人才可对数据进行加锁，继而才可以对数据进行操作，通过这种方式可以完全保证数据的独占性和正确性。

那么具体到文档编辑上边，我们可以对同一篇文档的编辑操作权限进行加锁，这样就可以保证同一时间只有一个人可以对文档进行编辑，其他人只能等待，直到前面的人把文档编辑完成并且释放锁之后，下一个人才可以对文档进行编辑，当然也可以开一个口子允许强行抢占并且将被抢占者的现场存储下来，相当于将一个并发操作压成了线性操作，这样就可以通过独占的方式保证文档的正确性，避免文档的内容冲突与丢失。

自动合并

自动合并，文档内容自动合并以及冲突处理的方式也是一个可行的方案，类似于Git的版本管理思想，可以对提交的内容进行diff差异对比、merge合并等操作，也可以在出现无法解决的冲突时出现时交给用户主动处理，GitBook是采用这种方式解决冲突问题的。

协同编辑

协同编辑，可以支持多个用户同时编辑文档，不会因为用户并发修改导致冲突，而导致结果不一致甚至数据丢失的问题。协同编辑重点在于协同算法，主要有Operational Transformation(OT)与Conflict-free Replicated DATA Type(CRDT)两种协同算法。协同算法不需要是正确的，其只需要保持一致，并且需要努力保持你的意图，就是说协同算法最主要的目的是在尽可能保持用户的意图的情况下提供最终的一致性，重点在于提供最终一致性而不是保持用户的意图。当前石墨文档、腾讯文档、飞书文档、Google Docs都是基于OT协同算法的，Atom编辑器使用的是CRDT协同算法。

OT协同算法

Operational Transformation(OT)协同算法的核心思想是将文档的每一次修改都看作是一个操作，然后将这些操作进行转换来合并，最终得到文档内容。OT算法的目的是在尽可能保持用户意图的情况下，保持文档的最终一致性，举个例子，当A和B同时在文档的L处插入了不同的字符，那么谁插入的字符在前协同算法并不关心，其只需要尽可能地根据一定策略例如时间戳来判断究竟是谁的字符在前，但是最终计算出的结果即究竟谁的字符在前并不影响协同算法，其关心的重点在于经过协同算法将用户产生的Op调度之后，在每个人面前呈现的文档内容是绝对一致的，这就是保持文档的最终一致性。从功能的角度上说，协同算法保证的是在多人同时在线编辑的情况下，由于每个人提交的内容是不一样的，就需要通过协同算法的调度，使得每个用户最终都能看到一样的内容。

在了解OT协同算法之前，我们也可以了解一下OT协同算法与CRDT协同算法的主要区别。首先OT与CRDT都提供了最终一致性，这也是协同编辑的最终目标，但是这两种方案达成这一目标的方式不一样：

• OT操作转换通过操作Operation转换Transformation来做到这一点，终端所进行的操作O通过网络传输，其他终端在收到操作O后需要进行转换T，之后才可以应用到文档上，最基础的OT是通过转换索引位置以确保收敛。
• OT通常必须要有中央服务器进行协同调度。
• OT通过算法处理编辑冲突的问题，增加了时间复杂度。
• CRDT无冲突复制数据类型则是通过数据结构来做到这一点，CRDT有两种实现方式，基于状态的CvRDT收敛复制数据类型和基于操作的CmRDT可交换复制数据类型。CvRDT是将各个副本进行合并，进行多少次合并或以何种顺序进行合并并不重要，所有副本都会收敛。CmRDT则具有可交换的操作，因此无需转换操作即可正确应用这些操作。
• CRDT更适合分布式系统，可以不需要中央服务器。
• CRDT通过数据结构保证了编辑的无冲突，增加了空间复杂度。

基本原理

回到我们要介绍的OT协同，我们在这里不涉及具体的协同算法，我们的侧重点在于实现OT的动机，例如协同为什么不是直接应用协作者的Op即可、为什么要有操作变换、如何进行操作变换、什么时候能够应用Op等等，当我们知道了一个技术的来由与动机时，其实现甚至都有可能跃然纸上了。那么在这里我们从A、B两者同时编辑同一段文本的基本操作开始，探讨一下OT协同为了保持一致性究竟做了什么。描述一篇文档的方式有很多，最经典的Operation有quill的delta模型，通过retain、insert、delete三个操作完成整篇文档的描述，还有slate的JSON模型，通过insert_text、split_node、remove_text等等操作来完成整篇文档的描述。在这里我们假设有一个加粗的操作Bold(start, end)，一个插入的操作insert(position, content)来描述整篇文档。

那么此时，我们假设原始文本为12，用户A、B分别进行了一个加粗操作一个插入操作。

• 用户A进行了一个Bold(1, 2)操作，A本地需要首先应用这个操作，由此A本地的文本是(12)，为了简单起见，加粗用()表示。
• 用户B同时也进行了一个insert(2, "B")操作，B本地需要首先应用这个操作，由此B本地的文本是12B。
• 此时需要同步Operation，用户A收到了用户B的insert(2, "B")操作，A从本地的(12)应用之后，得到了(12)B。
• 用户B收到了用户A的Bold(1, 2)操作，B从本地的12B应用之后，得到了(12)B。

看起来并没有发生任何冲突，A、B最终都获得了一致的文档内容(12)B，当然事情并没有那么简单，我们继续往下看看其他的情况。为了简单起见，我们假设目前的只有insert(position, content)这个操作，从定义也能够明显的看出来，这个函数的意思是在position处插入content文本。

那么此时，我们假设原始文本为123，用户A、B分别进行了一个插入操作。

• 用户A进行了一个insert(2, "A")操作，A本地需要首先应用这个操作，由此A本地的文本是12A3。
• 用户B同时也进行了一个insert(3, "B")操作，B本地需要首先应用这个操作，由此B本地的文本是123B。
• 此时需要同步Operation，用户A收到了用户B的insert(3, "B")操作，A从本地的12A3应用之后，得到了12AB3。
• 用户B收到了用户A的insert(2, "A")操作，B从本地的123B应用之后，得到了12A3B。

经过上述协同结果是，用户A看到的内容是12AB3，用户B看到的内容是12A3B，内容不一致，没有成功地保证最终一致性。那么根据OT的Operational Transformation这个名字，我们来看上边的协同，发现我们只是做了Operation的同步，并没有做Transformation去转换，所以我们这是一个不完整的协同，当然也就不能完整地覆盖各种Case。

我们再来看看上边的协同方法有什么问题，实际上我们只是对我们自己本地的内容应用了从其他位置同步过来的操作，而这个操作是失去了上下文Context的，也可以称为语境，具体来说，我们以A为例，当我们接受到B的insert(3, "B")操作时，这个Op实际上是在原始文本为123这个文本为上下文的基础上进行的Op，而此时我们本地的文本内容是12A3，而此时去执行B的Op就由于缺失了上下文而导致出现了问题，所以此时我们就需要OT的Transformation来将其进行转换，当协作者变更到来时，我们需要变换操作以适应当前上下文，才能直接应用，而调整的过程，则基于当前文档已经发生的变更来完成。

Ob' = OT(Oa, Ob)
Oa' = OT(Ob, Oa)

而由上边上下文的基本想法我们可以得到OT协同的基本思路是，将每个用户的操作都转换成相对于原始文本的操作，这样就可以保证最终一致性。具体来说，假设文档的初始状态为S，以同步时的A用户为例我们此时应用了Oa也就是insert(2, "A")这个操作，而此时恰好我们又收到了B的Ob也就是insert(3, "B")操作，那么我们此时要应用Ob的时候，就需要进行转换，也就是Ob' = OT(Oa, Ob)，注意此时我们是将Oa也作为参数传入了进去，也就是说此时我们是通过Oa与Ob来作为参数算出来Ob'的，那么也就是说我们此时的上下文为S，同理对于B来说我们进行Oa' = OT(Ob, Oa)计算要应用的Oa'时，所处的上下文同样也是S，那么这样就将操作转换成了相对于原始文本的操作了，从而得到一致性。换句话说，也可以这么理解，Ob' = OT(Oa, Ob)就相当于我们将原本已经执行的Oa撤销掉，然后结合Oa + Ob从来得到Ob'，将两者的Op结合起来再应用到S上，对于Oa' = OT(Ob, Oa)同理，那么此时无论A还是B执行的上下文都是S，从而得到一致性。

落实到具体实现上，我们需要定义一套算法来完成这个Transformation，下面我们就简单实现一下，在这里的实现很简单，因为我们定义的操作只有insert，假如是上文提到的retain、insert、delete三种操作来描述文档的话，就需要实现3x3 = 9种变换操作，在这里我们对于两个insert的位置进行变换，如果此时新来的cur op插入的位置是在先前的pre op之后的，那么说明在原来的内容上已经添加了内容，那么我们就需要将插入的位置后移pre op插入文本的长度。

function transform(pre, cur) {
  // 在`pre`之后插入，需要向后移动`cur`作用的`position`
  if (pre.insert && cur.insert && pre.insert.position <= cur.insert.position) {
    return { 
        insert: { 
            position: cur.insert.position + pre.insert.content.length, 
            content: cur.insert.content 
        }
    };
  }
  // ...
  return cur;
}

此外还记得之前说的OT的最终目的是保持最终的一致性，那么落实到这里，假设我们的两个insert操作都是同时在2位置插入一个不同的字符，那么在变换的时候我们需要决定究竟是谁在前，因为这两个操作的时序是一样的，也就是说可以认为是同时发生的，那么就必须制定一个策略来决定谁的字符在前，那么我们就通过第一个字符的ASCII来决定究竟是谁在前，这只是一个简单的策略，也就是所谓的尽可能保持用户意图的情况下，保持文档的最终一致性。

// 如果两个`insert`的位置相同，那么我们需要通过第一个字符的`ASCII`来决定谁在前
if(pre.insert.position === cur.insert.position) {
    if(pre.insert.text.charCodeAt(0) < cur.insert.text.charCodeAt(0)) {
        return { 
            insert: { 
                position: cur.insert.position + pre.insert.content.length, 
                content: cur.insert.content 
            }
        };
    }
    return cur;
}
// A: 12  insert(2, A) 12A   oa
// B: 12  insert(2, B) 12B   ob
// A: 12A insert(3, B) 12AB  ob'
// B: 12B insert(2, A) 12AB  oa'

应用上边的transform函数，我们可以再来看一下上边的例子。那么此时，我们假设原始文本为123，用户A、B分别进行了一个插入操作。

• 用户A进行了一个insert(2, "A")操作，A本地需要首先应用这个操作，由此A本地的文本是12A3，可以看作是2后边插入了A。
• 用户B同时也进行了一个insert(3, "B")操作，B本地需要首先应用这个操作，由此B本地的文本是123B，可以看作是3后边插入了B。
• 此时需要同步Operation，用户A收到了用户B的insert(3, "B")操作，经由变换transform(insert(2, "A"), insert(3, "B")) = insert(4, "B")，A从本地的12A3应用之后，得到了12A3B。
• 用户B收到了用户A的insert(2, "A")操作，经由变换transform(insert(3, "B"), insert(2, "A")) = insert(2, "A")，B从本地的123B应用之后，得到了12A3B。

我们最终A与B都得到了12A3B，完成了最终一致性的操作，这就是OT的基本原理，那么接下来这个典型的菱形示意图也就好理解了，

      S  
 Oa  / \  Ob
    /   \
    \   /
 Ob' \ /  Oa'
      T

Ops

前边的例子是协同的双方只进行了一个Op，那么实际上我们平时写文档的时候，大概率是会有多个Op的，那么对于多个Op同时出现的情况，OT又应该如何处理。首先要明确一点，OT的核心思想是不变的，也就是Operational Transformation，那么对于多个Op，我们的核心关注点就应该在如何transform。另外在刚接触OT的时候，我有一个想法，既然是多个Op那么在传输的时候将其合并为一个Op就可以了，后来仔细想了一下这样是不行的，首先有些操作确实是可以合并的，比如在同一个位置增加了一些文字，那么这些操作都可以归并为insert，相当于延时收集一下操作，但是有些操作就是不能合并的，比如在A位置写了一些文字，又在B位置写了一些文字，这样显然是不能合并的，除非是把整篇文档发送出去，那这就是State-based CRDT的范畴了，此外这样会导致协同的基础也就是原子化的Op失效，原子化失效了后边的变换、逻辑时序就都会出问题，那这是肯定不行的。

回到对多个Op做transform的问题上，假如此时A做了Oa1与Oa2两个Op，假设我们此时是在A的同步过程，也就是A需要在当前的基础上应用B的Op，那么依照于前文的Ob' = OT(Oa, Ob)，我们用当前最新的Oa2作为参数进行变换，也就是即将要应用的Ob' = OT(Oa2, Ob)，那么此时我们可能会看出来问题，Oa1的Op信息丢失了，那么即将要Ob'有可能是错误的，而且我们此时要应用的上下文并不是文档的初始内容S，而是进行了Oa1操作之后的S'，这就使我们之前总结的方案出了问题，出现了内容的分叉。那么如何纠正这个问题呢，很简单，我们应该让Ob做两次变换，也就是说我们需要Ob'' = OT(Oa2, OT(Oa1, Ob))，这样才可以将上下文回归到S，才能获得可以立即应用的正确的Op操作。对于这个示例，其也可以用经典的棱形来表示，两个客户端需要关注最外层的两条线，其实也可以看出来当客户端的操作比较多的时候，菱形会无限拓展。

              S
        Oa1 /   \ Ob
           /     \ 
       /   \     /
  Oa2 / Ob' \   / Oa1'
      \     / 
  Ob'' \   / Oa2'
         T

那么我们不妨再总结一下，实际上两个OP在进行transform时，本质上就是一个OP向另一个OP问询信息，并且根据信息来调整自己，那么只有产生自相同上下文，彼此通信的空间信息才是彼此信赖、可理解的，也才敢使用彼此的信息调整自己。那么我们可以总结出来:

• 可以做变换的前提是即将要变换的两个参数应该是产生自同一上下文的，例如上边的OT(Oa1, Ob)，当Ob'产生之后，此时Oa2和Ob'都是经过了Oa1操作之后得到的，也同属于同一上下文，那么OT(Oa2, Ob')的变换操作也是可行的。
• 可以应用的前提是Op产生自同一上下文，例如上边的Ob''，即将应用时可以追溯到其产生的上下文的位置是S，也就是文档的初始状态，而产生Oa1和Oa2两个操作的初始状态也是S，那么应用Ob''的操作也是可行的。

那么假如例子再复杂一些，A与B分别都产生了两个Op，那么该如何处理呢，那么此时就是去查询，找到可以做OT的OP，逐个进行变换，直到OP变换到当前上下文可用。我们假设S(x,y)表示在位置(x,y)的文档状态，x, y分别表示A, B两个客户端的状态，A(x,y)表示客户端A在状态S(x,y)下产生的操作，B(x,y)表示客户端B在状态S(x,y)下产生的操作，那么:

S(x,y) o A(x,y) = S(x+1,y)
S(x,y) o B(x,y) = S(x,y+1)

• 文档的初始状态为S(0,0)。
• A执行了操作A(0,0)，状态更新为S(1,0)，再执行A(1,0)，状态更新为S(2,0)
• B执行了操作B(0,0)，状态更新为S(0,1)，再执行B(0,1)，状态更新为S(0,2)。
• 在B中，A(0,0)基于B(0,0)做OT，得到可在状态S(0,1)上应用的A(0,1)，可得S(1,1)。
• 在B中，A(0,1)基于B(0,1)做OT，得到可在状态S(0,2)上应用的A(0,2)，可得S(1,2)。
• 在A中，B(0,0)基于A(0,0)做OT，得到可在状态S(1,0)上应用的B(1,0)，可得S(1,1)。
• 在A中，B(1,0)基于A(1,0)做OT，得到可在状态S(2,0)上应用的B(2,0)，可得S(2,1)。
• 在B中，A(1,0)基于B(1,0)做OT，得到可在状态S(1,1)上应用的A(1,1)，可得S(2,1)。
• 在A中，B(0,1)基于A(0,1)做OT，得到可在状态S(1,1)上应用的B(1,1)，可得S(1,2)。
• 在B中，A(1,1)基于B(1,1)做OT，得到可在状态S(1,2)上应用的A(1,2)，可得S(2,2)。
• 在A中，B(1,1)基于A(1,1)做OT，得到可在状态S(2,1)上应用的B(2,1)，可得S(2,2)。

可以通过图来比较直观地观察两者究竟是如何进行的操作，当然实际上这也是多个菱形，只不过摆正了而已，两个客户端需要关注最外层的两条线。当然上述流程以及图中表现的是一个完整的状态变换，对于A和B客户端各自的变换来说，并不是都需要完整地进行所有状态的变换的。对A而言，我们首先需要根据B(0,0)与A(0,0)变换出B(1,0)，再根据B(1,0)与A(1,0)变换出B(2,0)，然后A(0,0)与B(0,0)变换出A(0,1)，A(1,0)与B(1,0)变换出A(1,1)，之后B(0,1)与A(0,1)变换出B(1,1)，最后由B(1,1)与A(1,1)变换出B(2,1)，这样就得到了S(2,0) -> S(2,2)所需要的两个Op - B(2,0) B(2,1)。同理，对于B而言需要A(0,0)与B(0,0)变换出A(0,1)，A(0,1)与B(0,1)变换出A(0,2)，然后B(0,0)与A(0,0)变换出B(1,0)，B(0,1)与A(0,1)变换出B(1,1)，之后A(1,0)与B(1,0)变换出A(1,1)，最后由A(1,1)与B(1,1)变换出A(1,2)，这样就得到了S(0,2) -> S(2,2)所需要的两个Op - A(0,2) A(1,2)。

S(0,0)  →  A(0,0)  →  S(1,0)  →  A(1,0)  →  S(2,0)
   ↓                     ↓                     ↓
B(0,0)                B(1,0)                B(2,0)
   ↓                     ↓                     ↓
S(0,1)  →  A(0,1)  →  S(1,1)  →  A(1,1)  →  S(2,1)
   ↓                     ↓                     ↓
B(0,1)                B(1,1)                B(2,1)
   ↓                     ↓                     ↓
S(0,2)  →  A(0,2)  →  S(1,2)  →  A(1,2)  →  S(2,2)

对于A、B双方，最终我们都得到了S(2,2)的状态，请注意我们在客户端的起始位置是S(2,0)与S(0,2)，所以我们不能在以S(1,1)为基准的基础上做A(1,0)与B(0,1)的OT，而我们实际应用的Op如下所示，其余的状态都只是中间状态。

A：
A(0,0) --> A(1,0) --> B(2,0) --> B(2,1)   
S(2,0) ο B(2,0) ο B(2,1) = S(2,1) ο B(2,1) = S(2,2)

B：
B(0,1) --> B(0,2) --> A(0,2) --> A(1,2)
S(0,2) ο A(0,2) ο A(1,2) = S(1,2) ο A(1,2) = S(2,2)

中央服务器

在前边只是两位用户之间进行协同的操作，在这其中我们也探讨了多个Op的情况下如何进行OT。其实在实际的应用场景中，我们还需要中央服务器的角色来进行收集、派发、存储各个客户端的Op，被存储的Op代表了可连续应用的操作序列，可以用这些Op来描述一整篇文档的内容。服务端的如何调度各个Op，也是需要进行设计的，实现的算法的可靠性与效率决定了我们的应用的表现。

在研究有了中央服务器加入的协同之前，我们先来思考一下为什么协同这么难以实现，究竟是什么造成的，那么假如此时我们利用中央服务器来将多个用户的操作强行指定成同步操作会怎么样，也就是说我们所有本地进行的操作需要由服务器来进行Apply Op，本地虽然做了修改但是并不应用，也就是说我们本地写的内容不会立即应用到客户端上，需要中央服务器的确认之后才会正常显示，所有的Op都是在服务端中进行并且应用之后再同步到客户端，类似于悲观锁，只不过这个锁能够自动转移。假如是这种情况下，我们似乎就不需要一个很完善的调度算法了，因为是尽可能地保证了一个同步锁，当然由于网络的延时，还是很有可能出现冲突的问题，而且用户体验会特别差。那么回到我们正常的协同上，可以想到造成协同比较难以实现的一个原因是网络的传输，另一个原因就是有N个客户端可以同时应用Op，在无法实现完整同步的情况下，并发操作就有可能造成问题，由此就必须设计算法来进行调度，关于这块也可以看一下CAP理论。

回到服务端加入后的OT协同的场景，假设我们此时有A、B、Server三者，我们实际上可以认为通信的只有两位，也就是A/B与Server通信，A与B并不会直接通信，所有的客户端都只与Server通信，毕竟要是N个客户端直接通信的话，那就处理同步与冲突解决就太复杂了。那么此时，我们需要设计一下服务端的调度方案，我们先从最简单的开始，假设我们的服务端只处理冲突，但是不解决冲突，如果发现冲突我们就将冲突的部分退回，并且携带从相同的起点S以来所有的Op，让客户端去解决冲突计算该应用的Op，然后重新提交。

依照上边的设计，我们做一下场景的推演，假定文档的初始状态为S(0,0)。

• 服务端已经存储了B用户的三个操作，B(0,0)、B(0,1)、B(0,2)，文档状态步进到了S(0,3)。
• A用户在S(0,0)状态下打开文档，执行了四个操作A(0,0)、A(1,0)、A(2,0)、A(3,0)，文档状态到达了S(4,0)。
• 此时到了同步环节，当A用户将本地操作OpA 0-3提交到服务端时，服务端文档此时的状态是S(0, 3)，而A用户的操作产生于S(0,0)，在服务端无法直接应用，因此服务端不接收这些操作，但服务端把S(0,0)后落库的操作B(0,0)、B(0,1)、B(0,2)几个操作给到了A，相当于给了A所有S(0,0)之后的变更，因为我们设计的服务端不处理冲突，所以需要让A去进行操作变换，当A变换完成之后再度提交到服务端。
• A获得服务端下发的OP后，进行OT，A(0,0) A(1,0) A(2,0) A(3,0)基于B(0,0) B(0,1) B(0,2)做变换，得到了A(0,3) A(1,3) A(2,3) A(3,3)，对于这个OT的结果，由于在服务端的状态此时状态为S(0,3)，等同于A(0,3)的所处的语境，服务端可以直接应用，那么在A这里，注意这里与之前同步的操作不一样，之前同步做的OT是将B的Op同步过来我们要应用到A上，而此时我们做OT的操作是在B的基础上做A，然后在A上应用变换后的A，所以此时我们应该撤销掉我们做过的A(0,0) A(1,0) A(2,0) A(3,0)，然后应用B(0,0) B(0,1) B(0,2)再应用A(0,3) A(1,3) A(2,3) A(3,3)，此时我们的状态便可以达到S(4,3)，相当于模拟了一遍服务端要存储的Ops。
• 当A达到状态S(4,3)后，我们可以向服务端提交A(0,3) A(1,3) A(2,3) A(3,3)，服务端接受到这四个Op后，由于此时所处的状态为S(0,3)，等同于A(0,3)的所处的语境，服务端可以直接应用，那么服务端也可以到达状态S(4,3)。
• 紧接着，服务端再将A(0,3) A(1,3) A(2,3) A(3,3)同步到客户端B，B的状态也是S(0,3)，所以B也可以直接应用这个操作，那么此时三方的状态都达到了S(4,3)，达到了最终一致性。

看起来这个服务端设计还是可行的，但是设想一个场景，假如在A做好了操作变换之后，再次尝试提交时，服务端又多了B的新的操作B(0,4)，那么此时A新的操作因为上下文不匹配，再次被驳回，那么在一个多人协同密集的应用中，这样的架构设计显然是不可用的。总结一下，这个设计方案优点是在服务端只检测冲突，实现起来简单，而且保证了各端的操作顺序一致，一致性好；缺点就是在密集场景下打回几率高，操作容易滞留在本地，无法落库，客户端由于打回要频繁执行OT，会阻塞用户编辑。综上，架构能支持的协同人数非常有限，是一个不可用的架构。

既然前边我们设计的架构不够完善，那么我们对其进行改进，既然服务端只处理冲突，但是不解决冲突的方案不行，那我们就让服务端也能够解决冲突，并且允许客户端随意提交，这样的设计会发生什么情况，我们依旧依照上边的例子进行推演。

假定文档的初始状态为S(0,0)。

• 服务端已经存储了B用户的三个操作，B(0,0)、B(0,1)、B(0,2)，文档状态步进到了S(0,3)。
• A用户在S(0,0)状态下打开文档，执行了四个操作A(0,0)、A(1,0)、A(2,0)、A(3,0)，文档状态到达了S(4,0)。
• 此时A将Ops发送到了服务端，服务端在此时执行OT，将OT结果存储落库后，服务端的状态也步进到S(4, 3)。
• 此时服务端需要在基于A的操作对B操作做变化，也就是将B(0,0) B(0,1) B(0,2)在A(0,0) A(1,0) A(2,0) A(3,0)基础上做OT，得到B(4,0) B(4,1) B(4,2)，将OT之后的B操作发送给A，A执行Ops之后状态从S(4,0)到达了S(4,3)。
• 服务端还需要将A(0,3) A(1,3) A(2,3) A(3,3)发给B，状态从S(0,3)步进到S(4,3)，那么此时三方的状态都达到了S(4,3)，达到了最终一致性。

看起来这个服务端设计也还是可行的，主要在于服务端承载了解决冲突与分发Op的功能，但是再设想一个场景。

• 假如服务端做好了B(4,0) B(4,1) B(4,2)的OT后交还给A的时候，A本地又产生了两个Op A(4,0) A(5,0)，此时A本地的状态步进到了S(6,0)，那么服务端传过来的OpB是无法应用到本地的。
• 那么此时在A中需要进行OT，对B(4,0) B(4,1) B(4,2)基于A(4,0) A(5,0)做变换，得到B(6,0) B(6,1) B(6,2)，此时A需要应用B(6,0) B(6,1) B(6,2)，状态从S(6,0)步进到S(6,3)。
• 然后A需要将A(4,0) A(5,0)发送给服务端，然后再依据之前的过程完成服务端OT，得到A(4,3), A(5,3)，最终各端的状态能达到相同的S(6,3)。

总结起来，该架构设计的特点是当服务端收到Op时，服务端检测冲突，若无冲突直接落库存储，存在冲突则进行服务端OT，并将结果发送到客户端，当客户端收到Op时，若无冲突，则直接应用，反之进行客户端OT再应用收到的Op。那么根据上边的例子，我们可以看到对于A和B而言，两者执行的Op实际上是不一致的。

A: S(0,0) -> A(0,0) A(1,0) A(2,0) A(3,0) A(4,0) A(5,0) B(6,0) B(6,1) B(6,2) -> S(6,3)
B: S(0,0) -> B(0,0) B(0,1) B(0,2) A(0,3) A(1,3) A(2,3) A(3,3) A(4,3) A(5,3) -> S(6,3)

因此这个方案实际上依赖于S o OpsA o OT(OpsA, OpsB) = S o OpsB o OT(OpsB, OpsA)，又为算法增加了复杂性。这个设计方案的优点是在服务端能够解决冲突，客户端随意提交，不会打回，但是缺点是服务端需要做大量的OT，而且OT的结果需要发送给所有的客户端，这样的设计会导致服务端的压力非常大，在密集的多人协同的场景下，这样的设计能够支持的协同人数也会变得非常有限，如果客户端源源不断的地提交Op，服务端也将疲于应付，而且客户端也不能及时收到其他客户端的更新，此外如果有N个客户端同时发送Op，那么服务端进行OT的时候需要维护一个N维状态向量，这个过程的复杂度可就不只是上文我们看到的二维的棋盘变换了，这个架构也难以付诸实践。

此时我们再来改进一下方案，我们一直以来都是得到的Op就做变换与应用，没有一个时序的概念，之前说的顺序都是指时间先后顺序，冲突也是指同时产生编辑，但我们现在在同时这个概念上可以换一个方式理解，我们不再去考虑时间上的同时，而是版本上的同时。也就是说我们需要用一个东西表示每一个版本，类似git的每次提交有一个Commit Id，在这里我们每次提交到服务端的时候就要告诉服务端，我的修改是基于哪个版本的修改。那么最简单的标志位就是递增的数字，我们得到一个逻辑上的时序而不是类似于时间戳这种时间上的时许，那基于版本的冲突，可以简单理解为我们都是基于100版本的提交，那就是冲突了，也许我们并不是同时，只是谁先到后台决定了谁先被接受而已。当然在这里比较复杂的就是离线编辑，可能正常版本已经到了1000了，某个用户因为离线了，本地的版本一直停留在100，提交上来的版本是基于100的，那这个菱形就是一个单向拓展比较大的菱形了。

有了上边的时序的概念，我们再来看看具体的服务端与客户端的架构设计，我们可以限制客户端提交频度，为了简单起见我们每次都只能让客户端提交一个Op，直到服务端处理完成之后，客户端收到确认之后，我们才可以继续发送第二个Op，此时我们也是用逻辑上的时序，也就是一个单调自增的版本号来表示上下文语境，那么我们此时就有了几个状态，简单起见，在推演的过程中我们是用一个Sending一个Pending来分别表示等待确认的以及还未发送的Op。

那么此时我们表示的操作符号发生了改变，假定初始版本为0，且每次变更都会让版本号+1，客户端提交Op时，需要捎带版本号也就生生成该操作的语境，以便检测冲突，那么我们使用Op(Index)来表示完整的操作，例如A0(0)表示OpA0，并且操作的语境(逻辑时序)为0，B0(1)表示OpB0，并且操作的语境(逻辑时序)为1。

• 客户端A本地产生了两个操作A0(0)、A1(1)。
• 客户端B本地产生了一个操作B0(0)。
• 首先B0(0)被提交到服务端，此时B0(0)在B客户端的Sending队列中，由于此时服务端中Op序列为空，因此B0(0)可以直接落库，服务端将版本更新为1，并且将B0(0)发送至其他客户端。
• 服务端将B0(0)发给其他客户端，然后发送ACK到B，通知B该Op已经确认，此时B将B0(0)从Sending队列中出队，并且同步服务端的版本号为1。
• 在客户端A，提交了A0(0)，此时A的Sending队列中有A0(0)，Pending队列中有A1(1)。
• 服务端收到A0(0)后，此时服务端的版本号大于收到的版本号，由此检测到冲突，服务端执行OT，将获得的A0'(1)落库，更新服务端版本为2，并将A0'(1)分发到其他客户端，以及向客户端A返回A0的ACK。
• 在客户端A，收到了服务端发送的B0(0)，A检测到冲突，基于A0(0), A1(1)对B0(0)做变换，得到B0'(2)，并更新本地版本为3。
• 接下来A收到了A0'(1)的ACK，此时本地版本号已经到达了3，但是ACK确认的服务端版本号是2，此时我们依旧保持版本3，并且A将A0(0)从Sending出队，然后将A1(1)发送到服务端，并且从Pending出队再入队Sending，当然即将要发送的A1(1)也可以在上边收到B0(0)就做处理，然后作为ACK同步过来的版本号发送出去，类似于提前解决冲突，这就涉及具体实现了。
• 同理，B客户端收到ACK以后也更新自己的版本为1，紧接着到来的A0'(1)也可直接应用，更新本地版本到2。
• 在服务端，当前版本是2，因此收到的A1(1)发生了冲突，需要进行OT变换，得到A1(2)'后并应用，服务端更新版本为3，并发送A1(2)'到其它客户端，以及向客户端A回调A1的ACK。
• B在 收到A1(2)'之后，能够直接应用，应用后更新状态为3。
• A收到A1(2)'的ACK之后，将A1(1)出队Sending，更新本地版本号为3，至此各个客户端和服务端到达了一致的版本3。

上述的实现就比较接近真实的OT实现场景了，基于ACK机制，不但限制了Op提交的频度，也方便地通过简单地版本号就表示了文档上下文，避免维护一个N维状态向量。具体到真实的实现，例如ot.js，通过三种状态来控制操作，Synchronized没有正在提交并且等待回包的Op，AwaitingConfirm有一个Op提交了，等待后台确认，本地没有编辑数据，AwaitingWithBuffer有一个Op提交了，在等待后台确认，本地有编辑数据。接下来就是对于这三种状态分别进行处理了，可以具体实现可以参考https://github.com/Operational-Transformation/ot.js/blob/master/lib/client.js，还有一个可视化的实现http://operational-transformation.github.io/index.html。

最后

在上边的论述中我们似乎得到了一个不错的方案，但是实际上文中描述的内容也只是冰山一角，一个稳定协同过程还面临着诸多问题，例如需要支持多人协同的Undo/Redo，保证客户端与服务端OT算法的统一、在CAP理论下如何做取舍策略、如何保证多人协同的编辑器性能、如何保证数据的稳定性可恢复可回溯、光标的同步处理等等，当然不可能拥有从一开始就完美的架构设计，都是在发现问题之后一步步地让其变得完美。

说了这么多，实际上目前已经有很多开源的OT算法实现，我们并不需要特别关注于具体实现的细节，当然基础理论还是要懂的，当前有很多成熟的框架，例如ot.js、ShareDb、ot-json、EasySync等等，当然因为场景的复杂性，就算是我们接入也是需要大量工作的，文章也提到了，具体到Transformation是需要自己实现的，当然对于开源的富文本引擎来说也有很多开源的实现，在接入之前也是有比较深入研究一下的，否则很容易有种无从下手的感觉，特别推荐阅读实现的单元测试部分，来了解OT算法处理的场景和范围，在这里推荐两个OT的实现，基于Quill实现的https://github.com/ottypes/rich-text与基于Slate实现的https://github.com/solidoc/slate-ot。

每日一题

https://github.com/WindrunnerMax/EveryDay

参考

https://zhuanlan.zhihu.com/p/50990721
https://zhuanlan.zhihu.com/p/426184831
https://zhuanlan.zhihu.com/p/559699843
https://zhuanlan.zhihu.com/p/425265438
http://www.alloyteam.com/2020/01/14221/
http://www.alloyteam.com/2019/07/13659/
https://segmentfault.com/a/1190000040203619
https://www.shangyexinzhi.com/article/4676182.html
http://operational-transformation.github.io/index.html
https://xie.infoq.cn/article/a6fad791493bf4f698781d98e
https://github.com/yoyoyohamapi/book-slate-editor-design
https://www3.ntu.edu.sg/scse/staff/czsun/projects/otfaq/