基于半分布式实时协同编辑软件的协同处理方法

摘要

本发明公布了一种基于半分布式实时协同编辑软件的协同处理方法。本发明利用半分布式CRES站点间通讯的特征通过对操作进行编号来实现因果保持和收敛性；通过引入多视角队列来实现对只需要操作队列进行一次遍历并只使用包含变换来实现意图保持。利用本发明提供的技术方案，可以降低协同处理算法实现的难度。收敛性策略不需要对文档进行撤销操作；因果保持策略避免了复杂的状态向量计算；意图保持策略不需要先逆向执行排除变换然后再正向执行包含变换；同时每一个操作在发送到其他站点时所需要附加的信息也减少；半分布式CRES利于进行文档管理，编辑权限管理。

说明书

技术领域

本发明提供了一种协同处理方法，具体涉及一种半分布式实时协同编辑软件的协同处理 方法。

背景技术

实时协同编辑软件(Collaborative Real-time Editing Software，简称CRES)支持分布在不 同地理位置的作者来对文档进行协同编辑，在实时性方面有很高的要求。CRES需要在协同 编辑过程中保持文档的一致性以及对编辑中出现的冲突做出处理。协同编辑中文档的一致性 是指在进行协同编辑过程中需要满足：收敛，因果保持，意图保持。其中收敛要求一组操作 在所有的站点上的执行顺序相同；因果保持则要求有因果关系的操作按照他们产生的先后顺 序在所有的站点上执行；意图保持则要求操作在所有的站点上按照它们产生的意图来改变文 档。

1997年，Sun等人在论文“A Generic Operation Transformation Scheme for Consistency  Maintenance in Real-time Cooperative Editing Systems”(Proceedings of the international ACM  SIGGROUP conference on Supporting group work：the integration challenge ACM New York，NY， USA1997)中提出Generic Operation Transformation算法(简称GOT)。GOT是针对分布式结 构的CRES设计的协同处理算法。GOT设计了一种状态向量计算算法来实现收敛和因果保持 的要求，并且通过定义包含变换(Include Transformation)和排除变换(Exclude Transformation) 来实现意图保持。但是在GOT算法中状态向量计算规则复杂，在实现收敛策略时需要先撤消 (Undo)已经执行的操作，同时在实现意图保持时需要对操作队列进行两次遍历。另外分布式 的CRES也存在很难进行文档管理、编辑权限管理等问题。

发明内容

为了便于说明，本文约定：“半分布式CRES”表示CRES的协同站点，分为客户端站点 和服务器站点，通讯只在服务器站点和客户端站点之间进行(如图1)。“客户端站点”表示 半分布式CRES中参与协同编辑的客户端(如图1中的CC_1，CC_2)。“服务器站点”表示半 分布式CRES中的服务器端(如图1中的CS)。操作在客户端站点产生之后会封装成消息发 送到服务器站点(使用O或是O_i来表示，其中i为正整数)；操作在服务器站点处理后将再 一次封装为消息发送到客户端站点(使用EO或是EO_i来表示，其中i为正整数)，因此，根 据上下文“操作”可以等同于“消息”。EO_i表示操作O_i在服务器站点进行意图保持处理后的 结果，EO_i将被服务器站点发送到客户端站点；EO表示操作O在服务器站点上进行意图保持 处理后的结果，EO将被服务器发送到客户端站点。

本发明的目的是提供一种新的方法，使得能够利用半分布式CRES站点间通讯的特征通 过对操作进行编号来实现因果保持和收敛性而不需要撤消已经执行的操作；通过引入多视角 队列(即客户端站点上下文队列，因为从各个客户端看到的队列的元素顺序不同，所以本文 称之为多视角队列)来实现对只需要操作队列进行一次遍历并只使用包含变换来实现意图保 持。使得CRES在保证文档一致性时减少对文档的操作次数并且提高算法对操作的处理速度。

本发明提供的技术方案如下：

一种基于半分布式实时协同编辑软件的协同处理方法，其特征在于，所述协同处理满足 收敛、因果保持和意图保持的方法如下：

A.实现服务器端因果保持的方法：

