結(jié)構(gòu)性文檔下基于MCPS2的意圖維護(hù)與undo算法研究

王 丹，朱思征，王山山，高麗萍

1(上海理工大學(xué) 計算中心，上海 200093)

2(上海理工大學(xué) 光電信息與計算機工程學(xué)院，上海 200093)

1 引 言

CSCW[1](計算機支持的協(xié)同工作：Computer Supported Cooperative Work)作為一種新的工作模式，于1989年提出，歷經(jīng)30余年的研究，研發(fā)了大量的協(xié)同編輯算法[2-4]與協(xié)同應(yīng)用或系統(tǒng)[5-8]，為團隊協(xié)作的技術(shù)發(fā)展做出了巨大貢獻(xiàn).但傳統(tǒng)的樂觀協(xié)同控制算法，多是解決多用戶桌面協(xié)同操作的并發(fā)沖突問題，在移動互聯(lián)網(wǎng)迅速發(fā)展、移動設(shè)備與技術(shù)快速迭代的當(dāng)今社會，考慮到工作的即時性與便利性需求，桌面協(xié)同已無法滿足日漸提高的用戶需求.因此，科研人員圍繞移動互聯(lián)網(wǎng)、云計算、云平臺展開了一系列算法基礎(chǔ)[9-12]與移動應(yīng)用[13-15]研究.

移動端協(xié)同領(lǐng)域研究主要解決的問題即如何在面臨動態(tài)網(wǎng)絡(luò)、資源限制、算法效率、文檔模型等各種約束條件下，基于傳統(tǒng)的樂觀控制算法，設(shè)計和重構(gòu)適用于移動終端的并發(fā)控制算法，實現(xiàn)在最大程度上滿足多用戶意愿的同時，保證用戶操作端文檔的一致性，最終研發(fā)適配度高，響應(yīng)性快的移動協(xié)同應(yīng)用.

考慮到移動端在計算能力與存儲能力方面的限制，我們將協(xié)同操作的文檔模型聚焦在結(jié)構(gòu)文檔(文檔的內(nèi)容間具有清晰明確的等級關(guān)系或?qū)哟谓Y(jié)構(gòu))[16]上.首先結(jié)構(gòu)文檔在各行各業(yè)都具備很高的實用性，例如投標(biāo)書、科研文章、專利申請書等有指定格式與結(jié)構(gòu)要求的文本類文檔，html文檔、思維導(dǎo)圖等具有嚴(yán)格層級關(guān)系的專業(yè)性文檔；其次，文本協(xié)同編輯領(lǐng)域的樂觀控制算法研究相對成熟，有強大的理論知識后盾，在之前的研究[16，17]中，通過活躍度計算與判定的沖突消解機制，權(quán)限分配與轉(zhuǎn)移的意圖維護(hù)手段，在一定程度上滿足了多用戶意愿的同時維護(hù)協(xié)作副本的一致性；最后，結(jié)構(gòu)性文檔的抽象化存儲方式，更適用于存儲能力有限的移動終端.

為了進(jìn)一步的完善移動終端下的結(jié)構(gòu)文檔協(xié)同編輯算法的完整性、合理性和高效性，我們在MCPS2算法基礎(chǔ)上改善了操作權(quán)限的配置方式，參考文獻(xiàn)[18，19]中支持Undo/Redo操作的設(shè)計思想增加了 “撤銷”操作類型，并在操作執(zhí)行方面做出了調(diào)整.本文的結(jié)構(gòu)如下：首先回顧MCPS2算法的執(zhí)行流程與并發(fā)控制方法，并給出本文算法中涉及的文檔結(jié)構(gòu)、節(jié)點類型及屬性、操作類型與權(quán)限的基本定義；然后對改進(jìn)算法進(jìn)行詳細(xì)描述；并分析主體算法的復(fù)雜度，并結(jié)合實例闡述算法的整體執(zhí)行流程，驗證其有效性；最后給出總結(jié)，介紹今后的研究方向和重點.

2 相關(guān)工作

