支持操作續(xù)傳的網(wǎng)絡(luò)三階段一致性維護(hù)研究

王 丹,高麗萍,朱思征

1(上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院,上海 200093) 2(復(fù)旦大學(xué) 上海市數(shù)據(jù)科學(xué)重點(diǎn)實(shí)驗(yàn)室,上海 200093) 3(上海理工大學(xué) 計(jì)算中心,上海 200093)

1 引 言

計(jì)算機(jī)產(chǎn)業(yè)是當(dāng)今社會(huì)發(fā)展速度最為迅猛的產(chǎn)業(yè)之一,并日益影響著我們的日常生活與工作.隨著全球化、信息化的普及,為了提高工作效率,諸多領(lǐng)域采用分布式作業(yè),使員工們可以跨平臺(tái)、跨區(qū)域合作.而合作的方式,也隨著工作量的增大,從個(gè)人負(fù)責(zé)整體中的部分獨(dú)立模塊,通過合并實(shí)現(xiàn)合作,逐步發(fā)展為多人、多地域甚至實(shí)時(shí)的負(fù)責(zé)不同或相同模塊任務(wù)的合作方式.因此,群件系統(tǒng)、協(xié)同計(jì)算等一系列支持協(xié)作需求的產(chǎn)物應(yīng)運(yùn)而生.而在20世紀(jì)80年代依瑞·格里夫和保爾·喀什曼提出了計(jì)算機(jī)支持的協(xié)同工作(Computer Supported Cooperative Work,CSCW)概念[1-3].

在協(xié)同工作領(lǐng)域,實(shí)時(shí)群組編輯器是最為常用的協(xié)同工具之一.主要通過聯(lián)通網(wǎng)絡(luò)和適當(dāng)?shù)臎_突處理,使多用戶能夠?qū)崟r(shí)編輯同一文件對(duì)象,并最終得到狀態(tài)一致的文件.為了提高客戶端響應(yīng)速度和協(xié)作效率,全復(fù)制式架構(gòu)[3-5]和部分復(fù)制式架構(gòu)[6]相繼被提出,并將操作劃分為本地和遠(yuǎn)程兩類,與此同時(shí)涌現(xiàn)出諸多基于此架構(gòu)的沖突消解算法和應(yīng)用.

我們常用的較為成熟的沖突消解方法有OT(Operation Transformation)[7]和AST(Address Space Transformation)[4].但這兩種方法對(duì)網(wǎng)絡(luò)的聯(lián)通性要求較高,必須保證在良好的網(wǎng)絡(luò)狀態(tài)下,遠(yuǎn)程操作能夠完整的被接收和執(zhí)行.隨著移動(dòng)互聯(lián)時(shí)代的到來,各種移動(dòng)設(shè)備層出不窮,人們也將各類工作“搬運(yùn)”到移動(dòng)應(yīng)用上來,而移動(dòng)網(wǎng)絡(luò)的不穩(wěn)定性、易受干擾性,恰恰違背了一致性維護(hù)算法的必要前提.如何將一致性維護(hù)算法進(jìn)行整合,從而適應(yīng)移動(dòng)終端,最終提升協(xié)作的便利性和平臺(tái)多元化,是本研究任務(wù)的核心.

在文獻(xiàn)[8]中,我們初步提出一種支持?jǐn)嗑W(wǎng)狀態(tài)的移動(dòng)網(wǎng)絡(luò)協(xié)同副本一致性維護(hù)算法,并將網(wǎng)絡(luò)狀態(tài)劃分為斷網(wǎng)前、斷網(wǎng)后、聯(lián)網(wǎng)后三階段,提出使用游標(biāo)與網(wǎng)絡(luò)狀態(tài)屬性標(biāo)記文檔狀態(tài)和網(wǎng)絡(luò)狀態(tài),在不同網(wǎng)絡(luò)狀態(tài)環(huán)境下切換對(duì)應(yīng)處理進(jìn)程,最終為ABST算法的準(zhǔn)確執(zhí)行構(gòu)造協(xié)同站點(diǎn)間副本狀態(tài)一致這一必要條件.但該算法還只是單純針對(duì)兩個(gè)移動(dòng)端之間的操作進(jìn)行處理,若客戶端和操作數(shù)量增大,勢(shì)必會(huì)產(chǎn)生效率低、準(zhǔn)確性差、對(duì)移動(dòng)設(shè)備軟硬件要求過高等一系列的問題.因此,本文主要研究在不穩(wěn)定的網(wǎng)絡(luò)狀態(tài)下,如何高效準(zhǔn)確的實(shí)現(xiàn)多用戶協(xié)同工作.并使用中央處理器作為操作轉(zhuǎn)播媒介,同樣將網(wǎng)絡(luò)狀態(tài)劃分為三類,在之前算法的基礎(chǔ)之上進(jìn)行改進(jìn)并移植到服務(wù)器端.

