基于WebSocket的實時協(xié)同編輯方法及應(yīng)用

陳詩雨 熊才權(quán) 董奕

摘 要：操作意圖一致性控制是協(xié)同編輯的重要研究問題。傳統(tǒng)的協(xié)同控制算法在操作意圖一致性和交互性上存在加鎖粒度大小難以把握、函數(shù)轉(zhuǎn)換結(jié)果與用戶意圖不一致、操作對象全局ID難以分配等局限性。為減少用戶協(xié)同工作中出現(xiàn)的操作意圖不一致現(xiàn)象，提高工作效率，提出一種基于WebSocket協(xié)議及隱藏/恢復(fù)機制的共享同步控制方法。該方法采用WebSocket技術(shù)，通過集合類對編輯樣本和操作主體進行共同控制，從而減小操作主體的等待時間，實現(xiàn)在靜默和動態(tài)兩種情況下共享編輯樣本的一致性，不僅很好解決了用戶操作意圖一致性問題，還能滿足用戶在協(xié)同過程中的交互需求，提高頁面質(zhì)量。

關(guān)鍵詞：WebSocket；操作意圖一致性；頁面質(zhì)量；共享同步控制方法（SSCM）

DOI：10. 11907/rjdk. 182139

中圖分類號：TP301 文獻標(biāo)識碼：A 文章編號：1672-7800（2019）005-0079-05

Abstract： Operation intention consistency control is an important research problem in collaborative editing. Traditional collaborative control algorithm has shortcomings in operating intention consistency and interaction， such as the difficulties to ensure the sizes of lock granularities， the inconsistency between function conversion results and users intentions and difficulties to allocate global operation ID. In order to reduce the user operation intent inconsistent phenomenon occurring in a collaborative work and improve the efficiency of users to work together， we put forward shared SSCM （Shared Synchronization Control Method） based on the WebSocket protocol and hide/recovery mechanism， the method uses the WebSocket technology， control the common edit samples and operating subject through the collection class， thus reduces the waiting time for operation main body， and realises the consistency of shared editing samples in silence and dynamic cases. This method can not only solve the problem of the consistency of user operation intention， but also can meet the user's interactive demand in the collaborative process and improve the quality of the page.

Key Words： WebSocket；operational intent consistency；page quality；shared synchronization control method （SSCM）

0 引言

協(xié)同編輯指在網(wǎng)絡(luò)環(huán)境下多人共同編輯一個文檔，集結(jié)群體智慧，使最終文檔滿足群體多數(shù)人員的意見要求，是計算機協(xié)同工作研究領(lǐng)域的典型應(yīng)用。協(xié)同工作要求很強的實時性，即用戶不用刷新頁面就能及時看到他人所作的修改。實時協(xié)同編輯需要解決的重點問題是保證用戶操作意圖的一致性，即如何在較高的網(wǎng)絡(luò)延遲下盡可能多地維護用戶意圖?，F(xiàn)有的操作意圖一致性算法如OT（Operational Transformation）算法[1]、AST（Address SpaceTransformation）算法[2]、CRDT（Commutative Replicated Data Type）算法[3-6]等各具優(yōu)點，但都存在局限性[3]。在OT算法中，本地操作可以立即執(zhí)行， 而遠程操作需要結(jié)合本地歷史操作，進行并發(fā)操作轉(zhuǎn)換后才能執(zhí)行。而設(shè)計一個有效的并發(fā)操作轉(zhuǎn)換函數(shù)面臨很大挑戰(zhàn)，因而這種算法在實際應(yīng)用中存在一定的局限性[3]。AST（Address SpaceTransformation）算法通過文檔的地址空間回溯到操作產(chǎn)生時的狀態(tài)，以此獲取操作的執(zhí)行位置。為保證回溯的正確性，必須保存上次運算之后的求解路徑，而數(shù)據(jù)量過大數(shù)據(jù)庫就會產(chǎn)生超負現(xiàn)象。CRDT算法雖不需要保存操作歷史，且并發(fā)操作之間不需要進行轉(zhuǎn)換，但當(dāng)操作主體很多時，操作主體標(biāo)識可能不唯一，從而出現(xiàn)編輯沖突[3]。編輯鎖是解決編輯沖突最簡單的方法，但傳統(tǒng)的協(xié)同編輯方法是對整篇文章加鎖，粒度過大，不能實現(xiàn)多人協(xié)作；毛啟容等[7]提出的樂觀鎖技術(shù)雖減小了加鎖粒度，但卻需要在加鎖時人為發(fā)起請求，請求同意后才允許編輯，效率很低。無論是對整篇文章加鎖還是樂觀鎖技術(shù)，都是基于鎖或序列化的處理機制，著重于實現(xiàn)結(jié)果一致性卻無法滿足用戶在協(xié)同過程中對操作意圖的一致性需求。何發(fā)智等[5]對CRDT算法進行了大量優(yōu)化和改進，提出了一種支持對字符串操作的集成和選擇性撤銷算法，以緩解選擇性撤銷時出現(xiàn)的編輯沖突。LIU等[8]提出的DSGOT算法，雖然通過邏輯時鐘解決了操作之間的矛盾，可有效保證操作意圖一致性，但尚未在實際文本協(xié)同編輯系統(tǒng)中得到應(yīng)用。Sun等[9]提出的CCR方法，不僅提供了一種解決實時協(xié)同編輯系統(tǒng)沖突的方法，而且提供了一個支持部分沖突解決策略的框架。

