王 丹,朱思征,高麗萍,王山山,徐 燁,史 旻

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

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

1 引 言

計(jì)算機(jī)技術(shù)的不斷發(fā)展,使得人們的日常工作、生活、娛樂(lè)方式也隨之發(fā)生翻天覆地的變化.辦公地點(diǎn)隨著寬帶、無(wú)線網(wǎng)絡(luò)的普及,也不再局限于辦公室.近年來(lái),由于各行各業(yè)不同領(lǐng)域工作量以及設(shè)計(jì)規(guī)模不斷增大,個(gè)人想要獨(dú)立完成所有工作往往面臨操作量巨大、用時(shí)長(zhǎng)等一系列諸多問(wèn)題.由此計(jì)算機(jī)支持的協(xié)同工作(Computer Supported Cooperative Work,CSCW)技術(shù)被提出[1].

實(shí)時(shí)群組編輯器支持分布在不同區(qū)域的用戶同一時(shí)刻編輯同一個(gè)共享文檔.全復(fù)制式架構(gòu)(full replication architecture)[2-6]中提出在每個(gè)協(xié)作用戶本地生成副本并對(duì)其操作,并將操作類型劃分為本地和遠(yuǎn)程兩類,此方法大大提高了本地操作響應(yīng)速度.而在保證實(shí)時(shí)協(xié)同編輯系統(tǒng)的可用性和準(zhǔn)確性[2-6,10-12]方面同時(shí)迸發(fā)出若干問(wèn)題,并發(fā)控制技術(shù)作為攻克這些問(wèn)題的關(guān)鍵技術(shù),一直被更多的研究人員們逐步完善.并發(fā)控制技術(shù)[10-12]主要包括一致性維護(hù)和沖突消解兩部分,一致性維護(hù)側(cè)重于保證協(xié)同站點(diǎn)副本的一致性,沖突消解則是為了能夠在最大程度上滿足多用戶的意愿.最典型的并發(fā)控制算法主要有操作轉(zhuǎn)換算法(Operation Transformation,OT)[13]和地址空間轉(zhuǎn)換算法(Address Space Transformation,AST)[6].

基于全復(fù)制式架構(gòu)研究的沖突消解算法與開(kāi)發(fā)的協(xié)同編輯應(yīng)用不勝枚舉,其研究成果已相對(duì)成熟.但隨著移動(dòng)設(shè)備的快速發(fā)展,大量編輯器若想要被移植到移動(dòng)端,將面臨存儲(chǔ)空間小,內(nèi)存有限等一系列的問(wèn)題,最終導(dǎo)致之前研發(fā)的實(shí)時(shí)群組編輯器無(wú)法完全的適用于移動(dòng)設(shè)備.而之前的研究成果多是基于全復(fù)制式架構(gòu)的主要原因,是協(xié)同編輯的對(duì)象多為普通的線性文檔,層次結(jié)構(gòu)較為模糊.但在現(xiàn)實(shí)生活或工作中,結(jié)構(gòu)性文檔的使用率相對(duì)更高,例如常見(jiàn)的申請(qǐng)專利或軟件著作權(quán)等書面材料,具有規(guī)定的模板結(jié)構(gòu);撰寫不同的專著、書籍同樣存在各自的參照模板結(jié)構(gòu);如果可以將此種具有結(jié)構(gòu)的文檔,按照層次級(jí)別、關(guān)聯(lián)關(guān)系進(jìn)行分類,讓協(xié)同編輯者可以各取所需,將在很大程度上提升用戶效率并節(jié)省存儲(chǔ)空間.Huanhuan Xia[7]等人提出了局部復(fù)制式架構(gòu)(partial replication architecture),并基于此復(fù)制式架構(gòu)研發(fā)了適用于移動(dòng)端的評(píng)論系統(tǒng),為結(jié)構(gòu)性文檔協(xié)同編輯領(lǐng)域的研究奠定了基礎(chǔ).

計(jì)算能力較弱,是移動(dòng)設(shè)備的又一個(gè)嚴(yán)重缺陷,隨著編輯工作量的增大,協(xié)同用戶的增多,即使使用普通的服務(wù)器也很難處理龐大的操作集.因此,近年來(lái)發(fā)展迅猛的云服務(wù)器技術(shù)成為了解決此問(wèn)題的關(guān)鍵.云服務(wù)器又稱為云主機(jī),在架構(gòu)上與傳統(tǒng)的服務(wù)器又很大區(qū)別,它能夠接收龐大的數(shù)據(jù)輸入量[8],高效處理海量數(shù)據(jù)集[9],并基于集群服務(wù)器技術(shù),虛擬出多個(gè)獨(dú)立服務(wù)器部分,其具備的故障自動(dòng)遷移和快照備份功能,大大提升了存儲(chǔ)安全性.