本文的結(jié)構(gòu)如下:首先回顧[8]中的不穩(wěn)定網(wǎng)絡(luò)環(huán)境下的一致性維護(hù)算法,并分析其潛在的執(zhí)行效率、準(zhǔn)確性問題,針對(duì)本文涉及的算法對(duì)客戶端、服務(wù)器進(jìn)行設(shè)置;隨后詳細(xì)介紹本文提出的ORT算法,在不同網(wǎng)絡(luò)狀態(tài)下設(shè)計(jì)服務(wù)器端處理過程;然后對(duì)ORT算法的時(shí)空效率進(jìn)行分析;并基于開源文本編輯工具包UEditor,開發(fā)基于web的實(shí)時(shí)協(xié)同編輯系統(tǒng)Co-Editor,對(duì)ORT算法的準(zhǔn)確性進(jìn)行驗(yàn)證;最后針對(duì)本文提出后續(xù)的主要研究?jī)?nèi)容.

2 相關(guān)工作

實(shí)時(shí)協(xié)同領(lǐng)域的研究日漸成熟,并產(chǎn)生了大量的創(chuàng)新理論與實(shí)踐開發(fā)工具.其中并發(fā)控制技術(shù)是實(shí)時(shí)協(xié)同研究領(lǐng)域的難點(diǎn)之一,該技術(shù)主要包括兩點(diǎn):一致性維護(hù)與沖突消解.為了解決一致性維護(hù)問題,1989年Eliis[1]等人首次提出操作轉(zhuǎn)換OT[7]概念,并研發(fā)dOPT(distributed Operational Transformation)算法構(gòu)建Grove協(xié)同編輯系統(tǒng),初步建立一套一致性模型.1998年Sun[3]驗(yàn)證了dOPT算法在某些場(chǎng)景下存在協(xié)同站點(diǎn)產(chǎn)生結(jié)果不一致的問題,便在初期一致性模型基礎(chǔ)上加入意圖維護(hù)標(biāo)準(zhǔn),完善為CCI(Convergence,Causality,Intention) 模型,為今后的一致性維護(hù)技術(shù)準(zhǔn)確性驗(yàn)證提供了依據(jù).由此,一系列基于OT思想的一致性維護(hù)算法被提出,諸如對(duì)GOT算法進(jìn)行優(yōu)化的GOTO[3]算法,支持String類型的ABTS[9]算法,適用于移動(dòng)設(shè)備的ABST[10]和ABT[11]等算法.在基于OT思想的一致性維護(hù)算法研究較為成熟階段,科研人員發(fā)現(xiàn)了操作轉(zhuǎn)換潛在的執(zhí)行效率低,轉(zhuǎn)換規(guī)則復(fù)雜等問題.因此,NingGu等人[4]在2005年的一篇文章中提出地址空間轉(zhuǎn)換算法(Address Space Transformation,AST).一致性維護(hù)技術(shù)相對(duì)成熟后,人們把研究重點(diǎn)轉(zhuǎn)向了意愿維護(hù),及沖突消解技術(shù),提出基于協(xié)同感知的沖突預(yù)防策略和沖突發(fā)生之后的檢測(cè)及消解策略.結(jié)合兩種并發(fā)控制技術(shù),研發(fā)出大量適用于PC端的協(xié)同編輯系統(tǒng),如支持產(chǎn)品設(shè)計(jì)的Co-CAD[12]、支持協(xié)同文檔編輯的Codoxware、CoMaya、CoTable等.

如今,人們更傾向于較為便利的移動(dòng)辦公,而我們所了解的并發(fā)控制技術(shù),尤其是一致性維護(hù)技術(shù),均是在樂觀網(wǎng)絡(luò)狀態(tài)(即網(wǎng)絡(luò)狀態(tài)良好,所有操作都會(huì)被完整接收和執(zhí)行)下進(jìn)行研發(fā)的,而移動(dòng)網(wǎng)絡(luò)狀態(tài)不穩(wěn)定恰恰使得大部分現(xiàn)有的一致性維護(hù)算法不適用于移動(dòng)設(shè)備.2010年Shao等人[10]提出一種支持異步協(xié)同的ABST算法,通過合并與分解整合操作序列.但該算法只是對(duì)網(wǎng)絡(luò)狀態(tài)進(jìn)行模糊劃分,重點(diǎn)解決斷網(wǎng)后各協(xié)作站點(diǎn)產(chǎn)生的操作集,在我們之前的研究中[8]發(fā)現(xiàn)了ABST算法準(zhǔn)確執(zhí)行的必要前提:各協(xié)同站點(diǎn)副本的文檔狀態(tài)一致.客觀上來說,這也是其他支持異步協(xié)同算法的必要前提.因此我們?cè)谏弦黄恼轮刑岢隽艘环N能夠?yàn)锳BST算法準(zhǔn)確執(zhí)行構(gòu)造必要前提的一致性維護(hù)算法[8].但該算法僅僅支持兩個(gè)站點(diǎn)間簡(jiǎn)單的協(xié)同工作,通過驗(yàn)證,一旦用戶數(shù)量上漲,客戶端在斷網(wǎng)前的cursor更新和斷網(wǎng)后的本地副本恢復(fù)處理進(jìn)程將產(chǎn)生明顯的延遲.為了解決此問題,我們?cè)诒敬窝芯恐幸胫醒敕?wù)器,以提高客戶端響應(yīng)速度、減輕客戶端工作量.

