大家好，我是前端西瓜哥，今天我們來聊聊 OT 算法是什么。

OT 的英文全稱是 Operational transformation，是一種處理協(xié)同編輯的算法。

它常用于實(shí)現(xiàn)協(xié)同文檔的底層算法，支持多個(gè)用戶同時(shí)編輯文檔，不會(huì)因?yàn)椴l(fā)修改導(dǎo)致沖突，而使結(jié)果不一致或數(shù)據(jù)丟失。

沖突的處理方式

假設(shè) A 和 B 在同時(shí)編輯同一個(gè)內(nèi)容，我們處理沖突的方式有：

1. 加鎖。用戶 A 在編輯時(shí)，就鎖住文檔，只能 A 進(jìn)行更新。用戶 B 就不能編輯，或編輯后提交修改被服務(wù)器丟棄。
2. 覆蓋。誰最后修改，就全量使用他的修改，更早一些的其他人的修改會(huì)被丟棄。
3. 用戶自行處理沖突。就像 git merge 導(dǎo)致的沖突一樣，會(huì)提示哪個(gè)地方被同時(shí)修改了，讓合并者手動(dòng)選擇使用哪一個(gè)修改。
4. 使用一致性算法。比如我們要介紹的 OT 算法，可以讓用戶編輯進(jìn)行算法處理進(jìn)行調(diào)整，在多個(gè)客戶端生成一致的修改結(jié)果。

對(duì)于在線協(xié)同文檔。

加鎖體驗(yàn)太差，一個(gè)人在編輯時(shí)其他人就要干等著。

覆蓋則是導(dǎo)致用戶的修改來回彼此覆蓋，辛苦編輯的內(nèi)容突然被別人覆蓋掉了心情低落。

自行處理沖突則需要額外的操作步驟和成本，實(shí)時(shí)性很差，不適合高頻同時(shí)修改的場景。

一致性算法是最好的選擇，對(duì)用戶最友好，不過帶來了實(shí)現(xiàn)的復(fù)雜。

一致性問題

我們先來看看不使用 OT 導(dǎo)致的沖突問題。

假設(shè)用戶 A 和用戶 B 同時(shí)在編輯同一個(gè)文檔，文檔內(nèi)容為 “12”。

1. 用戶 A 在末尾添加一個(gè)字符 “A”，這個(gè)修改先應(yīng)用在本地，內(nèi)容變成了 “12A”，之后客戶端發(fā)送一個(gè)數(shù)據(jù) insert(2, "A")給服務(wù)端，代表在位置 2 的地方插入 “A”。服務(wù)端會(huì)將修改消息推送給其他客戶端，但這需要時(shí)間。
2. 用戶 B 在收到推送消息前，也在 “12” 的尾部添加了內(nèi)容 “B”，在本地變成了 “12B”，并將 insert(2, "B")的修改描述提交服務(wù)器。
3. 用戶 B 收到了 insert(2, "A")消息，應(yīng)用后，將 “12B” 變成了 “12AB”。
4. 用戶 A 則收到 insert(2, "B")消息，應(yīng)用后，將 “12B” 變成了 “12BA”。

結(jié)果是，用戶 A 看到的內(nèi)容是 “12BA”，用戶 B 看到的內(nèi)容是 “12AB”，內(nèi)容不一致，不符合預(yù)期。

使用 OT

OT 算法可以解決一致性問題，我們來看看 OT 到底做了什么。

同樣，原始內(nèi)容是 “12”。

1. 用戶 A 在末尾添加 “A”，本地變成 “12A”，并發(fā)送 insert(2, A)，這個(gè)操作計(jì)作 OA。
2. 用戶 B 在末尾添加 “B”，本地變成 “12B”，并發(fā)送 insert(2, B)，這個(gè)操作計(jì)作 OB。
3. 用戶 A 收到 OB，執(zhí)行 transform(OA, OB)，得到修正后的操作insert(3, B)，記為 OB'，相比 OB，它將插入位置從 2 修正為 3，于是 "12A" 變成了 “12AB”。
4. 用戶 B 則收到 OA，同樣執(zhí)行 transform(OA, OB)，得到修正操作insert(2, A)，記為 O1'，讓內(nèi)容從 "12A" 變成 “12AB”。transform 方法會(huì)同時(shí)產(chǎn)生 OA' 和 OB'。

最后，用戶 A 和用戶 B 看到的是 一致 的 “12AB”。

這里的核心在于這個(gè) transfrom 方法，它能夠?qū)Σ僮鬟M(jìn)行修正。transform 沒有固定實(shí)現(xiàn)，要根據(jù)實(shí)際需求自行實(shí)現(xiàn)。

這里有一個(gè)經(jīng)典的菱形示意圖。

從起始版本 T 開始，它接受了兩個(gè) 并發(fā)操作 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');
// 上述操作后得到結(jié)果 '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);
// 應(yīng)用 oB'，結(jié)果為：12AB （版本 3）
const t2 = oBp.apply(t1);

線上 demo 鏈接為：

https://codesandbox.io/s/b8ds8h。

transform 操作既發(fā)生在服務(wù)端：將基于某個(gè)版本的并發(fā)操作對(duì)象轉(zhuǎn)換成串行操作。

也發(fā)生在客戶端，本地的修改還沒來得及提交，就收到了服務(wù)端推送。

如果你想要深入研究 OT 算法，可以考慮參考 ot.js 庫的代碼實(shí)現(xiàn)，里面還附帶了一個(gè) OT 可視化過程。

https://github.com/Operational-Transformation/ot.js/。

結(jié)尾

OT 算法能夠在實(shí)時(shí)保證多個(gè)客戶端數(shù)據(jù)的一致性，被廣泛用于協(xié)同編輯場景。