文件管理中一種新穎的沖突檢測和解決方法

高麗萍,陶長青

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

1 引 言

在短短的過去的幾年時間里,我們見證了云計算、云存儲以及移動計算技術(shù)的快速發(fā)展.云時代技術(shù)已經(jīng)影響了人們生活的方方面面,成為了當下主流的研究以及應用技術(shù)之一.云存儲是數(shù)據(jù)共享和協(xié)作的主要云計算應用之一,用戶可以在云存儲系統(tǒng)上訪問和修改復制式文件,如同在本地計算機上操作,并將操作實時同步到數(shù)據(jù)中心以及其他用戶站點上.伴隨著云計算的不斷發(fā)展,將其與計算機支持的協(xié)同工作(Computer Supported Cooperative Work,CSCW)技術(shù)結(jié)合,正成為了當下研究的熱門領域之一.采用云的方案既能夠?qū)崿F(xiàn)用戶隨時隨地協(xié)同辦公和協(xié)同工作的要求,又能夠使得開發(fā)者在專為用戶設計應用時,無需擔心受到操作系統(tǒng)、辦公設備等限制,體現(xiàn)了良好的應用價值,從而可以大大提高人們工作的效率.其中,CSCW是指多個在地域上的分散的用戶在同一時間并發(fā)地對共享的同一文檔進行編輯,其強調(diào)的是人與人之間的交互,對交互過程中的響應性和并行性有著較高的要求.實時編輯系統(tǒng)作為CSCW代表性應用,要求協(xié)同效果即時可見,即協(xié)同用戶之間的工作畫面要維持一致.

隨著云服務的逐漸流行,越來越多的傳統(tǒng)辦公軟件被遷移到云端以提供更好的辦公協(xié)作支持,而文件管理作為企業(yè)辦公系統(tǒng)中的重要組成部分,合理且高效的管理文件對企業(yè)的工作進程來說起著巨大的作用.傳統(tǒng)的文件管理方法是分配一個人對文件進行管理,但在這個信息量暴增的時代,這種工作模式帶著強烈的主觀意識且效率低下,其他用戶想要在海量且龐雜的文件中找到所需文件并對其使用是極其浪費時間和人力的.而多人實時管理文件則是一個很好的適應信息化時代的文件管理的方法,通過多人協(xié)同管理,每個用戶均可對自己所需模塊的文件進行管理,不僅可以提高工作效率,還可在與其他用戶的交互過程中清楚的了解其他用戶在管理文件時的意愿,使得用戶對文件的管理更加安全且提高了用戶的體驗度.因此,實時文件管理系統(tǒng)作為協(xié)同分布式交互應用的重要分支,對其研究具有較大的實際應用價值和意義.

在實時的管理文件的過程中,地理位置分布不同的用戶在本地復制式文本上進行編輯操作并通過網(wǎng)絡進行交互,其中面臨的最大的挑戰(zhàn)即是在用戶協(xié)作過程中并發(fā)情況下如何維護共享工作空間的一致性,這對于協(xié)作系統(tǒng)的正確性和性能來說非常關(guān)鍵.而近幾年CRDT技術(shù)被提出作為協(xié)作文本編輯中的新的并發(fā)沖突控制機制,已被證明其算法的性能優(yōu)于傳統(tǒng)的并發(fā)控制方法,且適用于樹形結(jié)構(gòu)共享工作空間中.本文針對非線性結(jié)構(gòu)文件模型提出了一種基于CRDT技術(shù)的新的沖突檢測和解決方法.本文將著重設計基于CRDT的新的沖突檢測和解決方案,并在以下三個方面做出重要的貢獻:

1)定義操作的依賴沖突關(guān)系、非依賴沖突關(guān)系以及兼容關(guān)系,并設計操作關(guān)系檢測算法;

2)設計基于CRDT的沖突解決方案,來維護各個副本的最終的一致性,并同時盡可能多的維護用戶的意圖;

3)針對云環(huán)境設計合理的Client和Server端的控制算法;

4)舉例證明其正確性并分析其效率.

2 相關(guān)工作

