基于操作转换的并发控制算法的研究

孙 敏 王瑞花

(山西大学计算机与信息技术学院 山西 太原 030006)

基于操作转换的并发控制算法的研究

孙 敏 王瑞花

(山西大学计算机与信息技术学院 山西 太原 030006)

为解决协同图形编辑中出现的结果不一致、因果不一致、操作意愿不一致和语意不一致问题，提出一种基于操作转换的并发控制算法。该算法定义了操作序列的上下文有序、操作序列的上下文并发等概念。从协同编辑操作的预处理及实际执行时的操作转换两个方面，对基于上下文的操作转换(COT)算法进行改进，并进行实例验证分析。研究发现，其可有效地减少COT算法中存在的操作转换冗余的问题。

并发控制 协同编辑 操作转换 上下文有序

0 引 言

实时协同编辑支持地域上分散的用户,通过网络在同一时间对一共享文档进行编辑,并保证所有操作都能正确执行。由于存在人为或网络延迟等不可预料因素，若对各站点上协同操作的执行不加以控制，就可能会产生副本的不一致。协同图形编辑是协同编辑的一个子研究领域，对编辑过程进行有效的并发控制和一致性维护是研究的重点。相应的方法除有令牌环机制、锁机制和串行化机制等传统方法之外，目前主流的有两类：基于对象复制的多版本方法和基于操作转换的方法[1]。

Kanawati等在文献[2]中提出基于多版本技术的共享对象一致性保持算法。该算法将冲突操作的效果应用到同一操作对象的不同副本,无冲突操作应用到同一对象,从而使共享副本保持一致。杨君等提出基于版本复制的多版本模型[3],并设计多版本增创算法MVIC(Multiple Versions Incremental Creation)。之后许多研究人员在MVIC的基础上进行了诸多改进。但是，随着协同用户的不断增加、协同工作的逐渐深入，此类算法要求站点维系的版本数量也不断增多，操作之间的冲突也趋于复杂。这对信息的管理和存储提出挑战，同时也使得最终版本的选择策略趋于复杂，实时响应也变得有点不现实。

基于操作转换的算法最早由Ellis等提出[4]，他提出分布式操作转换算法 (dOPT)，是一种乐观并发控制方法。该算法能很好地解决因果和操作意愿维护问题，但算法构造的转换函数仅限于特定应用，存在不足。之后又出现大量对dOPT的改进算法。如Ressel等提出adOPTed算法[5-6]，是在 dOPT基础上，加入L-转换和多维交互图，它能解决因果和操作意愿一致性维护，但并不能完全解决数据不一致问题。之后Sun等[7]提出GOT及其优化算法，即GOTO。GOT只针对简单并发问题，通过设计包含转换和排斥转换两种转换函数来进行一致性维护，没有解决偏并发问题，而GOTO则是在GOT的基础上解决了偏并发问题。此外，还有SOCT2、SOCT3、TIBOT、 COT等操作转换算法。COT算法是由Sun等提出的[8-9]。此算法通过引入操作上下文的概念来系统地表述和判断协同操作间的关系，为操作副本的一致性维护提供了有效方法。

COT算法是目前在实际中应用最广泛的算法。但是，COT算法仍然存在许多不足。本文就是对COT算法中存在的不足进行研究和改进。

1 相关理论基础

1.1 基本关系描述

在协同编辑中，各个协同副本及操作之间存在的关系[8-9]如下所示：

1) 文档状态

表示某时刻某个站点副本的状态，是一个动态变化的已执行操作的集合。

(1) 初始情况下,定义站点的文档状态DS={}；

(2) 当有操作O执行后，其文档状态为DS′=DS∪{org(O)}，其中org(O)是O的原始表示。

2) 操作上下文(C(O))

(1) 对于一个原始操作，C(O)=DS；

(2) 对于转换操作O′，C(O′)=C(O)∪{org(O)}，其中O′=IT(O,Ox)。

