富文本协同编辑中基于树型结构地址空间转换的一致性维护

刘 亚,韩建功,高丽萍,2 ,曲 博

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

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

3(鹏城实验室 网络空间安全中心,广东 深圳 518066)

0 引 言

随着网络技术的发展,在线办公与远程协作已经变成了一种重要的工作模式,这不仅可以节约员工的通勤成本还更容易发挥群体的智慧,也体现了国际计算机协会(ACM)中以“人为中心的计算(Human-Centered Computing,HCC)”[1].协同编辑系统允许多个身处不同地理位置的用户通过网络查看和编辑共享对象,包含文本、矢量图、表格和XML文件等,它一直是计算机支持协同工作(CSCW)研究的重要课题.数据是信息系统的核心,所以共享对象的一致性维护是实时协同编辑的一个关键问题.在理论研究方面,经过30多年的发展,围绕着支持操作意图一致性这个前提逐渐形成了3种不同的协同编辑算法,分别是操作转换(Operation Transformation,OT),地址空间转换(Address Space Transformation,AST)和无冲突复制式的数据类型(Confict-free Replicated Data Type,CRDT).这些经典的协同编辑算法已经被应用到现实世界的开发与工作中[2-4],衍生出许多优秀的协同编辑Web应用,例如Google Docs、Yjs,石墨文档和飞书等.

为了解决纯文本文档协同工具无法满足用户的客制化需求这个问题,富文本编辑器应运而生,但是这种树型结构文档也为协同编辑系统带来了更加复杂的并发场景与用户意愿冲突.此外这些主流的实时协同系统大多都是基于经典的OT或CRDT算法设计的,但在实际开发中设计完备的OT转换函数十分复杂不易理解并且迭代更新困难,且某些CRDT算法已经被证实存在正确性问题[5,6],此外设计一种既能处理普通的执行操作又能处理用户发起的撤销操作的高效、正确的协同算法仍然是一个很大的挑战,因为这两种操作会以各种形式相互干扰[7].

为了解决上述问题,本文提出了一种基于位置的节点寻址方案和支持撤销(Undo)操作的拓展AST算法,使其能够支持树型文档的一致性维护,最后给出相应的案例分析和该算法对一致性维护的证明,并给出结论和未来研究方向的展望.

1 基本术语与相关工作

1.1 因果先序关系与并发关系

在分布式系统中Lamport逻辑时钟最先定义了操作间的偏序关系,即happened before和concurrent.在此基础上,Sun等人提出协同编辑系统中的因果先序关系和并发关系,详情见定义1和定义2.

定义1.因果先序关系.给定任意两个由站点i,j生成的操作Oa和Ob,当且仅当以下3个条件之一满足时,存在Oa因果先序于Ob(记作Oa→Ob):1)i=j,Oa生成在Ob之前;2)i≠j,Oa在站点j上的执行要先于Ob的生成;3)存在一个操作Ox,满足Oa→Ox并且Ox→Ob.

定义2.并发关系.给定任意两个操作Oa与Ob,当且仅当Oa与Ob,既不存在Oa→Ob,也不存在Ob→Oa时,称Oa与Ob是并发关系(独立关系).

1.2 全序关系

全序关系的提出使得任意两个操作或操作对象可以进行比较,协同编辑系统通常采用某种“优先级”来定义全序关系.例如AST算法的TOrder( )关系,为了确定两个插入字符节点的顺序,规定字符节点对应sum(SV)较小的排在前面,若相等则对应生成站点较小的排在前面.TOrder( )关系本质上是对Lamport借助进程ID确定全序关系方法的进一步完备.

1.3 一致性模型

为了解决协同过程中的不一致性问题,主流的协同编辑算法通常根据CCI模型进行设计与开发.下文给出了CCI模型[6]的具体描述,如定义3、定义4和定义5.

定义3.结果一致性(Convergence).当会话中所有的协同站点执行完相同的一组操作后,每个站点保存的共享副本完全相同.

定义4.因果一致性(Causality preservation).对于任意一对操作Oa和Ob,如果Oa→Ob,则在所有站点上Oa都要先于Ob执行.

定义5.意图一致性(Intention preservation).对于任意一个操作O,它在远程站点执行效果与其在本地站点执行效果相同,并且O的执行效果不会干扰到其他并发操作.

1.4 Undo前提

