高麗萍，徐曉芳

1(上海理工大學 光電信息與計算機工程學院，上海 200093) 2(復旦大學 上海市數據科學重點實驗室，上海 200093)

1 引 言

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

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

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

2 相關工作

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

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

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

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

3.1 基于CRDT的沖突解決

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

圖1 整體框架Fig.1 Overall framework

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

3.2 基本定義

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

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

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

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

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

圖形對象的唯一標識符由一個三元組組

1)s是會話的標識符

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

3)site是站點的唯一標識符

定義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.位置關系

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

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

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

定義7.沖突/相容關系

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

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

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

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

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

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

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

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

定義8.位置屬性約束關系

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

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

3.3 操作分類

3.3.1 基本操作

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

3.3.2 預定義關系操作

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

3.4 操作檢測

預定義操作沖突檢測

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

1)Oa||Ob

2)Oa、Ob∈Relate(Oa、Ob操作對象之間存在關聯關系)

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

3.5 CRDT算法

算法1介紹了如何解決基本操作之間的沖突.操作Oa是已經執(zhí)行過的操作，操作Ob是要執(zhí)行的遠程操作.有兩種情況需要考慮.當操作是同一種操作類型，則根據優(yōu)先級來決定執(zhí)行哪個操作，優(yōu)先級高的操作鏈接到雙鏈表中，優(yōu)先級低的操作不執(zhí)行，可見被設置為0，優(yōu)先級低的操作flag被設置為1.當操作是不同類型的操作時，我們規(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í)行的遠程操作.當兩個操作是兼容關系時，標識符較小的操作在標識符較高的操作之前執(zhí)行.與此同時，在雙鏈表中具有較大標識符的操作鏈接在具有較小標識符的操作之后.

算法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介紹了如何解決預定義操作之間的沖突.

算法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，有兩種情況需要考慮：首先，當Oa：pre_key為空并且在雙鏈表中沒有圖形操作存在時，Oa插入在雙鏈表的頭部.否則，操作插入在雙鏈表的最后一次圖形建模操作之后.第二種情況，當Oa.pre_key不為空時，需要找到剛剛在本地站點執(zhí)行的圖形建模操作(pre)，Oa連接在剛剛找到的Pre后面.然后，將Oa廣播到遠程站點.

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

算法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所示，站點1產生三個本地操作，分別是O1，O2，O3；站點2產生兩個本地操作，分別是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)

在站點1，本地操作O1生成，執(zhí)行O1，此時L1=O1.然后本地操作O2生成，執(zhí)行將O2加入到雙鏈表中，即L1=O1-O2.當O4到達時，O4跟O2有相同的文檔狀態(tài)，需要檢測他們之間的關系，因為是兼容關系，并且IDO2IDO4，執(zhí)行O4，在雙鏈表中把O4連接在O2之后，L1=O1-O2-O4.本地操作O3生成，O3的目標操作是O1，O2操作存在于O1后，因為O2和O3的狀態(tài)向量不同，IDO2IDO3 ，因此，將O3連接在O2之后，同理，O3連接在O4之后.執(zhí)行O3并將O3操作加入到雙鏈表中，此時L1=O1-O2-O4-O3.當O5到達站點1時，O5的目標對象是O1，O1后面有O2，O3，O4，因為O5跟O2和O3的狀態(tài)向量不同，連接在操作O4后面，O5的目標對象跟O3目標對象時相同的，并且狀態(tài)向量相同的，所以他們是基本類操作里面的沖突操作，因為IDO3IDO5，所以，O3操作撤銷，O5操作執(zhí)行.O3.visible=0同時將O5插入到雙聯表中，L1=O1-O2-O4-O3-O5.

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

最終，在兩個站點維護的雙鏈表分別為：L1=O1-O2-O4-O3-O5 L2=O1-O2-O4-O3-O5

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

第2階段：

如圖3所示展示第二階段的協(xié)同過程，在站點1生成一個本地操作06，站點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).

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

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

5 實驗分析

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

圖4 CRDT方法與COT方法比較Fig.4 ContrastofCRDTandCOT圖5 歷史操作數與站點數的對比圖Fig.5 Comparisonofhistoricaloperandsandnumberofsites

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

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

6 原型系統(tǒng)Intellij

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

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

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

7 總結與展望

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

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