朱思征,高麗萍,敖麗娜,王山山
(1.上海理工大學(xué) a.實驗室管理與服務(wù)中心,b.光電信息與計算機工程學(xué)院 上海 200093;
2.華為技術(shù)有限公司上海研究所 上海 200127)
?
移動協(xié)同環(huán)境下協(xié)同操作因果關(guān)系一致性研究
朱思征1a,高麗萍1b,敖麗娜2,王山山1a
(1.上海理工大學(xué) a.實驗室管理與服務(wù)中心,b.光電信息與計算機工程學(xué)院 上海 200093;
2.華為技術(shù)有限公司上海研究所 上海 200127)
摘要:針對移動協(xié)同網(wǎng)絡(luò)連接的不確定性,協(xié)同操作到其他節(jié)點并非完全可達,傳統(tǒng)基于操作轉(zhuǎn)換思想的協(xié)同算法在移動協(xié)同環(huán)境下其協(xié)同操作的因果關(guān)系會有不一致現(xiàn)象發(fā)生。分析了移動協(xié)同環(huán)境下的協(xié)同因果關(guān)系不一致的原因,并利用因果維持的必要條件與狀態(tài)向量定義操作數(shù)差值D[m],快速定位未收到的操作消息ID,通過歷史操作消息隊列與待接收操作消息隊列建立確認與消息請求重發(fā)機制,保證移動協(xié)同環(huán)境下協(xié)同操作結(jié)果的因果關(guān)系維持。最后使用連通率模擬仿真移動網(wǎng)絡(luò)環(huán)境,通過例證與仿真實驗驗證了算法的可行性與有效性。
關(guān)鍵詞:移動環(huán)境;協(xié)同計算;因果關(guān)系一致性;操作消息列表
協(xié)同過程的實現(xiàn)主要涉及協(xié)作場景的構(gòu)建問題與協(xié)同關(guān)系的沖突消解、協(xié)同結(jié)果的一致性維護、Redo/Undo的實現(xiàn)等協(xié)同機制的控制問題。協(xié)同環(huán)境中如何適應(yīng)協(xié)同節(jié)點狀況與協(xié)作需求間的動態(tài)變化是協(xié)作場景構(gòu)建研究的主題,是實時協(xié)同研究的方向之一。移動協(xié)同環(huán)境相對于傳統(tǒng)的協(xié)同系統(tǒng)會因為節(jié)點的移動性具有協(xié)同網(wǎng)絡(luò)節(jié)點間連接不穩(wěn)定、傳輸不可靠等問題,使得移動協(xié)同節(jié)點間消息傳輸不能完全正確傳達成為不可避免的事件,對節(jié)點協(xié)同結(jié)果的一致性產(chǎn)生致命影響,本文主要研究移動協(xié)同環(huán)境中協(xié)同操作消息未正確傳達的發(fā)現(xiàn)及糾錯機制,從而保證節(jié)點間協(xié)作操作的因果關(guān)系一致性。
1因果關(guān)系一致性
對具有分布性、交互性和協(xié)作性的實時協(xié)同應(yīng)用系統(tǒng),有大量的文章論證了操作轉(zhuǎn)換[1-2]、地址空間轉(zhuǎn)換[3]、WOOT[4]等樂觀的一致性維護技術(shù),其中操作轉(zhuǎn)換算法是目前最為成熟、被廣泛承認和接受并得到普遍應(yīng)用的一種一致性維護方法。研究人員相繼提出了dOPT,adOPTed,GOT,GOT2,GOTO,treeOPT,TreeLock_GOTO等操作轉(zhuǎn)化算法[5-10],在上述算法中狀態(tài)向量被廣泛地用來判定操作之間的因果順序關(guān)系。
定義1因果順序關(guān)系“→”
給出操作oa與ob.oa,ob是由節(jié)點i與節(jié)點j分別生成的操作,那么oa→ob當且僅當,
1)i=j,oa在ob之前生成;
2)i≠j,在節(jié)點j,oa先執(zhí)行,ob后生成;
3)存在ox,使得oa→ox,當ox→ob.
定義2依賴與并發(fā)關(guān)系
給出兩個操作oa與ob.
1) 存在oa→ob,則ob依賴于oa;
2) 不存在oa→ob,同時也不存在ob→oa,則oa→ob為并發(fā)關(guān)系,記為oa‖ob.
如果操作oa→ob,那么在任意一個節(jié)點,操作oa必須在ob之前執(zhí)行,記為滿足因果關(guān)系維護(causality-preservation)。
因果關(guān)系維護保證協(xié)同編輯過程中的依賴操作執(zhí)行順序的一致。在移動協(xié)同編輯系統(tǒng)中,由于節(jié)點間網(wǎng)絡(luò)狀況的不同,同一操作到達其他節(jié)點時間、質(zhì)量均有差異,有些節(jié)點可能因為數(shù)據(jù)接收緩沖溢出、鏈路噪聲造成數(shù)據(jù)破壞、路由過程發(fā)生中斷或者其他干擾等原因造成移動協(xié)同操作數(shù)據(jù)的損壞性丟失。丟失的協(xié)同操作若未得到及時糾錯,按照因果關(guān)系一致性原則,在任意節(jié)點與丟失操作有依賴關(guān)系的后續(xù)操作將無法執(zhí)行。
2移動協(xié)同環(huán)境下因果關(guān)系一致性的影響
2.1因果關(guān)系維護的必要條件
在眾多的一致性維護算法中[11-12],狀態(tài)向量與時間戳機制是解決因果關(guān)系違背問題的普遍解法。
定義3狀態(tài)向量SV(State Vector)
設(shè),n為協(xié)同群組中節(jié)點個數(shù),每個節(jié)點擁有一個長度為n向量SV=〈S0,S1,…,Si,…,Sn-1〉。標記SV,i為節(jié)點i的狀態(tài)向量,SV,i[j](i≠j)表示由節(jié)點j生成并且發(fā)送到節(jié)點i執(zhí)行的操作數(shù)目。節(jié)點i每產(chǎn)生一次新的操作首先在本地執(zhí)行,變更SV,i[i]=SV,i[i]+1,然后該操作廣播至其他協(xié)同節(jié)點。
定理1在任何時刻都有?i?j,SV,i[i]≥SV,j[i] .
證明當i=j時,SV,i[i]與SV,j[i]指代相同,均表示節(jié)點i產(chǎn)生的本地操作個數(shù),所以SV,i[i]=SV,j[i] ;當i≠j時,根據(jù)狀態(tài)向量定義,節(jié)點i每產(chǎn)生一次新的操作首先在本地執(zhí)行,再將產(chǎn)生的操作消息廣播至其他協(xié)同節(jié)點,節(jié)點j接收但未執(zhí)行操作消息時必然存在SV,j[i]≤SV,i[i] .證畢。
定義4操作消息(OperationMessage,OM)
操作消息是協(xié)同群組內(nèi)各節(jié)點廣播與交互的內(nèi)容,定義操作消息的表示方法為:OM=〈OM,ID,SID,SV,O〉 .
1)OM,ID:消息的唯一標識,由SID與SV[SID]組合而成,QM,ID=SID_SV[SID] .
2) SID:操作消息產(chǎn)生節(jié)點的唯一標識。
3) SV:產(chǎn)生操作后節(jié)點SID的狀態(tài)向量。
4)O:〈OID,object,method,content〉節(jié)點SID產(chǎn)生的操作向量,攜帶操作內(nèi)容。
節(jié)點j接收到來自節(jié)點i發(fā)送的操作消息OM,i=〈OM,ID,i,SV,i,O〉,操作OM,i,O在節(jié)點j執(zhí)行的必要條件如下:
條件1:SV,i[i]=SV,j[i]+1,i≠j ;
條件2:SV,i[m]≤SV,j[m],m∈{0,…,n-1}且m≠i.
條件1和條件2共同保證OM,i,O的所有依賴操作在節(jié)點j執(zhí)行過,滿足因果關(guān)系一致性要求。
2.2待接收消息的發(fā)現(xiàn)-確認機制
待接收操作:通過狀態(tài)向量對比,應(yīng)被節(jié)點接收但實際并未收到的操作。
協(xié)同算法不考慮網(wǎng)絡(luò)狀況,假設(shè)所有操作消息均能無誤傳達到任何節(jié)點。但在移動網(wǎng)絡(luò)環(huán)境中,這一假設(shè)無法成立。
定義5操作數(shù)差值(Distance of Operation,D[m])
發(fā)送節(jié)點i與接收節(jié)點j上執(zhí)行節(jié)點m的操作數(shù)之差記為D[m],表示為:D[m]=SV,i[m]-SV,j[m] m∈{0,…,n-1} .
當m=1時,若D[m]=1,OM,i,O操作符合在節(jié)點j執(zhí)行的條件1。若D[m]≠1,節(jié)點j存在D[m]個待接收操作消息,待接收的消息來自節(jié)點i,令s=SV,j[m]+1,g=SV,j[m]+D[m],則待接收操作消息OM,ID區(qū)間范圍[is,ie] .
對?m,m∈{0,…,n-1}且m≠i時逐一判定D[m]值,當?D[m]≤0,OM,i.O操作符合在節(jié)點j執(zhí)行的條件2。當?D[m]>0時,節(jié)點j存在D[m]個待接收操作消息,且待接收的消息來自節(jié)點m,其OM,ID區(qū)間范圍[ms,me].
2.3待接收消息的重新獲取策略
按一般交互系統(tǒng)的操作響應(yīng)閾值為100ms[5,13-14]的原則,在發(fā)現(xiàn)待接收操作消息的ID后,若100ms內(nèi)未能接收到該消息,應(yīng)啟動消息重新獲取機制。待接收消息的重新獲取涉及到消息重發(fā)請求目標節(jié)點的選擇、消息組織方式的選擇等為問題。
定義6已執(zhí)行操作消息隊列(ExecutedOMList,EOMList),EOMList=〈ID,OM,ID,SID,SV,O,t〉.其中〈OM,SID,SV,O〉=OM.
節(jié)點j接收到來自節(jié)點i發(fā)送的操作消息,節(jié)點j在確認待接收操作消息的OM,ID及其產(chǎn)生節(jié)點后,待接收操作消息的重新獲取有2種方式。1)向OM,ID的產(chǎn)生節(jié)點m請求消息重發(fā);2)向OM,ID已執(zhí)行節(jié)點i請求消息重發(fā)。第1種方式中重發(fā)請求的目標、請求的內(nèi)容、返回的地址等信息簡單明確,但未接收消息的產(chǎn)生正是由于節(jié)點m與接收節(jié)點間j之間網(wǎng)絡(luò)不通暢所致。第2種方式中,基于已執(zhí)行操作消息隊列的存在,節(jié)點j可批量也可單點向節(jié)點i發(fā)送重發(fā)請求。由于移動網(wǎng)絡(luò)的不確定性,重發(fā)請求在周期頻次超出設(shè)定閾值或有新的可選目標節(jié)點時,應(yīng)變更目標節(jié)點。
定義7待接收消息隊列(WaitedOM,IDList,WOMList)
WOMList=〈OM,ID,SS,ID,DS,ID,tf,f,DC,NO〉.
1)OM,ID:待接收消息的唯一標識。
2)SS,ID:消息產(chǎn)生節(jié)點
3)DS,ID:Destination Site ID,請求消息的目的地節(jié)點。
4)tf:Found Time,待接收消息的發(fā)現(xiàn)時間戳。
5)f:記錄周期頻次,如果超出限定閾值,將啟動DS,ID變更策略。
6)DC,NO:the No of Destination Changed,目標節(jié)點變更的次數(shù)。
定義8已接收消息隊列(Received OM List,ROMList),
ROMList=〈ID,OM〉,且OM=〈OM,ID,SID,SV,O〉.
3移動協(xié)同環(huán)境下協(xié)同操作因果維持算法
3.1相關(guān)算法
算法1:操作消息接收判定算法JudgeReceived(OM)
Void JudgeReveived(OM)
{
SV,loc=Local.Get SV();ROMList=Local.GetROMList();
WOMList=Local.GetWOMList();
EOMList=Local.GetEOMList();
if ((OM.OMID inEOMList)‖(OM.OM,IDinROMList))
{Drop(OM);}
else
{if(OM.OM,IDinWOMList)
{ROMList.Add(OM);
WOMList.Move(OM);}
else
{FindWOM(OM,WOMList)}
}
}
算法2:待接收消息的發(fā)現(xiàn)算法FindWOM(OM,WOMList)
Void FindWOM(OM,WOMlist)
{var temp=0; var tempOM,ID;
SV,op=OM.SV;SV,loc=Local.GetSV();
for(varm=0;m {D[m]=SV,op[m] — SV,loc[m]; if(m==OM.SID) {if(D[m] !=1) {for(vark=0;k {temp=SV,loc[m]+k; tempOM,ID=m+’-’+temp; if (tempOM,IDinWOMList) WOMList.Update(tempOM,ID,m); else WOMList.Add(tempOM,ID,m,m,tn,0,0); } } } else {if(D[m]> 0) {for(intk=1;k= {temp=SV,loc[m]+k; tempOM,ID=m+’-’+temp; if (tempOM,IDinWOMList) WOMList.Updata(tempOM,ID,m); else WOMList.Add(tempOM,ID,m,m,tn,0,0); } } } } } 算法3:消息重發(fā)請求算法SendRequest() Void SendRequest() {if(WOMList !=Null) {foreach wom inWOMList {varf=(tn-WOMtf)/100; if(f-WOM.f〉=1) {Request(WOM.DS,ID,WOM.OM,ID,locSID); WOM.Update(WOM.OM,ID,f+1); } } } 3.2因果一致性維持例證分析 因果關(guān)系維護保證協(xié)同編輯過程中的依賴操作執(zhí)行順序的一致,在文章所述算法中,通過接收端接收的操作消息主動判定該消息所蘊含操作oa的依賴操作ob是否已經(jīng)接收與執(zhí)行,如果依賴操作ob未被執(zhí)行,則啟動消息重發(fā)請求,確保依賴操作ob接收與執(zhí)行,從而保證oa→ob使其滿足因果關(guān)系維護要求。 本節(jié)通過舉例來描述待接收消息的快速發(fā)現(xiàn)與重發(fā)請求機制。如下圖所示,移動協(xié)同環(huán)境下存在三個協(xié)同節(jié)點〈S0,S1,S2〉,假設(shè)S0與S1、S2均雙向可達,S1與S2之間網(wǎng)絡(luò)故障。 1) S1生成新操作,廣播操作消息OM-1-0,S0接收到消息后判定符合因果一致性條件,該操作交于其它算法判定是否存在沖突操作,是否符合操作意愿等。S2因模擬移動網(wǎng)絡(luò)不可達,故無法接收OM1-0消息。 2) S2生成新操作,同上產(chǎn)生操作消息OM2-0。S0接收后同上需判定其它一致性約束等條件。 3)OM1-0與OM2-0先后在S0執(zhí)行后,節(jié)點S0的SV=〈0,1,1〉。此時,節(jié)點S0產(chǎn)生新操作,新操作在本地立即執(zhí)行后其SV=〈1,1,1〉,廣播的消息為OM0-0。 4) S1節(jié)點接收消息OM0-0,其OM0-0.SV=〈1,1,1〉。此時調(diào)用JudgeRecieve(OM0-0) a.獲取本地SV,loc=〈0,1,0〉; b.判定OM0-0是否在ROMList或WOMList中,此時判定結(jié)果為FALSE,調(diào)用待接收消息發(fā)現(xiàn)算法。 c.m=OM.SID=0,D[0]=SV,o[0] — SV,loc[0]=1-0=1;符合因果一致性判定條件1。 d.m=1,D[1]=1-1=0,不存在S1節(jié)點的待接收接收操作消息。 e.m=2,D[2]=1-0=1;存在一個待接收消息,且待接收消息的OM,ID=m+’-’+temp=2-0,調(diào)用算法WOMList.Add(2-0,tn1, 0); 5) 操作消息OM0-0攜帶的操作0-0暫緩執(zhí)行,并將其緩存到待執(zhí)行隊列。 6) 用SendRequest算法,以freq周期向S0發(fā)送重發(fā)請求,或者啟用請求節(jié)點改選機制,直至獲取該待接收操作。JudgeReceived算法進行了消息的篩選,保證消息執(zhí)行的唯一性。 7)S1節(jié)點接收由S0轉(zhuǎn)發(fā)的由S2節(jié)點產(chǎn)生的消息2-0,在滿足其它一致性條件后執(zhí)行,隨后遍歷待執(zhí)行操作列表,將0-0消息攜帶的操作執(zhí)行。 S2節(jié)點接收并待執(zhí)行待接收操作消息1-0的過程與上述流程相同,在此不在贅述。 4仿真實驗與分析 1) 仿真實驗1。設(shè)定每個節(jié)點產(chǎn)生的操作數(shù)量為100個,選定協(xié)同節(jié)點數(shù)量分別為5,10,15,連通率從100%按10%步長遞減,測量參與協(xié)同的所有節(jié)點完成因果維持所需的時間,每連通率測試5遍并求均值。若存在協(xié)同節(jié)點完成因果維持所需的時間超過理論最大時間的2倍以上,認定該連通率下本次實驗無法完成因果維持。實驗結(jié)果如圖1所示。 圖1 協(xié)同系統(tǒng)因果維持耗時與連通率關(guān)系圖Fig.1 Collaborative system causal maintaintime-consuming and connectivity rate 由仿真實驗1,文章所述算法可實現(xiàn)在不同網(wǎng)絡(luò)連通率下協(xié)同系統(tǒng)的因果關(guān)系維持。在節(jié)點數(shù)量固定的前提下,隨著網(wǎng)路連通率的下降,協(xié)同系統(tǒng)完成因果維持所需時間上升趨勢明顯。同時當網(wǎng)絡(luò)連通率下降到一定的閾值后,協(xié)同系統(tǒng)出現(xiàn)無法完成100%因果維持情況,且不同節(jié)點數(shù)量的網(wǎng)絡(luò)該聯(lián)率閾值不同。 2) 仿真實驗2。不同節(jié)點數(shù)下,協(xié)同系統(tǒng)完成因果維持的連通率最低閾值實驗。實驗選擇2~15個節(jié)點,連通率從100%按2%步長遞減,每連通率測試5遍,若一組實驗內(nèi)5次均不能完成因果維持,則認定上一個可完成協(xié)同系統(tǒng)因果維持的連通率為該節(jié)點數(shù)量下最低連通率閾值。實驗結(jié)果如圖2所示。 仿真實驗2結(jié)果表明隨著協(xié)同節(jié)點的遞增,參與協(xié)同的所有節(jié)點完成因果關(guān)系維護所需的網(wǎng)絡(luò)連通率呈現(xiàn)遞減關(guān)系。 仿真實驗不僅驗證了論文所述算法的可行性與有效性,并將協(xié)同系統(tǒng)網(wǎng)絡(luò)連通率與因果關(guān)系維持建立了關(guān)聯(lián)關(guān)系,這種關(guān)系符合何種數(shù)學(xué)模型將是今后論文研究的課題之一。 圖2 協(xié)同系統(tǒng)因果維持時點數(shù)量與連通率關(guān)系圖Fig.2 Collabrative system causal orderingquantity and maintaining connectivity rate 5結(jié)論 移動協(xié)同環(huán)境中由于節(jié)點間網(wǎng)絡(luò)狀況不同,協(xié)同操作到其他節(jié)點并非完全可達,傳統(tǒng)基于操作轉(zhuǎn)換思想的協(xié)同算法在移動協(xié)同環(huán)境下其協(xié)同操作的因果關(guān)系會有不一致現(xiàn)象發(fā)生。通過提出協(xié)同操作消息丟失發(fā)現(xiàn)、確認、重發(fā)機制,建立歷史消息隊列與重發(fā)請求消息隊列,快速定位丟失消息,保證了協(xié)同操作結(jié)果的因果關(guān)系一致性,論文通過例證與仿真實驗驗證了算法的可行性與有效性。參考文獻: [1]ELLIS C A,GIBBS S J.Concurrency control in groupware systems[C]∥ACM.Proc of SIGMOD’89. New York,New Youk:ACM Press,1989. [2]SUN Chengzheng,ELLIS C.Operational transformation in real-time group editors:issues,algorithms,and achievements[C]∥Proc of CSCW’98.New York:ACM Press,1998. [3]GU Ning,YANG Jiangming,ZHANG Qiwei.Consistency maintenance based on the mark & retrace technique in groupware systems[C]∥Proc of GROUP’05.New York:ACM Press,2005. [4]OSTER G,URSO P,MOLLI P,et al.Data consistency for P2P collaborative editing[C]∥ACM.Proc. of CSCW’06.New York:ACM Press,2006. [5]邵斌.高效的操作轉(zhuǎn)換一致性維護方法研究[D].上海:復(fù)旦大學(xué),2010. [6]顧寧,楊江明,張琦煒.協(xié)同組編輯中基于地址空間轉(zhuǎn)換的一致性維護方法[J].計算機學(xué)報,2007,30(5):763-774. [7]高麗萍.復(fù)制式協(xié)同設(shè)計環(huán)境中基于地址空間轉(zhuǎn)換的關(guān)聯(lián)操作一致性維護策略研究[J].小型微型計算機系統(tǒng),2011,32(4):599-605. [8]高麗萍,陳慶奎,姚一成.支持團隊分工的實時協(xié)同一致性維護技術(shù)研究[J].小型微型計算機系統(tǒng),2013,34(1):34-40. [9]王山山,鄔春學(xué),高麗萍,等.樹型模型中進化設(shè)計的一致性維護技術(shù)的研究[J].小型微型計算機系統(tǒng),2014,35(12):2780-2784. [10]SUN Chengzheng,DONG Xu.Operational transformation for dependency conflict resolution in real-time collaborative 3D design systems[C]∥ACM.Proceedings of the ACM 2012 Conference on Computer Supported Cooperative Work.New York:ACM Press,2012:1401-1410. [11]MATTHIAS R,DORIS N R,et al.An integrating transformation-oriented approach to concurrency control and undo in group editors[C].∥ACM.Proceedings of the ACM 2012 Conference on Computer Supported Cooperative Work.New York:ACM Press,1996:288-297. [12]高麗萍,盧暾.復(fù)制式協(xié)同圖形編輯環(huán)境中復(fù)合Undo操作語義一致性維護研究[J]. 計算機應(yīng)用研究,2010,27(9):3434-3438. [13]SHNEIDERMAN B.Response time and display rate in human performance with computers[J].ACM Computing Surveys,1984,16(3):265-85. [14]LI D,LI R.A performance study of group editing algorithms[C]∥IEEE.Proceedings of ICPADS’06:Proeeedings of the 12thInternational Conference on Parallel and Distributed Systems.Washington,DC,USA:IEEE Computer Society,2006:300-307. (編輯:朱倩) Research on Collaborative Operation Causal Consistency in Mobile Collaborative Environment ZHU Sizheng1a,GAO Liping1b,AO Lina2,WANG Shanshan1a (1.a.LabManagementandServiceCenter,b.SchoolofOpticalElectrical&ComputerEngineering,UniversityofShanghaiforScienceandTechnology,Shanghai200093,China;2.ShanghaiResearchInstitute,HuaweiTechnologyCo.Ltd.,Shanghai200127,China) Abstract:Owing to the uncertainty in connection of mobile collaborative network, collaborative operation message may not be fully sent to other nodes. The traditional algorithm based on operation transformation would not fit the mobile collaborative environment,it would cause the problem of causal in consistency. The paper analyzed the reason of causality inconsistency in mobile collaborative environment, and defined the D[m] (Distance of Operation)based on the prerequisite of causal consistency and the state vector,for fast locating of the ID of “Waited Operation Message”. The paper also defined the ‘Executed OM List’ and the ‘Waited OMID List’,provided methods to find,confirm and regain the unreceived operation message,and to ensure the maintenance of causal consistency in mobile collaborative environment. Finally, the mobile network environment was simulated by using the ConnectedRate, and the feasibility and effectiveness of the proposed algorithm were verified by examples and simulation experiments. Key words:mobile collaborative environment;collaborative computing;causal consistency;operation message list 中圖分類號:TP311 文獻標識碼:A DOI:10.16355/j.cnki.issn1007-9432tyut.2016.01.016 作者簡介:朱思征(1980-),男,上海人,碩士,工程師,主要從事數(shù)據(jù)挖掘、協(xié)同計算、云計算研究,(E-mail)zhusz@usst.edu.cn 基金項目:國家自然科學(xué)基金項目:設(shè)計軟件透明協(xié)同化關(guān)鍵技術(shù)研究(61202376);上海市教委科研創(chuàng)新項目:設(shè)計軟件透明協(xié)同化關(guān)鍵技術(shù)研究(13YZ075) 收稿日期:2015-05-26 文章編號:1007-9432(2016)01-0080-05