協同編輯中使用的 OT 算法是什么？
大家好，我是前端西瓜哥，今天我們來聊聊 OT 算法是什么。
OT 的英文全稱是 Operational transformation，是一種處理協同編輯的算法。
它常用于實現協同文檔的底層算法，支持多個用戶同時編輯文檔，不會因為并發修改導致沖突，而使結果不一致或數據丟失。
沖突的處理方式
假設 A 和 B 在同時編輯同一個內容，我們處理沖突的方式有：
- 加鎖。用戶 A 在編輯時，就鎖住文檔，只能 A 進行更新。用戶 B 就不能編輯，或編輯后提交修改被服務器丟棄。
- 覆蓋。誰最后修改，就全量使用他的修改，更早一些的其他人的修改會被丟棄。
- 用戶自行處理沖突。就像 git merge 導致的沖突一樣，會提示哪個地方被同時修改了，讓合并者手動選擇使用哪一個修改。
- 使用一致性算法。比如我們要介紹的 OT 算法，可以讓用戶編輯進行算法處理進行調整，在多個客戶端生成一致的修改結果。
對于在線協同文檔。
加鎖體驗太差，一個人在編輯時其他人就要干等著。
覆蓋則是導致用戶的修改來回彼此覆蓋，辛苦編輯的內容突然被別人覆蓋掉了心情低落。
自行處理沖突則需要額外的操作步驟和成本，實時性很差，不適合高頻同時修改的場景。
一致性算法是最好的選擇，對用戶最友好，不過帶來了實現的復雜。
一致性問題
我們先來看看不使用 OT 導致的沖突問題。
假設用戶 A 和用戶 B 同時在編輯同一個文檔，文檔內容為 “12”。
- 用戶 A 在末尾添加一個字符 “A”，這個修改先應用在本地，內容變成了 “12A”，之后客戶端發送一個數據 insert(2, "A")給服務端，代表在位置 2 的地方插入 “A”。服務端會將修改消息推送給其他客戶端，但這需要時間。
- 用戶 B 在收到推送消息前，也在 “12” 的尾部添加了內容 “B”，在本地變成了 “12B”，并將 insert(2, "B")的修改描述提交服務器。
- 用戶 B 收到了 insert(2, "A")消息，應用后，將 “12B” 變成了 “12AB”。
- 用戶 A 則收到 insert(2, "B")消息，應用后，將 “12B” 變成了 “12BA”。
結果是，用戶 A 看到的內容是 “12BA”，用戶 B 看到的內容是 “12AB”，內容不一致，不符合預期。
使用 OT
OT 算法可以解決一致性問題，我們來看看 OT 到底做了什么。
同樣，原始內容是 “12”。
- 用戶 A 在末尾添加 “A”，本地變成 “12A”，并發送 insert(2, A)，這個操作計作 OA。
- 用戶 B 在末尾添加 “B”，本地變成 “12B”，并發送 insert(2, B)，這個操作計作 OB。
- 用戶 A 收到 OB，執行 transform(OA, OB)，得到修正后的操作insert(3, B)，記為 OB'，相比 OB，它將插入位置從 2 修正為 3，于是 "12A" 變成了 “12AB”。
- 用戶 B 則收到 OA，同樣執行 transform(OA, OB)，得到修正操作insert(2, A)，記為 O1'，讓內容從 "12A" 變成 “12AB”。transform 方法會同時產生 OA' 和 OB'。
最后，用戶 A 和用戶 B 看到的是 一致 的 “12AB”。
這里的核心在于這個 transfrom 方法，它能夠對操作進行修正。transform 沒有固定實現，要根據實際需求自行實現。
這里有一個經典的菱形示意圖。
從起始版本 T 開始，它接受了兩個 并發操作 A 和 B。我們使用 trasform 方法生成 A' 和 B'。我們有：
S + A + B' = T
S + B + A' = T
這樣，從 S 得到相同的 T，保證了一致性。
下面使用了 ot.js 庫，演示了一下從 '12' 到 '12AB' 的過程。
const s = '12'; // 原始文案（版本 1）
// 在位置 3 插入 'A'
const oA = new TextOperation().retain(2).insert('A');
// 上述操作后得到結果 '12A'（版本 2）
const t1 = oA.apply(s);
// 收到 oB 操作：在位置 2 插入 'B'
const oB = new TextOperation().retain(2).insert('B');
// transform 拿到修正后的 [oA', oB']
// 我們這里只需要 oB'，它被修正為在位置 3 插入 'B'
const [oAp, oBp] = TextOperation.transform(oA, oB);
// 應用 oB'，結果為：12AB （版本 3）
const t2 = oBp.apply(t1);
線上 demo 鏈接為：
https://codesandbox.io/s/b8ds8h。
transform 操作既發生在服務端：將基于某個版本的并發操作對象轉換成串行操作。
也發生在客戶端，本地的修改還沒來得及提交，就收到了服務端推送。
如果你想要深入研究 OT 算法，可以考慮參考 ot.js 庫的代碼實現，里面還附帶了一個 OT 可視化過程。
https://github.com/Operational-Transformation/ot.js/。
結尾
OT 算法能夠在實時保證多個客戶端數據的一致性，被廣泛用于協同編輯場景。