3 準(zhǔn)備工作

3.1 算法回顧

各站點(diǎn)文檔初始狀態(tài)為””,cursor值為0;

各站點(diǎn)產(chǎn)生的操作:

·Site1:O1=Ins(‘a(chǎn)’,1);O4=Del(‘b’,2);

·Site2:O2=Ins(‘b’,1);O5=Ins(‘d’,3);

·Site3:O3=Ins(‘d’,1);O6=Del(‘e’,3).

圖1 三站點(diǎn)操作示例圖Fig.1 Operationsat three collaborative sites

圖1中T1和T2分別代表兩個(gè)本地站點(diǎn)向遠(yuǎn)程站點(diǎn)發(fā)送本地HB的時(shí)間點(diǎn).在之前的文章中我們以兩個(gè)站點(diǎn)為例,來認(rèn)證移動(dòng)網(wǎng)絡(luò)環(huán)境下一致性維護(hù)算法的準(zhǔn)確性,本文我們以三個(gè)站點(diǎn)為例對(duì)該算法進(jìn)行再次驗(yàn)證.

1.首先分析在T1時(shí)刻各站點(diǎn)的文檔狀態(tài)和時(shí)間戳等基本參數(shù):

Site 1:O1在本地生成并立即執(zhí)行,文檔狀態(tài)更新為“a”,此時(shí)狀態(tài)向量為(1,0,0);隨后O2到達(dá),利用AST算法,將文檔中所有字符標(biāo)記為無效,調(diào)用Range_Scan函數(shù)確認(rèn)字符的插入位置,得到文檔“ab”,狀態(tài)向量更新為(1,1,0);此時(shí)HB1={O1,O2},cursor值不變;

Site 2:O2在本地生成并執(zhí)行后,文檔狀態(tài)轉(zhuǎn)換為“b”,O1到達(dá)通過地址空間轉(zhuǎn)換算法,改變文檔狀態(tài)為“ab”,當(dāng)前的狀態(tài)向量更新為(1,1,0),HB2={O2,O1},cursor值無變化;

Site 3:站點(diǎn)三操作的執(zhí)行順序與site2相同,它的HB3={O2,O1},cursor值不變.

T1時(shí)刻,各個(gè)協(xié)同站點(diǎn)發(fā)送本地HB至遠(yuǎn)程站點(diǎn),但與之前文章中的例子不同的是,之前的文章中涉及的協(xié)同站點(diǎn)數(shù)為兩個(gè),HB的廣播和接受進(jìn)程處理相對(duì)比較簡(jiǎn)單,而本文中采用了三個(gè)協(xié)同站點(diǎn),那么每個(gè)站點(diǎn)將要分別給另外兩個(gè)站點(diǎn)分別發(fā)送HB,同時(shí)也要接收來自兩個(gè)站點(diǎn)的HB,因此HB的對(duì)比以及cursor值的更新將變得更為復(fù)雜.

假設(shè)我們通過循環(huán)使用之前的check()函數(shù),來實(shí)現(xiàn)各個(gè)協(xié)同站點(diǎn)cursor值的更新,以site1為例具體的流程如下:

Site1在T1時(shí)刻接收到分別來自site2和site3的HB,此時(shí)HB1需要選擇與HB2和HB3中的一方進(jìn)行check(),根據(jù)交集最短規(guī)則,選擇兩者中較短的一個(gè),我們選擇HB2,首次對(duì)比HBset為{ O1,O2},cursor值為2;將HBset與HB3進(jìn)行第二次check(),HBset{ O1,O2},cursor仍為2.我們所舉的例子對(duì)應(yīng)的操作數(shù)量較少,情形相對(duì)簡(jiǎn)單,但可以直觀的看出,在有三個(gè)站點(diǎn)的情況下每個(gè)站點(diǎn)在特定時(shí)刻更新cursor時(shí)至少要進(jìn)行2次check(),而整個(gè)協(xié)同工作在該時(shí)刻要進(jìn)行2*3即6次check(),這種方式雖然能解決一致性問題,但效率相對(duì)較差,因此,站點(diǎn)增多導(dǎo)致對(duì)比次數(shù)過多造成的效率降低是本文發(fā)現(xiàn)的第一個(gè)問題.

