二維表格實時協同編輯系統的一致性維護

魏 赟,宗 旭,高麗萍,2

1(上海理工大學 光電信息與計算機工程學院,上海 200093)

2(復旦大學 上海數據科學重點實驗室,上海 200093)

0 引 言

隨著分布式計算系統的發展,大量的協同系統被開發出來,并越來越多地被應用到現實世界中,協作應用程序影響了社會變革,吸引了學術研究人員和行業開發人員的研究和探索.

協同編輯作為CSCW(Computer Supported Cooperative Work)中最重要的領域,通過在協作用戶之間交換專業知識,提高了共享任務的質量和效率.同時,協同編輯系統支持和諧的人機交互,允許地理位置分散的用戶同時編輯共享文檔的任何部分,并且不會相互阻塞.

電子表格是應用最廣泛的計算機應用程序之一,金融行業、商業組織和政府以及日常生活中的普通人都經常使用它們.對電子表格和基于表格的文檔進行實時協同編輯的需求早已得到學術界和工業界的認可.近些年,隨著大數據和云計算的興起,電子表格在數據分析領域擔任著越來越重要的角色,電子表格協同編輯系統越來越趨向于大規模化,同時,這也帶來了一些不小的技術挑戰:一個是大規模協作中不可避免的會發生大量正交沖突問題,這給一致性維護帶來了更大的難度;另一個是對計算性能有很高的要求,這是協同編輯成功的關鍵因素.已發布的支持二維表格的協同編輯系統設計復雜,效率低下,不適合大規模的協同編輯[1,2].

總之,在大數據和云計算時代,如何以更高的效率解決電子表格中的沖突是大規模協同系統面臨的主要挑戰.因此,為電子表格協同編輯系統探索和研究基于CRDT的新同步技術是必要的.

針對以上需求,本文提出了一種新的基于CRDT的二維電子表格協同編輯方法.1)定義了操作的正交沖突關系、一維沖突關系、互斥關系和相容關系;2)基于操作之間的關系,設計了沖突消解方案,用以維護各個站點副本的一致性,并保留協作用戶的意圖;3)從理論上分析了時間復雜度和空間復雜度;4)通過案例分析、理論論證和構建原型系統驗證了該方法的正確性和可行性.

1 相關工作

為了實現高響應性,協同編輯系統采用了完全復制的體系結構,這給一致性維護帶來了巨大挑戰[3,4].操作轉換算法(OT,Operation Transformation)[5-8]特別適合于一致性維護,并且已經被提出了近30年.OT算法的主要思想是,本地編輯操作一經產生就立即執行,然后傳播到遠程站點.遠程操作在執行之前需要針對并發的操作進行轉換,以便修復沖突分歧.

自Ellis等開發第一個OT算法以來,大多數已發布的OT算法僅支持基于字符的純文本操作,電子表格文檔作為一種非純文本的文檔形式,目前僅有少數幾篇文獻[9-11]解決了在電子表格上進行協同編輯的不一致問題.在文獻[9]中,二維電子表格表示為一系列行或列,然后將一維OT技術(控制算法和轉換函數)直接用于支持表格上的操作.但這種分層方法不能很好地擴展到具有大量行/列的表格,此外,文獻[9]中的技術也無法解決正交沖突[10]問題.在文獻[10]中,Sun等人首次指出二維電子表格協同編輯系統中存在特殊沖突問題——正交沖突,設計了一個多版本(MV,Multi-Version)位置,既保留了用戶的操作意圖,也實現了文檔的一致性維護,成功將OT從一維空間擴展到二維空間;但是在數據量非常龐大時,這種方法需要耗費相當大的空間來存儲每個版本,空間復雜度較高.文獻[11]在GOTO算法的基礎上進行了改進,支持表格文檔環境下的協同,但是對于Insert、Delete、Merge和Split操作間的16種并發情況,需要設計各自的轉換函數,算法極其復雜;且底層使用類似矩陣的結構來存儲表格,維護困難.

