移動平臺下的結構性文檔意圖維護算法

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

1(上海理工大學 計算中心,上海 200093)2(上海理工大學 光電信息與計算機工程學院,上海 200093)

1 引 言

計算機產業(yè)的蓬勃發(fā)展,促進和影響著人們的日常工作和生活,網(wǎng)絡的出現(xiàn),讓人們可以跨越地域、跨越文化,實現(xiàn)在線的、實時的交流.然而近年來,各個行業(yè)的工作規(guī)模日益增大,僅靠個人的單打獨斗,很難高效高質量的勝任一項龐大的工作,為此,一種新的工作模式CSCW[1](計算機支持的協(xié)同工作：Computer Supported Cooperative Work)被提出.

協(xié)同工作概念的出現(xiàn),大大改變了人們的工作方式,提高了工作效率,它支持人們在不同的地區(qū),使用不同的設備,在同一時刻參與完成同一項工作.由此,產生了大量的支持協(xié)同工作的應用和系統(tǒng)[2-5],而在協(xié)同過程中伴隨出現(xiàn)了一系列的沖突與一致性問題[2].后來,人們圍繞沖突消解和一致性維護提出和改進了多種算法.一致性維護主要解決各協(xié)作用戶間的本地文檔存在差異的問題,最終使所有協(xié)作端能夠擁有相同的編輯副本.而沖突消解,意在維護每一個協(xié)作用戶的工作意圖.目前一致性維護算法和方法以及系統(tǒng)已經(jīng)設計和開發(fā)的相對成熟,而涉及到意圖維護方面的內容相對較少,在協(xié)同工作中,如何能夠在最大程度上公平公正的維護每一個協(xié)作用戶的意圖,是一件提升協(xié)同工作意義的重要工作.

近年來移動應用技術發(fā)展迅猛,移動設備、平臺、應用層出不窮,傳統(tǒng)的支持PC端的協(xié)同應用和算法也同樣在順應科技發(fā)展的潮流,逐步向移動端移植[6].移植過程中面臨的網(wǎng)絡、存儲、設備差異化等問題,都是亟待解決的關鍵問題.

結構文檔,我們可以簡單理解為文本內容間存在等級結構的文檔[7].例如我們在工作中常用的word文檔編輯模板,標題、表格、圖片等都有嚴格的樣式和層級規(guī)定,其中標題的等級,能夠清晰的體現(xiàn)文檔中內容的結構關系.將結構文檔加入到協(xié)同編輯工作中,利用結構化的方式存儲,一方面能夠將整體沖突細化到局部沖突,提升協(xié)作效率；另一方面,能夠對不同等級的文檔內容賦予編輯權限,盡可能的保證大部分協(xié)作用戶的編輯意愿；再者,結構文檔的存儲方式,更能夠適應移動終端,解決移動設備存儲空間有限的問題.因此,如何在優(yōu)化結構文檔在移動端的存儲方式,如何合理涉及用戶編輯權限,最終提升協(xié)作效率,最大程度上滿足協(xié)作用戶的操作意愿,研究意義重大.

本文的結構如下：首先回顧之前的移動平臺下基于局部復制的結構性文檔協(xié)同編輯沖突消解算法,并針對本文提出的算法對文檔結構、節(jié)點屬性、節(jié)點類型、網(wǎng)絡連接模式等定義；然后給出文檔初始化、仲裁方式、權限轉移等詳細的算法描述；最后對核心算法部分進行復雜度分析,并結合實例梳理算法整體實現(xiàn)流程,驗證其準確性；文章最后,介紹后續(xù)的研究方向和內容.

2 相關工作

