淺談在線文檔的那些事兒

前言

對前端來說開發一個在線文檔需要啥技術呢？想一下，開發一個在線文檔我們可能要解決的問題：

• 最基礎的文本編輯功能 (哦？好像 textarea 就可以完成，那如果是富文本呢？) 我們需要一個文檔模型來描述文檔；

• 富文本編輯器，提供富文本的編輯和渲染能力；

• 協同功能，不同的用戶對同一份文檔的編輯需要保持大家看到的都是一樣的；

• 協同網絡模型，保證服務器和客戶端之間的文檔模型一致；

名詞解釋

OT：一種解決協同問題的算法；

OP：operation 的簡稱，在 OT 中指的是一次操作；

etherpad: 一個實現文檔協同功能的開源庫；

easysync: etherpad 中實現文檔協同的核心算法，是 OT 算法的一種，主要用來處理文本協同；

ot-json：ot 算法的一種，顧名思義，是主要用來處理結構化數據；

Changeset: 一種描述文檔更改的數據格式，用來表示整個文檔的一次修改；

ClientVars ： 表示一篇文檔的初始化數據，一般由連續的 changeset 組合而成；

符號解釋

| ：移動光標；

·：疊加；

正文

OT 算法

什麼是 OT 算法呢？我們先從頭說起，如果要實現一個多人共同編輯文檔的功能，我們最簡單暴力的做法是啥？

編輯鎖

顧名思義，假如 A 在編輯文檔，服務端直接將這個文檔加鎖，B 如果在這個時候也加入了編輯，由於鎖的存在，B 的編輯直接被丟棄。可以看出，這種編輯鎖的實現方式非常粗暴，體驗極其糟糕，當然了，在很多公司 (比如我們的某死對頭公司) 的一些 wiki 系統就是用這種實現方式，由於這種實現方式比較簡單，而且體驗很糟糕(內容丟失 & 無法實時)，我們這裏就不做討論了。

Linux 中的 diff-patch

Linux 中有兩個命令：diff 和 patch；如果我們能在 JS 中實現這套算法，那麼多人協同編輯可以這樣做：

1. 用戶打開文檔後和服務端建立長鏈接，保存文檔副本；

2. 用戶編輯的時候如果有停頓 (比如 3s)，則將現有的文檔和副本進行 diff 對比，將結果傳給服務端，更新副本；

3. 服務端更新文檔，將 diff 結果通過長鏈接通知到其它用戶，其它用戶使用 patch 方法更新本地的文檔；

我們來測試下：

# 本地文檔
$ echo '復仇者聯盟
鋼鐵俠
美國隊長' > test-local.txt
# 生成用戶A編輯後的文檔
$ echo '復仇者聯盟
鋼鐵俠
綠巨人' > test-userA.txt
# diff兩個文檔
$ diff test-local.txt test-userA.txt > diff-test.patch
# 查看diff-test.patch內容
$ cat diff-test.patch
3c3
< 美國隊長
---
> 綠巨人

從 diff-test.patch 內容可以看出，已經找出了兩個文檔不同的地方，然後我們再模擬下用戶 B 的行爲：

# 生成用戶B編輯的文檔
$ echo '復仇者聯盟
黑寡婦
美國隊長' > test-userB.txt
# patch方法更新文檔
$ patch test-userB.txt < diff-test.patch
# 查看test-userB.txt內容
$ cat test-userB.txt
復仇者聯盟
黑寡婦
綠巨人

可以看到，用戶 B 文檔的第三行已經更新爲了用戶 A 修改後的 “綠巨人”。

1. 但這種實現方式有個問題，因爲他是基於行來進行對比的，就會導致很容易出現衝突，比如：

# 生成文件1
$ echo '復仇者聯盟' > local.txt
# 生成文件2
$ echo '復仇者聯盟鋼鐵俠' > userA.txt
# diff對比
$ diff local.txt userA.txt > diff.patch

查看 diff.patch 內容：

1c1
< 復仇者聯盟
---
> 復仇者聯盟鋼鐵俠

這就意味着如果兩個人同時修改同一行，那必然就會產生衝突，我們測試下:

# 生成文件3
$ echo '復仇者聯盟美國隊長' > userB.txt
# patch
$ patch userB.txt < diff.patch

以上我們發現，假如原始文檔是 “復仇者聯盟”，用戶 A 修改爲 “復仇者聯盟鋼鐵俠”，將 diff 結果傳給服務端，服務端傳給用戶 B，而用戶 B 只是將文檔改爲了 “復仇者聯盟美國隊長”，直覺上我們可以看出，這兩處是不衝突的，完全可以合併成 “復仇者聯盟鋼鐵俠美國隊長”，但實際上的 patch 結果卻是這樣的：

