支持操作续传的网络三阶段一致性维护研究

王 丹,高丽萍,朱思征

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

1 引 言

计算机产业是当今社会发展速度最为迅猛的产业之一,并日益影响着我们的日常生活与工作.随着全球化、信息化的普及,为了提高工作效率,诸多领域采用分布式作业,使员工们可以跨平台、跨区域合作.而合作的方式,也随着工作量的增大,从个人负责整体中的部分独立模块,通过合并实现合作,逐步发展为多人、多地域甚至实时的负责不同或相同模块任务的合作方式.因此,群件系统、协同计算等一系列支持协作需求的产物应运而生.而在20世纪80年代依瑞·格里夫和保尔·喀什曼提出了计算机支持的协同工作(Computer Supported Cooperative Work,CSCW)概念[1-3].

在协同工作领域,实时群组编辑器是最为常用的协同工具之一.主要通过联通网络和适当的冲突处理,使多用户能够实时编辑同一文件对象,并最终得到状态一致的文件.为了提高客户端响应速度和协作效率,全复制式架构[3-5]和部分复制式架构[6]相继被提出,并将操作划分为本地和远程两类,与此同时涌现出诸多基于此架构的冲突消解算法和应用.

我们常用的较为成熟的冲突消解方法有OT(Operation Transformation)[7]和AST(Address Space Transformation)[4].但这两种方法对网络的联通性要求较高,必须保证在良好的网络状态下,远程操作能够完整的被接收和执行.随着移动互联时代的到来,各种移动设备层出不穷,人们也将各类工作“搬运”到移动应用上来,而移动网络的不稳定性、易受干扰性,恰恰违背了一致性维护算法的必要前提.如何将一致性维护算法进行整合,从而适应移动终端,最终提升协作的便利性和平台多元化,是本研究任务的核心.

在文献[8]中,我们初步提出一种支持断网状态的移动网络协同副本一致性维护算法,并将网络状态划分为断网前、断网后、联网后三阶段,提出使用游标与网络状态属性标记文档状态和网络状态,在不同网络状态环境下切换对应处理进程,最终为ABST算法的准确执行构造协同站点间副本状态一致这一必要条件.但该算法还只是单纯针对两个移动端之间的操作进行处理,若客户端和操作数量增大,势必会产生效率低、准确性差、对移动设备软硬件要求过高等一系列的问题.因此,本文主要研究在不稳定的网络状态下,如何高效准确的实现多用户协同工作.并使用中央处理器作为操作转播媒介,同样将网络状态划分为三类,在之前算法的基础之上进行改进并移植到服务器端.

本文的结构如下:首先回顾[8]中的不稳定网络环境下的一致性维护算法,并分析其潜在的执行效率、准确性问题,针对本文涉及的算法对客户端、服务器进行设置;随后详细介绍本文提出的ORT算法,在不同网络状态下设计服务器端处理过程;然后对ORT算法的时空效率进行分析;并基于开源文本编辑工具包UEditor,开发基于web的实时协同编辑系统Co-Editor,对ORT算法的准确性进行验证;最后针对本文提出后续的主要研究内容.

2 相关工作

实时协同领域的研究日渐成熟,并产生了大量的创新理论与实践开发工具.其中并发控制技术是实时协同研究领域的难点之一,该技术主要包括两点:一致性维护与冲突消解.为了解决一致性维护问题,1989年Eliis[1]等人首次提出操作转换OT[7]概念,并研发dOPT(distributed Operational Transformation)算法构建Grove协同编辑系统,初步建立一套一致性模型.1998年Sun[3]验证了dOPT算法在某些场景下存在协同站点产生结果不一致的问题,便在初期一致性模型基础上加入意图维护标准,完善为CCI(Convergence,Causality,Intention) 模型,为今后的一致性维护技术准确性验证提供了依据.由此,一系列基于OT思想的一致性维护算法被提出,诸如对GOT算法进行优化的GOTO[3]算法,支持String类型的ABTS[9]算法,适用于移动设备的ABST[10]和ABT[11]等算法.在基于OT思想的一致性维护算法研究较为成熟阶段,科研人员发现了操作转换潜在的执行效率低,转换规则复杂等问题.因此,NingGu等人[4]在2005年的一篇文章中提出地址空间转换算法(Address Space Transformation,AST).一致性维护技术相对成熟后,人们把研究重点转向了意愿维护,及冲突消解技术,提出基于协同感知的冲突预防策略和冲突发生之后的检测及消解策略.结合两种并发控制技术,研发出大量适用于PC端的协同编辑系统,如支持产品设计的Co-CAD[12]、支持协同文档编辑的Codoxware、CoMaya、CoTable等.