在协同编辑系统中要保证所有Undo操作都是有意义的,因此Undo操作必须满足以下情况:每个用户只能Undo自身执行过的非Undo操作,不能Undo曾经被Undo过的操作.

1.5 相关工作

CRDT是一种新颖的支持实时协同编辑的一致性维护方法.由Oster等人在2006提出,近几年在GitHub上出现了许多基于CRDT的协同编辑开源项目,如Teletype和Alchemy Book.同时它也支持树型结构数据的一致性维护,例如支持云端协同设计场景中分层访问控制的CAD系统[8]和文件管理系统[9],CRDT算法的优点是适用于大规模的P2P协同编辑领域[10-12],但是墓碑机制牺牲了空间上的复杂度,此外CRDT的变种算法Logoot也被证实存在一些正确性问题.

OT是第1个也是应用范围最广的支持协同编辑的一致性维护方法,OT算法及其变种被应用到许多协同编辑系统中,例如文本编辑[13]和协同几何建模模型[14],同时它也率先支持树型数据层次访问的协同算法[15].OT算法的优点是本地操作响应性高.同时它也面临一些问题,例如,设计一个完全满足CCI模型的操作转换函数和控制算法是非常复杂和困难的,此外在实际开发中不断有特定协同场景下的“puzzle”被发现.

AST算法与上述两种算法不同,它为共享对象的一致性维护提供了新的思路[16].其核心思想是通过时间戳和回溯函数将文档的地址空间恢复至远程操作生成时的状态,确定远程操作的执行形式,以此来保证共享对象的一致性维护,并设计专门的自动压缩对象序列来解决元数据开销问题[17].这种巧妙的地址空间转换算法被应用到了许多领域,如移动设备评论系统的部分复制方案[18]和不稳定网络环境下协同文档的一致性维护[19].

如何实现完备的撤销功能一直是协同编辑系统面临的难题,首先,在协同编辑系统中该功能要支持选择性撤销,而不仅仅是按顺序撤销最后一个操作.其次,从用户的角度来看,此撤销必须是正确的,系统要返回到从未执行过目标操作的状态.很多协同算法都已支持撤销功能[20,21],但撤销操作的具体实现方式有所差异.例如在一些OT算法中,撤销函数通过生成目标操作的逆操作来抵消操作的影响[22].而在一些AST算法和CRDT算法中则是通过引入计数器概念统计用户的操作意愿来实现撤销功能[23,24],这种撤销方式的好处是尽可能维护用户的意图并且避免逆操作生成和执行时带来的特定场景下的“puzzle”.

2 数据模型与操作模型

与传统线性文档的AST算法类似,树型结构的一致性维护方法也通过矢量时钟(vetor clock)来保证操作的因果关系.接下来重点讨论文档下的远程操作满足执行条件时,如何拓展AST算法使其排除并发操作的影响,能够在正确的位置上执行以保证结果一致性和意图一致性.

2.1 树型数据的存储结构与寻址方式

线性数据抽象模型可以建模平面文本,但它不能对格式化的文本、向量图形和SGML文档进行建模[15].而Web富文本本质上是一段HTML内容,W3C提出的文档对象模型(Document Object Model,DOM)是HTML和XML文档的编程接口,DOM将HTML文档呈现为带有元素、属性和文本的节点树,它允许程序动态访问和更新文档的内容、结构和样式.因此本文提出的树型数据结构参考了HTML中对于DOM的设计,将富文本文档中的所有内容设为节点(Node)和选区两部分,节点(Node)是一个属性集合,包含以下属性:

1)标识符(ID),代表了作用在该节点上的最新的操作的 唯一标识符;

2)类型(type),表明节点类型;

3)内容(text),保存节点内容数据;

4)子节点列表(children),保存子节点序列;

5)属性列表(attributes),保存若干个节点样式;

6)计数器(counter),判断节点有效性;

7)路径(path),由段落节点和相对路径组成.

选区包含起始位置和偏移量等属性,此部分内容不属于本文重点,详情见HTML DOM标准.考虑下面一段富文本样例,如图1所示,它由多位用户协作编辑完成,图2为该样例的节点树模型图.

图1 富文本文档内容示意图Fig.1 Rich text document content diagram

图2 富文本文档节点树模型图Fig.2 Node tree model diagram of rich text