$ cat userB.txt.rej
***************
*** 1
- 復仇者聯盟
--- 1 -----
+ 復仇者聯盟鋼鐵俠

因此這種基於行的算法還是比較粗糙，體驗上比編輯鎖雖然好了一點，但實際弊端還是比較大，既然基於行的實現無法滿足需求，那有木有可能去基於字符進行 diff 呢？

diff-patch 算法

diff-match-patch[1] 是另一種 diff-patch 算法的實現，它是基於字符去進行 diff 的，這裏不介紹該算法的細節了，它的算法在這：diff-match-patch JS 實現源碼 [2]。我們直接測試下它的效果

// 示例1
const localText = '復仇者聯盟';
const userAText = '復仇者聯盟鋼鐵俠';
const userBText = '復仇者聯盟美國隊長';

// 結果爲：復仇者聯盟鋼鐵俠美國隊長
// 示例2
const localText = '復仇者聯盟';
const userAText = '復仇者聯盟美國隊長';
const userBText = '復仇者聯盟鋼鐵俠';

// 結果爲：復仇者聯盟鋼鐵俠美國隊長
// 示例3
const localText = '復仇者聯盟';
const userAText = '復仇者聯盟 美國隊長';
const userBText = '復仇者聯盟 鋼鐵俠';

// 結果爲：復仇者聯盟 美國隊長 鋼鐵俠

如上示例已經解決了 Linux 的 diff-patch 基於行 diff 的弊端，但仍然存在問題，如上的示例 1 和示例 2 如果沒有符號分割，那麼結果是一樣的。

const localText = '復仇者 Iron Man';
const userAText = 'Iron Man 鋼鐵俠';
const userBText = '復仇者 Caption';
// 結果爲：Caption

原始文檔爲 “復仇者 Iron Man”，用戶 A 修改爲了 “Iron Man 鋼鐵俠”，用戶 B 修改爲了 “復仇者 Caption”，直覺上其實可以合併爲 “Caption 鋼鐵俠”，但實際上卻修改爲了 “Caption ”(注意 Caption 後面有個空格，鋼鐵俠沒了)，也就是說 diff-match-patch 存在丟字符的情況，這個富文本格式的文檔中會是致命的問題，比如丟失了某個 > 可能整個文檔都會亂掉，那麼有木有既解決了行匹配衝突問題又解決了丟字符問題的解決方案呢？答案就是本文的重點——OT 算法

operation transformation

示例

ot.js[3] 是針對純文本的一種 JS 實現，我們看下它的實現效果，針對同樣的示例：

const str = '復仇者 Iron Man';
const operation0 = new ot.TextOperation().delete('復仇者 ').retain(8).insert(' 鋼鐵俠');
const operation1 = new ot.TextOperation().retain(4).delete('Iron Man').insert('Captain');

const op = ot.TextOperation.transform(operation0, operation1);
// 結果：Captain 鋼鐵俠

可以看到這正是符合我們預期的結果。

原理

看了很多講 OT 的文檔，基本每一篇都很長，雲山霧罩，但其實它的核心原理很簡單。在 OT 中，我們將文檔的操作分爲三個類型，通過組合這三個原子操作完成對整個文檔的編輯工作：

• insert(插入字符)；

• delete(刪除字符)

• retain(保持 n 個字符，也就是移動光標)；

注： 實際上 diff-match-patch 算法也將操作分爲三類：insert，delete，equal(不變的字符)，insert、delete 和 OT 中含義類似，equal 是指對比 diff 過程中那些沒有改變的字符，diff-match-patch 會給這些不同類型的字符打標，後面 patch 的時候再根據不同類型的字符做對應的邏輯處理。

insert

|

復仇者聯盟 |

如上 | 代表的是光標的位置，從上到下模擬用戶操作的行爲，以上操作使用 ot.js 來描述：

const str = '';
const operation = new ot.TextOperation().insert('復仇者聯盟');
const result = operation.apply(str); 
console.log(result); // 復仇者聯盟

op 創建時會有一個虛擬光標位於字符的開頭，在一個 op 結束時，光標一定要在字符串的末尾，其中 insert 會自動移動光標位置，因此我們這裏不需要手動去移動光標；

retain

| 復仇者聯盟

復仇者聯盟 |

復仇者聯盟鋼鐵俠 |

如上過程用 ot.js 來描述：

const str = '復仇者聯盟';
const operation = new ot.TextOperation().retain(5).insert('鋼鐵俠');
const result = operation.apply(str); 
console.log(result);// 復仇者聯盟鋼鐵俠

delete

| 復仇者聯盟鋼鐵俠

復仇者聯盟 | 鋼鐵俠

復仇者聯盟 |

