多人協(xié)同編輯一直是我們 PingCode Wiki 不太敢觸碰的一個功能，因為技術(shù)實現(xiàn)上有挑戰(zhàn)。但協(xié)同編輯技術(shù)本身已經(jīng)發(fā)展多年，解決方案已經(jīng)相對成熟，我們團隊也是在剛剛結(jié)束的 Q3 里完成了基于 PingCode Wiki 編輯器協(xié)同編輯的方案落地，所以這里想結(jié)合我們的技術(shù)選型及落地實踐經(jīng)驗談?wù)勎覍@塊技術(shù)的理解。

主要內(nèi)容以協(xié)同編輯技術(shù)為主，中間也會談?wù)剬夹g(shù)發(fā)展演進的理解。

一個場景

一個常見的場景，頁面發(fā)布沖突，這個交互在我們產(chǎn)品中真實存在過

兩個用戶基于相同的文章內(nèi)容進行了修改，一個用戶先發(fā)布，后一個用戶在發(fā)布的時候就會有這樣的提醒，雖然有提示，這其實對用戶來說是不友好的。

通常產(chǎn)品的解決方案有以下三種：

1. 悲觀鎖 - 一個文檔只能同時有一個用戶在編輯

2. 內(nèi)容自動合并、沖突處理

3. 協(xié)同編輯

第二種方案也有國外產(chǎn)品在做就是 Gitbook

Gitbook 也是一種解決問題的方式。

然后下面我們產(chǎn)品協(xié)同編輯的最終的交互截圖：

主流的協(xié)同編輯交互就是這樣，可以看到協(xié)作者列表以及每個協(xié)作者的正在輸入的位置，實時看到他們輸入了什么內(nèi)容，我們甚至可以直接相互對話，這種方式可以有效避免沖突。

雖然協(xié)同編輯最終呈現(xiàn)給用戶的就這一個界面，但是它背后卻有復(fù)雜的技術(shù)作為支持，接下來就一起看看協(xié)同編輯是如何運作的。

認識協(xié)同編輯

指導(dǎo)思想： 系統(tǒng)不需要是正確的，它只需要保持一致，并且需要努力保持你的意圖。

我覺得這句話可以作為協(xié)同編輯沖突處理的一個指導(dǎo)思想，它很簡潔明了的闡述了一個事情，就是協(xié)同編輯的沖突處理不一定是完全正確的，因為沖突本來就意味著操作是互斥的，互斥雙方的操作意圖不可能完全保留。沖突處理最重要的是保證協(xié)同雙方最終數(shù)據(jù)的一致性，然后在這個基礎(chǔ)上努力保持各自的操作意圖。

聊聊富文本數(shù)據(jù)模型

協(xié)同編輯是構(gòu)建在富文本編輯器之上的技術(shù)，它的實現(xiàn)一定程度上依賴于富文本數(shù)據(jù)模型的設(shè)計，這里介紹兩個比較有代表性的數(shù)據(jù)模型：

2012 年 Quill -> Delta

2016 年 Slate -> JSON

Delta 數(shù)據(jù)模型

Quill 編輯器顯示一段文字

它的數(shù)據(jù)表示是這樣的

它定義三種操作（insert、retain、delete），編輯器產(chǎn)生的每一個操作記錄都保存了對應(yīng)的操作數(shù)據(jù)，然后用一些列的操作表達富文本內(nèi)容，操作列表即最終的結(jié)果。

Slate 數(shù)據(jù)模型（JSON）

模型定義：

編輯器中有一個圖片類型的節(jié)點，對應(yīng)的數(shù)據(jù)結(jié)構(gòu)

屬性修改操作

我們可以看出雖然 Delta 和 Slate 數(shù)據(jù)的表現(xiàn)形式不同，但是他們都有一個共同點，就是針對數(shù)據(jù)的修改都可以由操作對象表達，這個操作對象可以在網(wǎng)絡(luò)中傳輸，實現(xiàn)基于操作的內(nèi)容更新，這個是協(xié)同編輯的一個基礎(chǔ)。

下面的部分我想聊聊在實現(xiàn)協(xié)同編輯時所面臨的最核心的問題。

協(xié)同編輯面臨的問題

這里先拋出問題，帶大家了解協(xié)同編輯所面臨的問題的具體場景，從問題出發(fā)，而后再討論解決方法。

問題一：臟路徑問題

假如編輯器中有三個段落，如下圖所示

這里用數(shù)組簡單模擬上面的三個段落，下圖展示了兩個用戶同時對數(shù)據(jù)修改產(chǎn)生的操作序列

可以看到左邊插入的段落「Testhub」插入位置是錯誤的

最上面的是原始的數(shù)據(jù)結(jié)構(gòu)，左右兩邊代表兩個用戶的操作序列，開始時他們的狀態(tài)一致。 左邊用戶在 Index=2 的位置插入一個新的段落「Access」、右邊用戶在 Index=4 的位置插入一個新的段落「Testhub」，他們各自應(yīng)用完自己的操作后，分別把操作通過消息服務(wù)傳給對方，這個時候左邊用戶接收到右邊用戶同步過來的消息「在 Index=4 插入 Texthub」直接應(yīng)用就會出現(xiàn)左邊的結(jié)果，這個結(jié)果是與用戶原本的意圖是不一致的，而且與右邊最終的數(shù)據(jù)不一致。

究其原因就是左邊用戶先進行的插入操作導(dǎo)致了它后面數(shù)據(jù)的索引發(fā)生變化，那么基于同步過來的操作直接應(yīng)用就會出現(xiàn)上圖的異常，我把這種情況稱為臟路徑問題。

問題二：并發(fā)沖突問題

這里以前面介紹的圖片數(shù)據(jù)結(jié)構(gòu)為例說明并發(fā)沖突的問題，下圖展示問題出現(xiàn)的過程，為了方便表達，圖片節(jié)點僅保留 type 和 align 兩個字段

最上面的數(shù)據(jù)結(jié)構(gòu)展示了兩個用戶開始時基于相同的狀態(tài)，圖片 align = ‘center’。

