协同文本编辑系统的研究与实现

廖斌

摘 要：协同文本编辑系统可以使地理上分布在不同位置的用户通过网络来对同一共享文本对象进行查看和编辑。本文分析了实时协同文本编辑系统的协作架构和体系结构。以操作转换算法为基础，来实现一个协同文本编辑的原型系统，详细讨论了实现过程中的问题。

关键词：协同编辑；协作架构；体系结构；操作转换

一、引言

随着计算机和网络技术的发展，人们渴望自然的、自由的、随时随地的进行配合工作。因此，计算机支持的协同工作（Computer Supported Collaborative Work，简称CSCW）的概念便應运而生。对于计算机支持的协同工作的理论和技术，国内外已有大量的研究工作，已经成为计算机科学技术领域的一个研究热点。同时其也为系统科学和系统工程的研究提供强有力的支持手段，具有极其广阔的应用领域[1][2][3][4]。

协同文本编辑系统强调自然和谐的人人交互，对于系统响应有很高的要求。因此，该系统通常使用复制式的体系结构。在此种结构下，文本被复制到多个协同用户处。在多个用户并发交互的情况，必然会导致文本的版本的一致性维护问题。一致性维护（或者说并发控制）是实时协同编辑系统中需要解决的核心难题[5][6][7][8]。人们已经提出了大量的并发控制方法，比如两段锁、序列化、时间标签、令牌传递等。但是这些方法并不能直接应用于计算机支持的协同工作中，否则会使得协同编辑的效果大打折扣。考虑到这些问题，本文研究分析了协同文本编辑系统的协作架构和体系结构，并在操作转换类算法的基础上，实现了一个实时协同文本编辑原型系统。

二、协作架构与体系结构

协作架构指的是如何构造一个CSCW系统。协作架构（Collaborative Infrastructure）在1994年的IEEE Computer杂志CSCW专辑中是以协作框架（Collaborative Framework）来表述的。目前多以协作架构来表述（Infrastructure）。当前CSCW系统有两类协作架构，透明协作架构（Collaboration-transparent）和明确协作架构（Collaboration-aware）。采用透明协作架构的CSCW系统允许多个用户通过对单用户应用程序进行共享的方式来协同工作。而明确协作架构在处理协同工作的事件时，需要明确协作站点之间操作意图，以及相应的同构或者异构应用软件处理相关操作的机制。

（1）典型协作架构。在典型透明协作架构中，通过给普通的单用户应用程序增加协作功能，来获得一个协同工作系统。这种情况下的单用户应用程序就被称为透明应用。应用共享方式是透明协作架构的一个代表。在这种模式下，一个单机应用软件可以借助于互联网构建成多个协作站点协同工作的软件系统。其中较为有代表性的工作是将WPS、SolidWorks等单机应用软件通过某个第三方提供的共享应用程序（比如NetMeeting），将相同的人机交互界面提供给各个协同站点的用户，同时可以接受各个用户的交互操作命令，从而实现了一种多用户并发交互的模式。

显然，某个第三方提供的共享应用程序起到一种桥梁的作用，其把多用户输入的操作命令收集到一起，并且将其分发到除了本站以外的其他站点。各个其他站点的单机应用软件响应这些操作命令，并且按照某种顺序执行，从而给各个用户提供相应的反馈结果。应用共享方式遵循严格“WYSIWIS”的原则，通常采用两种实现模式：集中式（centralized）和复制式（duplicated）。

基于集中式体系结构的应用共享，人们将其定义为单版本对象的应用共享，其表明被共同使用的单机应用软件只运行在服务器端，其他的多用户站点都将作为客户端。多个用户的输入操作命令都将传输到服务器端执行，并将执行结果通过网络传递给其他协作用户。在其他用户的站点上，同样通过相应的单机应用软件将结果显示出来。基于复制式体系结构的应用共享，人们将其定义为多版本对象的应用共享，其表明在多个协作站点都要同时运行单机应用软件。每个用户输入的操作命令都要通过网络传递给其他所有的协作用户。当然，在此过程中必然会采用某种一致性维护方法，从而使得各个用户的单机应用软件都接受到本质上相同的输入操作命令，以提供给各个用户一致的用户界面和执行结果。由于多版本对象的应用共享实现起来较为复杂，因此更多的系统都使用单版本对象的应用共享形式，这其中比较有代表性的工作包括Microsoft NetMeeting，以及创通ShareVision。单版本对象的应用共享的特点使其易于实现对象的一致性维护，但是其非常耗费网络资源，对于图形图像等非线性数据对象，这个弊端非常明显。多版本对象的应用共享很好地克服了前者耗费大量网络资源的问题，并且对于多用户的操作能够较快的响应，但是其同时也面临着一致性维护的挑战。同时，对于多用户的动态参与或者退出协同工作，管理起来会更加困难。