1998年Sun[20]在Eliis[1]人提出的CCI(Convergence Causality Intention)一致性模型基礎(chǔ)上加入意愿維護(hù)的標(biāo)準(zhǔn)，其中一致性維護(hù)是驗證算法的準(zhǔn)確性，而意愿維護(hù)的程度是評判算法應(yīng)用性的重要標(biāo)準(zhǔn).在一致性維護(hù)方面，目前樂觀算法大多基于OT[1](Operation Trans-formation)與AST[21](Address Space Transformation)，例如CSOT[11](Cloud Storage Operational Transformation)云存儲操作轉(zhuǎn)換函數(shù)，能夠支持云存儲下文件粒度的實時一致性同步，COT[2]基于上下文的操作轉(zhuǎn)換算法等.基于這些算法，研發(fā)了一系列處理文本、圖像、代碼的協(xié)作應(yīng)用和系統(tǒng)，比如Google Docs(1)Google Docs[EB/OL].http：//docs.google.com/，2015.、Microsoft Office 365(2)Microsoft Office 365[EB/OL].https：//office.live.com/，2016.等支持文檔的協(xié)同編輯系統(tǒng)，Cloud9 IDE(3)Cloud9 IDE[EB/OL].https：//c9.io/，2016.、CoRED[22]等支持java程序協(xié)同開發(fā)的工具，ProcessOn、SketchPad、CSCW-based CAD[4]等支持在線協(xié)同繪圖服務(wù)的平臺.意圖維護(hù)方面，WH Wang[13]等人利用3種共享鎖機制解決語義沖突實現(xiàn)協(xié)同編程，Sun[23]等人提出基于 OT 技術(shù)采用多版本技術(shù)解決 2D 文檔模型下垂直交叉的沖突，維護(hù)了 2D 文檔一致性.以上算法多是在存儲空間、網(wǎng)絡(luò)狀態(tài)良好的樂觀前提下執(zhí)行，當(dāng)前移動網(wǎng)絡(luò)與移動設(shè)備發(fā)展迅速，將樂觀協(xié)同算法適當(dāng)改良和優(yōu)化移植到移動端，勢在必行.

目前基于移動網(wǎng)絡(luò)研發(fā)了部分算法[3，9，14]與應(yīng)用[12，15]，其中首要解決的是移動網(wǎng)絡(luò)不穩(wěn)定的問題.就此問題，Shao等人提出支持異步協(xié)同的算法ABST[3]，解決了網(wǎng)絡(luò)斷聯(lián)后如何處理各協(xié)作站點產(chǎn)生的操作集合.L Gao[24]等人發(fā)現(xiàn)ABST的成功執(zhí)行需要必要前提，并研究提出能夠構(gòu)造此前提的一致性維護(hù)算法，即支持操作續(xù)傳的網(wǎng)絡(luò)3階段一致性維護(hù)算法.其次是解決存儲空間和計算能力有限的問題，目前樂觀算法多用使用全復(fù)制式架構(gòu)[1，2](full replication architecture)，優(yōu)點是本地響應(yīng)速度快，缺點是浪費帶寬資源，占用本地存儲.2016年Huan Huanxia[10]等人提出局部復(fù)制式架構(gòu)(Partial replication based on dependency)，節(jié)約了本地副本存儲空間的同時節(jié)省了副本更新時間，更適合在移動端使用.基于局部復(fù)制原理，我們在之前的文章中提出了適用于移動終端的支持結(jié)構(gòu)文檔操作的MCPS[16]與MCPS2[17]算法，提出了副本監(jiān)聽、活躍度、創(chuàng)始站點等定義，盡可能上滿足多用戶的操作意愿的同時，設(shè)計沖突消解算法實現(xiàn)一致性維護(hù)的目的.出于功能性與應(yīng)用性的考慮，本文基于MCPS2算法，新增了支持Undo操作的處理進(jìn)程，同時改良了刪除機制，利用預(yù)設(shè)權(quán)限提升了協(xié)作效率.

3 準(zhǔn)備工作

3.1 MCPS2算法回顧

如圖1中的標(biāo)題結(jié)構(gòu)文檔，假設(shè)此時有3個用戶Site0、Site1和Site2同時編輯此文檔，用戶創(chuàng)建的節(jié)點序列如下：

圖1 MCPS2 算法舉例

Site0：TC=[DOC]

Site1：TC=[A，A1，B1，B2]

Site2：TC=[B，A2，A21，A22，A23]

由于Site0發(fā)起了此次協(xié)同編輯事件，則DOC.master=Site0，為了清晰描述MCPS2中的核心算法，我們假設(shè)3個用戶僅執(zhí)行了標(biāo)題插入操作，其他標(biāo)題的編輯、刪除與內(nèi)容的編輯操作均不涉及，那么此時標(biāo)題節(jié)點B的屬性是：