云存儲是數(shù)據(jù)共享和協(xié)作的主要云計算應用之一,用戶可以在云存儲系統(tǒng)上訪問和修改復制式文件,如同在本地計算機上操作,并將其實時同步到數(shù)據(jù)中心以及其他用戶站點上.而實時協(xié)同編輯系統(tǒng)中復制式文件的一致性維護技術(shù)是保證系統(tǒng)正確性的根本.目前市場上比較常用的一致性維護技術(shù)有操作轉(zhuǎn)換(OT,Operation Transformation)[1-3]、地址空間轉(zhuǎn)換(AST,Address Space Transformation)[4-6]和可交換復制式數(shù)據(jù)類型(CRDT,Commutative Replicated Data Type)[7-9]等技術(shù).其中,OT技術(shù)是最早提出的實時協(xié)同編輯系統(tǒng)下的一致性維護技術(shù),在1989年由Ellis提出,是基于操作本身,根據(jù)并發(fā)操作產(chǎn)生和執(zhí)行的效果,對操作中的參數(shù)進行修改,使得最終文本的一致性得到維護.AST技術(shù)是將文本狀態(tài)回溯到操作產(chǎn)生時的狀態(tài),直接執(zhí)行操作,并再次回溯狀態(tài),從而維護一致性.而CRDT技術(shù)則是設計操作可交換的復制式數(shù)據(jù)類型,在協(xié)同編輯過程中為每一個對象分配一個全局唯一標識符,從而可以實現(xiàn)對象間的可交換性需求,維護最終結(jié)果的一致性要求.目前CRDT技術(shù)多用于文本、二維圖形以及3D圖形的協(xié)同編輯系統(tǒng)的一致性維護中[7-10],還未應用到云存儲以及文件管理系統(tǒng)下等復雜的環(huán)境中,因此本文著重研究云環(huán)境下采用CRDT技術(shù)的文件協(xié)同管理系統(tǒng)的一致性維護.

目前為止,云環(huán)境下的一致性維護技術(shù)還不是很普遍,Xia在文獻[6,11]中對AST技術(shù)在移動云環(huán)境下的應用做出了研究,提出了基于標量時間戳的同步協(xié)議和基于全局標識符的地址空間轉(zhuǎn)換策略,實現(xiàn)了移動云環(huán)境中用戶畫面的異步協(xié)同.而實時文件系統(tǒng)作為CSCW領域中重要的分支,近年來多位學者也對其進行了相關(guān)研究,例如Sun等在文獻[12]中對云存儲中共享工作空間的實時同步的操作轉(zhuǎn)換做了研究,定義了各個基本操作(create,delete,update 和rename)在并發(fā)時期望得到的組合效果,并采用COT算法以避免需要設計轉(zhuǎn)換函數(shù)來保證收斂屬性2(CP2),設計了云存儲下的操作轉(zhuǎn)換函數(shù)(CSOT)來維護收斂屬性1(CP1),其中CP1和CP2可以用來保證轉(zhuǎn)換函數(shù)的正確性,以解決在云環(huán)境下文件存儲以及管理中用戶產(chǎn)生的操作沖突并達到理想的結(jié)果.L Gao等在在文獻[13-15]中對協(xié)作圖形編輯方面進行了研究,并改進算法將其應用到移動云環(huán)境下;在文獻[16，17]中對實時云辦公系統(tǒng)的文件管理的一致性維護做出了相關(guān)討論,提出改進的COT算法以適用云環(huán)境下新的集中式架構(gòu),并在CSOT轉(zhuǎn)換函數(shù)的基礎上設計操作轉(zhuǎn)換函數(shù),解決基本操作之間并發(fā)時產(chǎn)生的沖突,使云環(huán)境下辦公系統(tǒng)中對文件的管理能夠達到更高的實時性要求.本文是對云存儲中文件管理系統(tǒng)中采用CRDT的一致性維護技術(shù)上,設計合理的可交換式的數(shù)據(jù)和操作類型以解決并發(fā)操作之間沖突關(guān)系,并維護各個站點共享文檔的一致性.

隨著云計算技術(shù)的快速發(fā)展和普及,對部署在云上的應用程序的訪問也越來越多,用戶可以隨時隨地的使用本機設備對文件進行管理,當然這在交互響應和一致性維護方面也帶來了很大的挑戰(zhàn).因此,采用協(xié)同編輯技術(shù)中的工作空間復制的方法來解決以上問題.不同于傳統(tǒng)的P2P架構(gòu),本文針對云環(huán)境下集中式架構(gòu),設計合理的并發(fā)控制算法來解決基本操作(create,delete,rename和update)之間可能發(fā)生的并發(fā)操作沖突,并保證各用戶的工作空間滿足CCI模型.

3 數(shù)據(jù)模型和操作模型

3.1 基本數(shù)據(jù)結(jié)構(gòu)

文件管理系統(tǒng)的復制式工作空間可以被定義為一個樹模型:T=(N,A),其中N={N0,N1,N2,…}代表樹中的節(jié)點集合,即云存儲空間中的文件夾或者文件節(jié)點集合,A代表樹中的箭頭集合,即存儲空間中節(jié)點之間的父子關(guān)系.每個節(jié)點N都有一個名稱N.name,用一個字符串表示,為了簡單起見,這里用大寫字母′A′,′B′,…等表示;每個節(jié)點N上都有一個標識符屬性N.OID,代表了作用在該節(jié)點上的最新的操作的唯一標識符.節(jié)點的路徑是指從樹結(jié)構(gòu)中的根節(jié)點到某節(jié)點的父結(jié)點的名稱所組成的字符串,代表了該節(jié)點的路徑,如圖1中,文件M的路徑為A/G.