2.站點(diǎn)的增多,導(dǎo)致協(xié)同工作效率降低的同時(shí),如何保證所有協(xié)同站點(diǎn)間cursor值的一致同樣是重點(diǎn)需要解決的問題.因?yàn)閿嗑W(wǎng)不但會(huì)導(dǎo)致操作的丟失與漏發(fā),同樣會(huì)使HB的傳播任務(wù)中止,從而影響cursor更新操作執(zhí)行數(shù)據(jù)完整性,最終導(dǎo)致各站點(diǎn)在聯(lián)網(wǎng)后恢復(fù)本地副本時(shí)不一致.

為了解決以上問題,我們?cè)趯?shí)際應(yīng)用設(shè)計(jì)中考慮使用服務(wù)器,來集中接收、處理和轉(zhuǎn)發(fā)所有站點(diǎn)產(chǎn)生的操作.并在之前的移動(dòng)網(wǎng)絡(luò)環(huán)境下一致性維護(hù)算法基礎(chǔ)上進(jìn)行改進(jìn),實(shí)現(xiàn)多站點(diǎn)間高效準(zhǔn)確的協(xié)同編輯工作.

3.2 基本操作

對(duì)于操作,我們只考慮插入ins(p,c)和刪除del(p,c)兩個(gè)最原始的操作方式,分別代表在位置p處插入或刪除對(duì)象(字符)c.

3.3 服務(wù)器端設(shè)置

表1 服務(wù)器端基本設(shè)置
Table 1 Basic parameters on the server

符 號(hào) 定 義簡(jiǎn) 要 說 明netListener協(xié)同站點(diǎn)網(wǎng)絡(luò)狀態(tài)監(jiān)聽opInBuffer存儲(chǔ)各站點(diǎn)廣播的操作opOutBuffer存儲(chǔ)轉(zhuǎn)換后可發(fā)送至協(xié)同站點(diǎn)執(zhí)行的操作HBset各站點(diǎn)執(zhí)行過的操作集cursor記錄各站點(diǎn)副本一致最近點(diǎn)opBreakInBuffer存儲(chǔ)斷網(wǎng)站點(diǎn)斷網(wǎng)后其他協(xié)作站點(diǎn)生成的操作opBreakOutBuffer存儲(chǔ)斷網(wǎng)站點(diǎn)斷網(wǎng)后生成的本地操作Timer更新cursor的固定時(shí)間間隔DOC各協(xié)同站點(diǎn)副本備份

如表1所示,服務(wù)器端大致包括客戶端網(wǎng)絡(luò)狀態(tài)監(jiān)聽、若干緩沖區(qū)、協(xié)同站點(diǎn)HB集合HBset和計(jì)時(shí)器Timer等.

為了優(yōu)化查詢效率,我們將服務(wù)器的HBset設(shè)置成有序樹結(jié)構(gòu),即HBset為根節(jié)點(diǎn),各站點(diǎn)標(biāo)識(shí)作為HBset的孩子節(jié)點(diǎn),協(xié)同站點(diǎn)標(biāo)識(shí)按優(yōu)先級(jí)由高到低作為第三層子節(jié)點(diǎn),同一站點(diǎn)生成的操作按照時(shí)間戳由小到大排列作為對(duì)應(yīng)站點(diǎn)節(jié)點(diǎn)的孩子節(jié)點(diǎn)(如圖2所示),需要強(qiáng)調(diào)的是,opOutBuffer只自動(dòng)清除cursor前的操作.

圖2 HBset樹形結(jié)構(gòu)圖Fig.2 Tree model of HBset

4 ORT算法

在本設(shè)計(jì)中,我們將主進(jìn)程功能全部部署在服務(wù)器端,各協(xié)同站點(diǎn)均只負(fù)責(zé)生成和執(zhí)行本地操作、廣播本地操作至服務(wù)器端、執(zhí)行從服務(wù)器接收到的操作,以及在指定時(shí)刻發(fā)送本地HB至服務(wù)器,因此下面我們分別介紹服務(wù)器端在三種網(wǎng)絡(luò)狀態(tài):斷網(wǎng)前(break-before)、斷網(wǎng)后(break-after)和聯(lián)網(wǎng)后(connect-after),分別執(zhí)行的主要處理函數(shù).對(duì)于客戶端,我們?cè)跀嗑W(wǎng)前處理遠(yuǎn)程操作,斷網(wǎng)后除斷網(wǎng)客戶端外的其他協(xié)作客戶端間的互發(fā)操作,聯(lián)網(wǎng)后對(duì)于丟失操作的處理我們均采用AST算法.

4.1 客戶端斷網(wǎng)前-服務(wù)器主進(jìn)程

斷網(wǎng)前,服務(wù)器端主要處理進(jìn)程包括:接收和廣播操作、定時(shí)更新cursor值,并廣播最新cursor至所有協(xié)同站點(diǎn).

