大規模實時圖形編輯中可交換復制數據模型一致性維護
2019-07-09 11:43:48高麗萍徐曉芳
小型微型計算機系統 2019年7期
高麗萍，徐曉芳
1(上海理工大學 光電信息與計算機工程學院，上海 200093) 2(復旦大學 上海市數據科學重點實驗室，上海 200093)
1 引 言
實時協同編輯系統是一種廣泛使用的分布式計算機系統，它支持分布在不同地域的人通過網絡連接對同一個文檔(包括文本，圖形，視頻，音頻等)進行查看，編輯.針對不同研究領域，協同的概念不盡相同，但總體思想均是在良好的互聯網環境下合作者們可以同時在不同地域在產生沖突的前提下完成同一項工作，從而幫助提高我們項目的開發效率、方便各個成員之間的交流、增強分布在不同地理位置上的操作人員的實時交互.計算機技術的飛速發展，人們對日常工作高效需求，促使協同技術不斷創新，大量的理論相關、技術支持被提出和采用.然而，越來越多的問題相繼產生，這就需要大批科研人員逐步去完善革新，使得僅發展十余年的CSCW學科才有了如今的成就.為創新者提供了充足的科研資料.
隨著大數據和云計算興起，實時圖形編輯系統更傾向于大規模的協作. 在大規模協作中，一個復雜的項目通常涉及數以百計的設計人員協作完成一項任務. 在這種情況下，需要進一步考慮兩個問題. 一個問題是大量的并發沖突將不可避免地發生，這給一致性維護帶來了更高的挑戰. 另外一個問題，對于大量用戶同時編輯共享文檔的大規模協作[1]，共享文檔會經常更新. 這種情況通常會導致協作計算性能的下降[2]. 如何提高計算性能是智能和大規模協作編輯系統成功的另一個挑戰，其一致性在大數據和云計算時代，維護和計算性能非常關鍵.
CRDT算法的主要思想是設計交換并發操作.因此，不再需要轉換，可以按照任何順序執行并發操作.本文主要提出了一種用于智能和大規模協同圖形編輯系統的字符串CRDT算法，以解決新的挑戰.最近，CRDT技術被提出作為一種新的協同文本編輯的并發控制機制. 已經證明CRDT算法的性能優于傳統方法，并且適用于大規模分布式環境[7]. 本文組織結構如下：第二部分介紹了研究背景及相關工作；第三部分提出了在實時圖形編輯系統中基于CRDT的沖突解決方案；第四部分提出了一個協作設計的案例研究；第五部分給出了時間復雜度和空間復雜度分析；第六部分為了驗證算法正確性與有效性，在windows系統中開發一個協同圖形編輯系統co-Drawing；第七部分給出結論和未來工作.
2 相關工作
在近幾年的研究中，OT(Operation Transforma-tion[12]最初設計用于支持多個用戶在復制的文本文檔中同時插入和刪除字符并始終如一.還有基于地址空間轉換(Address Space Transformation，AST)[4]技術. OT的基本思想是根據已執行的并發操作的效果，對先前文檔狀態定義的編輯操作進行轉換，以使轉換后的操作能夠在當前文檔狀態下達到正確的效果. 盡管其文本編輯起源于OT，但它獨立于文本文檔和文本編輯，并且已被用于支持一致性維護和用戶啟動的撤消，以協作編輯文本和圖形文檔[3].而基于AST的算法與OT的不同是從文檔狀態出發，將文檔的狀態地址空間回溯到操作產生時的狀態，在這樣的情況下，我們可以直接找到操作的執行位置，從而維護文檔的一致性.但是，基于AST的技術不知處非線性結構文檔一致性的維護.并且，基于OT和地址空間轉換技術在實時群組編輯系統中執行效率比較低.
在協同圖形編輯系統中，一致性維護多采用多版本機制來解決并發控制問題，例如：Chengzheng Sun等在文獻[4]中創新提出了云存儲操作轉換函數(Cloud Storage Op-eration Transformation，CSOT)，實現了云存儲系統中實時同步共享樹形文檔結構的收斂性；Chengzheng Sun等在文獻[4]中提出了一種新的協作對象分組技術，稱CoGro-up，它基于操作轉換(OT)技術和TA[4].基于之前的工作，有人提出了一個優化的版本，以最優化解決對象版本的數量. Gao等[5，17]人在實時位圖系統中采用多版本策略來解決執行和撤銷/重做一致性維護問題.還有根據TIP-S[14]算法進行一系列的改變應用在協同圖形編輯系統中.基于OT的這些方法在大規模數據下協同編輯群組編輯中并不能有很好的執行效率.最近，CRDT(Commutative Repli-cated Data Type)被提議作為一種新的并發控制機制，以實現協作文本編輯的最終一致性.自文獻[6] 相關工作研究以來，已經提出了一種具有代表性的CRDT算法，并將其應用于協作文本編輯[7]HE等人在大規模協同編輯系統中提出過String-wise CRDT算法，解決了在智能和[7，10]大規模數據環境下的一致性維護，其正確性已經得到驗證.還有人將CRDT模型引入到實時協同CAD[10]系統中.在這兩篇文章中都突出了CRDT在大規模數據處理時的優勢，效率更高，時間復雜度和空間復雜度都得到很好的優化.在協同圖形編輯系統中，基于CRDT的研究很少，相比多版本機制，基于樹的各種機制，它有很大的優勢.本文針對C/S架構下圖形編輯系統中的實時性對CRDT算法做出了改進，同時在系統設計時保證我們采用的工具協議等可以達到更好的實時性.
本文跟傳統的OT[15]算法相比，有很大優勢.例如，以前將COT[13]算法改進應用到圖形編輯場景下，這種情況下，O的執行條件是將DS與C(O)[12]中的操作對比，在C(O)中所有的操作將與O進行操作轉換，那么在一次次操作傳輸過程中，DS和C(O)靠前的操作將會進行一次次無用的比對，這浪費了時間和傳輸開銷，本文提出的基于CRDT的算法根據唯一ID號找到操作對象直接進行操作，尤其在刪除操作時大大提高效率.
3 實時圖形編輯系統中一致性維護
3.1 基于CRDT的沖突解決
在字符串[7]編輯方面的工作，我們擴展和推進了數據結構，以便在實時圖形的Co-DRAWING系統中得到很好的使用.實時協作圖形編輯系統由大量的協作站點組成. 每個站點都維護CoRDG(即動態規則庫)，一個哈希表，一個雙鏈表和一個View交互視圖.CoRDG用于存儲預定義對象間的關聯關系. 哈希表存儲所有對象間的操作.雙鏈表按順序將所有圖形操作(包括可見和不可見建模操作)從頭到尾鏈接起來.每個圖形對象操作都被視為雙鏈表的操作節點.View可以為協作用戶提供交互界面.整個框架如圖1所示.
圖1 整體框架Fig.1 Overall framework
整個控制過程如圖1所示.協作設計人員同時在本地站點上創建、刪除、更新操作，并從其他站點接收遠程圖形對象操作.當一個本地操作產生時，本地操作立即執行并且通過使用上次操作的標識符，將操作直接鏈接在雙鏈表的最后一次操作之后.遠程操作的集成過程包括兩個步驟.首先，遠程操作需要在具有唯一標識符的散列表中找到目標圖像對象操作.其次，目標圖形對象操作的位置需要在雙鏈表中找到.一些被執行的操作可能存在于相同的目標對象操作之后，當存在沖突時，它們在CoRDG中的關聯關系的優先級以及它們的標識符需要被用來解決沖突，最后，集成更新的效果出現在交互視圖中.
3.2 基本定義
定義1.圖形對象操作(Oa)
在實時協同圖像編輯系統中，一個Oa由一個15元組
定義2.(Oa)給定雙鏈表中任意兩個Oa和Ob，Oa的位置表示為pos(Oa)，Ob的位置表示為pos(Ob)，如果：pos(Oa) 基于以上定義，由于在雙鏈表中不同的目標操作位置，我們可以在兩個圖形操作之間獲得Oa.然而，當兩個并發圖形操作在雙鏈表中可能具有相同的操作位置.在這種情況下，我們不能在兩個圖形操作之間獲得Oa，所以我們有必要對它們進行排序.因此，唯一的標識符可以決定他們的順序.唯一的標識符的定義如下. 定義3.標識符(ID)[15] 圖形對象的唯一標識符由一個三元組組 1)s是會話的標識符 2)ssv是一個操作的狀態向量之和 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.位置關系 為了確保最終的一致性，我們需要確保在所有站點中執行了所有操作時，雙鏈表中的所有建模操作在每個站點中具有相同的總排序. 以下給出了所有建模操作的總排序關系的定義. 定義6.操作的總排序關系(O?) 給定任何三個操作，O1，O2和O3，如果：(1)O1 定義7.沖突/相容關系 假設給定兩個操作Oa和Ob，Oa||Ob且Oa和Ob操作的目標圖形對象標識相同，有如表1所示的關系[13]. 表1 圖形對象間的沖突/相容關系Table 1 Conflict/compatibility between graphical objects 在實時協作文本編輯中，最終一致性和意向保存是CRDT算法的兩個重要的正確性標準. 因此，在協同文本編輯中的正確性標準之后，如果遵守以下標準，則認為實時Co-Drawing系統是正確的： 最終一致性：所有圖形操作都在所有站點中執行完畢后，來自不同站點的所有操作圖形都是相同的. 意向保存：需要在所有站點保存圖形并發操作的綜合效果. 此外，我們的研究工作需要考慮兩種種情況： 1)為了兼容操作，需要保留所有兼容操作的效果. 2)對于沖突操作，盡可能保留沖突操作的影響，必要時只需要保留沖突操作的一個效果，根據動態規則庫保留操作語義的一致性. 與協同文本編輯不同，在基于圖形對象操作的Co-RDG系統中，操作之間之間存在復雜關系，不同設計者之間的操作不可避免地存在沖突. 在這種情況下，由于操作沖突可能導致某些圖形對象操作無法執行，最終導致整個繪圖任務無法完成. 因此，需要沖突解決方法來保持更多的設計意圖并保持最終的一致性. 考慮到圖形操作的復雜性，為了維護最終的一致性，本文將操作分為基本操作和預定義關系操作兩種. 定義8.位置屬性約束關系 如果兩個不同的圖形對象存在一種或多種特殊的位置關聯關系，這樣的圖形對象之間的關系，我們定義為位置屬性約束關系.對這些圖形對象的任何一個對象進行操作，都要先檢測他們之間的約束關聯關系.位置關聯關系定義我們參考許[15]等人的研究. O(i)是用戶根據實際的設計的需求，動態的將圖形對象間的各種復雜的關聯關系添加到動態規則庫里，系統會及時通過廣播傳送給其他站點，使各個站點的語義沖突規則庫都保持最新的狀態. 3.3.1 基本操作 本文設計的協同圖形編輯系統中，有N操作(New)，D操作(Delete)以及U操作(Update)三種基本類型操作. 3.3.2 預定義關系操作 在實際的工程繪圖設計過程中，用戶可能根據自己的意愿或者實際的現實需求，預先給圖像對象間定義某些特殊的約束規則.在這樣的情況下，多人同時編輯這些圖形對象，執行結束后，可能就會違背之前定義的約束條件，從而造成語義不一致的問題.本文只討論，圖形對象之間位置上的關聯關系并且預定義關系一般指兩個操作作用在不同的對象之間. 預定義操作沖突檢測 預定義并發沖突操作 1)Oa||Ob 2)Oa、Ob∈Relate(Oa、Ob操作對象之間存在關聯關系) 3)Oa、Ob Rule?Oa、Ob在執行后違背了Rule定義的規則)那么，Oa和Ob是并發沖突操作預定義并發兼容操作 如果操作Oa和Ob不是并發沖突操作，則Oa和Ob是兼容操作. 算法1介紹了如何解決基本操作之間的沖突.操作Oa是已經執行過的操作，操作Ob是要執行的遠程操作.有兩種情況需要考慮.當操作是同一種操作類型，則根據優先級來決定執行哪個操作，優先級高的操作鏈接到雙鏈表中，優先級低的操作不執行，可見被設置為0，優先級低的操作flag被設置為1.當操作是不同類型的操作時，我們規定D操作的優先級大于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是執行操作，操作Ob是要執行的遠程操作.當兩個操作是兼容關系時，標識符較小的操作在標識符較高的操作之前執行.與此同時，在雙鏈表中具有較大標識符的操作鏈接在具有較小標識符的操作之后. 算法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不為空時，需要找到剛剛在本地站點執行的圖形建模操作(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 當遠程操作廣播過來后，圖形的目標操作可以使用唯一標識符直接找到.找到當前會話中的第一個建模操作，然后判斷遠程操作跟目標操作是否作用于同一目標對象，有兩種情況：一是作用于同一目標對象，根據基本類操作的沖突操作判斷是否是沖突操作，在相同文檔狀態下，若是沖突操作，調用CompatibleResolve算法，若是兼容操作，則調用 CompatibleResolve；在不同文檔狀態下，根據兩個操作的優先級來決定執行順序及目標操作的位置；二是兩個操作的對象目標不一致，此時要先去動態規則庫查詢兩個圖形對象間是否有空間位置關聯關系.在相同文檔狀態下，存在空間位置關聯關系，根據預定義的關聯關系，進一步需要判斷是不是違反約束規則，若是違反規則，則調用Predefined conflict resolution；若不違反規則，則調用CompatibleResolve.在不同的文檔狀態下，根據優先級來決定執行順序及目標操作在雙鏈表中的位置. 算法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 圖2 第一次協作過程Fig.2 First collaborative process 第1階段： 如圖2所示，站點1產生三個本地操作，分別是O1，O2，O3；站點2產生兩個本地操作，分別是O4，O5.所有操作的狀態向量分別是：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生成，執行O1，此時L1=O1.然后本地操作O2生成，執行將O2加入到雙鏈表中，即L1=O1-O2.當O4到達時，O4跟O2有相同的文檔狀態，需要檢測他們之間的關系，因為是兼容關系，并且IDO2IDO4，執行O4，在雙鏈表中把O4連接在O2之后，L1=O1-O2-O4.本地操作O3生成，O3的目標操作是O1，O2操作存在于O1后，因為O2和O3的狀態向量不同，IDO2IDO3 ，因此，將O3連接在O2之后，同理，O3連接在O4之后.執行O3并將O3操作加入到雙鏈表中，此時L1=O1-O2-O4-O3.當O5到達站點1時，O5的目標對象是O1，O1后面有O2，O3，O4，因為O5跟O2和O3的狀態向量不同，連接在操作O4后面，O5的目標對象跟O3目標對象時相同的，并且狀態向量相同的，所以他們是基本類操作里面的沖突操作，因為IDO3IDO5，所以，O3操作撤銷，O5操作執行.O3.visible=0同時將O5插入到雙聯表中，L1=O1-O2-O4-O3-O5. 在站點2，O1操作到達，L2=O1.操作O4生成，執行O4并將其加入雙鏈表中，L2=O1-O4.O2操作到達，因為O4和O2具有相同的文檔狀態，但是O2和O4目標對象不同，因此是兼容關系，同時IDO2IDO4.所以執行O2，在雙鏈表中把操作O2放到操作O4之前，L2=O1-O2-O4.O5生成，執行O5，O5的目標對象是O1，直接將O5插入到雙鏈表中O1之后，O5跟O2和O4狀態向量不同，在雙鏈表中將O5連接在O4之后，L2=O1-O2-O4-O5.當O3操作到達，O3操作的目標對象是O1，操作O2，O4，O5在操作O1之后，并且O5跟O3具有相同的狀態向量，因此O5跟O3的關系需要檢測，是沖突操作，因為IDO3IDO5.因此，O3不需要執行，O3.visible=0，在雙鏈表中不可見的操作O3連接在操作O5之前.此時，L2=O1-O2-O4-O3-O5. 最終，在兩個站點維護的雙鏈表分別為：L1=O1-O2-O4-O3-O5 L2=O1-O2-O4-O3-O5 圖3 第二次協作過程Fig.3 Second collaboration process 第2階段： 如圖3所示展示第二階段的協同過程，在站點1生成一個本地操作06，站點2生成一個本地操作07，所有操作的狀態向量分別是：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，不是當前協同會話過程中，所以跳過.操作O6在當前會話過程中，因為操作O6和O7作用在不同的操作對象中，用動態規則庫(CoRDG)檢查兩個操作是否違反Rule，檢查違反了預定義關系，根據優先級，撤銷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具有相同的文檔狀態，因為O7比O6具有更高的優先級.所以，O6不執行，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. 在本小節中，我們將對我們的方法進行實驗，以驗證算法的有效性.我們用Intellij IDEA作為實驗平臺，用JAVA語言實現，模擬測試仿真原型系統，并且由Windows 7系統，Intel Core i7，3.30 GHz CPU上的Visual Studio 2010編譯.然而，在協作編輯中沒有可用的公共數據集，性能評估通?；诓僮魅罩居蓞f作產生.我們設計實時協作以獲取操作日志.然后，重播兩種算法的所有操作.每個站點執行所有本地操作和遠程操作后，將繼續執行相同的過程.我們在每個操作日志中運行次30次算法，并記錄平均值. 圖4 CRDT方法與COT方法比較Fig.4 ContrastofCRDTandCOT圖5 歷史操作數與站點數的對比圖Fig.5 Comparisonofhistoricaloperandsandnumberofsites 在本節中，將我們的方法與文獻[11]傳統COT算法的計算時間進行比較. 首先，研究了我們的方法和COT算法將遠程圖形操作集成到操作歷史H中需要多長時間.其次，研究了我們的方法和COT的圖形操作的平均計算時間.圖5顯示了COT和我們的方法遠程操作的計算時間. 如圖5所示，隨著操作歷史的長度增加和遠程操作的數量增加，COT比我們的方法需要更多的時間. 尤其是，當操作歷史的長度為200時，COT需要64 ms來集成100個遠程操作，而我們的方法僅需5 ms來集成100個遠程操作. 圖4顯示了COT與我們的方法的基于圖形的操作的平均計算時間，其中刪除比率被設置為20%并且遠程操作的數量隨著歷史操作數而增加. 如圖5所示，COT需要更多時間來整合刪除操作，但我們的方法需要更少的時間. 主要原因是有沖突時，每個COT算法在集成遠程操作時，P2P環境下的COT每次傳輸都要附帶一個C(O)的文檔狀態文本，當協同工作時間過長或操作過多時，這個C(O)就會變得很龐大，每次沖突都要從歷史操作序列開頭進行一一對比. 例如，當遠程操作的數量是400，刪除率是20%時，我們的刪除操作能根據目標對象唯一的ID號直接進行刪除操作. 為了驗證大規模數據下實時圖形編輯系統中，算法的正確性與可行性，本文開發了一個基于Intellij IDEA平臺實時圖形編輯系統CO-DRAWING.客戶端：采用[19]webSocket協議實現實時圖形編輯系統CO-DRAWING.WebSocket協議可以實現持久連接的全雙工雙向通信，應用WebSocke 結合WSS協議達成多人實時異地協同設計的目標.服務器端：系統采用SSM(SpringMVC+Spring+Mybatis)框架來搭建的一個web系統，通過Intellij IDEA平臺，部署到到tomcat上來實現訪問，同時為了體現大規模數據的特性，采用Docker技術在一臺物理計算機上運行3個服務端程序. 圖6 算法原型系統Fig.6 Algorithm prototype system 多人同時編輯如圖6所示，上方是為選擇創建各種圖像(三角形，線條，矩形)，清空畫布等功能：屏幕右下方中間部分為協同用戶界面；屏幕右下方下面部分為圖形對象ID號；系統分為基本操作維護和語義沖突維護.其中語義操作維護根據動態規則庫來進行管理. 本文提出了一種新穎優化的CRDT算法，該算法主要應用于大數據時的智能和大規模協作的實時圖形編輯系統中. 該新穎算法可以保留操作的意圖并通過預定義圖形對象之間的關聯關系和位置屬性約束規則，設計本地操作和遠程操作的實現算法，使個站點的語義維護得到有效的保證.并且通過理論分析和實驗評估表明，該算法的計算性能大大優于現有的OT算法和AST算法. 因此，與現有算法相比，該算法更適合于智能和大規模協作應用. 在未來的研究中，我們計劃繼續探索以下幾個方面. 首先，圖形編輯系統中的Undo/Redo是很重要的操作，下一步將重點探索這個方面. 其次，我們將把圖形對象中的其他操作合理地加入進來，圖形之間的預定義操作不僅只有這一種，還有很多復雜的關聯操作需要考慮.第三，嘗試將我們的方法應用于現實生活中的協作應用程序. 例如，Google Drive，Codoxware，SubEthaEdit，Novell Vibe等基于云的協作服務近年來越來越流行. 這些協作應用程序需要通過在合作者之間交換意圖，想法，知識和智慧來共同創作共享文檔，從而提高效率和質量. 所提出的算法與要求非常匹配，并將在未來應用于這些領域.第四，我們將探討如何使用多核CPU /多核GPU加速大規模協作應用[9,10].
3.3 操作分類
3.4 操作檢測
3.5 CRDT算法
4 案例分析
5 實驗分析
6 原型系統Intellij
7 總結與展望
