基于操作轉換的并發控制算法的研究

孫 敏 王瑞花

(山西大學計算機與信息技術學院 山西 太原 030006)

基于操作轉換的并發控制算法的研究

孫 敏 王瑞花

(山西大學計算機與信息技術學院 山西 太原 030006)

為解決協同圖形編輯中出現的結果不一致、因果不一致、操作意愿不一致和語意不一致問題，提出一種基于操作轉換的并發控制算法。該算法定義了操作序列的上下文有序、操作序列的上下文并發等概念。從協同編輯操作的預處理及實際執行時的操作轉換兩個方面，對基于上下文的操作轉換(COT)算法進行改進，并進行實例驗證分析。研究發現，其可有效地減少COT算法中存在的操作轉換冗余的問題。

并發控制 協同編輯 操作轉換 上下文有序

0 引 言

實時協同編輯支持地域上分散的用戶,通過網絡在同一時間對一共享文檔進行編輯,并保證所有操作都能正確執行。由于存在人為或網絡延遲等不可預料因素，若對各站點上協同操作的執行不加以控制，就可能會產生副本的不一致。協同圖形編輯是協同編輯的一個子研究領域，對編輯過程進行有效的并發控制和一致性維護是研究的重點。相應的方法除有令牌環機制、鎖機制和串行化機制等傳統方法之外，目前主流的有兩類：基于對象復制的多版本方法和基于操作轉換的方法[1]。

Kanawati等在文獻[2]中提出基于多版本技術的共享對象一致性保持算法。該算法將沖突操作的效果應用到同一操作對象的不同副本,無沖突操作應用到同一對象,從而使共享副本保持一致。楊君等提出基于版本復制的多版本模型[3],并設計多版本增創算法MVIC(Multiple Versions Incremental Creation)。之后許多研究人員在MVIC的基礎上進行了諸多改進。但是，隨著協同用戶的不斷增加、協同工作的逐漸深入，此類算法要求站點維系的版本數量也不斷增多，操作之間的沖突也趨于復雜。這對信息的管理和存儲提出挑戰，同時也使得最終版本的選擇策略趨于復雜，實時響應也變得有點不現實。

基于操作轉換的算法最早由Ellis等提出[4]，他提出分布式操作轉換算法 (dOPT)，是一種樂觀并發控制方法。該算法能很好地解決因果和操作意愿維護問題，但算法構造的轉換函數僅限于特定應用，存在不足。之后又出現大量對dOPT的改進算法。如Ressel等提出adOPTed算法[5-6]，是在 dOPT基礎上，加入L-轉換和多維交互圖，它能解決因果和操作意愿一致性維護，但并不能完全解決數據不一致問題。之后Sun等[7]提出GOT及其優化算法，即GOTO。GOT只針對簡單并發問題，通過設計包含轉換和排斥轉換兩種轉換函數來進行一致性維護，沒有解決偏并發問題，而GOTO則是在GOT的基礎上解決了偏并發問題。此外，還有SOCT2、SOCT3、TIBOT、 COT等操作轉換算法。COT算法是由Sun等提出的[8-9]。此算法通過引入操作上下文的概念來系統地表述和判斷協同操作間的關系，為操作副本的一致性維護提供了有效方法。

COT算法是目前在實際中應用最廣泛的算法。但是，COT算法仍然存在許多不足。本文就是對COT算法中存在的不足進行研究和改進。

1 相關理論基礎

1.1 基本關系描述

在協同編輯中，各個協同副本及操作之間存在的關系[8-9]如下所示：

1) 文檔狀態

表示某時刻某個站點副本的狀態，是一個動態變化的已執行操作的集合。

(1) 初始情況下,定義站點的文檔狀態DS={}；

(2) 當有操作O執行后，其文檔狀態為DS′=DS∪{org(O)}，其中org(O)是O的原始表示。

2) 操作上下文(C(O))

(1) 對于一個原始操作，C(O)=DS；

(2) 對于轉換操作O′，C(O′)=C(O)∪{org(O)}，其中O′=IT(O,Ox)。

