廖斌

摘 要：協(xié)同文本編輯系統(tǒng)可以使地理上分布在不同位置的用戶通過網(wǎng)絡(luò)來對同一共享文本對象進行查看和編輯。本文分析了實時協(xié)同文本編輯系統(tǒng)的協(xié)作架構(gòu)和體系結(jié)構(gòu)。以操作轉(zhuǎn)換算法為基礎(chǔ)，來實現(xiàn)一個協(xié)同文本編輯的原型系統(tǒng)，詳細討論了實現(xiàn)過程中的問題。

關(guān)鍵詞：協(xié)同編輯；協(xié)作架構(gòu)；體系結(jié)構(gòu)；操作轉(zhuǎn)換

一、引言

隨著計算機和網(wǎng)絡(luò)技術(shù)的發(fā)展，人們渴望自然的、自由的、隨時隨地的進行配合工作。因此，計算機支持的協(xié)同工作（Computer Supported Collaborative Work，簡稱CSCW）的概念便應(yīng)運而生。對于計算機支持的協(xié)同工作的理論和技術(shù)，國內(nèi)外已有大量的研究工作，已經(jīng)成為計算機科學(xué)技術(shù)領(lǐng)域的一個研究熱點。同時其也為系統(tǒng)科學(xué)和系統(tǒng)工程的研究提供強有力的支持手段，具有極其廣闊的應(yīng)用領(lǐng)域[1][2][3][4]。

協(xié)同文本編輯系統(tǒng)強調(diào)自然和諧的人人交互，對于系統(tǒng)響應(yīng)有很高的要求。因此，該系統(tǒng)通常使用復(fù)制式的體系結(jié)構(gòu)。在此種結(jié)構(gòu)下，文本被復(fù)制到多個協(xié)同用戶處。在多個用戶并發(fā)交互的情況，必然會導(dǎo)致文本的版本的一致性維護問題。一致性維護（或者說并發(fā)控制）是實時協(xié)同編輯系統(tǒng)中需要解決的核心難題[5][6][7][8]。人們已經(jīng)提出了大量的并發(fā)控制方法，比如兩段鎖、序列化、時間標簽、令牌傳遞等。但是這些方法并不能直接應(yīng)用于計算機支持的協(xié)同工作中，否則會使得協(xié)同編輯的效果大打折扣?？紤]到這些問題，本文研究分析了協(xié)同文本編輯系統(tǒng)的協(xié)作架構(gòu)和體系結(jié)構(gòu)，并在操作轉(zhuǎn)換類算法的基礎(chǔ)上，實現(xiàn)了一個實時協(xié)同文本編輯原型系統(tǒng)。

二、協(xié)作架構(gòu)與體系結(jié)構(gòu)

協(xié)作架構(gòu)指的是如何構(gòu)造一個CSCW系統(tǒng)。協(xié)作架構(gòu)（Collaborative Infrastructure）在1994年的IEEE Computer雜志CSCW專輯中是以協(xié)作框架（Collaborative Framework）來表述的。目前多以協(xié)作架構(gòu)來表述（Infrastructure）。當(dāng)前CSCW系統(tǒng)有兩類協(xié)作架構(gòu)，透明協(xié)作架構(gòu)（Collaboration-transparent）和明確協(xié)作架構(gòu)（Collaboration-aware）。采用透明協(xié)作架構(gòu)的CSCW系統(tǒng)允許多個用戶通過對單用戶應(yīng)用程序進行共享的方式來協(xié)同工作。而明確協(xié)作架構(gòu)在處理協(xié)同工作的事件時，需要明確協(xié)作站點之間操作意圖，以及相應(yīng)的同構(gòu)或者異構(gòu)應(yīng)用軟件處理相關(guān)操作的機制。

（1）典型協(xié)作架構(gòu)。在典型透明協(xié)作架構(gòu)中，通過給普通的單用戶應(yīng)用程序增加協(xié)作功能，來獲得一個協(xié)同工作系統(tǒng)。這種情況下的單用戶應(yīng)用程序就被稱為透明應(yīng)用。應(yīng)用共享方式是透明協(xié)作架構(gòu)的一個代表。在這種模式下，一個單機應(yīng)用軟件可以借助于互聯(lián)網(wǎng)構(gòu)建成多個協(xié)作站點協(xié)同工作的軟件系統(tǒng)。其中較為有代表性的工作是將WPS、SolidWorks等單機應(yīng)用軟件通過某個第三方提供的共享應(yīng)用程序（比如NetMeeting），將相同的人機交互界面提供給各個協(xié)同站點的用戶，同時可以接受各個用戶的交互操作命令，從而實現(xiàn)了一種多用戶并發(fā)交互的模式。

