OT演算法在協同編輯器中的應用

語言: CN / TW / HK
時間 2022-07-03 14:15:09
主題:

1 背景

最近3年疫情的原因，導致面試者無法現場面試，於是遠端面試成了當前面試的主流。對於開發崗位來說，寫程式碼那是必須可少的功能，所以完善的面試系統有一個重要功能就是協同編輯，下面就讓我來帶大家分析一下協同編輯功能的實現方案和OT演算法的應用。

2 協同編輯場景

協同編輯的場景是在同一房間內，所有人都可同時操作編輯器內容，關鍵是讓所有人看到的內容是一致的，這裡面涉及的技術就包括了web編輯器，訊息的廣播和保證內容一致的演算法，我們今天討論的是保證內容一致的演算法。

讓我們看下實現保證內容一致的一些思路： - 思路1： 全量覆蓋 這種方法就是簡單粗暴，每次都把編輯器的內容全量廣播給其他人，這樣在多人同時操作的時候就會有相互覆蓋的現象，導致無法同時編輯，所以是不可取的。

  • 思路2: 加操作鎖 既然同時編輯會有相互覆蓋的問題，那就加個操作鎖，每次改變之前之前先搶一下鎖，然後再改變，這種思路不是實現同時編輯，而是強制不同時編輯，會導致體驗很差，明明輸入了但是因為沒有搶到鎖而不生效。

  • 思路3: 增量操作 既然全量傳遞會相互覆蓋，那就增量的傳遞，只傳遞這次改變了什麼，比如我在第2個字元插入了'xx'等等，這樣雖然不會全量覆蓋了 但是同時操作會導致內容不一致，舉例如下圖：

image.png

兩個使用者，開始的內容都是AAAZ，同時操作，經過傳遞和轉換之後兩端的內容就不一致了。 OT協同演算法的核心就是解決該問題。

3 OT演算法

OT演算法的關鍵技術點總結為四點：定義原子操作、版本確認機制、操作轉換、客戶端狀態轉移，下面就分別講解。

3.1 定義原子操作

OT演算法中對於內容的操作抽象為三種： - Retain 保持操作，用大於0的數字表示 記錄要保持的字元數量 - Insert 插入操作，用插入的字串表示 - Delete 刪除操作，用小於0的數字表示 -n就是刪除n個字元

每次對於整個文字的處理都可以用一個有上述3眾原子操作的陣列表示。下面我舉一些直觀的例子。 - "" -> "A" ,運算元組為 ["A"] 只有一個Insert - "A" -> "AB" ,運算元組為 [1,"B"] 保持一個字元,然後插入B - "ABC" -> "AB" ,運算元組為 [1,-1,1] 保持一個字元,刪除一個字元，然後再保持一個字元

編輯器和服務端之間傳輸的就是這種運算元組，當收到之後會將其轉換為操作物件，定義如下：

js function TextOperation () { this.ops = []; this.baseLength = 0; this.targetLength = 0; }

其中除了 this.ops記錄運算元組之外，還增加了兩個屬性this.baseLength和this.targetLength。 - this.baseLength表示該操作前文字的長度，會用於操作轉換時的校驗。 - this.targetLength表示該操作應用在文字後，文字的長度。

舉個複雜的例子： - "123456789" -> "123A89" ,運算元組為 [3,"A",-4,2],轉成的操作物件為

{ ops: [3,"A",-4,2], baseLength: 9, targetLength: 6 }

3.2 版本確認機制

在OT協同演算法中，服務端作為一個記錄文件內容和所有歷史版本操作的中心，當有新的客戶端建立連線時首先進行一次同步，之後客戶端每次傳送一個操作時 還要同時傳送本次操作時基於什麼版本進行的更新，這樣服務端會從該版本開始進行操作轉換。客戶端每次的操作不能直接修改當前的版本，而是要收到服務端的確認之後才能進行版本的更新，因為客戶端不記錄所有歷史的操作和版本的對應關係，通過未確認的狀態來判斷是否需要操作轉換。舉例如下圖：

