基于事務的分布式虛擬化環境下服務替換方法

鄒世辰 王慧強 呂宏武 馮光升 林俊宇

1(哈爾濱工程大學計算機科學與技術學院 哈爾濱 150001)2(中國科學院信息工程研究所 北京 100093)(zoushichen@hrbeu.edu.cn)

分布式虛擬化環境(distributed virtualized environment, DVE)[1]是一類以分布式虛擬化技術為核心的通用計算環境，具有顯著的開放、共享、動態、透明等特性.受到“一切皆服務”的思想啟發以及服務虛擬化技術的普及與發展，DVE下的服務數量呈現爆炸式增長，虛擬化映射后的服務通過動態組合來構建軟件系統的方式已然成為主流.面對著工業、農業、制造業、服務業、教育業等領域的業務需求，服務組合的可信性保障成為一個備受關注的研究熱點.由于各式各樣的服務運行在開放動態的DVE中，各種異常、失效、故障均可能導致服務可信性的降低，因此需要實現服務在線演化，即服務組合在外部環境和用戶需求發生變化時能夠進行適應性變更，并保持服務與相關應用有效性.作為服務可信性保障的重要一環，組合服務演化是一個非常復雜的處理過程.當組成服務組合的服務組件失效時，選擇與其功能相似且參數匹配服務組件進行服務替換已成為一種非常重要的技術手段.服務替換可以保證服務組合后續正常運行，避免服務可信性降低，受到工業界與學術界的廣泛關注.

傳統的服務替換大多采用備份路徑替換[2-3]、基于功能分簇替換[4-5]等策略，這些方法與策略能夠在一定程度上適應環境變化，保證系統不被中斷地運行下去，但這些方法忽略服務的事務屬性，缺乏對服務事務原子性和一致性的保障，直接造成了服務組合替換的正確率低、效率差，因此在實時變化的DVE中支持事務級的服務替換，提高服務異常處理的能力十分重要.但是事務級服務替換也面臨著一系列的挑戰，例如傳統的2階段提交機制需要對資源進行阻塞，顯然不適用于運行時間跨度普遍較大的服務組合中，需要適度放寬對事務原子性、隔離性的要求來提高資源并發使用的效率.同時，服務的動態組合決定了事務粒度不可能由單個服務組件的開發者決定，動態綁定的運行方式也使得服務組合依賴關系較為復雜，如何確定事務級替換粒度以及級聯補償范圍成為一個不可回避的難題.此外，大多數相關研究都是在故障或失效發生后如何觸發服務替換，卻對替換服務的選擇上有哪些事務級的限制鮮有提及，選取具有合適屬性的服務來進行替換也是軟件演化與可信性保障方法中十分值得關注的.

基于以上考慮，本文提出了一種基于事務補償的分布式虛擬化環境下服務替換方法，實現支持事務級的服務替換，維護服務組合在替換過程中的一致性為實現面向可信性保障與增強的服務組合演化提供支撐.本文的主要貢獻如下：

1) 提出了一個支持事務級屬性的層次化服務組合模型，使用擴展層次化有色網并結合服務事務屬性來描述服務組合中復雜的數據流關系，通過層次嵌套的方式來降低模型復雜度，避免后續分析過程中狀態空間爆炸問題；

2) 提出了服務事務粒度識別與服務替換補償方法，通過數據依賴關系來有效識別服務組合事務范圍，進而在服務替換時針對同一事務的服務組件進行補償，來維護服務組合的一致性；

3) 基于事務粒度識別與服務補償，提出了一種服務組合失效處理方法，并充分考慮候選替換服務選擇的事務屬性限制，為選擇合適的服務組件或組合服務來替換失效部分提供指導，促使服務組合的可信性增強演化.

1 支持事務級屬性的層次化服務組合模型

1.1 基本定義

為便于后續闡述和分析，本節給出一個“商務旅行”的組合服務作為實例，如圖1所示.用戶首先根據到達目的地距離、時間等情況選擇出行交通工具，通過“預訂機票”或者“預定火車票”等服務來實現，同時用戶需要查詢并預定一個目的地賓館，執行“預定賓館”服務；然后根據預定的出行方式以及酒店位置，規劃出行路線，并預定出租車來完成出行.

服務組合的基本單元是操作.圖1中所給出的服務活動大多為業務級服務，與只包含一個操作的簡單服務不同，每個業務服務可能包含著一個或多個操作，甚至嵌套著其他業務服務.如搜索航班的業務服務中包含著預訂操作、支付服務和出票操作，支付服務中還包含著支付請求、網上銀行支付等操作.

由圖1的實例可以看出，組合服務自身是存在著層次關系的，其間的數據依賴、控制關系更是錯綜復雜的，一旦某處失效，必然會導致整個組合服務的連鎖反應.在預定車票的服務中，當進行到Payment時可能由于網絡中斷等原因導致支付失敗，但是前期預訂車票的操作已經被提交，就會出現車票被預訂出去，但是由于支付失敗未能出票，而其他用戶又無法購買這張車票的情況.在無事務的服務替換過程中僅僅替換失效的支付服務，那么新啟用的支付服務勢必需要預訂服務重新發起一次支付請求來作為輸入，這會造成重復預訂，進而導致數據一致性的破壞.由此可見，預訂、支付、送票這一系列的服務操作必須作為一個事務，當支付服務失效時，需要對預訂服務來進行補償(即撤銷預訂的車票).

1.2 擴展層次化有色網

為了準確描述組合服務中層次結構以及各個部分之間數據控制關系，從而對服務組合中的事務粒度與服務替換補償方法進行分析，本節使用擴展層次化有色網對服務組合的組件及其消息交互進行建模.首先給出一些符號的定義：

1)Type表示變量或表達式的類型.

2)Var表示表達式的變量集合.

有色Petri網通過擴展Petri網的令牌機制，使其具有顏色和類型，能夠用于描述復雜的數據對象，同時也解決了普通Petri網中的二義性問題.但是使用普通有色網中單一的變遷類型難以表達服務組合中豐富的組合模式，因此引入擴展有色網ECPN(extended color Petri net)，將變遷根據其功能分為4類.

