多人協同編輯技術的演進

多人協同編輯一直是我們 PingCode Wiki 不太敢觸碰的一個功能，因爲技術實現上有挑戰。但協同編輯技術本身已經發展多年，解決方案已經相對成熟，我們團隊也是在剛剛結束的 Q3 裏完成了基於 PingCode Wiki 編輯器協同編輯的方案落地，所以這裏想結合我們的技術選型及落地實踐經驗談談我對這塊技術的理解。

主要內容以協同編輯技術爲主，中間也會談談對技術發展演進的理解。

一個場景

一個常見的場景，頁面發佈衝突，這個交互在我們產品中真實存在過

兩個用戶基於相同的文章內容進行了修改，一個用戶先發布，後一個用戶在發佈的時候就會有這樣的提醒，雖然有提示，這其實對用戶來說是不友好的。

通常產品的解決方案有以下三種：

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

2. 內容自動合併、衝突處理

3. 協同編輯

第二種方案也有國外產品在做就是 Gitbook

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

然後下面我們產品協同編輯的最終的交互截圖：

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

雖然協同編輯最終呈現給用戶的就這一個界面，但是它背後卻有複雜的技術作爲支持，接下來就一起看看協同編輯是如何運作的。

認識協同編輯

指導思想： 系統不需要是正確的，它只需要保持一致，並且需要努力保持你的意圖。

我覺得這句話可以作爲協同編輯衝突處理的一個指導思想，它很簡潔明瞭的闡述了一個事情，就是協同編輯的衝突處理不一定是完全正確的，因爲衝突本來就意味着操作是互斥的，互斥雙方的操作意圖不可能完全保留。衝突處理最重要的是保證協同雙方最終數據的一致性，然後在這個基礎上努力保持各自的操作意圖。

聊聊富文本數據模型

協同編輯是構建在富文本編輯器之上的技術，它的實現一定程度上依賴於富文本數據模型的設計，這裏介紹兩個比較有代表性的數據模型：

2012 年 Quill -> Delta

2016 年 Slate -> JSON

Delta 數據模型

Quill 編輯器顯示一段文字

它的數據表示是這樣的

它定義三種操作（insert、retain、delete），編輯器產生的每一個操作記錄都保存了對應的操作數據，然後用一些列的操作表達富文本內容，操作列表即最終的結果。

Slate 數據模型（JSON）

模型定義：

編輯器中有一個圖片類型的節點，對應的數據結構

屬性修改操作

我們可以看出雖然 Delta 和 Slate 數據的表現形式不同，但是他們都有一個共同點，就是針對數據的修改都可以由操作對象表達，這個操作對象可以在網絡中傳輸，實現基於操作的內容更新，這個是協同編輯的一個基礎。

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

協同編輯面臨的問題

這裏先拋出問題，帶大家瞭解協同編輯所面臨的問題的具體場景，從問題出發，而後再討論解決方法。

問題一：髒路徑問題

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

這裏用數組簡單模擬上面的三個段落，下圖展示了兩個用戶同時對數據修改產生的操作序列

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

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

究其原因就是左邊用戶先進行的插入操作導致了它後面數據的索引發生變化，那麼基於同步過來的操作直接應用就會出現上圖的異常，我把這種情況稱爲髒路徑問題。

問題二：併發衝突問題

這裏以前面介紹的圖片數據結構爲例說明併發衝突的問題，下圖展示問題出現的過程，爲了方便表達，圖片節點僅保留 type 和 align 兩個字段

最上面的數據結構展示了兩個用戶開始時基於相同的狀態，圖片 align = ‘center’。

左邊用戶修改 align 屬性爲 left、右邊用戶修改 align 屬性爲 right，按照默認處理他們把各自的操作通過消息服務傳給對方，則會造成左邊最終顯示居右、右邊最終顯示居左，數據出現不一致，這種情況稱爲併發衝突，他們基於相同的位置修改了相同的屬性。

問題三：undos/redos 問題

undos/redos 問題本質還是前面所說的「髒路徑問題」+ 「併發衝突問題」，但是問題出現的場景有些不一樣，又相對複雜，所以這裏單獨提出來了。

