高丽萍,陶长青

1(上海理工大学 光电信息与计算机工程学院,上海 200093)2(复旦大学 上海市数据科学重点实验室,上海 200093)

1 引 言

在短短的过去的几年时间里,我们见证了云计算、云存储以及移动计算技术的快速发展.云时代技术已经影响了人们生活的方方面面,成为了当下主流的研究以及应用技术之一.云存储是数据共享和协作的主要云计算应用之一,用户可以在云存储系统上访问和修改复制式文件,如同在本地计算机上操作,并将操作实时同步到数据中心以及其他用户站点上.伴随着云计算的不断发展,将其与计算机支持的协同工作(Computer Supported Cooperative Work,CSCW)技术结合,正成为了当下研究的热门领域之一.采用云的方案既能够实现用户随时随地协同办公和协同工作的要求,又能够使得开发者在专为用户设计应用时,无需担心受到操作系统、办公设备等限制,体现了良好的应用价值,从而可以大大提高人们工作的效率.其中,CSCW是指多个在地域上的分散的用户在同一时间并发地对共享的同一文档进行编辑,其强调的是人与人之间的交互,对交互过程中的响应性和并行性有着较高的要求.实时编辑系统作为CSCW代表性应用,要求协同效果即时可见,即协同用户之间的工作画面要维持一致.

随着云服务的逐渐流行,越来越多的传统办公软件被迁移到云端以提供更好的办公协作支持,而文件管理作为企业办公系统中的重要组成部分,合理且高效的管理文件对企业的工作进程来说起着巨大的作用.传统的文件管理方法是分配一个人对文件进行管理,但在这个信息量暴增的时代,这种工作模式带着强烈的主观意识且效率低下,其他用户想要在海量且庞杂的文件中找到所需文件并对其使用是极其浪费时间和人力的.而多人实时管理文件则是一个很好的适应信息化时代的文件管理的方法,通过多人协同管理,每个用户均可对自己所需模块的文件进行管理,不仅可以提高工作效率,还可在与其他用户的交互过程中清楚的了解其他用户在管理文件时的意愿,使得用户对文件的管理更加安全且提高了用户的体验度.因此,实时文件管理系统作为协同分布式交互应用的重要分支,对其研究具有较大的实际应用价值和意义.

在实时的管理文件的过程中,地理位置分布不同的用户在本地复制式文本上进行编辑操作并通过网络进行交互,其中面临的最大的挑战即是在用户协作过程中并发情况下如何维护共享工作空间的一致性,这对于协作系统的正确性和性能来说非常关键.而近几年CRDT技术被提出作为协作文本编辑中的新的并发冲突控制机制,已被证明其算法的性能优于传统的并发控制方法,且适用于树形结构共享工作空间中.本文针对非线性结构文件模型提出了一种基于CRDT技术的新的冲突检测和解决方法.本文将着重设计基于CRDT的新的冲突检测和解决方案,并在以下三个方面做出重要的贡献:

1)定义操作的依赖冲突关系、非依赖冲突关系以及兼容关系,并设计操作关系检测算法;

2)设计基于CRDT的冲突解决方案,来维护各个副本的最终的一致性,并同时尽可能多的维护用户的意图;

3)针对云环境设计合理的Client和Server端的控制算法;

4)举例证明其正确性并分析其效率.

2 相关工作