定義1. 一個ECPN是滿足下列條件的八元組，ECPN=(P,T,C,A,Cd,G,E,I)，其中：

1)P是庫所的有窮集合.

2)T是變遷的有窮集合，且P∩T=?.在擴展有色網的變遷中引入如下類型變遷.

① 服務處理變遷，當變遷被觸發后調用相對應的服務來完成動作.

② 流程控制變遷，根據服務流程的狀態與條件，產生不同的控制托肯，觸發不同的變遷，進入不同狀態.在針對并發服務時，用于協調各變遷之間的同步.從而加強網的數據流描述能力，豐富了網的語義表達功能，有助于模型的建立和理解.

③ 接口變遷，用來設置條件，判斷某上層網絡輸出令牌的顏色和數量與子網絡要求的輸入令牌是否一致.

④ 空變遷，相當于空轉移，滿足某些特殊情況下的有色網定義.

3)C是顏色類的有窮集合.

4)A是弧的有窮集合，P∩A=T∩A=?.

5)Cd是顏色函數，Cd:P∪T→C.

6)G是哨函數，G:T→expr且滿足?t∈T:[Type(G(t))=Bool∧Type(Var(G(t)))?C].

7)E是弧表達式函數，E:A→expr且滿足?a∈A:[Type(E(a))=Cd(p(a))MS∧Type(Var(E(a)))?C]，其中Cd(p(a))MS表示顏色集合上的所有多重集合的集合.

8)I是初始化函數，I:P→expr且滿足?p∈P:[Type(I(p))=Cd(P)MS].

由于ECPN中引入了變量和顏色，需要對變遷進行綁定.變遷的綁定是指將變遷中的每個變量用一種適當的顏色代替，并且滿足弧表達式，從而使得哨函數為真.

ECPN通過對變遷的多樣化，實現了對服務組合的復雜模式的描述，但是復雜的大型組合使得Petri網十分龐大復雜，因此引入層次化思想，形成擴展的層次化擴展有色網EH_CPN(extended hierarchical color Petri net)，通過分層描述，減小模型的復雜度，有效改善非層次化模型在描述大型Web服務組合時，狀態迅速膨脹，使得分析變得困難的狀況.

Fig. 3 The EH_CPN model of business travel service composition圖3 “商務旅行”服務組合EH_CPN模型

定義2. 一個EH_CPN是滿足下列條件的四元組，EH_CPN=(S,C,IC,I0)，其中：

1)S是子網的有窮集合，且滿足以下條件.

① ?s∈S，s=(ECPN,Ci,Co)，其中Ci和Co分別是輸入和輸出顏色的有窮集合.

② ?si，sj∈S，si≠sj∧(Psi∩Tsi∩Asi)∪(Psj∩Tsj∩Asj)=?.

2)C是顏色類的有窮集合.

3)IC是接口驗證函數，用于測試上層網絡輸入的token類型和數量是否符合要求，IC:I0→expr，且滿足Type(IC(I0))=Bool.

4)I0是初始狀態.

服務組合由一系列的服務或服務組合通過組合控制結構組合而成，通過分析其間邏輯關系，可以將這些控制結構分為5類[6]，分別是Sequence，And-Join，Or-Join，And-Split，Or-Split.包括循環結構在內的大部分復雜控制結構均可由這5類邏輯關系以及流程控制變遷組合而成.5類控制結構如圖2所示：

Fig. 2 Service composition control structure圖2 服務組合控制結構

為使服務變遷在沒有數據依賴時推動組合流程繼續執行，在EH_CPN模型中引入控制托肯，只有當變遷獲得控制托肯才能被觸發.控制托肯可以單獨的在網內流動，也可以和數據托肯混合流動，所構成的控制流不影響模型數據流的分析.對于需要根據服務組件的特定狀態來決定服務組合控制流等復雜情況，由于需要服務組合執行引擎提供活動實例執行情況的監視結果，模型無法提供直接支持，因此本文不做討論.圖1中服務組合經過EH_CPN建模后，如圖3所示.

為節省空間，圖3中省略了不同層次子網間的接口變遷.通過分析模型中可以得到庫所顏色集以及變遷顏色，如航班預定服務中的支付子服務組合中的變遷顏色Cd(PayRequest)={(CreditCard,FlightOrder,PaypalReq,EbankReq)|(CreditCard∧FlightOrder∧PaypalReq)∨(CreditCard∧FlightOrder∧EbankReq)}，Cd(Paypal)={(PaypalReq,PayInfo)|PaypalReq∧PayInfo}，模型其他部分的分析結果不再贅述.

1.3 事務屬性

事務是一組在邏輯上屬于一個單元的操作，這些操作要么全部生效，要么全部沒有發生.傳統的事務應當遵從ACID原則，即原子性(atomicity)、一致性(consistency)、隔離性(isolation)、持久性(durability).對于服務組合這類的跨組織協作的系統，顯然需要放開一些隔離性等方面的限制，但是一致性是必須被強制要求的.由于服務組件中的表現行為、依賴關系與服務組合中的有著一定的區別，事務屬性可被區分為服務的事務屬性和服務組合的事務屬性[7].

定義3. 服務的事務屬性用于保證服務執行過程中一致性，包括關鍵性(pivot)、可補償性(compensatable)和可重試性(retriable)，其中：

1) 關鍵性.具有關鍵性的服務一旦執行成功，其對系統的影響將持續下去，不可回滾或恢復，它并不保證服務一定成功執行，如果執行失敗將不對已執行的服務的結果產生任何影響，記作p.

2) 可補償性.具有可補償性的服務被執行后，可調用另外一個相應的服務來還原已經完成的活動，一般包括向前(替換)和向后(回滾撤銷)2類補償操作，記作c.

3) 可重試性.具有可重試性的服務可以被有限次的重復調用，直至執行成功，記作r.

一般而言，如果一個服務不是可補償或可重復的，那么它一定是關鍵性服務.服務的事務屬性可以相互疊加，具體的可能出現的屬性包括{p,c,pr,cr}.具有這些屬性的服務即可稱作具有事務屬性的服務.

定義4. 服務組合的事務屬性用于保證服務組合執行過程中一致性，包括原子性(atomic)、可補償性(compensatable)和可重試性(retriable)，其中：

