支持LRT的失敗恢復(fù)算法及其事務(wù)性質(zhì)分析

梅曉勇，黃昌勤，鄭小林，陳德人，李師賢

（1. 中山大學(xué) 信息科學(xué)與技術(shù)學(xué)院，廣東 廣州 510006；2. 浙江大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，浙江 杭州 310027）

1 引言

組合后長(zhǎng)運(yùn)行事務(wù) LRT(long running transactions)運(yùn)行的長(zhǎng)效性(可能持續(xù)幾小時(shí)、幾個(gè)月甚至更長(zhǎng))，這為 LRT的事務(wù)處理帶來(lái)難度。傳統(tǒng)的ACID(atomicity, consistency, isolation, durability)機(jī)制過(guò)于嚴(yán)格，不再適用于LRT，需要放寬隔離性，松弛資源持有條件，確?？煽縇RT執(zhí)行。因此，在組合事務(wù)環(huán)境下，把 Relaxed-ACID事務(wù)屬性應(yīng)用到LRT是非常有必要的。

文獻(xiàn)[1]和文獻(xiàn)[2]提出了基于容忍嵌套的 LRT失敗執(zhí)行框架，探討自動(dòng)處理容錯(cuò)和失敗處理策略。文獻(xiàn)[3]提出了組合Web事務(wù)的失效恢復(fù)算法。文獻(xiàn)[4]借助自適應(yīng)執(zhí)行上下文，提出一種新的基于語(yǔ)義的動(dòng)態(tài)恢復(fù)機(jī)制。文獻(xiàn)[5]提出了一種基于語(yǔ)義的 Web事務(wù)協(xié)議。文獻(xiàn)[6]提出了一種靈活的確?？煽棵嫦蚍?wù)事務(wù)的方法，確?？刂屏骱褪聞?wù)模式的高內(nèi)聚。文獻(xiàn)[7]提出一種支持業(yè)務(wù)流程的向后恢復(fù)補(bǔ)償方法，其將補(bǔ)償邏輯和失敗依賴(lài)作為協(xié)調(diào)邏輯的一部分。雖然這種方法解決了回滾問(wèn)題，但有2個(gè)主要缺點(diǎn)：第一，多數(shù)情況下只能完成半自適應(yīng)；第二，這些類(lèi)型的工作流需要非常嚴(yán)格的流程定義。

目前支持事務(wù)機(jī)制的組合Web服務(wù)環(huán)境只提供有限的補(bǔ)償能力，引入向后恢復(fù)確保事務(wù)的一致性。文獻(xiàn)[8]通過(guò)擴(kuò)展事務(wù)協(xié)調(diào)架構(gòu)和基礎(chǔ)設(shè)施，提出一種基于向前恢復(fù)策略的高級(jí)補(bǔ)償環(huán)境。文獻(xiàn)[9]提出一種基于規(guī)則的工程補(bǔ)償方法。文獻(xiàn)[10]提出了一種支持用戶(hù)指定失敗處理的Web服務(wù)組合框架。文獻(xiàn)[11]給出了一個(gè)基于Java的事務(wù)性組合服務(wù)JTWS的API框架。為了保證 LRT執(zhí)行語(yǔ)義的準(zhǔn)確性，要么正常結(jié)束, 包括借助替換恢復(fù)或向前恢復(fù)策略使流程繼續(xù)，要么通過(guò)執(zhí)行向后恢復(fù)策略撤銷(xiāo)已經(jīng)提交的執(zhí)行結(jié)果。面臨如下兩方面問(wèn)題：① LRT執(zhí)行時(shí)可能消耗大量資源，不一定對(duì)所有已提交任務(wù)逆向補(bǔ)償，并最終回滾到到初始狀態(tài)；② 中止整個(gè) LRT需要很大代價(jià)，一種折中的恢復(fù)機(jī)制是先向后退到一個(gè)點(diǎn)，然后用替代任務(wù)或修復(fù)失敗繼續(xù)正向執(zhí)行。引入靈活的 LRT的恢復(fù)策略，有如下優(yōu)勢(shì)：① 重試失敗任務(wù)或選擇等價(jià)替代任務(wù)有助于LRT重新獲得成功；② 比嘗試“修補(bǔ)”失敗任務(wù)更有效；③ 有利于預(yù)測(cè)長(zhǎng)事務(wù)執(zhí)行狀態(tài)，而不會(huì)導(dǎo)致長(zhǎng)時(shí)間占用資源。綜上所述，有必要進(jìn)一步研究基于 LRT靈活的事務(wù)恢復(fù)策略。

2 基于Petri網(wǎng)的任務(wù)形式化

首先給出了基于Petri的原子任務(wù)形式化定義。

定義1 原子任務(wù)I的三元組表示為(P,T,F)。