3.2 基本定義

定義1.特征依賴關(guān)系(|→ )

給定文件樹模型中的任意兩個節(jié)點N1和N2,當滿足以下情況時則稱N1依賴于N2,即N1|→N2.

1)N1和N2屬于父子關(guān)系,即N1.parentname=N2.name;

2)存在一個節(jié)點Nx,使得N2.name?Nx.path且Nx.name?N1.path

定義2.優(yōu)先級(P)

給定任意兩個操作O1和O2,針對的對象節(jié)點為N1 和N2,當N1|→N2時,則針對該節(jié)點的操作的優(yōu)先級為P(O1)>P(O2).

定義3.依賴沖突關(guān)系(⊕)

給定狀態(tài)向量SV相同的兩個操作O1和O2,當且僅當O1和O2的目標節(jié)點有依賴關(guān)系且以不同的順序執(zhí)行O1和O2后得到的結(jié)果不同時,O1和O2具有依賴沖突關(guān)系,記為O1⊕O2.

定義4.非依賴沖突關(guān)系(×)

給定狀態(tài)向量SV相同的兩個操作O1和O2,兩者所針對的目標節(jié)點的路徑之間沒有依賴關(guān)系,且以不同的順序執(zhí)行這兩個操作會產(chǎn)生不一樣的結(jié)果.則稱O1和O2是屬于非依賴沖突關(guān)系,記為O1×O2.

定義5.兼容關(guān)系(?)

當給定的操作O1和O2的目標節(jié)點沒有任何依賴關(guān)系時,即目標節(jié)點處于不同的子樹流中,兩者的執(zhí)行順序不影響他們的操作結(jié)果時,O1和O2屬于相容的操作,記作O1?O2.

定義6.操作的唯一標識符(OID)

操作的唯一標識符是一個三元組,其中s代表站點間進行的會話的標識符,sumsv代表操作攜帶的狀態(tài)向量的總和,site代表操作產(chǎn)生的站點的標識符.當滿足以下情況時,OID(O1)

1)OID(O1)[session]

2)當OID(O1)[session]=OID(O2)[session]時,OID(O1)[sumsv]

3)當OID(O1)[session]=OID(O2)[session]且OID(O1)[sumsv]=OID(O2)[sumsv]時,OID(O1)[site]

定義7.操作的全局順序(?)

給定雙鏈表中的任意兩個操作O1和O2,position(O)代表操作O在雙鏈表中的位置,若P(O1)>P(O2),position(O1)OID(O2)時,則O1?O2.

3.3 基本操作類型

本文主要在create、delete、rename以及update操作的基礎上進行分析和研究,操作的定義以及基本操作類型的介紹如下:

定義8.操作(O)

在文件管理系統(tǒng)中,操作O是一個八元組,其中,T代表了操作的類型,如create,delete,rename和update操作;l代表了操作是本地還是遠程的,true本地,False代表遠程;T-OID代表了操作的目標節(jié)點維護的唯一標識符,即目標操作的標識符;OID代表了操作的唯一標識符;指針next指向雙鏈表中的下一個操作;指針prior指向雙鏈表中的前一個操作,指針link用于哈希表中的單鏈表;狀態(tài)s代表了操作執(zhí)行時的狀態(tài).

1)O=Create(p,C,N):在路徑名為p的文件夾下創(chuàng)建一個以節(jié)點N為根的子樹T,該子樹可以是一個文件夾節(jié)點,也可以是一個文件,C代表節(jié)點類型,文件或者文件夾.

2)O=Delete(p,C,N):刪除路徑為p的文件夾中的節(jié)點N.

3)O=Rename(p,C,N.name,N.nameNew):在路徑為p的文件夾中名稱為N.name的類型為文件夾或者文件改名為N.nameNew.

4)O=update(p,N,d):更新路徑p下的文件節(jié)點N的內(nèi)容為d.

4 實時文件管理中的一致性維護

4.1 操作沖突檢測

文件管理系統(tǒng)中,基本操作有創(chuàng)建,刪除,改名和移動四個基本操作,由于操作針對的對象之間存在依賴關(guān)系,以及操作之間的復雜的關(guān)系,使得并發(fā)操作產(chǎn)生時,不同的執(zhí)行順序會產(chǎn)生不同的操作效果,即產(chǎn)生沖突.所以,在集成遠程操作時,操作之間會產(chǎn)生依賴沖突關(guān)系,非依賴沖突關(guān)系,以及兼容關(guān)系,在操作執(zhí)行之前,需要對并發(fā)操作之間的關(guān)系進行檢測.