如上過程用 ot.js 描述：

 const str = '復仇者聯盟鋼鐵俠';
const operation = new ot.TextOperation().retain(5).delete('鋼鐵俠');
const result = operation.apply(str); 
console.log(result);// 復仇者聯盟

刪除字符時可以輸入字符，也可以輸入字符數，實際上源碼中是直接取的'鋼鐵俠'.length 因此對於 delete 中字符串而言，只要長度正確就可以達到目的，上面代碼改成delete('123')不會有任何影響。

transform

前面的代碼我們看到過 ot.js 的這個方法，正是這個方法實現了 diff-match-patch 的丟失字符的問題，而 transform 正是 OT 中的核心方法。我們先不羅列他的源碼，先看幾個例子：

示例 1

原始文檔內容 (空白文檔)：|

用戶 A 編輯後的文檔內容：鋼鐵俠

用戶 B 編輯後的文檔內容：雷神

對應代碼實現：

const str = ' ';
const operation0 = new ot.TextOperation().insert('鋼鐵俠');
const operation1 = new ot.TextOperation().insert('雷神');
const op = ot.TextOperation.transform(operation0, operation1);
console.log('transform後op操作：', op[0].toString(), ' | ', op[1].toString()); 
// transform後op操作：insert '鋼鐵俠', retain 2  |  retain 3, insert '雷神'
console.log('transform後操作後的字符串：', op[0].apply(operation1.apply(str)), ' | ', op[1].apply(operation0.apply(str))); 
// transform後操作後的字符串： 鋼鐵俠雷神  |  鋼鐵俠雷神

最終結果是 “鋼鐵俠雷神”；

transform 的操作過程：

OiXRFV

示例 2

原始文檔：復仇者聯盟

用戶 A：復仇者鋼鐵俠聯盟

用戶 B：復仇者聯盟美國隊長

對應代碼實現：

const str = '復仇者聯盟';
const operation0 = new ot.TextOperation().retain(3).insert('鋼鐵俠').retain(2);
const operation1 = new ot.TextOperation().retain(5).insert('美國隊長');
const op = ot.TextOperation.transform(operation0, operation1);
console.log('transform後op操作：', op[0].toString(), ' | ', op[1].toString());
// transform後op操作：retain 3, insert '鋼鐵俠', retain 6  |  retain 8, insert '美國隊長'
console.log('transform後操作後的字符串：', op[0].apply(operation1.apply(str)), ' | ', op[1].apply(operation0.apply(str)));
// transform後操作後的字符串： 復仇者鋼鐵俠聯盟美國隊長  |  復仇者鋼鐵俠聯盟美國隊長

最終結果是 “復仇者鋼鐵俠聯盟美國隊長”；

transform 的操作過程：

ea2EI8

示例 3

原始文檔：復仇者聯盟鋼鐵俠美國隊長

用戶 A：復仇者聯盟鋼鐵俠

用戶 B：復仇者聯盟美國隊長

對應代碼實現：

const str = '復仇者聯盟鋼鐵俠美國隊長';
const operation0 = new ot.TextOperation().retain(5).delete('鋼鐵俠').retain(4);
const operation1 = new ot.TextOperation().retain(8).delete('美國隊長');
const op = ot.TextOperation.transform(operation0, operation1);
console.log('transform後op操作：', op[0].toString(), ' | ', op[1].toString());
// transform後op操作：retain 5, delete 3  |  retain 5, delete 4
console.log('transform後操作後的字符串：', op[0].apply(operation1.apply(str)), ' | ', op[1].apply(operation0.apply(str)));
// transform後操作後的字符串： 復仇者聯盟  |  復仇者聯盟

最終結果是 “復仇者聯盟”；

操作過程：

U3Hi4Y

最終結果是 “復仇者聯盟”；

示例 4

原始文檔：復仇者聯盟鋼鐵俠美國隊長'

用戶 A：復仇者聯盟

用戶 B：復仇者聯盟美國隊長

對應代碼實現：

const str = '復仇者聯盟鋼鐵俠美國隊長';
const operation0 = new ot.TextOperation().retain(5).delete('鋼鐵俠美國隊長');
const operation1 = new ot.TextOperation().retain(5).delete('鋼鐵俠').retain(4);
const op = ot.TextOperation.transform(operation0, operation1);
console.log('transform後op操作：', op[0].toString(), ' | ', op[1].toString());
//transform後op操作：retain 5, delete 4  |  retain 5
console.log('transform後操作後的字符串：', op[0].apply(operation1.apply(str)), ' | ', op[1].apply(operation0.apply(str)));
// transform後操作後的字符串： 復仇者聯盟  |  復仇者聯盟

最終結果是 “復仇者聯盟”；

操作過程：

vshnlX