Web富本文文档由多个呈树型结构排列的字符节点组成,传统线性AST算法不能解决节点定位问题,为此本文参考了路径寻址方案[15],在此基础上拓展了AST算法使其适应树型结构数据.超文本文档中节点数目是非常庞大的,因此本文采用了一种段落节点命名的位置寻址方案.其余节点都是匿名的,它们的位置信息由所在段落节点名称再加上自身与段落节点的相对路径组成.对于任意一个节点N,用符号表示节点N所在段落的名称,N[i]表示该路径向量的第i个元素.如图2所示,第一段中加粗字体所在节点的路径表示为(A,[1,1]).

2.2 操作类型

本文设计的协同富文本编辑系统中,有3种基本操作包括插入操作(insert)、删除操作(delete)和更改操作(change)与一个撤销操作(Undo).

1)插入操作:insert(Node,n,new)表示将节点New插入到节点Node子树中的第n个位置上.

2)删除操作:delete(Node,n,saveNode)表示删除Node的第n个子节点及其后代节点,并将被删除节点树信息赋给saveNode.

3)更改操作:change(Node,attr,val)表示将节点Node的atter属性值更改为val.

4)撤销操作:Undo(Oa)表示撤销操作Oa.

需要特别指出的是非更改操作对应的撤销操作只会影响目标节点的有效性/无效性(effective/ineffective),而更改操作和对应的撤销操作不会改变节点的位置和有效性,因此可以将撤销操作视为普通操作存在.确定了文档中有效字符节点的数量后,就可以得到目标节点的唯一路径,AST算法就是将文档的地址空间回溯至远程操作生成时的状态,使文档中有效节点的路径信息与远程操作的路径信息一致,这样就可以排除并发操作的影响方便远程操作找到正确的执行位置.

3 树型结构数据的一致性维护

3.1 支持树型结构AST算法

在协同编辑系统中数据通常采取全复制式存储来确保本地修改的可伸缩性和高响应性,这种复制是乐观的,它允许副本数据在短时间内发生分歧,但当系统处于空闲状态时,所有副本数据必须相同.其中因果一致性维护可以通过时间戳模型实现,本地站点生成的操作立即执行,远程操作到达后时要满足操作的执行条件:即该操作的所有因果先序操作都已在此站点上执行.但是网络延迟会导致不同站点间远程操作的到达顺序不同,执行顺序也就不同,这会带来不一致性问题.本文采用地址空间转换来消除这种影响,同时来保证结果一致性和意图一致性.

地址空间转换方案的控制算法(Control Algorithm)包含两次回溯过程,第1次回溯过程会根据远程操作的时间戳将文档的地址空间回溯到该操作生成时的状态,排除无效节点的影响以便确定远程操作正确的执行路径.然后调用Deliver函数执行该操作,在执行插入操作时目标位置可能会出现多个无效字符节点,为了保持收敛性本文采取了TOrder关系[25]来确定操作间的顺序.最后根据根据新时间戳进行第2次回溯,恢复文档的地址空间状态,详情见算法1.设操作O由远程站点X生成且时间戳为TSO,文档地址空间为TSDoc.

算法1.地址空间转换控制算法

输入：目标文档Doc、用户操作O

输出：执行完操作O后的文档

1.if O is a Remote-operation then

2. Wait Until 操作O满足远程操作的执行条件

3. Retracting(Doc,TSO)

4. Deliver(O)

5. TSDoc[X]+=1

6. Retracting(Doc,TSO)

7.end if

回溯过程(Retracting)是整个算法的核心,它将文档回溯到指定时间戳状态,保证操作可以在正确的位置执行.与线行文档不同的是,由于富文本文档数量庞大且结构复杂,回溯整个文档的地址空间是非常耗时的,因此采取回溯部分节点策略,首先根据时间戳和操作历史记录(History)获取非因果先序操作集,接着通过比较操作集中段落节点来跳过一些操作得到受影响的操作集(list_EO),详情见算法2.最后通过find函数找到list_EO影响的节点最后回溯它,回溯的结果就是将该操作的影响消除,其中插入和删除操作的回溯只是修改节点的可见性和路径信息并不会真正修改节点树的结构,更改操作的回溯效果就是将目标属性值取逆,具体的回溯算法将在下节的算法3中详述.

算法2.RelateOperations(History,TS)

输入：操作历史记录History,目标时间戳TS

输出：需要被回溯的操作集list_EO

1.for item in History do

2. if(item.ts>=TSo)&&(==)then

3. list_EO.append(item)

4. end if

5.end for

3.2 支持Undo操作的树型结构AST算法