云存储是数据共享和协作的主要云计算应用之一,用户可以在云存储系统上访问和修改复制式文件,如同在本地计算机上操作,并将其实时同步到数据中心以及其他用户站点上.而实时协同编辑系统中复制式文件的一致性维护技术是保证系统正确性的根本.目前市场上比较常用的一致性维护技术有操作转换(OT,Operation Transformation)[1-3]、地址空间转换(AST,Address Space Transformation)[4-6]和可交换复制式数据类型(CRDT,Commutative Replicated Data Type)[7-9]等技术.其中,OT技术是最早提出的实时协同编辑系统下的一致性维护技术,在1989年由Ellis提出,是基于操作本身,根据并发操作产生和执行的效果,对操作中的参数进行修改,使得最终文本的一致性得到维护.AST技术是将文本状态回溯到操作产生时的状态,直接执行操作,并再次回溯状态,从而维护一致性.而CRDT技术则是设计操作可交换的复制式数据类型,在协同编辑过程中为每一个对象分配一个全局唯一标识符,从而可以实现对象间的可交换性需求,维护最终结果的一致性要求.目前CRDT技术多用于文本、二维图形以及3D图形的协同编辑系统的一致性维护中[7-10],还未应用到云存储以及文件管理系统下等复杂的环境中,因此本文着重研究云环境下采用CRDT技术的文件协同管理系统的一致性维护.

目前为止,云环境下的一致性维护技术还不是很普遍,Xia在文献[6,11]中对AST技术在移动云环境下的应用做出了研究,提出了基于标量时间戳的同步协议和基于全局标识符的地址空间转换策略,实现了移动云环境中用户画面的异步协同.而实时文件系统作为CSCW领域中重要的分支,近年来多位学者也对其进行了相关研究,例如Sun等在文献[12]中对云存储中共享工作空间的实时同步的操作转换做了研究,定义了各个基本操作(create,delete,update 和rename)在并发时期望得到的组合效果,并采用COT算法以避免需要设计转换函数来保证收敛属性2(CP2),设计了云存储下的操作转换函数(CSOT)来维护收敛属性1(CP1),其中CP1和CP2可以用来保证转换函数的正确性,以解决在云环境下文件存储以及管理中用户产生的操作冲突并达到理想的结果.L Gao等在在文献[13-15]中对协作图形编辑方面进行了研究,并改进算法将其应用到移动云环境下;在文献[16，17]中对实时云办公系统的文件管理的一致性维护做出了相关讨论,提出改进的COT算法以适用云环境下新的集中式架构,并在CSOT转换函数的基础上设计操作转换函数,解决基本操作之间并发时产生的冲突,使云环境下办公系统中对文件的管理能够达到更高的实时性要求.本文是对云存储中文件管理系统中采用CRDT的一致性维护技术上,设计合理的可交换式的数据和操作类型以解决并发操作之间冲突关系,并维护各个站点共享文档的一致性.

随着云计算技术的快速发展和普及,对部署在云上的应用程序的访问也越来越多,用户可以随时随地的使用本机设备对文件进行管理,当然这在交互响应和一致性维护方面也带来了很大的挑战.因此,采用协同编辑技术中的工作空间复制的方法来解决以上问题.不同于传统的P2P架构,本文针对云环境下集中式架构,设计合理的并发控制算法来解决基本操作(create,delete,rename和update)之间可能发生的并发操作冲突,并保证各用户的工作空间满足CCI模型.

3 数据模型和操作模型

3.1 基本数据结构

文件管理系统的复制式工作空间可以被定义为一个树模型:T=(N,A),其中N={N0,N1,N2,…}代表树中的节点集合,即云存储空间中的文件夹或者文件节点集合,A代表树中的箭头集合,即存储空间中节点之间的父子关系.每个节点N都有一个名称N.name,用一个字符串表示,为了简单起见,这里用大写字母′A′,′B′,…等表示;每个节点N上都有一个标识符属性N.OID,代表了作用在该节点上的最新的操作的唯一标识符.节点的路径是指从树结构中的根节点到某节点的父结点的名称所组成的字符串,代表了该节点的路径,如图1中,文件M的路径为A/G.

3.2 基本定义

定义1.特征依赖关系(|→ )

给定文件树模型中的任意两个节点N1和N2,当满足以下情况时则称N1依赖于N2,即N1|→N2.

1)N1和N2属于父子关系,即N1.parentname=N2.name;

2)存在一个节点Nx,使得N2.name⊂Nx.path且Nx.name⊂N1.path

定义2.优先级(P)