A1.在服务器站点对所有的客户端站点进行编号，假如有N个客户端站点，则这 些站点的编号分别为0，1，...，N-1；然后在服务器站点上定义一个长度为N的一维 数组SV作为状态向量(N为站点个数)，其中SV[k]记录服务器站点接受的来自 编号为k的客户端站点的操作的个数(k∈{0，1，...，N-1})，并且SV[k]初始化为SV[k]＝0 (注：a＝b表示把b赋值给a，下同)；在编号为k的客户端站点上定义一个变 量SV_k记录该站点发送了的操作次数，SV_k初始化为SV_k＝0；

A2.对于编号为k的客户端站点，如果它产生一个操作O，则SV_k＝SV_k+1；O在被 发送时将SV_k作为附加信息，即O.SV_k；

A3.服务器站点接受O的条件是SV[k]＝＝O.SV_k-1(注：“＝＝”表示相等)，否则 该消息将被延时处理以便保证服务器站点按照客户端站点产生操作的顺序来处 理这些操作；

A4.服务器站点如果接受操作O，则SV[k]＝O.SV_k；

B.实现客户端因果保持的方法：

B1.在服务器站点上定义一个变量SS记录服务器站点发送操作的个数，并且将SS 初始化SS＝0；在编号为k的客户端站点上定义一个变量SS_k记录该客户端站点 接受来自服务器站点的操作的个数，SS_k初始化为SS_k＝0；

B2.服务器站点如果发送操作EO，则SS＝SS+1；EO在被发送时将SS作为附加信息， 即EO.SS；

B3.编号为k的客户端站点接受EO的条件是SS_k＝＝EO.SS-1，否则该消息将被延时处 理以便保证客户端站点按照服务器站点接受操作的顺序来处理这些操作；

B4.编号为k的客户端站点如果接受操作EO，则SS_k＝EO.SS；

C.在服务器站点和客户端站点按照步骤A和步骤B中所定义的方法处理操作后，客户 端站点和服务器站点就能够按照相同的顺序处理操作，因此也就满足了收敛性的要 求；

D.实现服务器站点意图保持的方法：

D1.服务器站点为每一个客户端站点维护一个上下文队列，编号为i的客户端站点的 上下文队列为HB[i]，并且HB[i]初始化为HB[i]＝Φ(即初始化为一个空队列)；HB[i][j] 表示上下文队列HB[i]中的第j个操作；

D2.对于服务器接受的操作O，使用O.id表示产生该操作的客户端站点的编号，O.SS 表示客户端站点产生操作O时该客户端站点上定义的变量SS_k的值；

D3.当一个服务器站点按照A3，A4中步骤对操作进行处理后，上下文队列中HB[O.id] 中从O.SS开始的每一个操作O′，如果O′.id≠O.id则先执行O″＝IT(O，O′)，然后使用 O″′＝IT(O′，O)代替队列中的操作O′，最后执行O＝O″，并开始对队列中下一个操作 按照步骤D3处理；

所述IT为包含变换函数，IT(X，Y)表示考虑操作Y的影响并且实现操作X原来 的意图；

D4.将操作O加入到服务器站点维护的每一个上下文队列中；

E.实现客户端站点意图保持的方法；

E1.在客户端站点使用变量CC_ID来表示该客户端站点的编号；客户端站点维护一 个上下文队列HB，并且HB初始化为HB＝Φ；客户端使用变量MsgReturn来记录 由该客户端发送到服务器，并且从服务器返回的操作的个数；

E2.服务器发送的操作EO使用EO.SS来表示服务器站点发送操作EO时变量SS的值；

EO.id表示操作EO产生的站点的编号；

E3.如果EO.id＝＝CC_ID，则MsgReturn＝MsgReturn+1；否则执行步骤E4；

E4.对于上下文队列HB中从MsgReturn开始的每一个操作O′，先执行EO″＝IT(EO，O′)， 然后使用O″′＝IT(O′，EO)代替队列中的操作O′，最后执行O＝EO″并开始对队列中下 一个操作按照步骤E4处理。