3) 上下文依賴關系(上下文因果關系)

4) 上下文等價關系

給定兩個操作Oa和Ob以及其上下文C(Oa)和C(Ob)，稱操作Oa和Ob的上下文是等價的，當且僅當C(Oa)=C(Ob)。

1.2 協作編輯中的不一致問題

由于人為或網絡延遲等原因，各協同操作到達站點是無序的。若對各站點上操作的執行不加控制，就可能會產生副本不一致，如圖1所示。

圖1 協同站點間的并發操作

常見的不一致有以下4種[10]：

1) 結果不一致

假設O1、O2、O3的執行順序一定。在各個站點上，如果操作的執行順序沒有限制，就可能產生結果不一致。假設站點初始狀態為“A12Ba”，若O1:Insert(2,"C")，O2:Delete(3)，O3:Insert(4,"5")，則在站點1的執行結果為“A12B5a”，在站點2的執行結果為“A1C2B5”。

2) 因果不一致

由于網絡延時，難以保證操作信息按產生的順序到達各個站點。如果這些遠程操作在執行時不加限制，就可能產生不一致。

3) 操作意愿不一致

是指協作者期望達到的效果與實際產生的結果不同。仍以1)中數據為例，O2實際意義是刪除“A12Ba”中第三個位置上的“2”,但在站點1，實際刪除的是O1插入的“C”，這違背了協作者的意愿，產生不一致。

4) 語義不一致

在基于對象的協同圖形編輯中，圖形對象可能存在空間位置上的依賴關系，也可能存在某些相關屬性的依賴關系。如果操作執行時，違背了這些語義關系，就會產生不一致。如圖2所示，并發操作O1、O2，O1是改變橢圓1的大小，O2是改變橢圓2的位置。若操作的對象相互獨立，則O1、O2間不存在沖突。若在操作對象間建立聯系：兩個橢圓大小相等、位置平行，則O1、O2在兩個協同站點執行，雖能保證結果一致，但會違背語義約束，出現操作語義的不一致。

圖2 圖形對象間的依賴關系

2 COT算法及改進

基于操作轉換的算法通常分為兩部分[11]：高層的轉換控制算法和底層的轉換函數。當到達站點的遠程操作已就緒，根據操作間的上下文關系，轉換控制算法決定哪些操作需與此操作進行轉換，及應采用怎樣的轉換順序；轉換函數是通過對操作的各種參數進行分析，來確定將以何種方式進行操作間的轉換。而轉換屬性和條件則是介于轉換控制算法和具體的轉換函數之間，主要用來保證遠程操作的正確轉換和執行，以及最終版本的一致性維護。因此，對協同編輯中的并發控制和一致性維護進行研究，一般是從以上這兩個方面入手。

2.1 基于上下文的操作轉換算法COT

COT算法是基于上下文的操作轉換算法。在各個協同站點，都維護著一個文檔狀態DS，是已執行操作的集合。COT的基本思路是：本地操作立即執行，遠程操作O只有當操作上下文C(O)與接收站點的文檔狀態相同時，才能執行。因此，站點接收到O，首先檢測是否上下文就緒。若準備就緒，查看O的上下文與站點的文檔狀態是否一致，若一致，則O立即執行；否則需通過一定的轉換，將O的上下文上升到接收站點的文檔狀態，或者說，將O轉換為可執行的形式，然后執行。執行完后更新站點的文檔狀態。具體COT算法如下(算法1和算法2)：

算法1

COT(O,DS)

O′=transform(O,DS-C(O))；

執行O′；

DS=DS∪{org(O′)}

算法2

transform(O,CD)

循環直到CD={}；

從CD中選擇并移出Ox,滿足C(Ox)?C(O)；

transform(Ox,C(O)-C(Ox))；

O′=IT(O,Ox)；

C(O′)=C(O)∪{org(Ox)}

2.2 COT算法的不足及改進

2.2.1 COT算法的不足

定義2 假設存在兩個上下文有序的圖形編輯操作序列L1、L2，若C(L1)=C(L2)，稱L1、L2上下文并發，即L1‖L2。