隨著互聯(lián)網(wǎng)技術(shù)的快速發(fā)展，基于Web的協(xié)同編輯應(yīng)用需求也越來越多。頁面質(zhì)量被認為是協(xié)同編輯的結(jié)果，不同層次的沖突對頁面質(zhì)量的影響不同，且隨時間變化而變化[10]。Xiao等[11]提出的基于P2P的ORGA協(xié)同編輯方法可不依賴于操作用戶的終端數(shù)量，較好實現(xiàn)操作意圖的一致性，但P2P服務(wù)需要重復(fù)建立通道，導(dǎo)致網(wǎng)絡(luò)負載壓力較大，對頁面質(zhì)量也有所影響。目前基于Web的協(xié)同編輯技術(shù)大多采用WebSocket協(xié)議，如基于Web的實時協(xié)同圖形編輯系統(tǒng)CoWebDraw[12]，通過WebSocket協(xié)議，實現(xiàn)了圖形的實時轉(zhuǎn)換且頁面質(zhì)量較高。

為滿足操作意圖一致性，提高頁面質(zhì)量，解決協(xié)同編輯在網(wǎng)絡(luò)環(huán)境下編輯沖突問題，本文提出一種基于WebSocket協(xié)議及隱藏/恢復(fù)機制[13]的共享同步控制方法（SSCM），用于實現(xiàn)編輯樣本的編輯沖突問題，以實現(xiàn)實時轉(zhuǎn)換目的。 WebSocket是一種雙向通信技術(shù)，將該技術(shù)應(yīng)用到協(xié)同編輯的同步控制中有以下優(yōu)勢：①可避免消息的被動更新，提供容錯功能[14]；②可改善因操作轉(zhuǎn)換算法的不唯一和難以控制帶來的協(xié)同工作環(huán)境下的不穩(wěn)定問題，提高用戶體驗感[15]；③可有效實現(xiàn)操作意圖一致性，緩解編輯沖突問題，提高協(xié)同編輯效率。

1 共享同步控制方法

共享同步控制方法（Shared Synchronization Control Method，SSCM）主要用來解決操作主體間因合作和資源共享所帶來的沖突問題。該方法首先通過文章預(yù)處理建立文章數(shù)據(jù)庫，然后利用集合類建立在線用戶隊列和段落用戶隊列，以保證所有用戶的實時性，最后在Web環(huán)境下建立基于WebSocket服務(wù)端和客戶端之間的通道，實現(xiàn)編輯樣本的共享同步控制。在WebSocket過程控制環(huán)境下，SSCM包括對文章的控制和對用戶的控制。對文章的控制包括文章的預(yù)處理以及文章的分段同步，對用戶的控制包括用戶編輯任務(wù)排隊及多段落互斥訪問控制。SSCM可有效縮小由于隊列等待引起的時間差，大大提升協(xié)同編輯效率。

1.1 文章預(yù)處理

