二维表格实时协同编辑系统的一致性维护

魏 赟,宗 旭,高丽萍,2

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

2(复旦大学 上海数据科学重点实验室,上海 200093)

0 引 言

随着分布式计算系统的发展,大量的协同系统被开发出来,并越来越多地被应用到现实世界中,协作应用程序影响了社会变革,吸引了学术研究人员和行业开发人员的研究和探索.

协同编辑作为CSCW(Computer Supported Cooperative Work)中最重要的领域,通过在协作用户之间交换专业知识,提高了共享任务的质量和效率.同时,协同编辑系统支持和谐的人机交互,允许地理位置分散的用户同时编辑共享文档的任何部分,并且不会相互阻塞.

电子表格是应用最广泛的计算机应用程序之一,金融行业、商业组织和政府以及日常生活中的普通人都经常使用它们.对电子表格和基于表格的文档进行实时协同编辑的需求早已得到学术界和工业界的认可.近些年,随着大数据和云计算的兴起,电子表格在数据分析领域担任着越来越重要的角色,电子表格协同编辑系统越来越趋向于大规模化,同时,这也带来了一些不小的技术挑战:一个是大规模协作中不可避免的会发生大量正交冲突问题,这给一致性维护带来了更大的难度;另一个是对计算性能有很高的要求,这是协同编辑成功的关键因素.已发布的支持二维表格的协同编辑系统设计复杂,效率低下,不适合大规模的协同编辑[1,2].

总之,在大数据和云计算时代,如何以更高的效率解决电子表格中的冲突是大规模协同系统面临的主要挑战.因此,为电子表格协同编辑系统探索和研究基于CRDT的新同步技术是必要的.

针对以上需求,本文提出了一种新的基于CRDT的二维电子表格协同编辑方法.1)定义了操作的正交冲突关系、一维冲突关系、互斥关系和相容关系;2)基于操作之间的关系,设计了冲突消解方案,用以维护各个站点副本的一致性,并保留协作用户的意图;3)从理论上分析了时间复杂度和空间复杂度;4)通过案例分析、理论论证和构建原型系统验证了该方法的正确性和可行性.

1 相关工作

为了实现高响应性,协同编辑系统采用了完全复制的体系结构,这给一致性维护带来了巨大挑战[3,4].操作转换算法(OT,Operation Transformation)[5-8]特别适合于一致性维护,并且已经被提出了近30年.OT算法的主要思想是,本地编辑操作一经产生就立即执行,然后传播到远程站点.远程操作在执行之前需要针对并发的操作进行转换,以便修复冲突分歧.

自Ellis等开发第一个OT算法以来,大多数已发布的OT算法仅支持基于字符的纯文本操作,电子表格文档作为一种非纯文本的文档形式,目前仅有少数几篇文献[9-11]解决了在电子表格上进行协同编辑的不一致问题.在文献[9]中,二维电子表格表示为一系列行或列,然后将一维OT技术(控制算法和转换函数)直接用于支持表格上的操作.但这种分层方法不能很好地扩展到具有大量行/列的表格,此外,文献[9]中的技术也无法解决正交冲突[10]问题.在文献[10]中,Sun等人首次指出二维电子表格协同编辑系统中存在特殊冲突问题——正交冲突,设计了一个多版本(MV,Multi-Version)位置,既保留了用户的操作意图,也实现了文档的一致性维护,成功将OT从一维空间扩展到二维空间;但是在数据量非常庞大时,这种方法需要耗费相当大的空间来存储每个版本,空间复杂度较高.文献[11]在GOTO算法的基础上进行了改进,支持表格文档环境下的协同,但是对于Insert、Delete、Merge和Split操作间的16种并发情况,需要设计各自的转换函数,算法极其复杂;且底层使用类似矩阵的结构来存储表格,维护困难.