表1 操作間的沖突關(guān)系表
Table 1 Conflict relationship table between operations

createdeleterenameupdatecreate×or×?deleteor×or×renameor×or×update?

給定操作O1和O2分別作用于節(jié)點N1和N2,針對上文定義的4個基本操作,有如表1所示的操作對之間可能會出現(xiàn)的沖突關(guān)系.

1)O1=create,O2=create,當且僅當p1=p2,C1=C2且N1.name=N2.name時,O1和O2為非依賴沖突關(guān)系,稱為O1×O2,其他情況為兼容關(guān)系,則稱O1?O2.

2)O1=create,O2=rename,若N1|→N2,則O1和O2為依賴沖突關(guān)系,稱為O1⊕O2;若p1=p2且N1.name=N2.nameNew,則O1和O2為非依賴沖突關(guān)系,稱為O1×O2;其他情況均為兼容關(guān)系,則稱O1?O2.

3)O1 =delete,O2=delete,若N1|→N2,則O1和O2為依賴沖突關(guān)系,若p1=p2且N1=N2時,O1和O2屬于非依賴沖突關(guān)系.

4)O1=delete,O2=rename,若N1|→N2,則O1和O2為依賴沖突關(guān)系,O1⊕O2;若p1=p2,且N1=N2,則O1和O2為非依賴沖突沖突關(guān)系,稱為O1×O2;其他情況下均為兼容關(guān)系,則稱O1?O2.

5)O1=rename,O2=rename,若N1|→N2,則O1和O2為依賴沖突關(guān)系,O1⊕O2;若p1=p2且N1.nameNew=N2.nameNew或者N1=N2且N1.nameNew!=N2.nameNew,則O1和O2是非依賴沖突關(guān)系,稱為O1×O2;其他情況下均為兼容關(guān)系,則稱O1?O2.

6)O1=delete,O2=update, 若N2|→N1,則O1和O2為依賴沖突關(guān)系,O1⊕O2;其他情況下均為兼容關(guān)系,則稱O1?O2.

7)O1=rename,O2=update,若N2|→N1,則O1和O2為依賴沖突關(guān)系,O1⊕O2;若p1=p2且N1=N2時,則O1和O2為非依賴沖突關(guān)系;其他情況下均為兼容關(guān)系,則稱O1?O2

8)其他情況下,操作之間屬于兼容的關(guān)系,則稱O1?O2.

根據(jù)以上操作對之間的關(guān)系分析設計檢測函數(shù)如算法1所示.

算法1.FindRelation(O1,O2)INPUT O1,O2If O1=create(p1,C1,N1),O2 =create(p2,C2,N2)then If p1 == p2 &&C1 == C2 && N1.name == N2.name then Return O1×O2 Else return O1?O2 End if Else if O1=create(p1,C1,N1),O2=rename(p2,C2,N2.name,N2.nameNew)then If p1 == p2&&C1 ==C2 && N1.name=N2.nameNew then Return O1×O2 Else if N1|?N2 || N2|?N1 then Return O1O2 Else return O1?O2 End ifElse If O1=create(p1,C1,N1),O2=delete(p2,C1,N2)then Return O1?O2Else if…….(to save space,omit the following statement)End if

4.2 操作沖突解決

在實時文件管理系統(tǒng)中,一致性的要求是維護CCI(Consistence,Convergence,Intention)模型.本文采用CRDT數(shù)據(jù)模型自動收斂,而一致性要求和意圖維護則需要所有操作執(zhí)行后在所有站點得到相同的結(jié)果,盡可能滿足所有用戶的意圖.針對以上操作之間關(guān)系的檢測,要求如下:

1)兼容關(guān)系:所有操作的效果都應得到實現(xiàn);

2)非依賴沖突關(guān)系,盡可能多的維護用戶的意圖;

3)依賴沖突關(guān)系:盡可能多的維護所有用戶的操作的效果.

由于不同用戶發(fā)出操作的對象之間的依賴關(guān)系,以及操作之間的沖突,都會導致復制文本不一致的情況,所以需要設計合理的操作沖突解決策略和算法來解決由于存在并發(fā)操作產(chǎn)生的沖突,最終實現(xiàn)各個復制副本的一致性需求.

依賴沖突解決方案:給定任意兩個操作O1和O2,O1是已經(jīng)執(zhí)行過的操作,而O2是一個遠程操作,且O1和O2屬于依賴沖突關(guān)系,則依賴沖突關(guān)系的解決方案如下:

算法2. Conflict-DependentResolution(O1O2)INPUT O1O2N1和N2代表操作O1和操作O2的目標對象If N1|?N2 then O2 is executed directly O2 is put into the doubly-linked list behind O1Else Undo O1,O2 is executed,redo O1 O2 is put into the doubly-linked list before O1End if

在算法2中,若操作O1 和操作O2作用的對象有依賴沖突,或者操作依賴沖突,或者操作O1的ID大于O2 的ID,則撤銷操作O2,執(zhí)行O1,重新執(zhí)行O2,并將操作O1鏈接到操作O2的前面;否則,直接將操作O2鏈接到操作O1的右側(cè).

非依賴沖突關(guān)系解決方案:

算法3. Non-dependentConflictResolution(O1×O2)INPUT:O1×O2There must be p1==p2if O2=update then P(O2)>P(O1) Undo O1,O2 is executed,redo O1 O2 is put into the double-linked list before O1Else If O1=update ‖ OID(O1)>OID(O2) then If O1 !=update then Transform(O2,O1) End if O2 is executed O2 is put into the double-linked list behind O1Else Undo O1,O2 is executed Transform(O1,O2) Redo O1 O2 is put into the double-linked list before O1End if

在算法3中,若操作O1 和操作O2屬于非依賴沖突關(guān)系,若操作O1的id小與操作O2的id,則對操作O2進行操作轉(zhuǎn)換,并將操作O1鏈接到操作O2的前面,否則,撤銷操作O1,執(zhí)行操作O2,并對操作O1 鏈接到操作O2的右側(cè).

算法4. Transform(O2,O1)INPUT O2,O1If O2=rename then If O1=rename&&(N1 !=N2)‖O1=create then N2.nameNew=N2.nameNew+UniqueString(sid2,uid2) Else if O1=rename&& N1=N2 then N2.nameOld=N1.nameNew Else O2=null End ifElse if O2=create then N2.name=N2.name + UniqueString(sid2,uid2)Else O2=nullEnd if Return O2

在算法4,針對非依賴性操作,不可避免的會出現(xiàn)操作轉(zhuǎn)換,該算法就是對其中的操作做出相應的操作轉(zhuǎn)換.

兼容操作關(guān)系解決方案:

算法5.CompatibleResolution(O1?O2)INPUT O1?O2If OID(O1)

在算法5中,若操作O1和操作O2屬于兼容關(guān)系,若操作O1的id小與操作O2的id,則撤銷操作O2,執(zhí)行操作O1,重新執(zhí)行操作O2,并將其鏈接到操作O2的前面,,否則,O1的操作為空,執(zhí)行操作O2,并將操作O1 鏈接到操作O2的右側(cè).

4.3 本地操作集成過程

當本地操作產(chǎn)生時,直接執(zhí)行,并將該操作直接鏈接到雙鏈表的后面,若接收到一個遠程操作,則找到它的目標操作,并檢測是否存在與它具有相同的目標操作的操作,以及和它們的關(guān)系.并根據(jù)它們的關(guān)系確定它們在雙鏈表中正確的位置.本地操作執(zhí)行過程如算法6所示.

算法6. LocalOperation(O)Execute a local operation O directlyIf head.next == null then O is double linked next to headElse O double linked next to last operation in Li SV[i]=SV[i]+1 OID stored in HiEnd if

4.4 遠程操作集成過程

遠程操作執(zhí)行過程如算法7所示.

在算法7中,當集成遠程操作O時,需要在雙鏈表中找到目標操作,若目標操作后有操作存在,則需要檢測該操作與操作O的關(guān)系,并找到操作O在雙鏈表中的正確的位置,算法中引用的函數(shù)FindPosiong()就是負責尋找操作O在雙鏈表中的位置.

算法7. RemoveOperation(O)Receive a remote operation Otar=Hi.get(N.OID);nextTar=tar.next;If nextTar=null then O is double linked after Tar in LiElse FindPosition(nextTar,O) Execute the operation O O is double linked in Li SV[i]=SV[i]+1 OID is stored in HiEnd if

算法8. FindPosition(O1,O2)While(O1.next != null)then if O1.s == O2.s then If FindRelation(O1,O2)=O1O2 then If N1|?N2 then O1=O1.next,continue Else Conflict-DependentResolution(O1O2)Break End if Else if FindRelation(O1,O2)=O1×O2 then if O2 !=update && OID(O1)>OID(O2) If O1!=update then O2=Transform(O2,O1) End if O1=O1.next,continue else Non-dependentConflictResolution(O1×O2) break End if Else if FindRelation(O1,O2)=O1?O2 then If OID(O1)> OID(O2) O1=O1.next,continue else CompatibleResolution(O1?O2) break End if End if Else if OID(O1)

