移动云平台下基于局部复制的结构性文档协同编辑冲突消解

2018-10-17朱思征高丽萍王山山

小型微型计算机系统 2018年10期

王丹,朱思征,高丽萍,王山山,徐烨,史旻

1(上海理工大学计算中心,上海 200093)

2(上海理工大学光电信息与计算机工程学院,上海 200093)

1 引言

计算机技术的不断发展,使得人们的日常工作、生活、娱乐方式也随之发生翻天覆地的变化.办公地点随着宽带、无线网络的普及,也不再局限于办公室.近年来,由于各行各业不同领域工作量以及设计规模不断增大,个人想要独立完成所有工作往往面临操作量巨大、用时长等一系列诸多问题.由此计算机支持的协同工作(Computer Supported Cooperative Work,CSCW)技术被提出[1].

实时群组编辑器支持分布在不同区域的用户同一时刻编辑同一个共享文档.全复制式架构(full replication architecture)[2-6]中提出在每个协作用户本地生成副本并对其操作,并将操作类型划分为本地和远程两类,此方法大大提高了本地操作响应速度.而在保证实时协同编辑系统的可用性和准确性[2-6,10-12]方面同时迸发出若干问题,并发控制技术作为攻克这些问题的关键技术,一直被更多的研究人员们逐步完善.并发控制技术[10-12]主要包括一致性维护和冲突消解两部分,一致性维护侧重于保证协同站点副本的一致性,冲突消解则是为了能够在最大程度上满足多用户的意愿.最典型的并发控制算法主要有操作转换算法(Operation Transformation,OT)[13]和地址空间转换算法(Address Space Transformation,AST)[6].

基于全复制式架构研究的冲突消解算法与开发的协同编辑应用不胜枚举,其研究成果已相对成熟.但随着移动设备的快速发展,大量编辑器若想要被移植到移动端,将面临存储空间小,内存有限等一系列的问题,最终导致之前研发的实时群组编辑器无法完全的适用于移动设备.而之前的研究成果多是基于全复制式架构的主要原因,是协同编辑的对象多为普通的线性文档,层次结构较为模糊.但在现实生活或工作中,结构性文档的使用率相对更高,例如常见的申请专利或软件著作权等书面材料,具有规定的模板结构;撰写不同的专著、书籍同样存在各自的参照模板结构;如果可以将此种具有结构的文档,按照层次级别、关联关系进行分类,让协同编辑者可以各取所需,将在很大程度上提升用户效率并节省存储空间.Huanhuan Xia[7]等人提出了局部复制式架构(partial replication architecture),并基于此复制式架构研发了适用于移动端的评论系统,为结构性文档协同编辑领域的研究奠定了基础.

计算能力较弱,是移动设备的又一个严重缺陷,随着编辑工作量的增大,协同用户的增多,即使使用普通的服务器也很难处理庞大的操作集.因此,近年来发展迅猛的云服务器技术成为了解决此问题的关键.云服务器又称为云主机,在架构上与传统的服务器又很大区别,它能够接收庞大的数据输入量[8],高效处理海量数据集[9],并基于集群服务器技术,虚拟出多个独立服务器部分,其具备的故障自动迁移和快照备份功能,大大提升了存储安全性.

本文的结构如下:首先对局部复制基本思想进行简要介绍,针对本文提出的算法给出文档结构、节点、操作、冲突类型等基本定义;随后详细介绍移动云平台下基于局部复制的结构性文档协同编辑冲突消解算法,针对不同的冲突类型,给出不同的消解过程;其次是对本文提出的算法进行效率分析,将算法与实例相结合,验证其准确性;最后提出后续的主要研究内容.

2 相关工作