顯然，某個第三方提供的共享應(yīng)用程序起到一種橋梁的作用，其把多用戶輸入的操作命令收集到一起，并且將其分發(fā)到除了本站以外的其他站點。各個其他站點的單機應(yīng)用軟件響應(yīng)這些操作命令，并且按照某種順序執(zhí)行，從而給各個用戶提供相應(yīng)的反饋結(jié)果。應(yīng)用共享方式遵循嚴格“WYSIWIS”的原則，通常采用兩種實現(xiàn)模式：集中式（centralized）和復(fù)制式（duplicated）。

基于集中式體系結(jié)構(gòu)的應(yīng)用共享，人們將其定義為單版本對象的應(yīng)用共享，其表明被共同使用的單機應(yīng)用軟件只運行在服務(wù)器端，其他的多用戶站點都將作為客戶端。多個用戶的輸入操作命令都將傳輸?shù)椒?wù)器端執(zhí)行，并將執(zhí)行結(jié)果通過網(wǎng)絡(luò)傳遞給其他協(xié)作用戶。在其他用戶的站點上，同樣通過相應(yīng)的單機應(yīng)用軟件將結(jié)果顯示出來?；趶?fù)制式體系結(jié)構(gòu)的應(yīng)用共享，人們將其定義為多版本對象的應(yīng)用共享，其表明在多個協(xié)作站點都要同時運行單機應(yīng)用軟件。每個用戶輸入的操作命令都要通過網(wǎng)絡(luò)傳遞給其他所有的協(xié)作用戶。當(dāng)然，在此過程中必然會采用某種一致性維護方法，從而使得各個用戶的單機應(yīng)用軟件都接受到本質(zhì)上相同的輸入操作命令，以提供給各個用戶一致的用戶界面和執(zhí)行結(jié)果。由于多版本對象的應(yīng)用共享實現(xiàn)起來較為復(fù)雜，因此更多的系統(tǒng)都使用單版本對象的應(yīng)用共享形式，這其中比較有代表性的工作包括Microsoft NetMeeting，以及創(chuàng)通ShareVision。單版本對象的應(yīng)用共享的特點使其易于實現(xiàn)對象的一致性維護，但是其非常耗費網(wǎng)絡(luò)資源，對于圖形圖像等非線性數(shù)據(jù)對象，這個弊端非常明顯。多版本對象的應(yīng)用共享很好地克服了前者耗費大量網(wǎng)絡(luò)資源的問題，并且對于多用戶的操作能夠較快的響應(yīng)，但是其同時也面臨著一致性維護的挑戰(zhàn)。同時，對于多用戶的動態(tài)參與或者退出協(xié)同工作，管理起來會更加困難。

在應(yīng)用共享的具體實現(xiàn)過程，需要考慮輸入與輸出操作命令的獲取、掌控機制和多用戶交互感知等諸多要素。例如，在以Microsoft NetMeeting為代表性工作的系統(tǒng)中，用戶借助于單機應(yīng)用軟件，能夠獲取單機模式下所有的軟件固有功能。但是，這類工作通常遵循嚴格的掌控機制，即只有擁有控制權(quán)的用戶才能進行操作，多用戶之間并不存在真正意義上的協(xié)同工作。因此，此種模式具有很大的局限性。其次，在明確協(xié)作架構(gòu)中，通常需要重新開發(fā)（或者需要對源代碼進行擴展）。如果要研制一個新的協(xié)作系統(tǒng)，需要重新定義相應(yīng)操作命令的協(xié)作架構(gòu)以及通信機制，即對于協(xié)作處理過程和意圖，各個站點的用戶和單機應(yīng)用軟件都要十分清楚，以便支持明確協(xié)作架構(gòu)。

