移動(dòng)云環(huán)境下的實(shí)時(shí)協(xié)同編程機(jī)制及策略研究

高麗萍，趙春芽

1(上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院，上海 200093)

2(復(fù)旦大學(xué) 上海市數(shù)據(jù)科學(xué)重點(diǎn)實(shí)驗(yàn)室，上海 200093)

E-mail：lipinggao@usst.edu.cn；450190073@qq.com

1 引 言

近些年來(lái)軟件行業(yè)的繁榮發(fā)展，移動(dòng)云計(jì)算是當(dāng)今的主要流行趨勢(shì)，移動(dòng)資源，云計(jì)算和云服務(wù)為協(xié)同交互應(yīng)用帶來(lái)了巨大挑戰(zhàn).同時(shí)網(wǎng)絡(luò)技術(shù)的發(fā)展使大量的協(xié)同編輯應(yīng)用程序得到了很大的開(kāi)發(fā)，同時(shí)軟件規(guī)模和復(fù)雜度也在提高，將計(jì)算機(jī)支持的協(xié)同工作與編程環(huán)境相結(jié)合是協(xié)同工作中重要的研究領(lǐng)域，協(xié)同編程不僅能提高工作效率，還能使各個(gè)站點(diǎn)的用戶更方便工作.過(guò)去的幾十年，已經(jīng)有許多的協(xié)同軟件研究者致力于協(xié)同編程軟件或是協(xié)同編程方法的研究上，研發(fā)了一系列的協(xié)同開(kāi)發(fā)工具.協(xié)同編輯工具在近年來(lái)得到了廣泛的應(yīng)用，在很多企業(yè)中也在使用協(xié)同辦公軟件很多的應(yīng)用程序也廣泛支持異步開(kāi)發(fā)，比如wikis和版本控制系統(tǒng).或者是同步協(xié)作，如分布式實(shí)時(shí)協(xié)作編輯器，協(xié)同設(shè)計(jì)工具或云集成開(kāi)發(fā)環(huán)境.

樂(lè)觀復(fù)制[5]，即副本數(shù)據(jù)全部復(fù)制結(jié)構(gòu)，是過(guò)去在集中式架構(gòu)(Jupiter[14]算法和TIPs[15]算法)，和一系列協(xié)同編輯中廣泛采用的方法，這能夠有效的解決分布式系統(tǒng)中網(wǎng)絡(luò)延遲問(wèn)題和數(shù)據(jù)一致性問(wèn)題，如GoogleDrive(1)“Google drive,”https://drive.google.com.和Docs(2)Google Docs[ED/OL)：//docs.google.com是在全部復(fù)制的基礎(chǔ)上使用操作轉(zhuǎn)換來(lái)保持一致性.但是在大規(guī)模數(shù)據(jù)并發(fā)下，比如Xia[4]提出的部分復(fù)制的概念去解決評(píng)論系統(tǒng)下的數(shù)據(jù)一致性，因?yàn)樵u(píng)論節(jié)點(diǎn)之間是樹(shù)形結(jié)構(gòu)，該部分復(fù)制的思想是如果對(duì)一個(gè)評(píng)論節(jié)點(diǎn)進(jìn)行操作，需要把該節(jié)點(diǎn)的父節(jié)點(diǎn)和兄弟節(jié)點(diǎn)加載到本地，稱(chēng)之為骨架節(jié)點(diǎn)，在服務(wù)器端使用一個(gè)副本結(jié)構(gòu)對(duì)本地骨架節(jié)點(diǎn)進(jìn)行數(shù)據(jù)跟蹤，用來(lái)完成對(duì)本地?cái)?shù)據(jù)的數(shù)據(jù)同步和增量更新.

傳統(tǒng)的協(xié)同編程體系中，在數(shù)據(jù)部分復(fù)制方面和控制語(yǔ)義沖突方面還有很多能夠優(yōu)化的地方.本文針對(duì)在云環(huán)境下，采用新的基于TIPs[1]的集中式架構(gòu)進(jìn)行操作轉(zhuǎn)換，并根據(jù)Fan提出的共享鎖[5]的結(jié)論來(lái)控制語(yǔ)義沖突的發(fā)生，論文整體結(jié)構(gòu)如下：第二部分介紹了協(xié)同編程的研究背景及相關(guān)工作；第三部分是分析了在云環(huán)境下協(xié)同編程模型；第四部分提出了在服務(wù)器端進(jìn)行的操作轉(zhuǎn)換和沖突解決方案；第五部分對(duì)相應(yīng)的操作轉(zhuǎn)換算法進(jìn)行可行性分析和評(píng)估；第六部分?jǐn)⑹隽薈loudCode原型系統(tǒng)設(shè)計(jì)的相關(guān)技術(shù)；第七部分進(jìn)行總結(jié)和對(duì)未來(lái)的展望.

2 相關(guān)工作

在近些年來(lái)的研究工作中，協(xié)同編輯技術(shù)被大量的開(kāi)發(fā)和應(yīng)用.最常用的一致性維護(hù)技術(shù)有操作轉(zhuǎn)換(Operation Transformation，OT)[6，7，9]技術(shù)和地址空間轉(zhuǎn)換(Address Space Transformation，AST)[8]技術(shù)，以上兩種技術(shù)最初都是在點(diǎn)對(duì)點(diǎn)的協(xié)同交互應(yīng)用中提出的，在實(shí)時(shí)編輯時(shí)每個(gè)用戶能夠立即看到其他用戶的改變.Xia[4]提出了適合在移動(dòng)云環(huán)境下應(yīng)用的地址空間轉(zhuǎn)換方法，并將這一方法運(yùn)用到了評(píng)論系統(tǒng)中.根據(jù)操作轉(zhuǎn)換，可以對(duì)并發(fā)操作做出合并，包括Ellis和Gibbs[17]在文獻(xiàn)中提出的DOPT算法，Sun和Ellis[7]提出的GOT和GOTO算法，Sun[11]在文獻(xiàn)中提出的COT算法等.

操作轉(zhuǎn)換技術(shù)(OT)適合于非線性文檔中，例如Ng A，Sun C[9]在文獻(xiàn)中提出的實(shí)現(xiàn)實(shí)時(shí)文件管理系統(tǒng)的一致性維護(hù).SUN[11]等在文獻(xiàn)中提出使用OT算法解決了3D系統(tǒng)中文檔依賴沖突的問(wèn)題.Fu[18]等人在文獻(xiàn)中提出改進(jìn)GOTO算法以支持表格文檔協(xié)同編輯下的一致性維護(hù).版本控制[12]，是在團(tuán)隊(duì)協(xié)同開(kāi)發(fā)中使用的，根據(jù)每一個(gè)時(shí)刻指針?biāo)赶虻陌姹?，可以恢?fù)到原來(lái)的版本，可以有效的對(duì)代碼進(jìn)行整合.