本文的結(jié)構(gòu)如下:首先對(duì)局部復(fù)制基本思想進(jìn)行簡(jiǎn)要介紹,針對(duì)本文提出的算法給出文檔結(jié)構(gòu)、節(jié)點(diǎn)、操作、沖突類型等基本定義;隨后詳細(xì)介紹移動(dòng)云平臺(tái)下基于局部復(fù)制的結(jié)構(gòu)性文檔協(xié)同編輯沖突消解算法,針對(duì)不同的沖突類型,給出不同的消解過(guò)程;其次是對(duì)本文提出的算法進(jìn)行效率分析,將算法與實(shí)例相結(jié)合,驗(yàn)證其準(zhǔn)確性;最后提出后續(xù)的主要研究?jī)?nèi)容.

2 相關(guān)工作

1989年,Eliis 等人[13]首次提出操作轉(zhuǎn)換概念,并建立OT[13]算法基本模型,其中提出的dOPT(distributed Operational Transformation)作為第一個(gè)基于OT的算法被運(yùn)用到Grove協(xié)同編輯系統(tǒng)中.然而,dOPT在某些場(chǎng)景下協(xié)同站點(diǎn)間結(jié)果會(huì)出現(xiàn)不一致的問(wèn)題,被Ressel[14]等人發(fā)現(xiàn).一致性維護(hù)技術(shù)的研究成為協(xié)同工作中的熱門問(wèn)題.1998年 Sun在早期的一致性模型基礎(chǔ)之上提出了CCI(Convergence Causality Intention)[15]模型,指出更為嚴(yán)格的一致性標(biāo)準(zhǔn)——意愿維護(hù),即沖突消解策略側(cè)重解決的問(wèn)題,由此,并發(fā)控制技術(shù)的研究得以完善.圍繞該一致性模型,一系列基于OT的樂(lè)觀并發(fā)控制技術(shù)被提出,如GOTO[15]、COT[10]、SCOT4[16]、LBT[17]、TIBOT[18]、ABST[11]等.由于OT的操作轉(zhuǎn)換規(guī)則較為復(fù)雜,準(zhǔn)確性證明比較困難,執(zhí)行效率較低.一種基于地址空間轉(zhuǎn)換的一致性維護(hù)技術(shù)AST被提出,對(duì)比OT,AST算法效率更高,并被證明可以準(zhǔn)確解決已有的并發(fā)控制問(wèn)題.近年來(lái),OT和AST技術(shù)被廣泛運(yùn)用到實(shí)時(shí)群組編輯領(lǐng)域[23],并研發(fā)出諸多協(xié)同應(yīng)用,例如 SketchPad、Co-CAD[19,20]、Co-eclipse[21]等.但這些研究目前只能夠適用于桌面協(xié)同應(yīng)用系統(tǒng),很難將其平移到移動(dòng)設(shè)備上使用,其中最主要的問(wèn)題在于移動(dòng)設(shè)備存儲(chǔ)空間有限,計(jì)算能力較弱,且之前的研究成果多是基于全復(fù)制式結(jié)構(gòu),致使移動(dòng)設(shè)備很難應(yīng)對(duì)數(shù)據(jù)量擴(kuò)張,操作數(shù)上漲的情況.面臨此困境,Huanhuan Xia[7]等人在2014年提出了適用于移動(dòng)端的評(píng)論系統(tǒng),并在考慮移動(dòng)設(shè)備內(nèi)存限制以及網(wǎng)速較差的前提下,提出了局部復(fù)制式架構(gòu),利用評(píng)論節(jié)點(diǎn)存儲(chǔ)用戶請(qǐng)求的詳細(xì)內(nèi)容,根據(jù)部分復(fù)制規(guī)則生成骨干節(jié)點(diǎn)從而生成本地局部副本,相比全復(fù)制式架構(gòu),大大節(jié)約了存儲(chǔ)本地副本的空間,節(jié)省了副本更新的時(shí)間.2016年,Sun等人提出了CSOT[22](Cloud storage Operational Transformation)算法,能夠支持在云存儲(chǔ)下實(shí)時(shí)文件同步功能,并維護(hù)一致性,實(shí)現(xiàn)理想的并發(fā)操作效果合并.CSOT算法首次將OT的一致性維護(hù)能力擴(kuò)展到云存儲(chǔ)共享空間中,并為基于云的協(xié)同技術(shù)發(fā)展做出了巨大貢獻(xiàn).