B={2，2，DOC，[B1，B2]，data，name，TN，1，[0，0，1]，[0，2，1]，2，null}，其中[0，0，1]代表各協(xié)作站點在該節(jié)點的節(jié)點活躍度(NLV)，表示site2創(chuàng)建節(jié)點B，site0和site1沒有對B執(zhí)行任何操作；[0，2，1]代表各協(xié)作站點在節(jié)點的樹活躍度(TLV)，即各用戶在以B為根節(jié)點的樹中的所有節(jié)點執(zhí)行操作的活躍度總和.

1)活躍度對比解決操作沖突舉例

假設(shè)此時協(xié)作站點發(fā)起兩個操作：

site0：InsertTitle(B，B3，0，data，name)

site1：InsertTitle(B，B3，0，data，name)

首先插入節(jié)點為一級標(biāo)題B節(jié)點的子節(jié)點，兩站點需要先向B節(jié)點的TC即site2發(fā)起編輯請求，假設(shè)site2同意兩站點執(zhí)行此操作，但是此時發(fā)生了插入位置沖突，根據(jù)MCPS2算法，此時先比較兩站點在B節(jié)點的節(jié)點活躍度NLV，因為(B.NLV.site0==0)=(B.NLV.site1==0)，繼續(xù)比較兩站點在B節(jié)點的樹活躍度TLV，(B.TLV.site0==0)<(B.TLV.site1==2)，所以site1插入操作優(yōu)先于site0執(zhí)行，沖突消解后，site0的插入操作調(diào)整為：

site0：InsertTitle(B，B4，0，data，name)

2)master權(quán)限轉(zhuǎn)移

當(dāng)前master為site0，若site0退出協(xié)同編輯，觸發(fā)master權(quán)限轉(zhuǎn)移機制，系統(tǒng)會自動計算各站點在DOC節(jié)點的樹活躍度，活躍度最高站點將繼承master，同時廣播至所有站點，將原master站點創(chuàng)建的節(jié)點TC之修改為新master站點，具體操作如下：

(DOC.TLV.site1==4)<(DOC.TLV.site2==5)

master → site2

master.TCListappend to site2

最后site2.TC=[DOC，B，A2，A21，A22，A23].

MCPS2在活躍度的比對與一致性維護(hù)方面已經(jīng)相對完善，但在master轉(zhuǎn)移和節(jié)點權(quán)限請求效率方面有待于優(yōu)化，并且在結(jié)構(gòu)文檔的協(xié)同編輯下，有必要根據(jù)實際應(yīng)用性調(diào)整已有操作的執(zhí)行方法，同時加入Undo功能，本文算法針對以上幾方面給出解決方案，以下為本文涉及的幾個關(guān)鍵基本定義.

3.2 文檔定義

文檔結(jié)構(gòu)與存儲結(jié)構(gòu)如圖1所示，繼續(xù)沿用MCPS2算法中的定義與解析方法，主副本利用樹形結(jié)構(gòu)存儲，樹中的子父級關(guān)系代表標(biāo)題節(jié)點的層級，這里不做贅述.

3.3 節(jié)點類型定義

在MCPS和MCPS2以及更早的基于局部復(fù)制策略的算法中，大多將節(jié)點類型分為請求節(jié)點、結(jié)構(gòu)父節(jié)點和結(jié)構(gòu)兄弟節(jié)點，在MCPS2算法中，我們將節(jié)點分為兩大類[參考文獻(xiàn)]，包括標(biāo)題節(jié)點(TN：Title-Node)、結(jié)構(gòu)父節(jié)點(SPN：Str-Parent-Node)和結(jié)構(gòu)兄弟節(jié)點(SBN：Str-Brother-Node)的第1類現(xiàn)實節(jié)點；同時提出虛擬標(biāo)題節(jié)點(VTN：Virtual-Title-Node)第2類虛擬節(jié)點，為維護(hù)結(jié)構(gòu)文檔整體樹型結(jié)構(gòu)和本文提出的undo操作和delete的改進(jìn)操作執(zhí)行而存在.具體的節(jié)點使用將在下文中詳解.

3.4 節(jié)點屬性定義

本文提出的算法在MCPS2基本操作上提出了Undo操作，因此在節(jié)點屬性定義中新增Undo操作的歷史序列UHB(Undo History Buffer)，以及節(jié)點操作權(quán)限標(biāo)記PM，為了更好地區(qū)分節(jié)點定義中屬性的主要功能，我們給出圖2中的節(jié)點屬性定義劃分，其中：