步骤D3中所述包含变换函数IT所实现的功能为，对本操作所表示的编辑位置进行调整 使得本操作考虑到其他操作的影响并且保持本操作原来的意图。在协同编辑过程中发送的操 作含有两个基本数据：1.该操作编辑的位置；2.编辑的内容。当操作发送到一个站点时由于该 站点上的文档可能已经改变，所以操作需要对编辑的位置进行调整以实现原来的意图。该函 数的实现和操作的具体类型相关，在具体实现时根据具体操作的关系来定义包含变换函数。 例如对于两个插入字符的操作在下文的具体实施说明方式部分通过实例描述了包含变换函数 的具体实现。

优选的，在服务器站点为每一个客户端站点维护一个上下文队列，当操作到达服务器站 点后按照步骤D中定义的意图保持方法进行处理；在客户端站点为服务器站点维护上下文队 列，服务器站点发送的操作到达客户端站点后按照步骤E中定义的意图保持方法进行处理； 因此意图保持方法不需要先逆向执行排除变换然后再正向执行包含变换，每一个操作在发送 到其他站点时所需要附加的信息减少了。

优选的，将一致性的要求和实时协同编辑软件的结构结合起来；实时协同编辑软件的站 点被分为客户端站点和服务器站点，通讯只在服务器站点和客户端站点之间进行；在这个基 础之上通过步骤A和步骤B中的方法实现因果保持的要求。

优选的，通讯只在服务器站点和客户端站点之间进行，在服务器站点和客户端站点都满 足了因果保持的要求的基础上，可以保证服务器站点和客户端站点都按照相同的顺序执行操 作，因而满足了收敛的要求并且不需要单独定义算法来满足收敛的要求。

本发明的有益效果：利用本发明提供的技术方案，可以降低协同处理算法实现的难度。 GOT在实现收敛策略时需要先撤消已经执行的操作，而本发明的收敛性策略不需要对文档进 行撤销操作；GOT设计了一种复杂的状态向量计算算法来实现因果保持，而本发明的因果保 持策略通过对操作进行编号从而避免了复杂的状态向量计算；GOT在实现意图保持时先逆向 执行排除变换然后再正向执行包含变换，因此需要对上下文队列进行两次遍历，而本发明的 意图保持策略只需要执行包含变换，因而只需要对上下文队列进行一次遍历；同时每一个操 作在发送到其他站点时所需要附加的信息也减少；半分布式CRES利于进行文档管理，编辑 权限管理。

附图说明

图1半分布式结构CRES的一个协同编辑场景。

图2分布式结构CRES的一个协同编辑场景。

具体实施方式

服务器站点意图保持算法的说明：

对于服务器站点可以根据上文步骤D定义如下算法处理步骤：

对于客户端站点可以根据上文步骤E定义如下算法处理步骤：

包含变换函数(Include Transformation，IT)说明：

图2描述的是分布式结构CRES的一个协同编辑场景。Site0，Site1，Site2是三个协同站点。 在分布式的CRES中各个站点间相互通讯。当一个操作产生后，该操作将会被发送到其他站 点。例如图中操作O₁在产生后将会被发送到站点Site1，Site2。假设图2中所有站点的文档内 容最初始为“ABCDEF”。假设操作O₁的意图是字符”A”前面插入一个字符“0”，记为： O₁＝insert[“0”，0]；操作O₂的意图是在字符“B”前面插入一个字符“1”，记为：O₂＝insert[“1”，1]。 按照意图保持的要求，当Site0和Site1在执行操作O₁及O₂之后结果应该为“0A1BCDEF”。 但是当操作O₂到达了站点Site0时如果O₂不加任何的处理而直接在Site0上执行，在Site0 的结果为“01ABCDEF”。这明显是错误的。因此为了保证O₂的意图能在站点Site0上得到实 现，则应该对O₂进行包含变换。操作O₂＝IT(O₂，O₁)是对操作O₂执行包含变换的结果。操作 O₂考虑到O₁的影响并且在站点site0上实现O₂的意图。根据以上的具体情况可知 O₂＝IT(O₂，O₁)＝insert[“1”，2]，则当O₂代替操作O₂在站点Site0上执行后Site0的结果为 “0A1BCDEF”。这样就保证了站点site0和site1上的文档最终是一致的。通过以上分析可知 包含变换函数是对操作O₂编辑的位置向后移动一个字符(因为操作O₁在操作O₂编辑的位置 的前面插入了一个字符)。