因為OT固有的復雜性,不適合大規模協作[1].近年來,另一類協同編輯算法CRDT[12-17]被提出,并逐漸成為協同計算和分布式計算領域的研究熱點.它的主要思想是設計可交換的并發操作,不再需要轉換,可以按任何順序執行并發操作;通過為所有操作對象分配唯一標識符(ID),將所有對象按總體順序放入抽象數據結構中.因此,CRDT算法可以保留協作用戶的操作意圖,并保證最終的一致性.

Lv等人[1]將協同編輯的原子操作從“字符”提升到“字符串”,大大降低了算法的時間復雜度,提升了協同的效率.Gao等人[18,19]提出了在大規模實時圖形協作編輯環境下的沖突消解方案.在對算法效率要求更高的移動環境下,Lv等人[20,21]基于CRDT提出了適用于移動設備的輕量級協同編輯算法,進一步拓展了CRDT在大數據時代的應用.這些工作通過理論和實驗證明了CRDT效率更高,更適用于大規模協作環境,在處理大規模數據時更有優勢.

目前,在二維電子表格協同編輯系統中,基于CRDT的研究很少,最主要的挑戰是如何保證共享電子表格的一致性,以及在大數據量情況下達到更高的效率.而現有的基于OT算法的電子表格協同編輯模型設計復雜,底層數據結構維護困難、效率低下,不適用于大規模協作,并且OT算法通過狀態向量(SV)來判斷并發操作,在協作用戶動態加入和退出的場景下效率極低,這是大規模的協同環境中不能被接受的.本文提出的算法跟傳統的OT算法相比,有很大的優勢.例如文獻[10]將COT改進后應用到表格協同場景下,在處理正交沖突時,需要額外調用一維沖突的轉換函數,并且在集成遠程操作時,需要對比操作歷史序列中的所有操作,進行操作轉換,這可能會產生無用的比對,浪費較多的系統資源和時間.本文提出的基于CRDT的算法根據唯一ID,能夠快速找到目標操作,減少無用比對,提高協同效率.

2 實時表格協同中的一致性維護

2.1 表格的操作關系

現有的研究表明,表格協同編輯系統的操作主要集中在3個基本問題上:單元格的插入、刪除和修改.為簡單清晰起見,本文中的操作僅限于單個單元格,但本文提出的解決方案可以拓展為插入/刪除任意數量的單元格(例如整行或整列).

操作的影響范圍表示為ER(O),是指操作O執行后直接或間接受到影響的單元格集合.如果O是行維度的,則ER(O)表示目標行中操作位置及其右側的所有單元格;如果O是列維度的,則ER(O)表示目標列中操作位置及其下方的所有單元格.如果兩個操作的影響范圍具有以下定義的共享單元格,則這兩個操作是重疊的.

定義1.重疊關系(#)

給定兩個操作Oi和Oj,當它們滿足ER(Oi)∩ER(Oj)≠{}時,Oi與Oj重疊,表示為Oi#Oj.

定義2.正交關系(⊥)

給定兩個操作Oi和Oj,若它們的操作維度不同,即Oi.dim≠Oj.dim,Oi與Oj正交,表示為Oi⊥Oj.

其中dim表示操作的維度,可以取兩個值之一:row(行)或col(列).行操作在目標行中具有從左向右(插入)或從右向左(刪除)的位移效果;列操作在目標列中具有從上到下(插入)或從下到上(刪除)的位移效果.

如果正交操作Oi和Oj是并發的(符號表示為Oi‖Oj),并且他們的影響范圍重疊,那么當它們以不同的順序執行時,可能會導致不一致的狀態,這種關系稱為正交(或二維)沖突,其定義如下:

定義3.正交(或二維)沖突(⊕)

給定兩個操作Oi和Oj,如果它們滿足以下條件,則認為Oi⊕Oj:

1)Oi⊥Oj;

2)Oi‖Oj;

3)Oi#Oj.

定義4.平行操作關系(∥)

給定兩個操作Oi和Oj,如果它們不是正交關系,則認為它們是平行的,表示為Oi∥Oj.