在应用共享的具体实现过程，需要考虑输入与输出操作命令的获取、掌控机制和多用户交互感知等诸多要素。例如，在以Microsoft NetMeeting为代表性工作的系统中，用户借助于单机应用软件，能够获取单机模式下所有的软件固有功能。但是，这类工作通常遵循严格的掌控机制，即只有拥有控制权的用户才能进行操作，多用户之间并不存在真正意义上的协同工作。因此，此种模式具有很大的局限性。其次，在明确协作架构中，通常需要重新开发（或者需要对源代码进行扩展）。如果要研制一个新的协作系统，需要重新定义相应操作命令的协作架构以及通信机制，即对于协作处理过程和意图，各个站点的用户和单机应用软件都要十分清楚，以便支持明确协作架构。

明确协作架构的优点是协作性能好，主要表现在交互的灵活、并发性和群体感知等方面。其主要缺点是需要额外的开发工作，既要开发应用功能，又要开发协作功能，使得协同工作系统与对应的单用户系统相比，在可用性和功能性方面受到牵制。这种方式适合进行理论研究，例如SUN CZ的REDUCE等。

（2）非典型协作架构。由于上述两类典型协作架构的不足，人们又对非典型协作架构（又称混合架构）进行了探索。其中，Java协同工作环境（JCE，Java Collaborative Environment）和 Habanero 系统局限于Java应用程序，并且需要对单用户应用的源代码进行少量的修改。灵活透明协作（Flexible Collaboration Transparency）方法则是在运行时用多用户界面来替换单用户交互界面以获得灵活性。但是该方法局限于 swing-based的Java小应用程序，对运行平台有特殊要求（如进程迁移、运行时对象替换、绑定等）。智能透明协作（ICT，Intelligent Collaboration Transparency）方法通过截取和重放用户消息来取得智能性（在处理异构问题时进行语义翻译），但该方法主要针对文本编辑程序。与智能透明协作方法类似，应用协同（Application Cooperating）方法取得了比应用共享更好的效果，主要实例是一个Windows 自带的简单二维绘图程序。这些非典型框架没有像集中式应用共享那样需要回传界面像素，而是交换事件消息。这样，在一定程度上提高了协作的灵活性。但是，这些消息主要是一些用户界面I/O消息（键盘和鼠标事件消息），需要大量的工作用于过滤、分解、翻译和执行这些底层消息，并随着应用背景的复杂化（例如达到商品化三维CAD系统的复杂程度）而急剧增加。这也可以解释为何在上述非典型框架中总是给出一些简单应用程序例子如文本编辑和 Windows绘图程序等。

由于复制式透明系统实现起来比集中式透明系統复杂和困难得多，故集中式透明系统成为透明系统的代表。就WYSIWIS、群体感知、网络带宽和协作任务等问题，Begole对透明系统和明确系统进行了比较。在Begole的比较中，典型的透明系统处于不利的地位。但是需要指出的是，Begole的比较并不公正，因为该比较实际进行的是集中式透明系统和复制式明确系统之间的比较。

（3）体系结构。由于不同背景应用系统的共享工作空间和用户间的交互方式千差万别，各种应用系统的结构也不相同，通常可以从体系结构上加以综述。现有的CSCW系统通常采用三种体系结构：集中式、复制式和混合式。

集中式结构包括一个或多个集中式的服务器及多个与服务器交互的客户端。客户端主要用于实现人机交互，即将用户发出的操作命令转换成服务器端系统可以理解并且执行的形式。而服务器在执行相应的操作后，将处理结果以用户可以认知的形式通过客户端反馈给用户。服务器控制和管理整个系统中的操作命令和操作对象。基于此种结构，系统可以较为容易的实现数据对象的一致性维护，以及用户界面视图的同步，但是其会导致系统的容错性较差，响应性也不能得到保证。