3) 上下文依赖关系(上下文因果关系)

4) 上下文等价关系

给定两个操作Oa和Ob以及其上下文C(Oa)和C(Ob)，称操作Oa和Ob的上下文是等价的，当且仅当C(Oa)=C(Ob)。

1.2 协作编辑中的不一致问题

由于人为或网络延迟等原因，各协同操作到达站点是无序的。若对各站点上操作的执行不加控制，就可能会产生副本不一致，如图1所示。

图1 协同站点间的并发操作

常见的不一致有以下4种[10]：

1) 结果不一致

假设O1、O2、O3的执行顺序一定。在各个站点上，如果操作的执行顺序没有限制，就可能产生结果不一致。假设站点初始状态为“A12Ba”，若O1:Insert(2,"C")，O2:Delete(3)，O3:Insert(4,"5")，则在站点1的执行结果为“A12B5a”，在站点2的执行结果为“A1C2B5”。

2) 因果不一致

由于网络延时，难以保证操作信息按产生的顺序到达各个站点。如果这些远程操作在执行时不加限制，就可能产生不一致。

3) 操作意愿不一致

是指协作者期望达到的效果与实际产生的结果不同。仍以1)中数据为例，O2实际意义是删除“A12Ba”中第三个位置上的“2”,但在站点1，实际删除的是O1插入的“C”，这违背了协作者的意愿，产生不一致。

4) 语义不一致

在基于对象的协同图形编辑中，图形对象可能存在空间位置上的依赖关系，也可能存在某些相关属性的依赖关系。如果操作执行时，违背了这些语义关系，就会产生不一致。如图2所示，并发操作O1、O2，O1是改变椭圆1的大小，O2是改变椭圆2的位置。若操作的对象相互独立，则O1、O2间不存在冲突。若在操作对象间建立联系：两个椭圆大小相等、位置平行，则O1、O2在两个协同站点执行，虽能保证结果一致，但会违背语义约束，出现操作语义的不一致。

图2 图形对象间的依赖关系

2 COT算法及改进

基于操作转换的算法通常分为两部分[11]：高层的转换控制算法和底层的转换函数。当到达站点的远程操作已就绪，根据操作间的上下文关系，转换控制算法决定哪些操作需与此操作进行转换，及应采用怎样的转换顺序；转换函数是通过对操作的各种参数进行分析，来确定将以何种方式进行操作间的转换。而转换属性和条件则是介于转换控制算法和具体的转换函数之间，主要用来保证远程操作的正确转换和执行，以及最终版本的一致性维护。因此，对协同编辑中的并发控制和一致性维护进行研究，一般是从以上这两个方面入手。

2.1 基于上下文的操作转换算法COT

COT算法是基于上下文的操作转换算法。在各个协同站点，都维护着一个文档状态DS，是已执行操作的集合。COT的基本思路是：本地操作立即执行，远程操作O只有当操作上下文C(O)与接收站点的文档状态相同时，才能执行。因此，站点接收到O，首先检测是否上下文就绪。若准备就绪，查看O的上下文与站点的文档状态是否一致，若一致，则O立即执行；否则需通过一定的转换，将O的上下文上升到接收站点的文档状态，或者说，将O转换为可执行的形式，然后执行。执行完后更新站点的文档状态。具体COT算法如下(算法1和算法2)：

算法1

COT(O,DS)

O′=transform(O,DS-C(O))；

执行O′；

DS=DS∪{org(O′)}

算法2

transform(O,CD)

循环直到CD={}；

从CD中选择并移出Ox,满足C(Ox)⊆C(O)；

transform(Ox,C(O)-C(Ox))；

O′=IT(O,Ox)；

C(O′)=C(O)∪{org(Ox)}

2.2 COT算法的不足及改进

2.2.1 COT算法的不足

定义2 假设存在两个上下文有序的图形编辑操作序列L1、L2，若C(L1)=C(L2)，称L1、L2上下文并发，即L1‖L2。

