大规模实时图形编辑中可交换复制数据模型一致性维护
2019-07-09高丽萍徐晓芳
高丽萍，徐晓芳
1(上海理工大学 光电信息与计算机工程学院，上海 200093) 2(复旦大学 上海市数据科学重点实验室，上海 200093)
1 引 言
实时协同编辑系统是一种广泛使用的分布式计算机系统，它支持分布在不同地域的人通过网络连接对同一个文档(包括文本，图形，视频，音频等)进行查看，编辑.针对不同研究领域，协同的概念不尽相同，但总体思想均是在良好的互联网环境下合作者们可以同时在不同地域在产生冲突的前提下完成同一项工作，从而帮助提高我们项目的开发效率、方便各个成员之间的交流、增强分布在不同地理位置上的操作人员的实时交互.计算机技术的飞速发展，人们对日常工作高效需求，促使协同技术不断创新，大量的理论相关、技术支持被提出和采用.然而，越来越多的问题相继产生，这就需要大批科研人员逐步去完善革新，使得仅发展十余年的CSCW学科才有了如今的成就.为创新者提供了充足的科研资料.
随着大数据和云计算兴起，实时图形编辑系统更倾向于大规模的协作. 在大规模协作中，一个复杂的项目通常涉及数以百计的设计人员协作完成一项任务. 在这种情况下，需要进一步考虑两个问题. 一个问题是大量的并发冲突将不可避免地发生，这给一致性维护带来了更高的挑战. 另外一个问题，对于大量用户同时编辑共享文档的大规模协作[1]，共享文档会经常更新. 这种情况通常会导致协作计算性能的下降[2]. 如何提高计算性能是智能和大规模协作编辑系统成功的另一个挑战，其一致性在大数据和云计算时代，维护和计算性能非常关键.
CRDT算法的主要思想是设计交换并发操作.因此，不再需要转换，可以按照任何顺序执行并发操作.本文主要提出了一种用于智能和大规模协同图形编辑系统的字符串CRDT算法，以解决新的挑战.最近，CRDT技术被提出作为一种新的协同文本编辑的并发控制机制. 已经证明CRDT算法的性能优于传统方法，并且适用于大规模分布式环境[7]. 本文组织结构如下：第二部分介绍了研究背景及相关工作；第三部分提出了在实时图形编辑系统中基于CRDT的冲突解决方案；第四部分提出了一个协作设计的案例研究；第五部分给出了时间复杂度和空间复杂度分析；第六部分为了验证算法正确性与有效性，在windows系统中开发一个协同图形编辑系统co-Drawing；第七部分给出结论和未来工作.
2 相关工作
在近几年的研究中，OT(Operation Transforma-tion[12]最初设计用于支持多个用户在复制的文本文档中同时插入和删除字符并始终如一.还有基于地址空间转换(Address Space Transformation，AST)[4]技术. OT的基本思想是根据已执行的并发操作的效果，对先前文档状态定义的编辑操作进行转换，以使转换后的操作能够在当前文档状态下达到正确的效果. 尽管其文本编辑起源于OT，但它独立于文本文档和文本编辑，并且已被用于支持一致性维护和用户启动的撤消，以协作编辑文本和图形文档[3].而基于AST的算法与OT的不同是从文档状态出发，将文档的状态地址空间回溯到操作产生时的状态，在这样的情况下，我们可以直接找到操作的执行位置，从而维护文档的一致性.但是，基于AST的技术不知处非线性结构文档一致性的维护.并且，基于OT和地址空间转换技术在实时群组编辑系统中执行效率比较低.
在协同图形编辑系统中，一致性维护多采用多版本机制来解决并发控制问题，例如：Chengzheng Sun等在文献[4]中创新提出了云存储操作转换函数(Cloud Storage Op-eration Transformation，CSOT)，实现了云存储系统中实时同步共享树形文档结构的收敛性；Chengzheng Sun等在文献[4]中提出了一种新的协作对象分组技术，称CoGro-up，它基于操作转换(OT)技术和TA[4].基于之前的工作，有人提出了一个优化的版本，以最优化解决对象版本的数量. Gao等[5，17]人在实时位图系统中采用多版本策略来解决执行和撤销/重做一致性维护问题.还有根据TIP-S[14]算法进行一系列的改变应用在协同图形编辑系统中.基于OT的这些方法在大规模数据下协同编辑群组编辑中并不能有很好的执行效率.最近，CRDT(Commutative Repli-cated Data Type)被提议作为一种新的并发控制机制，以实现协作文本编辑的最终一致性.自文献[6] 相关工作研究以来，已经提出了一种具有代表性的CRDT算法，并将其应用于协作文本编辑[7]HE等人在大规模协同编辑系统中提出过String-wise CRDT算法，解决了在智能和[7，10]大规模数据环境下的一致性维护，其正确性已经得到验证.还有人将CRDT模型引入到实时协同CAD[10]系统中.在这两篇文章中都突出了CRDT在大规模数据处理时的优势，效率更高，时间复杂度和空间复杂度都得到很好的优化.在协同图形编辑系统中，基于CRDT的研究很少，相比多版本机制，基于树的各种机制，它有很大的优势.本文针对C/S架构下图形编辑系统中的实时性对CRDT算法做出了改进，同时在系统设计时保证我们采用的工具协议等可以达到更好的实时性.
本文跟传统的OT[15]算法相比，有很大优势.例如，以前将COT[13]算法改进应用到图形编辑场景下，这种情况下，O的执行条件是将DS与C(O)[12]中的操作对比，在C(O)中所有的操作将与O进行操作转换，那么在一次次操作传输过程中，DS和C(O)靠前的操作将会进行一次次无用的比对，这浪费了时间和传输开销，本文提出的基于CRDT的算法根据唯一ID号找到操作对象直接进行操作，尤其在删除操作时大大提高效率.
3 实时图形编辑系统中一致性维护
3.1 基于CRDT的冲突解决
在字符串[7]编辑方面的工作，我们扩展和推进了数据结构，以便在实时图形的Co-DRAWING系统中得到很好的使用.实时协作图形编辑系统由大量的协作站点组成. 每个站点都维护CoRDG(即动态规则库)，一个哈希表，一个双链表和一个View交互视图.CoRDG用于存储预定义对象间的关联关系. 哈希表存储所有对象间的操作.双链表按顺序将所有图形操作(包括可见和不可见建模操作)从头到尾链接起来.每个图形对象操作都被视为双链表的操作节点.View可以为协作用户提供交互界面.整个框架如图1所示.
图1 整体框架Fig.1 Overall framework
整个控制过程如图1所示.协作设计人员同时在本地站点上创建、删除、更新操作，并从其他站点接收远程图形对象操作.当一个本地操作产生时，本地操作立即执行并且通过使用上次操作的标识符，将操作直接链接在双链表的最后一次操作之后.远程操作的集成过程包括两个步骤.首先，远程操作需要在具有唯一标识符的散列表中找到目标图像对象操作.其次，目标图形对象操作的位置需要在双链表中找到.一些被执行的操作可能存在于相同的目标对象操作之后，当存在冲突时，它们在CoRDG中的关联关系的优先级以及它们的标识符需要被用来解决冲突，最后，集成更新的效果出现在交互视图中.
3.2 基本定义
定义1.图形对象操作(Oa)
在实时协同图像编辑系统中，一个Oa由一个15元组
定义2.(Oa)给定双链表中任意两个Oa和Ob，Oa的位置表示为pos(Oa)，Ob的位置表示为pos(Ob)，如果：pos(Oa) 基于以上定义，由于在双链表中不同的目标操作位置，我们可以在两个图形操作之间获得Oa.然而，当两个并发图形操作在双链表中可能具有相同的操作位置.在这种情况下，我们不能在两个图形操作之间获得Oa，所以我们有必要对它们进行排序.因此，唯一的标识符可以决定他们的顺序.唯一的标识符的定义如下. 定义3.标识符(ID)[15] 图形对象的唯一标识符由一个三元组组 1)s是会话的标识符 2)ssv是一个操作的状态向量之和 3)site是站点的唯一标识符 定义4.给定任意两个图形对象的操作Oa，Ob，两个操作的ID分别是IDOa IDOb 1)如果IDOa[s] 2)如果IDOa[s]=IDOb[s]，IDOa[ssv] 3)如果IDOa[s]=IDOb[s]，IDOa[ssv]=IDOb[ssv]， IDOa[ssv]=IDOb[ssv]，IDOa[site] 定义5.位置关系 为了确保最终的一致性，我们需要确保在所有站点中执行了所有操作时，双链表中的所有建模操作在每个站点中具有相同的总排序. 以下给出了所有建模操作的总排序关系的定义. 定义6.操作的总排序关系(O⟹) 给定任何三个操作，O1，O2和O3，如果：(1)O1 定义7.冲突/相容关系 假设给定两个操作Oa和Ob，Oa||Ob且Oa和Ob操作的目标图形对象标识相同，有如表1所示的关系[13]. 表1 图形对象间的冲突/相容关系Table 1 Conflict/compatibility between graphical objects 在实时协作文本编辑中，最终一致性和意向保存是CRDT算法的两个重要的正确性标准. 因此，在协同文本编辑中的正确性标准之后，如果遵守以下标准，则认为实时Co-Drawing系统是正确的： 最终一致性：所有图形操作都在所有站点中执行完毕后，来自不同站点的所有操作图形都是相同的. 意向保存：需要在所有站点保存图形并发操作的综合效果. 此外，我们的研究工作需要考虑两种种情况： 1)为了兼容操作，需要保留所有兼容操作的效果. 2)对于冲突操作，尽可能保留冲突操作的影响，必要时只需要保留冲突操作的一个效果，根据动态规则库保留操作语义的一致性. 与协同文本编辑不同，在基于图形对象操作的Co-RDG系统中，操作之间之间存在复杂关系，不同设计者之间的操作不可避免地存在冲突. 在这种情况下，由于操作冲突可能导致某些图形对象操作无法执行，最终导致整个绘图任务无法完成. 因此，需要冲突解决方法来保持更多的设计意图并保持最终的一致性. 考虑到图形操作的复杂性，为了维护最终的一致性，本文将操作分为基本操作和预定义关系操作两种. 定义8.位置属性约束关系 如果两个不同的图形对象存在一种或多种特殊的位置关联关系，这样的图形对象之间的关系，我们定义为位置属性约束关系.对这些图形对象的任何一个对象进行操作，都要先检测他们之间的约束关联关系.位置关联关系定义我们参考许[15]等人的研究. O(i)是用户根据实际的设计的需求，动态的将图形对象间的各种复杂的关联关系添加到动态规则库里，系统会及时通过广播传送给其他站点，使各个站点的语义冲突规则库都保持最新的状态. 3.3.1 基本操作 本文设计的协同图形编辑系统中，有N操作(New)，D操作(Delete)以及U操作(Update)三种基本类型操作. 3.3.2 预定义关系操作 在实际的工程绘图设计过程中，用户可能根据自己的意愿或者实际的现实需求，预先给图像对象间定义某些特殊的约束规则.在这样的情况下，多人同时编辑这些图形对象，执行结束后，可能就会违背之前定义的约束条件，从而造成语义不一致的问题.本文只讨论，图形对象之间位置上的关联关系并且预定义关系一般指两个操作作用在不同的对象之间. 预定义操作冲突检测 预定义并发冲突操作 1)Oa||Ob 2)Oa、Ob∈Relate(Oa、Ob操作对象之间存在关联关系) 3)Oa、Ob Rule∉Oa、Ob在执行后违背了Rule定义的规则)那么，Oa和Ob是并发冲突操作预定义并发兼容操作 如果操作Oa和Ob不是并发冲突操作，则Oa和Ob是兼容操作. 算法1介绍了如何解决基本操作之间的冲突.操作Oa是已经执行过的操作，操作Ob是要执行的远程操作.有两种情况需要考虑.当操作是同一种操作类型，则根据优先级来决定执行哪个操作，优先级高的操作链接到双链表中，优先级低的操作不执行，可见被设置为0，优先级低的操作flag被设置为1.当操作是不同类型的操作时，我们规定D操作的优先级大于U操作的优先级. 算法1.ConflictResolve INPUT：Oa⊗Ob Int flag=0 If T(Oa)=T(Ob)=operate.Delete‖ T(Oa)=T(Ob)=Operate.Update& K(Oa)≠K(Ob)‖ Ob is not execute，Ob.visible=0，flag=1 If Oa.next=null then Oa.next=Ob，Ob.prior=Oa Else Ob.next=Oa.next，Oa.next.prior=Ob ， Oa.next=Ob，Ob.prior=Oa End if Else If T(Oa)=Operate.Update & T(Ob)=Operate.Delete then Oa is undone，Ob is execute Oa.prior.next=Ob，Ob.prior=Oa.prior，Ob.next=Oa， Oa.prior=Ob，Oa.visible=0 Else T(Oa)=Operate.Delete & T(Ob)=Operate.Update Ob is not execute，Ob.visible=0，flag=1 Ob.next=Oa.next，Oa.next.prior=Ob Oa.next=Ob，Ob.prior=Oa End if End if Output：flag 算法2介绍了如何解决基本操作之间的兼容操作.操作Oa是执行操作，操作Ob是要执行的远程操作.当两个操作是兼容关系时，标识符较小的操作在标识符较高的操作之前执行.与此同时，在双链表中具有较大标识符的操作链接在具有较小标识符的操作之后. 算法2.CompatibleResolve INPUT：Oa⊙Ob Ob is execute If Oa.next=NULL then Oa.next=Ob，Ob.prior=Oa Else Ob.next=Oa.next，Oa.next.prior=Ob ， Oa.next=Ob，Ob.prior=Oa End if Else Oa is undone，Ob is execute，Oa is redo Oa.prior.next=Ob，Ob.prior=Oa.prior， Ob.next=Oa，Oa.prior=Ob，Oa.visible=0 End if 算法3介绍了如何解决预定义操作之间的冲突. 算法3.Predefined conflict resolution INPUT Oa⊗Ob Int flag=0 IF Oa、Ob∈R elate & Oa、Ob∉ Rule then Ob is execute Ob is not execute，Ob.visible=0，flag=1 Oa.next=Ob，Ob.prior= Oa Else Oa is undo，Ob is executed Oa.prior.next=Ob，Ob.prior=Oa.prior Ob.next=Oa，Oa.prior=Ob，Oa.visible=0 End if End if OUTPUT：flag 算法4该算法给出了本地操作Oa，有两种情况需要考虑：首先，当Oa：pre_key为空并且在双链表中没有图形操作存在时，Oa插入在双链表的头部.否则，操作插入在双链表的最后一次图形建模操作之后.第二种情况，当Oa.pre_key不为空时，需要找到刚刚在本地站点执行的图形建模操作(pre)，Oa连接在刚刚找到的Pre后面.然后，将Oa广播到远程站点. 算法4.IntergrateRemote(Oa) INPUT ：Oa If Oa.pre_key==null then If head.next!=null then CT=head.next While CT!=null do CT=CT.next While CT!=NULL do NT=NT.next End While Oa is double linked after CT.prior Else Oa is double linked next to head End if Else pre=hash(Oa.pre_key) Oa is double linked after tar End if Oa is broadcast to remote site 算法5给出了远程操作Oa 当远程操作广播过来后，图形的目标操作可以使用唯一标识符直接找到.找到当前会话中的第一个建模操作，然后判断远程操作跟目标操作是否作用于同一目标对象，有两种情况：一是作用于同一目标对象，根据基本类操作的冲突操作判断是否是冲突操作，在相同文档状态下，若是冲突操作，调用CompatibleResolve算法，若是兼容操作，则调用 CompatibleResolve；在不同文档状态下，根据两个操作的优先级来决定执行顺序及目标操作的位置；二是两个操作的对象目标不一致，此时要先去动态规则库查询两个图形对象间是否有空间位置关联关系.在相同文档状态下，存在空间位置关联关系，根据预定义的关联关系，进一步需要判断是不是违反约束规则，若是违反规则，则调用Predefined conflict resolution；若不违反规则，则调用CompatibleResolve.在不同的文档状态下，根据优先级来决定执行顺序及目标操作在双链表中的位置. 算法5.IntergrateRemote(Oa) INPUT：Oa Tar=hash(Oa.t_key[Obji]) If CT==null then Oa is double linked after Tar Else CT=CT.next End while if Oa(Obja)==Ob(Objb)‖CT，Oa∉Relate-Rule then While CT!=null&&ID(CT)ID(Oa) do If CT.s==Oa.s then If(CT，Oa)==CT⊗Oa then ifOa(Obja)==Ob(Objb) then Flag=ConflicResolve(CT⊗Oa) Else Flag=PreConflicResolve Break Else CT=CT.next Else Undo CT，execute Oa，redo CT Oa is double linked before CT，break End if End if Else CT=CT.next，continue Else Undo CT，execute Oa ，redo CT Oa is double linked before CT，break End if End while If CT==null then Execute Oa and double link Oa after CT.prior End if If CT.s==Oa.s then If (CT，Oa)==CT⊗Oa then Flag=ConflicResolve(CT⊗Oa) Else CompatibleResolve(CT End if Else Oa is execute double linked before CT End if End if 图2 第一次协作过程Fig.2 First collaborative process 第1阶段： 如图2所示，站点1产生三个本地操作，分别是O1，O2，O3；站点2产生两个本地操作，分别是O4，O5.所有操作的状态向量分别是：SV(01)=(1，0)，SV(02)=(2，0)，SV(03)=(3，1)，SV(04)=(1，1)，SV(05)=(2，2).所有操作的ID号为：IDO1=(1，1，1)，IDO2=(1，2，1)，IDO3=(1，4，1)，IDO4=(1，2，2)，IDO5=(1，4，2) 在站点1，本地操作O1生成，执行O1，此时L1=O1.然后本地操作O2生成，执行将O2加入到双链表中，即L1=O1-O2.当O4到达时，O4跟O2有相同的文档状态，需要检测他们之间的关系，因为是兼容关系，并且IDO2IDO4，执行O4，在双链表中把O4连接在O2之后，L1=O1-O2-O4.本地操作O3生成，O3的目标操作是O1，O2操作存在于O1后，因为O2和O3的状态向量不同，IDO2IDO3 ，因此，将O3连接在O2之后，同理，O3连接在O4之后.执行O3并将O3操作加入到双链表中，此时L1=O1-O2-O4-O3.当O5到达站点1时，O5的目标对象是O1，O1后面有O2，O3，O4，因为O5跟O2和O3的状态向量不同，连接在操作O4后面，O5的目标对象跟O3目标对象时相同的，并且状态向量相同的，所以他们是基本类操作里面的冲突操作，因为IDO3IDO5，所以，O3操作撤销，O5操作执行.O3.visible=0同时将O5插入到双联表中，L1=O1-O2-O4-O3-O5. 在站点2，O1操作到达，L2=O1.操作O4生成，执行O4并将其加入双链表中，L2=O1-O4.O2操作到达，因为O4和O2具有相同的文档状态，但是O2和O4目标对象不同，因此是兼容关系，同时IDO2IDO4.所以执行O2，在双链表中把操作O2放到操作O4之前，L2=O1-O2-O4.O5生成，执行O5，O5的目标对象是O1，直接将O5插入到双链表中O1之后，O5跟O2和O4状态向量不同，在双链表中将O5连接在O4之后，L2=O1-O2-O4-O5.当O3操作到达，O3操作的目标对象是O1，操作O2，O4，O5在操作O1之后，并且O5跟O3具有相同的状态向量，因此O5跟O3的关系需要检测，是冲突操作，因为IDO3IDO5.因此，O3不需要执行，O3.visible=0，在双链表中不可见的操作O3连接在操作O5之前.此时，L2=O1-O2-O4-O3-O5. 最终，在两个站点维护的双链表分别为：L1=O1-O2-O4-O3-O5 L2=O1-O2-O4-O3-O5 图3 第二次协作过程Fig.3 Second collaboration process 第2阶段： 如图3所示展示第二阶段的协同过程，在站点1生成一个本地操作06，站点2生成一个本地操作07，所有操作的状态向量分别是：SV(O6)=(4，2)，SV(O7)=(3，3)，Relat-ion(line1，circular1，1，describe)，Describe(line1不高于circular1)，Rule：(1，y1-pos”<=”)所有操作的ID号为：IDO6=(2，6，1) ，IDO7=(2，6，2). 在站点1，本地操作O6生成，L1=O1-O2-O4-O3-O5-O6，当O7操作到达，O7的目标对象是操作02，在操作O2后面有O4-O3-O5-O6，因为不可见操作O3和操作O4，O5，不是当前协同会话过程中，所以跳过.操作O6在当前会话过程中，因为操作O6和O7作用在不同的操作对象中，用动态规则库(CoRDG)检查两个操作是否违反Rule，检查违反了预定义关系，根据优先级，撤销O6，在双链表中加入操作O7.O6.visible=0，O7连接在双链表之前. L1=O1-O2-O4-O3-O5-O7-O6. 站点2，本地操作O7生成，L= L1=O1-O2-O4-O3-O5-O7.当操作O6到达，O6的目标对象是操作O4，在操作O4后面有O3-O5-O7.跳过不可见操作O3和操作O5.因为O6和O7具有相同的文档状态，因为O7比O6具有更高的优先级.所以，O6不执行，O6.visible=0，在双链表中O6连接在07后面.L2= L1=O1-O2-O4-O3-O5-O7-O6.最终，在两个站点维护的双链表分别为：L1=O1-O2-O4-O3-O5-O7-O6L2=O1-O2-O4-O3-O5-O7-O6. 在本小节中，我们将对我们的方法进行实验，以验证算法的有效性.我们用Intellij IDEA作为实验平台，用JAVA语言实现，模拟测试仿真原型系统，并且由Windows 7系统，Intel Core i7，3.30 GHz CPU上的Visual Studio 2010编译.然而，在协作编辑中没有可用的公共数据集，性能评估通常基于操作日志由协作产生.我们设计实时协作以获取操作日志.然后，重播两种算法的所有操作.每个站点执行所有本地操作和远程操作后，将继续执行相同的过程.我们在每个操作日志中运行次30次算法，并记录平均值. 图4 CRDT方法与COT方法比较Fig.4 ContrastofCRDTandCOT图5 历史操作数与站点数的对比图Fig.5 Comparisonofhistoricaloperandsandnumberofsites 在本节中，将我们的方法与文献[11]传统COT算法的计算时间进行比较. 首先，研究了我们的方法和COT算法将远程图形操作集成到操作历史H中需要多长时间.其次，研究了我们的方法和COT的图形操作的平均计算时间.图5显示了COT和我们的方法远程操作的计算时间. 如图5所示，随着操作历史的长度增加和远程操作的数量增加，COT比我们的方法需要更多的时间. 尤其是，当操作历史的长度为200时，COT需要64 ms来集成100个远程操作，而我们的方法仅需5 ms来集成100个远程操作. 图4显示了COT与我们的方法的基于图形的操作的平均计算时间，其中删除比率被设置为20%并且远程操作的数量随着历史操作数而增加. 如图5所示，COT需要更多时间来整合删除操作，但我们的方法需要更少的时间. 主要原因是有冲突时，每个COT算法在集成远程操作时，P2P环境下的COT每次传输都要附带一个C(O)的文档状态文本，当协同工作时间过长或操作过多时，这个C(O)就会变得很庞大，每次冲突都要从历史操作序列开头进行一一对比. 例如，当远程操作的数量是400，删除率是20%时，我们的删除操作能根据目标对象唯一的ID号直接进行删除操作. 为了验证大规模数据下实时图形编辑系统中，算法的正确性与可行性，本文开发了一个基于Intellij IDEA平台实时图形编辑系统CO-DRAWING.客户端：采用[19]webSocket协议实现实时图形编辑系统CO-DRAWING.WebSocket协议可以实现持久连接的全双工双向通信，应用WebSocke 结合WSS协议达成多人实时异地协同设计的目标.服务器端：系统采用SSM(SpringMVC+Spring+Mybatis)框架来搭建的一个web系统，通过Intellij IDEA平台，部署到到tomcat上来实现访问，同时为了体现大规模数据的特性，采用Docker技术在一台物理计算机上运行3个服务端程序. 图6 算法原型系统Fig.6 Algorithm prototype system 多人同时编辑如图6所示，上方是为选择创建各种图像(三角形，线条，矩形)，清空画布等功能：屏幕右下方中间部分为协同用户界面；屏幕右下方下面部分为图形对象ID号；系统分为基本操作维护和语义冲突维护.其中语义操作维护根据动态规则库来进行管理. 本文提出了一种新颖优化的CRDT算法，该算法主要应用于大数据时的智能和大规模协作的实时图形编辑系统中. 该新颖算法可以保留操作的意图并通过预定义图形对象之间的关联关系和位置属性约束规则，设计本地操作和远程操作的实现算法，使个站点的语义维护得到有效的保证.并且通过理论分析和实验评估表明，该算法的计算性能大大优于现有的OT算法和AST算法. 因此，与现有算法相比，该算法更适合于智能和大规模协作应用. 在未来的研究中，我们计划继续探索以下几个方面. 首先，图形编辑系统中的Undo/Redo是很重要的操作，下一步将重点探索这个方面. 其次，我们将把图形对象中的其他操作合理地加入进来，图形之间的预定义操作不仅只有这一种，还有很多复杂的关联操作需要考虑.第三，尝试将我们的方法应用于现实生活中的协作应用程序. 例如，Google Drive，Codoxware，SubEthaEdit，Novell Vibe等基于云的协作服务近年来越来越流行. 这些协作应用程序需要通过在合作者之间交换意图，想法，知识和智慧来共同创作共享文档，从而提高效率和质量. 所提出的算法与要求非常匹配，并将在未来应用于这些领域.第四，我们将探讨如何使用多核CPU /多核GPU加速大规模协作应用[9,10].
3.3 操作分类
3.4 操作检测
3.5 CRDT算法
4 案例分析
5 实验分析
6 原型系统Intellij
7 总结与展望