過程1．Receive＿Broadcast(Ou，cursor)1． If(FirstuseServer)2． { initialize()；//初始化服務(wù)端基本設(shè)置3． lastTime=CurrentTime()；}4． HBset．sitex．HB．Append(Ou)；5． opInBuffer[Sitex]．Append(Ou)；6． for(i=1touser．count)7． { if(i！=x)8． {opOutBuffer[Sitei]．Append(Sitei．Ou)；}9． }10． Broadcast(opOutBuffer[Sitei]．Ou)TOSitei；11． If(Timer==CurrentTime?LastTime)12． {//各協(xié)作站點(diǎn)發(fā)送本地HB到服務(wù)器HBset中13． ReceiveHBsfromallSites；14． HBset．Append(HBs)；15． Cursor＿Update(HBset，cursor)；16． LastTime=CurrentTime；17． Broadcast(cursor)TOallSites；18． }函數(shù)1：Cursor＿Update(HBset，cursor)1． if(HBsitei．lengthistheminlengthinHBset)2． {HBr=HBsitei；//將最短HB拷貝到HBr3． Length=HBsitei．length；}4． for(mis0toLength?1)5． { userId=HBr[m]．id；6． vector=HBr[m]．v；7． for(nis1touser．count)8． { //與其他協(xié)作站點(diǎn)逐一匹配9． if(userid！=sitei．id)10． {//在HBset樹中查找是否存在操作HBr[m]11． if(HBset．HBsiten．userId．op．vectorexsitsinsiten)12． {posList．Append(indexOf(HBset．HBsiten．userId．op))；13． n++；}14． else15． { break；}16． }17． if(n=user．count?1)18． {m++；}19． else20． {//如果在posList中不存在大于m的操作21． for(jis0toposList．length?1)22． { if(posList[j]>m-1)23． {Length=m+1；//更新Length值24． returnstep5；}25． else26． { break； }27． }28． }}}29． cursor=cursor+m；

4.2 客戶端斷網(wǎng)后-服務(wù)器主進(jìn)程

在協(xié)同工作過程中,如果一旦有用戶斷開網(wǎng)絡(luò)連接,會(huì)造成與服務(wù)器失聯(lián),從而無法接收和發(fā)送操作,這時(shí)服務(wù)器就要進(jìn)行相應(yīng)的處理,為該斷網(wǎng)站點(diǎn)重新聯(lián)網(wǎng)后生成一致性副本做準(zhǔn)備.而斷網(wǎng)站點(diǎn)繼續(xù)生成和執(zhí)行本地操作,并對(duì)斷網(wǎng)后生成的操作進(jìn)行標(biāo)記,也就是在文章[8]中的package(SQ0,SQ1)過程,生成兩個(gè)操作集合SQ0(存儲(chǔ)斷網(wǎng)前cursor后的操作)和SQ1(存儲(chǔ)斷網(wǎng)后的操作).而服務(wù)器端也要對(duì)站點(diǎn)的失聯(lián)狀況進(jìn)行應(yīng)對(duì).

過程2．Break＿Response()1． netListener[i]=1；2． for(nis1touser．count)3． { //對(duì)于網(wǎng)絡(luò)狀態(tài)良好的站點(diǎn)，繼續(xù)通過服務(wù)器與其他站點(diǎn)進(jìn)行協(xié)同工作，但不更新cursor4． if(netListener[n]==0)5． { Receive＿Broadcast(Ou)； }6． else7． { while(receiveoperationOrfromothersites)//Or表示一類遠(yuǎn)程操作8． {Or．net=1；9． opInBuffer[n]．Append(Or)；10． }11． }12． }

通過Break_Response過程對(duì)操作的整合,我們可以從opInBuffer和opOutBuffer中得到兩種操作:一種是在站點(diǎn)i斷網(wǎng)后,其他協(xié)同站點(diǎn)生成的操作,存儲(chǔ)在opInBuffer中,且操作的net值為1;另一種是在站點(diǎn)i斷網(wǎng)前,cursor后廣播已執(zhí)行或廣播丟失或未廣播的操作,分散存儲(chǔ)在opInBuffer和opOutBuffer中,且操作的net值為0.為什么不把opInBuffer中net值為0的操作通過地址空間轉(zhuǎn)換直接整合到opOutBuffer？因?yàn)樵诼?lián)網(wǎng)后的執(zhí)行過程中,首先需要對(duì)opOutBuffer進(jìn)行遍歷,找出未廣播或廣播過程中由于斷網(wǎng)丟失的操作,而opInBuffer中的操作一定是還未廣播的操作,所以為了提高遍歷效率,減少副本恢復(fù)時(shí)間,我們?cè)诒闅v進(jìn)程結(jié)束后立即對(duì)opInBuffer中net=0的操作進(jìn)行轉(zhuǎn)換和廣播至斷網(wǎng)站點(diǎn).