如今,人们更倾向于较为便利的移动办公,而我们所了解的并发控制技术,尤其是一致性维护技术,均是在乐观网络状态(即网络状态良好,所有操作都会被完整接收和执行)下进行研发的,而移动网络状态不稳定恰恰使得大部分现有的一致性维护算法不适用于移动设备.2010年Shao等人[10]提出一种支持异步协同的ABST算法,通过合并与分解整合操作序列.但该算法只是对网络状态进行模糊划分,重点解决断网后各协作站点产生的操作集,在我们之前的研究中[8]发现了ABST算法准确执行的必要前提:各协同站点副本的文档状态一致.客观上来说,这也是其他支持异步协同算法的必要前提.因此我们在上一篇文章中提出了一种能够为ABST算法准确执行构造必要前提的一致性维护算法[8].但该算法仅仅支持两个站点间简单的协同工作,通过验证,一旦用户数量上涨,客户端在断网前的cursor更新和断网后的本地副本恢复处理进程将产生明显的延迟.为了解决此问题,我们在本次研究中引入中央服务器,以提高客户端响应速度、减轻客户端工作量.

3 准备工作

3.1 算法回顾

各站点文档初始状态为””,cursor值为0;

各站点产生的操作:

·Site1:O1=Ins(‘a’,1);O4=Del(‘b’,2);

·Site2:O2=Ins(‘b’,1);O5=Ins(‘d’,3);

·Site3:O3=Ins(‘d’,1);O6=Del(‘e’,3).

图1 三站点操作示例图Fig.1 Operationsat three collaborative sites

图1中T1和T2分别代表两个本地站点向远程站点发送本地HB的时间点.在之前的文章中我们以两个站点为例,来认证移动网络环境下一致性维护算法的准确性,本文我们以三个站点为例对该算法进行再次验证.

1.首先分析在T1时刻各站点的文档状态和时间戳等基本参数:

Site 1:O1在本地生成并立即执行,文档状态更新为“a”,此时状态向量为(1,0,0);随后O2到达,利用AST算法,将文档中所有字符标记为无效,调用Range_Scan函数确认字符的插入位置,得到文档“ab”,状态向量更新为(1,1,0);此时HB1={O1,O2},cursor值不变;

Site 2:O2在本地生成并执行后,文档状态转换为“b”,O1到达通过地址空间转换算法,改变文档状态为“ab”,当前的状态向量更新为(1,1,0),HB2={O2,O1},cursor值无变化;

Site 3:站点三操作的执行顺序与site2相同,它的HB3={O2,O1},cursor值不变.

T1时刻,各个协同站点发送本地HB至远程站点,但与之前文章中的例子不同的是,之前的文章中涉及的协同站点数为两个,HB的广播和接受进程处理相对比较简单,而本文中采用了三个协同站点,那么每个站点将要分别给另外两个站点分别发送HB,同时也要接收来自两个站点的HB,因此HB的对比以及cursor值的更新将变得更为复杂.

假设我们通过循环使用之前的check()函数,来实现各个协同站点cursor值的更新,以site1为例具体的流程如下:

Site1在T1时刻接收到分别来自site2和site3的HB,此时HB1需要选择与HB2和HB3中的一方进行check(),根据交集最短规则,选择两者中较短的一个,我们选择HB2,首次对比HBset为{ O1,O2},cursor值为2;将HBset与HB3进行第二次check(),HBset{ O1,O2},cursor仍为2.我们所举的例子对应的操作数量较少,情形相对简单,但可以直观的看出,在有三个站点的情况下每个站点在特定时刻更新cursor时至少要进行2次check(),而整个协同工作在该时刻要进行2*3即6次check(),这种方式虽然能解决一致性问题,但效率相对较差,因此,站点增多导致对比次数过多造成的效率降低是本文发现的第一个问题.