FAN和SUN在文獻(xiàn)[18]中提出的DAL技術(shù)能夠保證在實(shí)時(shí)協(xié)同編程環(huán)境中避免語(yǔ)義沖突.與OT不同的是：該方法采用悲觀鎖的方式，自動(dòng)對(duì)編輯的文檔內(nèi)容進(jìn)行加鎖，拒絕其他用戶的編輯操作，這種悲觀鎖的方式在實(shí)際應(yīng)用中是不合理的，因?yàn)檫@種悲觀鎖的方式假設(shè)加鎖的部分沒(méi)有覆蓋部分，還假設(shè)動(dòng)態(tài)依賴圖是靜止不變的，而在實(shí)際編程條件下代碼節(jié)點(diǎn)之間的依賴關(guān)系都是會(huì)發(fā)生變化的.后來(lái)又提出了三種共享鎖(shared-locking on common depended regions)[5]，這種方法能夠保證高的響應(yīng)性，有效性和一致性，并能在實(shí)時(shí)編程環(huán)境中阻止語(yǔ)義沖突發(fā)生.

Nieminen等人研究的CoRED[13]系統(tǒng)指的是基于瀏覽器上的對(duì)Java應(yīng)用程序進(jìn)行實(shí)時(shí)協(xié)同開(kāi)發(fā)，不僅能夠?qū)Υa詞匯進(jìn)行突出顯示和縮進(jìn)，還可以進(jìn)行錯(cuò)誤檢測(cè)和代碼自動(dòng)生成.You[19]提出的協(xié)同編程環(huán)境下基于CAS并發(fā)處理思想的語(yǔ)義沖突消解方法，其核心思想是通過(guò)對(duì)目標(biāo)對(duì)象設(shè)定期望值，若目標(biāo)對(duì)象的期望值由于并發(fā)更改發(fā)生變化時(shí)，則操作不能執(zhí)行.

Jupiter[14]算法和TIPs[15]算法是目前支持集中式架構(gòu)的算法，其中JupiterOT算法是第一個(gè)將操作轉(zhuǎn)換用在C/S結(jié)構(gòu)中的，它使用二維狀態(tài)向量來(lái)跟蹤轉(zhuǎn)換路徑，最終數(shù)據(jù)狀態(tài)取決于客戶端與服務(wù)器同步的順序，JupiterOT無(wú)法保證會(huì)采用正確的轉(zhuǎn)換路徑并產(chǎn)生正確一致的最終狀態(tài)，因此使用這個(gè)算法的最終結(jié)果是不能夠收斂的.

在移動(dòng)云環(huán)境下的一致性維護(hù)研究中，Gao[1]提出的實(shí)時(shí)協(xié)同圖形編輯，對(duì)TIPs算法進(jìn)行了改進(jìn)，原本TIPs算法采用HTTP協(xié)議，服務(wù)器端不能夠主動(dòng)為客戶端發(fā)送消息，服務(wù)器和客戶端之間的同步需要設(shè)置一定的時(shí)間間隔，對(duì)于在編程中，時(shí)間間隔的大小不容易控制，間隔過(guò)小會(huì)不利于編程效果，過(guò)大的話不能夠很好的做出響應(yīng)，這會(huì)造成很多帶寬資源的浪費(fèi)，通過(guò)實(shí)驗(yàn)?zāi)軌蜃C明，使用改進(jìn)之后的TIPs算法能夠使協(xié)同編輯效率提高.

本文將對(duì)樹(shù)形評(píng)論節(jié)點(diǎn)的部分復(fù)制[4]思想進(jìn)行改進(jìn)，在實(shí)際編程中，如果對(duì)一個(gè)代碼節(jié)點(diǎn)進(jìn)行編輯，這個(gè)代碼節(jié)點(diǎn)只與它的依賴節(jié)點(diǎn)有關(guān)系，所以只需要將依賴節(jié)點(diǎn)加載到客戶端即可，我們提出了基于依賴關(guān)系的部分復(fù)制(Partial replication based on dependency)，經(jīng)過(guò)一系列的實(shí)驗(yàn)證明了可行性，并得到了很好的效果.數(shù)據(jù)部分如果采取全復(fù)制的方式會(huì)嚴(yán)重浪費(fèi)帶寬資源，客戶端也不能得到快速響應(yīng)，在協(xié)同編程中，更適合采用部分復(fù)制的方式.但是為了提高快速響應(yīng)的能力和支持離線操作中數(shù)據(jù)一致性問(wèn)題，采用部分?jǐn)?shù)據(jù)復(fù)制分方法，這對(duì)協(xié)同編程并在解決語(yǔ)義沖突方面有很大的挑戰(zhàn).

根據(jù)Fan[5]等人提出的共享鎖的結(jié)論進(jìn)行并發(fā)操作，可以有效的防止語(yǔ)義沖突.根據(jù)Fan的結(jié)論，每個(gè)客戶端只有滿足下面的條件，并發(fā)操作才能得到許可：

1.編輯操作是在開(kāi)放域中；

2.編輯操作是在一個(gè)基本域中;

該基本區(qū)域被本地的程序員作為工作區(qū)域已經(jīng)加鎖；或者是該基本域沒(méi)有被其他合作的程序員加鎖，并且它的依賴域沒(méi)有被其他程序員作為工作區(qū)域加鎖.

可以得出，當(dāng)編輯操作發(fā)生在同一個(gè)節(jié)點(diǎn)上或者并發(fā)操作所對(duì)應(yīng)的節(jié)點(diǎn)之間有依賴關(guān)系時(shí)，才有可能發(fā)生語(yǔ)義沖突.而對(duì)于沒(méi)有依賴或間接依賴關(guān)系的并發(fā)沖突的代碼一致性維護(hù)，相當(dāng)于文本的一致性維護(hù)，在前面很多文獻(xiàn)中已經(jīng)有很多的解決方法了，本文不作為重點(diǎn)研究.

根據(jù)代碼節(jié)點(diǎn)之間復(fù)雜動(dòng)態(tài)依賴關(guān)系，運(yùn)用云計(jì)算環(huán)境，在部分復(fù)制的基礎(chǔ)上，進(jìn)行一致性維護(hù)和解決語(yǔ)義沖突有很大的挑戰(zhàn)性.移動(dòng)云計(jì)算能為客戶提供低成本，可靠和穩(wěn)定的服務(wù)，云環(huán)境下的新的架構(gòu)為協(xié)同編輯提出了很多新的挑戰(zhàn).

3 云環(huán)境下協(xié)實(shí)時(shí)同編程系統(tǒng)的設(shè)計(jì)與分析