4.3 客戶端聯(lián)網(wǎng)后-服務(wù)器主進(jìn)程

聯(lián)網(wǎng)后服務(wù)器對(duì)各協(xié)作站點(diǎn)副本的主要恢復(fù)操作大致包括

1)檢測(cè)斷網(wǎng)前站點(diǎn)接收過程中是否存在丟失操作,若存在,對(duì)該操作進(jìn)行相應(yīng)轉(zhuǎn)換處理,然后在斷網(wǎng)站點(diǎn)執(zhí)行;

2)檢測(cè)斷網(wǎng)前站點(diǎn)廣播操作至服務(wù)器過程中是否存在丟失操作,若存在,捕捉該操作,并將該丟失操作進(jìn)行轉(zhuǎn)換并廣播到其他協(xié)作站點(diǎn);

3)處理斷網(wǎng)后,各協(xié)作站點(diǎn)產(chǎn)生的操作,最終各站點(diǎn)生成一致性副本.

過程3．Server＿Recover(SQ0，SQ1)1． /?(1)?/2． for(iis0toSQ0．length?1)3． { //將SQ0中的本地操作和遠(yuǎn)程操作區(qū)分開4． if(SQ0[i]．id==n)5． { Larry．Append(SQ0[i])； }6． else7． { Rarry．Append(SQ0[i])； }8． }9． if(Rarry．length==opOutBuffer[n]．length)10． { Cursor＿Update(HBset，cursor)；11． Broadcast(cursor)TOallsites；12． }13． else14． {for(j=0toopOutBuffer[n]．length?1)15． {if(opOutBuffer[n][j]notinRrray)16． { Broadcast(opOutBuffer[n][j])TOsiten； }17． }18． }19． for(k=0toopInBuffer[n]．length?1)20． {//篩選斷網(wǎng)前的操作先執(zhí)行21． if(opInBuffer[n][k]．net==0)22． {opOutBuffer[Siten]．Append(O)；23． Broadcast(O)TOSiten； }24． else25． { opBreakInBuffer[Siten]．Append(opInBuffer[n][k])}26． }

27． /?(2)?/28． for(sis0toLarry．length?1)29． {if(！Larry[s]exsitsinHBset．siten)30． {//如果不存在，證明該操作在斷網(wǎng)時(shí)丟失，重發(fā)31． Broadcast(Larry[s])toothersites； }32． }33． /?(3)?/34． SQ1′=Compressed(SQ1)；35． OpBreakOutBuffer[siten]．Append(SQ1′)；36． Broadcast(Sequence(OpBreakOutBuffer[siten]))toothersites；37． Broadcast(Sequence(OpBreakInBuffer[siten]))tositen；38． ReceiveHBsfromallSites；39． HBset．Append(HBs)；//更新HBset40． Cursor＿Update(HBset，cursor)；41． Broadcast(cursor)TOallSites；

5 算法效率分析

本文將不穩(wěn)定的網(wǎng)絡(luò)狀態(tài)劃分為斷網(wǎng)前、斷網(wǎng)后和聯(lián)網(wǎng)后三部分,同樣在不同的網(wǎng)絡(luò)狀態(tài)下,服務(wù)器端會(huì)自動(dòng)切換不同的處理過程,而協(xié)同客戶端的效率,取決于所使用的一致性維護(hù)算法.下面我們針對(duì)每種網(wǎng)絡(luò)狀態(tài)分析服務(wù)器端處理過程的時(shí)空效率.

斷網(wǎng)前,服務(wù)器的主要處理函數(shù)Receive_Broadcast()負(fù)責(zé)接收和廣播操作到各協(xié)作站點(diǎn),并在特定的時(shí)間間隔通過Cursor_Update()方法更新cursor值.因此,在非更新cursor時(shí)段,服務(wù)器端的收發(fā)操作的時(shí)間復(fù)雜度為O(user.count),user.count為協(xié)同用戶總數(shù);而在更新cursor時(shí)段,服務(wù)器端的時(shí)間復(fù)雜度為O(Length·user.count·h),其中Length是所有協(xié)同站點(diǎn)中最短HB的長(zhǎng)度,由于我們?cè)诜?wù)器端使用樹形結(jié)構(gòu)存儲(chǔ)HBset,因此根據(jù)id和v檢索HBset中的指定操作時(shí),時(shí)間復(fù)雜度為HBset樹的高度h,且h是一個(gè)固定的數(shù)值4,所以總體時(shí)間復(fù)雜度可以簡(jiǎn)化為O(Length·user.count).

斷網(wǎng)后,非斷網(wǎng)站點(diǎn)仍通過服務(wù)器端Receive_Broadcast()互相協(xié)同工作、收發(fā)操作.斷網(wǎng)站點(diǎn)則更改netListener中對(duì)應(yīng)位置的值為1,然后根據(jù)操作net值將操作存放于不同的緩沖區(qū),以上部分的時(shí)間復(fù)雜度取決于用戶總數(shù),為O(user.count).

聯(lián)網(wǎng)后,Server_Recover()函數(shù)對(duì)各協(xié)作站點(diǎn)的副本進(jìn)行一致性處理,大致分為三步:

1)處理斷網(wǎng)前服務(wù)器向站點(diǎn)廣播過程丟失的操作,時(shí)間復(fù)雜度為O(SQ0.length),SQ0為斷網(wǎng)站點(diǎn)HB中cursor位置后net=0的操作集.