左邊用戶修改 align 屬性為 left、右邊用戶修改 align 屬性為 right，按照默認處理他們把各自的操作通過消息服務(wù)傳給對方，則會造成左邊最終顯示居右、右邊最終顯示居左，數(shù)據(jù)出現(xiàn)不一致，這種情況稱為并發(fā)沖突，他們基于相同的位置修改了相同的屬性。

問題三：undos/redos 問題

undos/redos 問題本質(zhì)還是前面所說的「臟路徑問題」+ 「并發(fā)沖突問題」，但是問題出現(xiàn)的場景有些不一樣，又相對復(fù)雜，所以這里單獨提出來了。

還是前面「臟路徑問題」的數(shù)據(jù)操作，這里只看右邊部分，分析它的撤回棧：

右邊用戶的操作列表：

右邊用戶撤回棧（序列與操作列表相反）：

① 刪除 Index=2 位置的 節(jié)點

② 刪除 Index=4 位置的 節(jié)點

執(zhí)行這種撤回邏輯其實是有問題，原因是撤回操作 ① 所對應(yīng)的操作的觸發(fā)者（Origin）是左邊用戶，如果按照這種撤回邏輯執(zhí)行左邊用戶可能就蒙了：” 我剛剛輸入的內(nèi)容怎么沒了 ！"，雖然邏輯上可以解釋，但它不符合用戶的使用習慣，所以對于協(xié)同編輯場景： 撤回應(yīng)當只撤回自己的操作，協(xié)同者的操作應(yīng)當被忽略。

右邊用戶撤回棧修復(fù)版：

① 刪除 Index=4 位置的節(jié)點

可以看到撤回棧只包含右邊的操作了，但是這又帶來了另外一個問題，大家仔細觀察可以發(fā)現(xiàn)現(xiàn)在 Index=4 對應(yīng)的節(jié)點是「Plan」，這個時候撤回會把「Plan」刪除掉，而右邊用戶在插入時插入的實際節(jié)點是「Testhub」，又出現(xiàn)了臟路徑。

除了這種「臟路徑」問題，「并發(fā)沖突」問題也會以類似的方式出現(xiàn)在，具體的邏輯就不再詳細分析了。

撤回棧忽略協(xié)同者操作后，撤回棧中的操作路徑會出現(xiàn)「臟路徑」問題 +「并發(fā)沖突」問題。

問題四：工程落地問題

這個問題比較好理解，就是協(xié)同編輯具體的落地問題：

1. 操作的同步
2. 光標的同步
3. 網(wǎng)絡(luò)不可知（網(wǎng)絡(luò)抖動、網(wǎng)絡(luò)延時、消息重連以及重連后的各種情況處理）
4. 文檔版本歷史
5. 離線編輯
6. ...

簡單歸納下上面所提到問題，其實可以分為兩類：

第一類：主要包含臟路徑、并發(fā)沖突、Undos/Redos等，可以統(tǒng)稱為數(shù)據(jù)一致性問題 ，它屬于學(xué)術(shù)問題的范疇，因為并發(fā)沖突的處理結(jié)果需要保證最終數(shù)據(jù)的一致性 ，這個需要經(jīng)過大量的學(xué)術(shù)研究、論證。

第二類：工程問題，重點是在解決「數(shù)據(jù)一致性」的基礎(chǔ)上實現(xiàn)一套具體的落地方案，除了前面提到的具體落地開發(fā)的功能點，還要考慮性能問題、數(shù)據(jù)傳輸效率問題等，這塊其實包含很大的工作量，是理論研究是否可以真正落地到生產(chǎn)實踐的關(guān)鍵。

第一類學(xué)術(shù)問題的解決方案就是數(shù)據(jù)一致性算法 ，學(xué)術(shù)界主要有兩個方面的研究：OT 算法 和 CRDT。

下面我們簡單介紹下這兩種算法。

數(shù)據(jù)一致性算法

這里不會過多介紹算法的實現(xiàn)細節(jié)，只是提供它處理沖突的思路，以及從問題的本身出發(fā)去看待它處理問題的一個思路，至于具體的算法實現(xiàn)大家有興趣可以去Github查找相關(guān)的資料去自己實踐。

OT

OT 全稱是 Operational Transformation，它的核心思想是操作轉(zhuǎn)換，通過轉(zhuǎn)換數(shù)據(jù)修改操作解決協(xié)同編輯中的各種問題。

發(fā)展歷史

OT是最早（1989年）被提出的協(xié)同沖突處理算法

2006 年被應(yīng)用到 Google docs

2011 年被應(yīng)用到

Office 365

至今 OT 仍然是實現(xiàn)協(xié)同編輯的最主要的技術(shù)選擇，Google docs 以及 Office 365 至今仍在采用 OT 的方案，國內(nèi)近些年來的出現(xiàn)的一些文檔類產(chǎn)品，包括石墨、釘釘、騰訊文檔等等，他們的協(xié)同編輯技術(shù)也都是基于 OT 的。

核心思想

就像它的名稱一樣，它的核心思想是對用戶協(xié)同編輯中產(chǎn)生的并發(fā)操作進行轉(zhuǎn)換，通過轉(zhuǎn)換對其中產(chǎn)生的 并發(fā)沖突 和 臟路徑 進行修正，然后把修正后的操作重新應(yīng)用到文檔中，保證操作的正確性和最終數(shù)據(jù)一致性。

原理圖

可以用 diamon 圖表示 OT 的核心原理

左圖解釋：

• a 標識左邊用戶的 operation
• b 表示右邊用戶的 operation
• 二者交叉的點表示文檔基于相同的初始狀態(tài)

左圖狀態(tài)：

兩邊用戶分別應(yīng)用操作 a 和 b 后 ，這時兩邊的文檔內(nèi)容都發(fā)生變化，且不一致；

操作轉(zhuǎn)換：

為了左右兩邊的文檔達到一致的狀態(tài)，我們需要對 a 和 b 進行操作轉(zhuǎn)換 transfrom(a, b) => (a', b') 得到兩個衍生的操作作 a' 和 b' 。

右圖應(yīng)用操作轉(zhuǎn)換的結(jié)果：