因为OT固有的复杂性,不适合大规模协作[1].近年来,另一类协同编辑算法CRDT[12-17]被提出,并逐渐成为协同计算和分布式计算领域的研究热点.它的主要思想是设计可交换的并发操作,不再需要转换,可以按任何顺序执行并发操作;通过为所有操作对象分配唯一标识符(ID),将所有对象按总体顺序放入抽象数据结构中.因此,CRDT算法可以保留协作用户的操作意图,并保证最终的一致性.

Lv等人[1]将协同编辑的原子操作从“字符”提升到“字符串”,大大降低了算法的时间复杂度,提升了协同的效率.Gao等人[18,19]提出了在大规模实时图形协作编辑环境下的冲突消解方案.在对算法效率要求更高的移动环境下,Lv等人[20,21]基于CRDT提出了适用于移动设备的轻量级协同编辑算法,进一步拓展了CRDT在大数据时代的应用.这些工作通过理论和实验证明了CRDT效率更高,更适用于大规模协作环境,在处理大规模数据时更有优势.

目前,在二维电子表格协同编辑系统中,基于CRDT的研究很少,最主要的挑战是如何保证共享电子表格的一致性,以及在大数据量情况下达到更高的效率.而现有的基于OT算法的电子表格协同编辑模型设计复杂,底层数据结构维护困难、效率低下,不适用于大规模协作,并且OT算法通过状态向量(SV)来判断并发操作,在协作用户动态加入和退出的场景下效率极低,这是大规模的协同环境中不能被接受的.本文提出的算法跟传统的OT算法相比,有很大的优势.例如文献[10]将COT改进后应用到表格协同场景下,在处理正交冲突时,需要额外调用一维冲突的转换函数,并且在集成远程操作时,需要对比操作历史序列中的所有操作,进行操作转换,这可能会产生无用的比对,浪费较多的系统资源和时间.本文提出的基于CRDT的算法根据唯一ID,能够快速找到目标操作,减少无用比对,提高协同效率.

2 实时表格协同中的一致性维护

2.1 表格的操作关系

现有的研究表明,表格协同编辑系统的操作主要集中在3个基本问题上:单元格的插入、删除和修改.为简单清晰起见,本文中的操作仅限于单个单元格,但本文提出的解决方案可以拓展为插入/删除任意数量的单元格(例如整行或整列).

操作的影响范围表示为ER(O),是指操作O执行后直接或间接受到影响的单元格集合.如果O是行维度的,则ER(O)表示目标行中操作位置及其右侧的所有单元格;如果O是列维度的,则ER(O)表示目标列中操作位置及其下方的所有单元格.如果两个操作的影响范围具有以下定义的共享单元格,则这两个操作是重叠的.

定义1.重叠关系(#)

给定两个操作Oi和Oj,当它们满足ER(Oi)∩ER(Oj)≠{}时,Oi与Oj重叠,表示为Oi#Oj.

定义2.正交关系(⊥)

给定两个操作Oi和Oj,若它们的操作维度不同,即Oi.dim≠Oj.dim,Oi与Oj正交,表示为Oi⊥Oj.

其中dim表示操作的维度,可以取两个值之一:row(行)或col(列).行操作在目标行中具有从左向右(插入)或从右向左(删除)的位移效果;列操作在目标列中具有从上到下(插入)或从下到上(删除)的位移效果.

如果正交操作Oi和Oj是并发的(符号表示为Oi‖Oj),并且他们的影响范围重叠,那么当它们以不同的顺序执行时,可能会导致不一致的状态,这种关系称为正交(或二维)冲突,其定义如下:

定义3.正交(或二维)冲突(⊕)

给定两个操作Oi和Oj,如果它们满足以下条件,则认为Oi⊕Oj:

1)Oi⊥Oj;

2)Oi‖Oj;

3)Oi#Oj.

定义4.平行操作关系(∥)

给定两个操作Oi和Oj,如果它们不是正交关系,则认为它们是平行的,表示为Oi∥Oj.

