實(shí)現(xiàn)一個(gè)多人協(xié)作在線文檔有哪些技術(shù)難點(diǎn)？

摘抄一個(gè)google到的文章：原文連接

淺談協(xié)同編輯的實(shí)現(xiàn)：

什么是實(shí)時(shí)協(xié)同編輯

這里所說的實(shí)時(shí)協(xié)同編輯，是指多人同時(shí)編輯一個(gè)文檔，最典型的例子是 Google Docs，你可以實(shí)時(shí)看到別人做出的修改，不用手動(dòng)刷新頁面。

要實(shí)現(xiàn)實(shí)時(shí)編輯，我們需要解決兩個(gè)技術(shù)點(diǎn)：實(shí)時(shí)通信問題、編輯沖突問題，其中實(shí)時(shí)通信問題比較好解決，可以使用 long pull 或 WebSocket，所以這里就不過多討論了，重點(diǎn)將放在如何解決編輯沖突問題上。

可選方案

接下來將從易至難的順序來介紹幾種可行的方案，分別是：「編輯鎖」、「GNU diff-patch」、「Myer’s diff-patch」、「Operational Transformation」和「分布式 Operational Transformation」。

編輯鎖

編輯鎖這是實(shí)現(xiàn)協(xié)同編輯最簡單的方法，簡單來說就是當(dāng)有人在編輯某個(gè)文檔時(shí)，系統(tǒng)會(huì)將這個(gè)文檔鎖定，避免其他人同時(shí)編輯，因?yàn)閷?shí)現(xiàn)簡單，所以這個(gè)方案是應(yīng)用最廣的，比如公司內(nèi)部常用的 TWiki 系統(tǒng)，采用這種方式雖然可以在一定程度上避免覆蓋問題，但它的使用體驗(yàn)不好，也做不到「實(shí)時(shí)」，所以這里就不討論了。

GNU diff-patch

Git 等版本管理軟件其實(shí)也是一種協(xié)同編輯工具，因?yàn)槊總€(gè)人都可以并行編輯，遇到編輯同一個(gè)文件時(shí)可以自動(dòng)合并，因此我們也能使用類似的原理來實(shí)現(xiàn)協(xié)同編輯，具體可以有兩種方法：diff-patch 和 merge。

先說 diff-patch，這里的 diff 和 patch 是指兩個(gè) unix 下的命令，diff 能輸出兩個(gè)文本的不同之處，然后用 patch 來更新其它文件，我們只要在 JS 中實(shí)現(xiàn)這兩個(gè)算法，就能通過如下流程來實(shí)現(xiàn)協(xié)同編輯：

1. 每個(gè)用戶進(jìn)來時(shí)都建立長連接，保存好當(dāng)前文檔副本
2. 有人編輯時(shí)，如果停頓 5 秒（具體要根據(jù)產(chǎn)品策略），就將現(xiàn)有文檔和之前的副本進(jìn)行 diff，將結(jié)果傳給服務(wù)端，更新副本
3. 服務(wù)端更新文檔，然后通過長連接將這個(gè) diff 結(jié)果發(fā)給同時(shí)在編輯的其它用戶，這些用戶使用 patch 方法來更新 ta 們文檔

但 GNU diff 有個(gè)問題，因?yàn)榛谛衅ヅ涞?，所以很容易沖突，讓我們測(cè)試一下「百度 Web」和「百度 Web 前端」這兩段文本的 diff 結(jié)果

[nwind@fex ~]$ diff old.txt other-new.txt > old-to-other-new.patch
[nwind@fex ~]$ cat old-to-other-new.patch
1c1
< 百度 Web
---
> 百度 Web 前端

在這個(gè) diff 結(jié)果中，1c1的第一個(gè)「1」代表修改前的第一行，后面的「c」代表「修改」，第二個(gè)「1」代表修改后的行，也就是說將第一行的「百度 Web」改成「百度 Web 前端」，修改后的內(nèi)容放第一行。也就意味著如果兩人同時(shí)修改一行就會(huì)沖突，可以通過下面的測(cè)試來確認(rèn)：

[nwind@fex ~]$ cat my-new.txt
Web

[nwind@fex ~]$ patch my-new.txt < old-to-other-new.patch
patching file b-new.txt
Hunk #1 FAILED at 1.
1 out of 1 hunk FAILED -- saving rejects to file my-new.txt.rej