左邊 a 操作的衍生操作 a' 在右邊應(yīng)用，b' 在左邊應(yīng)用，最終文檔內(nèi)容達到一致。

這里說明的只是最基礎(chǔ)的 OT 模型，每個客戶端只有一個操作的情況（1 : 1），還有每個客戶端對應(yīng)多個操作的情況（M : N），還有 OT 控制算法等等。并且在真正實現(xiàn) OT 時有可能每一次操作轉(zhuǎn)換只得到一個衍生操作（ottypes 定義的操作變換就是這樣），跟前面的 transforms 有些不一樣，但這些不是特別重要，具體實現(xiàn)的時候在仔細理解，這里描述的只是 OT 算法的最基礎(chǔ)思路。

用 OT 解決「臟路徑」問題

如上圖所示 OT 在操作同步的過程中增加一層操作轉(zhuǎn)換的邏輯，用于糾正并發(fā)操作產(chǎn)生的臟路徑。

左邊同步右邊操作時索引由 4 轉(zhuǎn)換為 5。

操作轉(zhuǎn)換邏輯分析：

對于左邊用戶：

因為在協(xié)同操作「在 Index= 4 插入 Testhub」到達之前，已經(jīng)執(zhí)行了本地操作「在 Index=2 插入 Access」，而本地操作的索引 Index=2 小于協(xié)同操作的索引 Index=4，所以協(xié)同操作的索引路徑應(yīng)當加上本地新增的節(jié)點長度，也就是1，索引發(fā)生變化由 4 變成 5。

對于右邊用戶：

因為協(xié)同操作的索引路徑小于本地操作的索引路徑，本地操作不對協(xié)同操作產(chǎn)生影響，所以不需要做任何的轉(zhuǎn)換，直接應(yīng)用源操作即可。

用 OT 解決「并發(fā)沖突」問題

可以看到基于 OT 解決「并發(fā)沖突」同樣是使用操作轉(zhuǎn)換邏輯，只不過這次的操作轉(zhuǎn)換并不轉(zhuǎn)換臟路徑，而是協(xié)調(diào)沖突的屬性修改，上圖的處理結(jié)果是假定右邊操作后到達服務(wù)器的，最終結(jié)果收攏到居右顯示。

從上面的兩種場景分析可以看出這個操作轉(zhuǎn)換過程并沒有太復(fù)雜，雖然真實的場景下要考慮的情況會比這要多，但是也就是一層邏輯轉(zhuǎn)換。還有就是真實的場景需要對每一種操作類型做交叉操作轉(zhuǎn)換，比如 Delta 支持三種操作，那么可能要支持 3*3 種操作變換，Slate 支持9種原子操作，可能要實現(xiàn) 9*9 種操作變換，復(fù)雜度大概就是這樣。

OT 解決 undos/redos 問題

前面已經(jīng)說過 undos/redos 問題 本質(zhì)就是 「臟路徑」+「并發(fā)沖突」問題，所以 OT 的處理方案就是當編輯器接收到協(xié)同操作時，需要對 Undo棧、Redo棧中的所有操作循環(huán)執(zhí)行操作轉(zhuǎn)換邏輯，undo 或者 redo 時最終執(zhí)行的是轉(zhuǎn)換后的操作，具體的邏輯不再意義贅述。

算法說明

可以看出 OT 是對編輯器的數(shù)據(jù)操作進行轉(zhuǎn)換，所以 OT 算法的實現(xiàn)依賴于編輯器數(shù)據(jù)模型的設(shè)計，不同的數(shù)據(jù)模型需要實現(xiàn)不同的操作轉(zhuǎn)換算法。

OT 算法大概就說到這里，下面看看 CRDT 是如何處理數(shù)據(jù)一致性問題的。

CRDT

CRDT (Conflict-free Replicated Data Type)即“無沖突復(fù)制數(shù)據(jù)類型”，它主要被應(yīng)用在分布式系統(tǒng)中，保證分布式應(yīng)用的數(shù)據(jù)一致性，文檔協(xié)同編輯可以理解為分布式應(yīng)用的一種，它的本質(zhì)是數(shù)據(jù)結(jié)構(gòu)，通過數(shù)據(jù)結(jié)構(gòu)的設(shè)計保證并發(fā)操作數(shù)據(jù)的最終一致性。

CRDT 于 2011 年正式被提出。 基于 CRDT 的協(xié)同編輯框架 Yjs 大概在2015年開源，Yjs 是專門為在 web 上構(gòu)建協(xié)同應(yīng)用程序而設(shè)計的。

核心思想

大多數(shù)的 CRDT 為在文檔中創(chuàng)建的每個字符分配一個唯一的標識符。

為了確保文檔始終能夠收斂，CRDT 模型即使在刪除字符時也會保留元數(shù)據(jù)。

CRDT 最初是為了解決分布式系統(tǒng)最終數(shù)據(jù)一致性而提出的，它支持各個主機副本之間數(shù)據(jù)修改的直接同步，而且數(shù)據(jù)修改的同步順序以及同步的次數(shù)不影響最終結(jié)果，只要修改操作一致，數(shù)據(jù)的最終狀態(tài)就是一致的，也就是通常大家說的 CRDT 數(shù)據(jù)的滿足交換性和冪等性。

簡單介紹 CRDT 是如何處理沖突的

下圖描述了 Yjs 中處理沖突的算法模型，它是一個支持點對點傳輸?shù)臎_突處理模型。

                                  

上圖基礎(chǔ)說明

• 最下面的 “AB” 標識初始狀態(tài)
• 上面的每一根線代表一個插入操作
• 每一個操作都有一個唯一標識符
  比如 C0,0 操作中的 0,0 就是一個標識符
  第一個 0 指示用戶編號
  第二個 0 指示操作序列

例如，以下標識符表示 user 0 插入 “C” 在 “A” 和 “B” 之間

C0,0

相同的用戶 user 0 插入 “D” 在 “B” 和 “C” 之間，可以使用下面的操作

D0,1

這時候另外一個用戶期望插入 “E” 在 ”A“ 和 ”B“ 之間，但是這個操作是與前面插入 ”C“ 的操作（C0, 0）是并發(fā)操作。