给定任意两个操作O1和O2,针对的对象节点为N1 和N2,当N1|→N2时,则针对该节点的操作的优先级为P(O1)>P(O2).

定义3.依赖冲突关系(⊕)

给定状态向量SV相同的两个操作O1和O2,当且仅当O1和O2的目标节点有依赖关系且以不同的顺序执行O1和O2后得到的结果不同时,O1和O2具有依赖冲突关系,记为O1⊕O2.

定义4.非依赖冲突关系(×)

给定状态向量SV相同的两个操作O1和O2,两者所针对的目标节点的路径之间没有依赖关系,且以不同的顺序执行这两个操作会产生不一样的结果.则称O1和O2是属于非依赖冲突关系,记为O1×O2.

定义5.兼容关系(Ө)

当给定的操作O1和O2的目标节点没有任何依赖关系时,即目标节点处于不同的子树流中,两者的执行顺序不影响他们的操作结果时,O1和O2属于相容的操作,记作O1ӨO2.

定义6.操作的唯一标识符(OID)

操作的唯一标识符是一个三元组,其中s代表站点间进行的会话的标识符,sumsv代表操作携带的状态向量的总和,site代表操作产生的站点的标识符.当满足以下情况时,OID(O1)

1)OID(O1)[session]

2)当OID(O1)[session]=OID(O2)[session]时,OID(O1)[sumsv]

3)当OID(O1)[session]=OID(O2)[session]且OID(O1)[sumsv]=OID(O2)[sumsv]时,OID(O1)[site]

定义7.操作的全局顺序(⟹)

给定双链表中的任意两个操作O1和O2,position(O)代表操作O在双链表中的位置,若P(O1)>P(O2),position(O1)OID(O2)时,则O1⟹O2.

3.3 基本操作类型

本文主要在create、delete、rename以及update操作的基础上进行分析和研究,操作的定义以及基本操作类型的介绍如下:

定义8.操作(O)

在文件管理系统中,操作O是一个八元组,其中,T代表了操作的类型,如create,delete,rename和update操作;l代表了操作是本地还是远程的,true本地,False代表远程;T-OID代表了操作的目标节点维护的唯一标识符,即目标操作的标识符;OID代表了操作的唯一标识符;指针next指向双链表中的下一个操作;指针prior指向双链表中的前一个操作,指针link用于哈希表中的单链表;状态s代表了操作执行时的状态.

1)O=Create(p,C,N):在路径名为p的文件夹下创建一个以节点N为根的子树T,该子树可以是一个文件夹节点,也可以是一个文件,C代表节点类型,文件或者文件夹.

2)O=Delete(p,C,N):删除路径为p的文件夹中的节点N.

3)O=Rename(p,C,N.name,N.nameNew):在路径为p的文件夹中名称为N.name的类型为文件夹或者文件改名为N.nameNew.

4)O=update(p,N,d):更新路径p下的文件节点N的内容为d.

4 实时文件管理中的一致性维护

4.1 操作冲突检测

文件管理系统中,基本操作有创建,删除,改名和移动四个基本操作,由于操作针对的对象之间存在依赖关系,以及操作之间的复杂的关系,使得并发操作产生时,不同的执行顺序会产生不同的操作效果,即产生冲突.所以,在集成远程操作时,操作之间会产生依赖冲突关系,非依赖冲突关系,以及兼容关系,在操作执行之前,需要对并发操作之间的关系进行检测.

表1 操作间的冲突关系表
Table 1 Conflict relationship table between operations

createdeleterenameupdatecreate×or×Өdeleteor×or×renameor×or×updateӨ

给定操作O1和O2分别作用于节点N1和N2,针对上文定义的4个基本操作,有如表1所示的操作对之间可能会出现的冲突关系.

1)O1=create,O2=create,当且仅当p1=p2,C1=C2且N1.name=N2.name时,O1和O2为非依赖冲突关系,称为O1×O2,其他情况为兼容关系,则称O1ӨO2.