然而,CSOT算法的操作粒度為文件,粒度較大,對(duì)于文件內(nèi)容的更改,也只局限于對(duì)內(nèi)容的整體更新覆蓋.且在之前的并發(fā)技術(shù)研究中多是基于全復(fù)制式架構(gòu),考慮到移動(dòng)設(shè)備的存儲(chǔ)空間和計(jì)算能力的限制,本文基于局部復(fù)制策略的基本思想,將控制算法部署在云服務(wù)器下,提出一種適用于移動(dòng)終端的結(jié)構(gòu)性文檔協(xié)同編輯沖突消解算法,簡(jiǎn)稱為MCPS算法.

3 準(zhǔn)備工作

3.1 局部復(fù)制方法回顧

局部復(fù)制策略是一種適用于移動(dòng)評(píng)論系統(tǒng),為了解決移動(dòng)設(shè)備資源有限、評(píng)論的突發(fā)性等問(wèn)題,利用樹(shù)形結(jié)構(gòu)存儲(chǔ)請(qǐng)求數(shù)據(jù),并基于地址空間轉(zhuǎn)換算法研發(fā)的高效一致性維護(hù)算法.

圖1 局部復(fù)制原理圖Fig.1 Principle of partial replication architecture

如圖1所示,中央服務(wù)器負(fù)責(zé)維護(hù)評(píng)論會(huì)話的主副本(Primary copy),各個(gè)協(xié)作客戶端維持本地副本,稱為部分副本.當(dāng)有新用戶加入并向服務(wù)器請(qǐng)求評(píng)論內(nèi)容時(shí),請(qǐng)求的評(píng)論將通過(guò)操作的形式返回,而返回的數(shù)據(jù)在客戶端以節(jié)點(diǎn)構(gòu)成的“骨架樹(shù)(skeleton tree)”結(jié)構(gòu)存在.通過(guò)“釋放”骨架樹(shù)中的數(shù)據(jù)構(gòu)建部分副本,同時(shí)將本地副本通過(guò)SYNC請(qǐng)求與主副本同步.對(duì)于同步過(guò)程中創(chuàng)建、插入、刪除和更新等操作產(chǎn)生的沖突,該策略采用地址空間轉(zhuǎn)換技術(shù)解決,給出具體執(zhí)行規(guī)則,并實(shí)現(xiàn)數(shù)據(jù)的一致性維護(hù).

需要強(qiáng)調(diào)的是,當(dāng)以增量的形式構(gòu)建本地部分副本時(shí),需遵循如下規(guī)則:“如果一個(gè)評(píng)論節(jié)點(diǎn)被復(fù)制,該節(jié)點(diǎn)的父親節(jié)點(diǎn)(如果存在)也必須被復(fù)制”.為了區(qū)分同步節(jié)點(diǎn)類型為請(qǐng)求同步還是自動(dòng)同步,Huanhuan Xia等人將骨架樹(shù)種的節(jié)點(diǎn)大致分為三種:評(píng)論節(jié)點(diǎn)(comment node),即客戶端請(qǐng)求的節(jié)點(diǎn),包含評(píng)論內(nèi)容數(shù)據(jù);骨架父節(jié)點(diǎn)(skeleton parent node),作為請(qǐng)求節(jié)點(diǎn)的未被請(qǐng)求的父節(jié)點(diǎn),自動(dòng)同步到骨架樹(shù)中,但不包含評(píng)論數(shù)據(jù);骨架葉節(jié)點(diǎn)(skeleton leaf node):作為請(qǐng)求節(jié)點(diǎn)的未被請(qǐng)求的兄弟節(jié)點(diǎn),為在客戶端副本保持一致的節(jié)點(diǎn)兄弟關(guān)系而自動(dòng)同步到骨架樹(shù)種的節(jié)點(diǎn),同樣不包含評(píng)論數(shù)據(jù).

圖2 骨架樹(shù)示例圖Fig.2 Example of skeleton tree

舉例說(shuō)明,如圖2中的用戶B,當(dāng)其加入到協(xié)同評(píng)論會(huì)話中時(shí),本地的初始部分副本為空,首先發(fā)出一條FETCH請(qǐng)求,請(qǐng)求的評(píng)論節(jié)點(diǎn)集為{T,D },在生成骨架樹(shù)時(shí),檢測(cè)節(jié)點(diǎn)D擁有父節(jié)點(diǎn)B,此時(shí)將自動(dòng)同步節(jié)點(diǎn)B到骨架樹(shù)中,并標(biāo)記為骨架父節(jié)點(diǎn),且D有一個(gè)兄弟節(jié)點(diǎn)為E,則標(biāo)記為骨架葉節(jié)點(diǎn).“執(zhí)行”骨架樹(shù)構(gòu)建本地部分副本時(shí),部分副本中只包含評(píng)論節(jié)點(diǎn)中的數(shù)據(jù).

3.2 基本定義

3.2.1 文檔結(jié)構(gòu)定義

圖3 等級(jí)標(biāo)題結(jié)構(gòu)文檔Fig.3 Structured document

