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

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

1 引 言

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

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

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

結(jié)構(gòu)文檔,我們可以簡(jiǎn)單理解為文本內(nèi)容間存在等級(jí)結(jié)構(gòu)的文檔[7].例如我們?cè)诠ぷ髦谐Ｓ玫膚ord文檔編輯模板,標(biāo)題、表格、圖片等都有嚴(yán)格的樣式和層級(jí)規(guī)定,其中標(biāo)題的等級(jí),能夠清晰的體現(xiàn)文檔中內(nèi)容的結(jié)構(gòu)關(guān)系.將結(jié)構(gòu)文檔加入到協(xié)同編輯工作中,利用結(jié)構(gòu)化的方式存儲(chǔ),一方面能夠?qū)⒄w沖突細(xì)化到局部沖突,提升協(xié)作效率；另一方面,能夠?qū)Σ煌燃?jí)的文檔內(nèi)容賦予編輯權(quán)限,盡可能的保證大部分協(xié)作用戶的編輯意愿；再者,結(jié)構(gòu)文檔的存儲(chǔ)方式,更能夠適應(yīng)移動(dòng)終端,解決移動(dòng)設(shè)備存儲(chǔ)空間有限的問題.因此,如何在優(yōu)化結(jié)構(gòu)文檔在移動(dòng)端的存儲(chǔ)方式,如何合理涉及用戶編輯權(quán)限,最終提升協(xié)作效率,最大程度上滿足協(xié)作用戶的操作意愿,研究意義重大.

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

2 相關(guān)工作

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

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

3 準(zhǔn)備工作

3.1 MCPS算法回顧

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

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

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

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

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

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

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

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

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

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

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

文檔結(jié)構(gòu)的定義沿用MCPS算法中的定義,主副本利用樹形結(jié)構(gòu)存儲(chǔ),樹中的子父級(jí)關(guān)系代表標(biāo)題節(jié)點(diǎn)的層級(jí).

3.4 節(jié)點(diǎn)類型定義

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

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

標(biāo)題節(jié)點(diǎn)(TN：Title-Node)：客戶端請(qǐng)求節(jié)點(diǎn)；

結(jié)構(gòu)父節(jié)點(diǎn)(SPN：Str-Parent-Node)：客戶端請(qǐng)求節(jié)點(diǎn)的父節(jié)點(diǎn),且未被請(qǐng)求,為了維護(hù)副本樹結(jié)構(gòu)復(fù)制在客戶端但不包含文本內(nèi)容；

結(jié)構(gòu)兄弟節(jié)點(diǎn)(SBN：Str-Brother-Node)：客戶端請(qǐng)求節(jié)點(diǎn)的兄弟節(jié)點(diǎn),且未被請(qǐng)求,為了維護(hù)副本樹結(jié)構(gòu)復(fù)制在客戶端但不包含文本內(nèi)容；

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

虛擬根節(jié)點(diǎn)(VRN：Virtual-Root-Node)：虛擬根節(jié)點(diǎn)為每一個(gè)一級(jí)標(biāo)題的父節(jié)點(diǎn),是在后臺(tái)虛擬存儲(chǔ),為維護(hù)結(jié)構(gòu)文檔整體樹型結(jié)構(gòu)而存在,可以存儲(chǔ)結(jié)構(gòu)文檔的文檔名稱,也可為空；

虛擬結(jié)構(gòu)節(jié)點(diǎn)(VSN：Virtual-Str-Node )：虛擬節(jié)點(diǎn)的存在類似于虛擬根節(jié)點(diǎn)DOC,因?yàn)樵诜菢?biāo)準(zhǔn)的結(jié)構(gòu)文檔中,不能保證每個(gè)標(biāo)題節(jié)點(diǎn)的層級(jí)結(jié)構(gòu)都是完整的,對(duì)于結(jié)構(gòu)文檔中散落的標(biāo)題節(jié)點(diǎn),我們自動(dòng)為其創(chuàng)建父級(jí)虛擬結(jié)構(gòu)節(jié)點(diǎn),達(dá)到維護(hù)結(jié)構(gòu)文檔樹型架構(gòu)的目的.虛擬結(jié)構(gòu)節(jié)點(diǎn)只在后臺(tái)存儲(chǔ),并不顯示在結(jié)構(gòu)文檔中.

3.5 節(jié)點(diǎn)屬性定義

在之前文章對(duì)節(jié)點(diǎn)定義的基礎(chǔ)上,我們新增了兩個(gè)新的節(jié)點(diǎn)屬性：

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

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

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