1989年,Eliis 等人[13]首次提出操作转换概念,并建立OT[13]算法基本模型,其中提出的dOPT(distributed Operational Transformation)作为第一个基于OT的算法被运用到Grove协同编辑系统中.然而,dOPT在某些场景下协同站点间结果会出现不一致的问题,被Ressel[14]等人发现.一致性维护技术的研究成为协同工作中的热门问题.1998年 Sun在早期的一致性模型基础之上提出了CCI(Convergence Causality Intention)[15]模型,指出更为严格的一致性标准——意愿维护,即冲突消解策略侧重解决的问题,由此,并发控制技术的研究得以完善.围绕该一致性模型,一系列基于OT的乐观并发控制技术被提出,如GOTO[15]、COT[10]、SCOT4[16]、LBT[17]、TIBOT[18]、ABST[11]等.由于OT的操作转换规则较为复杂,准确性证明比较困难,执行效率较低.一种基于地址空间转换的一致性维护技术AST被提出,对比OT,AST算法效率更高,并被证明可以准确解决已有的并发控制问题.近年来,OT和AST技术被广泛运用到实时群组编辑领域[23],并研发出诸多协同应用,例如 SketchPad、Co-CAD[19,20]、Co-eclipse[21]等.但这些研究目前只能够适用于桌面协同应用系统,很难将其平移到移动设备上使用,其中最主要的问题在于移动设备存储空间有限,计算能力较弱,且之前的研究成果多是基于全复制式结构,致使移动设备很难应对数据量扩张,操作数上涨的情况.面临此困境,Huanhuan Xia[7]等人在2014年提出了适用于移动端的评论系统,并在考虑移动设备内存限制以及网速较差的前提下,提出了局部复制式架构,利用评论节点存储用户请求的详细内容,根据部分复制规则生成骨干节点从而生成本地局部副本,相比全复制式架构,大大节约了存储本地副本的空间,节省了副本更新的时间.2016年,Sun等人提出了CSOT[22](Cloud storage Operational Transformation)算法,能够支持在云存储下实时文件同步功能,并维护一致性,实现理想的并发操作效果合并.CSOT算法首次将OT的一致性维护能力扩展到云存储共享空间中,并为基于云的协同技术发展做出了巨大贡献.

然而,CSOT算法的操作粒度为文件,粒度较大,对于文件内容的更改,也只局限于对内容的整体更新覆盖.且在之前的并发技术研究中多是基于全复制式架构,考虑到移动设备的存储空间和计算能力的限制,本文基于局部复制策略的基本思想,将控制算法部署在云服务器下,提出一种适用于移动终端的结构性文档协同编辑冲突消解算法,简称为MCPS算法.

3 准备工作

3.1 局部复制方法回顾

局部复制策略是一种适用于移动评论系统,为了解决移动设备资源有限、评论的突发性等问题,利用树形结构存储请求数据,并基于地址空间转换算法研发的高效一致性维护算法.

图1 局部复制原理图Fig.1 Principle of partial replication architecture

如图1所示,中央服务器负责维护评论会话的主副本(Primary copy),各个协作客户端维持本地副本,称为部分副本.当有新用户加入并向服务器请求评论内容时,请求的评论将通过操作的形式返回,而返回的数据在客户端以节点构成的“骨架树(skeleton tree)”结构存在.通过“释放”骨架树中的数据构建部分副本,同时将本地副本通过SYNC请求与主副本同步.对于同步过程中创建、插入、删除和更新等操作产生的冲突,该策略采用地址空间转换技术解决,给出具体执行规则,并实现数据的一致性维护.

需要强调的是,当以增量的形式构建本地部分副本时,需遵循如下规则:“如果一个评论节点被复制,该节点的父亲节点(如果存在)也必须被复制”.为了区分同步节点类型为请求同步还是自动同步,Huanhuan Xia等人将骨架树种的节点大致分为三种:评论节点(comment node),即客户端请求的节点,包含评论内容数据;骨架父节点(skeleton parent node),作为请求节点的未被请求的父节点,自动同步到骨架树中,但不包含评论数据;骨架叶节点(skeleton leaf node):作为请求节点的未被请求的兄弟节点,为在客户端副本保持一致的节点兄弟关系而自动同步到骨架树种的节点,同样不包含评论数据.

图2 骨架树示例图Fig.2 Example of skeleton tree

举例说明,如图2中的用户B,当其加入到协同评论会话中时,本地的初始部分副本为空,首先发出一条FETCH请求,请求的评论节点集为{T,D },在生成骨架树时,检测节点D拥有父节点B,此时将自动同步节点B到骨架树中,并标记为骨架父节点,且D有一个兄弟节点为E,则标记为骨架叶节点.“执行”骨架树构建本地部分副本时,部分副本中只包含评论节点中的数据.

3.2 基本定义

3.2.1 文档结构定义

图3 等级标题结构文档Fig.3 Structured document

如图3所示是一个具有等级标题结构的文档,我们将此类型的文档抽象,通过树结构存储在云服务器端,即以DOC为主根节点(主副本为空时,首先分配一个id=0 的DOC虚根节点,用来维护主副本树结构的完整性),按照标题等级构建主副本树——StrTree,我们将图3中的文档构建成StrTree的结果如图4所示.

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

而客户端通过请求节点在本地生成的部分副本,可以视为StrTree中的一个子树.子树中包含三种节点:

标题节点(TN:Title-Node):客户端请求节点;

结构父节点(SPN:Str-Parent-Node):客户端请求节点的父节点,且未被请求,为了维护副本树结构复制在客户端但不包含文本内容;

结构兄弟节点(SBN:Str-Brother-Node):客户端请求节点的兄弟节点,且未被请求,为了维护副本树结构复制在客户端但不包含文本内容.