如果在同一行或者同一列中执行两个并发操作,它们以不同的顺序执行可能会导致文档状态的不一致,这两个操作之间关系的称为一维冲突,定义如下:

1)Oi∥Oj;

2)Oi‖Oj;

3)Oi#Oj.

定义6.互斥关系(⊖)

给定两个操作Oi和Oj,根据它们的操作语义,如果只有一个能执行,则它们是互斥的,表示为Oi⊖Oj.

定义7.相容关系(⊙)

图1 表格中操作之间的关系Fig.1 Relations among operations in a table

2.2 总体框架和基本思路

在介绍总体框架和方法之前,以下先介绍一些相关的定义和概念.

定义8.表格操作对象(O)

在表格协同编辑系统中,一个操作对象表示为O,它是一个12元组,其中:1)t是操作O的类型,它可能是插入(insert),删除(delete)或修改(update);2)l是一个bool变量,它有两个值true和false分别表示本地操作和远程操作;3)key表示当前操作的唯一标识符;4)dim是一个表示操作维度的变量;5)(x,y)表示当前操作在表格中的位置坐标;6)content表示所操作单元格的内容;7)visible代表操作的状态,当操作无效时值为0,否则值为1;8)pre_key代表前一个操作的标识符;9)指针prior用来指向双链表中的前一个操作;10)指针用来指向双链表中的下一个操作;11)link是一个指针用来链接双链表与哈希表HT;12)s是操作执行时的文档状态.

定义9.(O)给定任意两个操作Oi和Oj,当Oi在双链表中的位置位于Oj之前时,OiOj.

定义10.操作的全序关系(O⟹)

给定任意3个操作Oi,Oj,Ok,若全部操作序列满足以下条件,则它们之间符合全序关系:

1)OiOj或者OjOi或

2)OiOj,OjOk,那么OiOk

定义11.操作的唯一标识符(ID)

一个操作的ID是一个3元组,其中:

1)s是当前会话的标识符,它是一个全局自增的变量

2)ssv是一个操作的状态向量之和

3)site是站点的唯一标识符

定义12.(IDO)给定两个操作Oi和Oj,这两个操作的ID被表示为IDOi和IDOj,若满足以下条件,IDOiIDOj:

1)IDOi[s]

2)IDOi[s]=IDOj[s],IDOi[ssv]

3)IDOi[s]=IDOj[s],IDOi[ssv]=IDOj[ssv],IDOi[site]

整体框架如图2所示,电子表格协同系统由多个协作站点组成,每个站点维护视图(View)和模型(Model)两个部分.View是前端显示界面,协作人员在该界面直接进行操作和交互.Model由一个名为HT的hash表和一个双链表组成,其中HT存储操作与其在双链表中位置关系的映射,使得能够在O(1)时间内找到目标操作位置;双链表按照一定的顺序链接所有的本地和远程操作,包括可见和不可见的操作,可见操作表示有效的可执行操作,不可见操作表示无效和不可执行的操作.

图2 整体框架Fig.2 Whole framework

整体的控制流程如下.每个站点上的用户可以随时生成本地操作(Local Operations),同时也可以接收远程操作(remote Ox).本地站点上生成一个操作时,该操作立即执行,然后将它直接连接到双链表的末尾.当站点接收到远程操作Ox时,应先HT在中找到Ox的目标操作.假设O4是目标操作,而O5与Ox具有相同的目标操作,且O5和Ox来自同一个状态,则调用冲突检测机制(ConflictDetection)来检测四种关系.此时需要考虑4种情况:

1)若它们之间存在正交冲突关系,则进行一定的转换达到一种联合效果;

2)若它们之间存在一维冲突关系,则需要根据它们的依赖优先级和标识符决定执行顺序;

3)若它们具有互斥关系,则它们的依赖优先级和标识符决定了该执行哪个操作;

4)若它们是相容关系,则根据标识符决定执行顺序.

2.3 冲突消解

