OT是operation transform的簡(jiǎn)稱，即操作轉(zhuǎn)化聚假，在協(xié)同編輯領(lǐng)域應(yīng)用的比較多。以協(xié)同編輯為例闰非，OT可以理解為膘格，當(dāng)你在輸入一個(gè)字符的時(shí)候，碰巧其他人也正在輸入字符财松，此時(shí)就產(chǎn)生了沖突闯袒，這時(shí)候需要把你的輸入操作進(jìn)行一次操作轉(zhuǎn)化，以處理你和別人的編輯沖突游岳。
這么說可能有點(diǎn)抽象，我們舉一個(gè)具體的例子其徙。
對(duì)于一段文本 abc
A用戶在字符b后面增加了一個(gè)d字符胚迫，我們把A用戶的操作記為Insert[2,'d']，即在第二個(gè)字符后面增加一個(gè)d字符
B用戶對(duì)于同樣的abc文本唾那，在c字符后面增加了一個(gè)e字符访锻，我們把B用戶的操作記為Insert[3,'e']，即在第三個(gè)字符后面增加一個(gè)e字符
此時(shí)A闹获、B用戶針對(duì)同一段文本都做了操作期犬，產(chǎn)生了沖突。對(duì)于這種簡(jiǎn)單增加的情況避诽，我們預(yù)期的結(jié)果很顯然是abdce龟虎。如果我們不處理沖突，依次執(zhí)行A沙庐、B用戶的操作鲤妥，那么有
abc—A—abdc—B—abdec
最后得到的結(jié)果abdec和我們預(yù)期的abdce不相符，所以我們需要對(duì)B用戶的操作做一次操作轉(zhuǎn)化拱雏，記這個(gè)轉(zhuǎn)化函數(shù)為Follow(x,y)棉安，x為先執(zhí)行的操作，y為后執(zhí)行的操作铸抑，函數(shù)值就是y進(jìn)行了操作轉(zhuǎn)化后的操作值贡耽，那么有
Follow(A,B) = Follow(Insert[2,'d'],Insert[3,'e']) = Insert[4,'e']
此時(shí)操作結(jié)果
abc—A—abdc—Follow(A,B)—abdce，符合預(yù)期。
Easysync雙邊OT
以上是站在A用戶的角度蒲赂，A用戶先執(zhí)行了A操作阱冶，再執(zhí)行Follow(A,B)操作，得到預(yù)期的結(jié)果凳宙。
那么對(duì)于B用戶來說熙揍，B用戶先執(zhí)行了B操作，同理這時(shí)候就需要執(zhí)行Follow(B,A)操作氏涩，才能得到預(yù)期的結(jié)果届囚。
Follow(B,A) = Follow(Insert[3,'e'],Insert[2,'d']) = Insert[2,'d']
此時(shí)B用戶的操作結(jié)果
abc—B—abce—Follow(B,A)—abdce，符合預(yù)期是尖。
我們把原始的abc的狀態(tài)記為O意系，則有
O A Follow(A,B) === O B Follow(B,A)
這個(gè)公式就是easysync中的沖突處理的核心。這種算法有兩個(gè)特點(diǎn)
- 本地應(yīng)用的操作和協(xié)同給別人的操作不相同饺汹。對(duì)于A來說蛔添，B操作協(xié)同過來后，本地應(yīng)用的是Follow(A,B)兜辞，而協(xié)同給B的是Follow(B,A)迎瞧，這也是稱之為雙邊的原因。
- Follow函數(shù)需要保證上述等式恒成立
- 多沖突處理更加復(fù)雜
基于undo的單邊OT
對(duì)于B用戶來說逸吵，B用戶先執(zhí)行了B操作凶硅，那么其實(shí)我們可以對(duì)B操作先執(zhí)行一次undo，讓B用戶當(dāng)前的文檔狀態(tài)和A用戶的初始狀態(tài)一致扫皱，再執(zhí)行和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)
這種算法有以下特點(diǎn)
- 本地應(yīng)用的操作和協(xié)同給別人的操作相同。對(duì)于A用戶來說韩脑，均為Follow(A,B)氢妈。這也就是稱之為單邊的原因，只有一種Follow操作在傳遞段多。
- 對(duì)于Follow函數(shù)的要求更低首量，無需保證順序Follow的冪等
- 需要額外的undo支持，undo操作也需要Follow
- 多沖突處理更為簡(jiǎn)單