[nwind@fex ~]$ cat my-new.txt.rej
***************
*** 1
- 百度 Web--- 1 -----
+ 百度 Web 前端

其中 my-new.txt 是我修改的版本，我去掉了前面的「百度 」，只留下「Web」，其實(shí)這兩處修改是不沖突的，它們可以合并成「Web 前端」，如下圖所示

但使用 patch 命令部下，它在沖突后會(huì)生成一個(gè)新文件 my-new.txt.rej 來描述失敗原因，這種展現(xiàn)方式不直觀，需要打開兩個(gè)文件比對(duì)，我們使用另一種方式來更好地展現(xiàn)，那就是接下來介紹的 merge 命令，它的使用方法如下：

[nwind@fex ~]$ merge my-new.txt old.txt other-new.txt
merge: warning: conflicts during merge

[nwind@fex ~]$ cat my-new.txt
<<<<<<< my-new.txt
Web=======
百度 Web 前端>>>>>>> other-new.txt

可以看到它直接將沖突的地方寫到 my-new.txt 里了，這點(diǎn)比 patch 看起來要方便些，對(duì)于這個(gè)結(jié)果估計(jì)大部分同學(xué)都會(huì)眼熟，因?yàn)?merge 命令和 Git 等工具中的合并算法是一樣的。

通過使用我們可以發(fā)現(xiàn) merge 命令有個(gè)缺點(diǎn)，那就是需要使用 3 份完整的文本來進(jìn)行比較，為了避免每次傳遞所有文本內(nèi)容，我們可以結(jié)合使用 diff 來減小傳輸體積，在后端 patch 成新的文本。

無論是 diff 還是 merge，由于它們的算法都是基于行進(jìn)行比較，導(dǎo)致對(duì)同一行的編輯必然沖突，為了解決這個(gè)問題，我們可以嘗試基于字符粒度的 diff 算法，那就是接下來將介紹的 Myer’s diff-patch。

Myer’s diff-patch

Myer 算法是另一種 diff-patch 算法，它有很多語言的開源實(shí)現(xiàn)，這里我們就不介紹細(xì)節(jié)算法了，直接用之前的例子來測(cè)試它的效果，首先看一下它的 diff 結(jié)果，調(diào)用代碼如下：

var old_text = "百度 Web";
var new_text = "百度 Web 前端";

var dmp = new diff_match_patch();
var patch_list = dmp.patch_make(old_text, new_text);
patch_text = dmp.patch_toText(patch_list);

console.log(decodeURI(patch_text))

輸出結(jié)果為

@@ -1,6 +1,9 @@
 百度 Web
+ 前端

其中第一行的 - 和 + 兩個(gè)符號(hào)沒有什么意義，這句話表示修改處之前的起始位置為 1（由于數(shù)組是從 0 開始的，所以內(nèi)部計(jì)算時(shí)會(huì)先減一），長度為 6，后面的 1,9，表示修改后的起始位置為 1，長度為 9。在接下來的兩段文本代表修改的地方，注意「百度 Web」前面有空格，這代表相等，也就是直接添加這個(gè)字符串，而后面的 + 代表添加文本，具體細(xì)節(jié)可以通過它的實(shí)現(xiàn)源碼了解。

因此確定它的 diff 策略是基于字符匹配的，這樣能否解決我們之前遇到的沖突問題呢？接下來來測(cè)試一下，源碼如下：

//相關(guān)代碼同上
var patches = dmp.patch_fromText(patch_text);
var results = dmp.patch_apply(patches, "Web");

console.log(results[0]); //Web 前端

這個(gè)輸出結(jié)果是正確的，也就是說它能很好地解決之前的問題，但如果是同一個(gè)位置的修改會(huì)怎樣？我繼續(xù)做了幾個(gè)實(shí)驗(yàn)：

var old_text = "百度 Web";
var other_new_text = "百度 Web 后端";
var my_new_text = "百度 Web 前端";
...
//結(jié)果為「百度 Web 前端 后端」

===
var old_text = "百度 Web 前端";
var other_new_text = "百度 Web 后端";
var my_new_text = "百度 Web 全端";
...
//結(jié)果為「百度 Web 后端」