文章預(yù)處理的主要工作是對文章進行分段，建立段落庫。為解決操作意圖的一致性，編輯樣本以段為節(jié)點，將操作記錄與節(jié)點進行綁定，同時利用隱藏/恢復(fù)機制實現(xiàn)編輯樣本的一致性。首先根據(jù)上傳文件及相關(guān)文件操作獲取文章信息，再根據(jù)相關(guān)算法建立整體段落庫，同時標(biāo)識每個段落的ID。方法描述如下：

輸入 文章名（擴展名為doc）

輸出 段落集paraList

Begin

新建編輯樣本輸入流命名in，構(gòu)建HWPFDocument類對象doc；

定義length，表示文章字數(shù)；

定義paraList存儲自然段的鏈表；

定義paracont 自然段內(nèi)容；

FOR i 0 to length-1 by 1 do //當(dāng)定義變量i小于文章總字數(shù)時進入該循環(huán)

Range（i，i+1，doc）；//定義讀取范圍

CharacterRun cr = range.getCharacterRun（0）； //定義掃描字符變量cr，range表示掃描范圍

char c； //用于獲取下一個讀取的字符；

IF c為換行符

paracont+”

”；

將paracont插入paraList以更新自然段鏈表paraList；

清空paracont ；

ENDIF

END

返回整合后的paraList；

END

預(yù)處理的基本思想：在含有n個編輯段落的編輯樣本中，通過現(xiàn)有HWPFDocument類（處理doc文檔）、XWPFDocument類（處理docx文檔）對編輯樣本進行掃描分段，并將段落內(nèi)容插入鏈表內(nèi)，完成每個段落的ID標(biāo)識。

1.2 基于TCP的Websocket共享同步控制

基于Websocket共享同步控制操作的主要對象由客戶端和服務(wù)端構(gòu)成，圖1為協(xié)同控制原理。

1.2.1 共享同步

Map集合類用于存儲鍵值對，其中每個鍵唯一映射一個值。實現(xiàn)共享同步主要依賴兩個不同的Map數(shù)據(jù)結(jié)構(gòu)，分別命名為PassageMap和OnEditMap以示區(qū)別，結(jié)合Map集合類和WebSocket技術(shù)以實現(xiàn)操作意圖的一致性。

定義1 在線編輯用戶隊列。PassageMap將所有編輯樣本與樣本段落隊列聯(lián)系起來，實現(xiàn)從編輯樣本ID到段落隊列的映射。每個段落隊列對應(yīng)一個在線編輯用戶隊列，以表示每個段落對應(yīng)的所有編輯用戶，其結(jié)構(gòu)為：

[PassageMap：：{Map>}]

定義2 正在編輯用戶表。OnEditMap實現(xiàn)從編輯樣本ID到正在編輯文章的映射。每個在線編輯用戶隊列的第一用戶進入正在編輯用戶表，以表示當(dāng)前正在對樣本進行所有用戶的編輯，其結(jié)構(gòu)為：

[OnEditMap：：{Integer，List}]

如果各進程互斥地訪問同一資源，這一資源便稱為臨界資源。將編輯樣本中的每一段都看作一個臨界資源，則協(xié)同工作過程可視為各用戶排隊對臨界資源進行編輯，同時前一用戶的編輯結(jié)果會同步更新至所有在線編輯用戶界面上。

為理解同步控制過程的處理機制，這里定義3種狀態(tài)：

定義3 就緒狀態(tài)。將處于PassageMap隊列中的用戶從第二個起至最后一個用戶的狀態(tài)稱為就緒狀態(tài)。

定義4 執(zhí)行狀態(tài)。將處于OnEditMap中正在編輯的用戶狀態(tài)稱為執(zhí)行狀態(tài)。

每個就緒隊列的第一個用戶加入OnEditMap，且每次都由該用戶對映射段落進行加鎖，其余選擇編輯該段的用戶進入就緒隊列處于就緒狀態(tài)。處于OnEditMap的用戶編輯完成或者超過邏輯時鐘后便退出OnEditMap，由后一處于就緒狀態(tài)的用戶加入OnEditMap，狀態(tài)由就緒狀態(tài)變?yōu)閳?zhí)行狀態(tài)，過程中若有用戶申請編輯該段將排至就緒隊列隊尾，直到就緒隊列用戶全部退出，該段編輯結(jié)束。