2)O1=create,O2=rename,若N1|→N2,则O1和O2为依赖冲突关系,称为O1⊕O2;若p1=p2且N1.name=N2.nameNew,则O1和O2为非依赖冲突关系,称为O1×O2;其他情况均为兼容关系,则称O1ӨO2.

3)O1 =delete,O2=delete,若N1|→N2,则O1和O2为依赖冲突关系,若p1=p2且N1=N2时,O1和O2属于非依赖冲突关系.

4)O1=delete,O2=rename,若N1|→N2,则O1和O2为依赖冲突关系,O1⊕O2;若p1=p2,且N1=N2,则O1和O2为非依赖冲突冲突关系,称为O1×O2;其他情况下均为兼容关系,则称O1ӨO2.

5)O1=rename,O2=rename,若N1|→N2,则O1和O2为依赖冲突关系,O1⊕O2;若p1=p2且N1.nameNew=N2.nameNew或者N1=N2且N1.nameNew!=N2.nameNew,则O1和O2是非依赖冲突关系,称为O1×O2;其他情况下均为兼容关系,则称O1ӨO2.

6)O1=delete,O2=update, 若N2|→N1,则O1和O2为依赖冲突关系,O1⊕O2;其他情况下均为兼容关系,则称O1ӨO2.

7)O1=rename,O2=update,若N2|→N1,则O1和O2为依赖冲突关系,O1⊕O2;若p1=p2且N1=N2时,则O1和O2为非依赖冲突关系;其他情况下均为兼容关系,则称O1ӨO2

8)其他情况下,操作之间属于兼容的关系,则称O1ӨO2.

根据以上操作对之间的关系分析设计检测函数如算法1所示.

算法1.FindRelation(O1,O2)INPUT O1,O2If O1=create(p1,C1,N1),O2 =create(p2,C2,N2)then If p1 == p2 &&C1 == C2 && N1.name == N2.name then Return O1×O2 Else return O1ӨO2 End if Else if O1=create(p1,C1,N1),O2=rename(p2,C2,N2.name,N2.nameNew)then If p1 == p2&&C1 ==C2 && N1.name=N2.nameNew then Return O1×O2 Else if N1|➝N2 || N2|➝N1 then Return O1O2 Else return O1ӨO2 End ifElse If O1=create(p1,C1,N1),O2=delete(p2,C1,N2)then Return O1ӨO2Else if…….(to save space,omit the following statement)End if

4.2 操作冲突解决

在实时文件管理系统中,一致性的要求是维护CCI(Consistence,Convergence,Intention)模型.本文采用CRDT数据模型自动收敛,而一致性要求和意图维护则需要所有操作执行后在所有站点得到相同的结果,尽可能满足所有用户的意图.针对以上操作之间关系的检测,要求如下:

1)兼容关系:所有操作的效果都应得到实现;

2)非依赖冲突关系,尽可能多的维护用户的意图;

3)依赖冲突关系:尽可能多的维护所有用户的操作的效果.

由于不同用户发出操作的对象之间的依赖关系,以及操作之间的冲突,都会导致复制文本不一致的情况,所以需要设计合理的操作冲突解决策略和算法来解决由于存在并发操作产生的冲突,最终实现各个复制副本的一致性需求.

依赖冲突解决方案:给定任意两个操作O1和O2,O1是已经执行过的操作,而O2是一个远程操作,且O1和O2属于依赖冲突关系,则依赖冲突关系的解决方案如下:

算法2. Conflict-DependentResolution(O1O2)INPUT O1O2N1和N2代表操作O1和操作O2的目标对象If N1|➝N2 then O2 is executed directly O2 is put into the doubly-linked list behind O1Else Undo O1,O2 is executed,redo O1 O2 is put into the doubly-linked list before O1End if

在算法2中,若操作O1 和操作O2作用的对象有依赖冲突,或者操作依赖冲突,或者操作O1的ID大于O2 的ID,则撤销操作O2,执行O1,重新执行O2,并将操作O1链接到操作O2的前面;否则,直接将操作O2链接到操作O1的右侧.