所以最終我們對(duì)一個(gè)標(biāo)題節(jié)點(diǎn)的定義可以表示為圖3中的形式.

3.6 操作定義

1)Append(N)：本地增量式向節(jié)點(diǎn)集N中的每個(gè)節(jié)點(diǎn)的Title Creator請(qǐng)求數(shù)據(jù)；

2)Delete(id,site)：站點(diǎn)site刪除標(biāo)識(shí)符為id的節(jié)點(diǎn)；

3)InsertTitle ( parentId,id,site,data,name)：在父節(jié)點(diǎn)parentId的子節(jié)點(diǎn)尾部追加一個(gè)新的標(biāo)題節(jié)點(diǎn)；

4)InsertTitleBefore (parentId,refId,id,site,data,name)：在父節(jié)點(diǎn)parentId的子節(jié)點(diǎn)隊(duì)列中refId節(jié)點(diǎn)前插入一個(gè)標(biāo)識(shí)符為id,標(biāo)題內(nèi)容為name,標(biāo)題文本內(nèi)容為data的節(jié)點(diǎn)；

5)UpdateName(id,newName,oldName,site)：更新標(biāo)識(shí)符為id的節(jié)點(diǎn)標(biāo)題名稱oldName為newName.

6)UpdateData(id,newData,oldData,site)：更新標(biāo)識(shí)符為id的標(biāo)題下的內(nèi)容oldData為newData.

4 MCPS2算法設(shè)計(jì)

4.1 結(jié)構(gòu)文檔初始化

在結(jié)構(gòu)文檔開始協(xié)同編輯工作開始時(shí),首先給協(xié)同工作發(fā)起站點(diǎn)分配master權(quán)限,master客戶端首先初始化提供的結(jié)構(gòu)文檔中的數(shù)據(jù),即將每一個(gè)標(biāo)題節(jié)點(diǎn)(文中提出的標(biāo)題節(jié)點(diǎn)包括所有等級(jí)的節(jié)點(diǎn),具體的等級(jí)關(guān)系通過節(jié)點(diǎn)屬性中的參數(shù)關(guān)聯(lián))都被賦予第三部分提出的節(jié)點(diǎn)屬性參數(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é)作站點(diǎn)請(qǐng)求數(shù)據(jù)