還是前面「髒路徑問題」的數據操作，這裏只看右邊部分，分析它的撤回棧：

右邊用戶的操作列表：

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

① 刪除 Index=2 位置的 節點

② 刪除 Index=4 位置的 節點

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

右邊用戶撤回棧修復版：

① 刪除 Index=4 位置的節點

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

除了這種「髒路徑」問題，「併發衝突」問題也會以類似的方式出現在，具體的邏輯就不再詳細分析了。

撤回棧忽略協同者操作後，撤回棧中的操作路徑會出現「髒路徑」問題 +「併發衝突」問題。

問題四：工程落地問題

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

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

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

第一類：主要包含髒路徑、併發衝突、Undos/Redos 等，可以統稱爲數據一致性問題 ，它屬於學術問題的範疇，因爲併發衝突的處理結果需要保證最終數據的一致性 ，這個需要經過大量的學術研究、論證。

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

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

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

數據一致性算法

這裏不會過多介紹算法的實現細節，只是提供它處理衝突的思路，以及從問題的本身出發去看待它處理問題的一個思路，至於具體的算法實現大家有興趣可以去 Github 查找相關的資料去自己實踐。

OT

OT 全稱是 Operational Transformation，它的核心思想是操作轉換，通過轉換數據修改操作解決協同編輯中的各種問題。

發展歷史

OT 是最早（1989 年）被提出的協同衝突處理算法

2006 年被應用到 Google docs

2011 年被應用到

Office 365

至今 OT 仍然是實現協同編輯的最主要的技術選擇，Google docs 以及 Office 365 至今仍在採用 OT 的方案，國內近些年來的出現的一些文檔類產品，包括石墨、釘釘、騰訊文檔等等，他們的協同編輯技術也都是基於 OT 的。

核心思想

就像它的名稱一樣，它的核心思想是對用戶協同編輯中產生的併發操作進行轉換，通過轉換對其中產生的 併發衝突 和 髒路徑 進行修正，然後把修正後的操作重新應用到文檔中，保證操作的正確性和最終數據一致性。

原理圖

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

左圖解釋：

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

左圖狀態：

兩邊用戶分別應用操作 a 和 b 後 ，這時兩邊的文檔內容都發生變化，且不一致；

操作轉換：

爲了客戶端和服務端的文檔達到一致的狀態，我們需要對 a 和 b 進行操作轉換 transfrom(a, b) => (a', b') 得到兩個衍生的操作作 a'和 b' 。

右圖應用操作轉換的結果：

左邊用戶的 a 操作的衍生操作 a'在右邊用戶端應用，b' 在左邊用戶端應用，最終文檔內容達到一致。

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

用 OT 解決「髒路徑」問題

如上圖所示 OT 在操作同步的過程中增加一層操作轉換的邏輯，用於糾正併發操作產生的髒路徑。

左邊同步右邊操作時索引由 4 轉換爲 5。​

操作轉換邏輯分析：

對於左邊用戶：

因爲在協同操作「在 Index= 4 插入 Testhub」到達之前，已經執行了本地操作「在 Index=2 插入 Access」，而本地操作的索引 Index=2 小於協同操作的索引 Index=4，所以協同操作的索引路徑應當加上本地新增的節點長度，也就是 1，索引發生變化由 4 變成 5。

對於右邊用戶：

因爲協同操作的索引路徑小於本地操作的索引路徑，本地操作不對協同操作產生影響，所以不需要做任何的轉換，直接應用源操作即可。

用 OT 解決「併發衝突」問題

可以看到基於 OT 解決「併發衝突」同樣是使用操作轉換邏輯，只不過這次的操作轉換並不轉換髒路徑，而是協調衝突的屬性修改，上圖的處理結果是假定右邊操作後到達服務器的，最終結果收攏到居右顯示。

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

OT 解決 undos/redos 問題

前面已經說過 undos/redos 問題 本質就是 「髒路徑」+「併發衝突」問題，所以 OT 的處理方案就是當編輯器接收到協同操作時，需要對 Undo 棧、Redo 棧中的所有操作循環執行操作轉換邏輯，undo 或者 redo 時最終執行的是轉換後的操作，具體的邏輯不再意義贅述。