1998年Sun[2]在最初的dOPT[1](distributed Operational Transformation)算法中提出的一致性維護模型CCI(Convergence Causality Intention)的基礎上,補充了意愿維護的標準,強調了用戶意愿在協(xié)同工作中的重要性.在維護一致性方面,最具代表性的算法大致分為兩類,基于操作轉換的OT算法(Operation Trans-formation)[1]和基于地址空間轉換的AST算法(Address Space Transformation)[4].至今,圍繞OT和AST技術衍生了眾多并發(fā)控制算法,如GOTO[1]、SCOT4[8]、ABST[9]、TIBOT[10]等.同時這兩類技術也被廣泛應用在協(xié)同應用和系統(tǒng)的開發(fā)中,典型的如支持多用戶協(xié)同編輯的分布式草圖系統(tǒng)SketchPad和支持產品設計的協(xié)同系統(tǒng)Co-CAD[11].在意愿維護方面,針對不同類型的文檔,提出了相應的沖突消解策略,如解決文本意愿沖突的多版本策略[12],和Ignat[13]提出的基于二維圖形編輯的語義沖突消解策略.但這些研究多是基于全復制式架構[2],且站在狀態(tài)樂觀的角度,需保證網(wǎng)絡連續(xù),通訊順暢,存儲空間充足等環(huán)境,一旦文檔規(guī)模變大,操作數(shù)量上漲,網(wǎng)絡出現(xiàn)不穩(wěn)定,缺少良好的應急處理機制,將導致策略失效,協(xié)同工作無法進行.而存儲有限、網(wǎng)絡不穩(wěn)恰恰是移動端的特性所在.針對此問題,2014年Huanhuan Xia[17]等人提出了局部復制式架構,與全復制式架構相比,不僅節(jié)約存儲空間,也節(jié)省了文檔副本的更新時間,更加適用于移動終端；而后,Sun在2016年提出了CSOT[14](Cloud storage Operational Trans-formation)算法,首次將OT的一致性維護能力移植到云存儲共享空間中,實現(xiàn)理想的并發(fā)操作效果合并,為基于云的協(xié)同技術發(fā)展奠定了基礎.

在Huanhuan Xia及Sun的研究基礎上,我們在之前的文章[7]中,提出了移動平臺下基于局部復制的結構性文檔協(xié)同編輯沖突消解算法,簡稱MCPS算法,初步的設計了結構性文檔協(xié)同工作中可能出現(xiàn)的沖突消解算法,并提出了樹活躍度(TLV： Tree liveness)和節(jié)點活躍度(NLV：Node liveness)兩個概念,來動態(tài)的解決操作沖突,一定程度上客觀的維護了協(xié)同用戶的意圖,但整個結構性文檔的協(xié)同編輯設計仍需細化,例如如何控制用戶的加入和退出,不同協(xié)同用戶所具備的權限.在之前的意圖維護算法中,多使用站點優(yōu)先級對比,時間戳對比,版本控制等方法.本文在文獻[7]中提出的活躍度基礎上,更改網(wǎng)絡連接模式,加入了標題和站點master屬性,賦予用戶權限,為了實現(xiàn)用戶即來即走的特性,根據(jù)用戶在共享文檔中的編輯活躍度,設計了合理的權限轉移控制機制,提出了移動平臺下基于用戶活躍度的結構性文檔意圖維護算法,簡稱MCPS2算法.

3 準備工作

3.1 MCPS算法回顧

在之前的文章中[7],我們分析了結構性文檔在移動云平臺下進行協(xié)同編輯時可能產生的一系列沖突,并對每種沖突設計了對應的消解方案,以解決協(xié)同編輯過程中各協(xié)作站點文檔副本不一致的問題.同時,我們將各種沖突消解策略整合在一起,設計了一款基于局部復制的結構性文檔協(xié)同編輯沖突消解算法,簡稱MCPS算法.該算法中主要包括表1中的幾種沖突類型：

圖1 結構文檔StrTree和骨架樹Fig.1 A figure introduces the structured document tree (StrTree) and skeleton tree

表1 沖突類型和說明Table 1 Illustration of conflict types

在圖1中,我們給出了MCPS算法設計的節(jié)點屬性中涉及的基本定義,其中虛線框中包含的節(jié)點集,也就是StrTree的子樹,我們稱它為協(xié)作站點可向服務器請求的骨架樹(skeleton tree),詳細的局部復制式架構副本請求策略可以參考文獻[7].為了在最大程度上維護協(xié)作用戶的意愿,我們提出了節(jié)點活躍度(NLV： Node liveness)和樹活躍度(TLV： Tree liveness)的定義,動態(tài)記錄和更新每個協(xié)作用戶在各個標題節(jié)點和子樹上的編輯活躍度,在產生編輯沖突時,對比沖突站點的活躍度,決定操作的優(yōu)先執(zhí)行順序,相比以往的通過判定站點的優(yōu)先級,時間戳等人為規(guī)定操作執(zhí)行順序的方式,此方法更為客觀公平.本文將在之前提出的MCPS算法基礎上,對通信方式、協(xié)同編輯流程、用戶權限、文檔定義、意愿維護等方面進行改進和細化,以提升算法在系統(tǒng)開發(fā)中的可用性.