1) 原子性.具有原子性的服務組合中，所有服務組件執行成功后的結果均不可回滾或恢復，如果某組件失效，則所有已執行的服務組件需要被補償，記作a；不具有原子性的服務組合用～a表示.

2) 可補償性.具有可補償性的服務組合中，所有服務組件都可以補償，記作c.

3) 可重試性.具有可重試性的服務組合可以被有限次的重復調用，直至執行成功，記作r.

服務組合的事務屬性也可以相互疊加，具體的可能出現的屬性包括{a,c,ar,cr}.一個服務組合只要具有上述集合中任何一個屬性，則這個服務組合就被稱作具有事務屬性的服務組合.

由于服務通常是長時間運行的，是典型的長事務，為了維持數據一致性，直接采用數據庫系統中資源鎖定的方式顯然不適用，由此引入的服務補償的概念來維持服務系統的一致性.

定義5. 服務補償.在服務發生故障或失效時，用來撤銷已完成的服務活動所產生的執行效果的操作.

服務補償通常作為服務的事務性保證最有效的手段，最先由Garcia-Molina和Salem在定義的Saga模型[8]中提出來.其中每個可補償的子事務都有一個對應的補償塊，通常由服務開發者預先提供.如果某事務發生失效，則從失效部位出發，根據服務的控制流、業務流和數據流等依賴關系確定補償范圍，按照子事務被提交的逆序調用每一個子事務對應的補償塊.由此可見，事務粒度的識別以及補償圖的生成是能否維持服務組合系統一致性的重中之重，同時由于業務級聯所帶來的級聯補償問題也同樣對失效處理與服務替換的成功有著極大影響.

2 事務粒度識別與補償方法

服務是典型的長事務，同時不同的服務來自不同地域、不同開發者，服務之間各種數據流、控制流錯綜復雜，使得業務流程中的事務粒度和范圍無法由服務提供商來給定.因此為了保證支持事務的服務組合系統中數據一致性，需要先識別得到事務的粒度，進而采用服務替換、失效補償等手段來維持服務系統的穩定運行.組合服務間的事務范圍的獲取主要還是由依賴關系來決定的，其中最重要的就是數據依賴關系.

2.1 數據依賴關系

服務組合中各組件之間的交互是基于XML消息報文的，因此數據依賴關系可以通過分析服務間交互信息，從報文中包含的各種變量的生成與使用情況可以獲得數據流在不同服務組件之間的流動情況.與傳統應用程序變量有所不同，服務組合中變量不是最小單元，而是由更小粒度的類型復合而成.結合EH_CPN模型來看，數據在服務組件間的流動可以被映射為數據托肯在變遷的流動，變量則是服務變遷消耗或生成的數據托肯集，庫所則是提供了一個變量緩存的場所，通過分析定義在變遷上的顏色就可以有效地分析出帶有顏色的數據托肯的消耗和生成情況，進而可以得到服務組合的數據流.由模型中的變遷顏色所得到的數據定義與使用關系，可以將服務組件間的數據依賴分為直接依賴關系和間接依賴關系.

定義6. 直接依賴關系.服務變遷ST1定義的數據被服務變遷ST2使用，那么ST1和ST2存在直接依賴關系，記作D_Dep(ST1,ST2).

服務組合中所有服務變遷間的直接依賴關系的集合可由算法1獲得.

算法1. 構建直接依賴關系.

輸入:服務組合EH_CPN模型SC;

輸出:數據依賴集D_Dep.

ForeachtinSC

Iftnot inSTthen

continue;

Else

ForeachcinCd(t)

IfcinType(Var(AIN)) then /*AIN為變遷t的輸入弧*/

Puttinuse(c); /*use(c)為顏色c所代表的變量的使用者集合*/

Else IfcinType(Var(AOUT)) then

/*AOUT變遷t的輸出弧*/

Puttindef(c); /*def(c)顏色c所代表的變量的定義者集合*/

End If

End Foreach

End If

End Foreach

ForeachcinC

Ifdef(c)=? oruse(c)=?

continue;

Else

Foreachst1 indef(c)

Foreachst2 inuse(c)

PutD_Dep(st1,st2) inD_Dep;

End Foreach

End Foreach

End If

End Foreach

ReturnD_Dep.

存在直接依賴關系的服務變遷之間并不一定是通過庫所直接連接，之間可能間隔控制變遷、接口變遷甚至是不涉及變量消耗的服務變遷.此外需要注意的是D_Dep(ST1,ST2)不等價于D_Dep(ST2,ST1)，即依賴關系不符合交換律.但依賴關系是可傳遞的，從而構成了間接依賴關系.下面給出間接依賴關系的定義.

定義7. 間接依賴關系.如果服務變遷ST2利用服務變遷ST1定義的數據作為輸入，進而定義了新的數據被服務變遷ST3使用，則稱服務變遷ST1和ST3之間存在間接依賴關系，記作I_Dep(ST1,ST2).

定義8. 數據依賴集.所有和服務變遷ST存在直接依賴關系和間接依賴關系的服務變遷構成的集合稱為數據依賴集，記作DepSet(ST).

由定義顯然可知，對于STi∈DepSet(ST)，滿足D_Dep(STi,ST)或者I_Dep(STi,ST).通過直接和間接的數據依賴關系，我們可以采用遞歸調用的方法，沿著服務變遷組合的EH_CPN模型中連接庫所與變遷間的弧，逆向構建生成關于某個服務變遷ST的數據依賴集.

通過對服務組合中某個組件的數據依賴關系分析構建得到的數據依賴集，可以直觀地反映出數據流影響的范圍，但是由于服務組合中各部分的運行通常是并發，而數據依賴集只能體現出順序的數據調用與被調用，無法用于分析并發分支間的數據依賴情況，因此需要對數據依賴集進行擴展，從而實現服務組合事務范圍識別.

2.2 服務組合事務范圍識別

