高麗萍，徐曉芳

1(上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院，上海 200093) 2(復(fù)旦大學(xué) 上海市數(shù)據(jù)科學(xué)重點(diǎn)實(shí)驗(yàn)室，上海 200093)

1 引 言

實(shí)時協(xié)同編輯系統(tǒng)是一種廣泛使用的分布式計(jì)算機(jī)系統(tǒng)，它支持分布在不同地域的人通過網(wǎng)絡(luò)連接對同一個文檔(包括文本，圖形，視頻，音頻等)進(jìn)行查看，編輯.針對不同研究領(lǐng)域，協(xié)同的概念不盡相同，但總體思想均是在良好的互聯(lián)網(wǎng)環(huán)境下合作者們可以同時在不同地域在產(chǎn)生沖突的前提下完成同一項(xiàng)工作，從而幫助提高我們項(xiàng)目的開發(fā)效率、方便各個成員之間的交流、增強(qiáng)分布在不同地理位置上的操作人員的實(shí)時交互.計(jì)算機(jī)技術(shù)的飛速發(fā)展，人們對日常工作高效需求，促使協(xié)同技術(shù)不斷創(chuàng)新，大量的理論相關(guān)、技術(shù)支持被提出和采用.然而，越來越多的問題相繼產(chǎn)生，這就需要大批科研人員逐步去完善革新，使得僅發(fā)展十余年的CSCW學(xué)科才有了如今的成就.為創(chuàng)新者提供了充足的科研資料.

隨著大數(shù)據(jù)和云計(jì)算興起，實(shí)時圖形編輯系統(tǒng)更傾向于大規(guī)模的協(xié)作. 在大規(guī)模協(xié)作中，一個復(fù)雜的項(xiàng)目通常涉及數(shù)以百計(jì)的設(shè)計(jì)人員協(xié)作完成一項(xiàng)任務(wù). 在這種情況下，需要進(jìn)一步考慮兩個問題. 一個問題是大量的并發(fā)沖突將不可避免地發(fā)生，這給一致性維護(hù)帶來了更高的挑戰(zhàn). 另外一個問題，對于大量用戶同時編輯共享文檔的大規(guī)模協(xié)作[1]，共享文檔會經(jīng)常更新. 這種情況通常會導(dǎo)致協(xié)作計(jì)算性能的下降[2]. 如何提高計(jì)算性能是智能和大規(guī)模協(xié)作編輯系統(tǒng)成功的另一個挑戰(zhàn)，其一致性在大數(shù)據(jù)和云計(jì)算時代，維護(hù)和計(jì)算性能非常關(guān)鍵.

CRDT算法的主要思想是設(shè)計(jì)交換并發(fā)操作.因此，不再需要轉(zhuǎn)換，可以按照任何順序執(zhí)行并發(fā)操作.本文主要提出了一種用于智能和大規(guī)模協(xié)同圖形編輯系統(tǒng)的字符串CRDT算法，以解決新的挑戰(zhàn).最近，CRDT技術(shù)被提出作為一種新的協(xié)同文本編輯的并發(fā)控制機(jī)制. 已經(jīng)證明CRDT算法的性能優(yōu)于傳統(tǒng)方法，并且適用于大規(guī)模分布式環(huán)境[7]. 本文組織結(jié)構(gòu)如下：第二部分介紹了研究背景及相關(guān)工作；第三部分提出了在實(shí)時圖形編輯系統(tǒng)中基于CRDT的沖突解決方案；第四部分提出了一個協(xié)作設(shè)計(jì)的案例研究；第五部分給出了時間復(fù)雜度和空間復(fù)雜度分析；第六部分為了驗(yàn)證算法正確性與有效性，在windows系統(tǒng)中開發(fā)一個協(xié)同圖形編輯系統(tǒng)co-Drawing；第七部分給出結(jié)論和未來工作.

2 相關(guān)工作