1)P=Ps∪Pio∪Pqos∪Pc，其中，Ps指I的狀態(tài)庫(kù)所{Ready,Activated,Failed,Running,Aborted,Cancelled,Committed,Compensated,Half_Compensated} ;Pio指I的I/O庫(kù)所集，通常描述Web服務(wù)的功能參數(shù)；Pqos指描述I的非功能參數(shù)；Pc描述I的信號(hào)庫(kù)所。對(duì)于I，分別用I.ps,I.pio,I.pc和I.pqos來(lái)描述I的狀態(tài)、功能、信號(hào)和非功能參數(shù)。

2)T=Tn∪Tb∪τ，其中，Tn指I正向事件集{Activate( ),Run( ),Fail( ) ,Abort(),Cancel(),Commit( ) }；Tb指I反向事件集{Compensate( ),Hcompensate(),Retry()}；τ∈T為空操作。為簡(jiǎn)化描述，正向事件Activate(),Run(),Fail(),Abort(),Commit(),Cancel()分別簡(jiǎn)記為tact,trun,tfal,tabt,tcmt,tcnl；反向事件Retry( )和Compensate( )分別簡(jiǎn)記為trty和tcmp。對(duì)于任務(wù)I，用I.t獲取I的執(zhí)行事件。

3)F= (P×T) ∪ (T×P)分別描述P到T或T到P控制流和數(shù)據(jù)流的有向弧集合。事件/狀態(tài)對(duì) (t1,p1)和 (t2,p2)間有如下約束：① 偏序關(guān)系 (t1,p1)? (t2,p2)；② 排斥關(guān)系 (t1,p1) ? ? (t2,p2)；③ (t1,p1)≈ (t2,p2)描述動(dòng)作t1和t2同時(shí)發(fā)生或都不發(fā)生。

每個(gè)原子服務(wù)都有獨(dú)特的事務(wù)行為，依據(jù)功能語(yǔ)義將分為 4類(lèi)：樞軸(pivot)服務(wù)(記為WSp)、可補(bǔ)償(Compensable)服務(wù)(記為WSc)、可重試(R etriable )服務(wù)(記為WSr)和關(guān)鍵(Vital)服務(wù)(記為WSv)。對(duì)于任務(wù)I，其事務(wù)類(lèi)型記為I.TBP，其中，I.TBP∈{Pivot,Vital,Retriable,Compensable}。

WSp指Ip既不可重試，也不可補(bǔ)償，如圖1(a)所示。WSc是當(dāng)Ic成功提交后，通過(guò)執(zhí)行其補(bǔ)償任務(wù)來(lái)消除產(chǎn)生的影響，如圖1(b)所示。WSr指Ir執(zhí)行失敗，有限次重試后，確保Ir成功提交，如圖1(c)所示。WSv指Iv具備重試和補(bǔ)償?shù)哪芰?，如圖1(d)所示。表1給出了任務(wù)執(zhí)行狀態(tài)和變遷含義，運(yùn)行時(shí)任務(wù)可能轉(zhuǎn)移到就緒(p0)、運(yùn)行(p1)、提交(p2)、中止(p4)、取消(p6)、失敗(p7)和補(bǔ)償(p9)狀態(tài)之一，觸發(fā)Activate()、Run()、Fail()、Abort()、Cancel()或Commit()等內(nèi)部或外部動(dòng)作。

圖1 原子任務(wù)形式化

表1 事務(wù)屬性的變遷和庫(kù)所

3 恢復(fù)范圍及恢復(fù)契約

LRT流程的可靠性和一致性問(wèn)題變得尤為突出，有必要提出一種可靠的失敗恢復(fù)算法。目前，現(xiàn)有規(guī)范大多涉及補(bǔ)償算法，且補(bǔ)償算法定義在范圍(BPEL4WS)或上下文(WSCI)或編排(WS-CDL)中。本文擴(kuò)展BPEL4WS范圍，擴(kuò)展后范圍由靜態(tài)指定改為動(dòng)態(tài)計(jì)算，恢復(fù)范圍相對(duì)固定，缺乏靈活性。

3.1 恢復(fù)范圍

考慮不同恢復(fù)需求，為不同恢復(fù)策略靈活地定義恢復(fù)范圍Ξ。況且流程設(shè)計(jì)師為失敗類(lèi)型的失敗恢復(fù)確定Ξ，也是一件非常困難的事情。本文給出的解決方法是依據(jù)恢復(fù)規(guī)格說(shuō)明動(dòng)態(tài)計(jì)算Ξ。

對(duì)于給定 LRT，執(zhí)行跡σ，如果?σ?Ii,Ij∈σ∧Ii.TBP,Ij.TBP{Co∈mpensable,Vital}，Ii和Ij之間存在依賴(lài)之一，且Ii和Ij均是可補(bǔ)償?shù)模瑒tσ是可補(bǔ)償?shù)?，記為?Compensated。若LRT中每個(gè)任務(wù)都是可補(bǔ)償?shù)?，且與失敗任務(wù)存在依賴(lài)的任務(wù)都能確保成功補(bǔ)償，則該LRT是可補(bǔ)償?shù)摹?/p>