如果在同一行或者同一列中執行兩個并發操作,它們以不同的順序執行可能會導致文檔狀態的不一致,這兩個操作之間關系的稱為一維沖突,定義如下:

1)Oi∥Oj;

2)Oi‖Oj;

3)Oi#Oj.

定義6.互斥關系(?)

給定兩個操作Oi和Oj,根據它們的操作語義,如果只有一個能執行,則它們是互斥的,表示為Oi?Oj.

定義7.相容關系(⊙)

圖1 表格中操作之間的關系Fig.1 Relations among operations in a table

2.2 總體框架和基本思路

在介紹總體框架和方法之前,以下先介紹一些相關的定義和概念.

定義8.表格操作對象(O)

在表格協同編輯系統中,一個操作對象表示為O,它是一個12元組,其中:1)t是操作O的類型,它可能是插入(insert),刪除(delete)或修改(update);2)l是一個bool變量,它有兩個值true和false分別表示本地操作和遠程操作;3)key表示當前操作的唯一標識符;4)dim是一個表示操作維度的變量;5)(x,y)表示當前操作在表格中的位置坐標;6)content表示所操作單元格的內容;7)visible代表操作的狀態,當操作無效時值為0,否則值為1;8)pre_key代表前一個操作的標識符;9)指針prior用來指向雙鏈表中的前一個操作;10)指針用來指向雙鏈表中的下一個操作;11)link是一個指針用來鏈接雙鏈表與哈希表HT;12)s是操作執行時的文檔狀態.

定義9.(O)給定任意兩個操作Oi和Oj,當Oi在雙鏈表中的位置位于Oj之前時,OiOj.

定義10.操作的全序關系(O?)

給定任意3個操作Oi,Oj,Ok,若全部操作序列滿足以下條件,則它們之間符合全序關系:

1)OiOj或者OjOi或

2)OiOj,OjOk,那么OiOk

定義11.操作的唯一標識符(ID)

一個操作的ID是一個3元組,其中:

1)s是當前會話的標識符,它是一個全局自增的變量

2)ssv是一個操作的狀態向量之和

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

定義12.(IDO)給定兩個操作Oi和Oj,這兩個操作的ID被表示為IDOi和IDOj,若滿足以下條件,IDOiIDOj:

1)IDOi[s]

2)IDOi[s]=IDOj[s],IDOi[ssv]

3)IDOi[s]=IDOj[s],IDOi[ssv]=IDOj[ssv],IDOi[site]

整體框架如圖2所示,電子表格協同系統由多個協作站點組成,每個站點維護視圖(View)和模型(Model)兩個部分.View是前端顯示界面,協作人員在該界面直接進行操作和交互.Model由一個名為HT的hash表和一個雙鏈表組成,其中HT存儲操作與其在雙鏈表中位置關系的映射,使得能夠在O(1)時間內找到目標操作位置;雙鏈表按照一定的順序鏈接所有的本地和遠程操作,包括可見和不可見的操作,可見操作表示有效的可執行操作,不可見操作表示無效和不可執行的操作.

圖2 整體框架Fig.2 Whole framework

整體的控制流程如下.每個站點上的用戶可以隨時生成本地操作(Local Operations),同時也可以接收遠程操作(remote Ox).本地站點上生成一個操作時,該操作立即執行,然后將它直接連接到雙鏈表的末尾.當站點接收到遠程操作Ox時,應先HT在中找到Ox的目標操作.假設O4是目標操作,而O5與Ox具有相同的目標操作,且O5和Ox來自同一個狀態,則調用沖突檢測機制(ConflictDetection)來檢測四種關系.此時需要考慮4種情況:

1)若它們之間存在正交沖突關系,則進行一定的轉換達到一種聯合效果;

2)若它們之間存在一維沖突關系,則需要根據它們的依賴優先級和標識符決定執行順序;

3)若它們具有互斥關系,則它們的依賴優先級和標識符決定了該執行哪個操作;

4)若它們是相容關系,則根據標識符決定執行順序.

2.3 沖突消解