算法8是根據(jù)狀態(tài)向量找到并發(fā)操作,并根據(jù)并發(fā)操作間的關(guān)系,找到雙鏈表中操作正確的鏈接位置,若并發(fā)操作間為依賴沖突關(guān)系,則根據(jù)操作對象的依賴關(guān)系確定位置,若操作間為非依賴沖突關(guān)系,則進行合理的操作轉(zhuǎn)換并確定位置,若并發(fā)操作間為兼容關(guān)系,則根據(jù)操作的唯一標識符確定并發(fā)操作的執(zhí)行順序和在雙鏈表中的正確的位置.

5 云環(huán)境下文件實時協(xié)同管理的一致性維護

本文所研究的是基于云環(huán)境下的協(xié)同文件管理系統(tǒng)的一致性維護,設計基于CRDT數(shù)據(jù)類型設計并存儲用戶的操作,使其適用于云環(huán)境下的文件管理系統(tǒng),本章節(jié)設計相應的算法使得操作的順序可以交換并能夠保證最終狀態(tài)一致性.區(qū)別于傳統(tǒng)的P2P架構(gòu),云環(huán)境主要采用的是C/S架構(gòu),本節(jié)在C/S架構(gòu)的基礎上設計合理的服務器端和客戶端的算法.

1)客戶端的主要任務有:執(zhí)行并向服務器端發(fā)送本地操作;接收遠程操作,找到該操作在雙鏈表中正確的位置并執(zhí)行.

算法9. ControlPro on clientGet the latest workspace status from the serverThread1: Generate a local operation O LocalOperation(O) Send O to serverThread2: Receive remote operations sequence T For(i=0;i

在算法1中,Li代表一個雙鏈表,存放的是按照全局順序存儲的操作,SVi代表的是站點i的當前狀態(tài)向量,Hi代表存放全局唯一標識符的哈希表.

2)服務器端的主要任務是:線程一處理新的連接請求并發(fā)送最新的副本給新站點等;線程二接收遠程操作并執(zhí)行.線程三負責更新該操作的目標操作,節(jié)省該操作與其他客戶端的并發(fā)操作的比對,并將更新過的遠程操作轉(zhuǎn)發(fā)給非發(fā)送源的其他站點.服務器端的算法如下:

算法10. ControlPro on ServerInit()Li=[];Hi=[];Thread1: handling new connection requestsThread2: Receive remove operations sequences RS from clients RS =[T1,T2,…Tn] For(i=0;i

6 實例分析

本節(jié)主要設計一個協(xié)作文件管理場景來驗證提出的算法的正確性,假設有兩個站點協(xié)作管理文件,站點間的交互時序圖如圖2所示,初始會話為1,兩個站點的的關(guān)系為ID(site0)

圖2 站點操作時序圖Fig.2 Operation sequence diagram

在站點1,本地操作O1、O2和O4立即執(zhí)行,并依次直接鏈接到雙鏈表的最后,即站點1的雙鏈表為L1=O1→O2→O4;遠程操作O3到達,O3的目標操作為O1,而雙鏈表中操作O1后面有操作O2和O4的存在,所以需要依次檢測O3和它們的關(guān)系,操作O3和O2來自相同的空間狀態(tài),兩者屬于兼容的操作關(guān)系,且OID(O2)OID(O8),且它們來自不同的狀態(tài),所以O7應該鏈接到操作O8的前面,此時雙鏈表為L1=O1→O2→O3→O5→O4→O6→O7→O8.

在站點2,遠程操作O1到達,沒有目標操作,直接鏈接到雙鏈表中,L2=O1;本地操作O3立即執(zhí)行,直接連接到雙鏈表中,雙鏈表為L2=O1→O3;遠程操作O2到達,其目標操作為O1,而O2和O3來自相同的狀態(tài)且屬于兼容操作關(guān)系,OID(O2)OID(O7),所以應該連接到操作O7的后面,雙鏈表為L2=O1→O2→O3→O5→O4→O6→O7→O8.

圖3 協(xié)作工作后各站點維護的文本狀態(tài)圖Fig.3 State diagram maintained by each site after collaborative work

由上述案列分析可知,站點1和站點2按照不同的順序執(zhí)行相同的操作后,都能得到相同的如圖3所示的最終文本狀態(tài),實現(xiàn)協(xié)同管理文件的一致性的維護.

7 效率分析

時間復雜度:如本地操作執(zhí)行過程算法所示,根據(jù)哈希表和唯一標識符信息直接查詢本地操作的目標操作的時間復雜度為O(1),當會話開始后,需要在雙鏈表中找到最后一個執(zhí)行的操作,在這種情況下的時間復雜度為O(n),其中n代表的是在雙鏈表中已經(jīng)執(zhí)行過的操作的數(shù)量.而在集成遠程操作,其最好情況下的時間復雜度為O(1).在這種情況下,通過唯一標識符T-OID在哈希表找到目標操作,而遠程操作的位置剛好位于該目標操作的旁邊,只有目標操作后面沒有其他操作,或者遠程操作需要直接鏈接到目標操作后面時,才會出現(xiàn)這種情況.而考慮最壞的情況時,集成遠程操作時會調(diào)用FindPosition函數(shù)來查找操作的正確的位置,而FindPosition函數(shù)的最壞的時間復雜度是O(m),其中,m是目標操作后面存在的操作數(shù)量.

空間復雜度:在我們所提出的方法中,每個操作O都是八元組,假設它的長度為Q,雙鏈表中的操作有n個,則空間復雜度為(Q×n),假設哈希表和雙鏈表一樣的空間開銷,且每個站點的文件或文件夾總共為P個,但肯定不會多于雙鏈表中的操作的數(shù)量,每個文件或文件夾有名稱屬性以及維護一個操作標識符,假設所占空間為L,所以在我們提出的方法中,總空間復雜度為(2Q×n+P×L).

8 正確性證明

在實時文件管理系統(tǒng)中,證明一致性維護方法正確的要求模型是維護CCI模型,本文采用改進CRDT的一致性維護機制,自動維護收斂,無需證明.因此,只要滿足以下標準即可證明本文所提出的算法的正確性.

定理1.所提出的方法能夠維護最終一致性

證明:在實時文件管理系統(tǒng)中,狀態(tài)相同的遠程操作可能會有建模沖突,在下面的證明中,所有的操作都是以相同狀態(tài)的遠程操作的形式給出,有三種情況需要考慮.

1.對于兩個遠程操作Oi和Oj,Oi依賴沖突Oj,無論以什么順序執(zhí)行,兩鏈表中的操作的順序都是相同的.

假設當前的雙鏈表為L=O1-O2-…-Ok-Os-…On.且操作Oi和Oj的目標操作均為操作Ok

1)若先接收到Oi且將Oi鏈接到雙鏈表中Ok的后面,此時雙鏈表為L=O1-O2-…-Ok-Oi-Os-…On,操作Oj到達,有兩種情況需要考慮.