客户端站点上下文队列(即多视角队列)说明：

在本算法的意图保持策略中，服务器站点将为每一个客户端站点维护一个上下文队列。 这样做的目的是使得服务器站点在处理一个操作时只需要执行包含转换即可。每个客户端站 点按照它的上下文队列中的操作的顺序来执行这些操作，但是最后文档结果是一致的。客户 端站点的上下文队列中操作的顺序是从该客户端站点的角度看到的顺序，因此这种上下文队 列也称为视角队列。例如：三个不同客户端站点CC_1，CC_2，CC_3分别执行了 O₁＝Insert[“O”，0]，O₂＝Insert[“1”，1]，O₃＝Insert[“2”，2]三个操作，这些操作到达服务器站点的顺序 为O₁，O₂，O₃。在CC_1看来这些操作执行的顺序为：Insert[“0”，0]，Insert[“1”，2]，Insert[“2”，4]， 服务器站点将操作按照这个顺序放在一个新队列中，即客户端站点CC_1的上下文队列；在 CC_2看来这些操作执行的顺序为：Insert[“1”，1]，Insert[“0”，0]，Insert[“2”，4]，服务器站点将操作 按照这个顺序放在一个新队列中，即客户端站点CC_2上下文队列；在CC_3看来这些操作 执行的顺序为：Inset[“2”，2]，Insert[“0”，0]，Insert[“1”，2]，服务器站点将操作按照这个顺序放在 一个新队列中，即客户端站点CC_3上下文队列。通过这个实例可以得知：每个客户端站点 的上下文队列中操作的顺序是将原来队列中由该站点产生的操作放在上下文队列的前面，而 其他的操作按照原来顺序加入到上下文队列。操作在加入到上下文队列时需要保持原来的意 图。例如：客户端站点CC_2的上下文队列是将原来的第二个操作(即操作O₂)作为CC_2 下文队列的第一个操作，而原来的第一个，第三个操作按照原来的顺序加入到上下文队列中； 操作O₁加入到CC_2的上下文队列时需要在考虑到O₂的影响并且保持原来的意图，即CC_2 上下文中的第二个操作为Insert[“0”，0]，同理第三个操作为Insert[“2”，4]。这个过程的具体实 施可参考上文意图保持算法说明部分。

这样做的目的是使得当服务器站点在处理下一个操作时只需要执行包含变换而不需要和 GOT中那样需要先执行排除变换然后再执行包含变换。例如：如果现在需要处理一个来自客 户端站点CC_1的操作O₄＝insert[“3”，4]，按照上述步骤D2中描述，需要将O₄和CC_1视角队 列中的第二个，第三个操作执行包含转换。即最后EO₄＝insert[“4”，6]。当处理完成之后，EO₄ 可以直接放入到CC_1，CC_2，CC_3视角队列的队尾。在CC_1的视角队列中还需要对原来队 列中的第二个、第三个操作进行包含变换使得它们能够考虑到操作EO₄的影响。这实际上是 对CC_1的视角队列做一个调整，使得下一个来自CC_1的操作也能按照O₄这样的顺序进行 处理。下面通过举例来说明意图保持算法的工作原理。

意图保持策略实例说明：

图1中描述的是半分布式结构的CRES的一个协同编辑场景。在半分布式结构的CRES 中，站点分为客户端站点和服务器站点。客户端站点如图中的CC_1，CC_2；服务器站点如 图中的CS。半分布式结构的CRES站点间的通讯方式是客户端站点将消息发送到服务器站点， 在服务器站点上进行处理完成后由服务器站点推送到客户端站点。例如：图中操作O₁在站点 CC_1上产生后发送到服务器站点，在服务器站点处理完成后将处理完的结果EO₁发送到客 户端站点。下面以图1为例来说明算法的处理过程。