算法1介紹了如何解決兩個操作之間的正交沖突.O1表示已經執行的操作,O2表示要執行的遠程操作.根據兩個操作的ID決定它們的先后順序.

算法1.OrthogonalConflictResolve(O1⊕O2)

1.INPUT:O1⊕O2

2.ifID(O1)ID(O2) then

3. Transform(O2,O1)

4.O2is executed and linked afterO1

5.else

6.O1is undone,O2is executed

7. Transform(O1,O2)

8.O1is redone and linked afterO2

9.end if

在算法1中,操作O1和O2之間是正交沖突關系,為達到聯合效果,需要對操作進行轉換.算法2介紹了轉換的具體流程.如果O1是行維度插入,O2是列維度插入,那么在它們的交叉點上創建一個多版本位置Multi-Version(MV)position[10](第3行),MV位置中每個單元格都屬于一個特定維度.創建MV位置時,它有兩個初始單元格:一個被當前單元格占據,另一個先置為空,可以通過直接插入或間接移動單元格來填充該空白位置.接著復制(O1.x,O2.y+1)位置上的內容插入到(O1.x+1,O2.y)(第4行).第5～8行介紹的是其他各種情況的處理方案.

算法2.Transform(O2,O1)

1.INPUT:O2,O1,

2.ifO1.dim=row&&O1.t=insert&&O2.t=insetthen

3. create an MV position at(O1.x,O2.y)

4. copy the cell at position(O1.x,O2.y+1)and insert it to position(O1.x+1,O2.y)

5.else ifO1.dim=row&&O1.t=insert&&O2.t=deletethen

6. create an MV position at(O1.x,O2.y)

7. copy the cell at position(O1.x,O2.y+1)to position(O1.x-1,O2.y)

8.else …//other cases are omitted for conciseness

9.end if

算法3介紹了如何解決兩個操作之間的一維沖突.如果O1和O2的操作位置相同,那么需要進一步判斷兩個操作的類型,調整執行順序(第2～11行).否則根據和的重疊關系調整執行順序(第15～18行).

2.ifO1.(x,y)=O2.(x,y) then

3. ifO1.t=insert&&O2.t=insertthen

4. ifID(O1)ID(O2) then

5.O2is executed and linked afterO1

6. else

7.O1is undone,O2is executed

8.O1is redone and linked afterO2

9. end if

10. else if…//other cases are omitted for conciseness

11. end if

12.else

13. ifO2.(x,y)?ER(O1) then

14.O2is executed and linked afterO1

15. else

16.O2is undone,O2is executed

17.O2is redone and linked afterO2

18.end if

算法4介紹了如何解決兩個操作之間的互斥關系.根據ID判斷優先級,將優先級高的操作鏈接在前面,而優先級低的保存為墓碑鏈接在后面.

算法4.MutualExclusionResolve(O1?O2)

1.INPUT:O1?O2

2.ifID(O1)ID(O2) then

3.O2.visible=0,O2is not executed and linked afterO1

5.else

6.O1is undone,O2is executed

7.O1.visible=0,O1is linked afterO2

8.end if

算法5介紹了如何執行兩個相容操作.當O1.key小于O2.key時,直接執行O2并鏈接到O1后面,否則將O2鏈接到O1前面.

算法5.CompatibleResolve(O1⊙O2)

1.INPUT:O1⊙O2

2.ifID(O1)ID(O2) then

3.O2is executed and linked afterO1

4.else

5.O2is executed and linked beforeO1

6.end if

2.4 集成本地/遠程操作

算法6介紹了如何集成本地操作.如果目標操作不為空,則通過哈希表直接找到操作位置并鏈接在目標操作后(第8～10行);如果新一輪會話開啟,目標操作為空,那么需要判斷雙鏈表是否為空,若為空,直接將O鏈接到head后執行,否則鏈接到雙鏈表的末尾(第2～7行).

算法6.IntegrateLocal(O)

1.INPUT:O

2.ifO.pre_key==NULL then

3. ifhead==NULL then

4.Ois executed and linked next tohead

5. else

6.Ois executed and linked after tail by scanning the list one by one