算法1介绍了如何解决两个操作之间的正交冲突.O1表示已经执行的操作,O2表示要执行的远程操作.根据两个操作的ID决定它们的先后顺序.

算法1.OrthogonalConflictResolve(O1⊕O2)

1.INPUT:O1⊕O2

2.ifID(O1)ID(O2) then

3. Transform(O2,O1)

4.O2is executed and linked afterO1

5.else

6.O1is undone,O2is executed

7. Transform(O1,O2)

8.O1is redone and linked afterO2

9.end if

在算法1中,操作O1和O2之间是正交冲突关系,为达到联合效果,需要对操作进行转换.算法2介绍了转换的具体流程.如果O1是行维度插入,O2是列维度插入,那么在它们的交叉点上创建一个多版本位置Multi-Version(MV)position[10](第3行),MV位置中每个单元格都属于一个特定维度.创建MV位置时,它有两个初始单元格:一个被当前单元格占据,另一个先置为空,可以通过直接插入或间接移动单元格来填充该空白位置.接着复制(O1.x,O2.y+1)位置上的内容插入到(O1.x+1,O2.y)(第4行).第5～8行介绍的是其他各种情况的处理方案.

算法2.Transform(O2,O1)

1.INPUT:O2,O1,

2.ifO1.dim=row&&O1.t=insert&&O2.t=insetthen

3. create an MV position at(O1.x,O2.y)

4. copy the cell at position(O1.x,O2.y+1)and insert it to position(O1.x+1,O2.y)

5.else ifO1.dim=row&&O1.t=insert&&O2.t=deletethen

6. create an MV position at(O1.x,O2.y)

7. copy the cell at position(O1.x,O2.y+1)to position(O1.x-1,O2.y)

8.else …//other cases are omitted for conciseness

9.end if

算法3介绍了如何解决两个操作之间的一维冲突.如果O1和O2的操作位置相同,那么需要进一步判断两个操作的类型,调整执行顺序(第2～11行).否则根据和的重叠关系调整执行顺序(第15～18行).

2.ifO1.(x,y)=O2.(x,y) then

3. ifO1.t=insert&&O2.t=insertthen

4. ifID(O1)ID(O2) then

5.O2is executed and linked afterO1

6. else

7.O1is undone,O2is executed

8.O1is redone and linked afterO2

9. end if

10. else if…//other cases are omitted for conciseness

11. end if

12.else

13. ifO2.(x,y)∉ER(O1) then

14.O2is executed and linked afterO1

15. else

16.O2is undone,O2is executed

17.O2is redone and linked afterO2

18.end if

算法4介绍了如何解决两个操作之间的互斥关系.根据ID判断优先级,将优先级高的操作链接在前面,而优先级低的保存为墓碑链接在后面.

算法4.MutualExclusionResolve(O1⊖O2)

1.INPUT:O1⊖O2

2.ifID(O1)ID(O2) then

3.O2.visible=0,O2is not executed and linked afterO1

5.else

6.O1is undone,O2is executed

7.O1.visible=0,O1is linked afterO2

8.end if

算法5介绍了如何执行两个相容操作.当O1.key小于O2.key时,直接执行O2并链接到O1后面,否则将O2链接到O1前面.

算法5.CompatibleResolve(O1⊙O2)

1.INPUT:O1⊙O2

2.ifID(O1)ID(O2) then

3.O2is executed and linked afterO1

4.else

5.O2is executed and linked beforeO1

6.end if

2.4 集成本地/远程操作

算法6介绍了如何集成本地操作.如果目标操作不为空,则通过哈希表直接找到操作位置并链接在目标操作后(第8～10行);如果新一轮会话开启,目标操作为空,那么需要判断双链表是否为空,若为空,直接将O链接到head后执行,否则链接到双链表的末尾(第2～7行).

算法6.IntegrateLocal(O)

1.INPUT:O

2.ifO.pre_key==NULL then