3.1 基于協(xié)同編程的技術(shù)挑戰(zhàn)

在協(xié)同編程模型中如果采用全復(fù)制結(jié)構(gòu)，由于本地資源帶寬的限制，會(huì)浪費(fèi)很多不必要的資源.移動(dòng)云計(jì)算，就是要將移動(dòng)終端設(shè)備的龐大計(jì)算量通過(guò)網(wǎng)絡(luò)傳輸移動(dòng)到計(jì)算中心，通過(guò)云計(jì)算不僅能滿足用戶高的性能體驗(yàn)，還能滿足數(shù)據(jù)量的需求.

1.架構(gòu)的變化.在移動(dòng)云環(huán)境下，為了充分利用良好的跨平臺(tái)性，一般都是采用B/S模式，移動(dòng)云環(huán)境下的客戶端主要是移動(dòng)設(shè)備(手機(jī)或筆記本電腦)，服務(wù)器端一般是分布式體系架構(gòu)，具有高擴(kuò)展，高效率，高可靠等優(yōu)點(diǎn).這里我們采用分布式服務(wù)框架Zookeeper來(lái)管理分布式環(huán)境中的數(shù)據(jù).

2.如何對(duì)所需要的編輯節(jié)點(diǎn)進(jìn)行部分復(fù)制并對(duì)本地?cái)?shù)據(jù)節(jié)點(diǎn)進(jìn)行動(dòng)態(tài)更新.傳統(tǒng)的協(xié)同編輯都是采用全復(fù)制來(lái)解決高的響應(yīng)性.在移動(dòng)云環(huán)境下，采用部分復(fù)制的方法對(duì)本地?cái)?shù)據(jù)進(jìn)行動(dòng)態(tài)一致性的維護(hù)，這種方式能夠有效的節(jié)約本地用戶的存儲(chǔ)資源并減少能量消耗.

3.如何在部分復(fù)制的情況下，采用不加鎖的方式，動(dòng)態(tài)的實(shí)現(xiàn)客戶端和服務(wù)器端的數(shù)據(jù)同步，同時(shí)維持高的響應(yīng)性并保證不發(fā)生語(yǔ)義沖突.

4.如何設(shè)計(jì)簡(jiǎn)單高效的算法進(jìn)行交互，滿足用戶動(dòng)態(tài)加入或離開(kāi)，并保證移動(dòng)端和服務(wù)器端的有效擴(kuò)展.

3.2 數(shù)據(jù)結(jié)構(gòu)和基本定義

操作轉(zhuǎn)換能夠使用戶在不加鎖沒(méi)有阻礙的情況下修改本地副本的任何部分，在協(xié)同編程中，可以通過(guò)進(jìn)一步的改進(jìn)，操作轉(zhuǎn)換算法允許用戶的并發(fā)操作按照任意順序執(zhí)行，并發(fā)沖突發(fā)生時(shí)，會(huì)按照規(guī)定的操作轉(zhuǎn)換算法自動(dòng)的解決和融合并發(fā)操作沖突.如圖1所示，對(duì)這個(gè)list類(lèi)中的代碼節(jié)點(diǎn)用連續(xù)的字母表示，字母之間的連接方向就表示代碼節(jié)點(diǎn)之間的依賴關(guān)系.

圖1 代碼節(jié)點(diǎn)之間的關(guān)系圖

定義1.代碼域(Code Area，CA)和開(kāi)放域(Open Area，OA)

在一系列源代碼組成的有語(yǔ)法意義的文檔部分稱(chēng)為代碼域(CA)，代碼文檔之外的空白部分都是開(kāi)放域(OA).

定義2.依賴關(guān)系

代碼節(jié)點(diǎn)(Node)之間的依賴關(guān)系是動(dòng)態(tài)變化的，依賴圖之間的依賴關(guān)系代表代碼節(jié)點(diǎn)之間的依賴關(guān)系.節(jié)點(diǎn)之間有直接依賴關(guān)系和間接依賴關(guān)系，例如C->B，B->A是直接依賴關(guān)系，C->A是間接依賴關(guān)系.

定義3.兼容關(guān)系(⊙)

代碼編輯中的兼容關(guān)系表現(xiàn)為：1.并發(fā)操作發(fā)生在一對(duì)有依賴關(guān)系的節(jié)點(diǎn)上時(shí)，都是按照自己的意愿進(jìn)行編輯的，且沒(méi)有出現(xiàn)語(yǔ)義沖突；2.或者是并發(fā)操作發(fā)生在沒(méi)有依賴關(guān)系的節(jié)點(diǎn)上；3.或者是并發(fā)操作所發(fā)生的節(jié)點(diǎn)有公共依賴節(jié)點(diǎn).4.或者是并發(fā)操作都是發(fā)生在開(kāi)放域(OA).

表1 并發(fā)操作發(fā)生在相互依賴的節(jié)點(diǎn)上如(B->A)情況時(shí)，會(huì)產(chǎn)生的沖突和兼容

表2 并發(fā)操作發(fā)生在同一個(gè)節(jié)點(diǎn)時(shí)，會(huì)產(chǎn)生的沖突和兼容

定義4.相互排斥關(guān)系(?)

如表1、表2所示，如果多個(gè)用戶并發(fā)對(duì)同一個(gè)節(jié)點(diǎn)進(jìn)行操作，或者用戶對(duì)有依賴關(guān)系的節(jié)點(diǎn)進(jìn)行并發(fā)編輯也有可能發(fā)生語(yǔ)義沖突，相互排斥的關(guān)系不容易進(jìn)行意愿融合，考慮到在實(shí)際編程的效果，出現(xiàn)相互排斥的關(guān)系時(shí)，系統(tǒng)會(huì)給產(chǎn)生并發(fā)操作的用戶發(fā)送消息機(jī)制，根據(jù)返回的信息決定是保留哪個(gè)版本.下面的部分我們會(huì)詳細(xì)說(shuō)明，在并發(fā)操作發(fā)生在一個(gè)節(jié)點(diǎn)上，或發(fā)生在相互依賴的節(jié)點(diǎn)上的情況下，哪些情況可以進(jìn)行意愿融合，哪些情況是通過(guò)發(fā)送消息機(jī)制來(lái)決定.

定義5.代碼節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)(Node Structure)

每個(gè)代碼節(jié)點(diǎn)(Node)包含的信息有唯一的位置標(biāo)識(shí)符(AD)，直接依賴的節(jié)點(diǎn)集合rootNode，對(duì)應(yīng)代碼域的文本內(nèi)容(Code Content)，被復(fù)制到客戶端的代碼類(lèi)型Copy Type，如果該節(jié)點(diǎn)是工作節(jié)點(diǎn)就表示為WN，如果是依賴節(jié)點(diǎn)表示為DN，一個(gè)節(jié)點(diǎn)表示為{N | N=}.