7. end if

8.else

9.Pre=hash(O.pre_key),Ois double linked next toPre

10.end if

11.Ois broadcast to remote sites

算法7介紹了如何集成遠程操作O.在第2行中,通過唯一標識符直接找到O的目標操作,如果目標操作后有其余操作存在,那么需要依次判斷該操作與O的關系(第5～44行):當Next和O來自同一狀態時,調用相應函數解決沖突(第9～20行),否則逐一向后檢查每個操作直至首次遇到ID(Next第?ID(O)(21～23行).在第28-38行中,找到操作O的正確插入位置,如果存在沖突,調用相應函數來解決;否則將O鏈接到Next前面.之后繼續沿著雙鏈表向后判斷沖突(第41～43行).

算法7.IntegrateRemote(O)

1.INPUT:O

2.Tar=hash(O),Next=Tar,next

3.ifNext==NULL then

4.Ois executed and double linked afterTar

5.else

6. whileNext.key.s

7.Next=Next.next

8. end while

9. whileNext!=NULL &&ID(Next)ID(O) do

10. ifNext.s==O.s&&(Next,O)==Next⊕O&&Next.visible==1 then

11. if isExistMV(Next,O)==false then

12. Transform(Next⊕O)

13. end if

14.Next=Next.next,Continue

15. else ifNext.s==O.s&&(Next,O)==Next⊙O&&Next.visible==1 then

16.Next=Next.next,Continue

19. else ifNext.s==O.s&&(Next,O)==Next?O&&Next.visible==1 then

20. MutualExclusionResolve(Next?O)

21. else

22.Next=Next.Next,Continue

23. end if

24. end while

25. ifNext==NULL then

26.Ois executed and linked afterNext.prior

27. end if

28. ifID(O)ID(Next) then

29. ifNext.s==O.s&&(Next,O)==Next⊕O&&Next.visible==1 then

30. OrthogonalConflictResolve(Next,O)

34. MutualExclusionResolve(Next?O)

35. else ifNext.s==O.s&&(Next,O)==Next⊙O&&Next.visible==1 then

36. CompatibleResolve(O1⊙O2)

37. else

38.Ois executed double linked beforeNext

39. end if

40. end if

41. whileNext!=NULL do

42. detect and handle conflicts as above

43. end while

44.end if

3 正確性證明與復雜度分析

3.1 案例分析

為了驗證所提出方法的正確性和可行性,本文舉了一個綜合示例來解釋算法的執行過程.假設3個站點參與協同任務,并且存在ID[site1]

圖3 協作的綜合案例Fig.3 A comprehensive case of collaboration

在站點1,本地操作O1立即執行,L1=O1.當操作O2到達時,O1與O2是正交沖突關系,需要進行轉換,由于IDO1IDO2,所以將O2鏈接到O1后面.L1=O1-O2.接著O4到達,它與O1是相容關系,因為IDO1IDO4,又由于O2是O4的因操作,所以將O4鏈接到O2后面.L1=O1-O2-O4.當O3到達,其文本狀態與O1相同,依次向后進行沖突檢測,它與O1,O2均為相容關系,與O4是互斥關系,存在IDO4?IDO3,因此O4被撤銷,執行O3,并將O4鏈接在O3后面.L1=O1-O2-O3-O4.當O5到達,其目標操作為O3,因為O3是它的因操作且O3的狀態與O1相同,所以從O1開始向后進行沖突檢測,其與O1是一維沖突,根據算法3,操作O5的執行位置在O1的影響范圍內,所以撤銷O1后執行O5,再重新執行O1,O5與O2是正交沖突關系,但由于多版本位置已存在,不需要進行轉換,IDO4IDO5,因此O5鏈接在O4后面.L1=O1-O2-O3-O4-O5.

在站點2,本地操作O2和O4立即執行,L2=O2-O4.當O3到達,其與O2為相容關系,與O4為互斥關系,存在IDO3IDO4,因此撤銷O4,執行O3,此時L2=O2-O3-O4.當操作O5到達,它的目標操作為O2,與O2為正交沖突關系,因此進行轉換;O3是其因操作,存在IDO4IDO5,將O5鏈接到O4后面.L2=O2-O3-O4-O5.最后操作O1到達,其文本狀態與O2相同且IDO1IDO2,O1與O2為正交沖突關系,但此時多版本位置已存在,所以無需轉換,撤銷O2,執行O1后重新執行O2并將其鏈接在O1后面.L2=O1-O2-O3-O4-O5.

在站點3,本地操作O3和O5立即執行.L3=O3-O5.

當操作O2到達,O2與O3文本狀態相同,O3又是O5的因操作,所以依次與它們進行沖突檢測,O2與O3是相容關系,與O5是正交沖突關系,需要進行轉換,存在IDO2IDO3IDO5,因此O2鏈接在O3前面.L3=O2-O3-O5.當操作O4到達,其目標操作為O2,所以從O2開始依次向后進行沖突檢測,O2是O4的因操作,O3與O4為互斥關系,存在IDO4?IDO3,因此O4不執行,但將其鏈接在O3后面.L3=O2-O3-O4-O5.最后,操作O1到達站點3,其文本狀態與O2相同,且與O2是正交沖突關系,但此時多版本位置已存在,無需進行轉換,由于IDO1IDO2,所以先撤銷O2,接著執行O1,再重新執行O2,將O1鏈接到O2前面.L3=O1-O2-O3-O4-O5.

最終3個站點的操作序列是相同的:L1=L2=L3=O1-O2-O3-O4-O5.由圖3所示,3個站點執行結果狀態是一致的.

3.2 最終一致性和意圖保留

如果表格協同編輯系統符合以下兩個標準,則認為該系統是正確的:

定理1.最終一致性:當全部協作站點執行了所有操作后,不同站點間的文檔狀態是一致的.

證明：在表格協同編輯系統中,狀態相同的遠程操作可能會存在沖突,在下面的證明中,所有操作都是以相同狀態的遠程操作形式給出,此時需要考慮4種情況.

(1)對于兩個遠程操作Oi和Oj,它們是正交沖突關系.不論以任何順序執行,雙鏈表中的操作順序都是相同的.

假設當前雙鏈表為L=O1-O2-…Op-Oq-…-On,且Oi、Oj的目標操作均為Op.

1)若先接收到Oi,將Oi鏈接到Op后面,此時雙鏈表為L=O1-O2-…Op-Oi-Oq-…-On,然后Oj到達,需要考慮兩種情況.