服務組合中的事務范圍識別直接關系到服務替換時能否有效地維護數據一致性，只有正確識別事務粒度和范圍大小，才能明確如何在服務替換后對服務組合中有數據依賴的部分進行補償.由2.1節得到的數據依賴集僅能支持在邏輯上沿著數據流動的方向順序找到位于失效服務前的服務，對于并行分支間存在的間接或嵌套依賴顯得無能為力，因此僅靠數據依賴集來確定服務組合事務范圍是不完整的.需要結合服務組合的EH_CPN模型以及前文提出的分支結構補償處理的方法，將數據依賴集擴展成為依賴圖，從而到達準確識別服務組合事務范圍的效果.面向一致性維護的服務組合事務范圍主要是由數據依賴關系決定，顯然與失效待替換部分有著數據依賴的服務組件必須加入到事務中來，在服務替換之后需要對已完成的部分進行補償.但由于服務組合中的控制結構復雜多樣，因此需要根據服務組合過程模型的控制結構和數據依賴關系的不同來分別處理.首先定義補償關系：

定義9. 補償關系.如果服務變遷ST2發生服務替換后需要對變遷ST1進行補償來維護服務組合的一致性，則稱服務變遷ST1和ST2之間存在間接依賴關系，記作Comp(ST1,ST2).

由1.2節可知，組合過程的控制結構可分為Sequence，And-Join，Or-Join，And-Split，Or-Split，大部分復雜控制結構均可由這5類邏輯關系以及流程控制變遷組合而成.因此本節針對這5種最基本的控制結構，結合EH_CPN模型來對事務范圍的識別作出如下處理：

1) Sequence.服務變遷ST1與ST2之間是Sequence結構時，如果ST1與ST2之間存在依賴關系，顯然ST2失效時需要對ST1進行補償，即Comp(ST1,ST2)，ST1以及ST1與ST2之間所有順序相連的變遷都需要加入事務范圍中.

2) Or-Split.由于分支結構間是互斥的，所以只有失效服務變遷所在分支被觸發激活，只需將該分支內有依賴關系的服務變遷加入事務范圍，不同分支間無需處理.

3) Or-Join.與Or-Split類似，如果后續服務失效時，只需對已觸發完成的分支內存在數據依賴的服務變遷加入事務范圍，其他分支無需處理.

4) And-Split.不妨設ST2和ST3是And-Split中并行的2個分支且ST1與ST2∧ST3構成Sequence.①如果ST2與ST1存在數據依賴，則ST2失效時需要對ST1進行補償，即Comp(ST1,ST2)，同時由于ST1被觸發補償，ST3作為ST1并行分支，該分支上所有已完成的服務也需要被補償，因此均需要加入事務范圍；②如果ST2與ST1不存在數據依賴，則ST2失效時不需要對ST1以及ST3所在分支進行補償，因此無需處理.

5) And-Join.不妨設ST1和ST2是And-Join中并行的2個分支，如果ST1和ST2間存在數據依賴，則Comp(ST1,ST2)，不同分支內的服務變遷需要加入事務范圍進行補償；如果ST1和ST2間不存在數據依賴，則不同分支間不需要加入事務范圍進行補償.

經過上述對于屬于不同控制結構的服務變遷進行分析，可以得到服務組合中的所有事務的范圍.由于篇幅限制，該算法不做具體偽代碼描述.針對并行的And-Split和And-Join情況，以圖4為例進行說明.圖4針對圖1流程中的訂機票階段進行了改動，訂機票服務將根據所訂機票的起飛機場不同，同時并發地預訂到達起飛機場的出租車，只有在訂票和訂車2個支付全部成功后才能觸發送機票服務，因此2個并行分支構成了And-Split和And-Join結構.當機票支付服務失效時，由于與預訂服務存在著數據依賴，根據前文提出的方法，預訂出租車的服務也要補償(沒有成功購買該機場出發的航班也就沒有必要坐出租車去該機場).如果送票服務失效，由于只有機票支付服務與其有數據依賴，因而不需對出租車支付服務進行補償(但由于與機票支付服務間And-Split結構，最終出租車支付服務還是需要補償).與此同時，機票和出租車的支付服務經過合并所得到的嵌套服務，與預訂服務、送票服務間構成了Sequence結構，由于各個服務間均存在數據依賴，因此這些服務共同屬于一個事物范圍.

Fig. 4 The compensation of And-Join and And-Split圖4 And-Join和And-Split時的補償

2.3 補償圖生成與服務失效處理

在獲取服務組合中各組件之間的數據依賴關系以及確定事務范圍之后，就可以對服務組合中失效部位進行替換，并生成補償圖.補償圖是是服務組合失效部位及其所在事務范圍內部分構成的集合，是服務組合失效處理器進行服務替換補償時的執行路線.補償圖實質上是在原服務組合模型的基礎上，生成了一個由補償服務構成的一個子服務組合.依賴圖的生成只需要對2.2節得到的依賴圖所對應的事務與原服務組合EH_CPN模型的交集，將弧的方向取反，構成補償路線圖，算法細節不再贅述.根據動態生成的補償圖，從失效替換部位對所在事務范圍內的其他服務組件選取適當的補償服務進行補償，以維持整個服務組合系統處于語義上的一致狀態.

在獲得補償圖的基礎上，結合服務的事務屬性，本文進一步提出基于事務級服務替換的服務組合失效處理算法,詳細過程如下：

算法2. 失效處理算法.

輸入:服務組合EH_CPN模型SC、失效服務fs;

輸出:自動失效處理結果.

Iffsis retriable Then

rebootfs;

Else

subs(fs); /*進行服務替換*/

cg=compensategraph(fs); /*構建fs的補償圖*/

Foreachstincg

Ifstis compensatable Then

compensatest; /*對補償圖內所有服務進行補償*/

Else

Return Failed; /*如果st不能補償，

則終止算法，等待人工介入*/

End If

End Foreach

Return Success;

End If

算法2中，首先如果失效服務具有r事務屬性，說明該服務能重啟，那么就先嘗試重新激活該服務并運行，直到成功完成，如果不能重啟則需要替換該服務，并對事務范圍的其他服務進行補償.具體補償過程是先在事務范圍內，根據失效服務生成的補償圖；然后從失效部位開始反向向前的、針對已執行完畢的服務進行補償，如果事務范圍內的某一服務或服務組合不能被補償(不具有補償屬性或者沒有補償服務操作)，則服務失效的自動處理失敗，終止算法并請求人工介入處理.