圖2 節(jié)點屬性定義

1)基礎(chǔ)屬性：記錄了標(biāo)題節(jié)點的名稱和內(nèi)容，決定了標(biāo)題在結(jié)構(gòu)文檔中的層級和位置；

2)數(shù)據(jù)同步：type和value兩個屬性主要用于協(xié)作站點請求數(shù)據(jù)時，局部復(fù)制后保證文檔樹結(jié)構(gòu)的完整性；

3)沖突消解：對于協(xié)作站點發(fā)起的操作，一旦產(chǎn)生位置或更新等沖突，此時需要對比操作對象上執(zhí)行站點間的節(jié)點活躍度NLV或樹活躍度TLV，調(diào)整操作的執(zhí)行順序或具體屬性，保證最大程度上滿足各協(xié)作用戶的意愿；

4)操作權(quán)限：節(jié)點的創(chuàng)造者與協(xié)作用戶群，是決定在某節(jié)點某協(xié)作用戶是否具備編輯或刪除權(quán)限的主要因素，PM標(biāo)記類型參照文中權(quán)限定義部分；

5)UHB(Undo History Buffer)：是記錄master未發(fā)起文檔合并命令前本地執(zhí)行的歷史操作序列，以執(zhí)行本地的撤銷操作.

3.5 操作定義

在之前的Delete操作中，一旦刪除某標(biāo)題節(jié)點，以該節(jié)點為根節(jié)點的所有節(jié)點將被刪除，為了提升應(yīng)用性，我們對Delete操作進(jìn)行改進(jìn)：“刪除標(biāo)題節(jié)點操作僅刪除該節(jié)點本身，不刪除其子孫節(jié)點”.另外引入undo操作，支持用戶在未響應(yīng)文檔合并命令前撤銷已執(zhí)行的操作.在表1中，我們給出本算法涉及的主要操作，以及執(zhí)行undo后對應(yīng)的操作，具體操作流程在本文第4部分詳細(xì)描述.

表1 操作類型和說明

3.6 權(quán)限定義

在之前的MCPS2算法中，只有在其它協(xié)作站點請求節(jié)點數(shù)據(jù)的時候，才能通過TC節(jié)點和其他CE節(jié)點的仲裁結(jié)果決定是否可以操作此節(jié)點，如圖3所示，在request user發(fā)出請求后需要等待TC user決定是否接受請求，通過后CE users并發(fā)投票(贊成數(shù)大于等于反對接受同步請求，否則不接受)，最后將請求結(jié)果返回給request user.考慮到請求的反饋速度與TC和CE站點操作執(zhí)行的連貫性與執(zhí)行效率，我們?yōu)槲臋n中的節(jié)點引入權(quán)限概念，TC站點可以在創(chuàng)建節(jié)點或編輯過程中為標(biāo)題節(jié)點賦予權(quán)限，優(yōu)化請求站點發(fā)送請求操作到接收執(zhí)行的中間過程，減少等待階段與時間.本算法的節(jié)點操作權(quán)限主要分為以下幾種：

圖3 MCPS2中的Arbitration算法

1)Edit：協(xié)作站點可以直接請求并編輯節(jié)點，但不可刪除節(jié)點；

2)Readonly：協(xié)作站點可以請求同步節(jié)點，但只能查看節(jié)點內(nèi)容，不可編輯；

3)Delete：非TC的協(xié)作站點可以請求編輯或刪除節(jié)點；

4)Locked：CE用戶總數(shù)超過系統(tǒng)默認(rèn)最大協(xié)同用戶量或TC設(shè)置的最大協(xié)同用戶量時Edit權(quán)限自動鎖定，轉(zhuǎn)為Readonly；

5)Arbitrated：默認(rèn)權(quán)限，在TC站點未賦予節(jié)點任何權(quán)限時使用，與MCPS2中的請求節(jié)點方式相同，需要向TC與CE站點申請編輯權(quán)限，具體流程如圖3.

4 MCPS2算法改進(jìn)

4.1 節(jié)點權(quán)限控制

當(dāng)?shù)?次創(chuàng)建結(jié)構(gòu)文檔、站點新增標(biāo)題節(jié)點或協(xié)作用戶在協(xié)作過程中修改自身創(chuàng)建的節(jié)點的權(quán)限時時觸發(fā)此事件.

算法1.ConstructDoc(Doc)：Str-Doc

輸入：[N]/*節(jié)點集*/

輸出：Str-Doc

1.Forn 0 to[N].lengthDo