从用户的视图来说,撤销功能需要正确地消除目标操作造成的影响.假设一个场景:用户A插入一个字符,然后用户B删除它,接着两位用户并发撤销各自的操作,考虑到操作的效果当上述任务全部执行后,插入操作和删除操作的影响均被消除,即从用户视图来说该字符是不可见的,并且在任意站点中不管远程操作的执行顺序如何,所有复制副本应该是一致的.如果撤销功能是通过直接执行逆操作来实现的,则远程操作的执行顺序可能会影响系统最终的一致性,假如插入操作的撤销操作最后到达站点则目标字符不可见,反之删除操作的撤销操作最后到达站点则字符可见,此外这种直接执行逆操作的撤销方案可能会丢失操作的位置信息不利于系统的一致性维护,因此在存储时需要额外的弥补措施.

为了获取令人满意的撤销效果,本文为每个字符节点引入了一个计数器counter来统计操作的效果,其中delete和Undo(insert)操作的效果是使字符点无效,即counter自减,Undo(delete)操作的效果是使字符点有效,即counter自加,更改操作及其撤销操作不会影响计数器.若counter小于等于0则意味着该字符节点在用户界面不可见,由此可见撤销操作同插入操作和删除操作类似,它只会影响字符的可见性而不会改变字符的相对位置,因此上文中的控制函数不需要额外的修改,但是支持Undo操作的回溯函数就要考虑计数器带来的影响,详情见算法3.

算法3.支持Undo操作的回溯算法

输入：目标文档Doc、用户操作O,目标时间戳TS

输出：时间戳TS下的文档地址空间状态

1.list_EO=RelateOperations(History,TS)

2.for o in list_EO do

3. fnode=find(o.Node.path)

4. If o.type== delete‖o.type== Undo(insert)then

5. node=fnode.children[o.n],node.counter++

6. end if

7. if o.type== insert‖o.type== Undo(delete)then

8. node=fnode.children[o.n],node.counter--

9. end if

10. update the children of the affected fnode

11. if O.type== change then

12. fnode.attributes[O.attr]-=O.val

13. end if

14. If O.type== Undo(change)then

15. fnode.attributes[O.attr]+=O.val

16. end if

17.end for

在地址空间转换控制算法中,第1次回溯过程结束后,远程操作便可以执行,算法4给出了3种基本操作与Undo操作的执行过程.

算法4.基本操作执行算法

输入：用户操作O

输出：修改后的节点信息

1.if O.type== insert then

2. fnode=find(o.Node.path)

3. fnode.Children.insert(O.n,O.new)

4.end if

5.if O.type== delete‖O.type== Undo(insert)then

6. fnode=find(O.Node.path)

7. node=fnode.children[O.n],node.counter--

8. O.saveNode=fnode.Children.delete(O.n)

9.end if

10.if O.type== change then

11. node=find(O.Node.path)

12. node.attributes[O.attr]+=O.val

13.end if

14.if O.type== Undo(delete)then

15. fnode=find(O.Node.path)

16. fnode.children.insert[O.n,O.saveNode]

17. node=fnode.children[O.n],node.counter++

18.end if

19.if O.type== Undo(change)then

20. node=find(O.Node.path)

21. node.attributes[O.attr]-=O.val

22.end if

23.update the children of the affected nodes

3.3 复杂度分析

通过上文的描述可以发现算法的时间复杂度主要集中在两个方面,即回溯函数与操作的执行函数.首先分析执行函数的复杂度.执行操作的第1步是找到正确地执行位置,根据路径信息表可以迅速找到执行位置时间复杂度为O(1),其中插入操作需要额外的range-scan函数来确定无效节点的位置关系,range-scan函数的时间复杂度为O(m),m是无效节点的数量[16].对于删除操作、更改操作和对应的撤销操作,它们只修改字符节点的属性值复杂度为O(1).除更改操作外其余操作都需要更新路径信息表,为了减少受影响节点的路径修改次数本文根据段落标识来定义路径,时间复杂度为O(c),其中c是执行位置所处段落的字符数量.

其次分析回溯过程的复杂度.第1步是遍历操作历史记录H来获取与相关操作集,时间复杂度为O(h)其中h是相关操作数量,在实际工作中同一时间的并发操作数是很小的[5].然后是根据相关操作集来找到需要回溯的节点并修改对应属性和更新路径信息,时间复杂度为O(h×c),第2次回溯同理.