LRT執(zhí)行失敗，確定終止依賴(lài)點(diǎn)(TDP, terminate dependency point)非常關(guān)鍵，恢復(fù)處理器(RH, recovery handler)啟動(dòng)恢復(fù)策略(RHS, recovery handling strategy)，對(duì)Ξ中所有任務(wù)執(zhí)行恢復(fù)，直到TDP。對(duì)于給定σ，如果?σ?Ii，Ij∈σ∧Ii.TBP,Ij.TBP∈ {Vital,Compensable}，Ii和Ij之間存在數(shù)據(jù)流依賴(lài)或稱(chēng)Ii是Ij的 TDP，如圖 2所示。若Ij失敗，從依賴(lài)點(diǎn)Ii開(kāi)始對(duì)σm(σm∈σ)執(zhí)行恢復(fù)，稱(chēng)σm為Ij的依賴(lài)路徑。

對(duì)于給定 LRT，Ij(Ij∈σ)失敗，計(jì)算Ij的依賴(lài)路徑集{σm1,σm2,…,σmk}，回滾到Ii并注入修正參數(shù)，正向執(zhí)行σm直到LRT成功執(zhí)行。考慮恢復(fù)代價(jià)，對(duì){σm1,σm2,…,σmk}的恢復(fù)范圍集{Ξ1,Ξ2,…,Ξk}，優(yōu)先選取恢復(fù)范圍小的Ξ執(zhí)行恢復(fù)。

圖2 確定失敗任務(wù)的恢復(fù)范圍

范圍嵌套類(lèi)似于聚合模式嵌套，如圖3所示，Ξ[1] ╞Ξ[1][2]指Ξ[1][2]是Ξ[1]的子范圍，括號(hào)中數(shù)字表明嵌套層次。Ξ[1]╞ …╞Ξ[1]…[i]…[m]表示Ξ包含m個(gè)嵌套層，其中，每個(gè)嵌套子范圍可能包含零個(gè)或多個(gè)任務(wù)。RH啟動(dòng)Ξ中預(yù)定義的 RHS，用二元組(Failtype,Action)i描述Ξ中失敗任務(wù)I啟動(dòng)第i個(gè)事務(wù)失敗處理策略rhsi，其中，F(xiàn)ailtype為不同失敗觸發(fā)類(lèi)型，Action為失敗處理事件。Failtype又可分為簡(jiǎn)單失敗(記為Fail(Sname))和組合失敗(記為Fail(Sname1)∧Fail(Sname2)∧…∧Fail(Snamen))。Action描述觸發(fā)事件定義的失敗處理操作，其又可分為原子操作和組合操作，前者指單一替代或補(bǔ)償操作，后者指聚合算子連接的多個(gè)原子行為。

通常，Ξ與RHS集(rhs1,rhs2,…,rhsn)(rhsi≠rhsj,i≠j)相關(guān)聯(lián)。例如，TRP中Ξ有2個(gè)恢復(fù)策略rhs1=(Fail(ReserveAirline_Tickets),Compensate(UndoAirline Tickets))和rhs2=(Fail(CarRenting),Alter(BusRenting))，其中，當(dāng)ReserveAirline Tickets失敗，執(zhí)行補(bǔ)償，撤銷(xiāo)預(yù)訂機(jī)票；而CarRenting失敗，調(diào)用替代恢復(fù)BusRenting執(zhí)行巴士租賃服務(wù)。

3.2 恢復(fù)契約

局部依賴(lài)伴隨于任務(wù)間交互，全局依賴(lài)往往存在時(shí)序和條件約束。LRT中任務(wù)間前后執(zhí)行時(shí)序采用事件約束描述：σ1?e?σ2,σ1?e和e?σ2，其中，事件e{∈Activate(),Run(),Fail(),Abort(),Cancel(),Retry(),Compensate,Hcompensate(),Commit()}，σ1?e?σ2使得e一定發(fā)生，記為?e；而σ1?﹁e?σ2則禁止e發(fā)生，記為﹁?e。擴(kuò)展后的串行約束σ1?(e1,…,en)?σ2記為?(e1,…,en)，等價(jià)于?e1⊕ …⊕ ?en，表明事件e1,…,en均發(fā)生。

為了更好地采用Petri網(wǎng)描述恢復(fù)契約，引入擴(kuò)展謂詞邏輯CTR，除了,,∨∧﹁,?和?等算子外，還包括連接算子(⊕和|)和模態(tài)算子⊙。?e1⊕?e2指先后執(zhí)行e1和e2；?e1||?e2指e1和e2以交織方式并發(fā)執(zhí)行；?e1∧?e2指e1和e2同時(shí)執(zhí)行；?e1∨ ?e2僅e1或e2執(zhí)行。⊕,||,∧和∨分別用于sequence,And-split,Or-split控制流交互，并伴有數(shù)據(jù)流。此外，還存在如下復(fù)雜約束：① ?IiRun()∧ ?IiCommit()指Ii執(zhí)行了Run()和Commit()；② ﹁?IiFail()∧﹁?IiCommit()指Ii不可能執(zhí)行了Fail()和Commit()；③?IiCompensate()→?IiCommit()指Commit()需要在Compensate()之前執(zhí)行；④?IiRetry()→ (?IiFail().⊕ ?IiRetry())指Retry()需要在Fail()之后執(zhí)行；⑤?IiCommit()∧ ?IiCompensate()→(?IiCommit()⊕ ?IiCompensate())指Commit()和Compensate()都發(fā)生，且Commit()在Compensate()之前執(zhí)行。