2. n.TC executes PM-control(n of[N]，PM)

3. n.PM←PM

4.Ifn is new nodethen/*提升傳輸效率*/

5. broadcast n to master

6.Else

7. broadcast n.PM to master

8.Endif

9.Endfor

通過權(quán)限控制算法，為單個節(jié)點賦予操作權(quán)限，權(quán)限包括文中3.6小節(jié)介紹的5種，其中默認(rèn)權(quán)限為Arbitrated，權(quán)限間可由節(jié)點的TC用戶任意轉(zhuǎn)換，詳細(xì)算法如下：

算法2.PM-Control(n，PM)

1.IfPM==null ‖“Arbitrated”then

2. Waiting for n.TC && n.CE vote

3.Elseif PM==“Locked”then

4. n.TCInputmax length of n.CE

5.ElseifPM==“Readonly”then

6. n.CE.length←0

7.ElseifPM==”Edit”then

8. n.CE cannot delete n

9.ElseifPM==”Delete”then

10. n.CE can edit n

11.Endif

4.2 UHB輸入輸出

UHB的存儲方式類似于HB的存儲，區(qū)別在于需要區(qū)分已廣播和未廣播操作，存儲除Apeend()的其他類型操作，undo操作時按照先入后出的原則，依次轉(zhuǎn)換操作屬性恢復(fù)操作執(zhí)行前的文檔狀態(tài).

算法3.UHB-In(O)

1. Local operation O is executed

2.While(O !=‘Append’)then

3.IfUHB.length < max(UHB.length)then

4. UHB.append(O)

5.Else

6. Remove(UHB[0])

7. Array index of UBH forward 1 step

8. UHB.append(O)

9.Endif

10.Endwhile

算法4.UHB-Out(O)

1.IfO exist in UHBthen

2. id ← O.id

3.IfO==“InsertTitle”‖“InsertTitleBefore”then

4. execute Delete(id，site)

5.Endif

6.IfO==“UpdateName”then

7. oldName ← O.newName

8. newName ← O.oldName

9. execute UpdateName(id，newName，oldName)

10.Endif

11.IfO==“Delete”then

12. execute Undo-Delete(id，site)

13.Endif

14.IfO had been broadcastedthen

15. Broadcast Undo(O)

16.Else

17. Stop Broadcast O

18.Endif

19.Endif

4.3 Delete與Undo-delete的執(zhí)行

與之前文章不同的是，delete操作執(zhí)行并不會將刪除節(jié)點的子孫節(jié)點全部刪除，而是先隱藏此節(jié)點，將子孫節(jié)點暫時繼承給兄節(jié)點，一旦刪除操作被撤銷，將恢復(fù)節(jié)點并恢復(fù)其子孫節(jié)點，否則在合并文檔操作執(zhí)行后，UHB清空，節(jié)點永久被刪除.

算法5.Delete(id，site)

1.Ifn.children !=nullthen

2. pbro ← n.prev()

3. nbro ← n.next()

4. children ← n.children()

5. parent ← n.parent()

6.Ifpbro !=nullthen

7. pbro.children.Append(children)

8.Elseifpbro==null && nbro !=nullthen

9. Nbro.children.Prepend(children)

10.Else

11. parent.children.Append(children)

12.Endif

13.Endif

14. n.type ← VTN

15. UHB.In(ODelete)

算法6.Undo-Delete(id，site)

1. n.type ← TN

2. recover n.children()

3. n.prev.children.remove(n.children())

4. UHB.In(OInsert)

4.4 undo-insert的執(zhí)行

插入操作分為InsertTitleBefore和InsertTitle兩種，因為undo操作執(zhí)行的為上一步操作，所有任意的insert操作在執(zhí)行后，插入的節(jié)點都不會存在子孫節(jié)點，所以撤銷insert操作后本地將執(zhí)行對應(yīng)的delete操作，具體流程與算法5一致.

4.5 UHB清空UHB-destroy

一旦任意站點發(fā)起文檔合并請求，并合并成功，所有協(xié)作站點的UHB將被清空，即用戶將不可撤回文檔合并前執(zhí)行的所有操作，其中所有delete操作的節(jié)點狀態(tài)將由隱藏轉(zhuǎn)變?yōu)閺氐讋h除.

算法7.UHB-destroy()

1.Whileperforming merge()then

2.Forn 0 to UHB.lengthDo

3.IfUHB[n]==‘Delete’then

4. Remove UHB[n].node from Doc