如圖3所示是一個(gè)具有等級(jí)標(biāo)題結(jié)構(gòu)的文檔,我們將此類型的文檔抽象,通過(guò)樹(shù)結(jié)構(gòu)存儲(chǔ)在云服務(wù)器端,即以DOC為主根節(jié)點(diǎn)(主副本為空時(shí),首先分配一個(gè)id=0 的DOC虛根節(jié)點(diǎn),用來(lái)維護(hù)主副本樹(shù)結(jié)構(gòu)的完整性),按照標(biāo)題等級(jí)構(gòu)建主副本樹(shù)——StrTree,我們將圖3中的文檔構(gòu)建成StrTree的結(jié)果如圖4所示.

圖4 StrTree示例圖Fig.4 An example of strtree

而客戶端通過(guò)請(qǐng)求節(jié)點(diǎn)在本地生成的部分副本,可以視為StrTree中的一個(gè)子樹(shù).子樹(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ù)副本樹(shù)結(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ù)副本樹(shù)結(jié)構(gòu)復(fù)制在客戶端但不包含文本內(nèi)容.

增量式構(gòu)建本地副本遵循的規(guī)則參照文章3.1的介紹.子樹(shù)中的節(jié)點(diǎn)類型,會(huì)在客戶端每次向云服務(wù)器請(qǐng)求數(shù)據(jù)后進(jìn)行更新.

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

對(duì)于StrTree中的每個(gè)節(jié)點(diǎn),我們給出以下定義和若干屬性:

表1 節(jié)點(diǎn)和屬性定義Table 1 Definition of node and basic parameters

這里我們提出了活躍度概念,是為了能更大程度上維護(hù)用戶的操作意愿,當(dāng)在協(xié)同操作的過(guò)程中產(chǎn)生沖突時(shí),解決方式不再局限于判定時(shí)間戳、用戶優(yōu)先級(jí)等因素,而是通過(guò)云服務(wù)器動(dòng)態(tài)更新各個(gè)客戶端在每個(gè)節(jié)點(diǎn)和每棵子樹(shù)的活躍度,以活躍度越高,越優(yōu)先執(zhí)行為原則,決定操作的執(zhí)行先后順序.

3.2.3 操作定義

1)Append(N):增量獲取節(jié)點(diǎn)集N的數(shù)據(jù),請(qǐng)求和執(zhí)行方式與文章[7]中類似;

2)Insert(parentId,id,site,data):在父節(jié)點(diǎn)parentId的子節(jié)點(diǎn)后,插入一個(gè)新節(jié)點(diǎn);

3)InsertBefore(parentId,refId,id,site,data):創(chuàng)建一個(gè)標(biāo)識(shí)符和文本內(nèi)容為id和data的新節(jié)點(diǎn),并插入到標(biāo)識(shí)符為parentId父節(jié)點(diǎn)下子節(jié)點(diǎn)隊(duì)列中的refId節(jié)點(diǎn)前;

4)Delete(id,site):刪除標(biāo)識(shí)符為id的節(jié)點(diǎn);

5)UpdateName(id,newName,oldName,site):更新標(biāo)識(shí)符為id的節(jié)點(diǎn)的標(biāo)題名稱為newName,并記錄之前的名稱oldName;

6)UpdateData(id,data,site):更新標(biāo)識(shí)符為id的節(jié)點(diǎn)下的文本內(nèi)容為data;

3.3 沖突類型

針對(duì)上方提出的4種以標(biāo)題為粒度的操作,1種以標(biāo)題內(nèi)文本內(nèi)容為粒度的操作,我們分析得出了以下5類沖突情況.

CIB:InsertBefore()_InsertBefore(),當(dāng)云服務(wù)器接收兩個(gè)指定插入位置的節(jié)點(diǎn)插入操作,它們指向同一個(gè)父節(jié)點(diǎn),且refId值相同時(shí),操作在客戶端的執(zhí)行順序不同,將產(chǎn)生不一致結(jié)果;

CII:Insert()_Insert(),與CIB的沖突情況類似,插入標(biāo)題操作在客戶端的執(zhí)行順序不同,產(chǎn)生的結(jié)果不同;

CD:Delete(),當(dāng)客戶端想要執(zhí)行一個(gè)刪除標(biāo)題操作時(shí),需先向云服務(wù)器發(fā)送刪除請(qǐng)求,云服務(wù)器判定沒(méi)有客戶端在編輯以該節(jié)點(diǎn)為根節(jié)點(diǎn)的樹(shù)后,同意刪除請(qǐng)求,否則駁回;