在近幾年的研究中，OT(Operation Transforma-tion[12]最初設(shè)計(jì)用于支持多個用戶在復(fù)制的文本文檔中同時插入和刪除字符并始終如一.還有基于地址空間轉(zhuǎn)換(Address Space Transformation，AST)[4]技術(shù). OT的基本思想是根據(jù)已執(zhí)行的并發(fā)操作的效果，對先前文檔狀態(tài)定義的編輯操作進(jìn)行轉(zhuǎn)換，以使轉(zhuǎn)換后的操作能夠在當(dāng)前文檔狀態(tài)下達(dá)到正確的效果. 盡管其文本編輯起源于OT，但它獨(dú)立于文本文檔和文本編輯，并且已被用于支持一致性維護(hù)和用戶啟動的撤消，以協(xié)作編輯文本和圖形文檔[3].而基于AST的算法與OT的不同是從文檔狀態(tài)出發(fā)，將文檔的狀態(tài)地址空間回溯到操作產(chǎn)生時的狀態(tài)，在這樣的情況下，我們可以直接找到操作的執(zhí)行位置，從而維護(hù)文檔的一致性.但是，基于AST的技術(shù)不知處非線性結(jié)構(gòu)文檔一致性的維護(hù).并且，基于OT和地址空間轉(zhuǎn)換技術(shù)在實(shí)時群組編輯系統(tǒng)中執(zhí)行效率比較低.

在協(xié)同圖形編輯系統(tǒng)中，一致性維護(hù)多采用多版本機(jī)制來解決并發(fā)控制問題，例如：Chengzheng Sun等在文獻(xiàn)[4]中創(chuàng)新提出了云存儲操作轉(zhuǎn)換函數(shù)(Cloud Storage Op-eration Transformation，CSOT)，實(shí)現(xiàn)了云存儲系統(tǒng)中實(shí)時同步共享樹形文檔結(jié)構(gòu)的收斂性；Chengzheng Sun等在文獻(xiàn)[4]中提出了一種新的協(xié)作對象分組技術(shù)，稱CoGro-up，它基于操作轉(zhuǎn)換(OT)技術(shù)和TA[4].基于之前的工作，有人提出了一個優(yōu)化的版本，以最優(yōu)化解決對象版本的數(shù)量. Gao等[5，17]人在實(shí)時位圖系統(tǒng)中采用多版本策略來解決執(zhí)行和撤銷/重做一致性維護(hù)問題.還有根據(jù)TIP-S[14]算法進(jìn)行一系列的改變應(yīng)用在協(xié)同圖形編輯系統(tǒng)中.基于OT的這些方法在大規(guī)模數(shù)據(jù)下協(xié)同編輯群組編輯中并不能有很好的執(zhí)行效率.最近，CRDT(Commutative Repli-cated Data Type)被提議作為一種新的并發(fā)控制機(jī)制，以實(shí)現(xiàn)協(xié)作文本編輯的最終一致性.自文獻(xiàn)[6] 相關(guān)工作研究以來，已經(jīng)提出了一種具有代表性的CRDT算法，并將其應(yīng)用于協(xié)作文本編輯[7]HE等人在大規(guī)模協(xié)同編輯系統(tǒng)中提出過String-wise CRDT算法，解決了在智能和[7，10]大規(guī)模數(shù)據(jù)環(huán)境下的一致性維護(hù)，其正確性已經(jīng)得到驗(yàn)證.還有人將CRDT模型引入到實(shí)時協(xié)同CAD[10]系統(tǒng)中.在這兩篇文章中都突出了CRDT在大規(guī)模數(shù)據(jù)處理時的優(yōu)勢，效率更高，時間復(fù)雜度和空間復(fù)雜度都得到很好的優(yōu)化.在協(xié)同圖形編輯系統(tǒng)中，基于CRDT的研究很少，相比多版本機(jī)制，基于樹的各種機(jī)制，它有很大的優(yōu)勢.本文針對C/S架構(gòu)下圖形編輯系統(tǒng)中的實(shí)時性對CRDT算法做出了改進(jìn)，同時在系統(tǒng)設(shè)計(jì)時保證我們采用的工具協(xié)議等可以達(dá)到更好的實(shí)時性.

本文跟傳統(tǒng)的OT[15]算法相比，有很大優(yōu)勢.例如，以前將COT[13]算法改進(jìn)應(yīng)用到圖形編輯場景下，這種情況下，O的執(zhí)行條件是將DS與C(O)[12]中的操作對比，在C(O)中所有的操作將與O進(jìn)行操作轉(zhuǎn)換，那么在一次次操作傳輸過程中，DS和C(O)靠前的操作將會進(jìn)行一次次無用的比對，這浪費(fèi)了時間和傳輸開銷，本文提出的基于CRDT的算法根據(jù)唯一ID號找到操作對象直接進(jìn)行操作，尤其在刪除操作時大大提高效率.

3 實(shí)時圖形編輯系統(tǒng)中一致性維護(hù)

3.1 基于CRDT的沖突解決

在字符串[7]編輯方面的工作，我們擴(kuò)展和推進(jìn)了數(shù)據(jù)結(jié)構(gòu)，以便在實(shí)時圖形的Co-DRAWING系統(tǒng)中得到很好的使用.實(shí)時協(xié)作圖形編輯系統(tǒng)由大量的協(xié)作站點(diǎn)組成. 每個站點(diǎn)都維護(hù)CoRDG(即動態(tài)規(guī)則庫)，一個哈希表，一個雙鏈表和一個View交互視圖.CoRDG用于存儲預(yù)定義對象間的關(guān)聯(lián)關(guān)系. 哈希表存儲所有對象間的操作.雙鏈表按順序?qū)⑺袌D形操作(包括可見和不可見建模操作)從頭到尾鏈接起來.每個圖形對象操作都被視為雙鏈表的操作節(jié)點(diǎn).View可以為協(xié)作用戶提供交互界面.整個框架如圖1所示.