2.站点的增多,导致协同工作效率降低的同时,如何保证所有协同站点间cursor值的一致同样是重点需要解决的问题.因为断网不但会导致操作的丢失与漏发,同样会使HB的传播任务中止,从而影响cursor更新操作执行数据完整性,最终导致各站点在联网后恢复本地副本时不一致.

为了解决以上问题,我们在实际应用设计中考虑使用服务器,来集中接收、处理和转发所有站点产生的操作.并在之前的移动网络环境下一致性维护算法基础上进行改进,实现多站点间高效准确的协同编辑工作.

3.2 基本操作

对于操作,我们只考虑插入ins(p,c)和删除del(p,c)两个最原始的操作方式,分别代表在位置p处插入或删除对象(字符)c.

3.3 服务器端设置

表1 服务器端基本设置
Table 1 Basic parameters on the server

符 号 定 义简 要 说 明netListener协同站点网络状态监听opInBuffer存储各站点广播的操作opOutBuffer存储转换后可发送至协同站点执行的操作HBset各站点执行过的操作集cursor记录各站点副本一致最近点opBreakInBuffer存储断网站点断网后其他协作站点生成的操作opBreakOutBuffer存储断网站点断网后生成的本地操作Timer更新cursor的固定时间间隔DOC各协同站点副本备份

如表1所示,服务器端大致包括客户端网络状态监听、若干缓冲区、协同站点HB集合HBset和计时器Timer等.

为了优化查询效率,我们将服务器的HBset设置成有序树结构,即HBset为根节点,各站点标识作为HBset的孩子节点,协同站点标识按优先级由高到低作为第三层子节点,同一站点生成的操作按照时间戳由小到大排列作为对应站点节点的孩子节点(如图2所示),需要强调的是,opOutBuffer只自动清除cursor前的操作.

图2 HBset树形结构图Fig.2 Tree model of HBset

4 ORT算法

在本设计中,我们将主进程功能全部部署在服务器端,各协同站点均只负责生成和执行本地操作、广播本地操作至服务器端、执行从服务器接收到的操作,以及在指定时刻发送本地HB至服务器,因此下面我们分别介绍服务器端在三种网络状态:断网前(break-before)、断网后(break-after)和联网后(connect-after),分别执行的主要处理函数.对于客户端,我们在断网前处理远程操作,断网后除断网客户端外的其他协作客户端间的互发操作,联网后对于丢失操作的处理我们均采用AST算法.

4.1 客户端断网前-服务器主进程

断网前,服务器端主要处理进程包括:接收和广播操作、定时更新cursor值,并广播最新cursor至所有协同站点.