ot.js 中 transform 的源碼如下：

 TextOperation.transform = function (operation1, operation2) {
    // ...
    var operation1prime = new TextOperation();
    var operation2prime = new TextOperation();
    var ops1 = operation1.ops, ops2 = operation2.ops;
    var i1 = 0, i2 = 0;
    var op1 = ops1[i1++], op2 = ops2[i2++];
    while (true) {
      //...
      // 對應示例1第一次循環的操作邏輯
      if (isInsert(op1)) {
        operation1prime.insert(op1);
        operation2prime.retain(op1.length);
        op1 = ops1[i1++];
        continue;
      }
      // 對應示例1第二次循環的操作邏輯
      if (isInsert(op2)) {
        operation1prime.retain(op2.length);
        operation2prime.insert(op2);
        op2 = ops2[i2++];
        continue;
      }
      // ...

      var minl;
      // 對應示例2循環
      if (isRetain(op1) && isRetain(op2)) {
        if (op1 > op2) {
          minl = op2;
          op1 = op1 - op2;
          op2 = ops2[i2++];
        // 對應示例2第三次循環的操作邏輯
        } else if (op1 === op2) {
          minl = op2;
          op1 = ops1[i1++];
          op2 = ops2[i2++];
        // 對應示例2的第一次循環操作邏輯
        } else {
          minl = op1;
          op2 = op2 - op1;
          op1 = ops1[i1++];
        }
        operation1prime.retain(minl);
        operation2prime.retain(minl);
       // 對應示例4的第二次循環
      } else if (isDelete(op1) && isDelete(op2)) {
        if (-op1 > -op2) {
          op1 = op1 - op2;
          op2 = ops2[i2++];
        } else if (op1 === op2) {
          op1 = ops1[i1++];
          op2 = ops2[i2++];
        } else {
          op2 = op2 - op1;
          op1 = ops1[i1++];
        }
      // 示例3的第二次循環
      } else if (isDelete(op1) && isRetain(op2)) {
        if (-op1 > op2) {
          minl = op2;
          op1 = op1 + op2;
          op2 = ops2[i2++];
        } else if (-op1 === op2) {
          minl = op2;
          op1 = ops1[i1++];
          op2 = ops2[i2++];
        } else {
          minl = -op1;
          op2 = op2 + op1;
          op1 = ops1[i1++];
        }
        operation1prime['delete'](minl "'delete'");
      // 示例3的第三次循環
      } else if (isRetain(op1) && isDelete(op2)) {
        if (op1 > -op2) {
          minl = -op2;
          op1 = op1 + op2;
          op2 = ops2[i2++];
        } else if (op1 === -op2) {
          minl = op1;
          op1 = ops1[i1++];
          op2 = ops2[i2++];
        } else {
          minl = op1;
          op2 = op2 + op1;
          op1 = ops1[i1++];
        }
        operation2prime['delete'](minl "'delete'");
      } else {
        throw new Error( The two operations aren't compatible );
      }
    }

    return [operation1prime, operation2prime];
  };

如上 4 個示例覆蓋了transform所有分支的操作。核心原理其實很簡單，就是通過循環去將兩個操作重新進行排列組合，按照操作的類型作出不同的邏輯處理，這是 OT 中非常核心的方法，除此之外還有compose，apply等方法，這裏就不一一羅列了。

上面過程經常用一個菱形圖來表示 transform 過程：

transform(a, b) = (a', b');

compose

顧名思義，這個方法是用來合併兩次操作 OP 的，比如：

 const str = '復仇者聯盟';
const operation0 = new ot.TextOperation().retain(5).insert('鋼鐵俠');
const operation1 = new ot.TextOperation().retain(8).insert('黑寡婦');
const op = operation0.compose(operation1);
console.log('compose後op操作：', op.toString());
console.log('結果：', op.apply(str)); // 復仇者聯盟鋼鐵俠黑寡婦

compose 的實現和 transform 類似，羅列兩個 OP 所有的組合可能性，分別作出對應的邏輯處理。相關源碼可以去 github[4] 這裏查看。當然 ot.js 的 API 遠不止這兩個，比如客戶端的 undo/redo 方法用來實現文檔的撤銷 / 重做，這裏就不一一過了

時序控制

基於以上示例和代碼相信 OT 的核心原理大家應該比較清晰了，但 OT 算法基於順序來進行轉換的，假如用戶 A 操作了兩次文檔，但因爲網絡原因，第二次比第一次先到達了服務器，而服務器基於收到的順序來分發給其它用戶那麼必然會出現問題。流程圖如下：

因此我們需要對每次的操作進行一個版本控制，在每次提交的時候加上一個版本標識，類似 git 的 commitID，每次提交版本都自增 1，來標識每次的 OP 操作；客戶端和服務端各自維護一份版本；

客戶端：發送出的請求返回確認後，本地版本 + 1；

服務端：完成一次 OP 時，版本 + 1;

因此客戶端的版本一定是小於等於服務端的。

相關轉換過程如圖，這裏就不細說了，其實就是上面菱形的延伸。感興趣可以去 http://operational-transformation.github.io/index.html 這裏模擬體驗整個過程。github 上有很多 js 版本的 OT 實現庫，比如 https://github.com/marcelklehr/changesets 也是 OT 算法的實現，感興趣同學也可以去了解下。

狀態控制

OT 將操作的狀態三爲三種：

• Synchronized: 沒有提交 OP，等待新的 OP

• AwaitingConfirm： 有新的 OP 提交了，等待後臺確認，在此期間沒有新的編輯行爲產生；

此階段收到後臺新的 OP，會進行一次 transform

transform(OP1, OP) = (OP1', OP')；其中 OP'會被應用到本地

• OP1 是本地提交後但未被確認的 OP；

• AwaitingWithBuffer： 有新的 OP 提交了，等待後臺確認，在此期間有新的編輯行爲產品了新 OP；

此階段產生的新的 OP，會和上次本地編輯的 OP 做一次 compose，合併爲一個新的 OP

此階段收到後臺新的 OP，會進行兩次 transform 和一次 compose:

OP3 = OP1.compose(OP2);

transform(OP1, OP) = (OP1', OP');

transform(OP3 , OP') = (OP3', OP'');

最終 OP''會被應用到本地，然後更新 OP1 = OP1' 和 OP3 = OP3'

OP：服務端推送的新的 OP；

• OP1：本地提交後但未被確認的 OP；

• OP2：此階段產生的新的編輯操作；

• OP3：是 OP1 和 OP2 compose 後生成的 OP；

OT 算法很適合用用來處理文本的協同，最早提出時間可以追溯到 1989 年，也有各種語言的具體實現，相對比較成熟，目前在 Google Docs，騰訊文檔，包括我司的飛書文檔都是用的 OT 算法，但 OT 目前是沒法做到點對點通信的，隨着 Web 通信協議的發展 (比如 WebRTC)，點對點的通信已經成爲 C/S 架構的可替代方案，CRDT 算法也是一種協同算法，大概在 2006 年提出，目前在 Atom、Figma 等產品中都有落地使用，CRDT 在支持 C/S 架構模型的同時也可以支持點對點的傳輸，但目前各個文檔其實還是主要使用 OT，下面這個視頻有講說 CRDT 隨着文本內容的增加複雜度會遠大於 OT，具體原因還沒了解，感興趣的同學可以一起研究下。

https://youtu.be/PWzrbg9qqK8

CRDT 相關論文：https://www.researchgate.net/publication/310212186_Near_Real-Time_Peer-to-Peer_Shared_Editing_on_Extensible_Data_Types

CRDT 介紹：https://crdt.tech/resources

CRDT 開源實現：https://github.com/yjs/yjs

Easysync

以上介紹了協同處理算法中的 OT 算法，我們的例子也都是用的純文本，但實際上的在線文檔不可能如此簡單的，比如有各種各樣的 block，富文本的支持，評論，選中等等功能；如果單純去使用 ot.js 來去做的話，無異於挖坑自埋。而 easysync 也是 OT 算法的一種實現，它被使用在 etherpad 中。

關於 Etherpad

easysync 這套算法作者是申請了專利的，專利地址：https://www.freepatentsonline.com/y2012/0110445.html，憑藉這套算法作者創立了 etherpad 公司，後面被 google 收購，然後將 etherpad 開源了。起初 etherpad 是一套跑在 Java 虛擬機上，可以用 JS 來寫邏輯的服務，但更多的功能還是以 jar 包的形式提供，這樣搞也主要是爲了 easysync 只需要實現一份 JS 的版本就可以同時跑在前端和後臺，後面隨着功能的迭代完善官方也發覺了這套東西很難維護，後面推出了 nodejs 版本的 etherpad-lite[5]，不在需要維護 jar 包。簡單說 etherpad 就是個 google 開源 (Apache 協議) 的富文本編輯器(demo 地址 [6])，而協同算法用的是 OT 算法之一的 easysync 算法。

描述文檔 (clientVars)

在 easysync 中使用一種數據結構來描述整個文檔。

對於上面截圖中的文檔的描述：

{
    attribs : *0+5|1+1*1*2*3*4*5+1*6+3*2|1+1 ,
    text : 復仇者聯盟\n*鋼鐵俠\n
}

上面這個對象描述的是整個文檔的內容和格式，text 存儲的是整個文檔的內容包括換行符等符號，attribs 存儲的是對文檔內容格式的描述，上圖中的屬性中 *+ 都不是我們印象中的乘法加法，這裏面的數字只代表序號。翻譯下具體符號的含義：

• *n：第 n 個屬性；

• |n: 影響 n 行；

• +n: 取出 n 個字符數；

注：easysync 裏面的數字大都是 36 進制的，主要目的是爲了縮短傳輸字符的長度；

具體的屬性 (加粗，_斜體_等) 描述在另一個屬性 apool 中。上面文檔中對應的屬性描述如下：

{
    apool :{
        numToAttrib :{
            0 :[
                lineguid ,
                HwV9Nr
            ],
            1 :[
                align ,
                left
            ],
            2 :[
                author ,
                52000000000000025
            ],
            3 :[
                fragmentguid ,
                1981193224752831644
            ],
            4 :[
                insertorder ,
                first
            ],
            5 :[
                lmkr ,
                1
            ],
            6 :[
                lineguid ,
                sQgJ38
            ],
            7 :[
                store ,
                {\ contentConfig\ :{\ 0 \ :[1,2,3],\ 1 \ :[1,2,3],\ 2 \ :[1,2,3,4,5],\ 3 \ :[1,4,5],\ 4 \ :[]}}
            ]
        },
        nextNum :8
    }
}

如上的 numToAttrib 屬性裏面存儲的序號就是上面中數字。結合 apool 裏面的屬性值我們就可以把 *0+5|1+1*1*2*3*4*5+1*6+3*2|1+1 **** 給翻譯出來了：

• 第 0 個屬性，應用於前 5 個字符 (復仇者聯盟)，影響一行；

• 取出 1 個字符應用第 1，2，3，4，5 屬性 (這裏的屬性 2 是 author，即當前編輯這部分文本的用戶)；

• 取出 1 個字符應用屬性 6；

• 取出 3 個字符 (鋼鐵俠) 應用屬性 2，影響一行；

• 取出 1 個字符 (換行)；

可以看出這其實就是一份描述文檔的數據結構，理論上我們只要實現了對應平臺的渲染器，那就不僅可以把它渲染成 html，同樣也可以應用在 native。但這種格式是按文行和列來描述，遇到表格這種一行裏面分格子的需求就很難做了。

描述文檔的變更 (changeset)

上面 easysync 定義了一組數據結構來描述整個文檔內容，但在協同的場景下如何處理變更也會是一個很棘手的問題。在 easysync 定義了一個叫 changeset 的概念去描述文檔的變更。文檔在一開始創建或是導入的時候會生成一個初始化的內容結構，之後所有的更改都會用 changeset 來表示。對文檔做一下變更，則會產生一次 changeset：

Z:c>3|1=7=4*0+3$ 黑寡婦

如果用通信協議來理解 changeset 的話，可以分爲包頭和包體，包頭主要用來描述字符長度，而上面的 Z 似乎是個 Magicnumber，每一個 changeset 都會以 Z 開頭。而包體則用來描述具體的操作 (比如新增字符，刪除字符等)。$ 後面的被叫做 charbank，所有這次變更新增的字符都是從 charbank 裏面取出來的。在 changeset 中符號代表的含義如下：

• Z: Magicnumber，目測沒啥含義；

• :n: 之前文檔的長度（在 easysnc 中一般都用 36 進制來表示數字）；

• >n: 新增字節；

• <n: 刪除字節；

• |n：影響了第 n 行；

• *n: 應用屬性 n；

• +n：取出 n 個字符數；

• -n: 從當前位置開始，刪除 3 個字符；

• =n: 字節不變；

上面的 changeset 翻譯如下：

之前的文本長度是 c(十進制的 12)，影響了第 1 行，保留了 7 個字符，保留 4 個字符，插入 3 個字符應用屬性 0。

而這裏的+、-、=在某種意義上對應的就是 ot.js 中的insert,delete和retain三個原子操作；

我們再看一個刪除字符 (刪除了黑寡婦) 的例子：

Z:f<3|1=7=4-3$

之前的文本長度是 f(十進制的 15)，影響了第 1 行，保留 7 個字符，保留 4 個字符，從這個位置開始，刪除 3 個字符；

在刪除的 changeset 中 charbank 是空的，因爲是刪除，沒有新增字符；官方文檔參考：https://github.com/ether/etherpad-lite/blob/develop/doc/easysync/easysync-notes.pdf

協同

在實際操作中 changeset 會非常的多，很頻繁，比如現在的我在瘋狂碼字一樣，那麼對於 changeset 的合併 (compose) 就很重要，它可以極大地縮短傳輸字符的長度，而在協同的場景下，用戶 A 和用戶 B 提交的 changeset 就需要去合併，我們上面提到過的 ot.js 中的 transform 方法，在 easysync 中它叫做 follow。回顧下前面的 ot.js 我們會發現

• ot.js 中的一次 OP => easysync 中的 changeset；

• ot.js 中 tranform 方法 => easysync 中的 follow 方法；

compose

用戶 B 本地操作：插入字符” 美國隊長 “，對應 changeset 是：

Z:c>4|1=7=4*0+4$ 美國隊長

用戶 B 緊接着操作：插入字符” 雷神 “，對應 changeset 爲：

Z:g>2|1=7=8*0+2$ 雷神

兩次操作假設相隔很短，那麼完全可以合併爲一次 changeset：

const cs1 = 'Z:c>4|1=7=4*0+4$ 美國隊長';
const cs2 = 'Z:g>2|1=7=8*0+2$ 雷神';
console.log(Changeset.compose(cs1, cs2, false, null));
// Z:c>6|1=7=4*0+6$ 美國隊長雷神

注意，compose 是有合併順序的，參數 1 一定是參數 2 的前置操作。下文中我們將 compose 方法省略。 狀態 A 和狀態 B 合併爲狀態 C（狀態 A 是狀態 B 的前置操作），記爲 C = AB；

merge

compose 合併的是有前後操作關係的狀態，但在文檔協同中更多的是併發衝突問題，merge 是 easysync 中解決併發衝突的算法，比如用戶 A 和用戶 B 同時編輯了一份文檔：

用戶 A 插入 黑寡婦 ：

Z:c>3|1=7=4*0+3$ 黑寡婦

用戶 B 插入 美國隊長 ：

Z:c>4|1=7=4*0+4$ 美國隊長

merge 就是將操作 A 和 B 進行合併的，合併後的狀態我們記爲 C，即 C = m(A, B);

對 m 的約束條件： A 和 B 的順序可以是任意的，即 m(A, B) = m(B, A) ；

follow

上面的例子生成的狀態 C = m(B, A)，其實是應用於服務端的狀態，假設服務端狀態 X => X'。那麼可記爲 X' = Xm(B, A)。X'是通過 X 和 m(B, A) 合併得到的，但對客戶端來說無法直接去這樣操作，因爲對用戶 A 來說，狀態 C 並不是 A 的前置，無法直接去合併，我們需要一個算法去做轉換，這個實現就是 follow 方法，還是上面的例子：

const A = 'Z:b>3|1=4*0+3$ 黑寡婦';
const B = 'Z:b>4|1=4*0+4$ 美國隊長';

const A1 = follow(B, A, false, null);
const B1 = follow(A, B, true, null);
console.log(A1, B1);
// Z:f>3|1=4=4*0+3$ 黑寡婦 Z:e>4|1=4*0+4$ 美國隊長
const A2 = compose(A, B1);
const B2 = compose(B, A1);
console.log(A2, B2);
// Z:b>7|1=4*0+7$ 美國隊長黑寡婦 Z:b>7|1=4*0+7$ 美國隊長黑寡婦

可以看到用戶 A 和 B，最終的 changeset 分別是 A2 和 B2，A2 和 B2 是完全相等的。這裏我們將 follow 方法記爲 f, 當服務端收到用戶 A 和用戶 B 的併發操作的時候處理過程，假設服務端目前的狀態是 X，收到了用戶 A 的操作 A，然後 apply 到字符串變成了 XA，此時又收到了用戶 B 的操作 B，很明顯，此時直接應用 XAB 是不行的，因爲 A 和 B 都是基於 X 來變更的，A 並不是 B 的前置，此時就需要一個 B'，來實現 XAB'，且有 XAB' = XBA'。 也就是上面例子中的 follow 結果，B'= f(A, B)，A' = f(B, A)。由此可得到：XAf(A, B) = XBf(B, A)。即，Af(A, B) = B f(B, A) ; 這個公式就是 follow 算法的核心。

C/S 模型

前面也提到過 OT 算法必然需要一個 Server 去中轉，不支持點對點。我們來看下客戶端和服務端分別是怎麼工作的：

客戶端

前面說過在 OT 中客戶端可以把用戶的操作分爲三種狀態，在 easysync 中也有三種狀態：

A: 服務端最新內容，未進行修改；

X：changeset 已經提交了，還沒被確認；

Y: 客戶端產生的還沒提交到服務端的變更集；

還有一種特殊的 changeset，就是在 X 期間，又產生了新的 changeset，我們用 E 來代替。

E: ****changeset 提交期間產生的新的編輯；

etherpad 官方文檔裏面寫的巨複雜，我簡單梳理下這裏客戶端的狀態變化和操作 (注意：下文中的 = 和≠都是傳統數學意義上的符號，直接合並即使用 compose/merge 合併)：

1. 拉取最新文檔，未進行編輯

此時 X = Y = A = In(初始狀態)

2. 開始產生編輯行爲

用戶產生新的編輯 E，此時 Y 有兩種狀態，一種是初始狀態 Y = In，一種是之前產生了編輯，Y ≠ In。但無論 Y 是否等於 In，操作 E 都是合併到 Y 中，此時 Y = Y · E；這樣可以不間斷的更新 Y，不至於丟失用戶數據；

3. 提交變更集到服務器 (未收到 ack)；

此時，變更集 Y 會變成已提交狀態，同時 Y 的狀態重置，X = Y，Y = In；

4. 收到服務器 ack 確認；

此時 X 變成了已確認的狀態，A 狀態轉變爲最新的 X，X 狀態重置，也就是 A = X；X = In；

5. 收到用戶 B 的變更集 B；

• 前置條件： 對 B 的約束條件是，A 必須是 B 的前置，即運算 A · B 是可執行的（爲什麼要有這個約束條件，大家可以思考下） 此時的變化是比較複雜的，前面 AXY 的變遷規則已無法適應這種場景，需要作出調整。用戶 A 需要吸收 B 生成，A'、X'、Y'來回歸到前面的變遷行爲。由於此時 AXY 是已經展現給用戶的狀態了，我們用 V 來表示最終的文檔變更狀態。

• A 吸收 B 變爲 A': A' = AB;

• X 吸收 B 變爲 X': B 和 X 有相同的前置 A，使用 follow 方法合併即可，X' = f(B, X),B' = f(X, B); 可推斷出 ABX' = AXB '

• Y 吸收 B 變爲 Y'：

• 由 ab 兩點可知，A'B' = ABX' = AXB ' (follow 算法) 前面說了 B 的前置是 A，但 Y 的前置是 X，因此需要轉化一下 B'= f(X, B)，使得 B'和 Y 都有相同的前置 X，然後生成 Y'= f(B', Y)；即Y' = f(f(X, B), Y)；