假如O₂＝insert[“0”，0]，O₃＝insert[“1”，3]，O₁＝insert[“2”，2]。

服务器站点处理的步骤如下：

服务器站点为每个客户端站点建立一个上下文队列。站点CC_1的上下文为HB[1]，CC_2 的上下文为HB[2]。初始值HB[][]＝Φ。

当O₂到达服务器站点时，由于HB[2]＝Φ，O₂不需要进行包含变换，服务器站点执行 O₂(EO₂＝O₂)。同时HB[1].Add(EO₂)，HB[2].Add(EO₂)。

当O₃到达服务器站点时，HB[2]＝[EO₂]，而O₃是依赖于EO₂的，按照算法中描述，所以O₃也不进行包含变换，在服务器站点上执行EO₃(EO₃＝O₃)。同时HB[1].Add(EO₃)， HB[2].Add(EO₃)。

当O₁到达服务器站点时，HB[1]＝[EO₂，EO₃]，由于O₁和EO₂没有依赖关系，第一步： O₁’＝IT(O₁，EO₂)＝insert[“2”，3]；EO₂’＝IT(EO₂，O₁)＝insert[“0”，0]；使用EO₂’代替HB[1]中的EO₂。第 二步：O₁”＝IT(O₁’，EO₃)＝insert[“2”，3]；EO₃’＝IT(EO₃，O₁’)＝insert[“1”，4]；使用EO₃’代替HB[1] 中的EO₃。第三步：执行O₁”；HB[2].Add(EO₁)，HB[1]Add(EO₁)(注：EO₁＝O₁”)。

当O₄到达服务器站点时，根据算法，O₄和HB[1][0](即队列HB[1]中的操作EO₂)， HB[1][1](即队列HB[1]中的操作EO₃)执行包含转换，处理过程和O₁的处理过程类似。同理 可分析O₅在服务器站点的处理过程。

客户端站点处理步骤如下(以站点CC_1为例)：

当CC_1产生O₁，O₄之后，在客户端站点CC_1，HB＝[O₁，O₄]。当操作EO₂到达客户端站点 CC_1时，为了保持EO₂的意图，EO₂需要和O₁，O₄分别进行包含变换，同时调整上下文保证 EO₃达到时仍按照这个顺序处理。

当EO₁到达CC_1时，由于EO₁的原始操作O₁在站点CC_1上产生，因而EO₁的意图已 经在该站点上实现。因此不进行变换处理，同时MsgReturn++；同样EO₄到达时，也按照这样 的步骤处理。

当EO₅到达时由于MsgRetum＝2，按照算法中的描述，EO₅不需要和O₁，O₄进行变换，这 是因为EO₅在服务器站点执行时已经考虑到O₁，O₄的影响。

算法复杂度说明：

算法时间复杂度：假设有n个协同站点参与协同编辑，CRES已经处理过m个消息，则 对于任何一个新产生的操作，根据定义的算法在处理该操作时需要对操作队列进行一次遍历， 因此算法的时间复杂度为O(m)。

算法空间复杂度：根据定义的算法，由于服务器站点为每个协同站点维护n个视角，因 此需要的存储空间为m*n。

传统的GOT算法在实现因果保持和收敛时都需要复杂的状态向量计算。对于一个操作， 因果保持和收敛处理的时间复杂度为O(n)，而意图保持需要对队列进行两次遍历，因此时间 复杂度为O(2m)。最后总体的时间复杂度为O(2m)+O(n)。

另外还可以从两种算法处理一个操作时对文档更新的次数的角度来比较。本算法处理一 个操作时只需要在因果保持之后对文档进行一次更新。而GOT算法由于在实现收敛时需要先 撤消队列中的操作，然后再将操作更新到文档，因此处理一个操作时GOT需要对文档进行2m 次操作。在实际的应用中，对文档的更新是最耗时间的部分。以本算法验证程序Spreadsheet 为例：在服务器端删除一行相当于将数组中的元素依次向前移动一个位置。对于GOT算法， 处理一个操作需要对文档进行2m次类似的操作，而本算法只需要进行一次。