圖1 整體框架Fig.1 Overall framework

整個控制過程如圖1所示.協(xié)作設(shè)計(jì)人員同時在本地站點(diǎn)上創(chuàng)建、刪除、更新操作，并從其他站點(diǎn)接收遠(yuǎn)程圖形對象操作.當(dāng)一個本地操作產(chǎn)生時，本地操作立即執(zhí)行并且通過使用上次操作的標(biāo)識符，將操作直接鏈接在雙鏈表的最后一次操作之后.遠(yuǎn)程操作的集成過程包括兩個步驟.首先，遠(yuǎn)程操作需要在具有唯一標(biāo)識符的散列表中找到目標(biāo)圖像對象操作.其次，目標(biāo)圖形對象操作的位置需要在雙鏈表中找到.一些被執(zhí)行的操作可能存在于相同的目標(biāo)對象操作之后，當(dāng)存在沖突時，它們在CoRDG中的關(guān)聯(lián)關(guān)系的優(yōu)先級以及它們的標(biāo)識符需要被用來解決沖突，最后，集成更新的效果出現(xiàn)在交互視圖中.

3.2 基本定義

定義1.圖形對象操作(Oa)

在實(shí)時協(xié)同圖像編輯系統(tǒng)中，一個Oa由一個15元組t代表操作的類型；k表示圖形對象；(x，y)表示圖形對象中心對稱點(diǎn)在圖形文檔隱含坐標(biāo)系中的位置；l=tr-ue代表本地操作，l=flase代表遠(yuǎn)程操作；O(i)代表產(chǎn)生的圖形狀態(tài)關(guān)聯(lián)關(guān)系的集合，即CoRDG，其中O[k]=(i，j)，0≤k≤i；Obji表示圖形對象本身；visible=1代表有效操作；flag是一個集成變量，它的值為0或者1；c_key代表當(dāng)前操作的標(biāo)識符；pre_key代表前一個操作的標(biāo)識符；next是在雙鏈表中指向下一個操作的指針；pri-or是在雙鏈表中圖像操作的前驅(qū)；link是一個用在哈希表中的指針；s是圖形操作執(zhí)行的當(dāng)前狀態(tài).

定義2.(Oa)給定雙鏈表中任意兩個Oa和Ob，Oa的位置表示為pos(Oa)，Ob的位置表示為pos(Ob)，如果：pos(Oa)

基于以上定義，由于在雙鏈表中不同的目標(biāo)操作位置，我們可以在兩個圖形操作之間獲得Oa.然而，當(dāng)兩個并發(fā)圖形操作在雙鏈表中可能具有相同的操作位置.在這種情況下，我們不能在兩個圖形操作之間獲得Oa，所以我們有必要對它們進(jìn)行排序.因此，唯一的標(biāo)識符可以決定他們的順序.唯一的標(biāo)識符的定義如下.

定義3.標(biāo)識符(ID)[15]

圖形對象的唯一標(biāo)識符由一個三元組組

1)s是會話的標(biāo)識符

2)ssv是一個操作的狀態(tài)向量之和

3)site是站點(diǎn)的唯一標(biāo)識符

定義4.給定任意兩個圖形對象的操作Oa，Ob，兩個操作的ID分別是IDOa IDOb

1)如果IDOa[s]

2)如果IDOa[s]=IDOb[s]，IDOa[ssv]

3)如果IDOa[s]=IDOb[s]，IDOa[ssv]=IDOb[ssv]， IDOa[ssv]=IDOb[ssv]，IDOa[site]

定義5.位置關(guān)系

為了確保最終的一致性，我們需要確保在所有站點(diǎn)中執(zhí)行了所有操作時，雙鏈表中的所有建模操作在每個站點(diǎn)中具有相同的總排序. 以下給出了所有建模操作的總排序關(guān)系的定義.

定義6.操作的總排序關(guān)系(O?)

給定任何三個操作，O1，O2和O3，如果：(1)O1

定義7.沖突/相容關(guān)系

假設(shè)給定兩個操作Oa和Ob，Oa||Ob且Oa和Ob操作的目標(biāo)圖形對象標(biāo)識相同，有如表1所示的關(guān)系[13].

表1 圖形對象間的沖突/相容關(guān)系Table 1 Conflict/compatibility between graphical objects