===
var old_text = "百度 Web";
var other_new_text = "Web 前端";
var my_new_text = "百度 FE";
//結(jié)果為「FE 前」 

第一個(gè)例子是在后面添加不同的字符，它的結(jié)果是兩個(gè)添加都生效，第二個(gè)例子是在同一處修改成不同的字符，它的結(jié)果是別人的修改生效，但最后一個(gè)例子出錯(cuò)了，丟失了「端」字，這里看起來還好，但如果內(nèi)容是富文本就有問題了，比如 少了 > 是不行的。

整體來看 Myer 算法可以低成本地解決大部分問題，所以有些在線編輯器選擇它來實(shí)現(xiàn)協(xié)同編輯功能，比如 codebox，它的客戶端代碼在這，服務(wù)端代碼在這。

不過 Myer 在某些情況下會(huì)丟字符，是否還有更好的方法？答案是有，那就是接下來介紹的 Operational Transformation 技術(shù)。

Operational Transformation

Operational Transformation（下面簡稱 OT）技術(shù)正是 Google Docs 中所采用的方案，因此是經(jīng)過驗(yàn)證的，值得研究。

最開始我一直覺得 OT 會(huì)很復(fù)雜，因?yàn)樗南嚓P(guān)介紹文章都寫得很長，比如這篇及維基百科上的介紹，不過看了之后才后發(fā)現(xiàn)它的原理并不復(fù)雜，我將在這里進(jìn)行簡單的說明。

首先，我們可以將文本內(nèi)容修改轉(zhuǎn)成以下 3 種類型的操作(Operational)：

• retain(n)：保持 n 個(gè)字符，也就是說這 n 個(gè)字符不變
• insert(str)：插入字符 str
• delete(str)：刪除字符 str

舉個(gè)例子，假設(shè) A 用戶將「百度 Web」變成「Web 前端」，相當(dāng)于產(chǎn)生了如下 3 個(gè)操作：

delete('百度 '),  //刪掉「百度 」
retain(3),       //跳過 3 個(gè)字符（也就是「Web」）
insert(' 前端')   //插入「 前端」

提取這些操作可以通過 Levenshtein distance（編輯距離）算法來實(shí)現(xiàn)。那它如何解決沖突問題了？比如這時(shí)如果 B 用戶將「百度 Web」改成了「百度 FE」，B 所生產(chǎn)的操作步驟將會(huì)是如下：

retain(3),       //跳過 3 個(gè)字符（也就是「百度 」）
delete('Web'),
insert('FE')

如果我們先應(yīng)用 A 的操作，將字符串變?yōu)椤竁eb 前端」，然后再應(yīng)用 B 的操作時(shí)就會(huì)失效，因?yàn)樵趫?zhí)行 B 的第二個(gè)操作 delete('Web')時(shí)并沒有「Web」，這時(shí)從第四個(gè)字符開始已經(jīng)變成了「 前端」。

因此我們需要轉(zhuǎn)換 B 的操作來適應(yīng)新的字符串，比如調(diào)成如下操作：

delete('Web'),
insert('FE'),
retain(3)

這個(gè)轉(zhuǎn)換算法就是 OT 的核心，實(shí)際上 OT 指的是一類技術(shù)，而不是具體的算法，這個(gè)思路就是首先將編輯轉(zhuǎn)成操作(Operational)，如果多人操作同時(shí)進(jìn)行，需要對(duì)這些操作進(jìn)行轉(zhuǎn)換(Transformation)，這就是為什么叫 Operational Transformation，而具體應(yīng)該拆分成哪些操作以及轉(zhuǎn)換算法都是可以自定義的，因此 OT 可以靈活地支持各種協(xié)同編輯應(yīng)用，比如非文本類的編輯。

回到之前 Myer 算法導(dǎo)致丟字符的那個(gè)例子，我們看看 OT 是否能解決，這里我使用了一個(gè)開源庫 changesets，以下是基于它實(shí)現(xiàn)合并的例子：

var Changeset = require('changesets').Changeset;

var text = "百度 Web"
  , textA = "Web 前端"
  , textB = "百度 FE";

var csA = Changeset.fromDiff(text, textA);
var csB = Changeset.fromDiff(text, textB);

