OT算法比较

OT是operation transform的简称，即操作转化，在协同编辑领域应用的比较多。以协同编辑为例，OT可以理解为，当你在输入一个字符的时候，碰巧其他人也正在输入字符，此时就产生了冲突，这时候需要把你的输入操作进行一次操作转化，以处理你和别人的编辑冲突。

这么说可能有点抽象，我们举一个具体的例子。

对于一段文本 abc
A用户在字符b后面增加了一个d字符，我们把A用户的操作记为Insert[2,'d']，即在第二个字符后面增加一个d字符

B用户对于同样的abc文本，在c字符后面增加了一个e字符，我们把B用户的操作记为Insert[3,'e']，即在第三个字符后面增加一个e字符

此时A、B用户针对同一段文本都做了操作，产生了冲突。对于这种简单增加的情况，我们预期的结果很显然是abdce。如果我们不处理冲突，依次执行A、B用户的操作，那么有

abc—A—abdc—B—abdec

最后得到的结果abdec和我们预期的abdce不相符，所以我们需要对B用户的操作做一次操作转化，记这个转化函数为Follow(x,y)，x为先执行的操作，y为后执行的操作，函数值就是y进行了操作转化后的操作值，那么有

Follow(A,B) = Follow(Insert[2,'d'],Insert[3,'e']) = Insert[4,'e']

此时操作结果

abc—A—abdc—Follow(A,B)—abdce，符合预期。

Easysync双边OT

以上是站在A用户的角度，A用户先执行了A操作，再执行Follow(A,B)操作，得到预期的结果。

那么对于B用户来说，B用户先执行了B操作，同理这时候就需要执行Follow(B,A)操作，才能得到预期的结果。

Follow(B,A) = Follow(Insert[3,'e'],Insert[2,'d']) = Insert[2,'d']

此时B用户的操作结果

abc—B—abce—Follow(B,A)—abdce，符合预期。

我们把原始的abc的状态记为O，则有

O A Follow(A,B) === O B Follow(B,A)

这个公式就是easysync中的冲突处理的核心。这种算法有两个特点

1. 本地应用的操作和协同给别人的操作不相同。对于A来说，B操作协同过来后，本地应用的是Follow(A,B)，而协同给B的是Follow(B,A)，这也是称之为双边的原因。
2. Follow函数需要保证上述等式恒成立
3. 多冲突处理更加复杂

基于undo的单边OT

对于B用户来说，B用户先执行了B操作，那么其实我们可以对B操作先执行一次undo，让B用户当前的文档状态和A用户的初始状态一致，再执行和A用户同样的操作序列。

abc—B—abce—undo B—abc—A—abdc—Follow(A,B)—abdce

用公式表示就是
O A Follow(A,B) === O B undoB A Follow(A,B)

这种算法有以下特点

1. 本地应用的操作和协同给别人的操作相同。对于A用户来说，均为Follow(A,B)。这也就是称之为单边的原因，只有一种Follow操作在传递。
2. 对于Follow函数的要求更低，无需保证顺序Follow的幂等
3. 需要额外的undo支持，undo操作也需要Follow
4. 多冲突处理更为简单

待续