定义3 假设存在图形编辑操作序列L1、L2，若满足条件L1‖L2，当且仅当C(L1)≫L1=C(L2)≫L2时，L1与L2等价，即L1≡L2(C(L1)≫L1指在文档状态为C(L1)时顺序执行L1中的操作)。

2.2.2COT算法的改进

在各个协同站点，都包含有如下的4个队列：产生队列GH、接收队列RH、等待队列WH及实际操作执行序列H(H中存放的是各个操作的最近转换形式，由LLT转换得到)。由操作转换的基本思想可知，本地操作的优先权高于远程操作。当某个远程操作获得优先权，进行转换执行时，若有本地操作产生，则将其加入到GH及H中。当某个远程操作执行完后，首先要查看执行站点的GH是否为空，若不为空，则将GH中的操作进行转换和封装，然后发送到各协同站点。

本文提出的并发控制算法分为两部分：一部分是GH中的操作转换封装、远程站点协同操作的接收及具体操作的执行，另一部分是对COT算法的改进，分别如算法3和算法4所示。

算法3

1) 本地操作的传播

步骤1 若站点的RH为空，则直接将GH中的操作封装为一个协同请求，传输到各个协同站点。

步骤2 若站点的RH不为空，则通过调用LLT(GH,RH)转换，将GH中的操作和RH中的操作进行转换，然后将GH中经转换后的操作封装为一个协同请求，传输到各个协同站点。

2) 远程操作的接收

步骤1 查看协同请求中的操作L是否因果就绪，若没有就绪，则将其加到WH的队尾；否则转步骤2。

步骤2 查看接收站点的RH是否为空，若为空，则查看协同请求中的操作序列L的上下文与DS的关系。若相等，则直接将L中的操作加到RH的队尾，并更新H；若不相等，则通过调用ICOT(L,DS)，将操作序列L转换为可执行形式，然后将其加到RH的队尾，并更新H,然后转步骤3。

步骤3 若RH非空，则直接调用ICOT(L,RH)。然后将转换后的操作加到RH的队尾，并更新H。

步骤4 一旦WH中的操作满足因果就绪，则将其与协同请求中的操作先进行转换结合，使其整体上下文有序(转换过程仍通过ICOT实现)，然后转步骤2。

算法4

LLT(L1,L2)：

算法5

SIT(O1,O2)：操作O1、O2是上下文等价

3) 远程操作的执行

选中将要执行的操作O=RH[0]，如果GH为空，则直接执行操作O即可；若GH不为空，则调用LLT(O,GH)，然后再执行经过转换后的操作。

ICOT算法，是对COT算法的改进，如算法6所示。

算法6

ICOT(L,ds)：

步骤1 判断L的上下文与ds间的关系。若C(L)=ds，则操作序列保持不变，否则转步骤2；

步骤2 获得上下文差异集CD，CD=ds-C(L)，对于CD中的每一组操作，均是上下文有序的。循环选取CD中的每一组上下文有序的操作序列Q，并从H中获得其操作序列的最近转换形式Q′，选择与L的上下文更接近的操作序列作为Q。若C(L)=C(Q)，则调用LLT(L,Q)；否则，令ds=C(Q)-C(L)，递归地调用ICOT(L,ds)。

2.3 实例分析

假设有7个协同操作，在各协作站点的执行顺序以及操作之间的关系如图3所示，初始的文档状态为空。假设在站点1，当接收远程操作时，GH中的操作还没有进行传播，即GH不为空；在站点2和3，当接收远程操作时，GH为空(假设远程操作接收后不会执行)。

图3 实例分析图

通过对改进前后的算法进行对比分析可知，改进后的算法在协同操作向其他站点发送之前，以及远程操作在接收之时，均进行了操作转换。且发送和接收的并不是操作的原始形式，而是其转换后的形式。通过这种预处理方式，可以有效地减少操作间转换的重复，减少转换的次数。