在實(shí)時協(xié)作文本編輯中，最終一致性和意向保存是CRDT算法的兩個重要的正確性標(biāo)準(zhǔn). 因此，在協(xié)同文本編輯中的正確性標(biāo)準(zhǔn)之后，如果遵守以下標(biāo)準(zhǔn)，則認(rèn)為實(shí)時Co-Drawing系統(tǒng)是正確的：

最終一致性：所有圖形操作都在所有站點(diǎn)中執(zhí)行完畢后，來自不同站點(diǎn)的所有操作圖形都是相同的.

意向保存：需要在所有站點(diǎn)保存圖形并發(fā)操作的綜合效果. 此外，我們的研究工作需要考慮兩種種情況：

1)為了兼容操作，需要保留所有兼容操作的效果.

2)對于沖突操作，盡可能保留沖突操作的影響，必要時只需要保留沖突操作的一個效果，根據(jù)動態(tài)規(guī)則庫保留操作語義的一致性.

與協(xié)同文本編輯不同，在基于圖形對象操作的Co-RDG系統(tǒng)中，操作之間之間存在復(fù)雜關(guān)系，不同設(shè)計(jì)者之間的操作不可避免地存在沖突. 在這種情況下，由于操作沖突可能導(dǎo)致某些圖形對象操作無法執(zhí)行，最終導(dǎo)致整個繪圖任務(wù)無法完成. 因此，需要沖突解決方法來保持更多的設(shè)計(jì)意圖并保持最終的一致性. 考慮到圖形操作的復(fù)雜性，為了維護(hù)最終的一致性，本文將操作分為基本操作和預(yù)定義關(guān)系操作兩種.

定義8.位置屬性約束關(guān)系

如果兩個不同的圖形對象存在一種或多種特殊的位置關(guān)聯(lián)關(guān)系，這樣的圖形對象之間的關(guān)系，我們定義為位置屬性約束關(guān)系.對這些圖形對象的任何一個對象進(jìn)行操作，都要先檢測他們之間的約束關(guān)聯(lián)關(guān)系.位置關(guān)聯(lián)關(guān)系定義我們參考許[15]等人的研究.

O(i)是用戶根據(jù)實(shí)際的設(shè)計(jì)的需求，動態(tài)的將圖形對象間的各種復(fù)雜的關(guān)聯(lián)關(guān)系添加到動態(tài)規(guī)則庫里，系統(tǒng)會及時通過廣播傳送給其他站點(diǎn)，使各個站點(diǎn)的語義沖突規(guī)則庫都保持最新的狀態(tài).

3.3 操作分類

3.3.1 基本操作

本文設(shè)計(jì)的協(xié)同圖形編輯系統(tǒng)中，有N操作(New)，D操作(Delete)以及U操作(Update)三種基本類型操作.

3.3.2 預(yù)定義關(guān)系操作

在實(shí)際的工程繪圖設(shè)計(jì)過程中，用戶可能根據(jù)自己的意愿或者實(shí)際的現(xiàn)實(shí)需求，預(yù)先給圖像對象間定義某些特殊的約束規(guī)則.在這樣的情況下，多人同時編輯這些圖形對象，執(zhí)行結(jié)束后，可能就會違背之前定義的約束條件，從而造成語義不一致的問題.本文只討論，圖形對象之間位置上的關(guān)聯(lián)關(guān)系并且預(yù)定義關(guān)系一般指兩個操作作用在不同的對象之間.

3.4 操作檢測

預(yù)定義操作沖突檢測

預(yù)定義并發(fā)沖突操作

1)Oa||Ob

2)Oa、Ob∈Relate(Oa、Ob操作對象之間存在關(guān)聯(lián)關(guān)系)

3)Oa、Ob Rule?Oa、Ob在執(zhí)行后違背了Rule定義的規(guī)則)那么，Oa和Ob是并發(fā)沖突操作預(yù)定義并發(fā)兼容操作 如果操作Oa和Ob不是并發(fā)沖突操作，則Oa和Ob是兼容操作.

3.5 CRDT算法

算法1介紹了如何解決基本操作之間的沖突.操作Oa是已經(jīng)執(zhí)行過的操作，操作Ob是要執(zhí)行的遠(yuǎn)程操作.有兩種情況需要考慮.當(dāng)操作是同一種操作類型，則根據(jù)優(yōu)先級來決定執(zhí)行哪個操作，優(yōu)先級高的操作鏈接到雙鏈表中，優(yōu)先級低的操作不執(zhí)行，可見被設(shè)置為0，優(yōu)先級低的操作flag被設(shè)置為1.當(dāng)操作是不同類型的操作時，我們規(guī)定D操作的優(yōu)先級大于U操作的優(yōu)先級.