算法說明

可以看出 OT 是對編輯器的數據操作進行轉換，所以 OT 算法的實現依賴於編輯器數據模型的設計，不同的數據模型需要實現不同的操作轉換算法。

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

CRDT

CRDT (Conflict-free Replicated Data Type) 即 “無衝突複製數據類型”，它主要被應用在分佈式系統中，保證分佈式應用的數據一致性，文檔協同編輯可以理解爲分佈式應用的一種，它的本質是數據結構，通過數據結構的設計保證併發操作數據的最終一致性。

CRDT 於 2011 年正式被提出。 基於 CRDT 的協同編輯框架 Yjs 大概在 2015 年開源，Yjs 是專門爲在 web 上構建協同應用程序而設計的。

核心思想

大多數的 CRDT 爲在文檔中創建的每個字符分配一個唯一的標識符。

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

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

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

下圖描述了 Yjs 中處理衝突的算法模型，它是一個支持點對點傳輸的衝突處理模型。

上圖基礎說明

• 最下面的 “AB” 標識初始狀態
• 上面的每一根線代表一個插入操作
• 每一個操作都有一個唯一標識符
  比如 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）是併發操作。

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

E1,0

由於存在併發衝突，Yjs 執行與 OT 相同的衝突解決，並比較各自插入的用戶標識符。

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

ACDEB

以上就是 Yjs 處理併發衝突的算法介紹，其實也不難理解，首先它的插入操作是基於已有字符的相對位置，在 OT 中使用的相當於是基於索引的絕對位置，然後就是衝突的處理，主要是比較用戶標識符，標識符小的先應用，標識符大的後應用。

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

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

首先我們使用類似於 CRDT 的方式描述剛纔的數組：

可以看到右邊的列表使用唯一 Id 替換了原本數組的索引，然後描述內容修改的操作也相應的做一下調整

左邊操作：

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

右邊操作：

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

同步操作之後左邊和右邊最終的數據結構應該都是一樣的：

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

CRDT 解決併發衝突

這裏還是以圖片設置 align 屬性爲例介紹，首先看看 CRDT 如何描述對象屬性及屬性修改：

左邊是圖片數據模型，右邊是模擬 CRDT 對應的數據結構，圖片對象中的每一個字段都使用結構對象去描述內容及內容的修改，這裏以 align 字段的代表看它的表達

操作①：

最上面藍色部分表示 align 的初始值是 center ，（140, 20）是這個初始數據結構的標識，它也是基於某一個用戶的操作產生的。

這個時候一個用戶執行了操作①，把 align 屬性修改爲 left，產生了一個新的結構對象，就是圖中橙色部分的表示。操作完成後，Map 中的 align 字段指向了新產生的結構對象上，標識符是（141,0），因爲（141,0）這個結構對象是基於（140,20）的修改，所以它的 left 指向（140,20）這個結構對象。

這個示例會有一些歧義，就是鏈表的數據結構本身會有 left、right 兩個指針（在結構對象左右兩邊），然後中間部分其實是內容，但是我的內容存儲的是圖片的 align 屬性，它的值可能是 left、center、right，跟鏈表在 left、right 指針在一起可能產生混淆，這裏標記下，就是結構對象中的第二個塊描述的是屬性內容。

操作②：

這個時候另外一個用戶基於剛剛產生的結構對象（141,0）進行了操作②，把 align 屬性修改爲 right，產生了一個新的結構對象，就是圖中橙紅色部分的表示。

圖片下半部分是這兩個操作之後最終的數據結構，它是一個雙向鏈表的表達（這種表達已經很接近 Yjs 真實的數據結構了），它不僅可以描述最終的數據狀態（right），還可以表達出數據修改的順序：center -> left -> right。

這個示例其實描述的是順序操作，每一個操作基於的狀態都是最新狀態，兩個用戶執行的操作是有確定先後順序的。

下面看看兩個用戶併發的執行屬性修改時產生的數據結構：