若IDOiIDOj,則進行轉換后直接執行Oj并鏈接到Oi后面,此時雙鏈表為L1=O1-O2-…Op-Oi-Oj-Oq-…-On.

若IDOi?IDOj,則撤銷Oi,執行Oj,進行轉換后重新執行Oi并鏈接到Oj后面,此時雙鏈表為L2=O1-O2-…Op-Oj-Oi-Oq-…-On.

2)若先接收到Oj,將Oj鏈接到Op后面,此時雙鏈表為L=O1-O2-…Op-Oj-Oq-…-On,然后Oi到達,考慮兩種情況.

若IDOiIDOj,則撤銷Oj,執行Oi,進行轉換后重新執行Oj并鏈接到Oi后面,此時雙鏈表為L1′=O1-O2-…Op-Oi-Oj-Oq-…-On.

若IDOi?IDOj,則進行轉換后直接執行Oi并鏈接到Oj后面,此時雙鏈表為L2′=O1-O2-…Op-Oj-Oi-Oq-…-On.

由以上證明可知,雙鏈表L1和L1′相同,雙鏈表L2和L2′相同.

(2)對于兩個遠程操作Oi和Oj,它們是一維沖突關系.不論以任何順序執行,雙鏈表中的操作順序都是相同的.

假設當前雙鏈表為L=O1-O2-…Op-Oq-…-On,且Oi、Oj的目標操作均為Op.

1)若先接收到Oi,執行后將Oi鏈接到Op后面,此時雙鏈表為L=O1-O2-…Op-Oi-Oq-…-On,然后Oj到達,需要考慮兩種情況.