若F(Oi)依賴于F(Oj),則Oj被執(zhí)行并鏈接到操作Oi的后面.此時雙鏈表為L1=O1-O2-…-Ok-Oi-Oj-On.

若F(Oj)依賴于F(Oi),則Oi操作被撤銷,Oj操作被執(zhí)行并重新執(zhí)行操作Oi,操作Oj鏈接到操作Oi的前面,此時的雙鏈表為L2′=O1-O2-…Ok-Oj-Oi-On.

2)若先接收到操作Oj,且將Oj鏈接到雙鏈表中Ok的后面,此時雙鏈表為L=O1-O2-…-Ok-Oj-Os-…On,操作Oi到達,有兩種情況需要考慮.

若F(Oi)依賴于F(Oj),則Oi操作被撤銷,Oj操作被執(zhí)行并重新執(zhí)行操作Oi,操作Oj鏈接到操作Oi的后面,此時的雙鏈表為L1′=O1-O2-…-Ok-Oi-Oj-Os-…-On.

若F(Oj)依賴于F(Oi),則操作Oi被執(zhí)行并鏈接到操作Oj的后面.此時雙鏈表為L2′=O1-O2-…-Ok-Oj-Oi-…-On.

由以上證明可知,(1)中的雙鏈表L1和(2)中的L1′相同,(1)中的雙鏈表L2和(2)中的雙鏈表L2′相同.

2.對于兩個遠程操作Oi和Oj,Oi兼容Oj,無論以什么順序執(zhí)行,兩鏈表中的操作的順序都是相同的.

假設當前的雙鏈表為L=O1-O2-…-Ok-Os-…On.且操作Oi和Oj的目標操作均為操作Ok

1)若先接收到Oi且將Oi鏈接到雙鏈表中Ok的后面,此時雙鏈表為L=O1-O2-…-Ok-Oi-Os-…On,操作Oj到達,有兩種情況需要考慮.

若OiD(Oi)>OiD(Oj),則Oj被執(zhí)行并鏈接到操作Oi的后面.此時雙鏈表為L1=O1-O2-…-Ok-Oi-Oj-On.

若OiD(Oi)

2)若先接收到操作Oj,且將Oj鏈接到雙鏈表中Ok的后面,此時雙鏈表為L=O1-O2-…-Ok-Oj-Os-…On,操作Oi到達,有兩種情況需要考慮.