复制式结构本质上指的是处于系统中的各个协作站点既是服务器，也是客户端。各进程（站点）在地位上是对等的。它们都可以维护共享数据副本，也可以将用户的操作转化成事件后直接作用于它所维护的对象，同时将事件发送到相关其他站点。同集中式结构相比，复制式结构可以避免可靠性差以及响应速度降低等缺点，但是系统复杂程度较高。例如由于很难保证所有事件都按同一顺序到达其他进程（站点），因此很难保证各进程（站点）维护的目标对象的一致性。

混合式处于集中式和复制式之间，目的是继承集中式和复制式的优点。例如 PACT中的联邦式体系结构、CoDrawS 中的树状分布式结构等。这种方式的优缺点正好与应用共享方式相反：新系统的设计和实现比较灵活，可以自由选择所需的系统结构、共享数据的结构和分布结构、并发控制策略、人人协作方式和交互界面。

三、操作转换方法的构建

操作转换是明确复制式文本协同编辑的常用并发控制方法，其着眼于操作本身，试图通过变换操作的参数来实现操作意愿维护，具有较好的响应效果，但由于其与操作语义紧密相关，以及网络传输延迟的不确定性，当结点规模稍大时，操作之间的关系变得非常复杂，构造转换函数的难度较高。

设N代表系统中站点的个数，每个站点都有一个唯一的站点号i（1<=i<=N）来标识本站点。第j个站点的状态向量是一个N元向量组，其中第i个分量值表示已有多少个来自站点i的操作被站点j执行。对于任意两个状态向量 和 之间的关系，本文可以这样定义：

（1）Si=Sj Si中每个分量的值都等于Sj中对应分量的值。

（2）Si

（3）Si>Sj Si中至少有一个分量的值大于Sj中对应分量的值。

请求是一个元组形式，i表示站点号，s表示发起操作o站点的状态向量，p表示站点i的优先级。

请求队列：用来存放请求的队列，在下列2种情况下将请求加入请求队列中：

①本地站点从本地接收到一个请求；

②本地站点从网络中接收到一个异地请求。

一旦请求被执行，该请求就从请求队列中移除。

执行队列：每个站点都保存着一个被执行请求的日志，该日志按照插入的顺序排列。

在程序的实现过程中，假设操作O是来自于站点S，状态向量为SVO，在同时满足以下两个关系时才可以说O在站点d（d≠s）是满足因果保持关系的：

① SVo[s]=SVd[s]+1；

②SVo[i]≤SVd[i] i∈[1，2….N-1] and i≠s。

第一个条件保证了O是站点S队列中下一个要执行的操作，因此站点S发出的操作不会被站点d遗漏；第二个条件保证了在其他站点产生的并且在操作O发出之前的操作已经在站点S和站点d都已被执行过了。这两个关系保证了所有的在因果关系上先于O的操作已经在站点d执行过了。可以看到一个远程操作的执行如果同时满足以上两个条件，那么所有的操作都将按照它们的因果关系执行，从而实现了一致性模型中因果保持约束这一属性。

在操作转换算法的实现中，任何两条命令之间关系的判断是该算法的核心部分，因此在该算法的实现过程中，本文是按照如下流程进行判断的：

①接收到来自i的命令；

②比较站点i命令中状态向量第i个分量和站点j命令中状态向量第i个分量间是否满足：SVi[i]=SVj[i]+1，并且SVi[k]

第一个条件应使得站点i命令中状态向量第i个分量等于站点j命令中状态向量第i个分量值加1；

第二个条件应使得站点i命令中状态向量各个分量应小于等于站点j命令中状态向量各个分量值（除了第i个分量外）；

③若同时满足上述两个条件，就可以说Oj-> Oi；否则Oj||Oi。

本文以第i个站点作为对象来说明（ 表示第i个站点的请求队列；Qi表示第i个站点的执行队列，Li表示第i个站点的状态向量），具体算法流程如下

初始化：