过程1．Receive＿Broadcast(Ou，cursor)1． If(FirstuseServer)2． { initialize()；//初始化服务端基本设置3． lastTime=CurrentTime()；}4． HBset．sitex．HB．Append(Ou)；5． opInBuffer[Sitex]．Append(Ou)；6． for(i=1touser．count)7． { if(i！=x)8． {opOutBuffer[Sitei]．Append(Sitei．Ou)；}9． }10． Broadcast(opOutBuffer[Sitei]．Ou)TOSitei；11． If(Timer==CurrentTime⁃LastTime)12． {//各协作站点发送本地HB到服务器HBset中13． ReceiveHBsfromallSites；14． HBset．Append(HBs)；15． Cursor＿Update(HBset，cursor)；16． LastTime=CurrentTime；17． Broadcast(cursor)TOallSites；18． }函数1：Cursor＿Update(HBset，cursor)1． if(HBsitei．lengthistheminlengthinHBset)2． {HBr=HBsitei；//将最短HB拷贝到HBr3． Length=HBsitei．length；}4． for(mis0toLength⁃1)5． { userId=HBr[m]．id；6． vector=HBr[m]．v；7． for(nis1touser．count)8． { //与其他协作站点逐一匹配9． if(userid！=sitei．id)10． {//在HBset树中查找是否存在操作HBr[m]11． if(HBset．HBsiten．userId．op．vectorexsitsinsiten)12． {posList．Append(indexOf(HBset．HBsiten．userId．op))；13． n++；}14． else15． { break；}16． }17． if(n=user．count⁃1)18． {m++；}19． else20． {//如果在posList中不存在大于m的操作21． for(jis0toposList．length⁃1)22． { if(posList[j]>m-1)23． {Length=m+1；//更新Length值24． returnstep5；}25． else26． { break； }27． }28． }}}29． cursor=cursor+m；

4.2 客户端断网后-服务器主进程

在协同工作过程中,如果一旦有用户断开网络连接,会造成与服务器失联,从而无法接收和发送操作,这时服务器就要进行相应的处理,为该断网站点重新联网后生成一致性副本做准备.而断网站点继续生成和执行本地操作,并对断网后生成的操作进行标记,也就是在文章[8]中的package(SQ0,SQ1)过程,生成两个操作集合SQ0(存储断网前cursor后的操作)和SQ1(存储断网后的操作).而服务器端也要对站点的失联状况进行应对.

过程2．Break＿Response()1． netListener[i]=1；2． for(nis1touser．count)3． { //对于网络状态良好的站点，继续通过服务器与其他站点进行协同工作，但不更新cursor4． if(netListener[n]==0)5． { Receive＿Broadcast(Ou)； }6． else7． { while(receiveoperationOrfromothersites)//Or表示一类远程操作8． {Or．net=1；9． opInBuffer[n]．Append(Or)；10． }11． }12． }

通过Break_Response过程对操作的整合,我们可以从opInBuffer和opOutBuffer中得到两种操作:一种是在站点i断网后,其他协同站点生成的操作,存储在opInBuffer中,且操作的net值为1;另一种是在站点i断网前,cursor后广播已执行或广播丢失或未广播的操作,分散存储在opInBuffer和opOutBuffer中,且操作的net值为0.为什么不把opInBuffer中net值为0的操作通过地址空间转换直接整合到opOutBuffer？因为在联网后的执行过程中,首先需要对opOutBuffer进行遍历,找出未广播或广播过程中由于断网丢失的操作,而opInBuffer中的操作一定是还未广播的操作,所以为了提高遍历效率,减少副本恢复时间,我们在遍历进程结束后立即对opInBuffer中net=0的操作进行转换和广播至断网站点.

4.3 客户端联网后-服务器主进程

联网后服务器对各协作站点副本的主要恢复操作大致包括

1)检测断网前站点接收过程中是否存在丢失操作,若存在,对该操作进行相应转换处理,然后在断网站点执行;

2)检测断网前站点广播操作至服务器过程中是否存在丢失操作,若存在,捕捉该操作,并将该丢失操作进行转换并广播到其他协作站点;

3)处理断网后,各协作站点产生的操作,最终各站点生成一致性副本.