3 实验及算法的正确性分析

3.1 实验及分析比较

通过模拟实验对COT算法和本文算法的性能进行比较分析。假设有9个协同操作，在各协同站点的执行顺序以及各个操作之间的关系如图4所示(初始文档状态为空)。在两个算法中，任意操作的响应时间均由三部分构成：操作传播时间、操作在远程站点进行响应转换的时间、操作执行的时间，其中操作进行转换的时间起主导作用。故对两个算法进行模拟实验和性能分析，可以用操作执行时需转换的次数来代替操作的响应时间(如图5、图6所示)。

图4 模拟协同操作的执行

在站点2上的运行结果如图5所示。

图5 两种算法中操作转换次数的比较(站点2)

在站点3上的运行结果如图6所示。

图6 两种算法中操作转换次数的比较(站点3)

从实验结果对比分析可知，远程操作在转换执行时，若采用COT算法，则随着协同操作数的增加，操作执行时需转换的次数增加幅度远远大于采用本文算法。因此，本文算法可大幅度减少操作转换的次数，减少远程操作的响应时间，增加实时协同编辑时的效率。

3.2 改进前后算法时间复杂度的比较

对于改进前后的算法，其核心操作是进行操作间的转换，因此对改进前后算法的时间复杂度进行分析比较，也就是要对操作间的转换次数进行比较分析。改进后的本文算法，通过引入操作序列上下文有序及并发的概念，有效地减少了操作间转换的多次重复，减少了总的转换次数。

1) 假设存在操作O1,O2,…,On，C(O1)=C(O2)=…=C(On),若采用COT进行操作的转换执行，转换次数[9]为：

若采用本文算法，在转换的过程中，只有LLT转换。转换的次数为：T(n)=n-1。

2) 假设存在两组上下文有序序列S1=O1,1,O1,2,…,O1,n、S2=O2,1,O2,2,…,O2,n,S1和S2上下文并发。若采用COT对S2中的任一操作与S1中的操作进行转换执行，转换的次数为[9]：

若采用本文算法，在转换中采用LLT和SIT转换，进行转换的次数为：T(n,m)=2(m-1)×n+(n+m-1)。

对改进前后算法中有代表性的两类操作间的转换进行比较分析，理论上证明改进后的算法能有效地减少操作之间的转换次数，且所减少的转换次数均是COT算法中的冗余转换。

3.3 本文算法中操作的正确执行和转换

在COT算法中引入操作的上下文，是方便对操作的正确执行和转换进行统一管理。一个操作能正确执行，需满足:其定义上下文(操作产生时的文档状态)与执行上下文(操作执行时的文档状态)是相等的。两个操作能正确转换，则两个操作需是上下文等价的。本文算法延续使用了操作的上下文，为保证改进后算法中的并发操作能够正确执行和转换[10]，在本文算法中，真正只用到了LLT和SIT转换。因此只要LLT转换满足正确执行和转换的条件，那么本文算法中也同样满足条件。

4 结 语

本文针对在协同编辑中遇到的4种常见的不一致性问题进行阐述，对COT算法中存在的不足进行分析，并在此基础上，从两个方面进行改进。改进后的算法可有效地减少操作执行时转换的次数。但是，前文介绍的语义不一致问题没有解决，且在协同图形编辑中，对于图形编辑操作，有许多的操作是可以合并的，例如一个用户对同一图形对象的位置进行多次移动的操作，是可以合并为一个操作的。若在操作进行传播前能对这类型的操作进行一定的预处理，可以进一步减少转换的次数，提高协作的效率。怎样使得语义得到一致性维护，什么样的操作是可合并的操作，应对这些可合并的操作进行怎样的合并处理，将是下一步要研究的重点。

[1] 薛良贵. 协同图形编辑系统中操作合并的研究[D]. 广州：华南理工大学, 2010.

[2]KanawatiR.LICRA:Areplicated-datamanagementalgorithmfordistributedsynchronousgroupwareapplication[J].ParallelComputing,1997,22(13):1733-1746.