var csB_new = csB.transformAgainst(csA); //這里這就是操作轉(zhuǎn)換

var textA_new = csA.apply(text);
console.log(csB_new.apply(textA_new)); //結(jié)果是「 前端FE」

結(jié)果并不正確，正確的應(yīng)該是「FE 前端」，查看一下csB_new的內(nèi)容，發(fā)現(xiàn)它實(shí)際上是轉(zhuǎn)換成了如下操作：

delete(3),   //注意 changesets 在這里的參數(shù)不是字符串而是數(shù)字，它會(huì)直接刪掉 3 個(gè)字符，不夠內(nèi)容是什么
retain(3),
insert('FE')

需要注意這并不是 OT 技術(shù)本身的問題，而是 changesets 所實(shí)現(xiàn)的轉(zhuǎn)換算法問題，雖然不夠完美，但和之前的 Myer 算法相比，至少?zèng)]丟字符，后來我又做了幾個(gè)測(cè)試，發(fā)現(xiàn) OT 技術(shù)的準(zhǔn)確率比 Myer 高，因此它是最適合用于協(xié)同編輯的技術(shù)。

分布式 Operational Transformation

如果看完上面的文章你覺得實(shí)現(xiàn)實(shí)時(shí)協(xié)同編輯似乎不難，那你就錯(cuò)了，因?yàn)槲覀冎岸紱]有考慮分布式的問題，OT 技術(shù)在學(xué)術(shù)界都研究 20 多年了，至今也沒人總結(jié)出一個(gè)最好的方法，前 Google Wave 工程師在 ShareJS 首頁上這樣寫道：

Unfortunately, implementing OT sucks. There’s a million algorithms with different tradeoffs, mostly trapped in academic papers. The algorithms are really hard and time consuming to implement correctly. I am an ex Google Wave engineer. Wave took 2 years to write and if we rewrote it today, it would take almost as long to write a second time.

所以其實(shí)要做好是很難的，這里面最麻煩的就是分布式導(dǎo)致的問題，接下來將介紹 3 個(gè)我能想到的問題及解決方法。

1. 順序問題

首先第一個(gè)問題是順序問題，因?yàn)?OT 等算法都是依賴順序的，不同順序會(huì)導(dǎo)致結(jié)果不同，我們通過下面這張圖來說明：

假設(shè) Client A 在做兩次修改時(shí)發(fā)了兩個(gè)異步請(qǐng)求，可能因?yàn)榫W(wǎng)絡(luò)延遲導(dǎo)致第二個(gè)請(qǐng)求反而先到了，導(dǎo)致最終服務(wù)器版本和 Client A 所看到的不一致，同樣在服務(wù)器發(fā)往其它客戶端的請(qǐng)求時(shí)也會(huì)出現(xiàn)亂序的問題，如圖中 Client B 也有問題。

這個(gè)問題的解決方法很簡單，我們可以在客戶端和服務(wù)器端都加上隊(duì)列來保證請(qǐng)求順序，等前一個(gè)請(qǐng)求結(jié)束后再發(fā)下一個(gè)請(qǐng)求。

2. 存儲(chǔ)的原子操作

如果有多臺(tái)服務(wù)器，或者有多個(gè)線程/進(jìn)程在同時(shí)處理請(qǐng)求時(shí)就會(huì)遇到覆蓋問題，因?yàn)樽x寫數(shù)據(jù)庫并不是原子操作，比如下面的例子：

Web Server A 和 Web Server B 同時(shí)訪問數(shù)據(jù)庫，結(jié)果導(dǎo)致 Web Server A 的修改被覆蓋了。

好在這種問題還算比較常見，解決辦法可以有 3 種：

• 保證操作只在一個(gè)線程中執(zhí)行，比如某個(gè)文檔的更新只在某個(gè)固定的機(jī)器，使用 Node 這樣的單線程模型提供服務(wù)，這樣就不可能并行修改了
• 如果數(shù)據(jù)庫支持事務(wù)(transaction)，可以通過事務(wù)來解決
• 如果數(shù)據(jù)庫不支持事務(wù)，就只能用分布式鎖了，如 ZooKeeper