非依赖冲突关系解决方案:

算法3. Non-dependentConflictResolution(O1×O2)INPUT:O1×O2There must be p1==p2if O2=update then P(O2)>P(O1) Undo O1,O2 is executed,redo O1 O2 is put into the double-linked list before O1Else If O1=update ‖ OID(O1)>OID(O2) then If O1 !=update then Transform(O2,O1) End if O2 is executed O2 is put into the double-linked list behind O1Else Undo O1,O2 is executed Transform(O1,O2) Redo O1 O2 is put into the double-linked list before O1End if

在算法3中,若操作O1 和操作O2属于非依赖冲突关系,若操作O1的id小与操作O2的id,则对操作O2进行操作转换,并将操作O1链接到操作O2的前面,否则,撤销操作O1,执行操作O2,并对操作O1 链接到操作O2的右侧.

算法4. Transform(O2,O1)INPUT O2,O1If O2=rename then If O1=rename&&(N1 !=N2)‖O1=create then N2.nameNew=N2.nameNew+UniqueString(sid2,uid2) Else if O1=rename&& N1=N2 then N2.nameOld=N1.nameNew Else O2=null End ifElse if O2=create then N2.name=N2.name + UniqueString(sid2,uid2)Else O2=nullEnd if Return O2

在算法4,针对非依赖性操作,不可避免的会出现操作转换,该算法就是对其中的操作做出相应的操作转换.

兼容操作关系解决方案:

算法5.CompatibleResolution(O1ӨO2)INPUT O1ӨO2If OID(O1)

在算法5中,若操作O1和操作O2属于兼容关系,若操作O1的id小与操作O2的id,则撤销操作O2,执行操作O1,重新执行操作O2,并将其链接到操作O2的前面,,否则,O1的操作为空,执行操作O2,并将操作O1 链接到操作O2的右侧.

4.3 本地操作集成过程

当本地操作产生时,直接执行,并将该操作直接链接到双链表的后面,若接收到一个远程操作,则找到它的目标操作,并检测是否存在与它具有相同的目标操作的操作,以及和它们的关系.并根据它们的关系确定它们在双链表中正确的位置.本地操作执行过程如算法6所示.

算法6. LocalOperation(O)Execute a local operation O directlyIf head.next == null then O is double linked next to headElse O double linked next to last operation in Li SV[i]=SV[i]+1 OID stored in HiEnd if

4.4 远程操作集成过程

远程操作执行过程如算法7所示.

在算法7中,当集成远程操作O时,需要在双链表中找到目标操作,若目标操作后有操作存在,则需要检测该操作与操作O的关系,并找到操作O在双链表中的正确的位置,算法中引用的函数FindPosiong()就是负责寻找操作O在双链表中的位置.

算法7. RemoveOperation(O)Receive a remote operation Otar=Hi.get(N.OID);nextTar=tar.next;If nextTar=null then O is double linked after Tar in LiElse FindPosition(nextTar,O) Execute the operation O O is double linked in Li SV[i]=SV[i]+1 OID is stored in HiEnd if

算法8. FindPosition(O1,O2)While(O1.next != null)then if O1.s == O2.s then If FindRelation(O1,O2)=O1O2 then If N1|➝N2 then O1=O1.next,continue Else Conflict-DependentResolution(O1O2)Break End if Else if FindRelation(O1,O2)=O1×O2 then if O2 !=update && OID(O1)>OID(O2) If O1!=update then O2=Transform(O2,O1) End if O1=O1.next,continue else Non-dependentConflictResolution(O1×O2) break End if Else if FindRelation(O1,O2)=O1ӨO2 then If OID(O1)> OID(O2) O1=O1.next,continue else CompatibleResolution(O1ӨO2) break End if End if Else if OID(O1)