增量式构建本地副本遵循的规则参照文章3.1的介绍.子树中的节点类型,会在客户端每次向云服务器请求数据后进行更新.

3.2.2 节点属性定义

对于StrTree中的每个节点,我们给出以下定义和若干属性:

表1 节点和属性定义Table 1 Definition of node and basic parameters

这里我们提出了活跃度概念,是为了能更大程度上维护用户的操作意愿,当在协同操作的过程中产生冲突时,解决方式不再局限于判定时间戳、用户优先级等因素,而是通过云服务器动态更新各个客户端在每个节点和每棵子树的活跃度,以活跃度越高,越优先执行为原则,决定操作的执行先后顺序.

3.2.3 操作定义

1)Append(N):增量获取节点集N的数据,请求和执行方式与文章[7]中类似;

2)Insert(parentId,id,site,data):在父节点parentId的子节点后,插入一个新节点;

3)InsertBefore(parentId,refId,id,site,data):创建一个标识符和文本内容为id和data的新节点,并插入到标识符为parentId父节点下子节点队列中的refId节点前;

4)Delete(id,site):删除标识符为id的节点;

5)UpdateName(id,newName,oldName,site):更新标识符为id的节点的标题名称为newName,并记录之前的名称oldName;

6)UpdateData(id,data,site):更新标识符为id的节点下的文本内容为data;

3.3 冲突类型

针对上方提出的4种以标题为粒度的操作,1种以标题内文本内容为粒度的操作,我们分析得出了以下5类冲突情况.

CIB:InsertBefore()_InsertBefore(),当云服务器接收两个指定插入位置的节点插入操作,它们指向同一个父节点,且refId值相同时,操作在客户端的执行顺序不同,将产生不一致结果;

CII:Insert()_Insert(),与CIB的冲突情况类似,插入标题操作在客户端的执行顺序不同,产生的结果不同;

CD:Delete(),当客户端想要执行一个删除标题操作时,需先向云服务器发送删除请求,云服务器判定没有客户端在编辑以该节点为根节点的树后,同意删除请求,否则驳回;

CDI:Delete()_InsertBefore(),当一个删除操作被允许,云服务器同时接收一个InsertBefore操作,与被删除节点父节点相同,且被删除节点的refId与插入操作的refId相同,操作的执行顺序将影响客户端结果;

CUN:UpdateName()_UpdateName(),当两个操作同时更改同一个节点的名称时,客户端操作执行顺序不同结果不同;

CUD:UpdateData()_UpdateData(),与CUN类似,两个操作都欲更改同一个节点的文本内容时,客户端操作顺序不同将产生冲突.

4 MCPS算法设计

4.1 主副本更新监听器

为了记录客户端活跃度,判断执行操作的优先级,我们在云服务器开辟空间赋予CL(Cloud Listener),作为记录主副本变更的操作缓冲区,CL[n]表示节点n变更的操作缓冲区,CL[n]的结构为响应式增加site列的一张表(因为接下来要根据每个节点对应site的缓冲区大小计算对应客户端在该节点的活跃度即节点活跃度NLV,以及以该节点为根节点的树,树中所有节点对应site的缓冲区大小的累加值判断对应客户端在对这棵树的活跃度TLV),需要强调的是,为了保存所有节点的活跃度,当一个节点被删除,它在CL中依然存在,并且CL的更新不会影响StrTree.

过程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 控制算法

云服务器根据操作类型和操作中的节点属性,判断执行以下哪种冲突消解算法.

过程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消解过程

当云服务器端接受到来自不同客户端的InsertBefore操作,并检测到出现CIB冲突时,云服务器端需要通过判断生成插入操作的站点在此节点的树活跃度TLV,以及请求客户端传送插入节点对应父节点和兄弟节点的类型,并以节点类型为标题节点的客户端优先;节点类型相同时,对应站点在该节点父节点的的树活跃度越高,操作执行的优先级越高,其它插入操作的位置将进行适当调整,并将结果反馈给客户端.具体处理流程参照算法1,Oa和Ob操作分别插入两个节点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的消解过程与CIB同理,这里我们不再赘述.

4.4 CD消解过程

当客户端想要执行一个删除操作时,首先需向云服务器发送删除节点请求,若此时存在操作将要作用于以该节点为根节点的树,或删除节点在客户端部分副本中不属于标题节点,删除操作被驳回.具体处理流程参照算法2.

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

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

2. IF(na.deep<=nb.deep)//删除节点na是nb的祖先