3. ifhead==NULL then

4.Ois executed and linked next tohead

5. else

6.Ois executed and linked after tail by scanning the list one by one

7. end if

8.else

9.Pre=hash(O.pre_key),Ois double linked next toPre

10.end if

11.Ois broadcast to remote sites

算法7介绍了如何集成远程操作O.在第2行中,通过唯一标识符直接找到O的目标操作,如果目标操作后有其余操作存在,那么需要依次判断该操作与O的关系(第5～44行):当Next和O来自同一状态时,调用相应函数解决冲突(第9～20行),否则逐一向后检查每个操作直至首次遇到ID(Next第≻ID(O)(21～23行).在第28-38行中,找到操作O的正确插入位置,如果存在冲突,调用相应函数来解决;否则将O链接到Next前面.之后继续沿着双链表向后判断冲突(第41～43行).

算法7.IntegrateRemote(O)

1.INPUT:O

2.Tar=hash(O),Next=Tar,next

3.ifNext==NULL then

4.Ois executed and double linked afterTar

5.else

6. whileNext.key.s

7.Next=Next.next

8. end while

9. whileNext!=NULL &&ID(Next)ID(O) do

10. ifNext.s==O.s&&(Next,O)==Next⊕O&&Next.visible==1 then

11. if isExistMV(Next,O)==false then

12. Transform(Next⊕O)

13. end if

14.Next=Next.next,Continue

15. else ifNext.s==O.s&&(Next,O)==Next⊙O&&Next.visible==1 then

16.Next=Next.next,Continue

19. else ifNext.s==O.s&&(Next,O)==Next⊖O&&Next.visible==1 then

20. MutualExclusionResolve(Next⊖O)

21. else

22.Next=Next.Next,Continue

23. end if

24. end while

25. ifNext==NULL then

26.Ois executed and linked afterNext.prior

27. end if

28. ifID(O)ID(Next) then

29. ifNext.s==O.s&&(Next,O)==Next⊕O&&Next.visible==1 then

30. OrthogonalConflictResolve(Next,O)

34. MutualExclusionResolve(Next⊖O)

35. else ifNext.s==O.s&&(Next,O)==Next⊙O&&Next.visible==1 then

36. CompatibleResolve(O1⊙O2)

37. else

38.Ois executed double linked beforeNext

39. end if

40. end if

41. whileNext!=NULL do

42. detect and handle conflicts as above

43. end while

44.end if

3 正确性证明与复杂度分析

3.1 案例分析

为了验证所提出方法的正确性和可行性,本文举了一个综合示例来解释算法的执行过程.假设3个站点参与协同任务,并且存在ID[site1]

图3 协作的综合案例Fig.3 A comprehensive case of collaboration

在站点1,本地操作O1立即执行,L1=O1.当操作O2到达时,O1与O2是正交冲突关系,需要进行转换,由于IDO1IDO2,所以将O2链接到O1后面.L1=O1-O2.接着O4到达,它与O1是相容关系,因为IDO1IDO4,又由于O2是O4的因操作,所以将O4链接到O2后面.L1=O1-O2-O4.当O3到达,其文本状态与O1相同,依次向后进行冲突检测,它与O1,O2均为相容关系,与O4是互斥关系,存在IDO4≻IDO3,因此O4被撤销,执行O3,并将O4链接在O3后面.L1=O1-O2-O3-O4.当O5到达,其目标操作为O3,因为O3是它的因操作且O3的状态与O1相同,所以从O1开始向后进行冲突检测,其与O1是一维冲突,根据算法3,操作O5的执行位置在O1的影响范围内,所以撤销O1后执行O5,再重新执行O1,O5与O2是正交冲突关系,但由于多版本位置已存在,不需要进行转换,IDO4IDO5,因此O5链接在O4后面.L1=O1-O2-O3-O4-O5.

在站点2,本地操作O2和O4立即执行,L2=O2-O4.当O3到达,其与O2为相容关系,与O4为互斥关系,存在IDO3IDO4,因此撤销O4,执行O3,此时L2=O2-O3-O4.当操作O5到达,它的目标操作为O2,与O2为正交冲突关系,因此进行转换;O3是其因操作,存在IDO4IDO5,将O5链接到O4后面.L2=O2-O3-O4-O5.最后操作O1到达,其文本状态与O2相同且IDO1IDO2,O1与O2为正交冲突关系,但此时多版本位置已存在,所以无需转换,撤销O2,执行O1后重新执行O2并将其链接在O1后面.L2=O1-O2-O3-O4-O5.

在站点3,本地操作O3和O5立即执行.L3=O3-O5.

当操作O2到达,O2与O3文本状态相同,O3又是O5的因操作,所以依次与它们进行冲突检测,O2与O3是相容关系,与O5是正交冲突关系,需要进行转换,存在IDO2IDO3IDO5,因此O2链接在O3前面.L3=O2-O3-O5.当操作O4到达,其目标操作为O2,所以从O2开始依次向后进行冲突检测,O2是O4的因操作,O3与O4为互斥关系,存在IDO4≻IDO3,因此O4不执行,但将其链接在O3后面.L3=O2-O3-O4-O5.最后,操作O1到达站点3,其文本状态与O2相同,且与O2是正交冲突关系,但此时多版本位置已存在,无需进行转换,由于IDO1IDO2,所以先撤销O2,接着执行O1,再重新执行O2,将O1链接到O2前面.L3=O1-O2-O3-O4-O5.

最终3个站点的操作序列是相同的:L1=L2=L3=O1-O2-O3-O4-O5.由图3所示,3个站点执行结果状态是一致的.

3.2 最终一致性和意图保留

如果表格协同编辑系统符合以下两个标准,则认为该系统是正确的:

定理1.最终一致性:当全部协作站点执行了所有操作后,不同站点间的文档状态是一致的.

证明：在表格协同编辑系统中,状态相同的远程操作可能会存在冲突,在下面的证明中,所有操作都是以相同状态的远程操作形式给出,此时需要考虑4种情况.

(1)对于两个远程操作Oi和Oj,它们是正交冲突关系.不论以任何顺序执行,双链表中的操作顺序都是相同的.

假设当前双链表为L=O1-O2-…Op-Oq-…-On,且Oi、Oj的目标操作均为Op.

1)若先接收到Oi,将Oi链接到Op后面,此时双链表为L=O1-O2-…Op-Oi-Oq-…-On,然后Oj到达,需要考虑两种情况.