2.4 替換服務選擇的事務屬性限制

在服務失效補償完成之后，為了維持服務組合的繼續運行，需要選擇合適的服務組件或組合服務來替換失效部分.然而替換服務的選擇上，傳統方法大多僅是從QoS優化的角度出發，很少有考慮替換服務的事務屬性.如果替換服務的事務屬性選擇不當，會破壞原組合服務的事務性，從而導致后續失效處理上的失敗，降低了服務可信性.由于QoS最優化的替換服務可能不符合服務組合事務性要求，所以需要實現對待替換部位給出嚴格的事務性限制.

由于補償是一種向前的、針對已成功執行的服務所采取的失效處理手段，所以本文在討論事務屬性限制時只需考慮與待替換服務的部分有數據依賴的服務.此外由于Or-Split與Or-Join所構成的分支結構是互斥的，在服務組合流程控制完成分支選擇后實際上已經變為了一種Sequence結構，因此本文在分析待替換服務選擇時只需對順序結構和并行分支進行分析.具體分析如下：

1) 順序結構.①如果待替換的服務變遷ST2前的服務處理變遷ST1所對應的服務/服務組合的事務屬性是帶有p/a的(p,pr/a,ar)，由事務屬性定義可知ST1的執行效果是不能撤銷，后續服務失效時不能被補償，因此ST2必須保證執行成功，而只有r屬性能保證服務肯定能夠執行成功，所以ST2只能選擇pr/ar和cr中任意一種屬性的服務/服務組合.②如果ST1的事務屬性是帶有c的(c,cr)，由事務屬性定義可知ST1的執行效果在后續服務失效時可以被補償，因此ST2的事務屬性不做限制.

2) 并行結構.①當待替換的服務變遷ST2和ST1構成并行分支時，如果ST1所對應的服務/服務組合的事務屬性是p/a，由事務屬性定義可知ST1的執行效果是不能撤銷，ST2失效時不能被補償，因此ST2必須保證執行成功，同時在ST1失效時必須能夠被補償，所以ST2只能選擇cr屬性的服務/服務組合.②如果ST1所對應的服務/服務組合的事務屬性是pr/ar，由事務屬性定義可知ST1肯定能執行成功，但不能被補償，因此ST2必須保證執行成功，所以ST2只能選擇pr/ar和cr中任意一種屬性的服務/服務組合.③如果ST1所對應的服務/服務組合的事務屬性是c，則ST1成功執行的效果可以撤銷，但是不能保證一定成功，所以ST2必須能夠在ST1失效時可以被補償，ST2只能選擇c和cr中任意一種屬性的服務/服務組合.④如果ST1所對應的服務/服務組合的事務屬性是cr，則ST1執行的保證一定成功，成功執行的效果可以撤銷，所以ST2的事務屬性不做限制.

具體的待替換服務限制如表1所示：

Table1TheTransactionAttributeLimitfortheServicetobeSubstituted

表1 待替換服務事務屬性限制

對于待替換服務進行事務屬性的限制，不僅能夠維護原服務組合的事務不被破壞，而且通過替換合適的服務組件，可以進一步提升服務組合的事務機制的完備性，促進整個系統向著提升可信性的方向演化.

3 實驗分析

本文提出了一種基于事務與補償的服務替換方法，為了評估該方法的性能與正確性，本節將在服務組合仿真環境下與相關算法進行實驗對比，通過判斷服務替換觸發后失效是否成功恢復為標準，在算法效率與一致性等方面來分析不同算法之間的性能差異.

3.1 實驗準備

首先需要設置仿真對比實驗用的場景，為了貼近實際運行環境中服務組合的構建情況與運行狀態，本文采用一種人工生成與隨機匹配的方式.采用這種方式的原因主要是：一方面由于服務對于用戶是透明的(僅接口可見)，導致基于BPEL等規范的開源服務組合流程非常有限，難以大量收集來構造優質可靠的實驗數據集；另一方面目前能夠獲得開源服務組合實例大多非常簡單，組合包含的服務數量普遍在4個以下，不足以體現“一切皆服務”的大規模應用趨勢.實驗場景的生成具體而言，首先使用改進的Salama網絡拓撲隨機生成算法生成100個節點的服務組合運行的網絡環境.服務數據采用人工生成的方式，搜索采集100個服務，每個服務含有服務名稱、服務操作、參數接口、補償服務等信息，并映射在事先隨機生成的網絡拓撲中，將隨機拓撲中鏈路時延作為服務通信時延，節點時延作為服務處理時延.按照數據接口與語義匹配來隨機組合服務，從而得到若干不同規模的服務組合.

目前通用的面向事務級的服務替換和恢復算法較少，因此本文在對比實驗中加入了傳統不支持事務級替換的Yu算法[2]，該算法將所有已完成服務視作一個事務，在服務失效時將嘗試補償全部已提交的事務.此外還選擇面向長事務的失效恢復LHFR算法[9]，通過在仿真環境中向服務組合隨機注入故障，觸發服務替換與失效恢復的方式來與本文提出的算法比較分析.

3.2 實驗結果與分析

為了驗證本文提出的支持事務級的服務替換方法能夠正確、有效地處理服務組合運行過程中出現的故障、失效等問題，首先需要對算法的正確性進行實驗.通過對服務替換與失效處理后的服務狀態一致性進行驗證與分析，來證明基于事務級服務替換的失效處理方法能夠正確地處理服務替換過程中服務一致性保障問題.

雖然事務的最小單位是一組在邏輯上屬于一個單元的操作，但在實際服務組合系統中最小可操作粒度是組件服務或原子服務，事務可能對應單個的原子服務，也可能是多個組件服務構成的集合，因此通過服務運行信息可以獲得所對應事務的運行狀態信息.服務在生存周期內所處的狀態包括initial，active，failed，completed，aborted，cancelled等，根據收發的報文信息以及內部邏輯運行情況，服務在不同狀態間進行自動切換.在仿真服務節點上擴展加入服務狀態的自動機，模擬服務所處運行狀態的切換.通過隨機故障注入，即隨機選取服務組合中的某個部位，以不同的故障概率使服務進入failed狀態來觸發替換與失效恢復，根據具有的事務屬性的服務所處的狀態變化情況，觀察該服務以及對應的事務能否通過補償機制正確回滾至initial或者通過重啟達到completed，以此來考察事務級服務替換及失效處理后服務一致性.為了有效測試服務失效處理的正確性，本實驗中假設所有的服務均可以補償.圖5～6表示的是在節點數100的服務組合上，以不同的概率進行故障注入時服務一致性的評價結果.

