支持LRT的失敗恢復算法及其事務性質分析

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

（1. 中山大學 信息科學與技術學院，廣東 廣州 510006；2. 浙江大學 計算機科學與技術學院，浙江 杭州 310027）

1 引言

組合后長運行事務 LRT(long running transactions)運行的長效性(可能持續幾小時、幾個月甚至更長)，這為 LRT的事務處理帶來難度。傳統的ACID(atomicity, consistency, isolation, durability)機制過于嚴格，不再適用于LRT，需要放寬隔離性，松弛資源持有條件，確保可靠LRT執行。因此，在組合事務環境下，把 Relaxed-ACID事務屬性應用到LRT是非常有必要的。

文獻[1]和文獻[2]提出了基于容忍嵌套的 LRT失敗執行框架，探討自動處理容錯和失敗處理策略。文獻[3]提出了組合Web事務的失效恢復算法。文獻[4]借助自適應執行上下文，提出一種新的基于語義的動態恢復機制。文獻[5]提出了一種基于語義的 Web事務協議。文獻[6]提出了一種靈活的確保可靠面向服務事務的方法，確保控制流和事務模式的高內聚。文獻[7]提出一種支持業務流程的向后恢復補償方法，其將補償邏輯和失敗依賴作為協調邏輯的一部分。雖然這種方法解決了回滾問題，但有2個主要缺點：第一，多數情況下只能完成半自適應；第二，這些類型的工作流需要非常嚴格的流程定義。

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

2 基于Petri網的任務形式化

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

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

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

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

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

每個原子服務都有獨特的事務行為，依據功能語義將分為 4類：樞軸(pivot)服務(記為WSp)、可補償(Compensable)服務(記為WSc)、可重試(R etriable )服務(記為WSr)和關鍵(Vital)服務(記為WSv)。對于任務I，其事務類型記為I.TBP，其中，I.TBP∈{Pivot,Vital,Retriable,Compensable}。

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

圖1 原子任務形式化

表1 事務屬性的變遷和庫所

3 恢復范圍及恢復契約

LRT流程的可靠性和一致性問題變得尤為突出，有必要提出一種可靠的失敗恢復算法。目前，現有規范大多涉及補償算法，且補償算法定義在范圍(BPEL4WS)或上下文(WSCI)或編排(WS-CDL)中。本文擴展BPEL4WS范圍，擴展后范圍由靜態指定改為動態計算，恢復范圍相對固定，缺乏靈活性。

3.1 恢復范圍

考慮不同恢復需求，為不同恢復策略靈活地定義恢復范圍Ξ。況且流程設計師為失敗類型的失敗恢復確定Ξ，也是一件非常困難的事情。本文給出的解決方法是依據恢復規格說明動態計算Ξ。

對于給定 LRT，執行跡σ，如果?σ?Ii,Ij∈σ∧Ii.TBP,Ij.TBP{Co∈mpensable,Vital}，Ii和Ij之間存在依賴之一，且Ii和Ij均是可補償的，則σ是可補償的，記為σ.Compensated。若LRT中每個任務都是可補償的，且與失敗任務存在依賴的任務都能確保成功補償，則該LRT是可補償的。

LRT執行失敗，確定終止依賴點(TDP, terminate dependency point)非常關鍵，恢復處理器(RH, recovery handler)啟動恢復策略(RHS, recovery handling strategy)，對Ξ中所有任務執行恢復，直到TDP。對于給定σ，如果?σ?Ii，Ij∈σ∧Ii.TBP,Ij.TBP∈ {Vital,Compensable}，Ii和Ij之間存在數據流依賴或稱Ii是Ij的 TDP，如圖 2所示。若Ij失敗，從依賴點Ii開始對σm(σm∈σ)執行恢復，稱σm為Ij的依賴路徑。

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

圖2 確定失敗任務的恢復范圍

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

通常，Ξ與RHS集(rhs1,rhs2,…,rhsn)(rhsi≠rhsj,i≠j)相關聯。例如，TRP中Ξ有2個恢復策略rhs1=(Fail(ReserveAirline_Tickets),Compensate(UndoAirline Tickets))和rhs2=(Fail(CarRenting),Alter(BusRenting))，其中，當ReserveAirline Tickets失敗，執行補償，撤銷預訂機票；而CarRenting失敗，調用替代恢復BusRenting執行巴士租賃服務。

3.2 恢復契約

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

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

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