若IDOiIDOj,则进行转换后直接执行Oj并链接到Oi后面,此时双链表为L1=O1-O2-…Op-Oi-Oj-Oq-…-On.

若IDOi≻IDOj,则撤销Oi,执行Oj,进行转换后重新执行Oi并链接到Oj后面,此时双链表为L2=O1-O2-…Op-Oj-Oi-Oq-…-On.

2)若先接收到Oj,将Oj链接到Op后面,此时双链表为L=O1-O2-…Op-Oj-Oq-…-On,然后Oi到达,考虑两种情况.

若IDOiIDOj,则撤销Oj,执行Oi,进行转换后重新执行Oj并链接到Oi后面,此时双链表为L1′=O1-O2-…Op-Oi-Oj-Oq-…-On.

若IDOi≻IDOj,则进行转换后直接执行Oi并链接到Oj后面,此时双链表为L2′=O1-O2-…Op-Oj-Oi-Oq-…-On.

由以上证明可知,双链表L1和L1′相同,双链表L2和L2′相同.

(2)对于两个远程操作Oi和Oj,它们是一维冲突关系.不论以任何顺序执行,双链表中的操作顺序都是相同的.

假设当前双链表为L=O1-O2-…Op-Oq-…-On,且Oi、Oj的目标操作均为Op.