算法8是根据状态向量找到并发操作,并根据并发操作间的关系,找到双链表中操作正确的链接位置,若并发操作间为依赖冲突关系,则根据操作对象的依赖关系确定位置,若操作间为非依赖冲突关系,则进行合理的操作转换并确定位置,若并发操作间为兼容关系,则根据操作的唯一标识符确定并发操作的执行顺序和在双链表中的正确的位置.

5 云环境下文件实时协同管理的一致性维护

本文所研究的是基于云环境下的协同文件管理系统的一致性维护,设计基于CRDT数据类型设计并存储用户的操作,使其适用于云环境下的文件管理系统,本章节设计相应的算法使得操作的顺序可以交换并能够保证最终状态一致性.区别于传统的P2P架构,云环境主要采用的是C/S架构,本节在C/S架构的基础上设计合理的服务器端和客户端的算法.

1)客户端的主要任务有:执行并向服务器端发送本地操作;接收远程操作,找到该操作在双链表中正确的位置并执行.

算法9. ControlPro on clientGet the latest workspace status from the serverThread1: Generate a local operation O LocalOperation(O) Send O to serverThread2: Receive remote operations sequence T For(i=0;i

在算法1中,Li代表一个双链表,存放的是按照全局顺序存储的操作,SVi代表的是站点i的当前状态向量,Hi代表存放全局唯一标识符的哈希表.

2)服务器端的主要任务是:线程一处理新的连接请求并发送最新的副本给新站点等;线程二接收远程操作并执行.线程三负责更新该操作的目标操作,节省该操作与其他客户端的并发操作的比对,并将更新过的远程操作转发给非发送源的其他站点.服务器端的算法如下:

算法10. ControlPro on ServerInit()Li=[];Hi=[];Thread1: handling new connection requestsThread2: Receive remove operations sequences RS from clients RS =[T1,T2,…Tn] For(i=0;i

6 实例分析

本节主要设计一个协作文件管理场景来验证提出的算法的正确性,假设有两个站点协作管理文件,站点间的交互时序图如图2所示,初始会话为1,两个站点的的关系为ID(site0)

图2 站点操作时序图Fig.2 Operation sequence diagram

在站点1,本地操作O1、O2和O4立即执行,并依次直接链接到双链表的最后,即站点1的双链表为L1=O1→O2→O4;远程操作O3到达,O3的目标操作为O1,而双链表中操作O1后面有操作O2和O4的存在,所以需要依次检测O3和它们的关系,操作O3和O2来自相同的空间状态,两者属于兼容的操作关系,且OID(O2)OID(O8),且它们来自不同的状态,所以O7应该链接到操作O8的前面,此时双链表为L1=O1→O2→O3→O5→O4→O6→O7→O8.

在站点2,远程操作O1到达,没有目标操作,直接链接到双链表中,L2=O1;本地操作O3立即执行,直接连接到双链表中,双链表为L2=O1→O3;远程操作O2到达,其目标操作为O1,而O2和O3来自相同的状态且属于兼容操作关系,OID(O2)OID(O7),所以应该连接到操作O7的后面,双链表为L2=O1→O2→O3→O5→O4→O6→O7→O8.

图3 协作工作后各站点维护的文本状态图Fig.3 State diagram maintained by each site after collaborative work

由上述案列分析可知,站点1和站点2按照不同的顺序执行相同的操作后,都能得到相同的如图3所示的最终文本状态,实现协同管理文件的一致性的维护.

7 效率分析

时间复杂度:如本地操作执行过程算法所示,根据哈希表和唯一标识符信息直接查询本地操作的目标操作的时间复杂度为O(1),当会话开始后,需要在双链表中找到最后一个执行的操作,在这种情况下的时间复杂度为O(n),其中n代表的是在双链表中已经执行过的操作的数量.而在集成远程操作,其最好情况下的时间复杂度为O(1).在这种情况下,通过唯一标识符T-OID在哈希表找到目标操作,而远程操作的位置刚好位于该目标操作的旁边,只有目标操作后面没有其他操作,或者远程操作需要直接链接到目标操作后面时,才会出现这种情况.而考虑最坏的情况时,集成远程操作时会调用FindPosition函数来查找操作的正确的位置,而FindPosition函数的最坏的时间复杂度是O(m),其中,m是目标操作后面存在的操作数量.

空间复杂度:在我们所提出的方法中,每个操作O都是八元组,假设它的长度为Q,双链表中的操作有n个,则空间复杂度为(Q×n),假设哈希表和双链表一样的空间开销,且每个站点的文件或文件夹总共为P个,但肯定不会多于双链表中的操作的数量,每个文件或文件夹有名称属性以及维护一个操作标识符,假设所占空间为L,所以在我们提出的方法中,总空间复杂度为(2Q×n+P×L).

8 正确性证明

在实时文件管理系统中,证明一致性维护方法正确的要求模型是维护CCI模型,本文采用改进CRDT的一致性维护机制,自动维护收敛,无需证明.因此,只要满足以下标准即可证明本文所提出的算法的正确性.

定理1.所提出的方法能够维护最终一致性

证明:在实时文件管理系统中,状态相同的远程操作可能会有建模冲突,在下面的证明中,所有的操作都是以相同状态的远程操作的形式给出,有三种情况需要考虑.

1.对于两个远程操作Oi和Oj,Oi依赖冲突Oj,无论以什么顺序执行,两链表中的操作的顺序都是相同的.

假设当前的双链表为L=O1-O2-…-Ok-Os-…On.且操作Oi和Oj的目标操作均为操作Ok

1)若先接收到Oi且将Oi链接到双链表中Ok的后面,此时双链表为L=O1-O2-…-Ok-Oi-Os-…On,操作Oj到达,有两种情况需要考虑.