[3] 杨君, 窦万峰. 一种新的多版本增创算法[J]. 计算机学报, 2008, 31(4):702-710.

[4]EllisCA,GibbsSJ.Concurrencycontrolingroupwaresystems[N].AcmSigmodRecord.ACM,1989,18(2): 399-407.

[5]ResselM,Nitsche-RuhlandD,Gunzenh?userR.Anintegrating,transformation-orientedapproachtoconcurrencycontrolandundoingroupeditors[C]//Proceedingsofthe1996ACMConferenceonComputerSupportedCooperativeWork.ACM,1996:288-297.

[6] 廖斌, 何发智, 荆树旭. 实时协同工作系统中操作转换算法综述[J]. 计算机研究与发展, 2007, 44(2):326-333.

[7]SunD,SunC.Operationcontextandcontext-basedoperationaltransformation[C]//Proceedingsofthe2006 20thAnniversaryConferenceonComputerSupportedCooperativeWork.ACM,2006:279-288.

[8]SunD,SunC.Context-basedoperationaltransformationindistributedcollaborativeeditingsystems[J].IEEETransactionsonParallelandDistributedSystems, 2009, 20(10): 1454-1470.

[9] 许坚, 姜晓峰, 张坤．基于图形对象的一致性维护问题的研究[J]. 计算机应用与软件, 2012, 29(2): 261-265.

[10]Sun,C.OTFAQ:OperationalTransformationFrequentlyAskedQuestionsandAnswers[EB/OL].http://www3.ntu.edu.sg/home/czsun/projects/otfaq/.[11]SunC,WenH,FanH.Operationaltransformationfororthogonalconflictresolutioninreal-timecollaborative2deditingsystems[C]//ProceedingsoftheACM2012ConferenceonComputerSupportedCooperativeWork.ACM, 2012:1391-1400.

[12]Agustina,SunC,XuD.Operationaltransformationfordependencyconflictresolutioninreal-timecollaborative3Ddesignsystems[C]//ProceedingsoftheACM2012conferenceonComputerSupportedCooperativeWork.ACM, 2012:1401-1410.

[13]Agustina,SunC.Dependency-conflictdetectioninreal-timecollaborative3Ddesignsystems[C]//Proceedingsofthe2013ConferenceonComputerSupportedCooperativeWork.ACM, 2013:715-728.

[14]XuY,SunC,LiM.Achievingconvergenceinoperationaltransformation:conditions,mechanismsandsystems[C]//Proceedingsofthe17thACMConferenceonComputerSupportedCooperativeWork&SocialComputing.ACM, 2014: 505-518.

[15] 杨永涛, 黄国言.CSCW环境下协同设计并发控制算法的研究[J]. 现代计算机: 中旬刊, 2014(4): 16-21.

RESEARCH ON CONCURRENT CONTROL ALGORITHM BASED ON OPERATIONALTRANSFORMATION

Sun Min Wang Ruihua

(SchoolofComputerandInformationTechnology,ShanxiUniversity,Taiyuan030006,Shanxi,China)

To solve the inconsistency problem about results, causality, operational intention and semantics in collaborative graphic editing, a concurrent control algorithm based on operational transformation is proposed. The algorithm defines the conceptions about the context order, the concurrency of operation sequence, etc. From preprocess of collaborative editing and operational transformation in cooperative editing operation, the context-based operational transformation (COT) algorithm is improved. After verifying and analyzing the instance, it is found that the redundant problem in operation transformation in COT algorithm can be effectively reduced.

Concurrent control Collaborative editing Operational transformation Context in order

2015-09-20。山西省科技基础条件平台建设项目(2014091004-0105)；山西省高等学校教学改革重点项目(J2013010)。孙敏，副教授，主研领域：计算机网络。王瑞花，硕士生。

TP391

A

10.3969/j.issn.1000-386x.2017.01.048