过程3．Server＿Recover(SQ0，SQ1)1． /∗(1)∗/2． for(iis0toSQ0．length⁃1)3． { //将SQ0中的本地操作和远程操作区分开4． if(SQ0[i]．id==n)5． { Larry．Append(SQ0[i])； }6． else7． { Rarry．Append(SQ0[i])； }8． }9． if(Rarry．length==opOutBuffer[n]．length)10． { Cursor＿Update(HBset，cursor)；11． Broadcast(cursor)TOallsites；12． }13． else14． {for(j=0toopOutBuffer[n]．length⁃1)15． {if(opOutBuffer[n][j]notinRrray)16． { Broadcast(opOutBuffer[n][j])TOsiten； }17． }18． }19． for(k=0toopInBuffer[n]．length⁃1)20． {//筛选断网前的操作先执行21． if(opInBuffer[n][k]．net==0)22． {opOutBuffer[Siten]．Append(O)；23． Broadcast(O)TOSiten； }24． else25． { opBreakInBuffer[Siten]．Append(opInBuffer[n][k])}26． }

27． /∗(2)∗/28． for(sis0toLarry．length⁃1)29． {if(！Larry[s]exsitsinHBset．siten)30． {//如果不存在，证明该操作在断网时丢失，重发31． Broadcast(Larry[s])toothersites； }32． }33． /∗(3)∗/34． SQ1′=Compressed(SQ1)；35． OpBreakOutBuffer[siten]．Append(SQ1′)；36． Broadcast(Sequence(OpBreakOutBuffer[siten]))toothersites；37． Broadcast(Sequence(OpBreakInBuffer[siten]))tositen；38． ReceiveHBsfromallSites；39． HBset．Append(HBs)；//更新HBset40． Cursor＿Update(HBset，cursor)；41． Broadcast(cursor)TOallSites；

5 算法效率分析

本文将不稳定的网络状态划分为断网前、断网后和联网后三部分,同样在不同的网络状态下,服务器端会自动切换不同的处理过程,而协同客户端的效率,取决于所使用的一致性维护算法.下面我们针对每种网络状态分析服务器端处理过程的时空效率.

断网前,服务器的主要处理函数Receive_Broadcast()负责接收和广播操作到各协作站点,并在特定的时间间隔通过Cursor_Update()方法更新cursor值.因此,在非更新cursor时段,服务器端的收发操作的时间复杂度为O(user.count),user.count为协同用户总数;而在更新cursor时段,服务器端的时间复杂度为O(Length·user.count·h),其中Length是所有协同站点中最短HB的长度,由于我们在服务器端使用树形结构存储HBset,因此根据id和v检索HBset中的指定操作时,时间复杂度为HBset树的高度h,且h是一个固定的数值4,所以总体时间复杂度可以简化为O(Length·user.count).

断网后,非断网站点仍通过服务器端Receive_Broadcast()互相协同工作、收发操作.断网站点则更改netListener中对应位置的值为1,然后根据操作net值将操作存放于不同的缓冲区,以上部分的时间复杂度取决于用户总数,为O(user.count).

联网后,Server_Recover()函数对各协作站点的副本进行一致性处理,大致分为三步:

1)处理断网前服务器向站点广播过程丢失的操作,时间复杂度为O(SQ0.length),SQ0为断网站点HB中cursor位置后net=0的操作集.

2)处理断网前站点向服务器广播过程丢失的操作,复杂度为O(Larry.length),Larry为SQ0中操作id为断网站点id的操作集;

3)处理断网后,各协作站点产生的操作,主要操作为压缩操作和cursor更新操作,时间复杂度参考断网前和断网后.

6 Co-Editor编辑系统

不仅是移动网络具备不稳定的特点,使用有线宽带、无线wifi的终端设备,同样存在网络断开的情况,因此,为了验证ORT算法的准确性和可行性,我们基于web对开源的UEditor系统进行二次开发,研发Co-Editor协同编辑系统,支持多用户在不稳定的网络状态下借助浏览器共同编辑一个纯文本文档.

6.1 系统主界面介绍

如下页图4所示,是四个协同用户使用Co-Editor系统编辑同一个文档的示例.我们的编辑系统利用eclipse、tomcat、CSS和javascript等开发工具,结合easyUI框架,将界面大致划分为四个功能区域.左侧为用户显示栏目,并显示各用户当前的网络状态 (Online/Offline); 中部为文本编辑器主体,协同用户可直接在其之上编写文档(注:本编辑系统只支持纯文本文档编辑,其他功能将在后期扩展);右侧为功能栏,用户可点击对应按钮,实现从服务器同步主副本到本地,导出页面文档至本地,显示/隐藏功能栏和编辑器能功能;下侧为用户基本信息显示栏,显示用户ID、用户名、最后一次从服务器更新主副本的时间.

图3 断网时站点3及站点4文档状态Fig.3 State of document at site 3and site 4 when net-broke

6.2 一致性维护验证

图3中左下方为站点4,Mary用户的编辑界面,此时的文本内容为“Hello world”,该站点处于断网状态,且在断网后Mary并未对文档进行任何更改;右上方站点3的网络状态良好,文档为“Hello wor”,同样在站点4断网后,站点3也未执行任何操作;说明由于站点4的网络失联,站点4未将“ld“部分对应的操作发送给协作站点,或发送过程中由于断网造成丢失现象,站点3由于不能完整的接收远程操作,使得本地文档状态与站点4的不一致,当网络再次联通时,只能够处理在断网后各站点产生的操作,最终将导致各站点文本状态不一致的后果,破坏了协同工作的目的.

联网后,通过ORT控制算法,对各协同站点的本地副本状态进行一致性恢复,如图4所示,在Mary重新上线后,断网中丢失的操作得以重发,并在站点3上执行,最终所有站点生成一致性副本“Hello world”.