定義5 等待狀態(tài)。為解決用戶持續(xù)占用導(dǎo)致其余用戶饑餓的情況，為每個OnEditMap中的用戶添加一個10min的邏輯時鐘（Clock），當(dāng)邏輯時鐘報警后該用戶被提醒并存入另一隊列，該隊列稱為等待隊列，處于該隊列中的用戶狀態(tài)稱為等待狀態(tài)。當(dāng)處于就緒隊列的第二個用戶未能在第一個用戶完成編輯后就進入OnEditMap，亦被加入等待隊列進入等待狀態(tài)。

幾種隊列狀態(tài)轉(zhuǎn)換如圖2所示。

當(dāng)隊列中所有用戶都在編輯其它段落時，需等待排在最前面用戶一定時間后，將第一個用戶排至隊尾再等待下一個用戶，例如當(dāng)[（U1→fP1）∧（U2→wP1）∧（U2→wP1）∧？]，即未找到[Ui∈（Uj→τPi），j∈{1，2，？，m}，i∈{1，2，？，n}]，那么等待[U2]一定時間后將[U2]排至隊尾，再等待[U3]一定時間，依次類推。對應(yīng)用戶都可在等待時間內(nèi)結(jié)束目前編輯任務(wù)，例如正在編輯其它段落的[U2]可在等待時間內(nèi)結(jié)束正在編輯的段落。

用戶結(jié)束編輯后會從相應(yīng)段落的隊列中彈出，同時也會從正在編輯段落的用戶鏈表中移除，并將隊列中的下一位用戶插入正在編輯段落的用戶鏈表，從而在滿足協(xié)同工作一致性的基礎(chǔ)上提高協(xié)同效率。

1.2.2 操作意圖一致性控制

操作轉(zhuǎn)換的基本思想是本地操作立即執(zhí)行，遠程操作經(jīng)過轉(zhuǎn)換之后再執(zhí)行，各個站點按照不同的順序執(zhí)行操作后獲得相同的結(jié)果[16]。但操作轉(zhuǎn)換算法的復(fù)雜度會直接影響到協(xié)同工作效率，本文對基于隱藏/恢復(fù)機制的操作轉(zhuǎn)換方法[13]進行改進，同時引入WebSocket技術(shù)，以避免因算法復(fù)雜度高而造成的協(xié)同效率低下問題?？蛻舳擞糜谏上ⅰ⒖刂茰y試和顯示結(jié)果，服務(wù)端則進行處理和廣播。為此，創(chuàng)建客戶端界面用于承載編寫的數(shù)據(jù)，Websocket用于傳遞客戶端界面與服務(wù)器之間的數(shù)據(jù)[17]，具體處理過程如下：

服務(wù)端：對節(jié)點進行操作，將修改集成到HB（History Block）中并進行廣播。

具體過程如下：①初始化段落標(biāo)記，[Flag[i]=0，][i∈{0，1，？，N}；]②若標(biāo)記未置1，則標(biāo)記更改，[Flag[i]=1，][i∈{0，1，？，N}]，段落進入可編輯狀態(tài)（此時其他用戶處于就緒態(tài)）；③通過WebSocket技術(shù)對在線用戶進行廣播；④編輯結(jié)束，標(biāo)記位置0，[Flag[i]=0，][i∈{0，1，？，N}]，同時保存HB；⑤通過WebSocket技術(shù)對在線用戶進行廣播；⑥下一用戶進入執(zhí)行狀態(tài)，重復(fù)步驟②—步驟⑥。

客戶端：對節(jié)點進行操作，及時獲取WebSocket數(shù)據(jù)，過程如下：①初始化狀態(tài)：段落進入可編輯狀態(tài)；②對段落文字進行修改；③向WebSocket發(fā)送HB消息，接收WebSocket的HB消息。

以下用圖形表示各站點和各節(jié)點的操作，圖6為同一篇共享文章中3個站點的交互過程，以站點2為例：