此時用戶的唯一標識應(yīng)該與前面的不同，但是 clock 應(yīng)該是與前面的插入操作類似：

E1,0

由于存在并發(fā)沖突，Yjs 執(zhí)行與 OT 相同的沖突解決，并比較各自插入的用戶標識符。

由于用戶標識符 1 大于 0，因此生成的文檔為：

ACDEB

以上就是 Yjs 處理并發(fā)沖突的算法介紹，其實也不難理解，首先它的插入操作是基于已有字符的相對位置，在 OT 中使用的相當于是基于索引的絕對位置，然后就是沖突的處理，主要是比較用戶標識符，標識符小的先應(yīng)用，標識符大的后應(yīng)用。

上面是以 Yjs 為例介紹 CRDT 的沖突處理模型，下面看看 CRDT 是如何解決前面所提出的問題的。

用 CRDT 的思想解決臟路徑問題

首先我們使用類似于 CRDT 的方式描述剛才的數(shù)組：

可以看到右邊的列表使用唯一 Id 替換了原本數(shù)組的索引，然后描述內(nèi)容修改的操作也相應(yīng)的做一下調(diào)整

左邊操作：

在 Index=2 的位置插入 Access -> 在 111 之后插入 Access

右邊操作：

在 Index=4 的位置插入 Testhub -> 在 333 之后插入 Testhub

同步操作之后左邊和右邊最終的數(shù)據(jù)結(jié)構(gòu)應(yīng)該都是一樣的：

                           

因為這里只是模擬 CRDT ，解釋 CRDT 的思想，真實的 CRDT 通常是使用雙向鏈表，這里為了好理解所以仍然沿用數(shù)組，只是給數(shù)組中的每一個段落節(jié)點數(shù)據(jù)增加一個唯一標識。

CRDT 解決并發(fā)沖突

這里還是以圖片設(shè)置 align 屬性為例介紹，首先看看CRDT如何描述對象屬性及屬性修改：

左邊是圖片數(shù)據(jù)模型，右邊是模擬 CRDT 對應(yīng)的數(shù)據(jù)結(jié)構(gòu)，圖片對象中的每一個字段都使用結(jié)構(gòu)對象去描述內(nèi)容及內(nèi)容的修改，這里以 align 字段的代表看它的表達

操作 ①：

最上面藍色部分表示 align 的初始值是 center ，（140, 20）是這個初始數(shù)據(jù)結(jié)構(gòu)的標識，它也是基于某一個用戶的操作產(chǎn)生的。

這個時候一個用戶執(zhí)行了操作 ①，把 align 屬性修改為 left，產(chǎn)生了一個新的結(jié)構(gòu)對象，就是圖中橙色部分的表示。操作完成后，Map 中的 align 字段指向了新產(chǎn)生的結(jié)構(gòu)對象上，標識符是（141,0），因為（141,0）這個結(jié)構(gòu)對象是基于（140,20）的修改，所以它的 left 指向（140,20）這個結(jié)構(gòu)對象。

這個示例會有一些歧義，就是鏈表的數(shù)據(jù)結(jié)構(gòu)本身會有 left、right 兩個指針（在結(jié)構(gòu)對象左右兩邊），然后中間部分其實是內(nèi)容，但是我的內(nèi)容存儲的是圖片的 align 屬性，它的值可能是 left、center、right，跟鏈表在 left、right 指針在一起可能產(chǎn)生混淆，這里標記下，就是結(jié)構(gòu)對象中的第二個塊描述的是屬性內(nèi)容。

操作②：

這個時候另外一個用戶基于剛剛產(chǎn)生的結(jié)構(gòu)對象（141,0）進行了操作 ②，把 align 屬性修改為right，產(chǎn)生了一個新的結(jié)構(gòu)對象，就是圖中橙紅色部分的表示。

圖片下半部分是這兩個操作之后最終的數(shù)據(jù)結(jié)構(gòu)，它是一個雙向鏈表的表達（這種表達已經(jīng)很接近 Yjs 真實的數(shù)據(jù)結(jié)構(gòu)了），它不僅可以描述最終的數(shù)據(jù)狀態(tài)（right），還可以表達出數(shù)據(jù)修改的順序：center -> left -> right。

這個示例其實描述的是順序操作，每一個操作基于的狀態(tài)都是最新狀態(tài)，兩個用戶執(zhí)行的操作是有確定先后順序的。

下面看看兩個用戶并發(fā)的執(zhí)行屬性修改時產(chǎn)生的數(shù)據(jù)結(jié)構(gòu)：

與前面最大的不同就是執(zhí)行操作 ② 和執(zhí)行操作 ① 所基于的狀態(tài)是一致的，都是基于 align = 'center' 進行修改的，這種情況表達的就是并發(fā)數(shù)據(jù)的修改。接下來就是并發(fā)處理的邏輯了，跟前面介紹的一致，這個時候操作 ① 的對應(yīng)的用戶標識 141 小于操作 ② 對應(yīng)用戶標識 142，所以先應(yīng)用操作 ①，后應(yīng)用操作 ②，所以最終圖片的 align 屬性狀態(tài)是 right。

CRDT 解決 undso/redos問題

CRDT 可以理解為完全沒有「臟路徑」問題，然后并發(fā)沖突問題也完全可以基于 CRDT 的標識符（時間戳）去解決，那么基于 CRDT 的方案中，實現(xiàn) undos/redos 應(yīng)該就比較簡單了，只需要根據(jù) CRDT 的數(shù)據(jù)結(jié)構(gòu)的新增或者刪除去實現(xiàn) undos/redos 棧就可以有效解決問題。 假如進行了一個生成結(jié)構(gòu)對象的操作，那么撤回的時候可能就把它標記刪除。

假如進行一個刪除結(jié)構(gòu)對象的操作，在執(zhí)行撤回操作時可能就對應(yīng)于重新執(zhí)行結(jié)構(gòu)對象的插入操作。

CRDT 算法說明