LRT執行過程中，可能出現3種類型失敗：①調用Web服務執行失敗，失敗信息在調用服務描述文檔中給出；② 調用或執行服務超時；③ 執行引擎失敗。本文討論的失敗恢復主要針對前2種情形，因此在發布服務時，需要給出服務契約，任務執行時，給出調用契約：① 若Ii和Ij存在滿足契約CnlCon tract(Ij)，當且僅當Ii失敗且Ii.Failed∈CnlContract(Ij)，則觸發依賴② 若Ij滿足中止契約Abt Contract(Ij)，Ii.failed∈AbtContract(Ij)∨Ii.Aborted∈AbtContract(Ij) ∨Ii.Cancelled∈AbtCon-tract(Ij)，中止Ii則觸發中止依賴③ 若Ii和Ij滿足補償契約CptContract(Ij)，Ii.failed∈CptContract(Ij)∨Ii.Compen sated∈CptContract(Ij)，Ii失敗則觸發依賴為了更準確地選擇RHS提供失敗恢復，RH用恢復契約來配置RHS，優點是隨時增加或減少契約條目。

圖3 嵌套范圍

4 失敗恢復模型及算法

目前業界所提供的失敗處理規范主要是向后恢復，恢復代價較高開銷大，其沒有考慮失敗修復后LRT繼續執行。基于此，本文提出一種支持組合事務的綜合恢復策略，除了保留向后恢復，還擴展了向前和替代恢復。

4.1 向后恢復模型及算法

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

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

算法1 構造恢復流算法

輸入：LRT中任務I的集合, 失敗任務I?和補償依賴集CP

輸出: 恢復流Rflow

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

算法2 RH恢復執行算法

輸入: LRT中任務I的集合, 恢復流Rflow

輸出: 補償服務執行信息

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

4.2 向前恢復模型及算法

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

算法3 向前恢復FRPS算法

輸入：失敗任務I?，執行日志Log，業務流程LRT

輸出：恢復成功或失敗信息

逆向執行恢復流的時間復雜度為O(n)，而從TDP重新執行LRT的時間復雜度為O(n)，因此，FRPS算法的時間復雜度為O(n)。

4.3 替代恢復模型

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

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

5 LRT的事務性質擴展

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

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

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

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

6 失敗恢復網的性質分析

依據 RHS定義，僅有一個初始托肯處于源庫所，如果執行LRT沒有點火任何失敗變遷，托肯將隨正向傳遞，直到成功到達槽庫所。但是，LRT的執行可能導致失敗發生，設失敗恢復網系統依據失敗恢復類型不同，選取那么按流方向Σ

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

定理 1 設失敗恢復網系統Σ=(FRS,M0)，其正向網和恢復網系統分別為Σe=(Ne,Me)和Σr=(Nr-1,Mr)，若Σe執行失敗，則Σ是恢復可達的。

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

定理2 設失敗恢復網系統∑=(FRS,M0)，其中RHS可以是(保證正確恢復。

證明 設Σ的正向網系統和恢復網系統分別是是Σ的失敗發生，那么中任意包含tf的執行路徑若[Me,Mr1]RS(∈Σ,M0)∧Me1∈RS(eΣ,Me0)∧Mr1RS(∈rΣ,Mr0)，存在正向執行路徑σ1，使得M0[σ1＞Me1[tf＞Mr1，依據tf失敗類型，FRS觸發失敗恢復策略則tf點火Σr恢復步σ2 f，并執行σ2 f，使得Mr1[(σ2 f)＞，滿足f:σ1→σ2，Σ是可正確恢復的。

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

定理 3 設失敗恢復網系統Σ=(FRS,M0)，RHS是分別是Σ的正向網和恢復網系統，Σ失敗恢復是安全的。

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

7 基于組合事務恢復的應用

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

圖4 旅行預訂流程

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

表2 可用服務及其事務性質

圖5 TRP組合業務流及其恢復流

圖6 TRP執行預訂及其變更

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

表3 TRP中恢復對描述

圖7 失敗聚合性能比較

圖8 失敗恢復后性能比較

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

圖7中曲線分別對應圖8中QoS0、QoSC1、QoSC2、QoSC3和QoSC4恢復曲線，在第3、4、7和8個失敗處啟動恢復策略，恢復執行后，對響應時間產生了影響，但執行時間和代價變化不大。綜上分析，可以得出以下結論：① 采用合適的恢復策略，可有效減少失敗恢復代價；② 盡管失敗不可避免，但最終可篩選出失敗率較低的LRT；③ 受失敗率影響，聚合曲線可協調LRT中參與組合的服務，消除不利因素影響。

8 結束語

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

未來的工作主要包括如下 4個方面：① 引入事務流日志挖掘算法；② 建立組合事務恢復的依賴規則；③ 深入研究事務恢復的局部和全局約束；④ 違反組合事務性質的檢測技術。

[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.