实时协同编程环境下的语义冲突消解方法研究
2019-05-05高丽萍游书伟
高丽萍,游书伟
1(上海理工大学 光电信息与计算机工程学院,上海 200093)2(复旦大学 上海数据科学重点实验室,上海 200093)
1 引 言
移近年来互联网行业的快速发展,带来了软件行业的繁荣,对复杂软件的要求日益增加.软件的规模和复杂度不断提高,增加了软件制作的难度,使得开发工程师们不得不或是更愿意对软件项目实施协同工作.协同编程环境能够大大提高开发人员的工作效率,降低工作难度,缩短研发周期.将计算机支持的协同工作与编程环境结合是当下的热门研究领域之一[1],过去的几十年,已经有许多的协同软件研究者致力于协同编程软件或是协同编程方法的研究上,研发了一系列的协同开发工具[1,15].
传统的协同编程,往往指的是各个开发人员独立的工作于非实时的开发环境,再通过媒介工具上传代码、同步代码,实现协同工作.而实时协同的编程环境支持多个用户在任意时间任何地点并发的编辑共享的代码文档,不再需要通过第三方工具同步源代码文档.实时的协同编程环境须满足实时,分布,无约束3个基本条件.为了满足上述3个条件,研究人员通常采用复制式结构,每个协同站点将共享文档复制到本地工作区域.实时协同文本编辑环境中共享的文档通过OT(Operation transformation)[2,3,8]技术维护各个协同的站点的文本内容一致(语法一致).实时协同编程环境是特殊的协同文本编辑环境,该环境不仅要求维护文本内容的一致性,且在保证内容一致性的同时,需要保证文本内容的语义正确性.文本内容语义错误通常是因为并发的编辑操作导致的语义不一致.语义一致性是Sun等提出的CCI模型[8]中的一条,即意愿维护,只有在所有站点的收敛性和意愿一致性都满足时,CSCW系统才算是正确的计算机支持的协同系统.传统的语义维护主要针对文本编辑器中基于字符操作的一致性,在这种编辑环境下,字符与字符之间虽然具有前后继关系,但在属性上没有依赖关系[9].在编程环境下,操作具有更丰富和更广泛的语义信息,且字符与字符之间可能存在着大量的依赖关系,由于一些操作在执行过程中需要依赖于其它操作对象,操作的语义很有可能由于其它站点上的并发操作而受到影响,且协同编程系统中尤为强调语义一致性.只维护语法一致性,而忽略了语义一致性,在协同编程中可能产生难以维护,或者较难发现的错误,增加协同编程环境中代码正确性的维护难度.
本文针对实时协同编程环境语义冲突消解方法展开研究.本文组织结构如下:第2部分对研究背景与相关工作进行介绍;第3部介绍了协同编程环境中的语义冲突场景、动态依赖关系及不完整的编辑操作产生的编辑错误;第4部分设计了实时协同编程环境的语义冲突消解算法ACAS并进行了实例分析.第5部分,为了验证算法可行性,在Windows平台下基于ACAS算法开发了支持语义冲突消解的实时协同编程原型系统CoCode.第6部分,对设计的控制算法和相关函数进行了模拟仿真实验并给出实验分析结果.第7部分为全文内容的总结及对未来工作的展望.
2 相关工作
冲突消解是实时协同编辑系统中重要的研究课题,是保证系统正确性和可用性的关键性技术.针对实时协同编辑系统的冲突问题解决方法主要分为两大类:冲突消解方法和冲突避免方法.冲突消解方法允许协同编辑过程中发生冲突,一旦有冲突发生则使用相应的策略来消除冲突,从而保证共享文档的一致性.近些年,冲突消解方法研究中最常用的一致性维护技术主要分为两大类:基于操作转换OT[2,3,8]技术和基于地址转换(Address Space Transfor-mation,AST)[4]技术,包括Ellis和Gibbs在文献[2]中提出的dOPT算法,Sun和Ellis在文献[2]提出的GOT和GOTO算法,Sun在文献[3]提出的COT算法以及Gu等人在文献[4]中提出的AST算法等.冲突避免方法是指在冲突发生前避免冲突发生,该方法一般采用加锁的方式来避免冲突,即当用户对某对象进行操作时需要先申请加锁,只有申请成功的用户才能操作该对象.FAN和SUN在文献[1]中提出的DAL(Dedendency-based Automatic Locking)技术,以动态加锁的方式实现了实时协同编程环境的语义冲突避免,并采用Shared-Locking[6]的方法处理并发加锁的问题.该方法虽有效的避免了语义冲突的发生,但在一定程度上限制了协同编程的效率,且频繁的加锁与释放锁会加大对系统资源的开销.
传统的锁方法对协同编程的限制较大,在避免语义冲突的同时限制了对其它代码段的编辑.以并不是所有的并发操作都导致语义冲突为出发点,本文针对实时协同编程环境的语义冲突、不完整的编辑带来编辑错误问题以及代码文档依赖图动态依赖关系,在SUN,FAN等人的研究基础上,设计了协同编程环境下基于CAS并发处理思想的语义冲突消解方法ACAS(Automatic Compare And Swap).CAS(Compare And Swap)方法[5]是一种较为新颖的并发冲突处理技术,其核心思想是通过对目标对象设定期望值,若操作的目标对象的期望值由于某些因素发生变化,则操作不可执行.反之,操作可执行.CAS方法[5]虽用于处理线程间资源同步问题,但用于语义冲突消解上同样适用.
3 实时协同编程环境下的语义冲突消解方法
实时协同编程环境的编辑需要遵循语义一致性.语义一致性是指:共享文档的协同编辑要符合编程语言规则,并保证解决问题的逻辑方面的正确性.在协同编程的过程中,如果存在多个用户并发的编辑相同代码域或是存在依赖关系的不同代码域,都可能导致语义冲突的发生.协同编程环境中语义冲突的具体场景及相关定义在文献[1]中进行了详细描述.为了更好的说明语义冲突,文中也进行一些相关论述.
3.1 基本定义
独立的代码域是协同编程环境最基本的元素,独立的代码域及其相关的定义介绍如下:
定义1.基础域和开放域[1].
1)基础域(Basic Area,BA):一系列源代码组成的语义有意义且独立的代码域;
2)开放域(Open Area,OA):基础域之外的所有代码域;
定义2.依赖关系.
基础域A依赖于基础域B,表示为A→B;如存在A→B,B→C,则A→C;本文中将A→B,B→C称为直接依赖关系,A→C称为间接依赖关系.
定义3.依赖图.
1)每个基础域对应一个依赖图结点.
2)Node→Node,表示依赖图之间的依赖关系.
3)依赖图结点之间的依赖关系与其对应的基础域之间的依赖关系一致.基础域之间的依赖关系通过依赖派生机制实时分析,建立或取消基础域之间的依赖关系[1].
4)依赖图中记录的信息为对应基础域代码文本内容.
如图1所示,图中包含了节点d、c,由于节点d中对应的基础域中的代码为函数List,该函数引用了节点c中的变量maxSize,故节点d,c存在依赖关系且d→c,节点d直接依赖于节点c.
文中将G(Graph)表示为一个依赖图,G=(N),N为依赖图中的所有结点,表示为N={ N0,N1,…,Nn}.N0为依赖图中的一个结点,每个结点中记录的信息包含:结点id(Id),结点直接依赖的结点集合(RooNode,RN),以及对应基础域的代码文本内容(NodeContext,NC),表示为No=
3.2 基本的操作类型
关于代码的编辑操作:
1)insert():向基础域或者开放域插入新的字符.例如:insert(1,1,x)表示在第1行的位置1上插入字符x.
2)delete():删除基础域中的字符.例如:delete(1,1,6)表示删除第1行位置1之后的6个字符.
以代码域为单位对象的编辑操作:
1)createArea():创建一个新的基础域,即在开放域中插入新的字符;
2)deleteArea():删除某个基础域,即删除某个基础域中的所有字符;
3)revert():将基础域恢复到某个代码域版本;
4)save():保存基础域中的代码内容并生成相应代码域版本;
实际上,createArea和deleteArea只是特殊的insert 和delete操作,revert和save操作的作用将在后文中做进一步的讨论.
定义4.依赖冲突.
1)兼容关系:存在两个编辑操作O1和O2,若O1与O2是兼容关系,表示为O1⊙O2,iff 1)O1‖O2;2)O1,O2作用于无依赖关系的不同基础域.
2)排斥关系:存在两个编辑操作O1和O2,若O1与O2是冲突关系,表示为O1⊗O2,iff 1)O1‖O2;2)O1,O2作用于相同或存在依赖关系的基础域.
兼容的并发操作,可通过OT技术实现一致性维护.本文主要研究语义冲突消解,由于兼容的并发操作不引起语义冲突,故不对这种情况进行讨论.若并发的操作为排斥关系,由于相互排斥的操作难以进行操作意愿融合,故只有一个操作的编辑效果将会被保留.
3.3 协同编程环境中语义冲突的一般条件
协同编程环境中语义冲突可能发生的几种情况.
1)协同编程人员对相同的代码域的并发工作.
2)协同编程人员对存在依赖关系的代码域的并发工作.
3)协同编程人员的工作导致依赖图结构发生改变.
3.4 协同编程环境中语义冲突的场景分析
图2是一个未完成的c++类,该类用于实现线性表.图左侧为源代码,图右侧是源代码中基础域对应的依赖图结点.每个基础域(BA)对应一个依赖图结点,依赖图之间的依赖关系对应基础域中的依赖关系.图中空白的区域代表开放域(OA).当协同人员工作于这个类中时将可能发生以下几种冲突:
情况1.并发的编辑相同的基础域导致的语义冲突
如图2的(a)部分所示,依赖图结点G为List类中的方法Delete,在相同时间段,存在两个用户u0,u1并发的编辑结点b对应的基础域.
1)在站点0上,用户u0将Delete函数的返回值类型由int类型修改为void类型.
2)在站点1上,用户u1在Delete函数的函数体中添加了 return data[location].
首先,在各自工作的站点上,两个用户对结点b的编辑并未引起错误,当两个站点上的操作发送到对端,通过OT技术进行一致性维护处理后,得到的结果虽然满足了文本内容的一致性,却导致了编程语言规则错误.经过用户u0修改后的Delete方法不能有返回值,即通过OT技术处理后得到的代码内容违背了用户的编辑意愿,语义冲突发生.
图1 List类的依赖关系图Fig.1 Dependency graph of class list
情况2.并发的编辑存在相互依赖的基础域导致语义冲突.如图2的(b)部分所示,在某一时刻,用户u0与用户u1并发的工作于结点a,与结点d且结点d依赖于结点a.
图2 逻辑错误场景Fig.2 Logical error situation
1)在站点0上,用户u0修改变量data的数据类型,将data修改为int型的数组容器.
2)在站点1上,用户u1为指针变量data开辟内存空间
在各自的站点上,两位用户的编辑并未引起错误,但当用户的编程操作发送到对端时,语义冲突发生.冲突的原因在于用户u1对结点b的编辑基于结点a的代码,而用户u0修改了结点a中的代码.在代码同步时无法兼容两个用户的编辑操作从而导致语义冲突.
上述两个案例中的语义冲突都导致了编程语言规则错误,错误能由编译器捕捉,错误容易发现.在下文案例中,当两个站点的编辑操作广播到对端时,虽然未发生编程语言规则错误,却引起了编程逻辑错误,是一种较为特殊的语义冲突场景.如图3所示:
1)在站点0上,用户u0增加了一行代码逻辑location-=1.对变量location的值减1.
2)在站点1上,用户u1增加了一行代码location++,对变量location的值加1.
图3 逻辑错误场景Fig.3 Logical error situation
用户u0实现Get方法返回在location-1位置上的数据,而用户u1的编辑操作却实现了获得locaiton+1位置上的数据.并发的编辑操作到达对端站点时,并未导致编程语言错误.但是由于用于对相同的变量的编辑,产生编辑意愿重叠,从而实际实现的编程效果并未遵循用户的编辑意愿,导致了编程语言逻辑错误,语义冲突发生.
以上列举的3个案例是实时协同编程环境中比较有代表性的案例,语义冲突的情况还有很多,本文不在一一列举,情况3导致的语义冲突在3.5节中进行相关分析.
3.5 依赖图的动态变化分析
由于代码文档的高复杂性及依赖图结构的动态变化,极大的增加语义一致性的维护难度.对于基础域的编辑操作可能产生新的依赖关系,即调用新的方法,或是引用了新的参数,或者取消原有的依赖关系(删除了调用的方法,或是删除了引用).基于对代码域的编辑,编辑操作对依赖图结构依赖关系的影响可以分为3种情况:
1)编辑操作产生了新的依赖关系,依赖图结构发生改变.
2)编辑操作消除了部分或全部依赖关系,依赖图结构发生变化.
3)编辑操作消除了部分或全部依赖关系,且产生了新的依赖关系,依赖图结构发生改变.
情况1.如图4中的(a)部分所示,该部分左侧结点C是一个独立的基础域,用户u0对节点C的编辑产生了新的依赖关系C→B.右侧中用户u1对结点B的编辑产生了新的依赖关系B→C;
情况2.如图4的(b)部分所示,(a)部分中左侧用户u0对结点C的编辑取消了对结点B的依赖.右侧中用户u1对于依赖图结点B的编辑取消了对结点C的依赖.
情况3.如图4的(c)部分所示,用户u0关于结点C的编辑操作即取消了原有的依赖关系,且增加了新的依赖关系.
图4列举了依赖关系动态变化的3种情况.在协同编程环境中基础域被调用、引用或是取消调用、引用的情况十分普遍,故支持动态依赖关系的语义一致性维护在协同编程环境中是转关重要.值得强调的是,动态依赖图语义一致性维护难点在于并发的编辑可能导致各个站点上的依赖图不一致问题,而操作的发送只基于当前站点的依赖图结构,当操作到达其它站点若按原站点的依赖图结构执行亦可能导致语义错误.
图4 动态依赖图Fig.4 Dynamic depency graph
3.6 不完整的编辑操作
不完整的编辑操作指的是编辑还未完成或是编辑操作在编译器上存在不符合编程语言规则的情况.通常,不完整的编辑操作直接导致编程语言规则错误,且编译器中实时的出现错误提醒.不完整的编辑操作大致可以分为两种情况:
1)基础域中的内容编辑未完成或是不符合编程语言规则.
2)对于基础域的编辑操作,破坏了原有的依赖关系,导致了编程语言规则错误(破坏了原有的依赖关系,且符合编程语言规则的编辑操作,不属于不完整的编译操作的范畴).
情况1.如图5的(a)部分所示,在站点0上,用户u0向list类中添加方法void clear(){,但是符号‘{’少匹配了符号 ‘}’,违背了编程语言规则,即用户u0新添加的代码存在编程语言规则错误.且站点1执行了用户u0的存在编程语言错误的编辑操作导致该站点也出现编程语言规则错误.广播存在错误的操作可能带来许多不必要的麻烦.例如,若存在多个用户发现用户u0的错误代码,且并发的进行了修改,无形中增加了并发编辑及语义冲突的概率,降低了协同的效率.
图5 不完整的编辑操作Fig.5 Incompleted editing operation
情况2.如图5的(b)部分所示,站点0上用户u0将结点b中的变量length修改为m_length,由于该操作破坏了原有的依赖关系(结点e丢失依赖节点b),故对length的修改将引起所有引用变量length的基础域发生编程语言规则错误.在站点1上执行用户u0的编程操作将出现与站点0上相同的错误.用户需将结点e中变量length也修改为m_length或者是删除变量length,才能消除错误.若将结点b,e的变量length都修改为m_length,再打包发送结点b,e的编辑操作集合到其它站点,将避免上述不完整的编辑导致的编程语言规则错误.上述两种情况都将视为不完整的编辑操作.广播错误操作可能造成许多没有必要的麻烦.通常不完整的编辑操作产生的错误能得到编译器错误警告,并不是难以避免的,明知存在错误却仍发送错误的操作是不符合常理的,且广播存在错误的编辑操作到其它站点上,势必导致其它站点上的代码发生错误.从开发者的角度来说,提交或广播的代码应该是完整的(不存在编程语言错误),不完整的代码很难让协同工作者明白,接收到新的代码的作用、有无意义.若不完整的代码存在错误甚至可能影响了协同工作者的编码.故发送的编辑操作一定是完整的编辑操作.不完整的编程操作源于用户的编辑行为违背了编程语言规则,且并不是并发冲突导致的,故无需特殊的检查条件,只需判断此时编译器是否报错即可.
3.7 编辑操作的发送
文中对代码域的编辑自动发送设定为当用户开始工作于某个代码域视为工作开始,当用户离开当前代码域或是进入新的代码域视为完成编辑工作,编辑操作自动发送.当用户离开当前代码域或进入新的代码域,若编辑操作为不完整的编辑操作,该代码域的编辑操作不发送.发送的编辑操作应当是对应是代码域为完成状态下的编辑操作集合(完整的编辑操作).编辑操作在未发送前,操作集合存储在本地编辑队列(EditQueue)中等待发送.例如,图6的(a)部分对应图1中list类中添加clear方法,操作O1=insert(void clear(){;,20,0),操作O2=insert(},20,14).关于依赖图结点i的操作集合为EditQueue_i={O1,O2}.以此类推,图6中的(b)部分中修改结点b的完整编辑操作集合应当为EditQueue_b={O3}与EditQueue_e={O4}.
图6 完整的编辑操作Fig.6 Complete editing operation
4 自动比较与交换冲突消解方法(ACAS)
文中通过几个较有代表性的案例,分析语义冲突可能产生以及动态依赖语义冲突发生的场景.从上述的案例中我们不难发现协同编程系统无法判断非编程语言规则错误的操作是否存在语义冲突,若编辑操作为排斥关系,只保留一个操作,其它编辑操作将会被拒绝,又或是被保存.考虑操作不兼容的问题及减少协同编辑限制,本文基于SUN,FAN等人的研究,在网络稳定的前提下,采用复制式结构,结合CAS的并发控制思想以及依赖图的动态变化场景设计了实时协同编程环境的语义冲突消解方法ACAS.
4.1 ACAS算法设计
4.1.1 依赖图结点标识码(Tag)
本文对每个基础域添加标识码,标识码用于对比分析基础域的变化情况.通过判断标识码的变化情况,分析编辑操作是否存在语义冲突发生.标识码为一个三维向量,例如Tag(0,0,0).向量中,左值表示为UpStreamTag(UST),中值为DownStreamTag(DST),右值为SelfAreaTag(SAT).依赖图结点的标识码为对应基础域的标识码.
1)UpStreamTag:该基础域依赖的其它基础域的编辑操作会导致UST自加.
2)DownStreamTag:依赖于该基础域的所有基础域的编辑操作会引起DST自加.
3)SelfAreaTag:编辑操作在当前的基础域执行后SAT自加.
标识码只有在编辑操作成功执行后才能自加.
例如:C→B→A,假设结点A、B、C的标识码都为(0,0,0).当基础域B完成编辑工作.结点B的SAT发生改变,此时的基础域B的标识码为(0,0,1),由于结点C依赖于结点B,因此结点C的UST发生改变,结点C的标识码更新为(1,0,0).即结点B的编辑操作执行后,影响SAT的同时,影响结点A的DST,结点B的UST.
4.1.2 相同结点标识码的比较
存在两种站点i,j.两个站点上相同的结点x的标识码为(1,1,1).
Ti =(1,1,1),Tj=(1,1,1)证明在站点j和站点i标识码不变,没有影响结点x的操作.
Ti =(1,1,1),Tj=(1,1,2)证明在站点j上的结点x已经发生变化.Ti=(1,1,1),Tj=(2,1,1)证明在站点j上的结点x的依赖的其它结点发生变化.
Ti=(1,1,1),Tj=(1,2,1)证明在站点j上依赖于结点x的其它结点发生变化.
标识码相同时,证明该结点未被修改.若标识码不相同,可能存在语义冲突的情况,在依赖图结构不变的前提下,存在语义冲突,需要进行冲突消解.若依赖图结构发生改变,需要通过对依赖图结构进行分析后,判断语义冲突是否发生后,再进行相应处理.
4.1.3 基础域状态
本文对基础域添加了二个状态.每个基础域都有一个相对应的工作状态.基础域的工作状态分为两类:
1)Editing:基础域处于编辑状态.
2)Completed:基础域处于完成编辑状态.
当用户进入某个基础域,该基础域的工作状态,变为Editing.当用户离开该基础域或进入新的基础域,且产生的编辑操作为完整的编辑操作将视为代码编辑完成,基础域的工作状态变为Completed.
定义5.编辑操作优先.
1)假设存在两个基础域A、B,且B依赖于A,且并发的两个操作O1,O2分别作用于基础域A,B,操作O1优先于操作O2.操作O1优先更新的原因在于,若无并发的编辑操作,通常对基础域A的编辑可能影响到基础域B,而不论基础域B如何变化,对基础域A都不产生影响.
2)存在一个基础域A,如果存在对基础域A的并发的编辑操作.在编辑操作不改变依赖图结构的前提下,优先执行优先高的操作(站点号越小优先级越高).为避免单纯使用优先级在动态依赖图中带来的代码文本不一致问题,若编辑操作导致了依赖图结构发生变化,优先执行依赖图结点中依赖关系数较少的编辑操作.
定义6.编辑操作等待.
1)如果在某一基础域正处于Editing状态,其它站点关于该基础域的编辑到达时进行操作等待,直到该基础域编辑完成.
2)若基础域的编辑操作标识码SAT大于当前基础域的标识码,证明该操作为未来操作,需进行操作等待.
4.1.4 代码域内容的撤销与恢复
考虑到依赖关系动态变化及语义冲突导致编辑操作不兼容的问题,存在一些不得不撤销的编辑操作.很容易想到是采用OT技术的历史缓存进行undo-redo操作,但历史缓存数量较大时,undo-redo不是一个特别高效的方法.为了提高代码文档内容撤销与恢复的效率,文中采用版本技术记录编辑操作,并通过版本覆盖的方式恢复代码,且多余的版本将被删除或是被保存.
定义7.代码域版本(DepencyGraphicVersion).
代码域的版本以基础域为基本单位,每个基础域都有其对应的代码域版本.在每个站点上,用户创建一个新的基础域,或者在某个代码域成功执行的操作都会创建一个新的代码域版本,存储在本地,组成基础域的历史版本.代码域的版本号为其所对应的基础域的标识码的值.若存在代码域版本恢复的情况,该基础域的标识码及相关标识码需伴随着版本恢复回退至原先的值.
基础域的版本存储是有十分有意义的,复杂软件的开发往往具有较长的开发周期及庞大的代码量,可能需要对代码进行反复的修改.存储代码版本,开发人员可以通过历史版本,查看代码修改历史,能够直观的判断之前的修改目的,甚至当代码出错时判断出错原因,以及不再需要担心代码内容丢失或是难以恢复.
如图7所示,在站点0上,结点i当前的代码域版本为版本(0,0,0).当用户u0编辑了结点i,若操作成功执行,将生产新的代码域版本(0,0,1).假设此时存在其它用户的编辑操作与用户u0的操作存在语义冲突,且操作相互排斥,需要撤销用户u0的编辑操作,此时只需要执行revert操作将代码版本恢复至未修改前的版本(0,0,0)即可.用户u0的操作产生的结点i版本(0,0,1)将会被删除或被保存.从用户体验的角度考虑,若保存用户u0生成的版本(0,0,1),相当于保存了用户u0的工作,通过版本对比,分析当前节点i版本与用户u0的版本存在的差异,保存代码版本能更好的帮助用户工作.从节约资源的角度考虑,结点i已经恢复至版本(0,0,0),此时版本(0,0,1)是无效版本(产生语义冲突的代码域版本),删除即可.文中采用的方式是将无效的代码版本保存.
4.1.5 操作请求
文中将操作请求定义为一个二元组
Node为一个结构体其中包含了以下信息:
1)Id:结点id,通过id在依赖图中找到该节点.
2)Tag:结点标识码,用于判断语义冲突是否发生.
3)EditType:关于基础域的编辑类型,新建一个基础域用1表示,删除基础域用-1表示,编辑基础域表示为0.
4)EditQueue:用于保存基础域的编辑操作集合.
5)RootNode:未编辑前,结点直接依赖的其它结点集合,用于判断依赖图结构是否发生变化.
6)NewDepency:记录新增的依赖结点或减少的依赖结点,新增的结点表示为+Nodeid,减少标识为-Nodeid,在依赖图结构发生变化时用于判断语义冲突是否发生.
7)NodeVersion:记录当前基础域的版本号,用于语义冲突发生时,进行代码域版本恢复.
4.1.6 ACAS的数据结构
如文中将代码文本划分成多个代码域,存在代码的基础域对应一个标识码和编辑状态.ACAS表中记录代码文档中所有基础域对应的依赖图节点信息.ACAS表中记录节点信息随着节点状态的动态变化而改变.如图8所示,图左表示代码文档的划分,图右侧为ACAS table,表中记录节点A、B此时的标识码状态和编辑状态(C:Completed,E(Editing).
图8 ACAS数据结构Fig.8 Data structure of ACAS
4.1.7 编辑操作执行许可条件检查
1)基础域工作状态为Completed.
2)基础域的标识码中除DST外其它标识码需相等.
只有符合上述两个条件的操作才能成功执行.
4.1.8 ACAS算法设计
结合编辑操作执行许可检查条件,ACAS算法设计描述如下:
Algorithm 1:用于获得操作落入的代码域,如代码域为一个空白区域,需要新建一个基础域,并将基础域的编辑状态更新为editing.由于用户在进行编码过程中,可能收到来自其它站点上工作于相同代码域的用户并发操作,而导致语义冲突.为了消除这种情况带来的语义冲突,处在编辑状态下的代码域不接受其它站点的编辑操作直到编辑完成,其它站点的编辑操作,需等待本地编辑完成后才能执行.
Algorithm 1.GetWorkArea(O)
w:=GetArea(O);
if(w==NULL)
Area temp=CreateArea();
temp.workStaus=editing;
else w.tagStaus=editing;
Alogrithm2:对本地的编辑操作进行更新检查.代码域处在editing状态时,收到的远程站点的操作将会被保存在等待队列中等待执行.故本地生成的操作在发送之前需要判断等待队列是否为空,若等待队列为空,本地生成的操作成功发送,否则,编辑操作不发送,保存本地上已经执行编辑操作并撤销这些操作.之后,执行等待队列中的操作.
Algorithm 2.LocalUpdateCheck()
if(waitQueue()==NULL) return success;
else stop boardcast;
save()and revert(t);
for_each(auto x:waitQueue()) do x;
Algorithm 3:若编辑操作在基础域上成功执行,在本地站点上将会立即生成一个新的基础域版本.如:执行save操作或是对基础域的成功修改也生成一个新的代码域版本存在本地,版本号为立即生效后的标识码的值.代码版本用于记录代码的编辑历史以及代码的恢复.
Algorithm 3.createNewVersion(tag)
if(update_success) createNewVersion(tag);
if(save(tag)) createSaveVersion(tag);
Algorithm 4:检查操作编辑类型,若是创建一个新的基础域,操作立即执行.否则,检查操作请求的标识码与本地将要执行该操作的结点标识码是否相同,如果标识码相同,操作执行,如果不同,根据标识码变化类型进行相应处理.
Algorithm 4.RemoteUpdateCheck()
if(Node.editType ==1) return success;
if(equal(tag)) return success;
switch(change_type(tag)){
case UST_Change:UpStreamTagChange();
case SAT_Change:SelfAreaTagChange();
case DST_Change:DownStreamTagChange();
default:error(“type error”);break;}
Algorithm 5:由于代码文档的复杂性,编辑操作可能导致依赖图结构发生变化而导致语义冲突发生,故在远程站点上操作的执行需要检测基础域的依赖情况是否变化.首先判断NewDepency(ND,用于记录编辑操作产生的新依赖关系)是否为空,如为空,编辑操作未导致依赖图结构变化,语义冲突发生,编辑拒绝.如果发生改变,若增加了新的依赖域,需要考虑增加的依赖域的标识码是否发生改变,若标识码改变,则操作被拒绝.如果依赖域减少了,减少的依赖域不应该在对编辑操作将要执行的结点标识码产生影响,判断UST变化的值是否受到减少的依赖域的影响.排除减少的依赖域的影响后,若标识码相同,则证明不存在语义冲突.若UST的改变不存在语义冲突,再检查其它标识码的变化情况,若其他标识码未改变,则更新成功.
Algorithm 5.UpStreamTagChange()
if(ND.isEmpty())return reject;//(R==Remote)
else{
for_each(auto x:ND){
if(x.changeType==del && x∈R_x.rootNode){
times=|x.UST-R_x.UST|+|x.SAT-R_x.SAT|;
if(times !=|operation.UST-target.UST|) return reject;
else if(x.changeType==add){
if(x.tag !=Rx.tag) return reject;}
if(SAT_Change) SelfAreaTagChange();
if(DST_Change) DownStreamTagChange();}}
return success;
Algorithm 6:若SAT改变,证明存在对相同代码域的并发操作,通过标识码在远程站点中的请求日志找到并发的操作,对比操作之间的优先级,若操作请求的优先级大于当前站点的操作,则进行版本恢复,并撤销该并发操作对站点标识码的影响.同时检查DST是否改变,若DST未改变,进行DST变化检查.
Algorithm 6.SelfAreaTagChange
Rrequest = Log.find(tag);
if(Rrequset.Prop < operation.Prop){
revert(tag);
if(DST_Change) DownStreamTagChange();
return success;}
return reject;
Algorithm 7:若DST改变了,证明DownStreamNode中存在语义冲突的编辑操作.由于依赖关系的动态性,只比较编辑结点的标识码已经无法确定可能产生语义冲突的基础域.需要通过对比站点间的DownStreamNode的SAT的变化情况来确定是哪些代码域的编辑操作导致了DST的变化.若DowmStreamNode中结点的SAT不一致则证明语义冲突存在,应撤销导致SAT变化的编辑操作,消除冲突.
Algorithm 7.DownStreamTagChange()
subtract=operation.DST-RNode.DST;
for_each(auto x:DSNode && substract){
if(x.Version==Rx.Version)continue;
else{ temp-=Rx.Version-x.Version;
save()and revert();}
if(subtract)return success;}
return success;
4.2 实例分析
本小节着重介绍一个语义一致性维护的综合性案例,描述上小节中控制函数是如何维护协同编程环境下的语义冲突.
如图9所示,站点1、2、3上的操作O1、O2、O3分别作用于结点A,结点C和结点E.操作O1对结点A进行了修改,操作O2取消了结点C对结点A的依赖,故结点A的任何变化都不在对结点E产生影响.操作O3取消了结点E对结点C的依赖.当操作O1到达站点2,3时,通过Algorithm4判断标识码未发生改变,不存在语义冲突,操作O1成功执行.操作O2到达站点1时检测到结点C的UST发生改变,可能存在语义冲突,由于依赖图结构发生改变,通过Algorithm5处理后回退结点C的标识码,此时结点C的标识码与操作O2的标识码相同,无语义冲突,操作O2成功执行.同理操作O3也成功执行.操作O4,O5,O6,分别作用于站点1的结点D,站点2的结点D,站点3的结点A.当操作O4到达站点2时检测到结点D的SAT发生改变,此时语义冲突发生,通过Algotihm6
图9 案例分析Fig.9 Case analysis
处理后,撤销操作O5对结点D的影响,执行操作O4.操作O5到达其他站点时根据定义,操作将会被拒绝,由于操作O6工作于独立的基础域不产生语义冲突,操作成功执行.经过ACAS方法进行语义冲突消解后获得代码文档满足收敛性.
5 CoCode原型系统
为了验证ACAS算法及相关函数的可行性与正确性,本文在Windows平台下使用VS2015,C++语言编码开发了实时协同编程环境的原型系统CoCode.前端模块功能基于QT框架实现,后台服务器端逻辑基于SeaStar异步通信框架实现相关业务功能与通信事件的监听.本文在多台设备上安装了CoCode原型系统,登入的用户可通过图10左侧的文件目录访问不同或相同的代码文档并进行协同编辑.图10的中部为协同编码区域,用户所在的编辑代码行将存在颜色高亮.图10右侧为OnLineEditor模块与Information模块.OnlineEditor模块记录参与协同编辑工作的所有在线用户.Information模块用于记录用户实时交流信息、代码提交的反馈信息及代码域内容变更的提醒信息.图10的下方为当前代码的输出显示框,上方为系统菜单栏,其中包含了create、save、undo、redo、build、run、submit、download等功能.
图10 原型系统CoCodeFig.10 CoCode prototype system
6 实验分析
复杂软件的开发往往需要较长的周期,需要较多的开发人员参与,且软件的源代码文档数量较多.实验不考虑开发周期因素,将从开发人员数与源代码文档数两方面着手进行实验分析,本文将ACAS方法与DAL方法应用于协同编程环境进行效率对比分析.DAL方法不考虑出现shared-locking[7]时依赖于用户交流维护代码文档的情况的前提下,针对两种方法处理语义冲突的一致性维护时间进行对比.针对一致性维护时间与协同站点数量做了相关的测试,仿真协同编程环境的语义冲突消解及一致性维护实验.
实验1.以共享文档为实验对象,对共享文档划分代码域及依赖关系构建依赖关系表,通过修改表中数据实现ACAS方法中标识码的改变或是DAL中基础域的锁的状态改变,表中数据的修改即标识相对应的代码域发生变化.从实验结果图11可以看出ACAS方法语义冲突消解的处理时间略小于DAL方法,但相比于DAL方法,ACAS采用了版本恢复的方法增加了空间复杂度.同时可以看出不论是ACAS方法或是DAL方法,在文件数量固定的情况下,随着协同站点数量的增加,一致性的维护时间都稍有提高,站点数量对协同编程环境下的一致性维护具有一定的影响.同时为了验证代码文档数及站点数对ACAS方法的一致性维护时间的影响,本文进行了实验2.
图11 ACAS方法与DAL方法对比图Fig.11 Contrast of ACAS and DAL
实验2.对3种不同协同站点数在协同文档数量相同情况下验证ACAS方法的一致性维护效率,前提条件及实验方法与实验1相同,通过增加协同编辑文件的数量检验协同工作的一致性维护时间.由图12可知,在代码文档相同时,站点数越多一致性维护时间越长.若站点数相同时,一致性维护时间随着协同编辑的文档个数增加不断减少,且趋于平稳.通过实验分析,可以推断的是,基于ACAS方法的实时协同编程环境较为适用于小型团队的系统开发工作.
图12 文档数与站点数的对比图Fig.12 Contrast chart of files and sites
7 总结与展望
ACAS方法是实时协同编程环境下的一种新的语义冲突消解方法.本文深入分析协同编程环境的动态依赖关系带来的语义不一致问题,及不完整的编辑操作带来的编程错误,在P2P环境下基于CAS的并发控制思想设计了ACAS算法,并通过标识码对比函数及相关冲突消解方法实现了语义冲突检测与语义冲突消解.为了验证该算法的可行性与正确性,在Windows平台下开发了实时协同编程环境的原型系统CoCode并进行了相关仿真实验,以有效的实现多用户间的协同工作.
由于代码文档的复杂性,ACAS方法在一些较为特殊的应用场景下然存在一些问题,在未来的工作中,将致力于完善ACAS方法,以及实现多文件之间的语义冲突消解的研究.