3.2 網(wǎng)絡連接模式

本文未沿用MCPS算法中以中央服務器為操作處理和數(shù)據(jù)轉發(fā)的協(xié)同交互方式,而是選擇使用P2P的連接方式,原因在于協(xié)同客戶端間的傳輸粒度多為操作、操作集、標題集或部分文檔,不涉及大文件的頻繁傳輸,目前國內市場的移動終端應用技術發(fā)展迅猛,且網(wǎng)絡帶寬同時也在不斷提升,先進的軟硬件和網(wǎng)絡現(xiàn)狀,能夠支撐P2P的網(wǎng)絡連接模式.再者,P2P能使網(wǎng)絡上的溝通變得容易,實現(xiàn)更為直接的共享和交互,在協(xié)同工作和分布計算方面大有用途.

圖2 協(xié)作站點P2P連接方式Fig.2 P2P connection of collaborative sites

圖2中,我們?yōu)槊總€協(xié)作團隊,設置了一位master,協(xié)同工作開始時,master由結構文檔協(xié)同編輯工作的發(fā)起人擔任,一旦master在協(xié)同工作中退出,將在協(xié)作團隊中根據(jù)成員活躍度,推選新的master,詳細的選取流程將在算法設計中給出.

Master的主要工作,是在協(xié)同工作開始時,向各協(xié)作用戶發(fā)起結構文檔,同時具備合并結構文檔的權限,在本系統(tǒng)中,文檔合并是一個定時觸發(fā)的進程,即在系統(tǒng)工作經(jīng)歷特定時間間隔后,請求然后自動合并各協(xié)同用戶在該時間截點前的數(shù)據(jù), 若非master的協(xié)作用戶想要在本地合并結構性文檔,需向當前的master站點提出請求,請求通過后才可合并.

圖2中的協(xié)同工作由M1～M5(其中M1為 master)5個用戶完成,圖中的連接線代表各站點間網(wǎng)絡互連,每個協(xié)作站點的結構文檔只有標題整體架構一致,標題下的內容只有站點請求并通過才可同步.圖中的連接線分為實線和虛線,實線代表協(xié)作站點間存在共同編輯的標題塊,如M1和M2本地同時具有結構文檔中的P3.1的編輯權限,虛線代表各站點間產生新標題或刪除、修改標題時向其他站點廣播的過程.

3.3 文檔及節(jié)點定義

文檔結構的定義沿用MCPS算法中的定義,主副本利用樹形結構存儲,樹中的子父級關系代表標題節(jié)點的層級.

3.4 節(jié)點類型定義

節(jié)點類型包含以下兩類,共4種：.

第一類：現(xiàn)實節(jié)點.

標題節(jié)點(TN：Title-Node)：客戶端請求節(jié)點；

結構父節(jié)點(SPN：Str-Parent-Node)：客戶端請求節(jié)點的父節(jié)點,且未被請求,為了維護副本樹結構復制在客戶端但不包含文本內容；

結構兄弟節(jié)點(SBN：Str-Brother-Node)：客戶端請求節(jié)點的兄弟節(jié)點,且未被請求,為了維護副本樹結構復制在客戶端但不包含文本內容；

第二類：虛擬節(jié)點.

虛擬根節(jié)點(VRN：Virtual-Root-Node)：虛擬根節(jié)點為每一個一級標題的父節(jié)點,是在后臺虛擬存儲,為維護結構文檔整體樹型結構而存在,可以存儲結構文檔的文檔名稱,也可為空；

虛擬結構節(jié)點(VSN：Virtual-Str-Node )：虛擬節(jié)點的存在類似于虛擬根節(jié)點DOC,因為在非標準的結構文檔中,不能保證每個標題節(jié)點的層級結構都是完整的,對于結構文檔中散落的標題節(jié)點,我們自動為其創(chuàng)建父級虛擬結構節(jié)點,達到維護結構文檔樹型架構的目的.虛擬結構節(jié)點只在后臺存儲,并不顯示在結構文檔中.

3.5 節(jié)點屬性定義