與 OT 不同，CRDT是一種全新的解決方案，它不依賴于編輯器實現(xiàn)，對于任何的編輯器數(shù)據(jù)模型都可以使用一套 CRDT 數(shù)據(jù)結(jié)構(gòu)去處理沖突，也是因為數(shù)據(jù)結(jié)構(gòu)的性質(zhì)，它也可以不依賴中心化的服務(wù)器，而且穩(wěn)定性非常高，這區(qū)別于 OT，OT可以理解為是通過算法控制保證數(shù)據(jù)一致性，CRDT 通過數(shù)據(jù)結(jié)構(gòu)設(shè)計保證數(shù)據(jù)一致性，它在復(fù)雜的網(wǎng)絡(luò)環(huán)境中的處理是更穩(wěn)健的，CRDT 的代價就是要保存更多的元數(shù)據(jù)，這會帶來一定內(nèi)存消耗，但是這是可優(yōu)化的，事實證明這個代價在協(xié)同編輯場景是完全可忽略不計的。

Yjs 優(yōu)化

其實基于 CRDT 的協(xié)同編輯方案一直是被質(zhì)疑的，而且質(zhì)疑的聲音到現(xiàn)在都一直還在，Yjs 也受其影響。盡管基于 CRDT 實現(xiàn)的 Yjs 已經(jīng)如此強大了，大家還總是拿 CRDT 的內(nèi)存開銷、性能開銷說事，以我目前的了解：內(nèi)存開銷、性能問題對于 Yjs 來說早已不是問題，所以這里簡單介紹下 Yjs 的優(yōu)化，這部分內(nèi)容的整理基于官方對 Yjs 優(yōu)化的介紹，性能問題和內(nèi)存占用問題每一個點都有大量的基準測試去驗證，這里只對優(yōu)化方式進行一些簡單的介紹。

一、結(jié)構(gòu)表示優(yōu)化

當用戶從左到右鍵入內(nèi)容“ABC”時，它將執(zhí)行以下操作： insert(0, "A") ? insert(1, "B") ? insert(2, "C")。 對文本內(nèi)容建模的 YATA CRDT 的鏈表將如下所示：

插入內(nèi)容“ABC”的CRDT模型（假設(shè)用戶具有唯一的客戶端標識符“1”） 所有的 CRDT 都會為每個字符分配某種唯一的 ID 和附加的元數(shù)據(jù)，這對于大型文檔來說非常消耗內(nèi)存。我們不能刪除元數(shù)據(jù)，因為它是解決沖突的必要條件。

Yjs 也唯一地標識每個字符和分配元數(shù)據(jù)，有效地表示了這些信息。較大的文檔插入表示為單個 Item 對象，使用字符偏移量唯一地單獨標識每個字符。

然后這塊是有優(yōu)化空間，下面的 Item 也可以將字符“A”唯一標識為 {client:1,clock:0}，字符“B”為 {client:1,clock:1}，依此類推......

Item {
    id: { client: 1, clock: 0 },
    content: 'ABC',
    length: 3,
    ...
}

如果用戶將大量內(nèi)容復(fù)制/粘貼到文檔中，則插入的內(nèi)容由單個 Item 表示。此外，從左到右寫入的單字符插入可以合并為單個 Item。重要的是，我們能夠在不丟失任何元數(shù)據(jù)的情況下拆分和合并項。

這就是 Yjs 對于數(shù)據(jù)表示的優(yōu)化，通過這種方式可以有效減少 Yjs 數(shù)據(jù)結(jié)構(gòu)中結(jié)構(gòu)對象的數(shù)量，從而有效減少內(nèi)存的占用。

然而，這種方法最重要的缺點是處理單個字符變得更加復(fù)雜（也沒關(guān)系，因為這是 Yjs 框架做的事情）。

當另一個用戶希望在“B”和“C”之間插入一個字符時，需要將操作的“BC”部分拆分為兩個單獨的操作。 我們不能重新組合這些操作，因為在 CRDT 中我們永遠不能刪除字符或從文檔樹中刪除它們。

二、刪除優(yōu)化

我們可以指示需要刪除字符的唯一方法是將其標記為已刪除。雖然如此，這塊還是有優(yōu)化空間，以 Slate 的段落結(jié)構(gòu)為例，當你將段落標記為刪除時，你也可以將段落下的所有文本結(jié)構(gòu)標記為刪除。

比如，一個段落包含文本 ”ABC“，當標記段落刪除時：

（Paragraph）D

相當于將以下所有文本節(jié)點（字符）也標記為刪除：

AD    BD    CD

這是我們可以完全從內(nèi)存中刪除所有字符節(jié)點對應(yīng)的結(jié)構(gòu)，因為字符節(jié)點是被刪除段落的子節(jié)點。

基于這種方式也可以有效減少 Yjs 的內(nèi)存占用。

三、操作定義

這塊其實是從 V8 的角度去優(yōu)化 Yjs 結(jié)構(gòu)對象的創(chuàng)建，整體思路就是讓 Yjs 創(chuàng)建對象的過程能夠被瀏覽器優(yōu)化，無論是內(nèi)存占用還是對象創(chuàng)建速度。

四、查詢優(yōu)化

大家應(yīng)該都知道使用雙向鏈表最大的弊端就是查詢性能，因為每一個操作你都需要遍歷整個鏈表去查詢某一個結(jié)構(gòu)對象，當 Yjs 結(jié)構(gòu)對象數(shù)據(jù)非常巨大時，執(zhí)行的每一個操作有可能會因此損耗一定的時間，Yjs 對此也是有優(yōu)化措施的，目前我從源代碼中看到的是，Yjs 會對用戶經(jīng)常操作的結(jié)構(gòu)對象進行緩存（其實就是緩存位置），查找過程中優(yōu)先重緩存中去匹配，通過如果緩存命中則可以有效提高數(shù)據(jù)的查詢速度。

五、編碼優(yōu)化

Yjs 會對網(wǎng)絡(luò)中傳輸以及存儲在數(shù)據(jù)庫中結(jié)構(gòu)對象進行統(tǒng)一的二進制編碼，當然也會提供相應(yīng)的解碼操作，通過二進制編碼可以有效的提高數(shù)據(jù)的傳輸效率。

OT vs CRDT