综上所述,执行n次插入操作的时间复杂度为O(n×(m+c+h+2h×c)),删除操作及其撤销操作的时间复杂度为O(n×(c+h+2h×c)),更新操作及其撤销操作的时间复杂度为O(n×(h+2h×c)).空间复杂度:假设副本共有C个节点且每个节点的平均路径长度为L,那么对应的空间复杂度至少是O(C+C×L).

4 案例分析

接下通过用一个协同编辑场景来描述本文算法的执行过程.假设这次协作会话有两个站点a和站点b参与且存在a.ID

第1次协作过程如图3所示,站点a和站点b分别生成了本地操作Oa1、Oa2和Ob1,满足Oa1→Oa2,Oa1‖Ob1,Oa2‖Ob1,其中Oa1=insert[(B,[0]),1,X],Oa2=insert[(A,[1,1]),1,Y],Ob1=insert[(A,[1]),1,Z].

图3 第1次协作过程Fig.3 First collaborative process

在站点a,本地操作Oa1生成后立即执行,在此基础上操作Oa2生成后立即执行.当远程操作Ob1到达站点a时,控制算法首先会根据时间戳模型来判断Ob1是否满足执行条件,若不满足则Ob1在等待池中等待.在此情景中Ob1到达站点后不需要等待直接进行第1次回溯(retracing)过程,根据站点a的操作历史记录得到非因果先序操作集[Oa1,Oa2],通过比较操作节点的段落路径得知Oa1与Ob1分属两个段落子树互不影响,所以只需要回溯Oa2影响的节点Y将其设为无效,然后执行操作Ob1将节点Z插入到节点(A,[1])孩子节点的第1位上,更新完受影响节点的路径信息后执行第2次回溯.

在站点b,本地操作Ob1生成后立即执行,即在指定位置上插入节点Z,然后远程操作Oa2到达站点b,控制算法根据时间戳模型判断Oa2不满足执行条件,于是Oa2在等待池中等待.接着远程操作Oa1到达站点b,根据时间戳模型判断Oa1满足执行条件于是执行第1次retracing过程,因为Ob1和Oa1插入节点的段落信息不同,所以可以直接执行Oa1然后进行第2次retracing过程.当Oa1执行后,在等待池中的Oa2满足了执行条件进入第1次retracing过程,通过本地操作历史可得非因果先序集[Ob1],所以需要回溯操作Ob1影响的节点Z将其设为无效并更新路径信息,然后文档的地址空间就恢复至操作Oa1生成时的状态,接着根据Oa1的参数信息找到正确的执行路径并插入节点Y,最后进行第2次retracing过程将节点Z恢复.

如图4所示,站点b通过地址空间转换算法避免了将节点Y插入到节点Z的错误情况,这使得站点a与站点b储存的文档副本相同.最终站点a和站点b的文档结构收敛,该算法很好地维护了协同系统的一致性.

图4 站点b的地址空间转换过程Fig.4 Address space translation at site b

第2次协作过程:

如图5所示,站点a和站点b分别生成了本地操作Oa3、Oa4、Ob2和Ob3,满足Oa3‖Ob2,Oa4‖Ob3,其中Oa3=delete[(B,[0]),1,X],Oa4=Undo(Oa3),Ob2=delete[(B,[0]),1,X],Ob3=Undo(Ob2).

图5 第2次协作过程Fig.5 Second collaborative process

对于站点a来说,当所有操作执行后文档中的节点X有效,为了使系统收敛站点b的文档最终结果也应该保留节点X.不加处理的Undo操作可能会导致最终结果不一致,为此算法为每个字符节点引入了一个有效计数器counter,其初始值为1,删除操作和Undo(insert)操作会将counter减一,Undo(delete)操作会将counter加一.当counter小于1时表示该字符节点无效,即在用户界面不可见.若多个删除操作作用于同一个节点,只有当这些删除操作全部撤销时该节点可见.对于站点b来说,当所有操作执行后文档中的字符节点X有效,表明该算法能很好地维护用户的意图.

5 算法正确性证明

本文采用的时间戳模型可以保证系统的因果一致性,即远程操作需要满足执行条件才会真正执行.假设当某个时刻所有站点的节点数结构是一致的并且有n个待执行的操作时,接下来将证明执行完这些操作后所有站点的副本数据是相同的,即保证系统的结果一致性.

5.1 两个操作

定理1.来自不同站点的两个并发操作,按照任意顺序执行,其目标节点的位置是不变的.

