多人協(xié)同編輯技術(shù)的演進(jìn)
當(dāng)前位置：點晴教程→知識管理交流
→『 技術(shù)文檔交流 』
多人協(xié)同編輯一直是我們 PingCode Wiki 不太敢觸碰的一個功能，因為技術(shù)實現(xiàn)上有挑戰(zhàn)。但協(xié)同編輯技術(shù)本身已經(jīng)發(fā)展多年，解決方案已經(jīng)相對成熟，我們團(tuán)隊也是在剛剛結(jié)束的 Q3 里完成了基于 PingCode Wiki 編輯器協(xié)同編輯的方案落地，所以這里想結(jié)合我們的技術(shù)選型及落地實踐經(jīng)驗談?wù)勎覍@塊技術(shù)的理解。 主要內(nèi)容以協(xié)同編輯技術(shù)為主，中間也會談?wù)剬夹g(shù)發(fā)展演進(jìn)的理解。 一個場景一個常見的場景，頁面發(fā)布沖突，這個交互在我們產(chǎn)品中真實存在過
兩個用戶基于相同的文章內(nèi)容進(jìn)行了修改，一個用戶先發(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é)同編輯是如何運作的。 認(rèn)識協(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ù)，然后用一些列的操作表達(dá)富文本內(nèi)容，操作列表即最終的結(jié)果。 Slate 數(shù)據(jù)模型（JSON） 模型定義：
編輯器中有一個圖片類型的節(jié)點，對應(yīng)的數(shù)據(jù)結(jié)構(gòu)
屬性修改操作
我們可以看出雖然 Delta 和 Slate 數(shù)據(jù)的表現(xiàn)形式不同，但是他們都有一個共同點，就是針對數(shù)據(jù)的修改都可以由操作對象表達(dá)，這個操作對象可以在網(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ù)不一致。 究其原因就是左邊用戶先進(jìn)行的插入操作導(dǎo)致了它后面數(shù)據(jù)的索引發(fā)生變化，那么基于同步過來的操作直接應(yīng)用就會出現(xiàn)上圖的異常，我把這種情況稱為臟路徑問題。 問題二：并發(fā)沖突問題 這里以前面介紹的圖片數(shù)據(jù)結(jié)構(gòu)為例說明并發(fā)沖突的問題，下圖展示問題出現(xiàn)的過程，為了方便表達(dá)，圖片節(jié)點僅保留 type 和 align 兩個字段
最上面的數(shù)據(jù)結(jié)構(gòu)展示了兩個用戶開始時基于相同的狀態(tài)，圖片 align = ‘center’。 左邊用戶修改 align 屬性為 left、右邊用戶修改 align 屬性為 right，按照默認(rèn)處理他們把各自的操作通過消息服務(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)容怎么沒了 ！"，雖然邏輯上可以解釋，但它不符合用戶的使用習(xí)慣，所以對于協(xié)同編輯場景： 撤回應(yīng)當(dāng)只撤回自己的操作，協(xié)同者的操作應(yīng)當(dāng)被忽略。 右邊用戶撤回棧修復(fù)版： ① 刪除 Index=4 位置的節(jié)點 可以看到撤回棧只包含右邊的操作了，但是這又帶來了另外一個問題，大家仔細(xì)觀察可以發(fā)現(xiàn)現(xiàn)在 Index=4 對應(yīng)的節(jié)點是「Plan」，這個時候撤回會把「Plan」刪除掉，而右邊用戶在插入時插入的實際節(jié)點是「Testhub」，又出現(xiàn)了臟路徑。 除了這種「臟路徑」問題，「并發(fā)沖突」問題也會以類似的方式出現(xiàn)在，具體的邏輯就不再詳細(xì)分析了。 撤回棧忽略協(xié)同者操作后，撤回棧中的操作路徑會出現(xiàn)「臟路徑」問題 +「并發(fā)沖突」問題。 問題四：工程落地問題 這個問題比較好理解，就是協(xié)同編輯具體的落地問題：
簡單歸納下上面所提到問題，其實可以分為兩類： 第一類：主要包含臟路徑、并發(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)細(xì)節(jié)，只是提供它處理沖突的思路，以及從問題的本身出發(fā)去看待它處理問題的一個思路，至于具體的算法實現(xiàn)大家有興趣可以去Github查找相關(guān)的資料去自己實踐。 OTOT 全稱是 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ā)操作進(jìn)行轉(zhuǎn)換，通過轉(zhuǎn)換對其中產(chǎn)生的 并發(fā)沖突 和 臟路徑 進(jìn)行修正，然后把修正后的操作重新應(yīng)用到文檔中，保證操作的正確性和最終數(shù)據(jù)一致性。 原理圖 可以用 diamon 圖表示 OT 的核心原理
左圖解釋：
左圖狀態(tài)： 兩邊用戶分別應(yīng)用操作 a 和 b 后 ，這時兩邊的文檔內(nèi)容都發(fā)生變化，且不一致； 操作轉(zhuǎn)換： 為了左右兩邊的文檔達(dá)到一致的狀態(tài)，我們需要對 a 和 b 進(jìn)行操作轉(zhuǎn)換 transfrom(a, b) => (a', b') 得到兩個衍生的操作作 a' 和 b' 。 右圖應(yīng)用操作轉(zhuǎn)換的結(jié)果： 左邊 a 操作的衍生操作 a' 在右邊應(yīng)用，b' 在左邊應(yīng)用，最終文檔內(nèi)容達(dá)到一致。 這里說明的只是最基礎(chǔ)的 OT 模型，每個客戶端只有一個操作的情況（1 : 1），還有每個客戶端對應(yīng)多個操作的情況（M : N），還有 OT 控制算法等等。并且在真正實現(xiàn) OT 時有可能每一次操作轉(zhuǎn)換只得到一個衍生操作（ottypes 定義的操作變換就是這樣），跟前面的 transforms 有些不一樣，但這些不是特別重要，具體實現(xiàn)的時候在仔細(xì)理解，這里描述的只是 OT 算法的最基礎(chǔ)思路。 用 OT 解決「臟路徑」問題
如上圖所示 OT 在操作同步的過程中增加一層操作轉(zhuǎn)換的邏輯，用于糾正并發(fā)操作產(chǎn)生的臟路徑。 左邊同步右邊操作時索引由 4 轉(zhuǎn)換為 5。 操作轉(zhuǎn)換邏輯分析： 對于左邊用戶： 因為在協(xié)同操作「在 Index= 4 插入 Testhub」到達(dá)之前，已經(jīng)執(zhí)行了本地操作「在 Index=2 插入 Access」，而本地操作的索引 Index=2 小于協(xié)同操作的索引 Index=4，所以協(xié)同操作的索引路徑應(yīng)當(dā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é)果是假定右邊操作后到達(dá)服務(wù)器的，最終結(jié)果收攏到居右顯示。
OT 解決 undos/redos 問題 前面已經(jīng)說過 undos/redos 問題 本質(zhì)就是 「臟路徑」+「并發(fā)沖突」問題，所以 OT 的處理方案就是當(dāng)編輯器接收到協(xié)同操作時，需要對 Undo棧、Redo棧中的所有操作循環(huán)執(zhí)行操作轉(zhuǎn)換邏輯，undo 或者 redo 時最終執(zhí)行的是轉(zhuǎn)換后的操作，具體的邏輯不再意義贅述。 算法說明 可以看出 OT 是對編輯器的數(shù)據(jù)操作進(jìn)行轉(zhuǎn)換，所以 OT 算法的實現(xiàn)依賴于編輯器數(shù)據(jù)模型的設(shè)計，不同的數(shù)據(jù)模型需要實現(xiàn)不同的操作轉(zhuǎn)換算法。 OT 算法大概就說到這里，下面看看 CRDT 是如何處理數(shù)據(jù)一致性問題的。 CRDTCRDT (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)建的每個字符分配一個唯一的標(biāo)識符。 為了確保文檔始終能夠收斂，CRDT 模型即使在刪除字符時也會保留元數(shù)據(jù)。 CRDT 最初是為了解決分布式系統(tǒng)最終數(shù)據(jù)一致性而提出的，它支持各個主機(jī)副本之間數(shù)據(jù)修改的直接同步，而且數(shù)據(jù)修改的同步順序以及同步的次數(shù)不影響最終結(jié)果，只要修改操作一致，數(shù)據(jù)的最終狀態(tài)就是一致的，也就是通常大家說的 CRDT 數(shù)據(jù)的滿足交換性和冪等性。 簡單介紹 CRDT 是如何處理沖突的 下圖描述了 Yjs 中處理沖突的算法模型，它是一個支持點對點傳輸?shù)臎_突處理模型。 上圖基礎(chǔ)說明
例如，以下標(biāo)識符表示 user 0 插入 “C” 在 “A” 和 “B” 之間 相同的用戶 user 0 插入 “D” 在 “B” 和 “C” 之間，可以使用下面的操作 這時候另外一個用戶期望插入 “E” 在 ”A“ 和 ”B“ 之間，但是這個操作是與前面插入 ”C“ 的操作（C0, 0）是并發(fā)操作。 此時用戶的唯一標(biāo)識應(yīng)該與前面的不同，但是 clock 應(yīng)該是與前面的插入操作類似： 由于存在并發(fā)沖突，Yjs 執(zhí)行與 OT 相同的沖突解決，并比較各自插入的用戶標(biāo)識符。 由于用戶標(biāo)識符 1 大于 0，因此生成的文檔為： 以上就是 Yjs 處理并發(fā)沖突的算法介紹，其實也不難理解，首先它的插入操作是基于已有字符的相對位置，在 OT 中使用的相當(dāng)于是基于索引的絕對位置，然后就是沖突的處理，主要是比較用戶標(biāo)識符，標(biāo)識符小的先應(yīng)用，標(biāo)識符大的后應(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 解決并發(fā)沖突 這里還是以圖片設(shè)置 align 屬性為例介紹，首先看看CRDT如何描述對象屬性及屬性修改：
左邊是圖片數(shù)據(jù)模型，右邊是模擬 CRDT 對應(yīng)的數(shù)據(jù)結(jié)構(gòu)，圖片對象中的每一個字段都使用結(jié)構(gòu)對象去描述內(nèi)容及內(nèi)容的修改，這里以 align 字段的代表看它的表達(dá) 操作 ①：
最上面藍(lán)色部分表示 align 的初始值是 center ，（140, 20）是這個初始數(shù)據(jù)結(jié)構(gòu)的標(biāo)識，它也是基于某一個用戶的操作產(chǎn)生的。 這個時候一個用戶執(zhí)行了操作 ①，把 align 屬性修改為 left，產(chǎn)生了一個新的結(jié)構(gòu)對象，就是圖中橙色部分的表示。操作完成后，Map 中的 align 字段指向了新產(chǎn)生的結(jié)構(gòu)對象上，標(biāo)識符是（141,0），因為（141,0）這個結(jié)構(gòu)對象是基于（140,20）的修改，所以它的 left 指向（140,20）這個結(jié)構(gòu)對象。
操作②：
這個時候另外一個用戶基于剛剛產(chǎn)生的結(jié)構(gòu)對象（141,0）進(jìn)行了操作 ②，把 align 屬性修改為right，產(chǎn)生了一個新的結(jié)構(gòu)對象，就是圖中橙紅色部分的表示。 圖片下半部分是這兩個操作之后最終的數(shù)據(jù)結(jié)構(gòu)，它是一個雙向鏈表的表達(dá)（這種表達(dá)已經(jīng)很接近 Yjs 真實的數(shù)據(jù)結(jié)構(gòu)了），它不僅可以描述最終的數(shù)據(jù)狀態(tài)（right），還可以表達(dá)出數(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' 進(jìn)行修改的，這種情況表達(dá)的就是并發(fā)數(shù)據(jù)的修改。接下來就是并發(fā)處理的邏輯了，跟前面介紹的一致，這個時候操作 ① 的對應(yīng)的用戶標(biāo)識 141 小于操作 ② 對應(yīng)用戶標(biāo)識 142，所以先應(yīng)用操作 ①，后應(yīng)用操作 ②，所以最終圖片的 align 屬性狀態(tài)是 right。 CRDT 解決 undso/redos問題 CRDT 可以理解為完全沒有「臟路徑」問題，然后并發(fā)沖突問題也完全可以基于 CRDT 的標(biāo)識符（時間戳）去解決，那么基于 CRDT 的方案中，實現(xiàn) undos/redos 應(yīng)該就比較簡單了，只需要根據(jù) CRDT 的數(shù)據(jù)結(jié)構(gòu)的新增或者刪除去實現(xiàn) undos/redos 棧就可以有效解決問題。 假如進(jìn)行了一個生成結(jié)構(gòu)對象的操作，那么撤回的時候可能就把它標(biāo)記刪除。 假如進(jìn)行一個刪除結(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)如此強(qiáng)大了，大家還總是拿 CRDT 的內(nèi)存開銷、性能開銷說事，以我目前的了解：內(nèi)存開銷、性能問題對于 Yjs 來說早已不是問題，所以這里簡單介紹下 Yjs 的優(yōu)化，這部分內(nèi)容的整理基于官方對 Yjs 優(yōu)化的介紹，性能問題和內(nèi)存占用問題每一個點都有大量的基準(zhǔn)測試去驗證，這里只對優(yōu)化方式進(jìn)行一些簡單的介紹。 一、結(jié)構(gòu)表示優(yōu)化 當(dāng)用戶從左到右鍵入內(nèi)容“ABC”時，它將執(zhí)行以下操作： insert(0, "A") ? insert(1, "B") ? insert(2, "C")。 對文本內(nèi)容建模的 YATA CRDT 的鏈表將如下所示：
插入內(nèi)容“ABC”的CRDT模型（假設(shè)用戶具有唯一的客戶端標(biāo)識符“1”） 所有的 CRDT 都會為每個字符分配某種唯一的 ID 和附加的元數(shù)據(jù)，這對于大型文檔來說非常消耗內(nèi)存。我們不能刪除元數(shù)據(jù)，因為它是解決沖突的必要條件。 Yjs 也唯一地標(biāo)識每個字符和分配元數(shù)據(jù)，有效地表示了這些信息。較大的文檔插入表示為單個 Item 對象，使用字符偏移量唯一地單獨標(biāo)識每個字符。 然后這塊是有優(yōu)化空間，下面的 Item 也可以將字符“A”唯一標(biāo)識為 {client:1,clock:0}，字符“B”為 {client:1,clock:1}，依此類推...... 如果用戶將大量內(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 框架做的事情）。 當(dāng)另一個用戶希望在“B”和“C”之間插入一個字符時，需要將操作的“BC”部分拆分為兩個單獨的操作。 我們不能重新組合這些操作，因為在 CRDT 中我們永遠(yuǎn)不能刪除字符或從文檔樹中刪除它們。 二、刪除優(yōu)化 我們可以指示需要刪除字符的唯一方法是將其標(biāo)記為已刪除。雖然如此，這塊還是有優(yōu)化空間，以 Slate 的段落結(jié)構(gòu)為例，當(dāng)你將段落標(biāo)記為刪除時，你也可以將段落下的所有文本結(jié)構(gòu)標(biāo)記為刪除。 比如，一個段落包含文本 ”ABC“，當(dāng)標(biāo)記段落刪除時： （Paragraph）D 相當(dāng)于將以下所有文本節(jié)點（字符）也標(biāo)記為刪除： 這是我們可以完全從內(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)對象，當(dāng) Yjs 結(jié)構(gòu)對象數(shù)據(jù)非常巨大時，執(zhí)行的每一個操作有可能會因此損耗一定的時間，Yjs 對此也是有優(yōu)化措施的，目前我從源代碼中看到的是，Yjs 會對用戶經(jīng)常操作的結(jié)構(gòu)對象進(jìn)行緩存（其實就是緩存位置），查找過程中優(yōu)先重緩存中去匹配，通過如果緩存命中則可以有效提高數(shù)據(jù)的查詢速度。 五、編碼優(yōu)化 Yjs 會對網(wǎng)絡(luò)中傳輸以及存儲在數(shù)據(jù)庫中結(jié)構(gòu)對象進(jìn)行統(tǒng)一的二進(jìn)制編碼，當(dāng)然也會提供相應(yīng)的解碼操作，通過二進(jìn)制編碼可以有效的提高數(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 比較舊的版本，也不怎么維護(hù)了，但是它的實現(xiàn)給了我一些思路，加上原本的理解就有了現(xiàn)在的方案：slate + ottype-slate + sharedb。 ShareDB ShareDB 是基于 OT 實現(xiàn)協(xié)同編輯的一套解決方案，提供協(xié)同消息轉(zhuǎn)發(fā)、光標(biāo)同步、數(shù)據(jù)持久化、OT 控制算法等等。 ShareDB 架構(gòu)圖如下
下邊淺藍(lán)色部分是 ShareDB 包含的主要模塊，ShareDB 會提供基于 WebScoket 的消息服務(wù)實現(xiàn)以及對應(yīng)的前端鏈接消息服務(wù)的SDK，可以同步操作和光標(biāo)，ShareDB 也包含數(shù)據(jù)持久化部分的實現(xiàn)。 最左邊的 OTType 是核心的操作轉(zhuǎn)換的部分，因為不同編輯器的數(shù)據(jù)模型需要實現(xiàn)單獨 OT 的算法，所以 ShareDB 本身不包含 OT 的實現(xiàn)，而是提供了標(biāo)準(zhǔn)的接入接口，任何數(shù)據(jù)類型只要基于這個接口實現(xiàn)了對應(yīng)的操作轉(zhuǎn)換算法，那么它就可以通過注冊的方式接入到 ShareDB 中，這個標(biāo)準(zhǔn)接口的定義可以參考 ottypes 中的實現(xiàn)。 上面紫色部分是目前 ShareDB 可以支持的編輯器，編輯器想要接入最終的任務(wù)就是基于編輯器的數(shù)據(jù)模型實現(xiàn)一個自己的 OTType 就可以，然后 Quill 編輯器的 Delta 數(shù)據(jù)模型本身就實現(xiàn)了操作轉(zhuǎn)換的邏輯，所以 Quill 是最容易接入的。 ottypes 前面有提到的 ottypes 其實是定了一種標(biāo)準(zhǔn)的 OT 的接口，根據(jù)這種標(biāo)準(zhǔn)實現(xiàn)的的類型轉(zhuǎn)換可以都可以完美的與 ShareDB 配合使用，共同完成數(shù)據(jù)的協(xié)同編輯，前面方案中提到的 ottype-slate 其實就是 ottypes 的一種實現(xiàn)。 ottype-slate 個人感覺 slate 中定義的數(shù)據(jù)模型以及數(shù)據(jù)變換可讀性非常高，它的表達(dá)方式以及提供的工具函數(shù)式非常清晰且完善，并且每種原子操作都是可逆的，我大概看了 sharedb 默認(rèn)支持的基于 JSON 的操作變換實現(xiàn)(ot-json0)，ot-json 針對數(shù)據(jù)修改的表達(dá)，可讀性還是非常差的，所以我感覺可以自己寫一個針對 slate 數(shù)據(jù)模型的 OTType 實現(xiàn)，所以就有了ottype-slate。
ShareDB 方案流程圖
從上面開始看，假如用戶在基于 Slate 編輯器進(jìn)行協(xié)同編輯，可以看到用戶內(nèi)容修改產(chǎn)生的 operations 在傳遞給 ShareDB Serve 之前可能會經(jīng)過操作轉(zhuǎn)換，這取決于操作所基于的文檔版本和服務(wù)器的文檔版本是否一致，不一致就需要計算出兩個版本差異的部分操作，拿差異的操作與新產(chǎn)生的操作進(jìn)行操作轉(zhuǎn)換，基于操作轉(zhuǎn)換的結(jié)果去同步內(nèi)容的修改，這個過程之后就是把最終的操作通過消息服務(wù)轉(zhuǎn)發(fā)給其它客戶端，其它客戶端在應(yīng)用這個操作，實現(xiàn)協(xié)同編輯。 從這個流程可以看出操作轉(zhuǎn)換最終有可能是在服務(wù)端進(jìn)行，也有可能在客戶端進(jìn)行。因為操作轉(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 編輯器進(jìn)行一些數(shù)據(jù)的修改，它產(chǎn)生的 operations 需要先經(jīng) Yjs Bindings 把基于 Slate 的操作轉(zhuǎn)換為 Yjs 的數(shù)據(jù)修改（使用applySlate），更新本地 Yjs 的數(shù)據(jù)結(jié)構(gòu)，當(dāng) Yjs 的數(shù)據(jù)結(jié)構(gòu)被修改后它可以通過一種網(wǎng)絡(luò)傳輸協(xié)議把數(shù)據(jù)結(jié)構(gòu)的變更同步給協(xié)作者，協(xié)作者直接應(yīng)用這個遠(yuǎn)程的數(shù)據(jù)同步到本地的 Yjs 數(shù)據(jù)結(jié)構(gòu)上，然后 Yjs Bindings 中還有一個訂閱操作，就是訂閱遠(yuǎn)程的 Yjs 數(shù)據(jù)修改，然后通過 applyYjs 方法把 Yjs 數(shù)據(jù)修改的表達(dá)轉(zhuǎn)化成 Slate 的 operations，最終 Slate 應(yīng)用這個 operations 實現(xiàn)內(nèi)容的同步，中間并發(fā)沖突的問題完全交給 Yjs 數(shù)據(jù)結(jié)構(gòu)去處理，轉(zhuǎn)化到 Slate 的操作永遠(yuǎn)跟 Yjs 的處理結(jié)果一致。 從流程圖可以看出每一個客戶端都維護(hù)了一個 Yjs 數(shù)據(jù)結(jié)構(gòu)的副本，這個數(shù)據(jù)結(jié)構(gòu)副本所表達(dá)的內(nèi)容與Slate編輯器數(shù)據(jù)所表達(dá)的內(nèi)容完全一樣，只是它們承擔(dān)職責(zé)不同，Slate 數(shù)據(jù)供編輯器及其插件渲染使用，然后 Yjs 數(shù)據(jù)結(jié)構(gòu)用于處理沖突、保證數(shù)據(jù)一致性，數(shù)據(jù)的修改最終是通過 Yjs 的數(shù)據(jù)結(jié)構(gòu)來進(jìn)行同步的。 值得一提的是 Yjs 數(shù)據(jù)結(jié)構(gòu)本身支持端端數(shù)據(jù)的直接同步，可以不借助中心化的服務(wù)器。 PingCode Wiki 協(xié)同方案選擇2021年了，技術(shù)應(yīng)該變一變了，協(xié)同編輯方案不應(yīng)該只有OT，下面簡單談?wù)勎覀冏黾夹g(shù)選型時的考量。 今年 Q3 我們團(tuán)隊正式開始做協(xié)同編輯，我們的編輯器是基于Slate框架實現(xiàn)的，雖然在這之前我對協(xié)同編輯有一些調(diào)研，但都不成體系，所以在 Q3 開始的時候我們又重新進(jìn)行了一次調(diào)研，核心問題還是選 OT 還是 CRDT，下面是我們當(dāng)時掌握的一些情況： OT 方案
CRDT 方案
當(dāng)時調(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é)同編輯的一些細(xì)節(jié)問題，包括消息服務(wù)連接的控制、undos/redos 的問題、彈框處理等等，總之就是沒有太大的問題，而且性能上基本沒有損耗，大文檔的加載（大概5-6萬字的內(nèi)容） Yjs 基本可以在毫秒級去處理完成。 現(xiàn)在重新來看Yjs方案的選擇，我覺得我們這套方案的選擇非常正確，在這個過程中沒有浪費一點團(tuán)隊的時間，而且在Q3實現(xiàn)協(xié)同編輯的過程中，大家都很輕松，而且在 Yjs 上我們還可以學(xué)到很多東西，下面是我總結(jié)的 Yjs 在功能以及設(shè)計上的一些優(yōu)勢： 功能上：
設(shè)計上：
可以這么說現(xiàn)在 Yjs 對于我們的意義，就之于兩年前 Slate 對我們的意義，是我們這個階段了解和學(xué)習(xí)協(xié)同編輯的重要支柱，實現(xiàn)協(xié)同編輯到底包含哪些東西、都有什么問題、Yjs 是怎么解決的、Yjs 有什么缺點、它是如何優(yōu)化的等等，就像一個老師幫助你完成你的工作，然后讓你在這個過程中有所進(jìn)步。 談?wù)劶夹g(shù)的演進(jìn)
1989 年 OT 算法正式提出，代表著協(xié)同編輯技術(shù)的開始，但是當(dāng)時編輯器的架構(gòu)設(shè)計遠(yuǎn)不能達(dá)到現(xiàn)在的水平，它的理念在那個時期一定是非常超前的，現(xiàn)在協(xié)同編輯數(shù)據(jù)模型的演變我覺得一定程度上也有受 OT 算法的影響。 2006 年 Google 把 OT 真正到帶到了商業(yè)產(chǎn)品中，這個過程經(jīng)歷大概十多年，然后就是 2011 微軟緊接著基于 OT 實現(xiàn)了協(xié)同編輯，這中間也經(jīng)歷了大概5年的時間，我覺得這個時間跨度一定跟當(dāng)時的編輯器技術(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ù)模型得到進(jìn)一步優(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ù)修改操作」的表達(dá)所引起的，比如數(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」而準(zhǔn)備的主題內(nèi)容，然后我本身其實也想對協(xié)同編輯這塊的內(nèi)容做一個整理，趁這個機(jī)會就一起做了，主要是闡述了我對這塊技術(shù)的一個認(rèn)識，包括協(xié)同編輯是什么，協(xié)同編輯所遇到的一些問題或者說挑戰(zhàn)，然后主流協(xié)同編輯沖突處理算法是怎么工作的，再到后面的基于沖突處理算法的開源解決方案等等，這里面提到的大部分技術(shù)其實都是開源的，內(nèi)心其實是非常佩服這些開源作品的貢獻(xiàn)者的，也在督促自己努力的去做更多的開源輸出。 開源項目地址： github.com/quilljs/qui… 參考文章 OT SharedPen 之 Operational Transformation Yjs 這個倉儲記錄了我們在做協(xié)同編輯時整理的一些資料 轉(zhuǎn)自https://juejin.cn/post/7030327005665034247 該文章在 2025/4/14 10:04:19 編輯過 |
關(guān)鍵字查詢
相關(guān)文章
正在查詢... 
|
400 186 1886