定義6.全局唯一標(biāo)識(shí)符Identifier(ID)

客戶端對(duì)每個(gè)節(jié)點(diǎn)的操作O都會(huì)有一個(gè)標(biāo)識(shí)符ID，這個(gè)標(biāo)識(shí)符是一個(gè)二元組，其中s是這一次訪問(wèn)中會(huì)話信息的標(biāo)識(shí)符，site發(fā)起這一操作所對(duì)應(yīng)的客戶端站點(diǎn)標(biāo)識(shí)符.當(dāng)操作發(fā)生兼容關(guān)系時(shí)，會(huì)根據(jù)操作標(biāo)識(shí)符的大小進(jìn)行排序，可以保證數(shù)據(jù)的整體一致性.

定義7.操作類(lèi)型(operate type)

編輯操作的類(lèi)型和相關(guān)函數(shù)：

Create( )：表示創(chuàng)建相應(yīng)的代碼節(jié)點(diǎn)

Delete()：表示刪除指定的代碼節(jié)點(diǎn)

Update()：表示對(duì)指定節(jié)點(diǎn)進(jìn)行修改或更新

Move()：表示移動(dòng)代碼節(jié)點(diǎn)到一個(gè)新的位置.

定義8.操作(operate )

將客戶端的一個(gè)操作O定義為四元組，其中ID表示全局唯一標(biāo)識(shí)符，TargetNode指的是目標(biāo)節(jié)點(diǎn)，OperateType指的是上面的四種操作類(lèi)型，VersionType的值有0和1，表示有沒(méi)有與服務(wù)器端進(jìn)行同步，同步之后用1表示，未同步的話用0表示.

3.3 部分復(fù)制

本文提出了基于依賴關(guān)系的部分復(fù)制(Partial replication based on dependency).在中心服務(wù)器端，整個(gè)完整代碼節(jié)點(diǎn)目錄會(huì)以主副本(Main Replica)的形式存在，客戶端能夠請(qǐng)求得到部分節(jié)點(diǎn)，在網(wǎng)頁(yè)上進(jìn)行編輯，程序編譯和運(yùn)行需要在服務(wù)器端進(jìn)行，再將結(jié)果返回給用戶，這樣保證了移動(dòng)端的運(yùn)行效率，使能夠隨時(shí)隨地在移動(dòng)端進(jìn)行編輯.當(dāng)一個(gè)客戶端加入這個(gè)編輯會(huì)話中時(shí)，有可能只需要編輯代碼域的其中一部分，根據(jù)程序編程特點(diǎn)，在一個(gè)類(lèi)中，基本包括兩種語(yǔ)句，一種是定義，一種是函數(shù)，我們只需要把所編輯節(jié)點(diǎn)的依賴節(jié)點(diǎn)復(fù)制到本地.如圖2所示，在這個(gè)依賴圖中，如果對(duì)h節(jié)點(diǎn)進(jìn)行編輯操作，為了保持節(jié)點(diǎn)之間的依賴關(guān)系，我們?cè)趶?fù)制服務(wù)器端副本的時(shí)候，需要把相關(guān)加點(diǎn)a和b都加載到本地，在編程的過(guò)程中有可能還會(huì)需要其他依賴節(jié)點(diǎn)，這就需要對(duì)本地?cái)?shù)據(jù)進(jìn)行增量更新，可以再次請(qǐng)求所需要的節(jié)點(diǎn)，而這不需要把整個(gè)代碼文件全部下載下來(lái)，這會(huì)有利于節(jié)省本地的存儲(chǔ)資源.這里需要注意的是，當(dāng)一個(gè)代碼節(jié)點(diǎn)被復(fù)制時(shí)，需要將記錄在該節(jié)點(diǎn)的緩沖區(qū)的操作，也一同復(fù)制，便于得到最新的代碼版本.

圖2 代碼節(jié)點(diǎn)的簡(jiǎn)單依賴關(guān)系結(jié)構(gòu)

算法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的目的是：獲取目標(biāo)節(jié)點(diǎn)和依賴節(jié)點(diǎn)，即客戶端所需要的所有的節(jié)點(diǎn)集合M.根據(jù)代碼節(jié)點(diǎn)的唯一標(biāo)識(shí)符定位該節(jié)點(diǎn)，再運(yùn)用遞歸的方法獲得所依賴的節(jié)點(diǎn)，再將得到的所有的節(jié)點(diǎn)的標(biāo)識(shí)符記錄下來(lái)，用來(lái)與骨架節(jié)點(diǎn)作比較(下文會(huì)有詳細(xì)說(shuō)明)，只記錄節(jié)點(diǎn)的標(biāo)識(shí)符，可以節(jié)省所占用的內(nèi)存空間，這一過(guò)程的時(shí)間復(fù)雜度可看做是O(1).

本地副本的增量構(gòu)建：當(dāng)一個(gè)客戶端加入編輯會(huì)話的時(shí)候，第一個(gè)Request請(qǐng)求會(huì)發(fā)送到服務(wù)器，以獲得客戶端指定的代碼節(jié)點(diǎn).如果其他客戶端的操作對(duì)本地相關(guān)節(jié)點(diǎn)進(jìn)行更改，或者再次請(qǐng)求新的節(jié)點(diǎn)，就需要后續(xù)的Update操作根據(jù)服務(wù)器端的主副本來(lái)更新本地副本.但是為了節(jié)約帶寬，如果請(qǐng)求的節(jié)點(diǎn)或者所對(duì)應(yīng)的依賴節(jié)點(diǎn)已經(jīng)在本地客戶端存在，這個(gè)時(shí)候就只需要把本地沒(méi)有的節(jié)點(diǎn)挑選出來(lái)返回給用戶即可.在客戶端的數(shù)據(jù)我們稱(chēng)之為副本數(shù)據(jù)(Replica Data).

為了快速高效的決定返回哪些節(jié)點(diǎn)給客戶端，以響應(yīng)再次請(qǐng)求，同時(shí)避免返回本地已經(jīng)有的節(jié)點(diǎn)，我們需要在服務(wù)器端保存一個(gè)與客戶端相同的骨架依賴節(jié)點(diǎn)(Skeleton Dependent Node)，這個(gè)骨架依賴節(jié)點(diǎn)只用節(jié)點(diǎn)的標(biāo)識(shí)符和復(fù)制類(lèi)型來(lái)表示節(jié)點(diǎn)之間的關(guān)系，為了節(jié)省空間和快速查找，并沒(méi)有存儲(chǔ)實(shí)際的數(shù)據(jù).該骨架依賴節(jié)點(diǎn)記錄了哪些節(jié)點(diǎn)復(fù)制到了客戶端以及節(jié)點(diǎn)復(fù)制的類(lèi)型(CopyType)，DN指的是復(fù)制成依賴節(jié)點(diǎn)，WN指的是復(fù)制成工作節(jié)點(diǎn)，目的是為了更好的跟蹤每個(gè)客戶端的數(shù)據(jù)狀態(tài).