在之前文章對節(jié)點定義的基礎上,我們新增了兩個新的節(jié)點屬性：

圖3 節(jié)點屬性定義Fig.3 Attributes of node

CE(Current Editors Numbers)：當前參與該標題節(jié)點下文檔編輯的協(xié)同用戶人數(shù)；

TC(Title Creator)：每一個標題節(jié)點中,記錄該標題節(jié)點的創(chuàng)造人,以便后期的請求仲裁和文檔合并工作使用；

所以最終我們對一個標題節(jié)點的定義可以表示為圖3中的形式.

3.6 操作定義

1)Append(N)：本地增量式向節(jié)點集N中的每個節(jié)點的Title Creator請求數(shù)據(jù)；

2)Delete(id,site)：站點site刪除標識符為id的節(jié)點；

3)InsertTitle ( parentId,id,site,data,name)：在父節(jié)點parentId的子節(jié)點尾部追加一個新的標題節(jié)點；

4)InsertTitleBefore (parentId,refId,id,site,data,name)：在父節(jié)點parentId的子節(jié)點隊列中refId節(jié)點前插入一個標識符為id,標題內容為name,標題文本內容為data的節(jié)點；

5)UpdateName(id,newName,oldName,site)：更新標識符為id的節(jié)點標題名稱oldName為newName.

6)UpdateData(id,newData,oldData,site)：更新標識符為id的標題下的內容oldData為newData.

4 MCPS2算法設計

4.1 結構文檔初始化

在結構文檔開始協(xié)同編輯工作開始時,首先給協(xié)同工作發(fā)起站點分配master權限,master客戶端首先初始化提供的結構文檔中的數(shù)據(jù),即將每一個標題節(jié)點(文中提出的標題節(jié)點包括所有等級的節(jié)點,具體的等級關系通過節(jié)點屬性中的參數(shù)關聯(lián))都被賦予第三部分提出的節(jié)點屬性參數(shù)值.

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

1. M1←master

2. i ← 0,Str-Doc ←Doc

3.forall nodes in Str-Docdo

4. Str-Doc[i].TC ←M1

5. i←i+1

6.endfor

7. user M1 choose editing Nodes as index sequence N

8.forj← 0 to N.length-1do

9. Str-Doc[ N[j]].CE ←M1

10.endfor

11.returnStr-Doc

4.2 協(xié)作站點請求數(shù)據(jù)

在節(jié)點屬性中我們設置了標題創(chuàng)始人參數(shù)TC,用來標記該標題節(jié)點是由哪一個協(xié)作站點新增,假設圖2中,站點M2請求編輯的標題節(jié)點集為P=[p3.1,p4.1],標題節(jié)點p3.1和p4.1的TC屬性均為M1,所以向M1站點發(fā)出數(shù)據(jù)請求,操作流程參見算法2；M1接收到請求后先判斷請求的標題節(jié)點是否已達編輯人數(shù)上限,是則拒絕請求,否則等待該標題內協(xié)作用戶的集體仲裁,且TC具有一票否決的權利,若TC通過,CE中的其他站點繼續(xù)仲裁,仲裁階段設置時間限制,超時默認自動放棄仲裁,請求判定標準為：通過用戶在該節(jié)點的節(jié)點活躍度(NLV)之和與拒絕用戶在該節(jié)點的節(jié)點活躍度之和進行比較,活躍度高者判定結果生效,仲裁邏輯詳見算法3.

算法2.RequesetNodes(P)

1. for i←0 to P.length do

2. request for site of P[i].TC

3. end for

算法3.Arbitration(id)：n /*此站點為M,節(jié)點集為N */

1.fori←0 to N.lengthdo

2.if(N[i].id==id)then

3. n←N[i]

4.endif

5.endfor

6.if(n.CE.length>=MaxCE)then

7. post refuse to the request site

8. return n←null

9.else

10.if(site M agree)then

11.for(j←0 to n.CE.length)do

12. Ask for arbitration from collaborative sites in n.CE[j]

13.if(n.CE[j]agree)then

14. NLVa←n.CE[j].NLV

15.elseif (n.CE[j]refuse)then

16. NLVr←n.CE[j].NLV

17.else

18. j←j+1

19.endif

20.endfor

21.else

22. post refuse to the request site

23. return n←null

24.endif