Fig. 5 Number of transaction recovery圖5 事務恢復的個數

圖5分別記錄了通過補償(compensate，C)機制回滾恢復服務一致性的事務個數和通過重啟(reboot，R)完成事務恢復的個數，圖6記錄了事務恢復的成功率.通過實驗結果可以看出，在故障率較低的條件下，服務組合中的事務能夠通過重啟成功執行或者補償來恢復到初始狀態，呈現出較好的事務恢復成功率；當故障率增高時，事務恢復的成功率有所下降，但均能維持在85%以上較好的恢復成功率.有實驗驗證結果可以看出，本文提出的算法可以很好地維護事務服務狀態，有效保障服務替換過程中服務一致性.

Fig. 6 Transaction recovery success rate圖6 事務恢復的成功率

下面通過在仿真環境下測試服務組合運行時間，來說明事務級服務替換算法對于維持服務一致性，支撐服務組合系統穩定運行的關鍵作用.同樣假設服務組合中所有的服務組件都可以補償.選取5組不同規模的服務組合，在每組服務組合中選擇相同的位置、以不同的故障注入率下進行隨機故障注入，觸發失效處理，記錄服務組合的平均執行時間，其中包括服務正常時間以及服務失效時進行替換與補償的時間.為體現算法的性能優勢，將本文算法與傳統Yu算法、LHFR算法進行對比，由于傳統的Yu算法不支持事務范圍識別，因此Yu算法將整個服務組合視作一個事務，在失效處理時對全部已提交的部分進行補償.圖7～9顯示了在包含20，40，60，80，100服務組件的服務組合中，故障注入概率1%，2%，3%條件時，分別引入本文算法與Yu算法、LHFR算法后服務組合的平均執行時間.

Fig. 7 Average execution time of service composition (fault injection probability 1%)圖7 服務組合的平均執行時間(故障注入概率1%)

Fig. 8 Average execution time of service composition (fault injection probability 2%)圖8 服務組合的平均執行時間(故障注入概率2%)

Fig. 9 Average execution time of service composition (fault injection probability 3%)圖9 服務組合的平均執行時間(故障注入概率3%)

由實驗結果可以看出，隨著服務規模的增大以及故障率的提高，服務運行時間呈現出增長的趨勢，但總體而言支持事務級服務替換與失效處理方法在運行時間上要明顯優于Yu算法，這是由于支持事務級的算法能夠按照事務粒度劃分，識別事務補償的范圍，降低失效恢復時間.其中本文算法在服務運行時間上要微弱地優于LHFR算法，這是由于失效恢復時，本文算法能夠識別出與失效服務存在數據依賴，會導致一致性缺損的服務并補償，有效控制影響范圍，而并非像LHFR算法一樣采用按照服務執行歷史進行完全回滾的方法來進行失效處理，從而省去了維護龐大的服務執行歷史圖的時間，降低了服務組合的平均執行時間.

下面對服務替換與失效處理過程中的人工介入率進行考察，來分析算法性能.本實驗中假設所有的服務中有不同的概率是關鍵性服務，是不可以補償的，一旦失效恢復失敗就會終止算法并請求人工介入處理.該實驗設置為在一段時間內重復運行服務組合，一旦失效自動恢復失敗觸發人工介入，則記錄下來并重啟整個服務組合繼續運行.人工介入率就是記錄服務組合在失效發生后不能自動進行替換與補償處理，需要人工介入的次數與總運行次數的比率.越低則說明算法自動化程度越高，失效處理的性能越好.假設在包含60個服務組件的服務組合中有10%的概率是不可補償的，圖10顯示了故障注入概率分別為1%，2%，3%時，分別引入本文算法與Yu算法、LHFR算法后服務組合的人工介入率.

Fig. 10 Manual intervention rate圖10 人工介入率

從實驗結果可以看出，在介入率指標上本文提出的算法明顯較好，這是由于本文算法引入替換屬性限制，通過事務級服務替換實現了面向一致性維持的服務組合演化，提升服務組合系統的可信性保障能力，使得服務的自動失效恢復的成功率有了提高，減少了因無法補償而需要人工介入進行干預的概率，從而縮短失效恢復所需時間，提升整個服務組合系統的MTTF(mean time to failure).同時也可以看出關鍵性服務越多，說明服務事務性越差，在發生失效觸發替換時難以自動進行補償處理來維護一致性.

由于服務組合是動態綁定，且實際環境中服務運行情況十分復雜，測試服務替換算法需要服務監控、服務選擇與匹配、故障注入等技術的協同合作，顯然超出本文研究范圍.本文實驗用的仿真環境中雖然忽略了服務組合在實際專業應用背景下的業務流程與需求，但足以驗證算法的正確性與有效性.

4 相關工作分析

服務替換是在服務發現與服務匹配的基礎上的，選擇替換用的服務勢必需要進行服務匹配，以滿足用戶對于替換服務功能屬性方面的需求，因此分析服務發現與匹配相關研究十分有必要.Zhou等人[10]將面向服務計算環境下的服務劃分為EP(effect-providing)服務和DP(data-providing)服務，通過建立域本體模型來對DP服務進行分類，并通過計算服務向量距離來實現服務聚類，以便用戶發現與選擇匹配.但是服務替換并不單純等同于服務匹配，因為服務是一個動態綁定運行的過程，服務組合中各組件之間通過消息報文實現業務通信與數據交換，為保障服務組合的整體可信性，服務替換過程需要綜合考慮組合上下文、服務接口兼容等多方面的因素.