OT 和 CRDT 算法的部分就到這里，下面介紹下基于 OT 和 CRDT 算法在實際開發(fā)中的工程落地方案。

開源解決方案

這里主要介紹兩種方案，一種是基于 OT 的 ShareDB 方案，另外一種是基于 CRDT 的 Yjs 方案。

ShareDB 方案

針對 OT 其實社區(qū)一直有一個對應(yīng)的解決方案 - sharedb，只是比較遺憾的是 slate 和 sharedb 該怎么結(jié)合缺少明確方案，我在 Github 上搜索發(fā)現(xiàn)也有人研究過，只不過是針對的是 slate 比較舊的版本，也不怎么維護了，但是它的實現(xiàn)給了我一些思路，加上原本的理解就有了現(xiàn)在的方案：slate + ottype-slate + sharedb。

ShareDB ShareDB 是基于 OT 實現(xiàn)協(xié)同編輯的一套解決方案，提供協(xié)同消息轉(zhuǎn)發(fā)、光標同步、數(shù)據(jù)持久化、OT 控制算法等等。

ShareDB 架構(gòu)圖如下

下邊淺藍色部分是 ShareDB 包含的主要模塊，ShareDB 會提供基于 WebScoket 的消息服務(wù)實現(xiàn)以及對應(yīng)的前端鏈接消息服務(wù)的SDK，可以同步操作和光標，ShareDB 也包含數(shù)據(jù)持久化部分的實現(xiàn)。

最左邊的 OTType 是核心的操作轉(zhuǎn)換的部分，因為不同編輯器的數(shù)據(jù)模型需要實現(xiàn)單獨 OT 的算法，所以 ShareDB 本身不包含 OT 的實現(xiàn)，而是提供了標準的接入接口，任何數(shù)據(jù)類型只要基于這個接口實現(xiàn)了對應(yīng)的操作轉(zhuǎn)換算法，那么它就可以通過注冊的方式接入到 ShareDB 中，這個標準接口的定義可以參考 ottypes 中的實現(xiàn)。

上面紫色部分是目前 ShareDB 可以支持的編輯器，編輯器想要接入最終的任務(wù)就是基于編輯器的數(shù)據(jù)模型實現(xiàn)一個自己的 OTType 就可以，然后 Quill 編輯器的 Delta 數(shù)據(jù)模型本身就實現(xiàn)了操作轉(zhuǎn)換的邏輯，所以 Quill 是最容易接入的。

ottypes

前面有提到的 ottypes 其實是定了一種標準的 OT 的接口，根據(jù)這種標準實現(xiàn)的的類型轉(zhuǎn)換可以都可以完美的與 ShareDB 配合使用，共同完成數(shù)據(jù)的協(xié)同編輯，前面方案中提到的 ottype-slate 其實就是 ottypes 的一種實現(xiàn)。

ottype-slate

個人感覺 slate 中定義的數(shù)據(jù)模型以及數(shù)據(jù)變換可讀性非常高，它的表達方式以及提供的工具函數(shù)式非常清晰且完善，并且每種原子操作都是可逆的，我大概看了 sharedb 默認支持的基于 JSON 的操作變換實現(xiàn)(ot-json0)，ot-json 針對數(shù)據(jù)修改的表達，可讀性還是非常差的，所以我感覺可以自己寫一個針對 slate 數(shù)據(jù)模型的 OTType 實現(xiàn)，所以就有了ottype-slate。

ottype-slate 當前只是初步實現(xiàn)了部分操作變換函數(shù)，然后結(jié)合 slate-angular 和 sharedb 搭建了一個協(xié)同編輯的測試 Demo，剩余的部分操作變換函數(shù)后續(xù)慢慢補充。

ShareDB 方案流程圖

從上面開始看，假如用戶在基于 Slate 編輯器進行協(xié)同編輯，可以看到用戶內(nèi)容修改產(chǎn)生的 operations 在傳遞給 ShareDB Serve 之前可能會經(jīng)過操作轉(zhuǎn)換，這取決于操作所基于的文檔版本和服務(wù)器的文檔版本是否一致，不一致就需要計算出兩個版本差異的部分操作，拿差異的操作與新產(chǎn)生的操作進行操作轉(zhuǎn)換，基于操作轉(zhuǎn)換的結(jié)果去同步內(nèi)容的修改，這個過程之后就是把最終的操作通過消息服務(wù)轉(zhuǎn)發(fā)給其它客戶端，其它客戶端在應(yīng)用這個操作，實現(xiàn)協(xié)同編輯。

從這個流程可以看出操作轉(zhuǎn)換最終有可能是在服務(wù)端進行，也有可能在客戶端進行。因為操作轉(zhuǎn)換的過程需要通過 OT 控制算法實現(xiàn)多客戶端的操作變換的協(xié)調(diào)，這個過程必須走一個中心化的服務(wù)器，否則過程很難控制，所以基于 OT 算法這個方案是不能實現(xiàn)點對點通訊的。

Yjs 方案

Yjs 是基于 CRDT 的開源解決方案，它提供了比較完善的生態(tài)，在2020年的時候社區(qū)也出現(xiàn)了基于 Slate 編輯器的中間綁定層。

Yjs 架構(gòu)圖

y-websocket - 提供協(xié)同編輯時的消息通訊，包含服務(wù)端實現(xiàn)和前端集成的SDK

y-protocols - 定義消息通訊協(xié)議，包括消息服務(wù)初始化、內(nèi)容更新、鑒權(quán)、感知系統(tǒng)等

y-redis - 持久化數(shù)據(jù)到 Redis

y-indexeddb - 持久化數(shù)據(jù)到 IndexedDB

在上層 Yjs 支持任何大部分主流編輯器的接入，因為 Yjs 也可以理解為一套獨立的數(shù)據(jù)模型，它與每種編輯器本身的數(shù)據(jù)模型是不同的，所以每種編輯器想要接入 Yjs 都必須實現(xiàn)一個中間綁定層，用于編輯器數(shù)據(jù)模型與 Yjs 數(shù)據(jù)模型轉(zhuǎn)換，這個轉(zhuǎn)換是雙向的，官方目前提供了 Prosemirror、Quill、Ace等編輯器的中間綁定層，基于 Slate 編輯器的中間綁定層是由社區(qū)開發(fā)者提供的。