25.endif

26. /*活躍度對比*/

27.if(NLVa>= NLVr)then

28. n.CE.add(M)

29. post node n to the request site

30.else

31. post refuse to the request site

32. n←null

33.endif

34. return n

請求站點接收到返回的標題節(jié)點后,在本地通過Append操作自動構建編輯副本,構建過程可參考文獻[7]中的局部復制算法.

4.3 基本操作

任何協(xié)作站點想要插入新的標題節(jié)點,除了一級標題外的所有節(jié)點,都需要向父節(jié)點的TC請求插入權限,通過以后才可以插入新節(jié)點,并向所有協(xié)作站點發(fā)送此標題節(jié)點,保證各站點樹形文檔結構的一致.受篇幅所限,我們將InsertTitle和InsertTitleBefore兩個操作的處理算法中類似的部分抽取出來進行描述.

算法4.Insert(parentId,id,site,data,name) /*請求站點為M,插入節(jié)點N*/

1. define n.id==parrentId

2.if(n.TC !=M)then

3. request authority from n.TC

4. switch the response of n.TC do

5.case“agree”

6. N.parentId←n.id

7. N.TC←M

8. N.CE.add(M)；

9.case“delay”

10. repeat “agree”；

11.case“otherwise”

12. break；

13.endsw

14.endsw

15.endif

同樣,任何協(xié)作站點執(zhí)行更新和刪除節(jié)點操作時,需要向該節(jié)點的Title Creator 提出請求,請求通過才可執(zhí)行.

4.4 文檔合并

master在特定時間間隔合并文檔,因為每個標題節(jié)點有且僅有一個標題創(chuàng)建者,所以合并過程為向所有站點請求這些站點各自創(chuàng)建的節(jié)點數(shù)據(jù),若協(xié)作站點想要合并結構文檔需向master提出請求,請求通過才可合并文檔.

算法5.merge(M1,sites )： StrDoc /*請求站點為M1,sites為所有站點的集合*/

1.if(M1is not master)then

2. request for master

3.switchresponsedo

4.case“refuse”

5. break；

6.case“agree”

7. merge as master

8.endsw

9.else

10.for(i←0 to sites.length)do

11. request for sites[i]for nodes which node.TC is sites[i]

12. StrDoc.add(nodes)

13.endfor

14.endif

15. return StrDoc

4.5 master & TC 權限轉移

協(xié)同編輯系統(tǒng),支持協(xié)同用戶的隨時加入和隨時退出,但在本文算法中,提出的節(jié)點包含了TC (Title Creator) 這一屬性,在上側算法中也涉及到向標題節(jié)點TC請求權限的操作,一旦在請求前,仲裁站點退出,那么請求將不會得到響應,最終導致此標題節(jié)點可以被任意修改；同樣,在協(xié)同工作中的master也存在退出的可能,若退出后不推選出新的master,那么文檔合并工作將停止,這些問題最終都將違背我們最大程度保護用戶編輯意圖的初衷.為了解決此問題,我們設計了支持master和TC退出,權限轉移的算法.

master退出前需要先決定將權限轉移給哪一個協(xié)作站點,站點選擇的主要依據(jù)是：“在樹型結構文檔中活躍度最高,貢獻最大的站點,將作為下一任master”,即在虛擬根節(jié)點DOC上的樹活躍度TLV最高的站點被選為master.

算法6.masterChange(M1,Str)： M

1. sites←Str.DOC.CE

2. result←-1

3.ifmaster exsitthen

4.fori←0 to sites.lengthdo

5. result←Max(result ,Str.DOC.sites[i].TLV)

6.endfor

7.forj←0 to sites.lengthdo

8.if(Str.DOC.sites[j].TLV==result)then

9. M←sites[j]

10. break；

11.endif

12.endfor

13.endif

14. grant privilege to site M

站點M接收到master授權后,在本地首次合并結構文檔,并向其他站點廣播更新master站點信息.

同樣任意站點退出時,查找此站點創(chuàng)建的標題節(jié)點,統(tǒng)計是否存在一個站點,參與編輯的標題節(jié)點數(shù)量最多,若存在且唯一,取此站點替代退出站點；若存在但不唯一,比較這些站點在結構文檔副本的活躍度,活躍度最高的站點,取代退出站點,繼承退出站點的所有權限；若不存在,說明沒有其他站點參與這些標題節(jié)點的編輯工作,則master直接繼承退出站點的所有權限.