從實(shí)現(xiàn)角度來看，第一和第二種方法都比較簡單，而第三種方法會(huì)帶來很多問題，比如可能導(dǎo)致文檔被鎖死，假如上鎖后由于種種原因沒有執(zhí)行解鎖操作，這個(gè)文檔就會(huì)永遠(yuǎn)被鎖住，所以還得加上超時(shí)限制等策略。

然而在解決了原子操作后，我們將發(fā)現(xiàn)一個(gè)新的問題，那就是版本管理問題。

3. 版本管理問題

在前面的例子中，兩段新文本的修改都是基于同一個(gè)舊版本的，如果舊版本不一樣，就有可能出錯(cuò)，具體可以通過下面這張圖來解釋：

在這個(gè)例子中，Web Server A 接收到操作命令是將「a」文本改成「aa」，Web Server B 接收到操作命令是將「a」文本改成「ab」，這里我們加上了鎖機(jī)制來避免同時(shí)讀寫數(shù)據(jù)，Web Server A 首先得到了鎖，然后修改并更新數(shù)據(jù)，而 Web Server B 需要先等待數(shù)據(jù)解鎖，等 Web Server B 拿到數(shù)據(jù)后它已經(jīng)從「a」變成了「aa」，如果還按照 retain(1), insert('b') 進(jìn)行修改，數(shù)據(jù)將變成「ab」，而不是正確的「aab」，引起這個(gè)問題的原因就是舊版本不一致，Web Server B 需要根據(jù) Web Server A 的操作進(jìn)行操作轉(zhuǎn)換，變成 retain(2), insert('b')，然后才能對(duì)數(shù)據(jù)進(jìn)行修改。

因此想要解決這個(gè)問題，就必須引入版本，每次修改后都需要存儲(chǔ)下新版本，有了版本我們就能使用 diff 功能來計(jì)算不同版本的差異，得到其它人修改的內(nèi)容，然后通過 OT 合并算法合并兩個(gè)操作，如下所示：

在 Web Server A 操作前數(shù)據(jù)版本是 v=1，操作后變成了 v=2，等到 Web Server B 處理的時(shí)候，它通過版本比較發(fā)現(xiàn)不一致，所以就首先通過編輯距離算法算出 Web Server A 所做的操作，然后用這個(gè)操作來對(duì)自己的操作進(jìn)行轉(zhuǎn)換，得到正確的新操作，從而避免了覆蓋問題。

如果保存所有版本會(huì)導(dǎo)致數(shù)據(jù)量大大增加，所以還需要再優(yōu)化，比如每個(gè)服務(wù)器保存一個(gè)數(shù)據(jù)副本，但這里就不再展開了，可以看要支持分布式 還是挺麻煩的，不過目前出現(xiàn)了一些前后端整合的方案，如 ShareJS 和 OpenCoweb Framework，可以參考。

另外之前提到的 Myer’s diff 算法也有分布式解決方案，具體細(xì)節(jié)可以參考這篇文檔。

初步結(jié)論

• 如果你只是一個(gè)內(nèi)部小項(xiàng)目，實(shí)時(shí)性要求不高，但對(duì)準(zhǔn)確性要求比較高
• 推薦用 merge 或 diff3 工具，出現(xiàn)同一行沖突時(shí)由用戶來解決，這樣能避免自動(dòng)合并有可能出錯(cuò)的問題

• 如果想具備一定的實(shí)時(shí)性，流量不大，不想實(shí)現(xiàn)太復(fù)雜，且對(duì)少量的沖突可以忍受
• 推薦用 Myer’s diff，后端只開一個(gè) Node 進(jìn)程

• 如果想具備實(shí)時(shí)性，且有多臺(tái)后端服務(wù)同時(shí)處理
• 可以用 Operational Transformation 或 Myer’s diff，但需要注意分布式帶來的問題

• 如果需要很精細(xì)的控制，如支持富文本編輯等非單純文本格式
• 只能使用 Operational Transformation，但要自己實(shí)現(xiàn)操作合并算法，比如 XML 可以參考這篇文章

后續(xù)

除了文本合并，真正要做在線編輯還有很多細(xì)節(jié)處理，感興趣的同學(xué)可以繼續(xù)研究：

• 支持選區(qū)，看到其他人選擇的文本段，當(dāng)然，這也有合并問題
• 指針要更隨文本變化移動(dòng)到正確的位置
• 支持 undo