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

高麗萍,陶長青

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

1 引 言

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

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

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

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

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

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

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

2 相關工作

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

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

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

3 數據模型和操作模型

3.1 基本數據結構

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

3.2 基本定義

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

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

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

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

定義2.優先級(P)

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

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

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

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

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

定義5.兼容關系(?)

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

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

操作的唯一標識符是一個三元組,其中s代表站點間進行的會話的標識符,sumsv代表操作攜帶的狀態向量的總和,site代表操作產生的站點的標識符.當滿足以下情況時,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)

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

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

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

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

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

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

4.1 操作沖突檢測

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

表1 操作間的沖突關系表
Table 1 Conflict relationship table between operations

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

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

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

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

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

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

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

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

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

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

根據以上操作對之間的關系分析設計檢測函數如算法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 操作沖突解決

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

1)兼容關系:所有操作的效果都應得到實現;

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

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

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

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

算法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,執行O1,重新執行O2,并將操作O1鏈接到操作O2的前面;否則,直接將操作O2鏈接到操作O1的右側.

非依賴沖突關系解決方案:

算法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屬于非依賴沖突關系,若操作O1的id小與操作O2的id,則對操作O2進行操作轉換,并將操作O1鏈接到操作O2的前面,否則,撤銷操作O1,執行操作O2,并對操作O1 鏈接到操作O2的右側.

算法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,針對非依賴性操作,不可避免的會出現操作轉換,該算法就是對其中的操作做出相應的操作轉換.

兼容操作關系解決方案:

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

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

4.3 本地操作集成過程

當本地操作產生時,直接執行,并將該操作直接鏈接到雙鏈表的后面,若接收到一個遠程操作,則找到它的目標操作,并檢測是否存在與它具有相同的目標操作的操作,以及和它們的關系.并根據它們的關系確定它們在雙鏈表中正確的位置.本地操作執行過程如算法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 遠程操作集成過程

遠程操作執行過程如算法7所示.

在算法7中,當集成遠程操作O時,需要在雙鏈表中找到目標操作,若目標操作后有操作存在,則需要檢測該操作與操作O的關系,并找到操作O在雙鏈表中的正確的位置,算法中引用的函數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是根據狀態向量找到并發操作,并根據并發操作間的關系,找到雙鏈表中操作正確的鏈接位置,若并發操作間為依賴沖突關系,則根據操作對象的依賴關系確定位置,若操作間為非依賴沖突關系,則進行合理的操作轉換并確定位置,若并發操作間為兼容關系,則根據操作的唯一標識符確定并發操作的執行順序和在雙鏈表中的正確的位置.

5 云環境下文件實時協同管理的一致性維護

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

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

算法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的當前狀態向量,Hi代表存放全局唯一標識符的哈希表.

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

算法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 實例分析

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

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

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

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

圖3 協作工作后各站點維護的文本狀態圖Fig.3 State diagram maintained by each site after collaborative work

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

7 效率分析

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

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

8 正確性證明

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

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

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

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

假設當前的雙鏈表為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被執行并鏈接到操作Oi的后面.此時雙鏈表為L1=O1-O2-…-Ok-Oi-Oj-On.

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

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

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

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

假設當前的雙鏈表為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被執行并鏈接到操作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操作被執行并重新執行操作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,無論以什么順序執行,兩鏈表中的操作的順序都是相同的.

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

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

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

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

若OiD(Oi)>OiD(Oj),則操作Oj相對操作Oi做操作轉換得到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為更新操作,則直接執行操作Oi并將操作Oi鏈接到Oj的后面,此時的雙鏈表為L1′=O1-O2-…-Ok-Oj-Oi-…-On.

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

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

若OiD(Oi)

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

定理2.所提出的方法能夠實現意圖維護

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

9 總結與展望

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