1)若先接收到Oi,执行后将Oi链接到Op后面,此时双链表为L=O1-O2-…Op-Oi-Oq-…-On,然后Oj到达,需要考虑两种情况.

①若Oj和Oi的操作位置相同,此时有5种情况需要考虑.

若Oi为插入操作,Oj为插入操作,则通过判断两个操作的ID决定执行顺序.此时双链表为L1=O1-O2-…Op-Oi-Oj-Oq-…-On,或L1=O1-O2-…Op-Oj-Oi-Oq-…-On.

若Oi为插入操作,Oj为删除操作,则撤销Oi,执行Oj后再执行Oi并链接到Oj后面,此时双链表为L2=O1-O2-…Op-Oj-Oi-Oq-…-On.

若Oi为插入操作,Oj为修改操作,则撤销Oi,执行Oj后再执行Oi并链接到Oj后面,此时双链表为L3=O1-O2-…Op-Oj-Oi-Oq-…-On.

若Oi为删除操作,Oj为插入操作,直接执行Oj并链接到Oi后面,此时双链表为L4=O1-O2-…Op-Oi-Oj-Oq-…-On.

若Oi为修改操作,Oj为插入操作,直接执行Oj并链接到Oi后面,此时双链表为L5=O1-O2-…Op-Oi-Oj-Oq-…-On.

②若Oj和Oi的操作位置不同,此时有两种情况需要考虑.

若Oj.(x,y)∈ER(Oi),则撤销Oi执行Oj,再重新执行Oi并链接到Oj后面,此时双链表为L6=O1-O2-…Op-Oj-Oi-Oq-…-On.

若Oj.(x,y)∉ER(Oi),直接执行Oj并链接到Oi后面,此时双链表为L7=O1-O2-…Op-Oi-Oj-Oq-…-On.

2)若先接收到Oj,将Oj链接到Op后面,此时双链表为L=O1-O2-…Op-Oj-Oq-…-On,然后Oi到达,需要考虑两种情况.

①若Oi和Oj的操作位置相同,此时有5种情况需要考虑.

证明过程同 1)中的①,分别得到L1′=O1-O2-…Op-Oi-Oj-Oq-…-On,或L1′=O1-O2-…Op-Oj-Oi-Oq-…-On;L2′=O1-O2-…Op-Oj-Oi-Oq-…-On;L3′=O1-O2-…Op-Oj-Oi-Oq-…-On;L4′=O1-O2-…Op-Oi-Oj-Oq-…-On;L5′=O1-O2-…Op-Oi-Oj-Oq-…-On;

②若Oi和Oj的操作位置不同,此时有两种情况需要考虑.

证明过程同1)中的②,分别得到L6′=O1-O2-…Op-Oj-Oi-Oq-…-On;L7′=O1-O2-…Op-Oi-Oj-Oq-…-On.

由以上证明可知,L1=L1′,L2=L2′,L3=L3′,L4=L4′,L5=L5′,L6=L6′,L7=L7′.

(3)对于两个远程操作Oi和Oj,它们是互斥关系.不论以任何顺序执行,双链表中的操作顺序都是相同的.

假设当前双链表为L=O1-O2-…Op-Oq-…-On,且Oi、Oj的目标操作均为Op.

1)若先接收到Oi,执行后将Oi链接到Op后面,此时双链表为L=O1-O2-…Op-Oi-Oq-…-On,然后Oj到达,根据ID判断操作的执行顺序,且优先级低的操作不执行,保存为墓碑链接到双链表中.此时双链表为L1=O1-O2-…Op-Oi-Oj--Oq-…-On,或L2=O1-O2-…Op-Oj-Oi--Oq-…-On.

2)若先接收到Oj,执行后将Oj链接到Op后面,此时双链表为L=O1-O2-…Op-Oj-Oq-…-On,然后Oi到达,根据ID判断操作在双链表中的位置,且优先级低的操作不执行,保存为墓碑链接到双链表中.此时双链表为L1′=O1-O2-…Op-Oi-Oj--Oq-…-On,或L2′=O1-O2-…Op-Oj-Oi--Oq-…-On.