①若Oj和Oi的操作位置相同,此時有5種情況需要考慮.

若Oi為插入操作,Oj為插入操作,則通過判斷兩個操作的ID決定執行順序.此時雙鏈表為L1=O1-O2-…Op-Oi-Oj-Oq-…-On,或L1=O1-O2-…Op-Oj-Oi-Oq-…-On.

若Oi為插入操作,Oj為刪除操作,則撤銷Oi,執行Oj后再執行Oi并鏈接到Oj后面,此時雙鏈表為L2=O1-O2-…Op-Oj-Oi-Oq-…-On.

若Oi為插入操作,Oj為修改操作,則撤銷Oi,執行Oj后再執行Oi并鏈接到Oj后面,此時雙鏈表為L3=O1-O2-…Op-Oj-Oi-Oq-…-On.

若Oi為刪除操作,Oj為插入操作,直接執行Oj并鏈接到Oi后面,此時雙鏈表為L4=O1-O2-…Op-Oi-Oj-Oq-…-On.

若Oi為修改操作,Oj為插入操作,直接執行Oj并鏈接到Oi后面,此時雙鏈表為L5=O1-O2-…Op-Oi-Oj-Oq-…-On.

②若Oj和Oi的操作位置不同,此時有兩種情況需要考慮.

若Oj.(x,y)∈ER(Oi),則撤銷Oi執行Oj,再重新執行Oi并鏈接到Oj后面,此時雙鏈表為L6=O1-O2-…Op-Oj-Oi-Oq-…-On.

若Oj.(x,y)?ER(Oi),直接執行Oj并鏈接到Oi后面,此時雙鏈表為L7=O1-O2-…Op-Oi-Oj-Oq-…-On.

2)若先接收到Oj,將Oj鏈接到Op后面,此時雙鏈表為L=O1-O2-…Op-Oj-Oq-…-On,然后Oi到達,需要考慮兩種情況.

①若Oi和Oj的操作位置相同,此時有5種情況需要考慮.

證明過程同 1)中的①,分別得到L1′=O1-O2-…Op-Oi-Oj-Oq-…-On,或L1′=O1-O2-…Op-Oj-Oi-Oq-…-On;L2′=O1-O2-…Op-Oj-Oi-Oq-…-On;L3′=O1-O2-…Op-Oj-Oi-Oq-…-On;L4′=O1-O2-…Op-Oi-Oj-Oq-…-On;L5′=O1-O2-…Op-Oi-Oj-Oq-…-On;

②若Oi和Oj的操作位置不同,此時有兩種情況需要考慮.

證明過程同1)中的②,分別得到L6′=O1-O2-…Op-Oj-Oi-Oq-…-On;L7′=O1-O2-…Op-Oi-Oj-Oq-…-On.

由以上證明可知,L1=L1′,L2=L2′,L3=L3′,L4=L4′,L5=L5′,L6=L6′,L7=L7′.

(3)對于兩個遠程操作Oi和Oj,它們是互斥關系.不論以任何順序執行,雙鏈表中的操作順序都是相同的.

假設當前雙鏈表為L=O1-O2-…Op-Oq-…-On,且Oi、Oj的目標操作均為Op.

1)若先接收到Oi,執行后將Oi鏈接到Op后面,此時雙鏈表為L=O1-O2-…Op-Oi-Oq-…-On,然后Oj到達,根據ID判斷操作的執行順序,且優先級低的操作不執行,保存為墓碑鏈接到雙鏈表中.此時雙鏈表為L1=O1-O2-…Op-Oi-Oj--Oq-…-On,或L2=O1-O2-…Op-Oj-Oi--Oq-…-On.

2)若先接收到Oj,執行后將Oj鏈接到Op后面,此時雙鏈表為L=O1-O2-…Op-Oj-Oq-…-On,然后Oi到達,根據ID判斷操作在雙鏈表中的位置,且優先級低的操作不執行,保存為墓碑鏈接到雙鏈表中.此時雙鏈表為L1′=O1-O2-…Op-Oi-Oj--Oq-…-On,或L2′=O1-O2-…Op-Oj-Oi--Oq-…-On.

