移动协同环境下协同操作因果关系一致性研究

朱思征，高丽萍，敖丽娜，王山山

(1.上海理工大学 a.实验室管理与服务中心,b.光电信息与计算机工程学院 上海 200093;

2.华为技术有限公司上海研究所 上海 200127)



移动协同环境下协同操作因果关系一致性研究

朱思征1a，高丽萍1b，敖丽娜2，王山山1a

(1.上海理工大学 a.实验室管理与服务中心,b.光电信息与计算机工程学院 上海 200093;

2.华为技术有限公司上海研究所 上海 200127)

摘要:针对移动协同网络连接的不确定性,协同操作到其他节点并非完全可达,传统基于操作转换思想的协同算法在移动协同环境下其协同操作的因果关系会有不一致现象发生。分析了移动协同环境下的协同因果关系不一致的原因,并利用因果维持的必要条件与状态向量定义操作数差值D[m],快速定位未收到的操作消息ID,通过历史操作消息队列与待接收操作消息队列建立确认与消息请求重发机制,保证移动协同环境下协同操作结果的因果关系维持。最后使用连通率模拟仿真移动网络环境,通过例证与仿真实验验证了算法的可行性与有效性。

关键词:移动环境；协同计算；因果关系一致性；操作消息列表

协同过程的实现主要涉及协作场景的构建问题与协同关系的冲突消解、协同结果的一致性维护、Redo/Undo的实现等协同机制的控制问题。协同环境中如何适应协同节点状况与协作需求间的动态变化是协作场景构建研究的主题,是实时协同研究的方向之一。移动协同环境相对于传统的协同系统会因为节点的移动性具有协同网络节点间连接不稳定、传输不可靠等问题,使得移动协同节点间消息传输不能完全正确传达成为不可避免的事件,对节点协同结果的一致性产生致命影响,本文主要研究移动协同环境中协同操作消息未正确传达的发现及纠错机制,从而保证节点间协作操作的因果关系一致性。

1因果关系一致性

对具有分布性、交互性和协作性的实时协同应用系统,有大量的文章论证了操作转换[1-2]、地址空间转换[3]、WOOT[4]等乐观的一致性维护技术,其中操作转换算法是目前最为成熟、被广泛承认和接受并得到普遍应用的一种一致性维护方法。研究人员相继提出了dOPT，adOPTed，GOT，GOT2，GOTO，treeOPT，TreeLock_GOTO等操作转化算法[5-10],在上述算法中状态向量被广泛地用来判定操作之间的因果顺序关系。

定义1因果顺序关系“→”

给出操作oa与ob.oa,ob是由节点i与节点j分别生成的操作,那么oa→ob当且仅当，

1)i=j,oa在ob之前生成;

2)i≠j,在节点j,oa先执行,ob后生成;

3)存在ox,使得oa→ox,当ox→ob.

定义2依赖与并发关系

给出两个操作oa与ob.

1) 存在oa→ob,则ob依赖于oa;

2) 不存在oa→ob,同时也不存在ob→oa,则oa→ob为并发关系,记为oa‖ob.

如果操作oa→ob,那么在任意一个节点,操作oa必须在ob之前执行,记为满足因果关系维护(causality-preservation)。

因果关系维护保证协同编辑过程中的依赖操作执行顺序的一致。在移动协同编辑系统中,由于节点间网络状况的不同,同一操作到达其他节点时间、质量均有差异,有些节点可能因为数据接收缓冲溢出、链路噪声造成数据破坏、路由过程发生中断或者其他干扰等原因造成移动协同操作数据的损坏性丢失。丢失的协同操作若未得到及时纠错,按照因果关系一致性原则,在任意节点与丢失操作有依赖关系的后续操作将无法执行。

2移动协同环境下因果关系一致性的影响

2.1因果关系维护的必要条件

在众多的一致性维护算法中[11-12],状态向量与时间戳机制是解决因果关系违背问题的普遍解法。

定义3状态向量SV(State Vector)

设,n为协同群组中节点个数,每个节点拥有一个长度为n向量SV=〈S0,S1,…,Si，…，Sn-1〉。标记SV,i为节点i的状态向量,SV,i[j](i≠j)表示由节点j生成并且发送到节点i执行的操作数目。节点i每产生一次新的操作首先在本地执行,变更SV，i[i]=SV，i[i]+1,然后该操作广播至其他协同节点。

定理1在任何时刻都有∀i∀j，SV,i[i]≥SV,j[i] .

证明当i=j时,SV,i[i]与SV,j[i]指代相同,均表示节点i产生的本地操作个数,所以SV，i[i]=SV，j[i] ；当i≠j时,根据状态向量定义,节点i每产生一次新的操作首先在本地执行,再将产生的操作消息广播至其他协同节点,节点j接收但未执行操作消息时必然存在SV，j[i]≤SV，i[i] .证毕。