任何復(fù)雜約束都可以轉(zhuǎn)換為∨i(∧jConstri,j)，其中，Constri,j為約束表達(dá)式。同樣可以討論Ii和Ij之間的復(fù)雜約束，例如?IiActivate()→?IjCommit()是指如果Ii執(zhí)行Activate()，則Ij必須在其之前執(zhí)行Commit()；?IiFail()→?IiCompensate()是指Ii執(zhí)行失敗將導(dǎo)致Ij補(bǔ)償。

LRT執(zhí)行過(guò)程中，可能出現(xiàn)3種類(lèi)型失?。孩僬{(diào)用Web服務(wù)執(zhí)行失敗，失敗信息在調(diào)用服務(wù)描述文檔中給出；② 調(diào)用或執(zhí)行服務(wù)超時(shí)；③ 執(zhí)行引擎失敗。本文討論的失敗恢復(fù)主要針對(duì)前2種情形，因此在發(fā)布服務(wù)時(shí)，需要給出服務(wù)契約，任務(wù)執(zhí)行時(shí)，給出調(diào)用契約：① 若Ii和Ij存在滿(mǎn)足契約CnlCon tract(Ij)，當(dāng)且僅當(dāng)Ii失敗且Ii.Failed∈CnlContract(Ij)，則觸發(fā)依賴(lài)② 若Ij滿(mǎn)足中止契約Abt Contract(Ij)，Ii.failed∈AbtContract(Ij)∨Ii.Aborted∈AbtContract(Ij) ∨Ii.Cancelled∈AbtCon-tract(Ij)，中止Ii則觸發(fā)中止依賴(lài)③ 若Ii和Ij滿(mǎn)足補(bǔ)償契約CptContract(Ij)，Ii.failed∈CptContract(Ij)∨Ii.Compen sated∈CptContract(Ij)，Ii失敗則觸發(fā)依賴(lài)為了更準(zhǔn)確地選擇RHS提供失敗恢復(fù)，RH用恢復(fù)契約來(lái)配置RHS，優(yōu)點(diǎn)是隨時(shí)增加或減少契約條目。

圖3 嵌套范圍

4 失敗恢復(fù)模型及算法

目前業(yè)界所提供的失敗處理規(guī)范主要是向后恢復(fù)，恢復(fù)代價(jià)較高開(kāi)銷(xiāo)大，其沒(méi)有考慮失敗修復(fù)后LRT繼續(xù)執(zhí)行。基于此，本文提出一種支持組合事務(wù)的綜合恢復(fù)策略，除了保留向后恢復(fù)，還擴(kuò)展了向前和替代恢復(fù)。

4.1 向后恢復(fù)模型及算法

LRT執(zhí)行失敗，Ij激活fail()，中止正向流，觸發(fā)RH，RH捕獲Ij事件fail()，計(jì)算Ξ，抽取執(zhí)行日志，計(jì)算恢復(fù)輸入Ii′.in (從Ii.In和Ii.Out獲取)和Ii′.Cp(由Ii.TBP和Ii.State產(chǎn)生)，啟動(dòng)向后恢復(fù)策略。為便于問(wèn)題描述，將逆向恢復(fù)流從正向事務(wù)流中分離出來(lái)，Ξ中的任務(wù)滿(mǎn)足Ii.TBP{∈Compensable,Vital}，RH 激活I(lǐng)i′，Ii逐個(gè)映射Ii′。下面給出向后恢復(fù)配對(duì)策略BRPS的形式化定義。

假定I=(P,T,F)和I'=(P',T',F')分別表示LRT的正向和逆向流，?Ξ?I∈Ξ|I÷I'∈T÷T'，tic映射Ii到Ii+1的補(bǔ)償，tif映射Ii到Ii′的失敗轉(zhuǎn)移，ti'c描述Ii'到Ii+1'的逆向轉(zhuǎn)移。BRPS的三元組表示為其中下面給出BRPS的逆向構(gòu)建算法。

算法1 構(gòu)造恢復(fù)流算法

輸入：LRT中任務(wù)I的集合, 失敗任務(wù)I?和補(bǔ)償依賴(lài)集CP

輸出: 恢復(fù)流Rflow

該算法的時(shí)間復(fù)雜度與 LRT中任務(wù)數(shù)目及Ξ中補(bǔ)償任務(wù)數(shù)有關(guān)，若max(|LRT|,|Ξ|)=n，則該算法的時(shí)間復(fù)雜度為O(mn)。下面給出向后恢復(fù)算法。