定義3 假設存在圖形編輯操作序列L1、L2，若滿足條件L1‖L2，當且僅當C(L1)?L1=C(L2)?L2時，L1與L2等價，即L1≡L2(C(L1)?L1指在文檔狀態為C(L1)時順序執行L1中的操作)。

2.2.2COT算法的改進

在各個協同站點，都包含有如下的4個隊列：產生隊列GH、接收隊列RH、等待隊列WH及實際操作執行序列H(H中存放的是各個操作的最近轉換形式，由LLT轉換得到)。由操作轉換的基本思想可知，本地操作的優先權高于遠程操作。當某個遠程操作獲得優先權，進行轉換執行時，若有本地操作產生，則將其加入到GH及H中。當某個遠程操作執行完后，首先要查看執行站點的GH是否為空，若不為空，則將GH中的操作進行轉換和封裝，然后發送到各協同站點。

本文提出的并發控制算法分為兩部分：一部分是GH中的操作轉換封裝、遠程站點協同操作的接收及具體操作的執行，另一部分是對COT算法的改進，分別如算法3和算法4所示。

算法3

1) 本地操作的傳播

步驟1 若站點的RH為空，則直接將GH中的操作封裝為一個協同請求，傳輸到各個協同站點。

步驟2 若站點的RH不為空，則通過調用LLT(GH,RH)轉換，將GH中的操作和RH中的操作進行轉換，然后將GH中經轉換后的操作封裝為一個協同請求，傳輸到各個協同站點。

2) 遠程操作的接收

步驟1 查看協同請求中的操作L是否因果就緒，若沒有就緒，則將其加到WH的隊尾；否則轉步驟2。

步驟2 查看接收站點的RH是否為空，若為空，則查看協同請求中的操作序列L的上下文與DS的關系。若相等，則直接將L中的操作加到RH的隊尾，并更新H；若不相等，則通過調用ICOT(L,DS)，將操作序列L轉換為可執行形式，然后將其加到RH的隊尾，并更新H,然后轉步驟3。

步驟3 若RH非空，則直接調用ICOT(L,RH)。然后將轉換后的操作加到RH的隊尾，并更新H。

步驟4 一旦WH中的操作滿足因果就緒，則將其與協同請求中的操作先進行轉換結合，使其整體上下文有序(轉換過程仍通過ICOT實現)，然后轉步驟2。

算法4

LLT(L1,L2)：

算法5

SIT(O1,O2)：操作O1、O2是上下文等價

3) 遠程操作的執行

選中將要執行的操作O=RH[0]，如果GH為空，則直接執行操作O即可；若GH不為空，則調用LLT(O,GH)，然后再執行經過轉換后的操作。

ICOT算法，是對COT算法的改進，如算法6所示。

算法6

ICOT(L,ds)：

步驟1 判斷L的上下文與ds間的關系。若C(L)=ds，則操作序列保持不變，否則轉步驟2；

步驟2 獲得上下文差異集CD，CD=ds-C(L)，對于CD中的每一組操作，均是上下文有序的。循環選取CD中的每一組上下文有序的操作序列Q，并從H中獲得其操作序列的最近轉換形式Q′，選擇與L的上下文更接近的操作序列作為Q。若C(L)=C(Q)，則調用LLT(L,Q)；否則，令ds=C(Q)-C(L)，遞歸地調用ICOT(L,ds)。

2.3 實例分析

假設有7個協同操作，在各協作站點的執行順序以及操作之間的關系如圖3所示，初始的文檔狀態為空。假設在站點1，當接收遠程操作時，GH中的操作還沒有進行傳播，即GH不為空；在站點2和3，當接收遠程操作時，GH為空(假設遠程操作接收后不會執行)。

圖3 實例分析圖

通過對改進前后的算法進行對比分析可知，改進后的算法在協同操作向其他站點發送之前，以及遠程操作在接收之時，均進行了操作轉換。且發送和接收的并不是操作的原始形式，而是其轉換后的形式。通過這種預處理方式，可以有效地減少操作間轉換的重復，減少轉換的次數。