算法7.TCChange(M1,StrCopy)： M /*M1為退出站點,StrCopy是M1本地結構文檔副本*/

1.if(site M1exsit)then

2.fori←0toStrCopy.lengthdo

3.if(StrCopy[i].TC == M1)then

4. contact( StrCopy[i].CE ) as array CEs /* contact是合并所有站點CE產生新數(shù)組,產生新的數(shù)組CEs,CEs為對象數(shù)組,包含站點site和重復值count兩個屬性 */

5. count and duplicate CEs /*計算CEs中每個元素的重復值,并記錄在count屬性中,并刪減重復元素*/

6.endif

7.endfor

8. select max elements in CEs as array L

9.switchL.length do

10.case“=1”

11. Grant privilege of M1to M which L[0].site

12. case ”>1”

13.for(j←0 to L.length)do

14. max(StrCopy[0].L[j].TLV)

15. index←j

16.endfor

17. Grant privilege of M1to M which L[index].site

18.case“<1”

19. Grant privilege of M1 to master

20.endsw

21.endif

站點M接收到M1授權后,向所有站點廣播替換節(jié)點中TC和CE中的M1為M,由于篇幅所限,具體的替換流程,我們在后續(xù)文章中提出.

5 復雜度分析

結構文檔初始化是結構文檔創(chuàng)建者即master給標題節(jié)點中的TC、CE等屬性賦值的過程,暫不涉及其他站點協(xié)作,假設初始結構文檔中的節(jié)點個數(shù)為N,其中master請求參與協(xié)同編輯的節(jié)點個數(shù)為M,則標記節(jié)點TC的時間復雜度為O(N),請求節(jié)點后CE中新增站點信息的時間復雜度為O(M),由于M<=N,所以,當master創(chuàng)建一個新的結構文檔協(xié)作任務時,整體的時間復雜度為O(N).

協(xié)作站點請求數(shù)據(jù)時,需等待TC站點的仲裁,在算法3中,在TC站點同一發(fā)送請求數(shù)據(jù)之后,需要向該節(jié)點CE中的所有的站點發(fā)出仲裁請求,通過站點的活躍度總和與拒絕站點的活躍度總和進行對比,我們假設請求的節(jié)點為n,在等待請求結果方面我們設置的最大延遲時間,假設為時長為delayTimes,則在最差的環(huán)境下,該節(jié)點操作站點數(shù)量達到上限S,且每個站點都要等到最大延遲時間才返回請求結果,那么請求時所需的時間復雜度為O(S), 并伴隨n.CE.length *delayTimes時長的而延遲.

對于新增、插入、刪除等基本操作,我們加入了權限控制,請求操作執(zhí)行權限時時間復雜度為O(1),并伴隨delayTimes時長的延遲.在之前的文章中,我們對整個并發(fā)控制過程的最壞時間復雜度進行了分析,可以抽象為O(N2),N為結構文檔中的節(jié)點總數(shù),最壞的情況下,假設此時有S個站點同時編輯一個節(jié)點并產生了沖突,且S為編輯人數(shù)上限, 則基本操作階段,解決一個節(jié)點沖突的時間復雜度為T(N,S)=T(N2)+S*T(1)=O(N2),并伴隨S*delayTimes時長的延遲.

在master切換階段,要在其他站點中找到一個站點,它在結構文檔也就是虛擬根節(jié)點DOC上的樹活躍度最高,賦予它master權限,假設master退出后繼續(xù)參與協(xié)同工作的站點個數(shù)為T,則此過程所需的時間復雜度O(T)；而在TC權限轉移階段,首先將退出站點的所有節(jié)點(節(jié)點個數(shù)為N)的CE合并為長數(shù)組CEs,時間復雜度為O(N)；利用數(shù)組處理算法(由于篇幅所限,本文不對此算法進行詳細描述),求出CEs中每個數(shù)組元素的重復次數(shù),若該數(shù)組中有且僅有一個重復次數(shù)最大額數(shù)組元素,那么他對應的站點將被賦予退出站點的所有權限,一般的處理算法時間復雜度為O(CEs.length2),最差情況下,所有節(jié)點的CE已達到最大編輯人數(shù)S,此時的時間復雜度為O((N*S)2)；若不唯一,則比較這些站點在該節(jié)點的節(jié)點活躍度,活躍度高者接替退出站點權限；若不存在,則直接授權給master；所以TC權限轉移所需的時間復雜度可以表示為T(N,S)=O(N)+O((N*S)2)=O((N*S)2).