算法1.ConflictResolve

INPUT：Oa?Ob

Int flag=0

If T(Oa)=T(Ob)=operate.Delete‖

T(Oa)=T(Ob)=Operate.Update& K(Oa)≠K(Ob)‖

Ob is not execute，Ob.visible=0，flag=1

If Oa.next=null then

Oa.next=Ob，Ob.prior=Oa

Else

Ob.next=Oa.next，Oa.next.prior=Ob ，

Oa.next=Ob，Ob.prior=Oa

End if

Else

If T(Oa)=Operate.Update & T(Ob)=Operate.Delete then

Oa is undone，Ob is execute

Oa.prior.next=Ob，Ob.prior=Oa.prior，Ob.next=Oa，

Oa.prior=Ob，Oa.visible=0

Else T(Oa)=Operate.Delete & T(Ob)=Operate.Update

Ob is not execute，Ob.visible=0，flag=1

Ob.next=Oa.next，Oa.next.prior=Ob

Oa.next=Ob，Ob.prior=Oa

End if

End if

Output：flag

算法2介紹了如何解決基本操作之間的兼容操作.操作Oa是執(zhí)行操作，操作Ob是要執(zhí)行的遠(yuǎn)程操作.當(dāng)兩個操作是兼容關(guān)系時，標(biāo)識符較小的操作在標(biāo)識符較高的操作之前執(zhí)行.與此同時，在雙鏈表中具有較大標(biāo)識符的操作鏈接在具有較小標(biāo)識符的操作之后.

算法2.CompatibleResolve

INPUT：Oa⊙Ob

Ob is execute

If Oa.next=NULL then

Oa.next=Ob，Ob.prior=Oa

Else

Ob.next=Oa.next，Oa.next.prior=Ob ，

Oa.next=Ob，Ob.prior=Oa

End if

Else

Oa is undone，Ob is execute，Oa is redo

Oa.prior.next=Ob，Ob.prior=Oa.prior，

Ob.next=Oa，Oa.prior=Ob，Oa.visible=0

End if

算法3介紹了如何解決預(yù)定義操作之間的沖突.

算法3.Predefined conflict resolution

INPUT Oa?Ob

Int flag=0

IF Oa、Ob∈R elate & Oa、Ob? Rule then

Ob is execute

Ob is not execute，Ob.visible=0，flag=1

Oa.next=Ob，Ob.prior= Oa

Else

Oa is undo，Ob is executed

Oa.prior.next=Ob，Ob.prior=Oa.prior

Ob.next=Oa，Oa.prior=Ob，Oa.visible=0

End if

End if

OUTPUT：flag

算法4該算法給出了本地操作Oa，有兩種情況需要考慮：首先，當(dāng)Oa：pre_key為空并且在雙鏈表中沒有圖形操作存在時，Oa插入在雙鏈表的頭部.否則，操作插入在雙鏈表的最后一次圖形建模操作之后.第二種情況，當(dāng)Oa.pre_key不為空時，需要找到剛剛在本地站點(diǎn)執(zhí)行的圖形建模操作(pre)，Oa連接在剛剛找到的Pre后面.然后，將Oa廣播到遠(yuǎn)程站點(diǎn).

算法4.IntergrateRemote(Oa)

INPUT ：Oa

If Oa.pre_key==null then

If head.next!=null then

CT=head.next

While CT!=null do

CT=CT.next

While CT!=NULL do

NT=NT.next

End While

Oa is double linked after CT.prior

Else

Oa is double linked next to head

End if

Else

pre=hash(Oa.pre_key)

Oa is double linked after tar

End if

Oa is broadcast to remote site

算法5給出了遠(yuǎn)程操作Oa 當(dāng)遠(yuǎn)程操作廣播過來后，圖形的目標(biāo)操作可以使用唯一標(biāo)識符直接找到.找到當(dāng)前會話中的第一個建模操作，然后判斷遠(yuǎn)程操作跟目標(biāo)操作是否作用于同一目標(biāo)對象，有兩種情況：一是作用于同一目標(biāo)對象，根據(jù)基本類操作的沖突操作判斷是否是沖突操作，在相同文檔狀態(tài)下，若是沖突操作，調(diào)用CompatibleResolve算法，若是兼容操作，則調(diào)用 CompatibleResolve；在不同文檔狀態(tài)下，根據(jù)兩個操作的優(yōu)先級來決定執(zhí)行順序及目標(biāo)操作的位置；二是兩個操作的對象目標(biāo)不一致，此時要先去動態(tài)規(guī)則庫查詢兩個圖形對象間是否有空間位置關(guān)聯(lián)關(guān)系.在相同文檔狀態(tài)下，存在空間位置關(guān)聯(lián)關(guān)系，根據(jù)預(yù)定義的關(guān)聯(lián)關(guān)系，進(jìn)一步需要判斷是不是違反約束規(guī)則，若是違反規(guī)則，則調(diào)用Predefined conflict resolution；若不違反規(guī)則，則調(diào)用CompatibleResolve.在不同的文檔狀態(tài)下，根據(jù)優(yōu)先級來決定執(zhí)行順序及目標(biāo)操作在雙鏈表中的位置.