3 實驗及算法的正確性分析

3.1 實驗及分析比較

通過模擬實驗對COT算法和本文算法的性能進行比較分析。假設有9個協同操作，在各協同站點的執行順序以及各個操作之間的關系如圖4所示(初始文檔狀態為空)。在兩個算法中，任意操作的響應時間均由三部分構成：操作傳播時間、操作在遠程站點進行響應轉換的時間、操作執行的時間，其中操作進行轉換的時間起主導作用。故對兩個算法進行模擬實驗和性能分析，可以用操作執行時需轉換的次數來代替操作的響應時間(如圖5、圖6所示)。

圖4 模擬協同操作的執行

在站點2上的運行結果如圖5所示。

圖5 兩種算法中操作轉換次數的比較(站點2)

在站點3上的運行結果如圖6所示。

圖6 兩種算法中操作轉換次數的比較(站點3)

從實驗結果對比分析可知，遠程操作在轉換執行時，若采用COT算法，則隨著協同操作數的增加，操作執行時需轉換的次數增加幅度遠遠大于采用本文算法。因此，本文算法可大幅度減少操作轉換的次數，減少遠程操作的響應時間，增加實時協同編輯時的效率。

3.2 改進前后算法時間復雜度的比較

對于改進前后的算法，其核心操作是進行操作間的轉換，因此對改進前后算法的時間復雜度進行分析比較，也就是要對操作間的轉換次數進行比較分析。改進后的本文算法，通過引入操作序列上下文有序及并發的概念，有效地減少了操作間轉換的多次重復，減少了總的轉換次數。

1) 假設存在操作O1,O2,…,On，C(O1)=C(O2)=…=C(On),若采用COT進行操作的轉換執行，轉換次數[9]為：

若采用本文算法，在轉換的過程中，只有LLT轉換。轉換的次數為：T(n)=n-1。

2) 假設存在兩組上下文有序序列S1=O1,1,O1,2,…,O1,n、S2=O2,1,O2,2,…,O2,n,S1和S2上下文并發。若采用COT對S2中的任一操作與S1中的操作進行轉換執行，轉換的次數為[9]：

若采用本文算法，在轉換中采用LLT和SIT轉換，進行轉換的次數為：T(n,m)=2(m-1)×n+(n+m-1)。

對改進前后算法中有代表性的兩類操作間的轉換進行比較分析，理論上證明改進后的算法能有效地減少操作之間的轉換次數，且所減少的轉換次數均是COT算法中的冗余轉換。

3.3 本文算法中操作的正確執行和轉換

在COT算法中引入操作的上下文，是方便對操作的正確執行和轉換進行統一管理。一個操作能正確執行，需滿足:其定義上下文(操作產生時的文檔狀態)與執行上下文(操作執行時的文檔狀態)是相等的。兩個操作能正確轉換，則兩個操作需是上下文等價的。本文算法延續使用了操作的上下文，為保證改進后算法中的并發操作能夠正確執行和轉換[10]，在本文算法中，真正只用到了LLT和SIT轉換。因此只要LLT轉換滿足正確執行和轉換的條件，那么本文算法中也同樣滿足條件。

4 結 語

本文針對在協同編輯中遇到的4種常見的不一致性問題進行闡述，對COT算法中存在的不足進行分析，并在此基礎上，從兩個方面進行改進。改進后的算法可有效地減少操作執行時轉換的次數。但是，前文介紹的語義不一致問題沒有解決，且在協同圖形編輯中，對于圖形編輯操作，有許多的操作是可以合并的，例如一個用戶對同一圖形對象的位置進行多次移動的操作，是可以合并為一個操作的。若在操作進行傳播前能對這類型的操作進行一定的預處理，可以進一步減少轉換的次數，提高協作的效率。怎樣使得語義得到一致性維護，什么樣的操作是可合并的操作，應對這些可合并的操作進行怎樣的合并處理，將是下一步要研究的重點。

[1] 薛良貴. 協同圖形編輯系統中操作合并的研究[D]. 廣州：華南理工大學, 2010.