與前面最大的不同就是執行操作 ② 和執行操作 ① 所基於的狀態是一致的，都是基於 align = 'center' 進行修改的，這種情況表達的就是併發數據的修改。接下來就是併發處理的邏輯了，跟前面介紹的一致，這個時候操作 ① 的對應的用戶標識 141 小於操作 ② 對應用戶標識 142，所以先應用操作 ①，後應用操作 ②，所以最終圖片的 align 屬性狀態是 right。

CRDT 解決 undso/redos 問題

CRDT 可以理解爲完全沒有「髒路徑」問題，然後併發衝突問題也完全可以基於 CRDT 的標識符（時間戳）去解決，那麼基於 CRDT 的方案中，實現 undos/redos 應該就比較簡單了，只需要根據 CRDT 的數據結構的新增或者刪除去實現 undos/redos 棧就可以有效解決問題。 假如進行了一個生成結構對象的操作，那麼撤回的時候可能就把它標記刪除。

假如進行一個刪除結構對象的操作，在執行撤回操作時可能就對應於重新執行結構對象的插入操作。

CRDT 算法說明

與 OT 不同，CRDT 是一種全新的解決方案，它不依賴於編輯器實現，對於任何的編輯器數據模型都可以使用一套 CRDT 數據結構去處理衝突，也是因爲數據結構的性質，它也可以不依賴中心化的服務器，而且穩定性非常高，這區別於 OT，OT 可以理解爲是通過算法控制保證數據一致性，CRDT 通過數據結構設計保證數據一致性，它在複雜的網絡環境中的處理是更穩健的，CRDT 的代價就是要保存更多的元數據，這會帶來一定內存消耗，但是這是可優化的，事實證明這個代價在協同編輯場景是完全可忽略不計的。

Yjs 優化

其實基於 CRDT 的協同編輯方案一直是被質疑的，而且質疑的聲音到現在都一直還在，Yjs 也受其影響。儘管基於 CRDT 實現的 Yjs 已經如此強大了，大家還總是拿 CRDT 的內存開銷、性能開銷說事，以我目前的瞭解：內存開銷、性能問題對於 Yjs 來說早已不是問題，所以這裏簡單介紹下 Yjs 的優化，這部分內容的整理基於官方對 Yjs 優化的介紹，性能問題和內存佔用問題每一個點都有大量的基準測試去驗證，這裏只對優化方式進行一些簡單的介紹。

一、結構表示優化

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

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

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

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

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

如果用戶將大量內容複製 / 粘貼到文檔中，則插入的內容由單個 Item 表示。此外，從左到右寫入的單字符插入可以合併爲單個 Item。重要的是，我們能夠在不丟失任何元數據的情況下拆分和合並項。

這就是 Yjs 對於數據表示的優化，通過這種方式可以有效減少 Yjs 數據結構中結構對象的數量，從而有效減少內存的佔用。

然而，這種方法最重要的缺點是處理單個字符變得更加複雜（也沒關係，因爲這是 Yjs 框架做的事情）。

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

二、刪除優化

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

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

（Paragraph）D

相當於將以下所有文本節點（字符）也標記爲刪除：

AD    BD    CD

這是我們可以完全從內存中刪除所有字符節點對應的結構，因爲字符節點是被刪除段落的子節點。

基於這種方式也可以有效減少 Yjs 的內存佔用。

三、操作定義

這塊其實是從 V8 的角度去優化 Yjs 結構對象的創建，整體思路就是讓 Yjs 創建對象的過程能夠被瀏覽器優化，無論是內存佔用還是對象創建速度。

四、查詢優化

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

五、編碼優化

Yjs 會對網絡中傳輸以及存儲在數據庫中結構對象進行統一的二進制編碼，當然也會提供相應的解碼操作，通過二進制編碼可以有效的提高數據的傳輸效率。

OT vs CRDT