算法5.IntergrateRemote(Oa)

INPUT：Oa

Tar=hash(Oa.t_key[Obji])

If CT==null then

Oa is double linked after Tar

Else

CT=CT.next

End while

if Oa(Obja)==Ob(Objb)‖CT，Oa?Relate-Rule then

While CT!=null&&ID(CT)ID(Oa) do

If CT.s==Oa.s then

If(CT，Oa)==CT?Oa then

ifOa(Obja)==Ob(Objb) then

Flag=ConflicResolve(CT?Oa)

Else

Flag=PreConflicResolve

Break

Else

CT=CT.next

Else

Undo CT，execute Oa，redo CT

Oa is double linked before CT，break

End if

End if

Else

CT=CT.next，continue

Else

Undo CT，execute Oa ，redo CT

Oa is double linked before CT，break

End if

End while

If CT==null then

Execute Oa and double link Oa after CT.prior

End if

If CT.s==Oa.s then

If (CT，Oa)==CT?Oa then

Flag=ConflicResolve(CT?Oa)

Else

CompatibleResolve(CT

End if

Else

Oa is execute double linked before CT

End if

End if

4 案例分析

圖2 第一次協(xié)作過程Fig.2 First collaborative process

第1階段：

如圖2所示，站點(diǎn)1產(chǎn)生三個本地操作，分別是O1，O2，O3；站點(diǎn)2產(chǎn)生兩個本地操作，分別是O4，O5.所有操作的狀態(tài)向量分別是：SV(01)=(1，0)，SV(02)=(2，0)，SV(03)=(3，1)，SV(04)=(1，1)，SV(05)=(2，2).所有操作的ID號為：IDO1=(1，1，1)，IDO2=(1，2，1)，IDO3=(1，4，1)，IDO4=(1，2，2)，IDO5=(1，4，2)

在站點(diǎn)1，本地操作O1生成，執(zhí)行O1，此時L1=O1.然后本地操作O2生成，執(zhí)行將O2加入到雙鏈表中，即L1=O1-O2.當(dāng)O4到達(dá)時，O4跟O2有相同的文檔狀態(tài)，需要檢測他們之間的關(guān)系，因?yàn)槭羌嫒蓐P(guān)系，并且IDO2IDO4，執(zhí)行O4，在雙鏈表中把O4連接在O2之后，L1=O1-O2-O4.本地操作O3生成，O3的目標(biāo)操作是O1，O2操作存在于O1后，因?yàn)镺2和O3的狀態(tài)向量不同，IDO2IDO3 ，因此，將O3連接在O2之后，同理，O3連接在O4之后.執(zhí)行O3并將O3操作加入到雙鏈表中，此時L1=O1-O2-O4-O3.當(dāng)O5到達(dá)站點(diǎn)1時，O5的目標(biāo)對象是O1，O1后面有O2，O3，O4，因?yàn)镺5跟O2和O3的狀態(tài)向量不同，連接在操作O4后面，O5的目標(biāo)對象跟O3目標(biāo)對象時相同的，并且狀態(tài)向量相同的，所以他們是基本類操作里面的沖突操作，因?yàn)镮DO3IDO5，所以，O3操作撤銷，O5操作執(zhí)行.O3.visible=0同時將O5插入到雙聯(lián)表中，L1=O1-O2-O4-O3-O5.

在站點(diǎn)2，O1操作到達(dá)，L2=O1.操作O4生成，執(zhí)行O4并將其加入雙鏈表中，L2=O1-O4.O2操作到達(dá)，因?yàn)镺4和O2具有相同的文檔狀態(tài)，但是O2和O4目標(biāo)對象不同，因此是兼容關(guān)系，同時IDO2IDO4.所以執(zhí)行O2，在雙鏈表中把操作O2放到操作O4之前，L2=O1-O2-O4.O5生成，執(zhí)行O5，O5的目標(biāo)對象是O1，直接將O5插入到雙鏈表中O1之后，O5跟O2和O4狀態(tài)向量不同，在雙鏈表中將O5連接在O4之后，L2=O1-O2-O4-O5.當(dāng)O3操作到達(dá)，O3操作的目標(biāo)對象是O1，操作O2，O4，O5在操作O1之后，并且O5跟O3具有相同的狀態(tài)向量，因此O5跟O3的關(guān)系需要檢測，是沖突操作，因?yàn)镮DO3IDO5.因此，O3不需要執(zhí)行，O3.visible=0，在雙鏈表中不可見的操作O3連接在操作O5之前.此時，L2=O1-O2-O4-O3-O5.