若F(Oi)依赖于F(Oj),则Oj被执行并链接到操作Oi的后面.此时双链表为L1=O1-O2-…-Ok-Oi-Oj-On.

若F(Oj)依赖于F(Oi),则Oi操作被撤销,Oj操作被执行并重新执行操作Oi,操作Oj链接到操作Oi的前面,此时的双链表为L2′=O1-O2-…Ok-Oj-Oi-On.

2)若先接收到操作Oj,且将Oj链接到双链表中Ok的后面,此时双链表为L=O1-O2-…-Ok-Oj-Os-…On,操作Oi到达,有两种情况需要考虑.

若F(Oi)依赖于F(Oj),则Oi操作被撤销,Oj操作被执行并重新执行操作Oi,操作Oj链接到操作Oi的后面,此时的双链表为L1′=O1-O2-…-Ok-Oi-Oj-Os-…-On.

若F(Oj)依赖于F(Oi),则操作Oi被执行并链接到操作Oj的后面.此时双链表为L2′=O1-O2-…-Ok-Oj-Oi-…-On.

由以上证明可知,(1)中的双链表L1和(2)中的L1′相同,(1)中的双链表L2和(2)中的双链表L2′相同.

2.对于两个远程操作Oi和Oj,Oi兼容Oj,无论以什么顺序执行,两链表中的操作的顺序都是相同的.

假设当前的双链表为L=O1-O2-…-Ok-Os-…On.且操作Oi和Oj的目标操作均为操作Ok

1)若先接收到Oi且将Oi链接到双链表中Ok的后面,此时双链表为L=O1-O2-…-Ok-Oi-Os-…On,操作Oj到达,有两种情况需要考虑.

若OiD(Oi)>OiD(Oj),则Oj被执行并链接到操作Oi的后面.此时双链表为L1=O1-O2-…-Ok-Oi-Oj-On.

若OiD(Oi)

2)若先接收到操作Oj,且将Oj链接到双链表中Ok的后面,此时双链表为L=O1-O2-…-Ok-Oj-Os-…On,操作Oi到达,有两种情况需要考虑.

若OiD(Oi)>OiD(Oj),则Oi操作被撤销,Oj操作被执行并重新执行操作Oi,操作Oj链接到操作Oi的后面,此时的双链表为L1′=O1-O2-…-Ok-Oi-Oj-Os-…-On.