Yjs 方案流程圖

從上到下描述一下用戶操作的同步過程，假如上面用戶在基于 Slate 編輯器進行一些數(shù)據(jù)的修改，它產(chǎn)生的 operations 需要先經(jīng) Yjs Bindings 把基于 Slate 的操作轉(zhuǎn)換為 Yjs 的數(shù)據(jù)修改（使用applySlate），更新本地 Yjs 的數(shù)據(jù)結(jié)構(gòu)，當 Yjs 的數(shù)據(jù)結(jié)構(gòu)被修改后它可以通過一種網(wǎng)絡(luò)傳輸協(xié)議把數(shù)據(jù)結(jié)構(gòu)的變更同步給協(xié)作者，協(xié)作者直接應(yīng)用這個遠程的數(shù)據(jù)同步到本地的 Yjs 數(shù)據(jù)結(jié)構(gòu)上，然后 Yjs Bindings 中還有一個訂閱操作，就是訂閱遠程的 Yjs 數(shù)據(jù)修改，然后通過 applyYjs 方法把 Yjs 數(shù)據(jù)修改的表達轉(zhuǎn)化成 Slate 的 operations，最終 Slate 應(yīng)用這個 operations 實現(xiàn)內(nèi)容的同步，中間并發(fā)沖突的問題完全交給 Yjs 數(shù)據(jù)結(jié)構(gòu)去處理，轉(zhuǎn)化到 Slate 的操作永遠跟 Yjs 的處理結(jié)果一致。

從流程圖可以看出每一個客戶端都維護了一個 Yjs 數(shù)據(jù)結(jié)構(gòu)的副本，這個數(shù)據(jù)結(jié)構(gòu)副本所表達的內(nèi)容與Slate編輯器數(shù)據(jù)所表達的內(nèi)容完全一樣，只是它們承擔職責不同，Slate 數(shù)據(jù)供編輯器及其插件渲染使用，然后 Yjs 數(shù)據(jù)結(jié)構(gòu)用于處理沖突、保證數(shù)據(jù)一致性，數(shù)據(jù)的修改最終是通過 Yjs 的數(shù)據(jù)結(jié)構(gòu)來進行同步的。

值得一提的是 Yjs 數(shù)據(jù)結(jié)構(gòu)本身支持端端數(shù)據(jù)的直接同步，可以不借助中心化的服務(wù)器。

PingCode Wiki 協(xié)同方案選擇

2021年了，技術(shù)應(yīng)該變一變了，協(xié)同編輯方案不應(yīng)該只有OT，下面簡單談?wù)勎覀冏黾夹g(shù)選型時的考量。

今年 Q3 我們團隊正式開始做協(xié)同編輯，我們的編輯器是基于Slate框架實現(xiàn)的，雖然在這之前我對協(xié)同編輯有一些調(diào)研，但都不成體系，所以在 Q3 開始的時候我們又重新進行了一次調(diào)研，核心問題還是選 OT 還是 CRDT，下面是我們當時掌握的一些情況：

OT 方案

• TinyMCE 編輯器基于 Slate 模型 + OT 實現(xiàn)協(xié)同編輯，但是他們的不開源
• 大廠產(chǎn)品的協(xié)同編輯方案都是基于 OT 實現(xiàn)的
• 對于 OT 當時只是了解思路，不知道如何落地 ，準確的說都不知道協(xié)同編輯應(yīng)該包含哪些基礎(chǔ)模塊

CRDT 方案

• 社區(qū)對于 CRDT 一直有一些質(zhì)疑的聲音
• CRDT 缺少商業(yè)產(chǎn)品上的應(yīng)用案例（文檔類）
• Yjs 生態(tài)比較完善 基于Slate編輯器有成熟的Demo
• 翻譯了部分 Yjs 技術(shù)資料、對 Yjs 印象不錯
• 基于我們的編輯器搭建了Yjs的協(xié)同編輯Demo，可以跑通

當時調(diào)研的 slate-yjs 提供的 Demo 截圖如下

這個Demo可以說功能非常完善，而且技術(shù)棧跟我們基本是完全吻合。 雖然對于 CRDT 社區(qū)有一些質(zhì)疑的聲音，但是事實總要驗證一下，因為 Yjs 完善的 Demo 以及對它的初步印象，我們決定按照 Yjs 的方案試一試。

這基本上是我們選型的過程了，因為之后的過程就很順利，首先是我們基于 Yjs 的生態(tài)快速在測試環(huán)境上搭建了協(xié)同編輯的初步版本，逐漸的我們在官方提供的消息服務(wù)的基礎(chǔ)上重新實現(xiàn)了一個我們自己的消息服務(wù)，加上鑒權(quán)，然后基于就是逐步排查和修復(fù)協(xié)同編輯的一些細節(jié)問題，包括消息服務(wù)連接的控制、undos/redos 的問題、彈框處理等等，總之就是沒有太大的問題，而且性能上基本沒有損耗，大文檔的加載（大概5-6萬字的內(nèi)容） Yjs 基本可以在毫秒級去處理完成。

現(xiàn)在重新來看Yjs方案的選擇，我覺得我們這套方案的選擇非常正確，在這個過程中沒有浪費一點團隊的時間，而且在Q3實現(xiàn)協(xié)同編輯的過程中，大家都很輕松，而且在 Yjs 上我們還可以學(xué)到很多東西，下面是我總結(jié)的 Yjs 在功能以及設(shè)計上的一些優(yōu)勢：

功能上：

• 設(shè)計了完善的感知體系，用戶同步用戶在線狀態(tài)、光標位置等
• 支持離線編輯
• 網(wǎng)絡(luò)不可知，可以非常穩(wěn)健的處理網(wǎng)絡(luò)抖動、網(wǎng)絡(luò)延時等問題
• 提供 undos/redos 的管理
• 版本歷史

設(shè)計上：