5.Endif

6.Endfor

7. Clear UHB

8.Endwhile

4.6 master轉(zhuǎn)移

MCPS2算法中忽略了多站點文檔活躍度相同的情況，在本文中我們對此算法適當(dāng)改進(jìn).與節(jié)點編輯權(quán)限預(yù)設(shè)的方法類似，master同樣可以設(shè)置自己的“繼承者”，若無繼承的master，則比對請求副本率超過P(自定義)的協(xié)作站點的文檔操作活躍度；活躍度相同時判定站點是否發(fā)起過文檔合并請求，若有則請求最近者為master，若沒有則比對站點優(yōu)先級，優(yōu)先級高者勝任.

算法8.masterTrans()

1.Whilemaster is off-linethen

2.Ifthe successor of master exsitthen

3. master ← successor

4.else

5.forn 0 to sites.lengthdo

6.Ifsites[n].copy.propotion >=Pthen

7. M.Append(site[n])

8.Endif

9.Endfor

10.IfM.length >=1then

11. Mmax ← Max(M.strDoc.TLV)

12.IfMmax.length > 1then

13. Top priority sites of Mmax ← master

14.Else

15. Mmax[0]← master

16.Endif

17.Else

18. Execute masterChange()of MCPS2

19.Endif

20.Endif

21.Endwhile

本文要求副本占比率需超過30%，計算方式如下，假設(shè)Siten站點結(jié)構(gòu)文檔副本中標(biāo)題節(jié)點總數(shù)為TNSum，結(jié)構(gòu)節(jié)點總數(shù)為SNsum，主副本節(jié)點總數(shù)為Str-Doc.Nsum，那么副本占比率PSiten為：

PSiten=(TNsum×Pt+SNsum×Ps)÷Str-Doc.Nsum×100%

其中Pt代表標(biāo)題節(jié)點占副本權(quán)重，Ps代表結(jié)構(gòu)節(jié)點占副本權(quán)重(根據(jù)實際情況賦值)，本算法Pt設(shè)定值為0.8，Ps設(shè)定值為0.2.

5 復(fù)雜度分析

本算法構(gòu)建結(jié)構(gòu)文檔主要分為3種情況：

1)結(jié)構(gòu)文檔初始化，與MCPS2相比加入了預(yù)設(shè)權(quán)限的功能，假設(shè)初始化涉及的標(biāo)題節(jié)點數(shù)量為n，預(yù)設(shè)權(quán)限節(jié)點個數(shù)為m，且m<=n(站點若無預(yù)設(shè)操作，權(quán)限為默認(rèn)值)，初始化時間復(fù)雜度為O(n+m)，最壞情況下時間復(fù)雜度為O(n)；

2)站點新增標(biāo)題節(jié)點，僅涉及單個節(jié)點TC、CE與權(quán)限賦值操作，所以時間復(fù)雜度為O(1)；

3)TC站點修改節(jié)點權(quán)限，每修改一個節(jié)點都會觸發(fā)初始化進(jìn)程，因此時間復(fù)雜度也為O(1).

最后，在提供節(jié)點預(yù)設(shè)權(quán)限功能情況下初始化結(jié)構(gòu)文檔的綜合時間復(fù)雜度為O(n)，與MCPS2中結(jié)構(gòu)文檔初始化相比，時間復(fù)雜度不變，功能得到優(yōu)化.

在MCPS2算法中需要考慮仲裁延遲時間，假設(shè)在最差的環(huán)境下，達(dá)到S個站點協(xié)作上限，請求節(jié)點操作權(quán)限的時間復(fù)雜度為O(S)，并且存在n.CE.length *delayTimes(delayTimes為可等待請求結(jié)果的最大延遲時間)時長的而延遲.本文算法給出節(jié)點預(yù)設(shè)編輯權(quán)限后，默認(rèn)狀態(tài)下請求方式同MCPS2；非默認(rèn)狀態(tài)下，協(xié)作站點在請求節(jié)點時無需向TC站點發(fā)出任何請求，僅根據(jù)該節(jié)點已設(shè)置的權(quán)限查看或操作節(jié)點，因此不存在等待延遲，同時優(yōu)化了時間復(fù)雜度為O(1).