CDI:Delete()_InsertBefore(),當(dāng)一個(gè)刪除操作被允許,云服務(wù)器同時(shí)接收一個(gè)InsertBefore操作,與被刪除節(jié)點(diǎn)父節(jié)點(diǎn)相同,且被刪除節(jié)點(diǎn)的refId與插入操作的refId相同,操作的執(zhí)行順序?qū)⒂绊懣蛻舳私Y(jié)果;

CUN:UpdateName()_UpdateName(),當(dāng)兩個(gè)操作同時(shí)更改同一個(gè)節(jié)點(diǎn)的名稱時(shí),客戶端操作執(zhí)行順序不同結(jié)果不同;

CUD:UpdateData()_UpdateData(),與CUN類似,兩個(gè)操作都欲更改同一個(gè)節(jié)點(diǎn)的文本內(nèi)容時(shí),客戶端操作順序不同將產(chǎn)生沖突.

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

4.1 主副本更新監(jiān)聽(tīng)器

為了記錄客戶端活躍度,判斷執(zhí)行操作的優(yōu)先級(jí),我們?cè)谠品?wù)器開(kāi)辟空間賦予CL(Cloud Listener),作為記錄主副本變更的操作緩沖區(qū),CL[n]表示節(jié)點(diǎn)n變更的操作緩沖區(qū),CL[n]的結(jié)構(gòu)為響應(yīng)式增加site列的一張表(因?yàn)榻酉聛?lái)要根據(jù)每個(gè)節(jié)點(diǎn)對(duì)應(yīng)site的緩沖區(qū)大小計(jì)算對(duì)應(yīng)客戶端在該節(jié)點(diǎn)的活躍度即節(jié)點(diǎn)活躍度NLV,以及以該節(jié)點(diǎn)為根節(jié)點(diǎn)的樹(shù),樹(shù)中所有節(jié)點(diǎn)對(duì)應(yīng)site的緩沖區(qū)大小的累加值判斷對(duì)應(yīng)客戶端在對(duì)這棵樹(shù)的活躍度TLV),需要強(qiáng)調(diào)的是,為了保存所有節(jié)點(diǎn)的活躍度,當(dāng)一個(gè)節(jié)點(diǎn)被刪除,它在CL中依然存在,并且CL的更新不會(huì)影響StrTree.

過(guò)程1.priCopyListener(operation O)

1. Site = O.site;

2. IF(O.type == “Create”){

3. NEW node CL[n];

4. n.id = O.id;

5. IF(O.type == “Insert”){

6. n→parentId = O→parentId;

7. }

8. ELSE IF(O.type == “InsertBefore”){

9. n→parentId = O→parentId;

10. n→refId = O→refId;

11. }

12. Add CL[n].Site into CL[n];

13. }

14. ELSE{

15. SEARCH n WITCH n.id == O.id;

16. IF(CL[n].Site not exists){

17. Add CL[n].Site into CL[n];

18. }

19. }

20. Append(O)into CL[n].site;

21. n.NLV[site]= n.NLV[site]+ 1;

22. n.TLV[site]= n.TLV[site]+ 1;

23. NEW node p = n;

24. DO WHILE(p→parentId != 0)

25. {

26. childTLV[site]= p.TLV[site];

27. p.id = p→parentId;

28. p.TLV[site]= p.TLV[site]+ childTLV[site];

29. }

4.2 控制算法

云服務(wù)器根據(jù)操作類型和操作中的節(jié)點(diǎn)屬性,判斷執(zhí)行以下哪種沖突消解算法.

過(guò)程2.ControllAlgorithm(O1,O2)

1. IF ( O1.type==O2.type==InsertBefore

and O1.refId==O2.refId )

2. { return resolution_CIB(O1,O2); }

3. IF( O1.type==O2.type==Insert

and O1.parentId==O2.parentId )

4. { return resolution_CII(O1,O2); }

5. IF(O1.type==Del or O2.type==Del)

6. { return resolution_CD(O1,O2); }

7. IF((O1.type==Del and O2.type==InserBefore)‖

8. (O1.type==InsertBefore and O2.type==Del))

9. { return resolution_CDI(O1,O2); }

10. IF (O1.type==O2.type==UpdateName

and O1.id==O2.id)

11. { return resolution_CUN(O1,O2); }

12. IF (O1.type==O2.type==UpdateData

and O1.id==O2.id)

13. { return resolution_CUD(O1,O2); }

4.3 CIB消解過(guò)程