算法2 RH恢復(fù)執(zhí)行算法

輸入: LRT中任務(wù)I的集合, 恢復(fù)流Rflow

輸出: 補(bǔ)償服務(wù)執(zhí)行信息

若|Rfolw|=n和Edge(I?)=m分別為Rfolw中任務(wù)數(shù)和邊數(shù)，該算法的時(shí)間復(fù)雜度為O(mn)。

4.2 向前恢復(fù)模型及算法

與BRPS模型構(gòu)造類(lèi)似，不同的是向前恢復(fù)模型回滾到TDP后，RH注入正確輸入，重啟正向流執(zhí)行。假定I=(P,T,F)是LRT正向流，若Ij執(zhí)行失敗，計(jì)算其Ii.TDP和Ξ，向前恢復(fù)策略FRPS的三元組表示為，其中：下面給出FRPS恢復(fù)算法。

算法3 向前恢復(fù)FRPS算法

輸入：失敗任務(wù)I?，執(zhí)行日志Log，業(yè)務(wù)流程LRT

輸出：恢復(fù)成功或失敗信息

逆向執(zhí)行恢復(fù)流的時(shí)間復(fù)雜度為O(n)，而從TDP重新執(zhí)行LRT的時(shí)間復(fù)雜度為O(n)，因此，F(xiàn)RPS算法的時(shí)間復(fù)雜度為O(n)。

4.3 替代恢復(fù)模型

LRT失敗，失敗任務(wù)Ii.TDP={Ij}且Ii.Ξ=Ii，若{Ii}={Ij}，則Ii的失敗發(fā)生不依賴(lài)其他任務(wù)，選擇FRPS或BRPS恢復(fù)代價(jià)都過(guò)高，僅需要選擇Ii的替代服務(wù)，替代恢復(fù)ARS的形式化描述如下。

假定Ii=(Pi,Ti,Fi)是LRT正向流，Ij執(zhí)行失敗，計(jì)算Ii.TDP和Ii.Ξ，若?Ξ?Ij∈Ξ|Ii=Ij，引入替代流Ii″=(Pi″,Ti″,Fi″)，ARS 三元組表示為，其中：LRT執(zhí)行失敗，依據(jù)iI失敗類(lèi)型選取 RHS，BRPS恢復(fù)代價(jià)最高，ARS最低，F(xiàn)RPS介于兩者之間。

5 LRT的事務(wù)性質(zhì)擴(kuò)展

LRT往往涉及復(fù)雜恢復(fù)行為，并以不同聚合模式構(gòu)造。LRT的事務(wù)性質(zhì)需借助基本聚合模式的事務(wù)性質(zhì)，并擴(kuò)展LRT的事務(wù)性質(zhì)。假定有3個(gè)聚合服務(wù)cs1、cs2和cs3對(duì)應(yīng)的聚合片段分別為Ii⊙…⊙Ij、Im⊙…⊙In和Ip⊙…⊙Iq，其中，{⊙∈⊕,||,? ,Θ}，借助形成一組新的聚合服務(wù)集合和

1) 對(duì)于順序聚合cs1⊕cs2，cs1.TBP?cs2.TBP的聚合事務(wù)性質(zhì)需檢查cs1中Ii⊙…⊙Ij的Ij.TBP，cs2中Im⊙…⊙In的Im.TBP，檢查連接點(diǎn)Ij.TBP⊕Im.TBP的事務(wù)性質(zhì)，特別地，Ij.Retriable⊕Im.Compensable不能保證LRT的原子性。

2) 并行組合cs1⊕(cs2||cs3)需要檢查連接點(diǎn)Ij.TBP⊕Im.TBP和Ij.TBP⊕Ip.TBP的事務(wù)性質(zhì)；而(cs1||cs2)⊕cs3則需要檢查連接點(diǎn)Ij.TBP⊕Ip.TBP和In.TBP⊕Ip.TBP的事務(wù)性質(zhì)。

3) 選擇聚合cs1⊕(cs2?cs3)和鑒別器cs1⊕(cs2Θcs3)類(lèi)似于cs1⊕ (cs2?cs3)連接點(diǎn)分析，檢查Ij.TBP⊕Im.TBP和Ij.TBP⊕Ip.TBP的事務(wù)性質(zhì)；分析(cs1?cs2)⊕cs3和(cs1Θcs2)⊕cs3類(lèi)似于(cs1||cs2)⊕cs3。

6 失敗恢復(fù)網(wǎng)的性質(zhì)分析

依據(jù) RHS定義，僅有一個(gè)初始托肯處于源庫(kù)所，如果執(zhí)行LRT沒(méi)有點(diǎn)火任何失敗變遷，托肯將隨正向傳遞，直到成功到達(dá)槽庫(kù)所。但是，LRT的執(zhí)行可能導(dǎo)致失敗發(fā)生，設(shè)失敗恢復(fù)網(wǎng)系統(tǒng)依據(jù)失敗恢復(fù)類(lèi)型不同，選取那么按流方向Σ