對此，學術界和工業界開展了大量的研究，而綜合來看，服務替換的方法大致可以分為面向功能的服務替換和面向QoS保障的服務替換.在面向功能的服務替換方面，文獻[11]對服務控制流進行建模來描述服務間復雜的異步通信，從服務行為的角度來對服務替換的正確性進行研究，并給出幾種死鎖狀態的處理方法，從而保證服務替換過程中每個參與組合的服務都是正確，解決服務組合中交互的復雜性所帶來服務行為分析難題.服務行為兼容性對服務替換的成功也是非常重要的，Jin等人[12]提出基于服務上下文的行為替換度分析方法，使用Petri網對服務進行建模，通過分析待替換服務的變遷序列來生成局部服務行為限制條件，并選擇符合條件的服務來進行替換.文獻[13]則是通過對服務工作流進行建模，提出一種服務組合上下文信息的采集方法，找出服務組件的K層和K域上下文鄰居，并根據服務接口的依賴關系，基于上下文編輯距離匹配來進行服務替換分析，提高替換服務的召回率和準確率.文獻[14]則是使用Pi演算的方法來對移動云計算系統下的服務進行建模分析，通過分析服務兼容性以及服務行為模擬能力來選擇合適的替換服務，有效避免分析過程空間爆炸的問題.而在面向QoS保障的服務替換上，文獻[15]提出一種基于云模型的服務動態替換方法，通過計算由于動態變化的網絡環境導致服務組合QoS不確定度來定位服務替換位置，重配置服務來保證滿足用戶QoS需求，從而有效保障服務可信性.文獻[16]提出了一個通用服務模型并通過QoS相等度的概念來對服務間的語義相等關系進行描述，在此基礎上提出語義替換機制來實現異構環境下服務替換，有效維持服務穩定運行.Santhanam等人[17]則是通過建立偏好度網絡來描述由非功能的QoS屬性所蘊含的用戶偏好，從而為優質替換服務的識別與選擇來提供指導，維護服務組合的整體功能表現.在此基礎上，文獻[18]通過對服務組件進行迭代替換，實現服務的動態自適應，從而應對在功能性需求不變時，用戶對于安全性、開銷等非功能QoS需求的動態變化.

以上這些服務替換方法提出了一些有效的服務替換策略，一定程度地保障服務運行，但這些方法仍然存在著種種問題，其中最為嚴重的是替換后的服務正確率低.究其原因是現有方法大多關注替代服務的功能是否近似、接口是否兼容等，忽略了動態運行的服務與生俱來的事務屬性，尤其是一致性.在服務發生替換后未及時處理服務一致性缺損問題，內存駐留數據并未被釋放，從而導致服務替換后，服務組合的故障與失效不僅沒有得到抑制，反而出現擴散的趨勢，導致服務的可信性持續下降.由此可見，引入事務機制來分析服務組合中的失效處理和替換機制顯得尤為重要.

隨著虛擬化技術與分布式計算環境的發展與普及，大多數服務通常需要保持長期運行不穩定的分布式虛擬化環境中，是一種典型的長事務(long running transaction)，因此傳統事務機制先提交再執行、“非全則無”的方式存在系統效率低下、恢復困難等問題，勢必導致服務無法持續性的提供服務，反而加劇服務可信性惡化的趨勢，因此需要將傳統非層次的事務模型擴展為層次性的高級事務模型，其中比較有代表性的包括Sagas事務模型[8]、ACTA事務模型[19]等.

而在事務處理協議方面，Web服務協調事務(Web services-coordinationtransaction，WS-CT)和業務事務協議(business transaction protocol，BTP)是現有Web服務事務協議的2個主要協議.WS-CT包含WS-Coordination，WS-Atomic Transac-tion，WS-Business Activity這3個規范協議的規范集，可廣泛用于處理短期存在的原子事務以及長期運行的業務活動；BTP使用2階段提交協議，通過參數化2階段協議，部分參與者可以先提交而其余終止的事務，但是BTP協議并非是針對服務事務協調而專門開發的協議.Yao等人[20]為了使BTP協議能夠支持長事務，對其提出了一些改進并設計實現了一個事務處理系統，通過服務中間商來實現長事務的協調處理.這些對BTP協議中的事務改進并沒有提到補償的概念，WS-CT協議業務事務中定義了相關的補償機制，但其對在分布式環境下的恢復方法卻言之甚少.

此外，還有大量文獻對服務事務性以及補償機制展開研究.Zamani等人[21]針對無狀態的服務與有狀態的事務之間的差異與聯系進行了闡述，通過分析SOA下異構的事務性需求，建立了一個包含事務補償能力的、面向服務的事務處理模型，但是該模型還尚不完整，缺少對復雜業務流程下服務補償機制的設計與實現.印瑩等人[6]充分考慮服務間的多關系與事務特性，提出了一種主動伺機的事務級服務替換方法，但是該算法是由QoS收益模型驅動并分析事務補償代價，后續替換服務僅從QoS保障的角度進行選擇，沒有考慮替換服務的事務屬性對于服務組合系統的影響.

綜合來看，現有研究可以在一定程度上保證服務事務的一致性，在服務在發生故障情況下，能夠以動態演化的方式保障服務可信性，但目前服務事務處理還存在以下問題：

1) 算法擴展性差，目前支持事務級替換方法與補償機制大多是針對具體應用而開發的專用算法與機制，缺少針對算法擴展性與通用性的考慮，一旦脫離針對的環境，這些方法與機制難以適用.

2) 事務粒度設置，在對Web服務進行設計時我們很難確定一個事務被設計成多大是最合適的.小事務可以減輕在補償機制上所付出的代價，提高效率；而大事務在設計上比較簡單，可以減少業務過程開發費用.

3) 替換服務的事務性，大部分服務事務及失效處理的研究集中在服務組合事務粒度與事務范圍識別上，很少有考慮替換服務事務性，缺少從事務性限制的角度出發來選擇替換服務的.一旦選擇了事務性不合適的服務來進行替換，導致服務組合系統的事務粒度被破壞，難以維持后續運行上的一致性，進而導致失效處理后的可信性降低.

本文針對以上不足進行了一定程度的補充，充分考慮了服務的事務屬性，從服務組件間的數據流的角度切入，分析事務粒度與事務范圍.通過選擇具有合適事務屬性的替換服務，提升服務組合的可信性保障能力是本文解決的關鍵問題.