证明：不失一般性,假设O1‖O2,同时TOrder(O1)

1)若path1对应位置向量比path2大,则表明O2为插入一个节点或将撤销一个被删除的节点,因为O1‖O2,该节点的状态会在第一次回溯过程中设为无效,即path1[x]=path2[x],x∈[0,n].

2)若path1对应位置向量比path2小,则表明O2为删除一个节点或将撤销一个插入节点,通过回溯算法该节点在O1的时间戳下会被设为有效,即path1[x]=path2[x],x∈[0,n].

3)若path1对应位置向量与path2完全相同,则表明O1影响的节点在目标节点广义上的右侧或O1为非影响节点有效性的操作,那么即使执行回溯算法也不会改变目标节点路径.

基于以上3点,虽然O1对文档的节点树进行了修改,可能导致O2目标节点的实际路径信息与O2自身携带的路径信息不同,但是经过O2的回溯过程后目标节点的路径与自身携带的路径信息相同.同理O2先执行的情况下,经过O1的回溯过程后目标节点的路径与自身携带的路径信息相同.命题得证.

定理2.来自不同站点的两个并发操作,按照任意顺序执行,所有站点的文档结构是一致的.

证明：不失一般性,假设O1‖O2,同时TOrder(O1)

1)若在站点a处执行顺序为O1、O2,O1的执行效果先赋给目标节点后,由于O2的优先级高,O2的执行效果会覆盖O1.

2)若在站点a处执行顺序为O2、O1,O2的执行效果先赋给目标节点后,由于O1的优先级低,O1的执行效果会被舍去.

即文档的最终结构一致的,与这两个并发操作的执行顺序无关,命题得证.

5.2 N个操作

定理3.当n个操作都被执行后,所有站点的副本结构是一致的.

证明：假设按照上述情况执行了n-1个操作之后,所有站点的文档结构一致,而根据定理1和定理2得知当任意两个操作在满足执行条件的情况下不管按照什么顺序执行都不影响所有站点文档的结果一致性,通过调换前n-1个操作的执行顺序,易证执行n个操作后所有站点的副本结构是一致的[24].命题得证.

综上所述,本节证明了在满足执行条件的情况下以任意顺序执行n个操作不会影响树型结构数据中节点的路径信息和结果一致性,此外通过节点计数器使得尽可能多的用户操作意图得到了保留.

6 原型系统

为了验证拓展AST算法及相关函数的可行性与正确性,本文在Mac OS平台下使用Typescript语言编码开发了实时富文本文档编辑系统AST-RichText.前端模块采用React框架,后端服务器模块采用Nodejs+pm2+mysql框架构建一个Web系统.该系统使用Websocket协议来实现持久连接的全双工双向通信,客户端通过 Websocket 连接到单个端点,服务器在客户端之间分发操作信息和文档更新.

多人协同富文本文档编辑系统如图6所示,上方展示文档路径和用户信息,接着是文字样式栏,包含加粗、斜体、代码块和编号样式等功能,最后在富文本文档编辑区,配合协同插件可以实时显示其他用户的光标提示信息,此外还可以考虑集成聊天室模块,进一步增加用户的感知度并且降低操作冲突的概率,提高系统的实用性.

图6 AST-RichText原型系统Fig.6 AST-RichText prototype system

7 总结与展望

本文提出了一种拓展的地址空间转换算法,包括一个全局选择撤销机制,它可以用于构建树型结构文档的实时协同编辑系统.该算法通过基于位置的路径寻址和部分节点回溯策略拓展了传统AST算法使其能应用于富文本文档之类的树型结构数据,并且能保证每个站点在执行远程操作后的结果一致性,并给出了理论证明.与传统的OT算法相比,本文算法不需要设计复杂的转换函数同时还很好地解决了经典的Undo难题,维护了实时协同编辑系统的一致性.

未来的研究者可以从以下几个方面继续探索.首先,考虑用户的客制化需求,为协作系统增加更多的组合操作来提高实用性.其次,随着更多操作和文档格式的引入,并发操作造成的意愿冲突问题将更加复杂,如何更好地维护操作意图一致性是接下来的重点.最后,用户隐私与数据安全也是现代实时协作系统的重要组成部分,尝试将实时协作系统与去中心化技术相结合,例如将区块链中以太坊技术应用到的用户身份认证和去中心化的数据管理系统IPFS,从而进一步增加数据的安全性与隐私性.