被劃分為正向網(wǎng)系統(tǒng)∑e=(Ne,Me)和恢復(fù)網(wǎng)系統(tǒng)若?σ∈T*∧?tf∈σ∧tf∈Tf，滿(mǎn)足：存在恢復(fù)路徑σ=σ1， 使 得即 細(xì) 化，使得點(diǎn)火Σr中恢復(fù)步序列σ2∈使得，稱(chēng)σ2是σ1的恢復(fù)路徑。分別為Ie及其恢復(fù)任務(wù)Ir在σ1和σ2上的投影序列，若則有恢復(fù)映射f:σ1→σ2；③σ2是σ1的恢復(fù)路徑且存在映射f:σ1→σ2，若||σ1||≠0，則||σ2||≠0，稱(chēng)Σ是可正確恢復(fù)的。

定理 1 設(shè)失敗恢復(fù)網(wǎng)系統(tǒng)Σ=(FRS,M0)，其正向網(wǎng)和恢復(fù)網(wǎng)系統(tǒng)分別為Σe=(Ne,Me)和Σr=(Nr-1,Mr)，若Σe執(zhí)行失敗，則Σ是恢復(fù)可達(dá)的。

證明Σe和Σr中正向流和恢復(fù)流分別為(P×T)∪ (T×P)和(P′×T′)∪(T′×P′)，由Σe執(zhí)行失敗，依據(jù)恢復(fù)策略定義，構(gòu)造(P×Tf)∪(Tf×P′)∪(T×Pf)∪(Pf×T′)失敗轉(zhuǎn)移，從而轉(zhuǎn)向恢復(fù)流σ(σ∈TPfT′或σ∈(TP)*Tf(P′T′)*)，Pf或Tf使得Σ恢復(fù)可達(dá)。設(shè)M1,M2∈M0[＞∧M1∈RS(Σe)，存在恢復(fù)步序列σ，使得M1[σ＞M2∧M2?RS(Σe)，若失敗發(fā)生使得即tf點(diǎn)火Σ中的步序列σ2，使得從而Σ恢復(fù)可達(dá)。

定理2 設(shè)失敗恢復(fù)網(wǎng)系統(tǒng)∑=(FRS,M0)，其中RHS可以是(保證正確恢復(fù)。

證明 設(shè)Σ的正向網(wǎng)系統(tǒng)和恢復(fù)網(wǎng)系統(tǒng)分別是是Σ的失敗發(fā)生，那么中任意包含tf的執(zhí)行路徑若[Me,Mr1]RS(∈Σ,M0)∧Me1∈RS(eΣ,Me0)∧Mr1RS(∈rΣ,Mr0)，存在正向執(zhí)行路徑σ1，使得M0[σ1＞Me1[tf＞Mr1，依據(jù)tf失敗類(lèi)型，F(xiàn)RS觸發(fā)失敗恢復(fù)策略則tf點(diǎn)火Σr恢復(fù)步σ2 f，并執(zhí)行σ2 f，使得Mr1[(σ2 f)＞，滿(mǎn)足f:σ1→σ2，Σ是可正確恢復(fù)的。

對(duì)于(FRS,M0)中的σ，若步序列，由 BRPS 有且f:I→I′(其中，I∑∈e，I′∈rΣ)，即tf點(diǎn)火rΣ，I′消除I的影響；若M0)，其中，使得點(diǎn)火rΣ恢復(fù)步σ2 f并執(zhí)行，使得恢復(fù)后執(zhí)行繼續(xù)，稱(chēng)Σ是可恢復(fù)的。

定理 3 設(shè)失敗恢復(fù)網(wǎng)系統(tǒng)Σ=(FRS,M0)，RHS是分別是Σ的正向網(wǎng)和恢復(fù)網(wǎng)系統(tǒng)，Σ失敗恢復(fù)是安全的。

證明 ?Mrf1∈(Σ,M0)?tr∈T*，依據(jù)tf失敗類(lèi)型，觸發(fā)分3種情形證明Σ的安全性：① 若tr∈，由于Σe=(Ne,Me)是安全的，存在執(zhí)行路徑，使得僅影響Σe中Me1，而Σr中標(biāo)識(shí)不變，依據(jù)Σr定義，存在標(biāo)識(shí)轉(zhuǎn)移Me1[tr＞Mr1[σ1＞(其中，確保Σ安全恢復(fù)。

7 基于組合事務(wù)恢復(fù)的應(yīng)用

組合事務(wù)應(yīng)用實(shí)例用經(jīng)典的旅行預(yù)訂流程TRP，如圖4所示，旅行者TE向旅行社TA提交旅行需求說(shuō)明CRS；由CRS分別預(yù)訂機(jī)票FB(或火車(chē)票 TR)和賓館 HB，租賃小車(chē) CR(或大巴 BR)，TE確認(rèn)預(yù)訂并在線(xiàn)支付OP，快遞 EMS(或 UPS)投遞給 TE，TE簽收確認(rèn) TC。聚合嵌套后的事務(wù)流程為CRS⊕((FB?TR)||HB||(CR||BR))⊕OP⊕(EMS?UPS)⊕TC。實(shí)例中旅行社在廣州，而航空公司、酒店和汽車(chē)租賃公司分布于全國(guó) 20多個(gè)景點(diǎn)，表 2給出了 TRP中可能組合的服務(wù)及其事務(wù)性質(zhì)。若TRP聚合了WSp，其既不可補(bǔ)償也不可重試。要獲得LRT事務(wù)原子語(yǔ)義，WSp必須保證在執(zhí)行向后恢復(fù)之前提交或確保不發(fā)生失敗。

圖4 旅行預(yù)訂流程

試驗(yàn)環(huán)境配置：執(zhí)行引擎選用ActiveBPEL，2臺(tái)服務(wù)器IBM x3650 (4核Intel 2930MHz CPU、1GB RAM和SuSE 10.2 Linux OS)和12臺(tái)網(wǎng)絡(luò)工作站(Intel E5200 2.5 GHz CPU, 2GB RAM和Windows XP SP2)。TE自主選擇旅行路線(xiàn)并提交給TA，TA生成路線(xiàn)圖(協(xié)商最短路線(xiàn))，TE確認(rèn)路線(xiàn)，旅行社預(yù)訂機(jī)票、火車(chē)票、酒店以及出行交通工具，向TE提交預(yù)算，一旦預(yù)訂失敗，協(xié)商預(yù)訂子流程：① 變更無(wú)法預(yù)訂的服務(wù)，如將交通工具從火車(chē)改飛機(jī)、將酒店單人間改雙人間。② 變更不能成功預(yù)訂的景點(diǎn)，系統(tǒng)推薦景點(diǎn)。模擬事務(wù)回滾機(jī)制，自動(dòng)退訂已預(yù)訂的機(jī)票和酒店等。③ 刪除不能預(yù)訂的景點(diǎn)。預(yù)訂成功，將預(yù)訂信息返回給 TE。組合事務(wù)的執(zhí)行語(yǔ)義保證組合事務(wù)正確執(zhí)行，其不僅可以檢測(cè)TRP執(zhí)行的邏輯錯(cuò)誤，還能檢測(cè)執(zhí)行失敗恢復(fù)的正確性（如圖5所示）。如圖6所示，若預(yù)訂type為hotel，進(jìn)入酒店預(yù)訂子流程，當(dāng)star為三星級(jí)進(jìn)入 orderwanjia，Towanjia預(yù)訂萬(wàn)家酒店，Invokewanjia調(diào)用 WanJia HotelServcie。退訂 type為 hotel時(shí)，進(jìn)入退訂酒店子流程，當(dāng)退訂酒店為huatian，將 HuaTianReturnReq傳遞到 tohuatian退訂酒店，invokehuatian調(diào)用HuaTian HotelService，完成相應(yīng)的恢復(fù)。

表2 可用服務(wù)及其事務(wù)性質(zhì)

圖5 TRP組合業(yè)務(wù)流及其恢復(fù)流

圖6 TRP執(zhí)行預(yù)訂及其變更

TRP預(yù)訂流程中，旅行社負(fù)責(zé)預(yù)訂航班、酒店和租賃汽車(chē)。如果預(yù)訂機(jī)票失敗，需要取消酒店預(yù)訂和汽車(chē)租賃，最后與旅行者協(xié)商改火車(chē)出行，一旦成功預(yù)訂火車(chē)票將不能再次變更。表3描述TRP中多伙伴協(xié)作操作對(duì)，失敗恢復(fù)時(shí)，首先檢查發(fā)生失敗任務(wù)是否存在恢復(fù)任務(wù)，如果存在，執(zhí)行恢復(fù)；否則，執(zhí)行空操作。恢復(fù)對(duì)用I.action÷I'.action表示，其中，I.action表示I正向執(zhí)行操作，I'.action表示I'所執(zhí)行恢復(fù)，特別地，?是空操作。

表3 TRP中恢復(fù)對(duì)描述

圖7 失敗聚合性能比較

圖8 失敗恢復(fù)后性能比較

本文將TRP組合服務(wù)分為4組，前3組分別在不同執(zhí)行任務(wù)點(diǎn)失敗，第4組則執(zhí)行成功，比較4組恢復(fù)策略下的失敗率比較。圖7給出了TRP執(zhí)行失敗的聚合性能曲線(xiàn)，這里的聚合曲線(xiàn)是累計(jì)聚合值。應(yīng)用第4節(jié)給出的組合事務(wù)恢復(fù)算法討論TRP失敗恢復(fù)，更好地指導(dǎo)事務(wù)恢復(fù)。分5組聚合服務(wù)來(lái)執(zhí)行TRP流程，結(jié)果顯示，僅QoS0曲線(xiàn)成功執(zhí)行，其他4條曲線(xiàn)QoSC1、QoSC2、QoSC3和QoSC4分別執(zhí)行到第3、4、7和8個(gè)服務(wù)時(shí)失敗，從圖7可以看出，失敗率與選取不同性質(zhì)的原子服務(wù)有關(guān)，失敗率與服務(wù)信譽(yù)度基本一致，與響應(yīng)時(shí)間相比僅在第7和第8個(gè)失敗處顯著增加，與可靠性相比僅在第3、4和8個(gè)失敗處一致，與可用性相比僅在第7個(gè)失敗處一致，但執(zhí)行代價(jià)和執(zhí)行時(shí)間在執(zhí)行恢復(fù)策略前后幾乎無(wú)變化。

圖7中曲線(xiàn)分別對(duì)應(yīng)圖8中QoS0、QoSC1、QoSC2、QoSC3和QoSC4恢復(fù)曲線(xiàn)，在第3、4、7和8個(gè)失敗處啟動(dòng)恢復(fù)策略，恢復(fù)執(zhí)行后，對(duì)響應(yīng)時(shí)間產(chǎn)生了影響，但執(zhí)行時(shí)間和代價(jià)變化不大。綜上分析，可以得出以下結(jié)論：① 采用合適的恢復(fù)策略，可有效減少失敗恢復(fù)代價(jià)；② 盡管失敗不可避免，但最終可篩選出失敗率較低的LRT；③ 受失敗率影響，聚合曲線(xiàn)可協(xié)調(diào)LRT中參與組合的服務(wù)，消除不利因素影響。

8 結(jié)束語(yǔ)

鑒于LRT事務(wù)的復(fù)雜性，LRT中被組合任務(wù)可能具有不同的事務(wù)性質(zhì)，確保其在SOC環(huán)境中可靠執(zhí)行，需要構(gòu)建有效的失敗恢復(fù)策略。為此，本文提出一種支持組合事務(wù)的失敗恢復(fù)算法，為不同的失敗發(fā)生選取合適的恢復(fù)策略。旅行預(yù)訂實(shí)例分析表明該算法可確保LRT可靠執(zhí)行，最后通過(guò)對(duì)TRP失敗恢復(fù)分析，表明選擇合適的恢復(fù)算法對(duì)減少事務(wù)失敗率和消除不利因素影響是有利的。

未來(lái)的工作主要包括如下 4個(gè)方面：① 引入事務(wù)流日志挖掘算法；② 建立組合事務(wù)恢復(fù)的依賴(lài)規(guī)則；③ 深入研究事務(wù)恢復(fù)的局部和全局約束；④ 違反組合事務(wù)性質(zhì)的檢測(cè)技術(shù)。

[1] LAKHAL N B, KOBAYASHI T, YOKOTA H. FENECIA: failure endurable nested-transaction based execution of composite Web services with incorporated state analysis[J]. The International Journal on Very Large Data Bases, 2009, 18(1):1-56.

[2] LIU A, LI Q, HUANG L S,et al. FACTS: a framework for fault-tolerant composition of transactional Web services[J]. IEEE Transactions on Services Computing, 2010, 3(1):46-59.

[3] HEWETT R, KIJSANAYOTHIN P. Privacy and recovery in composite Web service transactions[J]. International Journal for Infonomics, 2010, 3(2): 240-248.

[4] KOLLINGBAUM M, SYCARA K, VACULIN R,et al. Recovery mechanisms for semantic Web services[J]. Distributed Applications and Interoperable Systems, 2008, 17(3): 100-105.

[5] MINH T, LE N, CAO J L. Flexible and semantics-based support for Web services transaction protocols[A]. Grid and Pervasive Computing[C]. 2008. 492-503.

[6] BHIRI S, GAALOUL W, GODART C,et al. Ensuring customised transactional reliability of composite services[J]. Journal of Database Management, 2011, 22(2): 64-92.

[7] YANG Z H, LIU C F. Implementing a flexible compensation mechanism for business processes in Web service environment[A].International Conference on Web Services[C]. Salt Lake City, USA,2006.753-760.

[8] SCHAFER M, DOLOG P, NEJDL W. An environment for flexible advanced compensations of Web service transactions[J]. ACM Transactions on the Web, 2008, 2(2):1-36.

[9] SCHAFER M, DOLOG P, NEJDL W. Engineering compensations in Web service environment[A]. International Conference on Web Engineering[C]. Como, Italy, 2007. 32-46.

[10] KIM Y, KIM J. Allowing user-specified failure handling in Web services composition[A]. Proceedings of the 2nd International Conference on Ubiquitous Information Management and Communication[C]. Kuala Lumpur, Malaysia, 2008. 452-458.

[11] BRUNI R, FERRARI G, MELGRATTI H,et al. From theory to practice in transactional composition of Web services[A]. International Workshop on Web Services and Formal Methods[C]. Versailles,France, 2005. 272-286.