3. {//由nb向上递归寻找父节点是否存在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消解过程

当一个删除节点操作被允许,且是另一个插入节点的兄弟节点,位置依赖于删除节点,为了保证插入位置的准确性,需要根据删除节点位置确认插入节点位置.

算法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消解过程

当存在若干操作都欲更改同一个节点的名称时,云服务器需要做出判断,采取哪个操作的结果,此时首先判断节点在发出更改操作客户端的类型,与CIB处理方式类似,类型为标题节点的操作优先,不同的是,若节点类型相同,对比站点在该节点的节点活跃度NLV,优先执行NLV高的站点发出的更改操作.

算法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的消解过程与CUN同理.

5 复杂度分析

本文提出的MCPS算法部署在云服务器端,处理进程分为两部分:动态更新各节点对应的的节点活跃度和树活跃度;检测冲突类型并消解冲突.

动态更新节点活跃度阶段,首先通过操作携带节点n的属性遍历Cloud Listener查找是否存在该节点信息,不存在则插入该节点;随后根据操作的生成站点id找到在CL[n]中对应的活跃度,先改变节点活跃度,再向上回溯更新它的祖先节点的活跃度,我们假设最糟糕的情况,查找到树中的最后一个节点才找到节点n,并要再向上回溯一次,N为树包含的节点总数,H为树的高度,则此过程所需的时间复杂度为O(N·H).

本文提出的六种冲突消解情况中,其核心首先时查找节点n,随后查找CL[n]中相关站点活跃度,最后插入节点或更改节点信息,可以简单理解为一个双重遍历的过程,假设找到节点n遍历过的节点个数为N,相关站点活跃度在CL[n]中存储位置最大的为L,则时间复杂度可以表示为:O(N·L).整个并发控制过程的最坏时间复杂度可以抽象为O(N2).

关于空间复杂度,因为将算法部署在云服务器,且加入的节点监听功能,并利用树结构存储主副本与监听缓存,假设主副本中包含的节点总数为N,那么对应的空间复杂度至少是O(2N),但对于移动客户端来说,空间复杂度将是一个小于或远小于O(N)的值.

6 算法实现举例

如图5所示,服务器端此时的主副本内容为图5(a)中结构树中的所有节点,当前的CL中各节点的活跃度如表2所示,表中的n0代表根节点DOC.有两个协同用户site1和site2参与编辑工作,并产生接下来的操作:

图5 主副本冲突消解结果Fig.5 Result of conflict resolution of primary copy

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

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

各自生成的部分副本子树如图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

执行Resolution_CIB(O1,O2)处理进程,两个协作客户端都欲在n2前插入一个新标题节点,首先判断DOC和n2节点在两站点被复制的类型,均为标题节点,接下来判断两站点在他们欲插入节点的父节点DOC的树活跃度:

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

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

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

树活跃度越高,操作执行优先级越高,所以先执行site1站点的插入操作,将O2操作转换为O2′= InsertBefore(DOC,n7,n8,site2,data),发送到站点1执行;O1操作不变发送到站点2执行.生成的结果如图6(b)和图6(e).CL中加入两个节点的信息,并更新site1和site2的活跃度.

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

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

执行Resolution_CD(O3,O4),site1发送删除请求至云服务器,同时接收到来自site2的操作O4,首先判断n1在site1的节点类型为标题节点,再判断n4的祖先节点中是否包含节点n1,因为n1是n4的父节点,所以删除操作被驳回,云服务器向site1发送O3操作取消指令和操作O4,同时更新site2的活跃度.

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

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

执行Resolution_CDI(O5,O6),O5是被允许之心的删除操作,n7.id等于O6.refId,所以优先执行O6,两站点部分副本更新后结构如图6(c)和图6(f).同时更新CL中对应的活跃度数值.

图6中两个站点最后生成的部分副本(图6(c)和图6(f)所示)中重叠的部分结构一致,证明了冲突消解算法的准确性;最后更新的CL中各节点的站点活跃度为表3中的数据.

7 总结及展望

随着移动网络逐步健全,移动设备迅猛发展,以及其具备的便携、对地理位置无约束特性使得人们更倾向于在移动终端上进行办公,移动网络环境下的协同研究及应用开发将成为未来科技发展的大趋势.但移动设备的存储和计算能力较弱,导致之前的协同研究成果不能完全适用于移动端.为了解决此问题,本文基于局部复制策略,提出了一种支持结构性文档协同编辑的冲突消解算法,并引入了云平台作为操作中转站,利用云平台强大的计算能力,解决协同过程中出现的各种冲突.创新的提出了用户活跃度这一概念,在最大程度满足多用户的意愿方面,不再仅仅依赖于判断客户端优先级、时间戳等手段,而是动态更新所有用户的活跃度,更合理的判断操作执行优先级.

后续的研究工作包括:1)优化算法执行效率,完善冲突类型;