當(dāng)云服務(wù)器端接受到來(lái)自不同客戶端的InsertBefore操作,并檢測(cè)到出現(xiàn)CIB沖突時(shí),云服務(wù)器端需要通過(guò)判斷生成插入操作的站點(diǎn)在此節(jié)點(diǎn)的樹(shù)活躍度TLV,以及請(qǐng)求客戶端傳送插入節(jié)點(diǎn)對(duì)應(yīng)父節(jié)點(diǎn)和兄弟節(jié)點(diǎn)的類型,并以節(jié)點(diǎn)類型為標(biāo)題節(jié)點(diǎn)的客戶端優(yōu)先;節(jié)點(diǎn)類型相同時(shí),對(duì)應(yīng)站點(diǎn)在該節(jié)點(diǎn)父節(jié)點(diǎn)的的樹(shù)活躍度越高,操作執(zhí)行的優(yōu)先級(jí)越高,其它插入操作的位置將進(jìn)行適當(dāng)調(diào)整,并將結(jié)果反饋給客戶端.具體處理流程參照算法1,Oa和Ob操作分別插入兩個(gè)節(jié)點(diǎn)na和nb.

算法1.resolution_CIB(Oa,Ob)

1. REQUEST Node and Node Type From Clients

2. Pa = na→parentId; Pb = nb→parentId;

3. Ra = na→refId; Rb = nb→refId;

4. IF(Pa.type==Pb.type&&Ra.type==Rb.type){

5. GET CL[P]from Listener CL WITCH P.id==Pa.id;

6. IF(TLV[P].sitea>=TLV[P].siteb){

7. nb.refId=na.id;

8. }

9. ELSE{

10. na.refId=na.id;}

11. }

12. IF((Pa.value+Ra.value)>(Pb.value+Rb.value)){

13. nb.refId=na.id;

14. }

15. IF((Pa.value+Ra.value)<(Pb.value+Rb.value)){

16. na.refId=na.id;

17. }

18. POST Oa,Ob to Sitea,Siteb;

沖突類型CII的消解過(guò)程與CIB同理,這里我們不再贅述.

4.4 CD消解過(guò)程

當(dāng)客戶端想要執(zhí)行一個(gè)刪除操作時(shí),首先需向云服務(wù)器發(fā)送刪除節(jié)點(diǎn)請(qǐng)求,若此時(shí)存在操作將要作用于以該節(jié)點(diǎn)為根節(jié)點(diǎn)的樹(shù),或刪除節(jié)點(diǎn)在客戶端部分副本中不屬于標(biāo)題節(jié)點(diǎn),刪除操作被駁回.具體處理流程參照算法2.

算法2.resolution_CD(Del(na),O(nb))

1. IF(na.type==TN){

2. IF(na.deep<=nb.deep)//刪除節(jié)點(diǎn)na是nb的祖先

3. {//由nb向上遞歸尋找父節(jié)點(diǎn)是否存在na

4. P=nb;

5. bool=false;

6. DO WHILE(P.deep

7. P=P→parentId;

8. IF(P.id==na.id){

9. BREAK;

10. bool=true;}

11. }

12. IF(bool==true){

13. POST CANCLE Del to Sitea; }

14. ELSE{

15. EXCUTE Del ON the SERVER;

16. POST EXCUTE Del to Sitea; }

17. }

18. ELSE{

19. EXCUTE Del ON the SERVER;

20. POST EXCUTE Del to Sitea;

21. }

22. }

23. ELSE { POST CANCLE Del to Sitea; }

4.5 CDI消解過(guò)程

當(dāng)一個(gè)刪除節(jié)點(diǎn)操作被允許,且是另一個(gè)插入節(jié)點(diǎn)的兄弟節(jié)點(diǎn),位置依賴于刪除節(jié)點(diǎn),為了保證插入位置的準(zhǔn)確性,需要根據(jù)刪除節(jié)點(diǎn)位置確認(rèn)插入節(jié)點(diǎn)位置.

算法3.resolution_CDI(Del(na),InsertBefore(nb))

1. IF(na→parentId==nb→parentId&&na.id==nb.refId){

2. SELECT nodes in order WHITCH id=na→parentId as set N;

3. IF(N[k].id==na.id)

4. { Addr = k; }

5. nb.refId = N[k+1].id;

6. }

7. POST InsertBefore′(nb)to remote clients;

4.6 CUN消解過(guò)程

當(dāng)存在若干操作都欲更改同一個(gè)節(jié)點(diǎn)的名稱時(shí),云服務(wù)器需要做出判斷,采取哪個(gè)操作的結(jié)果,此時(shí)首先判斷節(jié)點(diǎn)在發(fā)出更改操作客戶端的類型,與CIB處理方式類似,類型為標(biāo)題節(jié)點(diǎn)的操作優(yōu)先,不同的是,若節(jié)點(diǎn)類型相同,對(duì)比站點(diǎn)在該節(jié)點(diǎn)的節(jié)點(diǎn)活躍度NLV,優(yōu)先執(zhí)行NLV高的站點(diǎn)發(fā)出的更改操作.

算法4.resolution_CUN(O1,O2)

1. REQUEST Node and Node Type From Clients