明確協(xié)作架構(gòu)的優(yōu)點是協(xié)作性能好，主要表現(xiàn)在交互的靈活、并發(fā)性和群體感知等方面。其主要缺點是需要額外的開發(fā)工作，既要開發(fā)應(yīng)用功能，又要開發(fā)協(xié)作功能，使得協(xié)同工作系統(tǒng)與對應(yīng)的單用戶系統(tǒng)相比，在可用性和功能性方面受到牽制。這種方式適合進行理論研究，例如SUN CZ的REDUCE等。

（2）非典型協(xié)作架構(gòu)。由于上述兩類典型協(xié)作架構(gòu)的不足，人們又對非典型協(xié)作架構(gòu)（又稱混合架構(gòu)）進行了探索。其中，Java協(xié)同工作環(huán)境（JCE，Java Collaborative Environment）和 Habanero 系統(tǒng)局限于Java應(yīng)用程序，并且需要對單用戶應(yīng)用的源代碼進行少量的修改。靈活透明協(xié)作（Flexible Collaboration Transparency）方法則是在運行時用多用戶界面來替換單用戶交互界面以獲得靈活性。但是該方法局限于 swing-based的Java小應(yīng)用程序，對運行平臺有特殊要求（如進程遷移、運行時對象替換、綁定等）。智能透明協(xié)作（ICT，Intelligent Collaboration Transparency）方法通過截取和重放用戶消息來取得智能性（在處理異構(gòu)問題時進行語義翻譯），但該方法主要針對文本編輯程序。與智能透明協(xié)作方法類似，應(yīng)用協(xié)同（Application Cooperating）方法取得了比應(yīng)用共享更好的效果，主要實例是一個Windows 自帶的簡單二維繪圖程序。這些非典型框架沒有像集中式應(yīng)用共享那樣需要回傳界面像素，而是交換事件消息。這樣，在一定程度上提高了協(xié)作的靈活性。但是，這些消息主要是一些用戶界面I/O消息（鍵盤和鼠標事件消息），需要大量的工作用于過濾、分解、翻譯和執(zhí)行這些底層消息，并隨著應(yīng)用背景的復(fù)雜化（例如達到商品化三維CAD系統(tǒng)的復(fù)雜程度）而急劇增加。這也可以解釋為何在上述非典型框架中總是給出一些簡單應(yīng)用程序例子如文本編輯和 Windows繪圖程序等。

由于復(fù)制式透明系統(tǒng)實現(xiàn)起來比集中式透明系統(tǒng)復(fù)雜和困難得多，故集中式透明系統(tǒng)成為透明系統(tǒng)的代表。就WYSIWIS、群體感知、網(wǎng)絡(luò)帶寬和協(xié)作任務(wù)等問題，Begole對透明系統(tǒng)和明確系統(tǒng)進行了比較。在Begole的比較中，典型的透明系統(tǒng)處于不利的地位。但是需要指出的是，Begole的比較并不公正，因為該比較實際進行的是集中式透明系統(tǒng)和復(fù)制式明確系統(tǒng)之間的比較。

（3）體系結(jié)構(gòu)。由于不同背景應(yīng)用系統(tǒng)的共享工作空間和用戶間的交互方式千差萬別，各種應(yīng)用系統(tǒng)的結(jié)構(gòu)也不相同，通?？梢詮捏w系結(jié)構(gòu)上加以綜述?，F(xiàn)有的CSCW系統(tǒng)通常采用三種體系結(jié)構(gòu)：集中式、復(fù)制式和混合式。

集中式結(jié)構(gòu)包括一個或多個集中式的服務(wù)器及多個與服務(wù)器交互的客戶端?？蛻舳酥饕糜趯崿F(xiàn)人機交互，即將用戶發(fā)出的操作命令轉(zhuǎn)換成服務(wù)器端系統(tǒng)可以理解并且執(zhí)行的形式。而服務(wù)器在執(zhí)行相應(yīng)的操作后，將處理結(jié)果以用戶可以認知的形式通過客戶端反饋給用戶。服務(wù)器控制和管理整個系統(tǒng)中的操作命令和操作對象。基于此種結(jié)構(gòu)，系統(tǒng)可以較為容易的實現(xiàn)數(shù)據(jù)對象的一致性維護，以及用戶界面視圖的同步，但是其會導(dǎo)致系統(tǒng)的容錯性較差，響應(yīng)性也不能得到保證。