本文中對master轉(zhuǎn)移操作流程進(jìn)行的優(yōu)化，加入了繼承master，同時在master選取上優(yōu)先考慮請求副本率與請求合并文檔時間點，替代原有僅考慮站點活躍度的選取規(guī)則.MCPS2中master轉(zhuǎn)移的復(fù)雜度取決于協(xié)作站點個數(shù)T，為O(T)，本算法中在設(shè)置繼承master時時間復(fù)雜度為最優(yōu)O(1)，最差情況下，所有協(xié)作站點請求副本率滿足條件，且活躍度相同，最后需要比較優(yōu)先級，則時間復(fù)雜度為O(T)+O(T2)=O(T2)，即本算法最優(yōu)狀態(tài)下時間復(fù)雜度

另外，本算法提供undo功能，任意操作在執(zhí)行后都將被記錄在UHB中，即UHB-In操作，假設(shè)UHB最大長度為L，存儲空間足夠情況下追加已執(zhí)行操作的時間復(fù)雜度為O(1)，空間達(dá)到上限時，將刪除頭部前移已有操作，時間復(fù)雜度為O(L)；同樣任意操作在Undo后將從UHB中移除，即UHB-Out操作，操作為選擇和線性執(zhí)行，時間復(fù)雜度為O(1).

6 實例說明

如圖4所示，M1、M2和M3站點執(zhí)行部分操作后的結(jié)構(gòu)文檔存儲狀態(tài)，及各站點在各節(jié)點對應(yīng)的節(jié)點與樹活躍度情況(如表2).圖4中，M1為master，每個協(xié)作站點作為TC的節(jié)點都被賦予了預(yù)設(shè)權(quán)限，標(biāo)題節(jié)點(TN)、結(jié)構(gòu)節(jié)點(SN)與虛擬標(biāo)題節(jié)點(VTN)通過不同的風(fēng)格顯示.

圖4 協(xié)作站點結(jié)構(gòu)文檔存儲初始狀態(tài)

表2 協(xié)作站點初始活躍度

在文檔初始狀態(tài)下我們按流程執(zhí)行圖5中的所有操作，操作內(nèi)容如下：

圖5 操作傳播流程

O1=UpdateName(n5，newName，oldName，M2)

O2=InsertTile(n8，n10，M3，data，name)

O3=Delete(n1，M3)

O4=Undo(O3，M1)

O5=Delete(n5，M2)

Request(n6)：站點M2請求節(jié)點n6，圖4中所示，n6節(jié)點的TC站點為M1且未被賦予權(quán)限，默認(rèn)為Arbitrated，需要經(jīng)過該節(jié)點的CE節(jié)點集體仲裁通過后才可獲取該節(jié)點，仲裁流程參考文獻(xiàn)[24].

Request(n4)：節(jié)點n4的TC站點為M2，權(quán)限為locked，編輯上限為2，當(dāng)M3請求n4時，CE已滿，但仍將n4的完整內(nèi)容返回給M3，但僅具備Readonly權(quán)限，一旦任意協(xié)作站點推出，釋放資源，權(quán)限轉(zhuǎn)變?yōu)長ocked.

Execute(O1，O2，O3)：M2執(zhí)行O1，修改n5標(biāo)題內(nèi)容，不改變樹結(jié)構(gòu)，執(zhí)行后廣播至其他協(xié)作站點；M3執(zhí)行O2，為n8追加孩子節(jié)點n10后廣播至其他站點，M2站點接收后由于局部副本中未請求n8，所以操作無需執(zhí)行.M1執(zhí)行O3，首先n1的編輯權(quán)限可刪除，本文算法對刪除操作的執(zhí)行進(jìn)行了改良，在最近一次合并文檔前，所有刪除節(jié)點只在編輯器中隱藏，如圖6所示，O3操作的執(zhí)行步驟為：①查找n1是否有前一個兄弟節(jié)點，結(jié)果為不存在；②查找n1是否有后一個兄弟節(jié)點，結(jié)果為n2；③將n1的孩子節(jié)點追加到n2的孩子節(jié)點前；④n1節(jié)點類型轉(zhuǎn)換為虛擬標(biāo)題節(jié)點，在編輯器中隱藏；⑤操作記錄到UHB中，同時將操作O3廣播至其他站點.此時各站點的UHB狀態(tài)如下：

圖6 M1刪除n1執(zhí)行流程

M1.UHB=M3.UHB=[O1，O2，O3]；M2.UHB=[O1，O3]；

Execute(O4)：M1撤銷上一步操作，即O3，首先判斷是否已執(zhí)行過文檔合并操作，沒有則判斷上一步操作的類型，類型為Delete，將n1的類型由虛擬標(biāo)題節(jié)點轉(zhuǎn)換為標(biāo)題節(jié)點，恢復(fù)n1的子孫節(jié)點.