图4 联网后站点3文档状态Fig.4 Thestate of document at site 3 when net-connected

7 总结及展望

本文针对不稳定网络环境,提出ORT(支持操作续传的网络三阶段一致性维护) 算法.在之前支持两站点协同工作的研究基础上,引入服务器集中处理概念,在减轻客户端负载和处理复杂度的同时,提升协同工作的整体效率和功能特性.未来的研究工作包括:

1)我们对UEditor的二次开发只是基于纯文本,而该软件具备图形图像等多种对象的编辑功能,因此,研发各类对象的实时协同编辑功能,前景可观;

2)本文算法对网络状态的划分尚不够细致,考虑引入客户端、服务器性能、网络覆盖等可控因素,对算法进行改进;

3)添加undo/do[14]、update等操作,提高Co-Editor协同编辑系统的可用性.

[1] Ellis C A,Gibbs S J.Concurrency control in groupware systems [C].Proceedings of the Association for Computing Machinery(ACM)Sigmod International Conference on Management of Data(SICMD),1989:399-407.

[2] Ellis C A,Gibbs S J,Rein G L.Groupware:some issues and experiences [J].Communications of the Association for Computing Machinery(CACM),1991,34(1):39-58.

[3] Sun C Z,Ellis C A.Operational transformation in real-time group editors:issues,algorithms,and achievements[C].Proceedings of the Association for Computing Machinery Conference on Computer Supported Cooperative Work(CSCW),1998:59-68.

[4] Gu N,Yang J M,Zhang Q W.Consistency maintenance based on the mark & retrace technique in groupware systems[C].Proceedings of the International Association for Computing Machinery Sigroup Conference on Supporting Group Work(ACM SIGGROUP),2005:264-273.

[5] Shao B,Li D,Lu T,et al.An operational transformation based synchronization protocol for web 2.0 applications [C].Proceedings of the Association for Computing Machinery Conference on Computer Supported Cooperative Work(CSCW),2011:563-572.

[6] Xia H H,Lu T,Shao B.A partial replication approach for anywhere anytime mobile commenting[C].Proceedings of the 2014thComputer Supported Cooperative Work(CSCW),2014:15-19.

[7] Sun C,Chen D,Jia X.Reversible inclusion and exclusion transformation for string-wise operations in cooperative editing systems[C].Proceedings of the 21st Australasian Computer Science Conference,1997.

[8] Gao Li-ping,Wang Dan,Xiong Nai-xue.Consistency maintenance of collaborative shared documents in unstable network environment[C].Proceedings of the 11st Chinese Conference on Computer Supported Cooperative Work,2016.

[9] Shao B,Li D,Gu N.ABTS:a transformation-based consistency control algorithm for wide-area collaborative applications[C].Proceedings of the International Conference on Collaborative Computing:Networking,Applications and Work Sharing,Los Alamitos:Institute of Electrical and Electronics Engineers(IEEE) Computer Society Press,2009:1-10.

[10] Shao B,Li D,Gu N.A fast operational transformation algorithm for mobile and asynchronous collaboration [J].Institute of Electrical and Electronics Engineers(IEEE) Transaction Parallel and Distributed Systems,2010,21(12):1707-1720.

[11] Li D,Li R.A fast operational transformation algorithm for mobile and asynchronous collaboration [J].An Admissibility-based Operational Transformation Framework for Collaborative Editing Systems,2010,19(1):1-43.

[12] Zheng Y,Shen H F,Sun C Z.Leveraging single-user AutoCAD for collaboration by transparent adaptation [C].Proceedings of the13th International Conference on Computer Supported Cooperative Work in Design,2009:78-83.

[13] Cai Wei-wei,He Fa-zhi,Lv Xiao.An efficient preserving intention operational transformation for real-time collaborative editing [J].Chinese Journal of Computers,2015,38(10):2041-2053.

[14] Yu W,André L,Ignat C L.ACRDT supporting selective undo for collaborative text Editing[C].Proceedings of the Distributed Applications and Interoperable Systems,2015:193-206.

附中文参考文献：

[13] 蔡维纬,何发智,吕 晓.一种高效率的实时协同编辑中意图保持操作转换算法[J].计算机学报,2015,38(10):2041-2053.