站點1發(fā)出操作O1/P1，即[U1→eP1]，WebSocket廣播給各站點，各站點幾乎在同一時間段內(nèi)接收到消息，此階段[P1]為臨界資源，站點2對[P2]進行操作，即[U2→eP2]。同理，通過已建立好的WebSocket通道使其它站點接收到此操作。與此同時，站點2可接收由站點1發(fā)來的對[P1]的操作消息，另外站點3發(fā)出[U3→eP1]操作不會對[U2→eP2]有任何影響。當(dāng)[（U3→fP1）∧（U2→fP2）]，站點2上共享文章的顯示處理結(jié)果為{O1，O3，02}。同理，站點1和站點3的運行歷史記錄HB={O1，O3，02}。

2 案例分析

為驗證本文提出的共享同步控制方法（SSCM）的可行性和高效性，以SSCM為基礎(chǔ)設(shè)計了一個原型系統(tǒng)，對本文提出的方法進行測試。團隊共7組學(xué)生參與協(xié)同工作，這7組學(xué)生可根據(jù)自己的偏好對編輯樣本進行修改，并通過協(xié)商達成一致。實驗用的編輯樣本為《團隊簡介》，編輯前樣本界面如圖7所示。

各站點操作為：

站點1：{添加，（“事跡得到新華社、人民網(wǎng)、新華網(wǎng)及中國青年報等多家主流媒體的報道”）}；

站點2：{刪除，（“新華網(wǎng)”）}；

站點3：{修改，（“得到”，“獲得”）}；

站點2：{添加，（“深入引導(dǎo)青年學(xué)生踐行社會主義核心價值觀、增強青年學(xué)子對‘中國夢的認知、理解和實踐。”）}；

站點4：{修改，（“中國青年報”，“中青網(wǎng)”）}

各站點操作順序為：在[T1]時間段內(nèi)，[U1→eP3]、[U1→][T1，UQ3][{U1→（T1，UQ3）}]；在[T2]時間段內(nèi)，[U3，U2，U4][→T2，UQ3]的同時[U2→T2，UQ2]。

即在[T2]時間段內(nèi)，[U2]、[U3]、[U4] 三個操作主體想要編輯第三段[P3]，[（U3，U2，U4）→inUQ3]。與此同時，操作主體[U2]想要編輯第二段[P2]，[U2→inUQ2]。若按傳統(tǒng)的加鎖控制方法，則一個操作主體在一個時間段內(nèi)只能排在一個隊列里，即[U2]無法在[（U1→eP3）∧（U2→wP3）]時間段內(nèi)執(zhí)行操作[U2→eP2]，操作效率會大大降低。但采用SSCM方法后，[U2]在[U2→wP3]時間段內(nèi)可直接執(zhí)行操作[U2→eP2]，若此時[（U1→fP3）∧（U2→eP2）]，則會對操作主體[U2]進行提醒，若[U2]不放棄操作[U2→eP1]，則[U3→eP3]，反之[U2→eP3]，即操作主體可在等待時間內(nèi)對另一段落進行操作。利用此類處理機制，SSCM不僅可以保存操作主體對將要編輯樣本段落的操作，也可觸發(fā)操作主體想要編輯的樣本段落操作，從而實現(xiàn)協(xié)同工作的高效性。

在現(xiàn)有協(xié)同編輯中，若[T1]時間內(nèi)操作主體U1編輯完后，[U2]、[U3]、[U4]同時對某段進行編輯會產(chǎn)生3個沖突點。即[U3]、[U4]無法看到[U2]編輯的結(jié)果、[U2]、[U4]無法看到[U3]編輯的結(jié)果，[U2]、[U3]無法看到[U4]編輯的結(jié)果。在這種搶占式控制下，無疑會擾亂操作主體的思考方向，不利于在動態(tài)編輯中保持所有操作主體的操作意圖一致性。SSCM利用上述共享同步方法可很好地避免此類問題出現(xiàn)，以實現(xiàn)在靜默和動態(tài)下共享編輯樣本的一致性，見圖8、圖9、圖10。

最終得到的一致性編輯樣本見圖10。

同時將多組實驗數(shù)據(jù)與現(xiàn)有協(xié)同編輯在站點數(shù)、沖突數(shù)相同條件下進行對比，實驗結(jié)果如表1所示。

從圖11可以看到，當(dāng)站點數(shù)相同時，沖突數(shù)越大，SCCM方法處理的效果越好。