復(fù)制式結(jié)構(gòu)本質(zhì)上指的是處于系統(tǒng)中的各個協(xié)作站點既是服務(wù)器，也是客戶端。各進程（站點）在地位上是對等的。它們都可以維護共享數(shù)據(jù)副本，也可以將用戶的操作轉(zhuǎn)化成事件后直接作用于它所維護的對象，同時將事件發(fā)送到相關(guān)其他站點。同集中式結(jié)構(gòu)相比，復(fù)制式結(jié)構(gòu)可以避免可靠性差以及響應(yīng)速度降低等缺點，但是系統(tǒng)復(fù)雜程度較高。例如由于很難保證所有事件都按同一順序到達其他進程（站點），因此很難保證各進程（站點）維護的目標對象的一致性。

混合式處于集中式和復(fù)制式之間，目的是繼承集中式和復(fù)制式的優(yōu)點。例如 PACT中的聯(lián)邦式體系結(jié)構(gòu)、CoDrawS 中的樹狀分布式結(jié)構(gòu)等。這種方式的優(yōu)缺點正好與應(yīng)用共享方式相反：新系統(tǒng)的設(shè)計和實現(xiàn)比較靈活，可以自由選擇所需的系統(tǒng)結(jié)構(gòu)、共享數(shù)據(jù)的結(jié)構(gòu)和分布結(jié)構(gòu)、并發(fā)控制策略、人人協(xié)作方式和交互界面。

三、操作轉(zhuǎn)換方法的構(gòu)建

操作轉(zhuǎn)換是明確復(fù)制式文本協(xié)同編輯的常用并發(fā)控制方法，其著眼于操作本身，試圖通過變換操作的參數(shù)來實現(xiàn)操作意愿維護，具有較好的響應(yīng)效果，但由于其與操作語義緊密相關(guān)，以及網(wǎng)絡(luò)傳輸延遲的不確定性，當(dāng)結(jié)點規(guī)模稍大時，操作之間的關(guān)系變得非常復(fù)雜，構(gòu)造轉(zhuǎn)換函數(shù)的難度較高。

設(shè)N代表系統(tǒng)中站點的個數(shù)，每個站點都有一個唯一的站點號i（1<=i<=N）來標識本站點。第j個站點的狀態(tài)向量是一個N元向量組，其中第i個分量值表示已有多少個來自站點i的操作被站點j執(zhí)行。對于任意兩個狀態(tài)向量 和 之間的關(guān)系，本文可以這樣定義：

（1）Si=Sj Si中每個分量的值都等于Sj中對應(yīng)分量的值。

（2）Si

（3）Si>Sj Si中至少有一個分量的值大于Sj中對應(yīng)分量的值。

請求是一個元組形式，i表示站點號，s表示發(fā)起操作o站點的狀態(tài)向量，p表示站點i的優(yōu)先級。

請求隊列：用來存放請求的隊列，在下列2種情況下將請求加入請求隊列中：

①本地站點從本地接收到一個請求；

②本地站點從網(wǎng)絡(luò)中接收到一個異地請求。

一旦請求被執(zhí)行，該請求就從請求隊列中移除。

執(zhí)行隊列：每個站點都保存著一個被執(zhí)行請求的日志，該日志按照插入的順序排列。

在程序的實現(xiàn)過程中，假設(shè)操作O是來自于站點S，狀態(tài)向量為SVO，在同時滿足以下兩個關(guān)系時才可以說O在站點d（d≠s）是滿足因果保持關(guān)系的：

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

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

第一個條件保證了O是站點S隊列中下一個要執(zhí)行的操作，因此站點S發(fā)出的操作不會被站點d遺漏；第二個條件保證了在其他站點產(chǎn)生的并且在操作O發(fā)出之前的操作已經(jīng)在站點S和站點d都已被執(zhí)行過了。這兩個關(guān)系保證了所有的在因果關(guān)系上先于O的操作已經(jīng)在站點d執(zhí)行過了?？梢钥吹揭粋€遠程操作的執(zhí)行如果同時滿足以上兩個條件，那么所有的操作都將按照它們的因果關(guān)系執(zhí)行，從而實現(xiàn)了一致性模型中因果保持約束這一屬性。

在操作轉(zhuǎn)換算法的實現(xiàn)中，任何兩條命令之間關(guān)系的判斷是該算法的核心部分，因此在該算法的實現(xiàn)過程中，本文是按照如下流程進行判斷的：