| | 優勢 | 劣勢 | | --- | --- | --- | | OT | 1. 高性能
2. 保留原始的操作意圖 3. 容易理解 | 1. 需要中心化服務器
2. 需要 OT 控制算法 3. 不同數據模型 OT 算法需單獨實現 | | CRDT | 1. 去中心化
2. 天然支持離線編輯 3. 穩定性高 | 1. 損失操作意圖（比如 yjs 就不支持 split_node、move_node 操作的同步）
2. 損耗內存及性能 3. 基礎數據結構實現難度大 |

OT 和 CRDT 算法的部分就到這裏，下面介紹下基於 OT 和 CRDT 算法在實際開發中的工程落地方案。

開源解決方案

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

ShareDB 方案

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

ShareDB ShareDB 是基於 OT 實現協同編輯的一套解決方案，提供協同消息轉發、光標同步、數據持久化、OT 控制算法等等。

ShareDB 架構圖如下

下邊淺藍色部分是 ShareDB 包含的主要模塊，ShareDB 會提供基於 WebScoket 的消息服務實現以及對應的前端鏈接消息服務的 SDK，可以同步操作和光標，ShareDB 也包含數據持久化部分的實現。最左邊的 OTType 是核心的操作轉換的部分，因爲不同編輯器的數據模型需要實現單獨 OT 的算法，所以 ShareDB 本身不包含 OT 的實現，而是提供了標準的接入接口，任何數據類型只要基於這個接口實現了對應的操作轉換算法，那麼它就可以通過註冊的方式接入到 ShareDB 中，這個標準接口的定義可以參考 ottypes 中的實現。

上面紫色部分是目前 ShareDB 可以支持的編輯器，編輯器想要接入最終的任務就是基於編輯器的數據模型實現一個自己的 OTType 就可以，然後 Quill 編輯器的 Delta 數據模型本身就實現了操作轉換的邏輯，所以 Quill 是最容易接入的。

ottypes

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

ottype-slate

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

ottype-slate 當前只是初步實現了部分操作變換函數，然後結合 slate-angular 和 sharedb 搭建了一個協同編輯的測試 Demo，剩餘的部分操作變換函數後續慢慢補充。

ShareDB 方案流程圖

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

從這個流程可以看出操作轉換最終有可能是在服務端進行，也有可能在客戶端進行。因爲操作轉換的過程需要通過 OT 控制算法實現多客戶端的操作變換的協調，這個過程必須走一箇中心化的服務器，否則過程很難控制，所以基於 OT 算法這個方案是不能實現點對點通訊的。

Yjs 方案

Yjs 是基於 CRDT 的開源解決方案，它提供了比較完善的生態，在 2020 年的時候社區也出現了基於 Slate 編輯器的中間綁定層。

Yjs 架構圖

y-websocket - 提供協同編輯時的消息通訊，包含服務端實現和前端集成的 SDK

y-protocols - 定義消息通訊協議，包括消息服務初始化、內容更新、鑑權、感知系統等

y-redis - 持久化數據到 Redis

y-indexeddb - 持久化數據到 IndexedDB

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

Yjs 方案流程圖

從上到下描述一下用戶操作的同步過程，假如上面用戶在基於 Slate 編輯器進行一些數據的修改，它產生的 operations 需要先經 Yjs Bindings 把基於 Slate 的操作轉換爲 Yjs 的數據修改（使用 applySlate），更新本地 Yjs 的數據結構，當 Yjs 的數據結構被修改後它可以通過一種網絡傳輸協議把數據結構的變更同步給協作者，協作者直接應用這個遠程的數據同步到本地的 Yjs 數據結構上，然後 Yjs Bindings 中還有一個訂閱操作，就是訂閱遠程的 Yjs 數據修改，然後通過 applyYjs 方法把 Yjs 數據修改的表達轉化成 Slate 的 operations，最終 Slate 應用這個 operations 實現內容的同步，中間併發衝突的問題完全交給 Yjs 數據結構去處理，轉化到 Slate 的操作永遠跟 Yjs 的處理結果一致。

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

值得一提的是 Yjs 數據結構本身支持端端數據的直接同步，可以不借助中心化的服務器。

PingCode Wiki 協同方案選擇

2021 年了，技術應該變一變了，協同編輯方案不應該只有 OT，下面簡單談談我們做技術選型時的考量。

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