[2]KanawatiR.LICRA:Areplicated-datamanagementalgorithmfordistributedsynchronousgroupwareapplication[J].ParallelComputing,1997,22(13):1733-1746.

[3] 楊君, 竇萬峰. 一種新的多版本增創算法[J]. 計算機學報, 2008, 31(4):702-710.

[4]EllisCA,GibbsSJ.Concurrencycontrolingroupwaresystems[N].AcmSigmodRecord.ACM,1989,18(2): 399-407.

[5]ResselM,Nitsche-RuhlandD,Gunzenh?userR.Anintegrating,transformation-orientedapproachtoconcurrencycontrolandundoingroupeditors[C]//Proceedingsofthe1996ACMConferenceonComputerSupportedCooperativeWork.ACM,1996:288-297.

[6] 廖斌, 何發智, 荊樹旭. 實時協同工作系統中操作轉換算法綜述[J]. 計算機研究與發展, 2007, 44(2):326-333.

[7]SunD,SunC.Operationcontextandcontext-basedoperationaltransformation[C]//Proceedingsofthe2006 20thAnniversaryConferenceonComputerSupportedCooperativeWork.ACM,2006:279-288.

[8]SunD,SunC.Context-basedoperationaltransformationindistributedcollaborativeeditingsystems[J].IEEETransactionsonParallelandDistributedSystems, 2009, 20(10): 1454-1470.

[9] 許堅, 姜曉峰, 張坤．基于圖形對象的一致性維護問題的研究[J]. 計算機應用與軟件, 2012, 29(2): 261-265.

[10]Sun,C.OTFAQ:OperationalTransformationFrequentlyAskedQuestionsandAnswers[EB/OL].http://www3.ntu.edu.sg/home/czsun/projects/otfaq/.[11]SunC,WenH,FanH.Operationaltransformationfororthogonalconflictresolutioninreal-timecollaborative2deditingsystems[C]//ProceedingsoftheACM2012ConferenceonComputerSupportedCooperativeWork.ACM, 2012:1391-1400.

[12]Agustina,SunC,XuD.Operationaltransformationfordependencyconflictresolutioninreal-timecollaborative3Ddesignsystems[C]//ProceedingsoftheACM2012conferenceonComputerSupportedCooperativeWork.ACM, 2012:1401-1410.

[13]Agustina,SunC.Dependency-conflictdetectioninreal-timecollaborative3Ddesignsystems[C]//Proceedingsofthe2013ConferenceonComputerSupportedCooperativeWork.ACM, 2013:715-728.

[14]XuY,SunC,LiM.Achievingconvergenceinoperationaltransformation:conditions,mechanismsandsystems[C]//Proceedingsofthe17thACMConferenceonComputerSupportedCooperativeWork&SocialComputing.ACM, 2014: 505-518.

[15] 楊永濤, 黃國言.CSCW環境下協同設計并發控制算法的研究[J]. 現代計算機: 中旬刊, 2014(4): 16-21.

RESEARCH ON CONCURRENT CONTROL ALGORITHM BASED ON OPERATIONALTRANSFORMATION

Sun Min Wang Ruihua

(SchoolofComputerandInformationTechnology,ShanxiUniversity,Taiyuan030006,Shanxi,China)

To solve the inconsistency problem about results, causality, operational intention and semantics in collaborative graphic editing, a concurrent control algorithm based on operational transformation is proposed. The algorithm defines the conceptions about the context order, the concurrency of operation sequence, etc. From preprocess of collaborative editing and operational transformation in cooperative editing operation, the context-based operational transformation (COT) algorithm is improved. After verifying and analyzing the instance, it is found that the redundant problem in operation transformation in COT algorithm can be effectively reduced.

Concurrent control Collaborative editing Operational transformation Context in order

2015-09-20。山西省科技基礎條件平臺建設項目(2014091004-0105)；山西省高等學校教學改革重點項目(J2013010)。孫敏，副教授，主研領域：計算機網絡。王瑞花，碩士生。

TP391

A

10.3969/j.issn.1000-386x.2017.01.048