雖然在請求數(shù)據(jù)和仲裁等階段都會出現(xiàn)不同程度時長的延遲,這也是與之前大部分意圖維護算法的區(qū)別之處,但能夠通過此方式盡可能的保護用戶意愿,提升協(xié)同工作的意義,也是值得的.且后期能夠通過網(wǎng)絡帶寬的提升、算法的優(yōu)化等手段縮短延遲,最終達到更好的用戶體驗.

6 實例說明

如圖4所示,包含兩個協(xié)作站點M1和M2,其中M1作為master發(fā)起協(xié)同工作,并提供初始副本Str-Doc=[n1,n2,n3,n4,n5,n6,n7],在副本初始化過程中,M1作為Str-Doc中所有節(jié)點的創(chuàng)建人,那么這些節(jié)點中的TC屬性都被標記為M1,而其中M1只申請編輯了節(jié)點n1和n2,則n1.CE=[M1],n2.CE=[M1].

M2請求執(zhí)行O1=Request(n1,n6)：此時站點M2加入到協(xié)作任務中,并向master發(fā)起請求節(jié)點集N=[n1,n6](操作O1),因為n1和n6的TC都為M1,所以M1直接對O1操作進行仲裁,詳細的操作流程如下：

Step1.M1接收到O1的請求節(jié)點操作后,先判斷兩個節(jié)點各自的CE中編輯用戶數(shù)是否達到上限,未達到,接受M1的仲裁,M1同意發(fā)送節(jié)點數(shù)據(jù)給M2；

圖4 M1 和M2站點請求節(jié)點Fig.4 Example of requesting nodes at M1 and M2

Step2.M1同意后,分別向n1和n6的CE中的用戶發(fā)出集體仲裁請求,因為n1.CE= [M1],n2.CE=[],n1只有一個M1參與編輯,而n6暫時沒有用戶參與編輯,則默認仲裁通過；

Step3.仲裁通過后,M1在本地更改節(jié)點n1和n2屬性,即n1.CE=[M1,M2],n6.CE=[M2].

Step4.根據(jù)局部復制原理,保證局部副本的樹型存儲結構,M1將返回節(jié)點集N′=[DOC,n1,n2,n6]給M2,其中n2只包含存儲結構相關參數(shù)；

M2請求執(zhí)行O2=InsertTitleBefore(n1,n5,n8,M2,data,name)：M2請求在n5前插入節(jié)點n8：

Step1.首先找到n5節(jié)點的父節(jié)點為n1,n1.TC=M1；

Step2.向M1發(fā)起插入請求；

Step3.M1拒絕請求,并反饋給M2；

Step4.O2變?yōu)閺U操作.

M2請求執(zhí)行O3=InsertTitleBefore(n2,n6,n8,M2,data,name)：M2請求在n6前插入節(jié)點n8：

Step1.首先找到n6節(jié)點的父節(jié)點為n2,n2.TC=M1；

Step2.向M1發(fā)起插入請求；

Step3.M1同意請求,并向當前參與n2協(xié)同編輯的用戶們n2.CE發(fā)起仲裁請求,即向M1請求,則默認通過；

Step4.M1在本地執(zhí)行O3,Str-Doc=[n1,n2,n3,n4,n5,n6,n7,n8],n8.TC=[M2],n8.CE=[M2]并更新節(jié)點中的活躍度屬性,我們只將幾個有變動的節(jié)點對應的節(jié)點活躍度(NLV)和樹活躍度(TLV)標記如圖5所示.

圖5 站點M1和M2的節(jié)點、樹活躍度Fig.5 TLV and NLV of at M1 and M2

插入節(jié)點、刪除節(jié)點以及編輯節(jié)點內部的data和name信息,都需要通過如上的基本請求→仲裁→執(zhí)行流程,其中的仲裁過程是最能夠實現(xiàn)意圖維護意義的手段,為了更直觀的體現(xiàn)活躍度在意圖維護中的重要作用,我們加入新用戶M3,各站點執(zhí)行以下操作,詳細的操作交互流程如圖6所示.