• 模塊職責劃分清楚，尤其是抽取獨立的協(xié)議庫 y-protocols，讓復(fù)雜的消息同步變得非常的清晰可控
• 網(wǎng)絡(luò)協(xié)議/數(shù)據(jù)持久化 實現(xiàn)松耦合，網(wǎng)絡(luò)協(xié)議支持接入 y-websocket、y-webrtc，持久化 y-redis、社區(qū)有提供 y-mongodb
• 可以很快的與任意編輯器集成

可以這么說現(xiàn)在 Yjs 對于我們的意義，就之于兩年前 Slate 對我們的意義，是我們這個階段了解和學(xué)習協(xié)同編輯的重要支柱，實現(xiàn)協(xié)同編輯到底包含哪些東西、都有什么問題、Yjs 是怎么解決的、Yjs 有什么缺點、它是如何優(yōu)化的等等，就像一個老師幫助你完成你的工作，然后讓你在這個過程中有所進步。

談?wù)劶夹g(shù)的演進

1989 年 OT 算法正式提出，代表著協(xié)同編輯技術(shù)的開始，但是當時編輯器的架構(gòu)設(shè)計遠不能達到現(xiàn)在的水平，它的理念在那個時期一定是非常超前的，現(xiàn)在協(xié)同編輯數(shù)據(jù)模型的演變我覺得一定程度上也有受 OT 算法的影響。

2006 年 Google 把 OT 真正到帶到了商業(yè)產(chǎn)品中，這個過程經(jīng)歷大概十多年，然后就是 2011 微軟緊接著基于 OT 實現(xiàn)了協(xié)同編輯，這中間也經(jīng)歷了大概5年的時間，我覺得這個時間跨度一定跟當時的編輯器技術(shù)背景有關(guān)系，這個時期其實協(xié)同編輯技術(shù)也只是在這些頂尖科技公司得到發(fā)展和應(yīng)用。

2011 年 CRDT 算法提出代表著一種新的協(xié)同編輯方案的出現(xiàn)。

2012 年 Quill 編輯器開源，它的數(shù)據(jù)模型 Delta 就是基于 OT 算法設(shè)計的，個人覺得 Quill 編輯器的開源對于協(xié)同編輯以及 OT 的發(fā)展是一個重要的里程碑，在以前協(xié)同編輯可能是少數(shù)大公司在研究的技術(shù)，Quill 編輯之后協(xié)同編輯就逐漸應(yīng)用更多的中小公司產(chǎn)品中，比如國內(nèi)的石墨文檔整個核心技術(shù)包括協(xié)同編輯可能就是基于 Quill 和 Delta 實現(xiàn)的。

2013年 ShareDB 開源，代表著基于 OT 的一套完整解決方案的落地。

2015 年 Yjs 開源代表著基于 CRDT 的協(xié)同方案正式得到發(fā)展。 2019 年 Slate 框架基于 TypeScript 完全重構(gòu)，它的數(shù)據(jù)模型得到進一步優(yōu)化，目前已經(jīng)極其簡潔優(yōu)雅，我覺得這也代表著一種變化。

2020 年 slate-yjs 開源，它是 Yjs 和 Slate 的一個結(jié)合，有了這個結(jié)合其實就有了一個基于 Slate 的完整協(xié)同方案。

2021 年我覺得我們在這個時間選擇 Yjs 也很合理，不同的時期技術(shù)的選擇一定是不同的。

這里想延伸一點就是 OT 算法其實是在現(xiàn)有的編輯器數(shù)據(jù)模型的基礎(chǔ)上實現(xiàn)的協(xié)同編輯，它的思想也很好理解，其實反過來想，現(xiàn)在協(xié)同編輯所遇到的數(shù)據(jù)一致性的問題也有一部分原因是由于數(shù)據(jù)模型中「數(shù)據(jù)修改操作」的表達所引起的，比如數(shù)據(jù)修改操作中基于索引的方式去定位要修改的數(shù)據(jù)所產(chǎn)生的臟路徑問題，總之 OT 可以理解現(xiàn)有技術(shù)思路下的解決方案。然后 CRDT 其實是一種獨立于現(xiàn)有編輯器架構(gòu)的解決方案，是一種技術(shù)上的創(chuàng)新，它為實現(xiàn)協(xié)同編輯提供了一種新的思路，并且它有很多優(yōu)秀的特性，比如支持點到點的數(shù)據(jù)同步，并且基于數(shù)據(jù)結(jié)構(gòu)的沖突處理其實是更穩(wěn)健的，雖然基于 CRDT 的數(shù)據(jù)結(jié)構(gòu)在實現(xiàn)起來復(fù)雜度比較高，但是這個復(fù)雜度可以完全由框架層去完成，使用者其實對這塊可以是無感的。

收尾

這篇文章其實是為我們公司今年舉辦的 「PingCode 開發(fā)者大會 2021」而準備的主題內(nèi)容，然后我本身其實也想對協(xié)同編輯這塊的內(nèi)容做一個整理，趁這個機會就一起做了，主要是闡述了我對這塊技術(shù)的一個認識，包括協(xié)同編輯是什么，協(xié)同編輯所遇到的一些問題或者說挑戰(zhàn)，然后主流協(xié)同編輯沖突處理算法是怎么工作的，再到后面的基于沖突處理算法的開源解決方案等等，這里面提到的大部分技術(shù)其實都是開源的，內(nèi)心其實是非常佩服這些開源作品的貢獻者的，也在督促自己努力的去做更多的開源輸出。

開源項目地址：

github.com/quilljs/qui…
github.com/ottypes
github.com/pubuzhixing…
github.com/qqwee/slate…
github.com/share/share…
github.com/yjs/yjs

參考文章

OT

SharedPen 之 Operational Transformation
This Is How to Build a Collaborative Text Editor Using Rails

協(xié)同編輯原理與實踐 - 沙洲

Yjs
Yjs——一個基于CRDT的數(shù)據(jù)協(xié)同框架
Yjs deep dive: How Yjs makes real-time collaboration easier and more efficient
blog.kevinjahns.de/are-crdts-s…

這個倉儲記錄了我們在做協(xié)同編輯時整理的一些資料

github.com/pubuzhixing…?

轉(zhuǎn)自https://juejin.cn/post/7030327005665034247