2. O1=UpdateName(n1,Name1,oldname,site1);

3. O2=UpdateName(n2,Name2,oldname,site2);

4. IF(n1.type==n2.type){

5. GET CL[P]from Listener CL WITCH P.id==n1.id;

6. IF(NLV[P].site1>=NLV[P].site2){

7. EXCUTE O1;

8. POST EXCUTE O1 to site2; }

9. ELSE{

10. EXCUTE O2;

11. POST EXCUTE O2 to site1; }

12. }

13. IF(n1.value > n2.value){

14. EXCUTE O1;

15. POST EXCUTE O1 to site2; }

16. IF(n1.value < n2.value){

17. EXCUTE O2;

18. POST EXCUTE O2 to site1; }

沖突類型CUD的消解過(guò)程與CUN同理.

5 復(fù)雜度分析

本文提出的MCPS算法部署在云服務(wù)器端,處理進(jìn)程分為兩部分:動(dòng)態(tài)更新各節(jié)點(diǎn)對(duì)應(yīng)的的節(jié)點(diǎn)活躍度和樹(shù)活躍度;檢測(cè)沖突類型并消解沖突.

動(dòng)態(tài)更新節(jié)點(diǎn)活躍度階段,首先通過(guò)操作攜帶節(jié)點(diǎn)n的屬性遍歷Cloud Listener查找是否存在該節(jié)點(diǎn)信息,不存在則插入該節(jié)點(diǎn);隨后根據(jù)操作的生成站點(diǎn)id找到在CL[n]中對(duì)應(yīng)的活躍度,先改變節(jié)點(diǎn)活躍度,再向上回溯更新它的祖先節(jié)點(diǎn)的活躍度,我們假設(shè)最糟糕的情況,查找到樹(shù)中的最后一個(gè)節(jié)點(diǎn)才找到節(jié)點(diǎn)n,并要再向上回溯一次,N為樹(shù)包含的節(jié)點(diǎn)總數(shù),H為樹(shù)的高度,則此過(guò)程所需的時(shí)間復(fù)雜度為O(N·H).

本文提出的六種沖突消解情況中,其核心首先時(shí)查找節(jié)點(diǎn)n,隨后查找CL[n]中相關(guān)站點(diǎn)活躍度,最后插入節(jié)點(diǎn)或更改節(jié)點(diǎn)信息,可以簡(jiǎn)單理解為一個(gè)雙重遍歷的過(guò)程,假設(shè)找到節(jié)點(diǎn)n遍歷過(guò)的節(jié)點(diǎn)個(gè)數(shù)為N,相關(guān)站點(diǎn)活躍度在CL[n]中存儲(chǔ)位置最大的為L(zhǎng),則時(shí)間復(fù)雜度可以表示為:O(N·L).整個(gè)并發(fā)控制過(guò)程的最壞時(shí)間復(fù)雜度可以抽象為O(N2).

關(guān)于空間復(fù)雜度,因?yàn)閷⑺惴ú渴鹪谠品?wù)器,且加入的節(jié)點(diǎn)監(jiān)聽(tīng)功能,并利用樹(shù)結(jié)構(gòu)存儲(chǔ)主副本與監(jiān)聽(tīng)緩存,假設(shè)主副本中包含的節(jié)點(diǎn)總數(shù)為N,那么對(duì)應(yīng)的空間復(fù)雜度至少是O(2N),但對(duì)于移動(dòng)客戶端來(lái)說(shuō),空間復(fù)雜度將是一個(gè)小于或遠(yuǎn)小于O(N)的值.

6 算法實(shí)現(xiàn)舉例

如圖5所示,服務(wù)器端此時(shí)的主副本內(nèi)容為圖5(a)中結(jié)構(gòu)樹(shù)中的所有節(jié)點(diǎn),當(dāng)前的CL中各節(jié)點(diǎn)的活躍度如表2所示,表中的n0代表根節(jié)點(diǎn)DOC.有兩個(gè)協(xié)同用戶site1和site2參與編輯工作,并產(chǎn)生接下來(lái)的操作:

圖5 主副本沖突消解結(jié)果Fig.5 Result of conflict resolution of primary copy

1)site1:Append(N1),N1={n1,n2};

site2:Append(N2),N2={n2,n4,n5,n6};

各自生成的部分副本子樹(shù)如圖6(a)和圖6(d).

2)site1:O1=InsertBefore(DOC,n2,n7,site1,data);

site2:O2=InsertBefore(DOC,n2,n8,site2,data);

表2 CL初始活躍度參照表Table 2 Reference of CL liveness initialization