算法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指的是客戶端副本數(shù)據(jù)，算法顯示了響應(yīng)RequestNode請(qǐng)求q的過(guò)程，包含了一個(gè)節(jié)點(diǎn)查詢操作和提交本次請(qǐng)求之前的未提交給服務(wù)器處理的本地客戶端操作.到服務(wù)器端，調(diào)用Sync( )函數(shù)進(jìn)行同步從客戶端發(fā)送過(guò)來(lái)的操作，該算法具體執(zhí)行過(guò)程在下節(jié)給出.然后首先在最近更新過(guò)的主副本(main replica)上查詢所需要的節(jié)點(diǎn)集合M以及M的依賴節(jié)點(diǎn).

例如，如圖2所示，如果客戶端需要對(duì)h和e節(jié)點(diǎn)進(jìn)行編輯，就需要請(qǐng)求節(jié)點(diǎn)S={h，e}，根據(jù)前面的論述，通過(guò)一個(gè)查找依賴節(jié)點(diǎn)的函數(shù)(DetectTargetedNode( ))得到需要復(fù)制的節(jié)點(diǎn)集合M= {a，b，h，e}，M中的節(jié)點(diǎn)指的是需要復(fù)制的所有的節(jié)點(diǎn)，如果客戶端所請(qǐng)求的數(shù)據(jù)中，一部分節(jié)點(diǎn)有可能已經(jīng)在客戶端存在了，所以只需要返回客戶端沒(méi)有的節(jié)點(diǎn)即可，服務(wù)器端根據(jù)集合M中節(jié)點(diǎn)的復(fù)制類(lèi)型，按照下面的幾種情況以增量的方式返回相應(yīng)的數(shù)據(jù)：

Case1指的是所要復(fù)制的節(jié)點(diǎn)在副本數(shù)據(jù)中不存在，也不屬于客戶端直接請(qǐng)求的節(jié)點(diǎn)，所以是屬于依賴節(jié)點(diǎn)，要把該節(jié)點(diǎn)返回給客戶端，并標(biāo)記為依賴節(jié)點(diǎn).

Case2指的是所要復(fù)制的節(jié)點(diǎn)是客戶端直接請(qǐng)求的操作節(jié)點(diǎn)，所以將該節(jié)點(diǎn)標(biāo)記為工作節(jié)點(diǎn)，并把該節(jié)點(diǎn)返回給客戶端，顯示為工作節(jié)點(diǎn).

Case3指的是該節(jié)點(diǎn)已經(jīng)存在客戶端副本中，客戶端沒(méi)有直接請(qǐng)求作為工作節(jié)點(diǎn)，所以不需要返回任何數(shù)據(jù).

Case4指的是客戶端請(qǐng)求的工作節(jié)點(diǎn)在副本中已經(jīng)存在，是作為依賴節(jié)點(diǎn)存在的，只需要將依賴節(jié)點(diǎn)修改為工作節(jié)點(diǎn)即可，不需要返回該節(jié)點(diǎn)的數(shù)據(jù).

3.4 客戶端與服務(wù)器端的交互

如圖3所示,服務(wù)器端會(huì)同時(shí)處理很多個(gè)客戶端請(qǐng)求，用RBCj和SBCj分別標(biāo)識(shí)對(duì)應(yīng)的客戶端操作隊(duì)列，SBSj和RBSj分別對(duì)應(yīng)其它中心服務(wù)端的操作，從客戶端接收的操作需保存在服務(wù)器端的對(duì)應(yīng)緩存隊(duì)列RBCj中，即將發(fā)送給客戶端的操作，存儲(chǔ)在緩存隊(duì)列SBCj中，當(dāng)對(duì)應(yīng)的用戶進(jìn)入系統(tǒng)或離線狀態(tài)時(shí)，服務(wù)器端只需要?jiǎng)?chuàng)建或者刪除該緩沖隊(duì)列SBCj和RBCj即可，這樣的設(shè)計(jì)在服務(wù)器端會(huì)有很好的擴(kuò)展性，又能節(jié)省不必要的資源.RBSj表示從其他服務(wù)器中心接收的數(shù)據(jù)緩存隊(duì)列，SBSj表示該服務(wù)中心發(fā)送到其他服務(wù)器的緩存隊(duì)列，每個(gè)服務(wù)器都能將更新的操作隊(duì)列主動(dòng)發(fā)送到對(duì)應(yīng)的客戶端或其他站點(diǎn)的中心服務(wù)器.

圖3 系統(tǒng)的分布式結(jié)構(gòu)圖

3.5 服務(wù)器端對(duì)并發(fā)操作的檢測(cè)

因果序列要求：我們的方法要符合正確的因果關(guān)系，根據(jù)之前的協(xié)同編輯理論，在云環(huán)境下我們假設(shè)每個(gè)中心服務(wù)器在發(fā)送給其他服務(wù)器或者客戶端的時(shí)候都是按照相同的因果順序.

算法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的目的是：在服務(wù)器端，有規(guī)律的對(duì)接收到的N路序列進(jìn)行合并，這些序列是上下文有序的，也就是滿足相同的因果關(guān)系的N個(gè)操作序列.例如：有5個(gè)客戶端加入了協(xié)同會(huì)話中，在服務(wù)器端就會(huì)有5個(gè)緩存隊(duì)列來(lái)接受客戶端提交的操作，假如是sqlist[0]，sqlist[1]，sqlist[2]，sqlist[3]，sqlist[4]，首先對(duì)sqlist[0]，sqlist[3]進(jìn)行并發(fā)操作檢查，再對(duì)sqlist[1]，sqlist[4]，最后再將結(jié)果與sqlist[2]進(jìn)行合并檢測(cè).

CNi表示操作O對(duì)應(yīng)的客戶端副本節(jié)點(diǎn)，這里用代碼節(jié)點(diǎn)的標(biāo)識(shí)符來(lái)表示；

Oi指的是代碼節(jié)點(diǎn)CNi對(duì)應(yīng)的操作，緩沖隊(duì)列中的操作都是按照操作的因果關(guān)系存儲(chǔ)的；

T表示操作O在本地編輯完成時(shí)間；

T′表示操作O對(duì)應(yīng)的節(jié)點(diǎn)CN在最近一次與服務(wù)器端完成同步的時(shí)間；