Qi<-empty；

Li<-empty；

Si<-<0，0，....，0>。

产生操作：

从本地用户接收到一个命令；

Qi<-Qi+，将该命令传播到其他站点。

接收命令：

从网络中接收到命令；

Qi<-Qi+。

执行命令：

for each ∈Qiwhere Sj≤Sibegin

Qi<-Qi

if Sj

<-most recent entry in Li

where Sk≤Sj（or null if none）

do while ！=null and Oj ！=null

if the K'th component of Sj is≤the K'th component of Sk Oj<-T（Oj，Ok，Pj，Pk）

fi

od

fi

在站点i执行操作Oj；

Li<-Li+

中对应的第j个分量加1。

在初始化阶段把请求队列和执行队列置为空，各站点的状态向量每个分量都置为0；该算法的关键在于执行操作转换：遍历请求队列，找到可能执行的请求Rj=，Rj是否能够执行关键在于比较状态向量Si和Sj的关系，有3种可能：

①Sj> Si

请求不能被执行（操作Oj在站点j已经执行，但是在站点i还没有执行），因此该请求被放入Si的请求队列中；

②Sj=Si

Oj不需要任何转换马上执行；

③Sj

在这种情况下，请求可以执行，但是因为Rj所指示的状态向量是比站点i当前更早的状态向量，所以Oj必须经过转换。

四、系统实现

首先将要测试的命令存入服务器站点上，各分站点连接服务器后，服务器将预存入的命令向各个对应站点发送，各分站点接收到命令之后，经解析后执行，最后将执行效果显示在各个分站点的界面上。在程序中本文是以站点号来表示各个站点的优先级的，站点号越大表示该站点所具有的优先级别越高。为表示测试的一般性，在本例中测试的站点个数为3个，如图1所示。

本文所开发的协同文本编辑系统建立在如下的开发环境上：操作系统平台为Windows 7；网络平台为基于TCP/IP的Internet/Intranet网络；网络通讯协议为基于MFC的WinSocket 2.0通讯协议；VS 2010集成开发环境。

系统中所测试的命令均为8元组形式，例如1：000IA0，1表示站点号，000表示当前站点的状态向量，I表示插入操作，A表示插入的字符，0表示插入的参数位置。该命令表示接收到一号站点发来的在当前文本第0个位置上插入字符A。

五、结论

协同文本编辑系统中一致性维护问题将是CSCW研究人员长期研究的课题。关于多用户协同交互的基本方法需要进一步探索，协同文本编辑的原型系统需要进一步改进和完善。意图不一致问题一直是困扰研究人员的难题，如何解决该问题将是未来潜心研究的核心课题。

参考文献：

[1]Chen D.，Sun C.A distributed algorithm for graphic objects replication in real-time group editors[C]//. Proceedings of the international ACM SIGGROUP conference on supporting group work.New York：ACM，1999：121—130.

[2]Dubs S.，Haynes S. Distributed facilitation：a concept whose time has come？[C]// Proceedings of 1992 ACM Conference on CSCW. Toronto：ACM，1992：314—321.

[3]Ellis C.，Gibbs S. Concurrency control in groupware systems[C]. Proceeding of the 1989 ACM SIGMOD international conterence on Management of Data. Seattle：ACM，1989：399—407.

[4]Ellis C.，Gibbs S.，Reln G. Groupware：some issues and experiences[J].Communications of the ACM，1991，34（01）：39—58.

[5]Feng J.，Lin Z.A human-human interaction interface in cooperative editing system[C]//. Proceedings of Third International Workshop on CSCW in Design. Tokyo，1998：TF1-4.

[6]Flores F.，Graves M.，Hartfield B.，et al. Computer systems and the design of organizational interaction[J].ACM Transactions on Information Systems， 1988，6（06）：153—172.

[7]Garfinkel D.，Gust P.，Lemon M.，et al.The SharedX multiuser interface user's guide， version 2.0[R].Palo Alto：Hewlett-Packard Laboratories，1989.

[8]Greenberg S.，ed.Computer supported cooperative work and groupware：An introduction to the special edition[J]. International Journal of man machine studies，1992，34（02）：133—143.

（作者單位：湖北大学计算机与信息工程学院）