由以上证明可知,L1=L1′,L2=L2′.

(4)对于两个远程操作Oi和Oj,它们是相容关系.不论以任何顺序执行,双链表中的操作顺序都是相同的.

证明过程同(3),根据ID判断两个操作在双链表中的执行位置.

由以上证明可知,本文所提出的方法能够确保每个站点都维护相同的历史操作序列,最终取得一致的文本状态.

定理2.意图保留:需要在所有协作站点尽可能保留并发操作的效果.

证明:基于上述的最终一致性证明,远程操作的效果都尽可能得到了保留.在此考虑4种情况:

1)正交冲突操作:采用联合效果[10](Union Effect)保留冲突操作的影响;

2)一维冲突操作:两个操作的影响都得到了保留;

3)互斥操作:只需保留其中一个操作的效果;

4)相容操作:保留了所有操作的效果.

因此本文所提出的方法可以实现用户的意图保留.

3.3 复杂度分析

时间复杂度:如算法6所示,由于使用唯一ID和哈希表来搜索前置操作,所以在集成本地操作时,最佳情况的时间复杂度为O(1);而当一个新会话开始时,需要从头至尾扫描双链表,找到上一个会话中的最后一个操作,这是最坏情况,时间复杂度为O(n),其中代表此时站点中双链表上的所有操作数.在集成远程操作时,如算法7所示,最佳情况下的时间复杂度为O(1),在这种情况下,使用ID和哈希表直接找到目标操作,由于目标操作后没有其他操作,该远程操作可以直接链接在目标操作的后面;在最坏的情况下,远程操作到达时需要从目标操作开始依次向后判断冲突和查找正确的执行位置,此时的时间复杂度为O(m),其中m是目标操作后面链接的操作数.

空间复杂度:本文所提出的方法中,每个操作都是一个12元组,假设它的长度为L,每个站点上的双链表中有n个操作,则空间复杂度为O(L×n).同时每个站点还需要一个哈希表来提高集成速度,而哈希表的空间开销与双链表是相同的,所以总的空间复杂度为O(2L×n).

4 原型系统

为了验证所提出算法的合理性以及正确性,本文基于IntelliJ IDEA平台开发了Web端的二维表格协同编辑系统(Co-Table).其前端使用LuckySheet开源框架,后端采用轻量级框架SpringBoot搭建,并且采用WebSocket全双工通信协议进行持久的信息传输.

如图4是客户端的编辑界面,插入、删除、修改等基本功能都是基于LuckySheet实现的,为了实现协同编辑,其后台使用日志记录所有用户以及他们的操作,然后将这些操作通过WebSocket协议传播到远程站点,远程站点接收到操作后进行判断和冲突消解.如图5所示,后台日志还记录了用户的连接和断开以及当前参与协同的用户数目.

图4 前端界面Fig.4 Front-end interface

图5 协作用户与操作日志Fig.5 Collaboration users and operation logs

5 总结与展望

本文提出了一种新的基于CRDT的二维电子表格协同编辑一致性维护方案.首先定义了操作之间的4种关系;其次,根据操作之间的关系,设计集成本地和远程操作的算法,维护各个站点间表格文档的一致性;接着,从理论上分析了该方案的时间复杂度和空间复杂度;最后,通过案例分析、理论论证以及构建原型系统,验证了所提出的方法能够有效解决冲突、保留用户意图,实现最终的文本一致.

在未来的研究中,我们将继续探索以下方面:1)表格文档中的操作不仅限于简单的插入和删除,后续将继续研究单元格合并和拆分等操作的协同;2)撤销是表格文档中很重要的功能,将探索Undo/Redo协同的实现;3)随着移动端的普及和云计算的兴起,我们将探索移动云环境下协同的一致性维护.