這里的T和T′都是指中心服務(wù)器的物理時(shí)間，在過(guò)去的端對(duì)端架構(gòu)或者一些集中式協(xié)同系統(tǒng)中，很多都是采用二維時(shí)間戳來(lái)表示操作的執(zhí)行時(shí)間，這在共享數(shù)據(jù)是完全復(fù)制的狀態(tài)下是可以適用的，但是在部分復(fù)制的情況下，每個(gè)站點(diǎn)的數(shù)據(jù)狀態(tài)不一致，采用統(tǒng)一的物理時(shí)間在全局中比較容易計(jì)算.

對(duì)于客戶端，緩沖序列RQj中任意一個(gè)操作序列P中，代碼節(jié)點(diǎn)O對(duì)應(yīng)的產(chǎn)生時(shí)間O.T必然大于O.T′，因?yàn)楣?jié)點(diǎn)O在本地產(chǎn)生時(shí)，是與服務(wù)器端進(jìn)行同步完成之后產(chǎn)生的，而在O.T之后產(chǎn)生的新操作必定還沒(méi)有經(jīng)過(guò)中心服務(wù)器的主副本上進(jìn)行同步的，或者是即將提交到服務(wù)器的操作.服務(wù)器端上的RBCj隊(duì)列表示從客戶端接收的操作，根據(jù)操作序列的時(shí)間大小和副本節(jié)點(diǎn)是否相同得出操作之間的并發(fā)關(guān)系，對(duì)于任意兩個(gè)操作Oi和Oj，可以得出以下兩個(gè)結(jié)論：

如果Oi.T

如果Oi.T >Oj.T′ 且Oi.CN=Oj.CN，得出Oi || Oj，Oi并發(fā)于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

這個(gè)函數(shù)的目的是：依次掃描RBCj 和RBSj，集中的找出提交到服務(wù)器端的每組并發(fā)操作序列，其中這些并發(fā)操作包括針對(duì)一個(gè)節(jié)點(diǎn)的操作和針對(duì)不同節(jié)點(diǎn)的操作，如果判斷的是并發(fā)操作，就用HandlerOT函數(shù)也就是操作轉(zhuǎn)換來(lái)解決(下節(jié)會(huì)有詳細(xì)說(shuō)明).同一個(gè)客戶端的一個(gè)操作隊(duì)列中，操作之間的關(guān)系是因果關(guān)系.如果并發(fā)操作對(duì)應(yīng)的節(jié)點(diǎn)之間沒(méi)有依賴或者間接依賴的關(guān)系，可以不用考慮.

根據(jù)定義，如果服務(wù)器端緩存區(qū)接收到一個(gè)操作O，與其并發(fā)的操作，就是執(zhí)行完成時(shí)間T大于 O.T′，且對(duì)應(yīng)的客戶端不相同，其中O.T′就是O對(duì)應(yīng)的副本節(jié)點(diǎn)最近一次與服務(wù)器同步結(jié)束的時(shí)間.

3.6 客戶端的算法設(shè)計(jì)

首先需要滿足一下幾個(gè)性質(zhì)：1.客戶端在任何時(shí)刻都能加入或離開(kāi)一個(gè)合作對(duì)話.2.客戶端能夠獨(dú)立的決定什么時(shí)候與服務(wù)器端進(jìn)行同步.3.服務(wù)器也能單獨(dú)決定什么時(shí)候處理從客戶端接收的操作.4.有高的并發(fā)性，不同的客戶端能夠?qū)蚕砦臋n的任一部分進(jìn)行編輯，能夠避免過(guò)多的交互延遲.5.使用redis緩存隊(duì)列來(lái)做消息處理和任務(wù)調(diào)度.Redis緩存可以是基于內(nèi)存的，可以對(duì)數(shù)據(jù)進(jìn)行快速訪問(wèn)，不會(huì)產(chǎn)生過(guò)多的延遲，并且由于緩存文件可以重復(fù)利用，還可以減少帶寬，降低網(wǎng)絡(luò)負(fù)荷.另外，可以對(duì)緩存隊(duì)列中的每項(xiàng)操作設(shè)置過(guò)期時(shí)間，過(guò)期后可以自動(dòng)對(duì)數(shù)據(jù)進(jìn)行刪除.

算法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

客戶端的算法要更加簡(jiǎn)單高效.客戶端連接到系統(tǒng)之后，先請(qǐng)求所需要的數(shù)據(jù)節(jié)點(diǎn)，系統(tǒng)會(huì)進(jìn)行一些初始化的操作，為客戶端建立必要的數(shù)據(jù)結(jié)構(gòu).客戶端的線程主要是處理本地操作和遠(yuǎn)程并發(fā)操作，這兩個(gè)線程是并行執(zhí)行的，可以有效地利用多核處理器，提高了運(yùn)行效率.

在算法5中，新加入的客戶端首先應(yīng)通過(guò)DetectTargetedNode()請(qǐng)求所需要的節(jié)點(diǎn)，本地產(chǎn)生的操作會(huì)立即執(zhí)行，并存儲(chǔ)在Tj操作集合中，LHB操作緩沖區(qū)存放待發(fā)送到服務(wù)器端的操作，ERMerge( )函數(shù)的作用是使操作序列滿足“effect relation”關(guān)系，這樣能夠加快操作轉(zhuǎn)換的效率.RQj隊(duì)列存放服務(wù)器發(fā)送到客戶端的操作.線程一負(fù)責(zé)本地操作的執(zhí)行，執(zhí)行完本地操作，還需要把執(zhí)行過(guò)的操作先存入緩沖區(qū).線程二負(fù)責(zé)接收從服務(wù)器端發(fā)送過(guò)來(lái)的操作，并執(zhí)行這些操作，因?yàn)檫@些操作是在本地站點(diǎn)執(zhí)行過(guò)的操作或是有并發(fā)關(guān)系的遠(yuǎn)程操作，經(jīng)過(guò)與服務(wù)器端的同步，會(huì)與遠(yuǎn)處站點(diǎn)的編輯操作進(jìn)行一系列的操作轉(zhuǎn)換，返回到客戶端，用來(lái)更新本地站點(diǎn)的副本節(jié)點(diǎn).當(dāng)客戶端接收到Fetch指令時(shí)，客戶端向服務(wù)器發(fā)送本地執(zhí)行過(guò)的操作LHB.

3.7 服務(wù)器端的算法設(shè)計(jì)

算法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