在節(jié)點(diǎn)屬性中我們?cè)O(shè)置了標(biāo)題創(chuàng)始人參數(shù)TC,用來標(biāo)記該標(biāo)題節(jié)點(diǎn)是由哪一個(gè)協(xié)作站點(diǎn)新增,假設(shè)圖2中,站點(diǎn)M2請(qǐng)求編輯的標(biāo)題節(jié)點(diǎn)集為P=[p3.1,p4.1],標(biāo)題節(jié)點(diǎn)p3.1和p4.1的TC屬性均為M1,所以向M1站點(diǎn)發(fā)出數(shù)據(jù)請(qǐng)求,操作流程參見算法2；M1接收到請(qǐng)求后先判斷請(qǐng)求的標(biāo)題節(jié)點(diǎn)是否已達(dá)編輯人數(shù)上限,是則拒絕請(qǐng)求,否則等待該標(biāo)題內(nèi)協(xié)作用戶的集體仲裁,且TC具有一票否決的權(quán)利,若TC通過,CE中的其他站點(diǎn)繼續(xù)仲裁,仲裁階段設(shè)置時(shí)間限制,超時(shí)默認(rèn)自動(dòng)放棄仲裁,請(qǐng)求判定標(biāo)準(zhǔn)為：通過用戶在該節(jié)點(diǎn)的節(jié)點(diǎn)活躍度(NLV)之和與拒絕用戶在該節(jié)點(diǎn)的節(jié)點(diǎn)活躍度之和進(jìn)行比較,活躍度高者判定結(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 /*此站點(diǎn)為M,節(jié)點(diǎn)集為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. /*活躍度對(duì)比*/

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

請(qǐng)求站點(diǎn)接收到返回的標(biāo)題節(jié)點(diǎn)后,在本地通過Append操作自動(dòng)構(gòu)建編輯副本,構(gòu)建過程可參考文獻(xiàn)[7]中的局部復(fù)制算法.

4.3 基本操作

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

算法4.Insert(parentId,id,site,data,name) /*請(qǐng)求站點(diǎn)為M,插入節(jié)點(diǎn)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é)作站點(diǎn)執(zhí)行更新和刪除節(jié)點(diǎn)操作時(shí),需要向該節(jié)點(diǎn)的Title Creator 提出請(qǐng)求,請(qǐng)求通過才可執(zhí)行.

4.4 文檔合并

master在特定時(shí)間間隔合并文檔,因?yàn)槊總€(gè)標(biāo)題節(jié)點(diǎn)有且僅有一個(gè)標(biāo)題創(chuàng)建者,所以合并過程為向所有站點(diǎn)請(qǐng)求這些站點(diǎn)各自創(chuàng)建的節(jié)點(diǎn)數(shù)據(jù),若協(xié)作站點(diǎn)想要合并結(jié)構(gòu)文檔需向master提出請(qǐng)求,請(qǐng)求通過才可合并文檔.

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

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 權(quán)限轉(zhuǎn)移

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

master退出前需要先決定將權(quán)限轉(zhuǎn)移給哪一個(gè)協(xié)作站點(diǎn),站點(diǎn)選擇的主要依據(jù)是：“在樹型結(jié)構(gòu)文檔中活躍度最高,貢獻(xiàn)最大的站點(diǎn),將作為下一任master”,即在虛擬根節(jié)點(diǎn)DOC上的樹活躍度TLV最高的站點(diǎn)被選為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

站點(diǎn)M接收到master授權(quán)后,在本地首次合并結(jié)構(gòu)文檔,并向其他站點(diǎn)廣播更新master站點(diǎn)信息.

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

算法7.TCChange(M1,StrCopy)： M /*M1為退出站點(diǎn),StrCopy是M1本地結(jié)構(gòu)文檔副本*/

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是合并所有站點(diǎn)CE產(chǎn)生新數(shù)組,產(chǎn)生新的數(shù)組CEs,CEs為對(duì)象數(shù)組,包含站點(diǎn)site和重復(fù)值count兩個(gè)屬性 */

5. count and duplicate CEs /*計(jì)算CEs中每個(gè)元素的重復(fù)值,并記錄在count屬性中,并刪減重復(fù)元素*/

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

站點(diǎn)M接收到M1授權(quán)后,向所有站點(diǎn)廣播替換節(jié)點(diǎn)中TC和CE中的M1為M,由于篇幅所限,具體的替換流程,我們?cè)诤罄m(xù)文章中提出.

5 復(fù)雜度分析

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

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

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

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

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

6 實(shí)例說明

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

M2請(qǐng)求執(zhí)行O1=Request(n1,n6)：此時(shí)站點(diǎn)M2加入到協(xié)作任務(wù)中,并向master發(fā)起請(qǐng)求節(jié)點(diǎn)集N=[n1,n6](操作O1),因?yàn)閚1和n6的TC都為M1,所以M1直接對(duì)O1操作進(jìn)行仲裁,詳細(xì)的操作流程如下：

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

圖4 M1 和M2站點(diǎn)請(qǐng)求節(jié)點(diǎn)Fig.4 Example of requesting nodes at M1 and M2

Step2.M1同意后,分別向n1和n6的CE中的用戶發(fā)出集體仲裁請(qǐng)求,因?yàn)閚1.CE= [M1],n2.CE=[],n1只有一個(gè)M1參與編輯,而n6暫時(shí)沒有用戶參與編輯,則默認(rèn)仲裁通過；

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

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

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

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

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

Step3.M1拒絕請(qǐng)求,并反饋給M2；

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

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

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

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

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

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

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

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

M3： Append(N),N=[n1,n3,n4]；請(qǐng)求后M3站點(diǎn)存儲(chǔ)的局部副本結(jié)構(gòu)如圖5所示.

M1： UpdateName(n1)；UpdateData(n1)；兩個(gè)操作都只是改變節(jié)點(diǎn)內(nèi)部的標(biāo)題和內(nèi)容,并沒有改變文檔副本的結(jié)構(gòu)內(nèi)容.

M2： Delete(n6)；InsertTitle(DOC,n9)；執(zhí)行了刪除和插入操作后會(huì)對(duì)副本的結(jié)構(gòu)產(chǎn)生影響.

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

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

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

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

Step1.n1.TC=M1,向站點(diǎn)M1發(fā)出O9請(qǐng)求；

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

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

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

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

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

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

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

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

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

7 總結(jié)及展望

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

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

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

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

3)在應(yīng)用中引入圖像[15,16]、表格、文字等編輯內(nèi)容.