5 結 論

本文針對目前的服務組合替換算法無法很好地應對替換過程中不一致的問題，導致服務替換失敗的情況，提出了一種支持事務級屬性的層次化服務組合模型，使用擴展層次化有色網并結合服務事務屬性來描述服務組合中復雜的數據流關系，通過數據依賴關系來有效識別服務組合事務范圍，進而在服務替換時針對同一事務的服務組件進行補償，并充分考慮候選替換服務選擇的事務屬性限制，維護服務組合的穩定運行.仿真實驗結果驗證了本文方法的正確性和有效性.

在下一步工作中，嘗試將事務級的服務替換與服務補償方法與服務狀態監控結合，建立一套完整的服務運行時動態演化原型系統，同時通過對服務運行狀態和運行歷史模式進行挖掘，從而能夠實現對服務失效的提前預警，進一步提高服務動態自適應以及可信性保障能力.

[1]Wang Huiqiang, Zou Shichen, Lin Junyu, et al. A dependable service path searching method in distributed virtualized environment using adaptive bonus-penalty micro-canonical annealing[C] //Proc of the 2nd IEEE Int Conf on Cyber Security and Cloud Computing (CSCloud). Piscataway, NJ: IEEE, 2015: 530-539

[2]Yu Tao, Lin K. Adaptive algorithms for finding replacement services in autonomic distributed business processes[C] // Proc of IEEE ISADS 2005. Piscataway, NJ: IEEE, 2005: 427-434

[3]Yu Tao, Zhang Yue, Lin K. Efficient algorithms for Web services selection with end-to-end QoS constraints[J]. ACM Trans on the Web, 2007, 1(1): No.6

[4]Du Yuyue, Xue Jie, Li Yancheng. Substitution and analysis of service composition based on service clusters[J]. Acta Electronica Sinica, 2014, 42(11): 2231-2238 (in Chinese)(杜玉越, 薛潔, 李彥成. 基于服務簇的服務組合替換與分析[J]. 電子學報, 2014, 42(11): 2231-2238)

[5]Du Yuyue, Gai Junjing, Zhou Mengchu. A Web service substitution method based on service cluster nets[J/OL]. Enterprise Information Systems. [2016-12-01]. http://dx.doi.org/10.1080/17517575.2016.1172347

[6]Yin Ying, Zhang Bin, Zhang Xizhe. An active and opportunistic service replacement algorithm orienting transactional composite service dynamic adaptation[J]. Chinese Journal of Computers, 2010, 33(11): 2147-2162 (in Chinese)(印瑩, 張斌, 張錫哲. 面向組合服務動態自適應的事務級主動伺機服務替換算法[J]. 計算機學報, 2010, 33(11): 2147-2162)

[7]El Hadad J, Manouvrier M, Rukoz M. TQoS: Transactional and QoS-aware selection algorithm for automatic Web service composition[J]. IEEE Trans on Services Computing, 2010, 3(1): 73-85

[8]Garcia-Molina H, Salem K. Saga[M]. New York: ACM, 1987

[9]Ren Yi, Guan Jianbo, Ao Qi, et al. LHFR: A hierarchical failure recovery algorithm for long running transaction[J]. Journal of Computer Research and Development, 2010, 47(10): 1805-1811 (in Chinese)(任怡, 管劍波, 敖琦, 等. LHFR: 面向長事務的層次式失效恢復算法[J]. 計算機研究與發展, 2010, 47(10): 1805-1811)

[10]Zhou Zhangbing, Sellami M, Gaaloul W, et al. Data providing services clustering and management for facilitating service discovery and replacement[J]. IEEE Trans on Automation Science and Engineering, 2013, 10(4): 1131-1146

[11]Parnjai M C S J. Behavioral service substitution: Analysis and synthesis[D]. Berlin: Humboldt-Universit?t zu Berlin, 2013

[12]Jin Jun, Hu Jingjing, Cao Yuanda, et al. Behavioral compatibility analysis for context-independent service substitution[C] //Proc of the 7th China Grid Annual Conf. Piscataway, NJ: IEEE, 2012: 121-127

[13]Chan N N, Gaaloul W, Tata S. Composition context matching for Web service recommendation[C] //Proc of IEEE Int Conf on Services Computing (SCC). Piscataway, NJ: IEEE, 2011: 624-631

[14]Wang Peng, Yang Ling, Li Guowen, et al. A novel substitution judgment method for mobile cloud computing application system components[C] //Proc of the 6th IEEE Int Conf on Cloud Computing Technology and Science (CloudCom). Piscataway, NJ: IEEE, 2014: 911-916

[15]Gong Yan, Huang Lin, Han Ke. Service dynamic substitution approach based on cloud model[C] // Proc of the 1st Int Conf on Advanced Data and Information Engineering (DaEng-2013). Berlin: Springer, 2014: 563-570

[16]Ibrahim N, Mou?l F L, Frénot S. Semantic service substitution in pervasive environments[J]. International Journal of Services, Economics and Management, 2014, 6(4): 283-309

[17]Santhanam G R, Basu S, Honavar V. Web service substitution based on preferences over non-functional attributes[C] //Proc of IEEE Int Conf on Services Computing (SCC). Piscataway, NJ: IEEE, 2009: 210-217

[18]Santhanam G R, Basu S, Honavar V. Preference based service adaptation using service substitution[C] //Proc of the 2013 IEEE/WIC/ACM Int Joint Conf on Web Intelligence (WI) and Intelligent Agent Technologies (IAT)-Volume 01. Piscataway, NJ: IEEE, 2013: 487-493

[19]Chrysanthis P K, Ramamritham K. Synthesis of extended transaction models using ACTA[J]. ACM Trans on Database Systems, 1994, 19(3): 450-491

[20]Yao Zhilin, Han Lu, Zhang Jinting, et al. Long term Web service oriented transaction handling improvement of BTP protocol[M] //Frontier and Future Development of Information Technology in Medicine and Education. Dordrecht, Netherlands: Springer Netherlands, 2014: 889-898

[21]Zamani A S, Gupta P K. SOA-based distributed system in online transaction processing[J]. Journal of Information Sciences and Computing Technologies, 2015, 4(1): 258-264