服務(wù)器端的四個(gè)操作隊(duì)列都是先經(jīng)過(guò)操作轉(zhuǎn)換，再在中心服務(wù)器端的主副本上同步執(zhí)行之后的操作.線程1的作用主要是將從客戶端或服務(wù)器端接收到的遠(yuǎn)程操作，按照操作之間的依賴關(guān)系和因果關(guān)系重新排列，這里不是本文研究的重點(diǎn).然后再將接收到的操作分類(lèi)，也就是找出客戶端操作所對(duì)應(yīng)的的并發(fā)操作.線程2的任務(wù)主要是對(duì)遠(yuǎn)程并發(fā)操作進(jìn)行操作轉(zhuǎn)換，再將操作轉(zhuǎn)換結(jié)果應(yīng)用到中心服務(wù)器的主副本上，這樣的目的是為了讓所有的客戶和服務(wù)器都能共享相同的數(shù)據(jù)狀態(tài)，也能保證代碼數(shù)據(jù)的完整性.然后再將操作轉(zhuǎn)換之后的結(jié)果發(fā)送到對(duì)應(yīng)客戶端和遠(yuǎn)處服務(wù)器端.

3.8 解決每個(gè)站點(diǎn)操作的并發(fā)沖突

Fan提出的共享鎖中，如果編輯區(qū)域是在一個(gè)開(kāi)放域中，就不會(huì)發(fā)生語(yǔ)義沖突；如果并發(fā)操作有共同的依賴節(jié)點(diǎn)，也不會(huì)發(fā)生語(yǔ)義沖突；沖突的情況只會(huì)發(fā)生在并發(fā)編輯同一個(gè)節(jié)點(diǎn)，或者是發(fā)生在有依賴關(guān)系或者間接依賴的節(jié)點(diǎn)上.

所以，在服務(wù)器端首先要做的是，當(dāng)檢測(cè)到對(duì)應(yīng)站點(diǎn)的并發(fā)操作之后，就要再次確認(rèn)并發(fā)操作所對(duì)應(yīng)的節(jié)點(diǎn)之間的動(dòng)態(tài)依賴關(guān)系.

如果是并發(fā)對(duì)有依賴關(guān)系的節(jié)點(diǎn)編輯時(shí)，需要用編輯器檢測(cè)或者是發(fā)送消息給客戶端，再次判斷操作的關(guān)系，其中會(huì)出現(xiàn)的三種關(guān)系是兼容關(guān)系，排斥關(guān)系或者依賴關(guān)系.

這樣的方法能阻止語(yǔ)義沖突的發(fā)生，還能保證程序員的連續(xù)工作，即使依賴圖是動(dòng)態(tài)改變的，這中間是沒(méi)有中斷的.

算法7.HandlerOT(Oi)

1.Forall S∈Oido //對(duì)Oi每組并發(fā)操作進(jìn)行分析

2.ifSi.rootNode=Sj.rootNode//有共同的依賴節(jié)點(diǎn)

3.Oiis directly executed

4.elseifSiandSjhas dependent relation

5. ConDetect(Si，Sj)//判斷依賴關(guān)系和沖突檢測(cè)

6.elseSi.ID=Sj.ID//指的是同一個(gè)節(jié)點(diǎn)

7. Awareness solution(Si，Sj)

8.endif

該函數(shù)的作用是對(duì)并發(fā)操作分類(lèi)處理，并發(fā)操作都發(fā)生在開(kāi)放域，則不會(huì)發(fā)生語(yǔ)義沖突，這種情況是直接執(zhí)行的，只需要維護(hù)每個(gè)站點(diǎn)代碼節(jié)點(diǎn)的上下順序一致就可以了，在這里，可以通過(guò)每個(gè)操作的全局標(biāo)識(shí)符，通過(guò)比較標(biāo)識(shí)符的大小來(lái)排序.如果并發(fā)操作所對(duì)應(yīng)的節(jié)點(diǎn)，有依賴關(guān)系的話，就需要進(jìn)行沖突檢測(cè)，使用ConDetect()函數(shù)進(jìn)行沖突消解(下文會(huì)有解釋).如果并發(fā)操作是針對(duì)一個(gè)節(jié)點(diǎn)，就需要用下面的方法來(lái)解決.

如果是針對(duì)同一個(gè)節(jié)點(diǎn)的并發(fā)編輯，操作的類(lèi)型會(huì)有插入，更新，刪除和移動(dòng)節(jié)點(diǎn)，根據(jù)人的編輯意識(shí)操作，采用操作轉(zhuǎn)換對(duì)結(jié)果進(jìn)行合并，這種方法可以有效解決沖突.

算法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

上面的算法展示了并發(fā)沖突發(fā)生在同一個(gè)節(jié)點(diǎn)上的時(shí)候，是如何解決的.如果是兩個(gè)客戶端在相同的節(jié)點(diǎn)下并發(fā)創(chuàng)建新的節(jié)點(diǎn)，根據(jù)前面的許可審查條件，在開(kāi)放域中創(chuàng)建節(jié)點(diǎn)不會(huì)產(chǎn)生語(yǔ)義沖突，這種情況應(yīng)該考慮節(jié)點(diǎn)之間的前后順序即可，可以根據(jù)客戶端的標(biāo)識(shí)符或產(chǎn)生的節(jié)點(diǎn)標(biāo)識(shí)符排序.

算法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

在服務(wù)器端對(duì)并發(fā)操作的檢測(cè)之后，如果并發(fā)操作之間有間接依賴或直接依賴的關(guān)系，則會(huì)調(diào)用算法9.根據(jù)共享鎖的特點(diǎn)和實(shí)際編程中的效果，假如：Oi 對(duì)應(yīng)的節(jié)點(diǎn)是A，Oj對(duì)應(yīng)的節(jié)點(diǎn)是B，B依賴于A，A的操作直接決定著B(niǎo)是否會(huì)有語(yǔ)義沖突，A和B的操作可以是刪除(Delete)，更新(Update)和移動(dòng)(Move)，如果A是刪除，那么B無(wú)論做什么操作，都是無(wú)效的，所以A如果是刪除操作的話，沖突消解的辦法只能是把A和B節(jié)點(diǎn)同時(shí)刪除.如果A節(jié)點(diǎn)是更新或移動(dòng)操作，B節(jié)點(diǎn)是刪除操作，B節(jié)點(diǎn)的操作對(duì)A節(jié)點(diǎn)沒(méi)有影響，所以這兩個(gè)操作是兼容的.如果A和B兩個(gè)節(jié)點(diǎn)都是更新操作，則會(huì)想對(duì)應(yīng)的客戶端發(fā)送消息機(jī)制，可以避免意義沖突的發(fā)生.如果A是移動(dòng)操作，B是更新操作，則不會(huì)發(fā)生語(yǔ)義沖突，這兩個(gè)操作是兼容的.如果A節(jié)點(diǎn)更新，B節(jié)點(diǎn)移動(dòng)，這兩個(gè)操作也是兼容的.如果A和B節(jié)點(diǎn)(在合理的范圍內(nèi)，A節(jié)點(diǎn)一直在B節(jié)點(diǎn)之前)同時(shí)發(fā)生移動(dòng)的操作的話，這兩個(gè)操作也是兼容的.

