移動云環境下的實時協同編程機制及策略研究
2020-05-12 09:09:44高麗萍趙春芽
小型微型計算機系統 2020年3期
高麗萍，趙春芽
1(上海理工大學 光電信息與計算機工程學院，上海 200093)
2(復旦大學 上海市數據科學重點實驗室，上海 200093)
E-mail：lipinggao@usst.edu.cn；450190073@qq.com
1 引 言
近些年來軟件行業的繁榮發展，移動云計算是當今的主要流行趨勢，移動資源，云計算和云服務為協同交互應用帶來了巨大挑戰.同時網絡技術的發展使大量的協同編輯應用程序得到了很大的開發，同時軟件規模和復雜度也在提高，將計算機支持的協同工作與編程環境相結合是協同工作中重要的研究領域，協同編程不僅能提高工作效率，還能使各個站點的用戶更方便工作.過去的幾十年，已經有許多的協同軟件研究者致力于協同編程軟件或是協同編程方法的研究上，研發了一系列的協同開發工具.協同編輯工具在近年來得到了廣泛的應用，在很多企業中也在使用協同辦公軟件很多的應用程序也廣泛支持異步開發，比如wikis和版本控制系統.或者是同步協作，如分布式實時協作編輯器，協同設計工具或云集成開發環境.
樂觀復制[5]，即副本數據全部復制結構，是過去在集中式架構(Jupiter[14]算法和TIPs[15]算法)，和一系列協同編輯中廣泛采用的方法，這能夠有效的解決分布式系統中網絡延遲問題和數據一致性問題，如GoogleDrive(1)“Google drive,”https://drive.google.com.和Docs(2)Google Docs[ED/OL)：//docs.google.com是在全部復制的基礎上使用操作轉換來保持一致性.但是在大規模數據并發下，比如Xia[4]提出的部分復制的概念去解決評論系統下的數據一致性，因為評論節點之間是樹形結構，該部分復制的思想是如果對一個評論節點進行操作，需要把該節點的父節點和兄弟節點加載到本地，稱之為骨架節點，在服務器端使用一個副本結構對本地骨架節點進行數據跟蹤，用來完成對本地數據的數據同步和增量更新.
傳統的協同編程體系中，在數據部分復制方面和控制語義沖突方面還有很多能夠優化的地方.本文針對在云環境下，采用新的基于TIPs[1]的集中式架構進行操作轉換，并根據Fan提出的共享鎖[5]的結論來控制語義沖突的發生，論文整體結構如下：第二部分介紹了協同編程的研究背景及相關工作；第三部分是分析了在云環境下協同編程模型；第四部分提出了在服務器端進行的操作轉換和沖突解決方案；第五部分對相應的操作轉換算法進行可行性分析和評估；第六部分敘述了CloudCode原型系統設計的相關技術；第七部分進行總結和對未來的展望.
2 相關工作
在近些年來的研究工作中，協同編輯技術被大量的開發和應用.最常用的一致性維護技術有操作轉換(Operation Transformation，OT)[6，7，9]技術和地址空間轉換(Address Space Transformation，AST)[8]技術，以上兩種技術最初都是在點對點的協同交互應用中提出的，在實時編輯時每個用戶能夠立即看到其他用戶的改變.Xia[4]提出了適合在移動云環境下應用的地址空間轉換方法，并將這一方法運用到了評論系統中.根據操作轉換，可以對并發操作做出合并，包括Ellis和Gibbs[17]在文獻中提出的DOPT算法，Sun和Ellis[7]提出的GOT和GOTO算法，Sun[11]在文獻中提出的COT算法等.
操作轉換技術(OT)適合于非線性文檔中，例如Ng A，Sun C[9]在文獻中提出的實現實時文件管理系統的一致性維護.SUN[11]等在文獻中提出使用OT算法解決了3D系統中文檔依賴沖突的問題.Fu[18]等人在文獻中提出改進GOTO算法以支持表格文檔協同編輯下的一致性維護.版本控制[12]，是在團隊協同開發中使用的，根據每一個時刻指針所指向的版本，可以恢復到原來的版本，可以有效的對代碼進行整合.
FAN和SUN在文獻[18]中提出的DAL技術能夠保證在實時協同編程環境中避免語義沖突.與OT不同的是：該方法采用悲觀鎖的方式，自動對編輯的文檔內容進行加鎖，拒絕其他用戶的編輯操作，這種悲觀鎖的方式在實際應用中是不合理的，因為這種悲觀鎖的方式假設加鎖的部分沒有覆蓋部分，還假設動態依賴圖是靜止不變的，而在實際編程條件下代碼節點之間的依賴關系都是會發生變化的.后來又提出了三種共享鎖(shared-locking on common depended regions)[5]，這種方法能夠保證高的響應性，有效性和一致性，并能在實時編程環境中阻止語義沖突發生.
Nieminen等人研究的CoRED[13]系統指的是基于瀏覽器上的對Java應用程序進行實時協同開發，不僅能夠對代碼詞匯進行突出顯示和縮進，還可以進行錯誤檢測和代碼自動生成.You[19]提出的協同編程環境下基于CAS并發處理思想的語義沖突消解方法，其核心思想是通過對目標對象設定期望值，若目標對象的期望值由于并發更改發生變化時，則操作不能執行.
Jupiter[14]算法和TIPs[15]算法是目前支持集中式架構的算法，其中JupiterOT算法是第一個將操作轉換用在C/S結構中的，它使用二維狀態向量來跟蹤轉換路徑，最終數據狀態取決于客戶端與服務器同步的順序，JupiterOT無法保證會采用正確的轉換路徑并產生正確一致的最終狀態，因此使用這個算法的最終結果是不能夠收斂的.
在移動云環境下的一致性維護研究中，Gao[1]提出的實時協同圖形編輯，對TIPs算法進行了改進，原本TIPs算法采用HTTP協議，服務器端不能夠主動為客戶端發送消息，服務器和客戶端之間的同步需要設置一定的時間間隔，對于在編程中，時間間隔的大小不容易控制，間隔過小會不利于編程效果，過大的話不能夠很好的做出響應，這會造成很多帶寬資源的浪費，通過實驗能夠證明，使用改進之后的TIPs算法能夠使協同編輯效率提高.
本文將對樹形評論節點的部分復制[4]思想進行改進，在實際編程中，如果對一個代碼節點進行編輯，這個代碼節點只與它的依賴節點有關系，所以只需要將依賴節點加載到客戶端即可，我們提出了基于依賴關系的部分復制(Partial replication based on dependency)，經過一系列的實驗證明了可行性，并得到了很好的效果.數據部分如果采取全復制的方式會嚴重浪費帶寬資源，客戶端也不能得到快速響應，在協同編程中，更適合采用部分復制的方式.但是為了提高快速響應的能力和支持離線操作中數據一致性問題，采用部分數據復制分方法，這對協同編程并在解決語義沖突方面有很大的挑戰.
根據Fan[5]等人提出的共享鎖的結論進行并發操作，可以有效的防止語義沖突.根據Fan的結論，每個客戶端只有滿足下面的條件，并發操作才能得到許可：
1.編輯操作是在開放域中；
2.編輯操作是在一個基本域中;
該基本區域被本地的程序員作為工作區域已經加鎖；或者是該基本域沒有被其他合作的程序員加鎖，并且它的依賴域沒有被其他程序員作為工作區域加鎖.
可以得出，當編輯操作發生在同一個節點上或者并發操作所對應的節點之間有依賴關系時，才有可能發生語義沖突.而對于沒有依賴或間接依賴關系的并發沖突的代碼一致性維護，相當于文本的一致性維護，在前面很多文獻中已經有很多的解決方法了，本文不作為重點研究.
根據代碼節點之間復雜動態依賴關系，運用云計算環境，在部分復制的基礎上，進行一致性維護和解決語義沖突有很大的挑戰性.移動云計算能為客戶提供低成本，可靠和穩定的服務，云環境下的新的架構為協同編輯提出了很多新的挑戰.
3 云環境下協實時同編程系統的設計與分析
3.1 基于協同編程的技術挑戰
在協同編程模型中如果采用全復制結構，由于本地資源帶寬的限制，會浪費很多不必要的資源.移動云計算，就是要將移動終端設備的龐大計算量通過網絡傳輸移動到計算中心，通過云計算不僅能滿足用戶高的性能體驗，還能滿足數據量的需求.
1.架構的變化.在移動云環境下，為了充分利用良好的跨平臺性，一般都是采用B/S模式，移動云環境下的客戶端主要是移動設備(手機或筆記本電腦)，服務器端一般是分布式體系架構，具有高擴展，高效率，高可靠等優點.這里我們采用分布式服務框架Zookeeper來管理分布式環境中的數據.
2.如何對所需要的編輯節點進行部分復制并對本地數據節點進行動態更新.傳統的協同編輯都是采用全復制來解決高的響應性.在移動云環境下，采用部分復制的方法對本地數據進行動態一致性的維護，這種方式能夠有效的節約本地用戶的存儲資源并減少能量消耗.
3.如何在部分復制的情況下，采用不加鎖的方式，動態的實現客戶端和服務器端的數據同步，同時維持高的響應性并保證不發生語義沖突.
4.如何設計簡單高效的算法進行交互，滿足用戶動態加入或離開，并保證移動端和服務器端的有效擴展.
3.2 數據結構和基本定義
操作轉換能夠使用戶在不加鎖沒有阻礙的情況下修改本地副本的任何部分，在協同編程中，可以通過進一步的改進，操作轉換算法允許用戶的并發操作按照任意順序執行，并發沖突發生時，會按照規定的操作轉換算法自動的解決和融合并發操作沖突.如圖1所示，對這個list類中的代碼節點用連續的字母表示，字母之間的連接方向就表示代碼節點之間的依賴關系.
圖1 代碼節點之間的關系圖
定義1.代碼域(Code Area，CA)和開放域(Open Area，OA)
在一系列源代碼組成的有語法意義的文檔部分稱為代碼域(CA)，代碼文檔之外的空白部分都是開放域(OA).
定義2.依賴關系
代碼節點(Node)之間的依賴關系是動態變化的，依賴圖之間的依賴關系代表代碼節點之間的依賴關系.節點之間有直接依賴關系和間接依賴關系，例如C->B，B->A是直接依賴關系，C->A是間接依賴關系.
定義3.兼容關系(⊙)
代碼編輯中的兼容關系表現為：1.并發操作發生在一對有依賴關系的節點上時，都是按照自己的意愿進行編輯的，且沒有出現語義沖突；2.或者是并發操作發生在沒有依賴關系的節點上；3.或者是并發操作所發生的節點有公共依賴節點.4.或者是并發操作都是發生在開放域(OA).
表1 并發操作發生在相互依賴的節點上如(B->A)情況時，會產生的沖突和兼容
表2 并發操作發生在同一個節點時，會產生的沖突和兼容
定義4.相互排斥關系(?)
如表1、表2所示，如果多個用戶并發對同一個節點進行操作，或者用戶對有依賴關系的節點進行并發編輯也有可能發生語義沖突，相互排斥的關系不容易進行意愿融合，考慮到在實際編程的效果，出現相互排斥的關系時，系統會給產生并發操作的用戶發送消息機制，根據返回的信息決定是保留哪個版本.下面的部分我們會詳細說明，在并發操作發生在一個節點上，或發生在相互依賴的節點上的情況下，哪些情況可以進行意愿融合，哪些情況是通過發送消息機制來決定.
定義5.代碼節點的數據結構(Node Structure)
每個代碼節點(Node)包含的信息有唯一的位置標識符(AD)，直接依賴的節點集合rootNode，對應代碼域的文本內容(Code Content)，被復制到客戶端的代碼類型Copy Type，如果該節點是工作節點就表示為WN，如果是依賴節點表示為DN，一個節點表示為{N | N=
定義6.全局唯一標識符Identifier(ID)
客戶端對每個節點的操作O都會有一個標識符ID，這個標識符是一個二元組
定義7.操作類型(operate type)
編輯操作的類型和相關函數：
Create( )：表示創建相應的代碼節點
Delete()：表示刪除指定的代碼節點
Update()：表示對指定節點進行修改或更新
Move()：表示移動代碼節點到一個新的位置.
定義8.操作(operate )
將客戶端的一個操作O定義為四元組
3.3 部分復制
本文提出了基于依賴關系的部分復制(Partial replication based on dependency).在中心服務器端，整個完整代碼節點目錄會以主副本(Main Replica)的形式存在，客戶端能夠請求得到部分節點，在網頁上進行編輯，程序編譯和運行需要在服務器端進行，再將結果返回給用戶，這樣保證了移動端的運行效率，使能夠隨時隨地在移動端進行編輯.當一個客戶端加入這個編輯會話中時，有可能只需要編輯代碼域的其中一部分，根據程序編程特點，在一個類中，基本包括兩種語句，一種是定義，一種是函數，我們只需要把所編輯節點的依賴節點復制到本地.如圖2所示，在這個依賴圖中，如果對h節點進行編輯操作，為了保持節點之間的依賴關系，我們在復制服務器端副本的時候，需要把相關加點a和b都加載到本地，在編程的過程中有可能還會需要其他依賴節點，這就需要對本地數據進行增量更新，可以再次請求所需要的節點，而這不需要把整個代碼文件全部下載下來，這會有利于節省本地的存儲資源.這里需要注意的是，當一個代碼節點被復制時，需要將記錄在該節點的緩沖區的操作，也一同復制，便于得到最新的代碼版本.
圖2 代碼節點的簡單依賴關系結構
算法1.DetectTargetedNode(Node)
1.M={ }
2.If Node.rootNode is null
3. M=M+Node.AD
4. Return M
5.For item in Node.rootNode
6. Return M+DetectTargetedNode(item).AD
7.End
算法1的目的是：獲取目標節點和依賴節點，即客戶端所需要的所有的節點集合M.根據代碼節點的唯一標識符定位該節點，再運用遞歸的方法獲得所依賴的節點，再將得到的所有的節點的標識符記錄下來，用來與骨架節點作比較(下文會有詳細說明)，只記錄節點的標識符，可以節省所占用的內存空間，這一過程的時間復雜度可看做是O(1).
本地副本的增量構建：當一個客戶端加入編輯會話的時候，第一個Request請求會發送到服務器，以獲得客戶端指定的代碼節點.如果其他客戶端的操作對本地相關節點進行更改，或者再次請求新的節點，就需要后續的Update操作根據服務器端的主副本來更新本地副本.但是為了節約帶寬，如果請求的節點或者所對應的依賴節點已經在本地客戶端存在，這個時候就只需要把本地沒有的節點挑選出來返回給用戶即可.在客戶端的數據我們稱之為副本數據(Replica Data).
為了快速高效的決定返回哪些節點給客戶端，以響應再次請求，同時避免返回本地已經有的節點，我們需要在服務器端保存一個與客戶端相同的骨架依賴節點(Skeleton Dependent Node)，這個骨架依賴節點只用節點的標識符和復制類型來表示節點之間的關系，為了節省空間和快速查找，并沒有存儲實際的數據.該骨架依賴節點記錄了哪些節點復制到了客戶端以及節點復制的類型(CopyType)，DN指的是復制成依賴節點，WN指的是復制成工作節點，目的是為了更好的跟蹤每個客戶端的數據狀態.
算法2.RequestNode( R，q )
1.q ← Sync(R，q)
2.S ←Skeleton Dependent Node
3.M ←DetectTargetedNode()
4.Forall N∈M do
5.Case1：N?R∩N?S R.N.CopyType=DN and return N
6.Case2：N?R∩N∈S R.N.CopyType=WN and return N
7.Case3：N∈R∩N?S return null
8.Case4：N∈R∩N∈S R.N.CopyType=WN and return null
9.Update R and q
10.end
R指的是客戶端副本數據，算法顯示了響應RequestNode請求q的過程，包含了一個節點查詢操作和提交本次請求之前的未提交給服務器處理的本地客戶端操作.到服務器端，調用Sync( )函數進行同步從客戶端發送過來的操作，該算法具體執行過程在下節給出.然后首先在最近更新過的主副本(main replica)上查詢所需要的節點集合M以及M的依賴節點.
例如，如圖2所示，如果客戶端需要對h和e節點進行編輯，就需要請求節點S={h，e}，根據前面的論述，通過一個查找依賴節點的函數(DetectTargetedNode( ))得到需要復制的節點集合M= {a，b，h，e}，M中的節點指的是需要復制的所有的節點，如果客戶端所請求的數據中，一部分節點有可能已經在客戶端存在了，所以只需要返回客戶端沒有的節點即可，服務器端根據集合M中節點的復制類型，按照下面的幾種情況以增量的方式返回相應的數據：
Case1指的是所要復制的節點在副本數據中不存在，也不屬于客戶端直接請求的節點，所以是屬于依賴節點，要把該節點返回給客戶端，并標記為依賴節點.
Case2指的是所要復制的節點是客戶端直接請求的操作節點，所以將該節點標記為工作節點，并把該節點返回給客戶端，顯示為工作節點.
Case3指的是該節點已經存在客戶端副本中，客戶端沒有直接請求作為工作節點，所以不需要返回任何數據.
Case4指的是客戶端請求的工作節點在副本中已經存在，是作為依賴節點存在的，只需要將依賴節點修改為工作節點即可，不需要返回該節點的數據.
3.4 客戶端與服務器端的交互
如圖3所示,服務器端會同時處理很多個客戶端請求，用RBCj和SBCj分別標識對應的客戶端操作隊列，SBSj和RBSj分別對應其它中心服務端的操作，從客戶端接收的操作需保存在服務器端的對應緩存隊列RBCj中，即將發送給客戶端的操作，存儲在緩存隊列SBCj中，當對應的用戶進入系統或離線狀態時，服務器端只需要創建或者刪除該緩沖隊列SBCj和RBCj即可，這樣的設計在服務器端會有很好的擴展性，又能節省不必要的資源.RBSj表示從其他服務器中心接收的數據緩存隊列，SBSj表示該服務中心發送到其他服務器的緩存隊列，每個服務器都能將更新的操作隊列主動發送到對應的客戶端或其他站點的中心服務器.
圖3 系統的分布式結構圖
3.5 服務器端對并發操作的檢測
因果序列要求：我們的方法要符合正確的因果關系，根據之前的協同編輯理論，在云環境下我們假設每個中心服務器在發送給其他服務器或者客戶端的時候都是按照相同的因果順序.
算法3.nwayMerge(sqlist)
1.L ←sqlist；N ← length(L)
2.WhileN > 1 do
3. N，M ← N/2，N/2
4.For(i=0；i 5. L[ i ] ←extractConcurrentOperations(L[ i ]，L[ N + i ]) 6.End while N=1 7.extractConcurrentOperations(L[ i ]，L[ 1 ]) 8.End 在算法3的目的是：在服務器端，有規律的對接收到的N路序列進行合并，這些序列是上下文有序的，也就是滿足相同的因果關系的N個操作序列.例如：有5個客戶端加入了協同會話中，在服務器端就會有5個緩存隊列來接受客戶端提交的操作，假如是sqlist[0]，sqlist[1]，sqlist[2]，sqlist[3]，sqlist[4]，首先對sqlist[0]，sqlist[3]進行并發操作檢查，再對sqlist[1]，sqlist[4]，最后再將結果與sqlist[2]進行合并檢測. CNi表示操作O對應的客戶端副本節點，這里用代碼節點的標識符來表示； Oi指的是代碼節點CNi對應的操作，緩沖隊列中的操作都是按照操作的因果關系存儲的； T表示操作O在本地編輯完成時間； T′表示操作O對應的節點CN在最近一次與服務器端完成同步的時間； 這里的T和T′都是指中心服務器的物理時間，在過去的端對端架構或者一些集中式協同系統中，很多都是采用二維時間戳來表示操作的執行時間，這在共享數據是完全復制的狀態下是可以適用的，但是在部分復制的情況下，每個站點的數據狀態不一致，采用統一的物理時間在全局中比較容易計算. 對于客戶端，緩沖序列RQj中任意一個操作序列P中，代碼節點O對應的產生時間O.T必然大于O.T′，因為節點O在本地產生時，是與服務器端進行同步完成之后產生的，而在O.T之后產生的新操作必定還沒有經過中心服務器的主副本上進行同步的，或者是即將提交到服務器的操作.服務器端上的RBCj隊列表示從客戶端接收的操作，根據操作序列的時間大小和副本節點是否相同得出操作之間的并發關系，對于任意兩個操作Oi和Oj，可以得出以下兩個結論： 如果Oi.T 如果Oi.T >Oj.T′ 且Oi.CN=Oj.CN，得出Oi || Oj，Oi并發于Oj ； 算法4.extractConcurrentOperations(L[i]，L[N+i]) 1.CO[ ] ← Concurrent Operation Set 2.WhileL[ i ] or L[N+i]do 3.Forall Oi，Oj ∈L[ i ]，L[N+i] do 4.ifOi.T >Oj.T′ 5. HandlerOT(Oi，Oj)； 6.elsereturn 0； 7.End if 這個函數的目的是：依次掃描RBCj 和RBSj，集中的找出提交到服務器端的每組并發操作序列，其中這些并發操作包括針對一個節點的操作和針對不同節點的操作，如果判斷的是并發操作，就用HandlerOT函數也就是操作轉換來解決(下節會有詳細說明).同一個客戶端的一個操作隊列中，操作之間的關系是因果關系.如果并發操作對應的節點之間沒有依賴或者間接依賴的關系，可以不用考慮. 根據定義，如果服務器端緩存區接收到一個操作O，與其并發的操作，就是執行完成時間T大于 O.T′，且對應的客戶端不相同，其中O.T′就是O對應的副本節點最近一次與服務器同步結束的時間. 首先需要滿足一下幾個性質：1.客戶端在任何時刻都能加入或離開一個合作對話.2.客戶端能夠獨立的決定什么時候與服務器端進行同步.3.服務器也能單獨決定什么時候處理從客戶端接收的操作.4.有高的并發性，不同的客戶端能夠對共享文檔的任一部分進行編輯，能夠避免過多的交互延遲.5.使用redis緩存隊列來做消息處理和任務調度.Redis緩存可以是基于內存的，可以對數據進行快速訪問，不會產生過多的延遲，并且由于緩存文件可以重復利用，還可以減少帶寬，降低網絡負荷.另外，可以對緩存隊列中的每項操作設置過期時間，過期后可以自動對數據進行刪除. 算法5.Control Procedure at Client 1.Initialization： 2. Tj=[ ]；LHBj=[ ]；RQj=[ ]； 3. RequestPartialNode( )； 4. Get partial code nodes replica R from Server 5.Thread1： 6. executeOj at local partial code nodes 7. append Ojinto Tj 8.LHBj=ERMerge(O，LHBj )； 9.LHBj=[ ]；// only if LHBjis received by the server 10.Thread2： 11.casesq： 12. receive sequence sq in RQj from Server 13. sq=RQj；RQj [ ]； 14.Forall O∈sq do 15.ifO is at open area 16. execute O at R directly 17.elseexecute O to update R 18. save( )； 19.caseFetch： 20. Send local buffer operation LHBj to server directly 21. End if 客戶端的算法要更加簡單高效.客戶端連接到系統之后，先請求所需要的數據節點，系統會進行一些初始化的操作，為客戶端建立必要的數據結構.客戶端的線程主要是處理本地操作和遠程并發操作，這兩個線程是并行執行的，可以有效地利用多核處理器，提高了運行效率. 在算法5中，新加入的客戶端首先應通過DetectTargetedNode()請求所需要的節點，本地產生的操作會立即執行，并存儲在Tj操作集合中，LHB操作緩沖區存放待發送到服務器端的操作，ERMerge( )函數的作用是使操作序列滿足“effect relation”關系，這樣能夠加快操作轉換的效率.RQj隊列存放服務器發送到客戶端的操作.線程一負責本地操作的執行，執行完本地操作，還需要把執行過的操作先存入緩沖區.線程二負責接收從服務器端發送過來的操作，并執行這些操作，因為這些操作是在本地站點執行過的操作或是有并發關系的遠程操作，經過與服務器端的同步，會與遠處站點的編輯操作進行一系列的操作轉換，返回到客戶端，用來更新本地站點的副本節點.當客戶端接收到Fetch指令時，客戶端向服務器發送本地執行過的操作LHB. 算法6.Control Procedure on Serveri 1.Initialization： 2. RBCj=[ ]；SBCj=[ ]；RBSj=[ ]；SBSj=[ ]； 3.Thread1： 4. For all sqjin RBCj，RBSj 5.Ifsqjis null 6. sendFetch to clientjor server j 7. Get operation sequence sq from ClientjorServerj 8. SQj=ERMerge(sq，RBCj，RBSj)； 9.ElseSQj=ERMerge(sq，RBCj，RBSj)； 10.Forall Oi∈SQjdo 11. CO[ ]=extractConcurrentOperations(Oi，SQj)； 12.Thread2： 13.Forall Oiof COido 14.ifOiis at open area，Oiis executed directly 15.elseTj′=HandlerOT(Oi) 16. First execute Tj′ on primary copy 17. then add Tj′ into SBCj，SBSj 18. sendSBCj，SBSjto Clientjor Serverj 19. End if 服務器端的四個操作隊列都是先經過操作轉換，再在中心服務器端的主副本上同步執行之后的操作.線程1的作用主要是將從客戶端或服務器端接收到的遠程操作，按照操作之間的依賴關系和因果關系重新排列，這里不是本文研究的重點.然后再將接收到的操作分類，也就是找出客戶端操作所對應的的并發操作.線程2的任務主要是對遠程并發操作進行操作轉換，再將操作轉換結果應用到中心服務器的主副本上，這樣的目的是為了讓所有的客戶和服務器都能共享相同的數據狀態，也能保證代碼數據的完整性.然后再將操作轉換之后的結果發送到對應客戶端和遠處服務器端. Fan提出的共享鎖中，如果編輯區域是在一個開放域中，就不會發生語義沖突；如果并發操作有共同的依賴節點，也不會發生語義沖突；沖突的情況只會發生在并發編輯同一個節點，或者是發生在有依賴關系或者間接依賴的節點上. 所以，在服務器端首先要做的是，當檢測到對應站點的并發操作之后，就要再次確認并發操作所對應的節點之間的動態依賴關系. 如果是并發對有依賴關系的節點編輯時，需要用編輯器檢測或者是發送消息給客戶端，再次判斷操作的關系，其中會出現的三種關系是兼容關系，排斥關系或者依賴關系. 這樣的方法能阻止語義沖突的發生，還能保證程序員的連續工作，即使依賴圖是動態改變的，這中間是沒有中斷的. 算法7.HandlerOT(Oi) 1.Forall S∈Oido //對Oi每組并發操作進行分析 2.ifSi.rootNode=Sj.rootNode//有共同的依賴節點 3.Oiis directly executed 4.elseifSiandSjhas dependent relation 5. ConDetect(Si，Sj)//判斷依賴關系和沖突檢測 6.elseSi.ID=Sj.ID//指的是同一個節點 7. Awareness solution(Si，Sj) 8.endif 該函數的作用是對并發操作分類處理，并發操作都發生在開放域，則不會發生語義沖突，這種情況是直接執行的，只需要維護每個站點代碼節點的上下順序一致就可以了，在這里，可以通過每個操作的全局標識符，通過比較標識符的大小來排序.如果并發操作所對應的節點，有依賴關系的話，就需要進行沖突檢測，使用ConDetect()函數進行沖突消解(下文會有解釋).如果并發操作是針對一個節點，就需要用下面的方法來解決. 如果是針對同一個節點的并發編輯，操作的類型會有插入，更新，刪除和移動節點，根據人的編輯意識操作，采用操作轉換對結果進行合并，這種方法可以有效解決沖突. 算法8.Awareness solution(Si，Sj) 1.receiveO1，O2 2.ifO1and O2are both creationsthen 3. keep two operates and highlight new result 4.elseifO1and O2are both updatethen 5. show two versions to client 6.elseifO1is update and O2is deletethen 7. delete this code node and show it 8.elseifO1is update and O2is movethen 9. move the updated version and highlight it 10.elseifO1and O2are both deletethen 11. delete and nothing needed 12.elseifO1is delete and O2is movethen 13. delete this code node and show it 14.elseO1and O2are move delete 15. create clones and highlight clones 16.endif 上面的算法展示了并發沖突發生在同一個節點上的時候，是如何解決的.如果是兩個客戶端在相同的節點下并發創建新的節點，根據前面的許可審查條件，在開放域中創建節點不會產生語義沖突，這種情況應該考慮節點之間的前后順序即可，可以根據客戶端的標識符或產生的節點標識符排序. 算法9.ConDetect(Si，Sj) 1.Oi ←Si，Oj ← Sj 2.WhileOj.targetNode—>Oi.targetNode do 3.IfOj and Oi both are Deletethen 4.Oj.targetNodeand Oi.targetNode both are Delete 5.ElseIfOj is Delete and Oi is Updatethen 6.Oj.targetNode is Delete and Oi.targetNode is Update 7.ElseIfOj is Delete and Oi is Movethen 8.Oj.targetNode is Delete and Oi.targetNode is Move 9.ElseIfOj is Update and Oi is Deletethen 10. Oj.targetNode and Oi.targetNodeboth areDelete 11.ElseIfOj is Update and Oi is Updatethen 12. Oj.targetNode and Oi.targetNode both are Update and show it 13.ElseIfOj is Update and Oi is Movethen 14. Oj.targetNode is Update and Oi.targetNode is Move 15.ElseIfOj is Move and Oi is Deletethen 16. Oj.targetNode and Oi.targetNode both are Delete 17.ElseIfOj is Move and Oi is Updatethen 18. Oj.targetNode is Moveand Oi.targetNode is Update 19.ElseOj is Move and Oi is Movethen 20. Oj.targetNodeand Oi.targetNode are Move 21.End 在服務器端對并發操作的檢測之后，如果并發操作之間有間接依賴或直接依賴的關系，則會調用算法9.根據共享鎖的特點和實際編程中的效果，假如：Oi 對應的節點是A，Oj對應的節點是B，B依賴于A，A的操作直接決定著B是否會有語義沖突，A和B的操作可以是刪除(Delete)，更新(Update)和移動(Move)，如果A是刪除，那么B無論做什么操作，都是無效的，所以A如果是刪除操作的話，沖突消解的辦法只能是把A和B節點同時刪除.如果A節點是更新或移動操作，B節點是刪除操作，B節點的操作對A節點沒有影響，所以這兩個操作是兼容的.如果A和B兩個節點都是更新操作，則會想對應的客戶端發送消息機制，可以避免意義沖突的發生.如果A是移動操作，B是更新操作，則不會發生語義沖突，這兩個操作是兼容的.如果A節點更新，B節點移動，這兩個操作也是兼容的.如果A和B節點(在合理的范圍內，A節點一直在B節點之前)同時發生移動的操作的話，這兩個操作也是兼容的. 為了證明算法的合理性，設計了一個基于Vaadin框架的瀏覽器端的java代碼編輯器(CloudCode)，利用Web端軟件良好的跨平臺性，選擇Java作為目標語言，Vaadin作為主要框架，選擇Vaadin的原因是：它所運行的代碼都是在服務器端的，編譯速度快，能夠支持所有的Java庫，而且開發效率高，只需要Java語言即可，不需要JavaScript和XML進行配置.使用基于webSocket的協議進行信息傳輸. 客戶端使用Ace編輯器，Ace只一種開源的，基于瀏覽器端的代碼編輯器，能夠支持多種語言，且具有強大的功能.在服務器端安裝JDK作為分析源代碼的工具. 在服務器端，JDK作為分析代碼的工具，該應用程序的前端包括GUI圖形界面和代碼編輯器.并且使用多線程機制，可以同時響應和處理多個客戶端請求. 圖4 前端界面的編輯布局 如圖4是一個客戶端進行編輯交互的界面，客戶端的控制按鈕都是基于JavaScript的Ace editor編輯器實現基本功能.進入該界面的客戶端需要先點擊request請求操作，加載一部分數據到本地，再返回到CloudEditer編輯器界面進行編輯，根據用戶所編輯的位置信息進行監聽，通過接口ExamineArea( )進行判斷用戶所編輯的操作是在代碼域或開放域中，如果是在開放域，就不會與其他客戶端發生沖突，就不需要與其他并發編輯的客戶端進行意識交互；如果是對代碼節點進行編輯，就會通過服務器進行檢測，是否與其他客戶端所編輯的節點是否是并發的，如果是并發操作，就會HandlerOT進行操作轉換. 圖5 編輯時的信息交互模型圖 系統界面左邊可以看到在線人數，同時顯示與本地客戶端發生并發編輯的客戶端的編輯信息，可以選擇在線人員進行交互.如果與并發編輯的客戶端共同編輯同一個節點或者是有依賴關系節點時，會出現一個消息提示框，觸發Awareness solution()和ExaminateCurrent()接口，進行判斷操作之間的關系，或者是給其他客戶端發送意識消息，便于能得到更好的結果，如圖5所示. 合理性：整個程序的運行時間效率分為客戶端效率和服務器端效率.服務器端的性能表現在兩個方面：處理客戶端請求的時間：a)N路合并的時間和查找并發操作的時間，b)執行并發操作的時間.客戶端性能也包括兩個方面：請求目標代碼節點的時間，執行本地操作的時間和RQj中遠程操作的時間.從以上分析可以得出：整個程序的最終性能取決于客戶端提交的操作數量和代碼總量. 如果是采用全部復制的方法，隨著在線的協同編輯的用戶的增多，代碼量的不斷增加，傳輸效率會隨著代碼量的增加而減少，如果加入一個新用戶，如果在帶寬流量不好的情況下，會嚴重阻礙協同的效率.客戶端的算法是用JavaScript來實現的，我們假設在帶寬充足的情況下，采用Socket協議進行傳輸，分析協同編輯完成的效率，整個效率跟每個客戶端的運行效率都有關系.但是如果采用部分復制的方法，每個新加入的客戶端不會隨著時間的變化出現效率的降低，因為請求加載數據量不會逐漸增大.在線人數多的時候，效果會比較明顯. 本文提出了基于云端的CloudCode編程系統，在算法方面，采用了改進之后的TIPs集中式架構，運用部分復制提高了系統效率，最重要的是采用共享鎖的思想，使用中心服務器來檢測操作之間的復雜關系，檢測是否會發生語義沖突，并阻止了語義沖突的發生，操作轉換的結果更能符合用戶要求. 在系統架構方面，還可以進行很多改進，可以將軟件應用程序設計為微服務架構的形式.在協同編程中，如果要求返回到原來的版本，對一系列連續的操作進行撤銷的話，如何高效的進行Undo-Redo操作，對于項目中的一系列文件如何進行協同處理，如何提高用戶的體驗度，在數據庫設計方面，如何提高檢索效率，這些都是以后研究的方向.
3.6 客戶端的算法設計
3.7 服務器端的算法設計
3.8 解決每個站點操作的并發沖突
4 CloudCode原型系統
5 實驗分析
5.1 復雜度分析
5.2 樂觀復制中的全復制和部分復制的對比分析
6 總結與展望