從以上結(jié)果分析可以看出，本文提出的共享同步控制方法（SSCM）具有較高的可行性和高效性。

3 結(jié)語

本文對協(xié)同工作中并發(fā)控制方法進行了研究，提出了一種基于WebSocket協(xié)議及隱藏/恢復(fù)機制的共享同步控制方法（SSCM），并將協(xié)同編輯過程進行了可視化展示，能夠較好地滿足協(xié)同過程中的因果、結(jié)果及操作意圖的一致性，同時有較強的交互性。該方法是在WebSocket基本原理和3種狀態(tài)間相互轉(zhuǎn)換前提下得到正在執(zhí)行的線性表，可保證不同段并發(fā)操作的獨立性。從另一個角度來說，客戶端上的顯示是通過服務(wù)端不斷廣播數(shù)據(jù)和SSCM方法中操作主體的隊列轉(zhuǎn)換，實現(xiàn)編輯樣本的實時把控和主觀評判，為進一步的協(xié)同作業(yè)提供參考。利用WebSocket的優(yōu)點可以輕松解決客戶端和服務(wù)端之間通道重復(fù)建立問題，使消息傳遞的速度提高，提升各操作主體間的交互性。另外， SSCM中操作主體可對編輯樣本進行選擇操作，從而更好地集結(jié)協(xié)同工作用戶的群體智慧，促進一致性達成，在采用全復(fù)制式體系結(jié)構(gòu)的基礎(chǔ)上實現(xiàn)一致性維護，為協(xié)同工作用戶提供良好的響應(yīng)性。

本文方法存在一些不足：由于方法以段落為節(jié)點，對于段間的操作存在一定的局限性。此外，由于集合本身的限制，使得部分用戶無法立刻對文章段落進行操作，離協(xié)同的完全高效仍有一定距離，這是下一步研究的方向。

參考文獻：

[1] SUN C， ELLIS C. Operational transformation in real-time group editors： issues， algorithms， and achievements[C]. Proceedings of the 1998 ACM conference on Computer supported cooperative work. Seattle，1998：59-68.

[2] GU N， YANG J， ZHANG Q. Consistency maintenance based on the mark retrace technique in groupware systems[C]. 2005 International ACM SIGGROUP Conference on Supporting Group Work， Sanibel Island，2005：264-273.

[3] 何發(fā)智，呂曉，蔡維緯，等. 支持操作意圖一致性的實時協(xié)同編輯算法綜述[J]. 計算機學(xué)報，2017，41（4）：1-28.

[4] MARTIN S，URSO P，WEISS S. Scalable xml collaborative editing with undo （short paper）[C]. 9th Confederated International Conferences on On the Move to Meaningful Internet Systems，2010： 507-514.

[5] LV X，HE F Z，CAI W W，et al. Supporting selective undo of string- wise operations for collaborative editing systems[J]. Futur Gener Comp Syst. 2018 May，82： 41-62.

[6] LV X， HE F， CAI W，et al. A string-wise crdt algorithm for smart and large-scale collaborative editing systems[J]. Advanced Engineering Informatics，2017（33）： 397-409.

[7] 毛啟容，王進峰，詹永照. 相對位置樂觀鎖機制及在協(xié)同編輯中的應(yīng)用[J]. 計算機輔助設(shè)計與圖形學(xué)學(xué)報，2004，16（9）：1307-1312.

[8] LIU J H，WEI G Y，WANG C. Research on concurrency control algorithm for real-time collaborative editing systems[J]. Journal of China Universities of Posts and Telecommunications，2014，21（SUPPL. 1）： 6-11.

[9] SUN D， SUN C， XIA S，et al. Creative conflict resolution in realtime collaborative editing systems[C]. ACM 2012 Conference on Computer Supported Cooperative Work，2012： 1411-1420.

[10] QIU J， WANG C， CUI M. The influence of cognitive conflict on the result of collaborative editing in Wikipedia[J]. Behaviour & Information Technology，2014， 33（12）： 1361-1370.

[11] LV X， LI Y， ANG C. An improved commutative replicated data type for peer to peer collaborative editing. 3rd International conference on machinery[C]. Materials and Information Technology Applications， 2015：390-395.