執(zhí)行Resolution_CIB(O1,O2)處理進(jìn)程,兩個(gè)協(xié)作客戶端都欲在n2前插入一個(gè)新標(biāo)題節(jié)點(diǎn),首先判斷DOC和n2節(jié)點(diǎn)在兩站點(diǎn)被復(fù)制的類型,均為標(biāo)題節(jié)點(diǎn),接下來(lái)判斷兩站點(diǎn)在他們欲插入節(jié)點(diǎn)的父節(jié)點(diǎn)DOC的樹(shù)活躍度:

CL(DOC).TLV[site1]=5;

CL(DOC).TLV[site2]=3;

CL(DOC).TLV[site1]> CL(DOC).TLV[site2]

樹(shù)活躍度越高,操作執(zhí)行優(yōu)先級(jí)越高,所以先執(zhí)行site1站點(diǎn)的插入操作,將O2操作轉(zhuǎn)換為O2′= InsertBefore(DOC,n7,n8,site2,data),發(fā)送到站點(diǎn)1執(zhí)行;O1操作不變發(fā)送到站點(diǎn)2執(zhí)行.生成的結(jié)果如圖6(b)和圖6(e).CL中加入兩個(gè)節(jié)點(diǎn)的信息,并更新site1和site2的活躍度.

3)site1:O3=Del(n1,site1);

site2:O4=UpdateData(n4,data,site2);

執(zhí)行Resolution_CD(O3,O4),site1發(fā)送刪除請(qǐng)求至云服務(wù)器,同時(shí)接收到來(lái)自site2的操作O4,首先判斷n1在site1的節(jié)點(diǎn)類型為標(biāo)題節(jié)點(diǎn),再判斷n4的祖先節(jié)點(diǎn)中是否包含節(jié)點(diǎn)n1,因?yàn)閚1是n4的父節(jié)點(diǎn),所以刪除操作被駁回,云服務(wù)器向site1發(fā)送O3操作取消指令和操作O4,同時(shí)更新site2的活躍度.

4)site1:O5=Del(n7,site1);

site2:O6=InsertBefore(DOC,n7,n9,site2,data);

執(zhí)行Resolution_CDI(O5,O6),O5是被允許之心的刪除操作,n7.id等于O6.refId,所以優(yōu)先執(zhí)行O6,兩站點(diǎn)部分副本更新后結(jié)構(gòu)如圖6(c)和圖6(f).同時(shí)更新CL中對(duì)應(yīng)的活躍度數(shù)值.

圖6中兩個(gè)站點(diǎn)最后生成的部分副本(圖6(c)和圖6(f)所示)中重疊的部分結(jié)構(gòu)一致,證明了沖突消解算法的準(zhǔn)確性;最后更新的CL中各節(jié)點(diǎn)的站點(diǎn)活躍度為表3中的數(shù)據(jù).

7 總結(jié)及展望

隨著移動(dòng)網(wǎng)絡(luò)逐步健全,移動(dòng)設(shè)備迅猛發(fā)展,以及其具備的便攜、對(duì)地理位置無(wú)約束特性使得人們更傾向于在移動(dòng)終端上進(jìn)行辦公,移動(dòng)網(wǎng)絡(luò)環(huán)境下的協(xié)同研究及應(yīng)用開(kāi)發(fā)將成為未來(lái)科技發(fā)展的大趨勢(shì).但移動(dòng)設(shè)備的存儲(chǔ)和計(jì)算能力較弱,導(dǎo)致之前的協(xié)同研究成果不能完全適用于移動(dòng)端.為了解決此問(wèn)題,本文基于局部復(fù)制策略,提出了一種支持結(jié)構(gòu)性文檔協(xié)同編輯的沖突消解算法,并引入了云平臺(tái)作為操作中轉(zhuǎn)站,利用云平臺(tái)強(qiáng)大的計(jì)算能力,解決協(xié)同過(guò)程中出現(xiàn)的各種沖突.創(chuàng)新的提出了用戶活躍度這一概念,在最大程度滿足多用戶的意愿方面,不再僅僅依賴于判斷客戶端優(yōu)先級(jí)、時(shí)間戳等手段,而是動(dòng)態(tài)更新所有用戶的活躍度,更合理的判斷操作執(zhí)行優(yōu)先級(jí).

后續(xù)的研究工作包括:1)優(yōu)化算法執(zhí)行效率,完善沖突類型;

圖6 site1和site2部分副本沖突消解結(jié)果Fig.6 Result of conflicts resolution of site1 and site2

表3 CL更新后的活躍度參照表Table 3 Reference of CL liveness after updating

2)將MCPS算法實(shí)現(xiàn)在云平臺(tái)與移動(dòng)設(shè)備上,開(kāi)發(fā)一款結(jié)構(gòu)性文檔系統(tǒng)編輯APP;3)在應(yīng)用中引入圖像[24-26]、表格、文字附加屬性等協(xié)同操作功能.