最終，在兩個站點(diǎn)維護(hù)的雙鏈表分別為：L1=O1-O2-O4-O3-O5 L2=O1-O2-O4-O3-O5

圖3 第二次協(xié)作過程Fig.3 Second collaboration process

第2階段：

如圖3所示展示第二階段的協(xié)同過程，在站點(diǎn)1生成一個本地操作06，站點(diǎn)2生成一個本地操作07，所有操作的狀態(tài)向量分別是：SV(O6)=(4，2)，SV(O7)=(3，3)，Relat-ion(line1，circular1，1，describe)，Describe(line1不高于circular1)，Rule：(1，y1-pos”<=”)所有操作的ID號為：IDO6=(2，6，1) ，IDO7=(2，6，2).

在站點(diǎn)1，本地操作O6生成，L1=O1-O2-O4-O3-O5-O6，當(dāng)O7操作到達(dá)，O7的目標(biāo)對象是操作02，在操作O2后面有O4-O3-O5-O6，因?yàn)椴豢梢姴僮鱋3和操作O4，O5，不是當(dāng)前協(xié)同會話過程中，所以跳過.操作O6在當(dāng)前會話過程中，因?yàn)椴僮鱋6和O7作用在不同的操作對象中，用動態(tài)規(guī)則庫(CoRDG)檢查兩個操作是否違反Rule，檢查違反了預(yù)定義關(guān)系，根據(jù)優(yōu)先級，撤銷O6，在雙鏈表中加入操作O7.O6.visible=0，O7連接在雙鏈表之前. L1=O1-O2-O4-O3-O5-O7-O6.

站點(diǎn)2，本地操作O7生成，L= L1=O1-O2-O4-O3-O5-O7.當(dāng)操作O6到達(dá)，O6的目標(biāo)對象是操作O4，在操作O4后面有O3-O5-O7.跳過不可見操作O3和操作O5.因?yàn)镺6和O7具有相同的文檔狀態(tài)，因?yàn)镺7比O6具有更高的優(yōu)先級.所以，O6不執(zhí)行，O6.visible=0，在雙鏈表中O6連接在07后面.L2= L1=O1-O2-O4-O3-O5-O7-O6.最終，在兩個站點(diǎn)維護(hù)的雙鏈表分別為：L1=O1-O2-O4-O3-O5-O7-O6L2=O1-O2-O4-O3-O5-O7-O6.

5 實(shí)驗(yàn)分析

在本小節(jié)中，我們將對我們的方法進(jìn)行實(shí)驗(yàn)，以驗(yàn)證算法的有效性.我們用Intellij IDEA作為實(shí)驗(yàn)平臺，用JAVA語言實(shí)現(xiàn)，模擬測試仿真原型系統(tǒng)，并且由Windows 7系統(tǒng)，Intel Core i7，3.30 GHz CPU上的Visual Studio 2010編譯.然而，在協(xié)作編輯中沒有可用的公共數(shù)據(jù)集，性能評估通常基于操作日志由協(xié)作產(chǎn)生.我們設(shè)計(jì)實(shí)時協(xié)作以獲取操作日志.然后，重播兩種算法的所有操作.每個站點(diǎn)執(zhí)行所有本地操作和遠(yuǎn)程操作后，將繼續(xù)執(zhí)行相同的過程.我們在每個操作日志中運(yùn)行次30次算法，并記錄平均值.

圖4 CRDT方法與COT方法比較Fig.4 ContrastofCRDTandCOT圖5 歷史操作數(shù)與站點(diǎn)數(shù)的對比圖Fig.5 Comparisonofhistoricaloperandsandnumberofsites

在本節(jié)中，將我們的方法與文獻(xiàn)[11]傳統(tǒng)COT算法的計(jì)算時間進(jìn)行比較. 首先，研究了我們的方法和COT算法將遠(yuǎn)程圖形操作集成到操作歷史H中需要多長時間.其次，研究了我們的方法和COT的圖形操作的平均計(jì)算時間.圖5顯示了COT和我們的方法遠(yuǎn)程操作的計(jì)算時間. 如圖5所示，隨著操作歷史的長度增加和遠(yuǎn)程操作的數(shù)量增加，COT比我們的方法需要更多的時間. 尤其是，當(dāng)操作歷史的長度為200時，COT需要64 ms來集成100個遠(yuǎn)程操作，而我們的方法僅需5 ms來集成100個遠(yuǎn)程操作. 圖4顯示了COT與我們的方法的基于圖形的操作的平均計(jì)算時間，其中刪除比率被設(shè)置為20%并且遠(yuǎn)程操作的數(shù)量隨著歷史操作數(shù)而增加.