Execute(O5)：參考O3的執(zhí)行，n5為葉節(jié)點，且即不存在前一個兄弟節(jié)點也不存在后一個兄弟節(jié)點，可直接轉(zhuǎn)換為虛擬標(biāo)題節(jié)點.

Merge(Str-Doc)：M3向master站點(M1)發(fā)起合并文檔請求，M1接收后同意合并，合并流程詳見MCPS2[24]中的merge算法.合并后向其他站點發(fā)送最新合并節(jié)點內(nèi)容同時觸發(fā)UHB-destroy進(jìn)程：各站點依次清除本地UHB中的操作；若操作為刪除操作，則將該節(jié)點在后臺中徹底刪除，不可undo恢復(fù).

如圖7所示為3站點執(zhí)行上述操作后最終結(jié)構(gòu)副本狀態(tài)，為了簡化圖像，同時體現(xiàn)局部復(fù)制結(jié)構(gòu)不變的特點，我們將3站點的副本合并在一個結(jié)構(gòu)存儲圖像中，其中虛線部分為M2：Str-Doc.copy=[n1，n2，‘n3’，n4，‘n9’]，整體為M3：Str-Doc.copy=[n1，‘n2’，n3，‘n4’，‘n6’，n7，n8，n9，n10]，M1(master)：Str-Doc=[n1，n2，n3，n4，n6，n7，n8，n9，n10]，各站點局部與主副本結(jié)構(gòu)一致.

圖7 最終副本狀態(tài)

master轉(zhuǎn)移：假設(shè)M1站點退出協(xié)同編輯工作，且沒有預(yù)設(shè)“繼承者”，master的選取方式如下：第1步判斷各站點的本地副本占比率是否超過設(shè)定值P=30%，計算得PM3(68%)>PM2(36%)>P，站點M2和M3均符合篩選條件；第2步對比兩站點在結(jié)構(gòu)文檔的操作活躍度，在表2初始活躍度的基礎(chǔ)上，我們執(zhí)行前幾步操作后更新部分活躍度值，最終M2.DOC.TLV=11，M3.DOC.TLV=17，活躍度值高者繼承master，則M1站點退出后由M3作為下一任master，并在第一時刻發(fā)起文檔合并.若在第2步M2和M3文檔操作活躍度相同，則篩選其中最近發(fā)起文檔合并的站點，即3.

7 總結(jié)及展望

移動互聯(lián)網(wǎng)時代的快速發(fā)展，時刻影響著我們的工作和生活，在強調(diào)高效、快速理念的今天，移動辦公、協(xié)同辦公或?qū)⒊蔀槲磥砩鐣闹饕k公模式.CSCW這一概念的提出，加速了協(xié)同領(lǐng)域研究的發(fā)展.目前，樂觀狀態(tài)下的協(xié)同操作并發(fā)控制無論在算法或是應(yīng)用方面涌現(xiàn)了大量成果，而移動網(wǎng)絡(luò)與移動終端方面的研究與之相比還遠(yuǎn)遠(yuǎn)不夠.考慮到移動網(wǎng)絡(luò)的動態(tài)性，移動設(shè)備的存儲、計算能力等方面的限制，我們將協(xié)作文檔模型聚焦在結(jié)構(gòu)文檔上，通過設(shè)計網(wǎng)絡(luò)連接模式，設(shè)置用戶權(quán)限、節(jié)點權(quán)限，計算和比對活躍度等降低網(wǎng)絡(luò)變化對協(xié)同工作的影響，并在最大程度上滿足多用戶操作意愿；另外，為了匹配結(jié)構(gòu)文檔的特性，提升算法的實用性，改善刪除操作的執(zhí)行方式，加入支持undo功能的一系列控制算法，最終提升結(jié)構(gòu)文檔在移動網(wǎng)絡(luò)下的協(xié)同編輯工作意義.

今后的研究方向主要包括以下幾點：

1)將標(biāo)題粒度的文本結(jié)構(gòu)文檔并發(fā)控制算法研究擴展至其他粒度，如具備層次結(jié)構(gòu)的表格、圖像[4]等；

2)在undo的基礎(chǔ)上，支持任意redo[18，19]操作功能；

3)結(jié)合MCPS2與本文算法，設(shè)計一款支持結(jié)構(gòu)文檔協(xié)同操作的APP或小程序.