①接收到來自i的命令；

②比較站點i命令中狀態(tài)向量第i個分量和站點j命令中狀態(tài)向量第i個分量間是否滿足：SVi[i]=SVj[i]+1，并且SVi[k]

第一個條件應(yīng)使得站點i命令中狀態(tài)向量第i個分量等于站點j命令中狀態(tài)向量第i個分量值加1；

第二個條件應(yīng)使得站點i命令中狀態(tài)向量各個分量應(yīng)小于等于站點j命令中狀態(tài)向量各個分量值（除了第i個分量外）；

③若同時滿足上述兩個條件，就可以說Oj-> Oi；否則Oj||Oi。

本文以第i個站點作為對象來說明（ 表示第i個站點的請求隊列；Qi表示第i個站點的執(zhí)行隊列，Li表示第i個站點的狀態(tài)向量），具體算法流程如下

初始化：

Qi<-empty；

Li<-empty；

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

產(chǎn)生操作：

從本地用戶接收到一個命令；

Qi<-Qi+，將該命令傳播到其他站點。

接收命令：

從網(wǎng)絡(luò)中接收到命令；

Qi<-Qi+。

執(zhí)行命令：

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執(zhí)行操作Oj；

Li<-Li+

中對應(yīng)的第j個分量加1。

在初始化階段把請求隊列和執(zhí)行隊列置為空，各站點的狀態(tài)向量每個分量都置為0；該算法的關(guān)鍵在于執(zhí)行操作轉(zhuǎn)換：遍歷請求隊列，找到可能執(zhí)行的請求Rj=，Rj是否能夠執(zhí)行關(guān)鍵在于比較狀態(tài)向量Si和Sj的關(guān)系，有3種可能：

①Sj> Si

請求不能被執(zhí)行（操作Oj在站點j已經(jīng)執(zhí)行，但是在站點i還沒有執(zhí)行），因此該請求被放入Si的請求隊列中；

②Sj=Si

Oj不需要任何轉(zhuǎn)換馬上執(zhí)行；

③Sj

在這種情況下，請求可以執(zhí)行，但是因為Rj所指示的狀態(tài)向量是比站點i當(dāng)前更早的狀態(tài)向量，所以O(shè)j必須經(jīng)過轉(zhuǎn)換。

四、系統(tǒng)實現(xiàn)

首先將要測試的命令存入服務(wù)器站點上，各分站點連接服務(wù)器后，服務(wù)器將預(yù)存入的命令向各個對應(yīng)站點發(fā)送，各分站點接收到命令之后，經(jīng)解析后執(zhí)行，最后將執(zhí)行效果顯示在各個分站點的界面上。在程序中本文是以站點號來表示各個站點的優(yōu)先級的，站點號越大表示該站點所具有的優(yōu)先級別越高。為表示測試的一般性，在本例中測試的站點個數(shù)為3個，如圖1所示。

本文所開發(fā)的協(xié)同文本編輯系統(tǒng)建立在如下的開發(fā)環(huán)境上：操作系統(tǒng)平臺為Windows 7；網(wǎng)絡(luò)平臺為基于TCP/IP的Internet/Intranet網(wǎng)絡(luò)；網(wǎng)絡(luò)通訊協(xié)議為基于MFC的WinSocket 2.0通訊協(xié)議；VS 2010集成開發(fā)環(huán)境。

系統(tǒng)中所測試的命令均為8元組形式，例如1：000IA0，1表示站點號，000表示當(dāng)前站點的狀態(tài)向量，I表示插入操作，A表示插入的字符，0表示插入的參數(shù)位置。該命令表示接收到一號站點發(fā)來的在當(dāng)前文本第0個位置上插入字符A。

五、結(jié)論

協(xié)同文本編輯系統(tǒng)中一致性維護問題將是CSCW研究人員長期研究的課題。關(guān)于多用戶協(xié)同交互的基本方法需要進一步探索，協(xié)同文本編輯的原型系統(tǒng)需要進一步改進和完善。意圖不一致問題一直是困擾研究人員的難題，如何解決該問題將是未來潛心研究的核心課題。

參考文獻：

[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.

（作者單位：湖北大學(xué)計算機與信息工程學(xué)院）