OT 方案

• TinyMCE 編輯器基於 Slate 模型 + OT 實現協同編輯，但是他們的不開源
• 大廠產品的協同編輯方案都是基於 OT 實現的
• 對於 OT 當時只是瞭解思路，不知道如何落地 ，準確的說都不知道協同編輯應該包含哪些基礎模塊

CRDT 方案

• 社區對於 CRDT 一直有一些質疑的聲音
• CRDT 缺少商業產品上的應用案例（文檔類）
• Yjs 生態比較完善 基於 Slate 編輯器有成熟的 Demo
• 翻譯了部分 Yjs 技術資料、對 Yjs 印象不錯
• 基於我們的編輯器搭建了 Yjs 的協同編輯 Demo，可以跑通

當時調研的 slate-yjs 提供的 Demo 截圖如下

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

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

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

功能上：

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

設計上：

• 模塊職責劃分清楚，尤其是抽取獨立的協議庫 y-protocols，讓複雜的消息同步變得非常的清晰可控
• 網絡協議 / 數據持久化 實現松耦合，網絡協議支持接入 y-websocket、y-webrtc，持久化 y-redis、社區有提供 y-mongodb
• 可以很快的與任意編輯器集成

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

談談技術的演進

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

2006 年 Google 把 OT 真正到帶到了商業產品中，這個過程經歷大概十多年，然後就是 2011 微軟緊接着基於 OT 實現了協同編輯，這中間也經歷了大概 5 年的時間，我覺得這個時間跨度一定跟當時的編輯器技術背景有關係，這個時期其實協同編輯技術也只是在這些頂尖科技公司得到發展和應用。

2011 年 CRDT 算法提出代表着一種新的協同編輯方案的出現。

2012 年 Quill 編輯器開源，它的數據模型 Delta 就是基於 OT 算法設計的，個人覺得 Quill 編輯器的開源對於協同編輯以及 OT 的發展是一個重要的里程碑，在以前協同編輯可能是少數大公司在研究的技術，Quill 編輯之後協同編輯就逐漸應用更多的中小公司產品中，比如國內的石墨文檔整個核心技術包括協同編輯可能就是基於 Quill 和 Delta 實現的。

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

2015 年 Yjs 開源代表着基於 CRDT 的協同方案正式得到發展。 2019 年 Slate 框架基於 TypeScript 完全重構，它的數據模型得到進一步優化，目前已經極其簡潔優雅，我覺得這也代表着一種變化。

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

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

這裏想延伸一點就是 OT 算法其實是在現有的編輯器數據模型的基礎上實現的協同編輯，它的思想也很好理解，其實反過來想，現在協同編輯所遇到的數據一致性的問題也有一部分原因是由於數據模型中「數據修改操作」的表達所引起的，比如數據修改操作中基於索引的方式去定位要修改的數據所產生的髒路徑問題，總之 OT 可以理解現有技術思路下的解決方案。然後 CRDT 其實是一種獨立於現有編輯器架構的解決方案，是一種技術上的創新，它爲實現協同編輯提供了一種新的思路，並且它有很多優秀的特性，比如支持點到點的數據同步，並且基於數據結構的衝突處理其實是更穩健的，雖然基於 CRDT 的數據結構在實現起來複雜度比較高，但是這個複雜度可以完全由框架層去完成，使用者其實對這塊可以是無感的。

收尾

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

開源項目地址：

https://github.com/quilljs/quill
https://github.com/ottypes
https://github.com/pubuzhixing8/ottype-slate
https://github.com/qqwee/slate-ottype
https://github.com/share/sharedb
https://github.com/yjs/yjs

參考文章

OT

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

協同編輯原理與實踐 - 沙洲

Yjs
Yjs——一個基於 CRDT 的數據協同框架
Yjs deep dive: How Yjs makes real-time collaboration easier and more efficient
https://blog.kevinjahns.de/are-crdts-suitable-for-shared-editing/

這個倉儲記錄了我們在做協同編輯時整理的一些資料 https://github.com/pubuzhixing8/awesome-collaboration

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://zhuanlan.zhihu.com/p/425265438