若OiD(Oi)>OiD(Oj),則Oi操作被撤銷,Oj操作被執(zhí)行并重新執(zhí)行操作Oi,操作Oj鏈接到操作Oi的后面,此時的雙鏈表為L1′=O1-O2-…-Ok-Oi-Oj-Os-…-On.

若OiD(Oi)

由以上證明可知,(1)中的雙鏈表L1和(2)中的L1′相同,(1)中的雙鏈表L2和(2)中的雙鏈表L2′相同.

3.對于兩個遠程操作Oi和Oj,Oi非依賴沖突Oj,無論以什么順序執(zhí)行,兩鏈表中的操作的順序都是相同的.

假設當前的雙鏈表為L=O1-O2-…-Ok-Os-…On.且操作Oi和Oj的目標操作均為操作Ok.

1)若先接收到Oi且將Oi鏈接到雙鏈表中Ok的后面,此時雙鏈表為L=O1-O2-…-Ok-Oi-Os-…On,操作Oj到達,有四種情況需要考慮.

若操作Oj為更新操作,則撤銷操作Oi,執(zhí)行Oj并重新執(zhí)行Oi,操作Oj鏈接到Oi的前面,此時的雙鏈表為L1=O1-O2-…-Ok-Oj-Oi-…-On.

若操作Oi為更新操作,則直接執(zhí)行操作Oj并將操作Oj鏈接到Oi的后面,此時的雙鏈表為L2=O1-O2-…-Ok-Oi-Oj-…-On.

若OiD(Oi)>OiD(Oj),則操作Oj相對操作Oi做操作轉(zhuǎn)換得到Oj′,并將操作Oj′鏈接到雙鏈表中操作Oi的后面,此時雙鏈表為L3=O1-O2-…-Ok-Oi-Oj-Os-…On.

若OiD(Oi)

2)若先接收到操作Oj且將Oj鏈接到雙鏈表中Ok的后面,此時雙鏈表為L′=O1-O2-…-Ok-Oj-Os-On,這里亦有四種情況.

若操作Oj為更新操作,則直接執(zhí)行操作Oi并將操作Oi鏈接到Oj的后面,此時的雙鏈表為L1′=O1-O2-…-Ok-Oj-Oi-…-On.

若操作Oi為更新操作,則撤銷操作Oj,執(zhí)行操作Oi,重新執(zhí)行操作Oj,并將操作Oi鏈接到Oj的前面,此時的雙鏈表為L2′=O1-O2-…-Ok-Oi-Oj-…-On.

若OiD(Oi)>OiD(Oj),則撤銷操作Oj,執(zhí)行操作Oi,并將操作Oj相對操作Oi進行操作轉(zhuǎn)換得到Oj′,重新執(zhí)行操作Oj′,將Oi鏈接到操作Oj的前面,此時雙鏈表為L3′=O1-O2-…-Ok-Oi-Oj-Os-…On.

若OiD(Oi)

在這種情況下,L1=L1′,L2=L2′,L3=L3′,L4=L4′.由以上證明可知,本文所提出的方法能夠確保每個站點都維護相同的歷史操作集,且最終獲得了一致性的文本空間.因此,本文所提出的的方法能夠滿足維護最終的一致性的需求.

定理2.所提出的方法能夠?qū)崿F(xiàn)意圖維護

證明:基于上述的維護最終一致性的證明,遠程操作的綜合效果都得到了保留.在此,考慮三種情況:首先,對于依賴沖突關(guān)系的操作,兩個操作的效果都得到了實現(xiàn);其次,對于兼容關(guān)系的操作,兩個操作的效果也都得到了保留;最后,對于非依賴沖突的操作,本文通過一些簡單的操作轉(zhuǎn)換使盡可能多的用戶操作的意圖得到了保留.因此本文所提出的方法可以實現(xiàn)用戶的意圖維護.

9 總結(jié)與展望

本文針對云環(huán)境下實時的文件管理系統(tǒng)中,提出新的基于CRDT方法的沖突檢測和解決方案來維護協(xié)同工作的一致性維護.首先定義基本操作以及操作之間的關(guān)系,并提出了沖突檢測機制;其次,提出沖突解決的有效方案;最后,舉例并證明了提出方案的正確性,并從理論上分析其時間復雜度和空間復雜度,本文所提出的沖突檢測和解決方案能夠有效的維護最終文本的一致性,并能保證操作的正確執(zhí)行.在未來的研究中,我們將針對細粒度進行研究,即針對文件內(nèi)容的操作,并改進算法以適應細粒度的一致性維護的研究.同時,隨著云環(huán)境的興起和移動端的普及,移動云環(huán)境下的研究也越來也受歡迎,接下來的工作,可以將文件協(xié)同管理應用到移動云環(huán)境下,并根據(jù)新的應用場景設計合理的算法來維護協(xié)同工作的一致性.