若OiD(Oi)

由以上证明可知,(1)中的双链表L1和(2)中的L1′相同,(1)中的双链表L2和(2)中的双链表L2′相同.

3.对于两个远程操作Oi和Oj,Oi非依赖冲突Oj,无论以什么顺序执行,两链表中的操作的顺序都是相同的.

假设当前的双链表为L=O1-O2-…-Ok-Os-…On.且操作Oi和Oj的目标操作均为操作Ok.

1)若先接收到Oi且将Oi链接到双链表中Ok的后面,此时双链表为L=O1-O2-…-Ok-Oi-Os-…On,操作Oj到达,有四种情况需要考虑.

若操作Oj为更新操作,则撤销操作Oi,执行Oj并重新执行Oi,操作Oj链接到Oi的前面,此时的双链表为L1=O1-O2-…-Ok-Oj-Oi-…-On.

若操作Oi为更新操作,则直接执行操作Oj并将操作Oj链接到Oi的后面,此时的双链表为L2=O1-O2-…-Ok-Oi-Oj-…-On.

若OiD(Oi)>OiD(Oj),则操作Oj相对操作Oi做操作转换得到Oj′,并将操作Oj′链接到双链表中操作Oi的后面,此时双链表为L3=O1-O2-…-Ok-Oi-Oj-Os-…On.

若OiD(Oi)

2)若先接收到操作Oj且将Oj链接到双链表中Ok的后面,此时双链表为L′=O1-O2-…-Ok-Oj-Os-On,这里亦有四种情况.

若操作Oj为更新操作,则直接执行操作Oi并将操作Oi链接到Oj的后面,此时的双链表为L1′=O1-O2-…-Ok-Oj-Oi-…-On.

若操作Oi为更新操作,则撤销操作Oj,执行操作Oi,重新执行操作Oj,并将操作Oi链接到Oj的前面,此时的双链表为L2′=O1-O2-…-Ok-Oi-Oj-…-On.

若OiD(Oi)>OiD(Oj),则撤销操作Oj,执行操作Oi,并将操作Oj相对操作Oi进行操作转换得到Oj′,重新执行操作Oj′,将Oi链接到操作Oj的前面,此时双链表为L3′=O1-O2-…-Ok-Oi-Oj-Os-…On.

若OiD(Oi)

在这种情况下,L1=L1′,L2=L2′,L3=L3′,L4=L4′.由以上证明可知,本文所提出的方法能够确保每个站点都维护相同的历史操作集,且最终获得了一致性的文本空间.因此,本文所提出的的方法能够满足维护最终的一致性的需求.

定理2.所提出的方法能够实现意图维护

证明:基于上述的维护最终一致性的证明,远程操作的综合效果都得到了保留.在此,考虑三种情况:首先,对于依赖冲突关系的操作,两个操作的效果都得到了实现;其次,对于兼容关系的操作,两个操作的效果也都得到了保留;最后,对于非依赖冲突的操作,本文通过一些简单的操作转换使尽可能多的用户操作的意图得到了保留.因此本文所提出的方法可以实现用户的意图维护.

9 总结与展望

本文针对云环境下实时的文件管理系统中,提出新的基于CRDT方法的冲突检测和解决方案来维护协同工作的一致性维护.首先定义基本操作以及操作之间的关系,并提出了冲突检测机制;其次,提出冲突解决的有效方案;最后,举例并证明了提出方案的正确性,并从理论上分析其时间复杂度和空间复杂度,本文所提出的冲突检测和解决方案能够有效的维护最终文本的一致性,并能保证操作的正确执行.在未来的研究中,我们将针对细粒度进行研究,即针对文件内容的操作,并改进算法以适应细粒度的一致性维护的研究.同时,随着云环境的兴起和移动端的普及,移动云环境下的研究也越来也受欢迎,接下来的工作,可以将文件协同管理应用到移动云环境下,并根据新的应用场景设计合理的算法来维护协同工作的一致性.