2)處理斷網(wǎng)前站點(diǎn)向服務(wù)器廣播過程丟失的操作,復(fù)雜度為O(Larry.length),Larry為SQ0中操作id為斷網(wǎng)站點(diǎn)id的操作集;

3)處理斷網(wǎng)后,各協(xié)作站點(diǎn)產(chǎn)生的操作,主要操作為壓縮操作和cursor更新操作,時(shí)間復(fù)雜度參考斷網(wǎng)前和斷網(wǎng)后.

6 Co-Editor編輯系統(tǒng)

不僅是移動(dòng)網(wǎng)絡(luò)具備不穩(wěn)定的特點(diǎn),使用有線寬帶、無線wifi的終端設(shè)備,同樣存在網(wǎng)絡(luò)斷開的情況,因此,為了驗(yàn)證ORT算法的準(zhǔn)確性和可行性,我們基于web對(duì)開源的UEditor系統(tǒng)進(jìn)行二次開發(fā),研發(fā)Co-Editor協(xié)同編輯系統(tǒng),支持多用戶在不穩(wěn)定的網(wǎng)絡(luò)狀態(tài)下借助瀏覽器共同編輯一個(gè)純文本文檔.

6.1 系統(tǒng)主界面介紹

如下頁圖4所示,是四個(gè)協(xié)同用戶使用Co-Editor系統(tǒng)編輯同一個(gè)文檔的示例.我們的編輯系統(tǒng)利用eclipse、tomcat、CSS和javascript等開發(fā)工具,結(jié)合easyUI框架,將界面大致劃分為四個(gè)功能區(qū)域.左側(cè)為用戶顯示欄目,并顯示各用戶當(dāng)前的網(wǎng)絡(luò)狀態(tài) (Online/Offline); 中部為文本編輯器主體,協(xié)同用戶可直接在其之上編寫文檔(注:本編輯系統(tǒng)只支持純文本文檔編輯,其他功能將在后期擴(kuò)展);右側(cè)為功能欄,用戶可點(diǎn)擊對(duì)應(yīng)按鈕,實(shí)現(xiàn)從服務(wù)器同步主副本到本地,導(dǎo)出頁面文檔至本地,顯示/隱藏功能欄和編輯器能功能;下側(cè)為用戶基本信息顯示欄,顯示用戶ID、用戶名、最后一次從服務(wù)器更新主副本的時(shí)間.

圖3 斷網(wǎng)時(shí)站點(diǎn)3及站點(diǎn)4文檔狀態(tài)Fig.3 State of document at site 3and site 4 when net-broke

6.2 一致性維護(hù)驗(yàn)證

圖3中左下方為站點(diǎn)4,Mary用戶的編輯界面,此時(shí)的文本內(nèi)容為“Hello world”,該站點(diǎn)處于斷網(wǎng)狀態(tài),且在斷網(wǎng)后Mary并未對(duì)文檔進(jìn)行任何更改;右上方站點(diǎn)3的網(wǎng)絡(luò)狀態(tài)良好,文檔為“Hello wor”,同樣在站點(diǎn)4斷網(wǎng)后,站點(diǎn)3也未執(zhí)行任何操作;說明由于站點(diǎn)4的網(wǎng)絡(luò)失聯(lián),站點(diǎn)4未將“l(fā)d“部分對(duì)應(yīng)的操作發(fā)送給協(xié)作站點(diǎn),或發(fā)送過程中由于斷網(wǎng)造成丟失現(xiàn)象,站點(diǎn)3由于不能完整的接收遠(yuǎn)程操作,使得本地文檔狀態(tài)與站點(diǎn)4的不一致,當(dāng)網(wǎng)絡(luò)再次聯(lián)通時(shí),只能夠處理在斷網(wǎng)后各站點(diǎn)產(chǎn)生的操作,最終將導(dǎo)致各站點(diǎn)文本狀態(tài)不一致的后果,破壞了協(xié)同工作的目的.

聯(lián)網(wǎng)后,通過ORT控制算法,對(duì)各協(xié)同站點(diǎn)的本地副本狀態(tài)進(jìn)行一致性恢復(fù),如圖4所示,在Mary重新上線后,斷網(wǎng)中丟失的操作得以重發(fā),并在站點(diǎn)3上執(zhí)行,最終所有站點(diǎn)生成一致性副本“Hello world”.

