# 初探富文本之OT协同算法
`OT`的英文全称是`Operational Transformation`，是一种处理协同编辑的算法。当前`OT`算法用的比较多的地方就是富文本编辑器领域了，常用于作为实现文档协同的底层算法，支持多个用户同时编辑文档，不会因为用户并发修改导致冲突，而导致结果不一致甚至数据丢失的问题。
初探富文本编辑器系列相关文章
* [初探富文本编辑器#1-富文本概述](./初探富文本之富文本概述.md)
* [初探富文本编辑器#2-编辑器引擎](./初探富文本之编辑器引擎.md)
* [初探富文本编辑器#3-OT 协同算法](./初探富文本之OT协同算法.md)
* [初探富文本编辑器#4-OT 协同实例](./初探富文本之OT协同实例.md)
* [初探富文本编辑器#5-CRDT 协同算法](./初探富文本之CRDT协同算法.md)
* [初探富文本编辑器#6-CRDT 协同实例](./初探富文本之CRDT协同实例.md)
* [初探富文本编辑器#7-React 实时预览](./初探富文本之React实时预览.md)
* [初探富文本编辑器#8-文档 diff 算法](./初探富文本之文档diff算法.md)
* [初探富文本编辑器#9-在线文档交付](./初探富文本之在线文档交付.md)
* [初探富文本编辑器#10-划词评论能力](./初探富文本之划词评论能力.md)
* [初探富文本编辑器#11-文档虚拟滚动](./初探富文本之文档虚拟滚动.md)
* [初探富文本编辑器#12-搜索替换算法](./初探富文本之搜索替换算法.md)
* [初探富文本编辑器#13-序列化与反序列化](./初探富文本之序列化与反序列化.md)
## 概述
从名字就可以看出来，`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`插入文本的长度。
```js
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`来决定究竟是谁在前，这只是一个简单的策略，也就是所谓的尽可能保持用户意图的情况下，保持文档的最终一致性。
```js
// 如果两个`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`。
## 每日一题
-
## 参考
-
-
-
-
-
-
-
-
-
-
-
-