由以上證明可知,L1=L1′,L2=L2′.

(4)對于兩個遠程操作Oi和Oj,它們是相容關系.不論以任何順序執行,雙鏈表中的操作順序都是相同的.

證明過程同(3),根據ID判斷兩個操作在雙鏈表中的執行位置.

由以上證明可知,本文所提出的方法能夠確保每個站點都維護相同的歷史操作序列,最終取得一致的文本狀態.

定理2.意圖保留:需要在所有協作站點盡可能保留并發操作的效果.

證明:基于上述的最終一致性證明,遠程操作的效果都盡可能得到了保留.在此考慮4種情況:

1)正交沖突操作:采用聯合效果[10](Union Effect)保留沖突操作的影響;

2)一維沖突操作:兩個操作的影響都得到了保留;

3)互斥操作:只需保留其中一個操作的效果;

4)相容操作:保留了所有操作的效果.

因此本文所提出的方法可以實現用戶的意圖保留.

3.3 復雜度分析

時間復雜度:如算法6所示,由于使用唯一ID和哈希表來搜索前置操作,所以在集成本地操作時,最佳情況的時間復雜度為O(1);而當一個新會話開始時,需要從頭至尾掃描雙鏈表,找到上一個會話中的最后一個操作,這是最壞情況,時間復雜度為O(n),其中代表此時站點中雙鏈表上的所有操作數.在集成遠程操作時,如算法7所示,最佳情況下的時間復雜度為O(1),在這種情況下,使用ID和哈希表直接找到目標操作,由于目標操作后沒有其他操作,該遠程操作可以直接鏈接在目標操作的后面;在最壞的情況下,遠程操作到達時需要從目標操作開始依次向后判斷沖突和查找正確的執行位置,此時的時間復雜度為O(m),其中m是目標操作后面鏈接的操作數.

空間復雜度:本文所提出的方法中,每個操作都是一個12元組,假設它的長度為L,每個站點上的雙鏈表中有n個操作,則空間復雜度為O(L×n).同時每個站點還需要一個哈希表來提高集成速度,而哈希表的空間開銷與雙鏈表是相同的,所以總的空間復雜度為O(2L×n).

4 原型系統

為了驗證所提出算法的合理性以及正確性,本文基于IntelliJ IDEA平臺開發了Web端的二維表格協同編輯系統(Co-Table).其前端使用LuckySheet開源框架,后端采用輕量級框架SpringBoot搭建,并且采用WebSocket全雙工通信協議進行持久的信息傳輸.

如圖4是客戶端的編輯界面,插入、刪除、修改等基本功能都是基于LuckySheet實現的,為了實現協同編輯,其后臺使用日志記錄所有用戶以及他們的操作,然后將這些操作通過WebSocket協議傳播到遠程站點,遠程站點接收到操作后進行判斷和沖突消解.如圖5所示,后臺日志還記錄了用戶的連接和斷開以及當前參與協同的用戶數目.

圖4 前端界面Fig.4 Front-end interface

圖5 協作用戶與操作日志Fig.5 Collaboration users and operation logs

5 總結與展望

本文提出了一種新的基于CRDT的二維電子表格協同編輯一致性維護方案.首先定義了操作之間的4種關系;其次,根據操作之間的關系,設計集成本地和遠程操作的算法,維護各個站點間表格文檔的一致性;接著,從理論上分析了該方案的時間復雜度和空間復雜度;最后,通過案例分析、理論論證以及構建原型系統,驗證了所提出的方法能夠有效解決沖突、保留用戶意圖,實現最終的文本一致.

在未來的研究中,我們將繼續探索以下方面:1)表格文檔中的操作不僅限于簡單的插入和刪除,后續將繼續研究單元格合并和拆分等操作的協同;2)撤銷是表格文檔中很重要的功能,將探索Undo/Redo協同的實現;3)隨著移動端的普及和云計算的興起,我們將探索移動云環境下協同的一致性維護.