圖4 聯(lián)網(wǎng)后站點(diǎn)3文檔狀態(tài)Fig.4 Thestate of document at site 3 when net-connected

7 總結(jié)及展望

本文針對(duì)不穩(wěn)定網(wǎng)絡(luò)環(huán)境,提出ORT(支持操作續(xù)傳的網(wǎng)絡(luò)三階段一致性維護(hù)) 算法.在之前支持兩站點(diǎn)協(xié)同工作的研究基礎(chǔ)上,引入服務(wù)器集中處理概念,在減輕客戶端負(fù)載和處理復(fù)雜度的同時(shí),提升協(xié)同工作的整體效率和功能特性.未來的研究工作包括:

1)我們對(duì)UEditor的二次開發(fā)只是基于純文本,而該軟件具備圖形圖像等多種對(duì)象的編輯功能,因此,研發(fā)各類對(duì)象的實(shí)時(shí)協(xié)同編輯功能,前景可觀;

2)本文算法對(duì)網(wǎng)絡(luò)狀態(tài)的劃分尚不夠細(xì)致,考慮引入客戶端、服務(wù)器性能、網(wǎng)絡(luò)覆蓋等可控因素,對(duì)算法進(jìn)行改進(jìn);

3)添加undo/do[14]、update等操作,提高Co-Editor協(xié)同編輯系統(tǒng)的可用性.

[1] Ellis C A,Gibbs S J.Concurrency control in groupware systems [C].Proceedings of the Association for Computing Machinery(ACM)Sigmod International Conference on Management of Data(SICMD),1989:399-407.

[2] Ellis C A,Gibbs S J,Rein G L.Groupware:some issues and experiences [J].Communications of the Association for Computing Machinery(CACM),1991,34(1):39-58.

[3] Sun C Z,Ellis C A.Operational transformation in real-time group editors:issues,algorithms,and achievements[C].Proceedings of the Association for Computing Machinery Conference on Computer Supported Cooperative Work(CSCW),1998:59-68.

[4] Gu N,Yang J M,Zhang Q W.Consistency maintenance based on the mark & retrace technique in groupware systems[C].Proceedings of the International Association for Computing Machinery Sigroup Conference on Supporting Group Work(ACM SIGGROUP),2005:264-273.

[5] Shao B,Li D,Lu T,et al.An operational transformation based synchronization protocol for web 2.0 applications [C].Proceedings of the Association for Computing Machinery Conference on Computer Supported Cooperative Work(CSCW),2011:563-572.

[6] Xia H H,Lu T,Shao B.A partial replication approach for anywhere anytime mobile commenting[C].Proceedings of the 2014thComputer Supported Cooperative Work(CSCW),2014:15-19.

[7] Sun C,Chen D,Jia X.Reversible inclusion and exclusion transformation for string-wise operations in cooperative editing systems[C].Proceedings of the 21st Australasian Computer Science Conference,1997.

[8] Gao Li-ping,Wang Dan,Xiong Nai-xue.Consistency maintenance of collaborative shared documents in unstable network environment[C].Proceedings of the 11st Chinese Conference on Computer Supported Cooperative Work,2016.

[9] Shao B,Li D,Gu N.ABTS:a transformation-based consistency control algorithm for wide-area collaborative applications[C].Proceedings of the International Conference on Collaborative Computing:Networking,Applications and Work Sharing,Los Alamitos:Institute of Electrical and Electronics Engineers(IEEE) Computer Society Press,2009:1-10.

[10] Shao B,Li D,Gu N.A fast operational transformation algorithm for mobile and asynchronous collaboration [J].Institute of Electrical and Electronics Engineers(IEEE) Transaction Parallel and Distributed Systems,2010,21(12):1707-1720.

[11] Li D,Li R.A fast operational transformation algorithm for mobile and asynchronous collaboration [J].An Admissibility-based Operational Transformation Framework for Collaborative Editing Systems,2010,19(1):1-43.

[12] Zheng Y,Shen H F,Sun C Z.Leveraging single-user AutoCAD for collaboration by transparent adaptation [C].Proceedings of the13th International Conference on Computer Supported Cooperative Work in Design,2009:78-83.

[13] Cai Wei-wei,He Fa-zhi,Lv Xiao.An efficient preserving intention operational transformation for real-time collaborative editing [J].Chinese Journal of Computers,2015,38(10):2041-2053.

[14] Yu W,André L,Ignat C L.ACRDT supporting selective undo for collaborative text Editing[C].Proceedings of the Distributed Applications and Interoperable Systems,2015:193-206.

附中文參考文獻(xiàn)：

[13] 蔡維緯,何發(fā)智,呂 曉.一種高效率的實(shí)時(shí)協(xié)同編輯中意圖保持操作轉(zhuǎn)換算法[J].計(jì)算機(jī)學(xué)報(bào),2015,38(10):2041-2053.