如圖5所示，COT需要更多時間來整合刪除操作，但我們的方法需要更少的時間. 主要原因是有沖突時，每個COT算法在集成遠(yuǎn)程操作時，P2P環(huán)境下的COT每次傳輸都要附帶一個C(O)的文檔狀態(tài)文本，當(dāng)協(xié)同工作時間過長或操作過多時，這個C(O)就會變得很龐大，每次沖突都要從歷史操作序列開頭進(jìn)行一一對比. 例如，當(dāng)遠(yuǎn)程操作的數(shù)量是400，刪除率是20%時，我們的刪除操作能根據(jù)目標(biāo)對象唯一的ID號直接進(jìn)行刪除操作.

6 原型系統(tǒng)Intellij

為了驗(yàn)證大規(guī)模數(shù)據(jù)下實(shí)時圖形編輯系統(tǒng)中，算法的正確性與可行性，本文開發(fā)了一個基于Intellij IDEA平臺實(shí)時圖形編輯系統(tǒng)CO-DRAWING.客戶端：采用[19]webSocket協(xié)議實(shí)現(xiàn)實(shí)時圖形編輯系統(tǒng)CO-DRAWING.WebSocket協(xié)議可以實(shí)現(xiàn)持久連接的全雙工雙向通信，應(yīng)用WebSocke 結(jié)合WSS協(xié)議達(dá)成多人實(shí)時異地協(xié)同設(shè)計(jì)的目標(biāo).服務(wù)器端：系統(tǒng)采用SSM(SpringMVC+Spring+Mybatis)框架來搭建的一個web系統(tǒng)，通過Intellij IDEA平臺，部署到到tomcat上來實(shí)現(xiàn)訪問，同時為了體現(xiàn)大規(guī)模數(shù)據(jù)的特性，采用Docker技術(shù)在一臺物理計(jì)算機(jī)上運(yùn)行3個服務(wù)端程序.

圖6 算法原型系統(tǒng)Fig.6 Algorithm prototype system

多人同時編輯如圖6所示，上方是為選擇創(chuàng)建各種圖像(三角形，線條，矩形)，清空畫布等功能：屏幕右下方中間部分為協(xié)同用戶界面；屏幕右下方下面部分為圖形對象ID號；系統(tǒng)分為基本操作維護(hù)和語義沖突維護(hù).其中語義操作維護(hù)根據(jù)動態(tài)規(guī)則庫來進(jìn)行管理.

7 總結(jié)與展望

本文提出了一種新穎優(yōu)化的CRDT算法，該算法主要應(yīng)用于大數(shù)據(jù)時的智能和大規(guī)模協(xié)作的實(shí)時圖形編輯系統(tǒng)中. 該新穎算法可以保留操作的意圖并通過預(yù)定義圖形對象之間的關(guān)聯(lián)關(guān)系和位置屬性約束規(guī)則，設(shè)計(jì)本地操作和遠(yuǎn)程操作的實(shí)現(xiàn)算法，使個站點(diǎn)的語義維護(hù)得到有效的保證.并且通過理論分析和實(shí)驗(yàn)評估表明，該算法的計(jì)算性能大大優(yōu)于現(xiàn)有的OT算法和AST算法. 因此，與現(xiàn)有算法相比，該算法更適合于智能和大規(guī)模協(xié)作應(yīng)用.

在未來的研究中，我們計(jì)劃繼續(xù)探索以下幾個方面. 首先，圖形編輯系統(tǒng)中的Undo/Redo是很重要的操作，下一步將重點(diǎn)探索這個方面. 其次，我們將把圖形對象中的其他操作合理地加入進(jìn)來，圖形之間的預(yù)定義操作不僅只有這一種，還有很多復(fù)雜的關(guān)聯(lián)操作需要考慮.第三，嘗試將我們的方法應(yīng)用于現(xiàn)實(shí)生活中的協(xié)作應(yīng)用程序. 例如，Google Drive，Codoxware，SubEthaEdit，Novell Vibe等基于云的協(xié)作服務(wù)近年來越來越流行. 這些協(xié)作應(yīng)用程序需要通過在合作者之間交換意圖，想法，知識和智慧來共同創(chuàng)作共享文檔，從而提高效率和質(zhì)量. 所提出的算法與要求非常匹配，并將在未來應(yīng)用于這些領(lǐng)域.第四，我們將探討如何使用多核CPU /多核GPU加速大規(guī)模協(xié)作應(yīng)用[9,10].