4 CloudCode原型系統(tǒng)

為了證明算法的合理性，設(shè)計(jì)了一個(gè)基于Vaadin框架的瀏覽器端的java代碼編輯器(CloudCode)，利用Web端軟件良好的跨平臺(tái)性，選擇Java作為目標(biāo)語(yǔ)言，Vaadin作為主要框架，選擇Vaadin的原因是：它所運(yùn)行的代碼都是在服務(wù)器端的，編譯速度快，能夠支持所有的Java庫(kù)，而且開(kāi)發(fā)效率高，只需要Java語(yǔ)言即可，不需要JavaScript和XML進(jìn)行配置.使用基于webSocket的協(xié)議進(jìn)行信息傳輸.

客戶端使用Ace編輯器，Ace只一種開(kāi)源的，基于瀏覽器端的代碼編輯器，能夠支持多種語(yǔ)言，且具有強(qiáng)大的功能.在服務(wù)器端安裝JDK作為分析源代碼的工具.

在服務(wù)器端，JDK作為分析代碼的工具，該應(yīng)用程序的前端包括GUI圖形界面和代碼編輯器.并且使用多線程機(jī)制，可以同時(shí)響應(yīng)和處理多個(gè)客戶端請(qǐng)求.

圖4 前端界面的編輯布局

如圖4是一個(gè)客戶端進(jìn)行編輯交互的界面，客戶端的控制按鈕都是基于JavaScript的Ace editor編輯器實(shí)現(xiàn)基本功能.進(jìn)入該界面的客戶端需要先點(diǎn)擊request請(qǐng)求操作，加載一部分?jǐn)?shù)據(jù)到本地，再返回到CloudEditer編輯器界面進(jìn)行編輯，根據(jù)用戶所編輯的位置信息進(jìn)行監(jiān)聽(tīng)，通過(guò)接口ExamineArea( )進(jìn)行判斷用戶所編輯的操作是在代碼域或開(kāi)放域中，如果是在開(kāi)放域，就不會(huì)與其他客戶端發(fā)生沖突，就不需要與其他并發(fā)編輯的客戶端進(jìn)行意識(shí)交互；如果是對(duì)代碼節(jié)點(diǎn)進(jìn)行編輯，就會(huì)通過(guò)服務(wù)器進(jìn)行檢測(cè)，是否與其他客戶端所編輯的節(jié)點(diǎn)是否是并發(fā)的，如果是并發(fā)操作，就會(huì)HandlerOT進(jìn)行操作轉(zhuǎn)換.

圖5 編輯時(shí)的信息交互模型圖

系統(tǒng)界面左邊可以看到在線人數(shù)，同時(shí)顯示與本地客戶端發(fā)生并發(fā)編輯的客戶端的編輯信息，可以選擇在線人員進(jìn)行交互.如果與并發(fā)編輯的客戶端共同編輯同一個(gè)節(jié)點(diǎn)或者是有依賴關(guān)系節(jié)點(diǎn)時(shí)，會(huì)出現(xiàn)一個(gè)消息提示框，觸發(fā)Awareness solution()和ExaminateCurrent()接口，進(jìn)行判斷操作之間的關(guān)系，或者是給其他客戶端發(fā)送意識(shí)消息，便于能得到更好的結(jié)果，如圖5所示.

5 實(shí)驗(yàn)分析

5.1 復(fù)雜度分析

合理性：整個(gè)程序的運(yùn)行時(shí)間效率分為客戶端效率和服務(wù)器端效率.服務(wù)器端的性能表現(xiàn)在兩個(gè)方面：處理客戶端請(qǐng)求的時(shí)間：a)N路合并的時(shí)間和查找并發(fā)操作的時(shí)間，b)執(zhí)行并發(fā)操作的時(shí)間.客戶端性能也包括兩個(gè)方面：請(qǐng)求目標(biāo)代碼節(jié)點(diǎn)的時(shí)間，執(zhí)行本地操作的時(shí)間和RQj中遠(yuǎn)程操作的時(shí)間.從以上分析可以得出：整個(gè)程序的最終性能取決于客戶端提交的操作數(shù)量和代碼總量.

5.2 樂(lè)觀復(fù)制中的全復(fù)制和部分復(fù)制的對(duì)比分析

如果是采用全部復(fù)制的方法，隨著在線的協(xié)同編輯的用戶的增多，代碼量的不斷增加，傳輸效率會(huì)隨著代碼量的增加而減少，如果加入一個(gè)新用戶，如果在帶寬流量不好的情況下，會(huì)嚴(yán)重阻礙協(xié)同的效率.客戶端的算法是用JavaScript來(lái)實(shí)現(xiàn)的，我們假設(shè)在帶寬充足的情況下，采用Socket協(xié)議進(jìn)行傳輸，分析協(xié)同編輯完成的效率，整個(gè)效率跟每個(gè)客戶端的運(yùn)行效率都有關(guān)系.但是如果采用部分復(fù)制的方法，每個(gè)新加入的客戶端不會(huì)隨著時(shí)間的變化出現(xiàn)效率的降低，因?yàn)檎?qǐng)求加載數(shù)據(jù)量不會(huì)逐漸增大.在線人數(shù)多的時(shí)候，效果會(huì)比較明顯.

6 總結(jié)與展望

本文提出了基于云端的CloudCode編程系統(tǒng)，在算法方面，采用了改進(jìn)之后的TIPs集中式架構(gòu)，運(yùn)用部分復(fù)制提高了系統(tǒng)效率，最重要的是采用共享鎖的思想，使用中心服務(wù)器來(lái)檢測(cè)操作之間的復(fù)雜關(guān)系，檢測(cè)是否會(huì)發(fā)生語(yǔ)義沖突，并阻止了語(yǔ)義沖突的發(fā)生，操作轉(zhuǎn)換的結(jié)果更能符合用戶要求.

在系統(tǒng)架構(gòu)方面，還可以進(jìn)行很多改進(jìn)，可以將軟件應(yīng)用程序設(shè)計(jì)為微服務(wù)架構(gòu)的形式.在協(xié)同編程中，如果要求返回到原來(lái)的版本，對(duì)一系列連續(xù)的操作進(jìn)行撤銷(xiāo)的話，如何高效的進(jìn)行Undo-Redo操作，對(duì)于項(xiàng)目中的一系列文件如何進(jìn)行協(xié)同處理，如何提高用戶的體驗(yàn)度，在數(shù)據(jù)庫(kù)設(shè)計(jì)方面，如何提高檢索效率，這些都是以后研究的方向.