定义4操作消息(OperationMessage,OM)

操作消息是协同群组内各节点广播与交互的内容,定义操作消息的表示方法为:OM=〈OM,ID,SID,SV,O〉 .

1)OM，ID:消息的唯一标识,由SID与SV[SID]组合而成,QM，ID=SID_SV[SID] .

2) SID:操作消息产生节点的唯一标识。

3) SV:产生操作后节点SID的状态向量。

4)O:〈OID,object,method,content〉节点SID产生的操作向量,携带操作内容。

节点j接收到来自节点i发送的操作消息OM，i=〈OM,ID,i,SV，i,O〉,操作OM，i,O在节点j执行的必要条件如下:

条件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的所有依赖操作在节点j执行过,满足因果关系一致性要求。

2.2待接收消息的发现-确认机制

待接收操作:通过状态向量对比,应被节点接收但实际并未收到的操作。

协同算法不考虑网络状况,假设所有操作消息均能无误传达到任何节点。但在移动网络环境中,这一假设无法成立。

定义5操作数差值(Distance of Operation,D[m])

发送节点i与接收节点j上执行节点m的操作数之差记为D[m],表示为:D[m]=SV，i[m]-SV，j[m] m∈{0,…,n-1} .

当m=1时,若D[m]=1,OM，i,O操作符合在节点j执行的条件1。若D[m]≠1,节点j存在D[m]个待接收操作消息,待接收的消息来自节点i,令s=SV,j[m]+1,g=SV，j[m]+D[m],则待接收操作消息OM,ID区间范围[is,ie] .

对∀m,m∈{0,…,n-1}且m≠i时逐一判定D[m]值,当∀D[m]≤0,OM，i.O操作符合在节点j执行的条件2。当∃D[m]>0时,节点j存在D[m]个待接收操作消息,且待接收的消息来自节点m,其OM,ID区间范围[ms,me].

2.3待接收消息的重新获取策略

按一般交互系统的操作响应阈值为100ms[5,13-14]的原则,在发现待接收操作消息的ID后,若100ms内未能接收到该消息,应启动消息重新获取机制。待接收消息的重新获取涉及到消息重发请求目标节点的选择、消息组织方式的选择等为问题。

定义6已执行操作消息队列(ExecutedOMList,EOMList),EOMList=〈ID,OM,ID,SID,SV,O,t〉.其中〈OM,SID,SV,O〉=OM.

节点j接收到来自节点i发送的操作消息,节点j在确认待接收操作消息的OM,ID及其产生节点后,待接收操作消息的重新获取有2种方式。1)向OM,ID的产生节点m请求消息重发;2)向OM,ID已执行节点i请求消息重发。第1种方式中重发请求的目标、请求的内容、返回的地址等信息简单明确,但未接收消息的产生正是由于节点m与接收节点间j之间网络不通畅所致。第2种方式中,基于已执行操作消息队列的存在,节点j可批量也可单点向节点i发送重发请求。由于移动网络的不确定性,重发请求在周期频次超出设定阈值或有新的可选目标节点时,应变更目标节点。

定义7待接收消息队列(WaitedOM,IDList,WOMList)

WOMList=〈OM,ID,SS,ID,DS,ID,tf,f,DC,NO〉.

1)OM,ID:待接收消息的唯一标识。

2)SS,ID:消息产生节点

3)DS,ID:Destination Site ID,请求消息的目的地节点。

4)tf:Found Time,待接收消息的发现时间戳。

5)f:记录周期频次,如果超出限定阈值,将启动DS,ID变更策略。

6)DC,NO:the No of Destination Changed,目标节点变更的次数。

定义8已接收消息队列(Received OM List,ROMList),

ROMList=〈ID,OM〉,且OM=〈OM,ID,SID,SV,O〉.

3移动协同环境下协同操作因果维持算法

3.1相关算法

算法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:待接收消息的发现算法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:消息重发请求算法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因果一致性维持例证分析

因果关系维护保证协同编辑过程中的依赖操作执行顺序的一致,在文章所述算法中,通过接收端接收的操作消息主动判定该消息所蕴含操作oa的依赖操作ob是否已经接收与执行,如果依赖操作ob未被执行,则启动消息重发请求,确保依赖操作ob接收与执行,从而保证oa→ob使其满足因果关系维护要求。

本节通过举例来描述待接收消息的快速发现与重发请求机制。如下图所示,移动协同环境下存在三个协同节点〈S0,S1,S2〉,假设S0与S1、S2均双向可达,S1与S2之间网络故障。

1) S1生成新操作,广播操作消息OM-1-0,S0接收到消息后判定符合因果一致性条件,该操作交于其它算法判定是否存在冲突操作,是否符合操作意愿等。S2因模拟移动网络不可达,故无法接收OM1-0消息。

2) S2生成新操作,同上产生操作消息OM2-0。S0接收后同上需判定其它一致性约束等条件。