M3： Append(N),N=[n1,n3,n4]；請求后M3站點存儲的局部副本結構如圖5所示.

M1： UpdateName(n1)；UpdateData(n1)；兩個操作都只是改變節(jié)點內部的標題和內容,并沒有改變文檔副本的結構內容.

M2： Delete(n6)；InsertTitle(DOC,n9)；執(zhí)行了刪除和插入操作后會對副本的結構產生影響.

圖6 站點M1、M2和M3操作執(zhí)行流程Fig.6 Operations executed at M1 and M2 and M3

執(zhí)行上述操作后,各節(jié)點在各站點的活躍度更新為圖7中值.

上述的操作請求中,節(jié)點創(chuàng)建人TC和協(xié)同編輯用戶群CE,均是一致通過,若在請求仲裁過程中,出現(xiàn)仲裁結果不一致,有的用戶同意,有的用戶拒絕,該如何處理？我們以M3發(fā)起的一個操作舉例說明.

此時M3請求執(zhí)行O9=UpdateName(n1),執(zhí)行步驟如下：

Step1.n1.TC=M1,向站點M1發(fā)出O9請求；

Step2.M1接收到O9請求后,首先判斷同意執(zhí)行該操作；

Step3.查找n1.CE=[M1,M2,M3],繼續(xù)向協(xié)同編輯節(jié)點n1的用戶M2發(fā)起請求；

Step4.M2接收到請求后,拒絕執(zhí)行O9操作；

Step5.仲裁階段出現(xiàn)了意見不一致的情況,此時判斷同意用戶與拒絕用戶在該節(jié)點上的節(jié)點活躍度總和.如圖8所示,(n1.M1.NLV=2) > (n1.M2.NLV=0),即同意>拒絕,那么最后的仲裁結果為同意M3站點執(zhí)行O9操作；

Step6.M2在本地執(zhí)行O9操作,返回同意請求給M1；

Step7.M1接收后,在本地執(zhí)行O9,返回同意請求給M3；

Step8.M3接收后,在本地執(zhí)行O9.

在上述的操作仲裁過程中,我們充分使用了節(jié)點創(chuàng)建人權利優(yōu)先,協(xié)同編輯用戶活躍度高優(yōu)先的原則,也就是誰對節(jié)點貢獻越多,話語權越大,來綜合判定一個操作是否能夠執(zhí)行,這在很大程度上保證了多用戶的意愿.在一致性維護方面,圖8中,分別給出了執(zhí)行上述操作集后各站點最終的副本狀態(tài),從M1站點可以看出,站點M2和M3的局部副本都為M1局部副本的一部分,且文檔的樹形結構及節(jié)點間的父子兄弟關系都一致,說明一致性得到維護.

圖8 站點M1、M2和M3最終副本狀態(tài)Fig.8 Final Str-Doc at M1 、 M2 and M3

7 總結及展望

計算機技術與移動設備的迅猛發(fā)展,時刻影響著人們的工作和生活方式,移動辦公,是當前也將成為未來主要的辦公模式.協(xié)同辦公概念的出現(xiàn),可以視作辦公模式改革的又一里程碑.如何將之前的協(xié)同技術和應用成功移植到移動端,并適應移動設備網(wǎng)絡不穩(wěn)、存儲有限等約束條件,成為了亟待解決的關鍵問題.本文基于局部復制策略和用戶活躍度,在之前的研究基礎上,提出了移動平臺下基于用戶活躍度的結構性文檔意圖維護算法,利用P2P的網(wǎng)絡連接模式構建協(xié)同工作網(wǎng).創(chuàng)新的提出站點master,節(jié)點Title Creator屬性,合理分配節(jié)點編輯、請求、新增權限,最大程度滿足多用戶的意愿.同時為了滿足用戶即來即走的需求,提出了權限轉移動態(tài)控制機制,最終提升整個協(xié)同工作的的意義.

后續(xù)的研究工作包括：

1)優(yōu)化算法執(zhí)行效率,完善權限轉移控制流程；

2)將MCPS2算法與MCPS算法結合,開發(fā)一款結構性文檔協(xié)同編輯APP；

3)在應用中引入圖像[15,16]、表格、文字等編輯內容.