精品熟人妻一区二区三区四区不卡-精品爽黄69天堂a-精品水蜜桃久久久久久久-精品丝袜国产自在线拍-精品丝袜国产自在线拍a-精品丝袜国产自在线拍免费看

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

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

一個(gè)場(chǎng)景

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

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

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

1. 悲觀鎖 - 一個(gè)文檔只能同時(shí)有一個(gè)用戶在編輯

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

3. 協(xié)同編輯

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

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

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

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

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

認(rèn)識(shí)協(xié)同編輯

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

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

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

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

2012 年 Quill -> Delta

2016 年 Slate -> JSON

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

Quill 編輯器顯示一段文字

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

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

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

模型定義：

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

屬性修改操作

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

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

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

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

問題一：臟路徑問題

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

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

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

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

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

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

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

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

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

問題三：undos/redos 問題

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

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

右邊用戶的操作列表：

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

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

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

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

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

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

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

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

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

問題四：工程落地問題

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

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

簡(jiǎn)單歸納下上面所提到問題，其實(shí)可以分為兩類：

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

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

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

下面我們簡(jiǎn)單介紹下這兩種算法。

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

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

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

核心思想

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

原理圖

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

左圖解釋：

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

左圖狀態(tài)：

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

操作轉(zhuǎn)換：

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

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

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

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

用 OT 解決「臟路徑」問題

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

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

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

對(duì)于左邊用戶：

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

對(duì)于右邊用戶：

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

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

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

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

OT 解決 undos/redos 問題

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

算法說明

可以看出 OT 是對(duì)編輯器的數(shù)據(jù)操作進(jìn)行轉(zhuǎn)換，所以 OT 算法的實(shí)現(xiàn)依賴于編輯器數(shù)據(jù)模型的設(shè)計(jì)，不同的數(shù)據(jù)模型需要實(shí)現(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è)計(jì)保證并發(fā)操作數(shù)據(jù)的最終一致性。

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

核心思想

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

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

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

簡(jiǎn)單介紹 CRDT 是如何處理沖突的

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

                                  

上圖基礎(chǔ)說明

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

例如，以下標(biāo)識(shí)符表示 user 0 插入 “C” 在 “A” 和 “B” 之間

C0,0

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

D0,1

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

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

E1,0

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

由于用戶標(biāo)識(shí)符 1 大于 0，因此生成的文檔為：

ACDEB

以上就是 Yjs 處理并發(fā)沖突的算法介紹，其實(shí)也不難理解，首先它的插入操作是基于已有字符的相對(duì)位置，在 OT 中使用的相當(dāng)于是基于索引的絕對(duì)位置，然后就是沖突的處理，主要是比較用戶標(biāo)識(shí)符，標(biāo)識(shí)符小的先應(yīng)用，標(biāo)識(shí)符大的后應(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)該都是一樣的：

                           

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

CRDT 解決并發(fā)沖突

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

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

操作 ①：

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

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

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

操作②：

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

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

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

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

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

CRDT 解決 undso/redos問題

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

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

CRDT 算法說明

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

Yjs 優(yōu)化

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

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

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

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

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

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

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

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

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

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

當(dāng)另一個(gè)用戶希望在“B”和“C”之間插入一個(gè)字符時(shí)，需要將操作的“BC”部分拆分為兩個(gè)單獨(dú)的操作。 我們不能重新組合這些操作，因?yàn)樵?CRDT 中我們永遠(yuǎn)不能刪除字符或從文檔樹中刪除它們。

二、刪除優(yōu)化

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

比如，一個(gè)段落包含文本 ”ABC“，當(dāng)標(biāo)記段落刪除時(shí)：

（Paragraph）D

相當(dāng)于將以下所有文本節(jié)點(diǎn)（字符）也標(biāo)記為刪除：

AD    BD    CD

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

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

三、操作定義

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

四、查詢優(yōu)化

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

五、編碼優(yōu)化

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

OT vs CRDT

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

開源解決方案

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

ShareDB 方案

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

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

ShareDB 架構(gòu)圖如下

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

最左邊的 OTType 是核心的操作轉(zhuǎn)換的部分，因?yàn)椴煌庉嬈鞯臄?shù)據(jù)模型需要實(shí)現(xiàn)單獨(dú) OT 的算法，所以 ShareDB 本身不包含 OT 的實(shí)現(xiàn)，而是提供了標(biāo)準(zhǔn)的接入接口，任何數(shù)據(jù)類型只要基于這個(gè)接口實(shí)現(xiàn)了對(duì)應(yīng)的操作轉(zhuǎn)換算法，那么它就可以通過注冊(cè)的方式接入到 ShareDB 中，這個(gè)標(biāo)準(zhǔn)接口的定義可以參考 ottypes 中的實(shí)現(xiàn)。

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

ottypes

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

ottype-slate

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

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

ShareDB 方案流程圖

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

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

Yjs 方案

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

Yjs 架構(gòu)圖

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

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

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

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

在上層 Yjs 支持任何大部分主流編輯器的接入，因?yàn)?Yjs 也可以理解為一套獨(dú)立的數(shù)據(jù)模型，它與每種編輯器本身的數(shù)據(jù)模型是不同的，所以每種編輯器想要接入 Yjs 都必須實(shí)現(xiàn)一個(gè)中間綁定層，用于編輯器數(shù)據(jù)模型與 Yjs 數(shù)據(jù)模型轉(zhuǎn)換，這個(gè)轉(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)用這個(gè)遠(yuǎn)程的數(shù)據(jù)同步到本地的 Yjs 數(shù)據(jù)結(jié)構(gòu)上，然后 Yjs Bindings 中還有一個(gè)訂閱操作，就是訂閱遠(yuǎn)程的 Yjs 數(shù)據(jù)修改，然后通過 applyYjs 方法把 Yjs 數(shù)據(jù)修改的表達(dá)轉(zhuǎn)化成 Slate 的 operations，最終 Slate 應(yīng)用這個(gè) operations 實(shí)現(xiàn)內(nèi)容的同步，中間并發(fā)沖突的問題完全交給 Yjs 數(shù)據(jù)結(jié)構(gòu)去處理，轉(zhuǎn)化到 Slate 的操作永遠(yuǎn)跟 Yjs 的處理結(jié)果一致。

從流程圖可以看出每一個(gè)客戶端都維護(hù)了一個(gè) Yjs 數(shù)據(jù)結(jié)構(gòu)的副本，這個(gè)數(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，下面簡(jiǎn)單談?wù)勎覀冏黾夹g(shù)選型時(shí)的考量。

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

OT 方案

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

CRDT 方案

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

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

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

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

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

功能上：

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

設(shè)計(jì)上：

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

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

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

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

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

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

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

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

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

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

2021 年我覺得我們?cè)谶@個(gè)時(shí)間選擇 Yjs 也很合理，不同的時(shí)期技術(shù)的選擇一定是不同的。

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

收尾

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

開源項(xiàng)目地址：

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é)同編輯原理與實(shí)踐 - 沙洲

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

這個(gè)倉儲(chǔ)記錄了我們?cè)谧鰠f(xié)同編輯時(shí)整理的一些資料

github.com/pubuzhixing…?

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