• 生成最終狀態 V:

• V = A'X'Y'

  = AB · f(B, X) · f(f(X, B), Y)

  = A · Bf(B, X) · f(f(X, B), Y)

  = A · Xf(X, B) · f(f(X, B), Y)

  = AX · f(X, B) · f(f(X, B), Y)

  = AX · Y · f(Y, f(X,B))

  = AXY · f(Y, f(X, B)

此時再將新的 A'，X'，Y'賦值給 AXY

服務端

這裏服務端的處理邏輯相對前端來說要簡單很多，主要做兩件事：

1. 響應客戶端請求，建立鏈接，並返回文檔最新狀態；

2. 處理客戶端提交上來的變更集，返回確認信息；

其中處理變更集的邏輯比較值得一說，當服務端收到一個變更集 C 的時候，會做以下五件事：

1. 從客戶端版本記錄中，獲取 C 的前置版本 Sc （客戶端的初始版本）；

2. 注意服務器記錄的最後一個變更集（Changeset）Sh 與 Sc 之間可能還存在多次變更集（Changeset）記錄 (此時可能有其它用戶已經推送了新的版本，但還未下發到當前客戶端)。此時需要計算出 C 相對 Sh 的後置 C' 。這樣才能「疊加」到當前文檔上；

3. 發送 C' 到其它客戶端；

4. 發送確認（ACK）給當前客戶端；

5. 將 C' 添加到記錄列表中，同時更新版本；

後記

比較粗淺的瞭解了以上和在線文檔相關的一些技術，其中的一些細節實現和難題都充滿了挑戰，這個方向確實是道阻且長，很多看似簡單的功能背後都充滿着工程師的心血 (比如協同中的文字選中)。

參考資料

[1] diff-match-patch: https://github.com/google/diff-match-patch/tree/master/javascript

[2] diff-match-patch JS 實現源碼: https://github.com/google/diff-match-patch/blob/master/javascript/diff_match_patch_uncompressed.js

[3] ot.js: https://github.com/Operational-Transformation/ot.js/blob/master/lib/text-operation.js

[4] github: https://github.com/Operational-Transformation/ot.js/blob/master/lib/text-operation.js#L238

[5] etherpad-lite: https://github.com/ether/etherpad-lite

[6] demo 地址: https://rich.etherpad.com/p/re3434hkj

[7] 《OT 協同》: https://bytedance.feishu.cn/wiki/wikcnn505JVvliIX3Z0JKJEDQqh#zdaw84

[8] Etherpad 協同概述: https://bytedance.feishu.cn/wiki/wikcnQ0bGESsmnJr6HegIno15Gg

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/MmWDz7hqeOKMPr-xKwUHnA