3)OM1-0与OM2-0先后在S0执行后,节点S0的SV=〈0,1,1〉。此时,节点S0产生新操作,新操作在本地立即执行后其SV=〈1,1,1〉,广播的消息为OM0-0。

4) S1节点接收消息OM0-0,其OM0-0.SV=〈1,1,1〉。此时调用JudgeRecieve(OM0-0)

a.获取本地SV，loc=〈0,1,0〉;

b.判定OM0-0是否在ROMList或WOMList中,此时判定结果为FALSE,调用待接收消息发现算法。

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节点的待接收接收操作消息。

e.m=2,D[2]=1-0=1;存在一个待接收消息,且待接收消息的OM,ID=m+’-’+temp=2-0,调用算法WOMList.Add(2-0,tn1, 0);

5) 操作消息OM0-0携带的操作0-0暂缓执行,并将其缓存到待执行队列。

6) 用SendRequest算法,以freq周期向S0发送重发请求,或者启用请求节点改选机制,直至获取该待接收操作。JudgeReceived算法进行了消息的筛选,保证消息执行的唯一性。

7)S1节点接收由S0转发的由S2节点产生的消息2-0,在满足其它一致性条件后执行,随后遍历待执行操作列表,将0-0消息携带的操作执行。

S2节点接收并待执行待接收操作消息1-0的过程与上述流程相同,在此不在赘述。

4仿真实验与分析

1) 仿真实验1。设定每个节点产生的操作数量为100个,选定协同节点数量分别为5，10，15,连通率从100%按10%步长递减,测量参与协同的所有节点完成因果维持所需的时间,每连通率测试5遍并求均值。若存在协同节点完成因果维持所需的时间超过理论最大时间的2倍以上,认定该连通率下本次实验无法完成因果维持。实验结果如图1所示。

图1　协同系统因果维持耗时与连通率关系图Fig.1　Collaborative system causal maintaintime-consuming and connectivity rate

由仿真实验1,文章所述算法可实现在不同网络连通率下协同系统的因果关系维持。在节点数量固定的前提下,随着网路连通率的下降,协同系统完成因果维持所需时间上升趋势明显。同时当网络连通率下降到一定的阈值后,协同系统出现无法完成100%因果维持情况,且不同节点数量的网络该联率阈值不同。

2) 仿真实验2。不同节点数下,协同系统完成因果维持的连通率最低阈值实验。实验选择2～15个节点,连通率从100%按2%步长递减,每连通率测试5遍,若一组实验内5次均不能完成因果维持,则认定上一个可完成协同系统因果维持的连通率为该节点数量下最低连通率阈值。实验结果如图2所示。

仿真实验2结果表明随着协同节点的递增,参与协同的所有节点完成因果关系维护所需的网络连通率呈现递减关系。

仿真实验不仅验证了论文所述算法的可行性与有效性,并将协同系统网络连通率与因果关系维持建立了关联关系,这种关系符合何种数学模型将是今后论文研究的课题之一。

图2　协同系统因果维持时点数量与连通率关系图Fig.2　Collabrative system causal orderingquantity and maintaining connectivity rate

5结论

移动协同环境中由于节点间网络状况不同,协同操作到其他节点并非完全可达,传统基于操作转换思想的协同算法在移动协同环境下其协同操作的因果关系会有不一致现象发生。通过提出协同操作消息丢失发现、确认、重发机制,建立历史消息队列与重发请求消息队列,快速定位丢失消息,保证了协同操作结果的因果关系一致性,论文通过例证与仿真实验验证了算法的可行性与有效性。参考文献：

[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]邵斌.高效的操作转换一致性维护方法研究[D].上海:复旦大学,2010.

[6]顾宁,杨江明,张琦炜.协同组编辑中基于地址空间转换的一致性维护方法[J].计算机学报,2007,30(5):763-774.

[7]高丽萍.复制式协同设计环境中基于地址空间转换的关联操作一致性维护策略研究[J].小型微型计算机系统,2011,32(4):599-605.

[8]高丽萍,陈庆奎,姚一成.支持团队分工的实时协同一致性维护技术研究[J].小型微型计算机系统,2013,34(1):34-40.

[9]王山山,邬春学,高丽萍,等.树型模型中进化设计的一致性维护技术的研究[J].小型微型计算机系统,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]高丽萍,卢暾.复制式协同图形编辑环境中复合Undo操作语义一致性维护研究[J]. 计算机应用研究,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-)，男，上海人，硕士，工程师，主要从事数据挖掘、协同计算、云计算研究，(E-mail)zhusz@usst.edu.cn

基金项目：国家自然科学基金项目:设计软件透明协同化关键技术研究(61202376)；上海市教委科研创新项目：设计软件透明协同化关键技术研究(13YZ075)

收稿日期：2015-05-26

文章编号:1007-9432(2016)01-0080-05