image.png

3.3 操作轉換

操作轉換是OT演算法的核心，它的核心公式是：

``js [A,B`] = transform(A,B)

apply(apply(S, A), B') = apply(apply(S, B), A') ```

A和B兩個操作，經過轉換之後生成 A' 和 B' , 使得對於相同的內容S 經過A和B'的應用結果 等於 經過B和A'的應用結果,具體transform程式碼參見開源專案：ot.js。

這裡有一個菱形表示法用於圖形化的描述OT的操作轉換過程：

image.png

我們可以這樣理解，每一個點是一個狀態，每一條邊是一個操作，左邊的永遠是客戶端的操作， 右邊的永遠是服務端的操作，兩者在相同的狀態下，客戶端經過A和B'之後和服務端經過B和A'之後達到相同的狀態。 這是最基本的一個版本衝突的菱形表示法，實際應用中會有更多的版本衝突，使用菱形表示法會把整個過程展示的很直觀。

3.4 客戶端狀態轉移

客戶端每次操作不會立刻增加版本，而是要等待服務端的確認後增加版本，同時客戶端的操作在沒有被服務端確認之前，是不會繼續傳送新的操作，而是將要傳送的操作進行快取，等待確認後再進行傳送，這裡客戶端就維護了三種狀態，除了客戶端的傳送之外，還可能從服務端接受操作，不同的狀態客戶端會有不同的處理。 - Synchronized， 已經同步狀態，客戶端沒有待確認的操作。 - AwaitingConfirm， 等待確認狀態，客戶端有等待服務端確認的操作。 - AwaitingWithBuffer，等待確認狀態，並且還有待發送的操作。

三種狀態的轉移如下圖所示： image.png

4 OT場景分析

以上講解了OT演算法的關鍵技術，下面就針對需要進行OT操作的場景進行分析。

4.1 客戶端修改一次，服務端修改一次衝突

此時客戶端的狀態是AwaitingConfirm，而收到了服務端下發的操作，菱形表示法如下：

image.png

解釋：客戶端進行了A操作，服務端先進行了B操作，客戶端進行OT之後 應用B',等待的狀態變為 A', 而服務端收到A之後，同樣與B進行OT，然後應用A'。

4.2 客戶端修改一次,服務端修改多次衝突

此時客戶端的狀態是AwaitingConfirm，相比於4.1的情況，在收到修改確認之前，連續多次收到服務端的下發，菱形表示法如下：

image.png

客戶端先後應用B1'和B2',可以接受更多的修改。

對於服務端來說，當收到客戶端的操作A時，是連續進行轉換，菱形表示法如下：

image.png

讓操作A連續的和操作B1和B2進行轉換，最終應用A''。

4.3 客戶端修改多次,服務端修改一次衝突

此時客戶端的狀態是AwaitingWithBuffer，客戶端變化的菱形表示法如下：

image.png

客戶端進行了A操作後，還執行了A2操作，所以第一次OT之後 狀態C不是最終狀態，而是一種臨時狀態。B'和A2就要繼續OT計算，達到狀態D。同時注意這裡從等待發送A2 變成了等待放A2'。 服務端則是先收到A操作後 應用A',而後收到A2'。

5 總結

OT演算法和一整套完整的設計，確實解決了協同操作的問題，本文通過分析純文字的協同，講清楚最核心的關鍵技術點。對於更復雜的場景則需要設計的原子操作和操作轉換演算法也會更加的複雜。比如騰訊的線上文件，除了文字之外，還需要同步樣式、圖片元素等等。留一個問題：既然OT演算法可以解決協同操作問題，為什麼在使用騰訊線上excel的過程中發現多個人同時操作一個表格單元的時候，會出現相互覆蓋的問題？

  • 如果覺得有用請幫忙點個贊。
  • 我正在參與掘金技術社群創作者簽約計劃招募活動，點選連結報名投稿。
「」