李劉靜，邵 清，沈 穎

(1.上海理工大學 光電信息與計算機工程學院，上海 200093；2.上海計算機軟件技術開發(fā)中心,上海 200112)

基于組合調度框架的容錯Web服務選擇

李劉靜1，邵 清1，沈 穎2

(1.上海理工大學 光電信息與計算機工程學院，上海 200093；2.上海計算機軟件技術開發(fā)中心,上海 200112)

組合Web服務是互聯網提供服務的一種重要方法，而由于Web服務和網絡環(huán)境的不確定性會導致服務調度失敗。傳統的調度算法沒有兼顧調度可靠性和及時性的平衡，存在一定的局限性。文中結合多樣性和復制方式，提出了基于組合調度的容錯Web服務選擇框架。該算法通過設計服務Agent，根據組合Web服務依賴關系生成組合服務圖，計算出組合Web服務的關鍵路徑。在此基礎上設置同步節(jié)點，同時通過置信度表記錄服務地址和置信度，以保證在容忍一定故障數的情況下實現組合Web服務的及時調度。與傳統調度方式相比，算法在保證調度可靠性的前提下降低了調度響應時間。最后通過實驗驗證了該容錯調度框架的可行性。

組合Web服務；關鍵路徑；同步節(jié)點；容錯調度

組合Web服務是互聯網提供服務的一種重要方法。然而由于Web服務本身以及網絡環(huán)境中存在的各種問題會導致組合Web服務調度失敗。

傳統調度方法主要采用兩種容錯方式：復制和多樣性[1-4]。N版本程序設計，通過將不同版本程序執(zhí)行結果進行選舉，最終選取多數一致的結果作為調度結果集。1-out-of-N算法是選取其中一個版本進行執(zhí)行，如果調度失敗，再繼續(xù)選擇下一個版本進行執(zhí)行，直到成功為止[5-8]。復制方式由于網絡開銷大，重復出錯等問題，有一定的局限性。采用多樣性實現組合Web服務容錯模型雖然解決了復制方式存在的局限性問題[9-10]，但實際容錯環(huán)境中并不是每個服務都有多個實現版本，因此并不完全適用。文獻[11]根據組合服務的置信度來選取多版本服務中的版本，提高了調度的可靠性，但忽略了不是所有Web服務都具有多個版本。

針對上述問題,從組合服務調度框架的建立入手，提出了一種面向組合Web服務的容錯調度框架，能較好地實現調度快速性和容錯性之間的平衡。

1 問題描述

組合Web服務中的服務以及服務之間關系可以抽象成數據對象和數據關系。其中數據對象用來描述每個Web服務本身，數據關系如式(1)所示，用來描述服務間的關系

RF=(〈Wi,Wj〉|Wi,Wj∈W}

(1)

用P(Wi,Wj)表示從Wi～Wj的弧，謂詞P用來定義弧的意義或信息。在組合Web服務中P可以表示執(zhí)行時間或者執(zhí)行條件。

定義1置信度，是指調度成功次數在所有調度次數中所占的比例。Web服務能夠在容忍時間范圍內正常提供服務，即為一次成功的調度。用R表示置信度，如式(2)所示

(2)

2 組合服務調度框架

組合服務調度框架是容錯調度算法的執(zhí)行基礎，其生成邏輯如圖1所示。

圖1 組合服務調度框架

2.1 服務Agent

服務Agent的屬性用來描述Web服務的執(zhí)行狀態(tài)，具體定義如下：

Agent{

int key;

int credit;

WSDL feature;

Bollean syn; //是否為同步節(jié)點

Long cost;

Long deadline;

Int status; //執(zhí)行結果

int faults; //容錯次數

}

其中，syn表示該服務是否被設置為同步節(jié)點；Credit表示該服務執(zhí)行成功的次數，初始值在服務注冊時給出。服務Agent遵循一組簡單的行為規(guī)則同時存儲Web服務的相關信息，如圖2所示。

圖2 服務Agent功能

2.2 置信度表

組合Web服務中不同服務有著不同的置信度。將各服務的引用地址按置信度排序，組織成一張置信度表，作為調度版本選擇的依據。置信度表定義如下

Typedef struct WebServiceNode{

Struct WebServiceNode *nextwsn;

//指向下一個服務的指針

Agent *info;//該服務相關信息的指針

}WebServiceNode,AdjList[MAX];

置信度表生成過程中，對于已經存在的Web服務，根據其置信度，通過使用一個中間WebServiceNode完成插入操作。隨著置信度的變化，服務在表中的位置會及時更新。置信度表更新策略如圖3所示。

圖3 置信度表更新策略

2.3 組合服務調度圖

基于置信度表，形成組合服務執(zhí)行順序，建立組合服務圖。在此基礎上計算出關鍵路徑，并設置同步節(jié)點，最終形成組合服務調度圖。

2.3.1 組合服務圖

Web服務之間的關系包括并列、順序、選擇等，由此構造出組合Web服務執(zhí)行優(yōu)先關系的組合服務圖。如圖4所示，其中頂點表示Web服務，弧線上的P表示時間開銷。

圖4 組合服務圖

2.3.2 同步節(jié)點

關鍵路徑(Critical Path)是指組合服務圖中服務從開始到結束的最長路徑[12]。根據迪杰斯特拉算法求出圖4的關鍵路徑，如圖5所示。

圖5 關鍵路徑

同步節(jié)點(SynNode)是指關鍵路徑中入度大于出度的節(jié)點。在組合Web服務中同步節(jié)點越多，能容忍的故障就越多，但同時也會造成調度時間的增加。同步節(jié)點中有兩個重要參數：一個是截止時間(用DT表示)，規(guī)定同步節(jié)點前驅服務的執(zhí)行時間不超過截止時間；另一個是同步節(jié)點激活時間(用AT表示)，是指其前驅節(jié)點中所有服務調度的最晚完成時間，如式(3)所示

(3)

其中，i表示同步節(jié)點j所有前驅節(jié)點。設W1執(zhí)行時間T1=10 ms，W2執(zhí)行時間T1=100 ms，開始執(zhí)行時間AT=500 ms， 組合服務運行截止時間是DT=850 ms，重執(zhí)行時間開銷是m=25 ms。根據同步節(jié)點激活時間可以得到不同故障數K下組合服務容錯調度結果，如圖6所示。

圖6 不同故障數K下的組合服務容錯調度

2.3.3 組合服務調度圖(Fault Tolerant Graph)

組合Web服務中有些服務有多個版本，有些沒有。對于沒有多版本的Web服務采用重執(zhí)行方式，由此可以構建組合服務調度圖。以圖4顯示的組合服務圖為例，其組合服務調度圖如圖7所示。

圖7 組合服務調度圖

組合Web服務每一次容錯調度過程是通過容錯調度圖(FTG)的條件邊捕獲的，表現為組合服務調度圖中的一條路徑。以圖7為例，一次容錯調度路徑如圖8所示。

圖8 組合服務的一次容錯調度路徑

3 容錯Web服務選擇算法

容錯調度算法以組合服務圖為模型，從所有入度為0的服務開始調度，直到所有出度為0的服務調度完畢，最終的調度結果是組合服務調度圖的子圖。容錯調度算法步驟如下：

輸入組合服務圖，容忍故障數，置信度表AdjList；

輸出就緒隊列L；

(1)初始化置信度表。

Initalize: CreditTable, L, LinkList；

(2)獲取容錯調度圖的關鍵路徑。

TopLogicalOrder(G,T);

critical = CriticalPath(G);

(3)設置關鍵路徑中的同步節(jié)點。

SynNode = setSynNode(critical);

(4)計算同步節(jié)點在容忍時間內的的最晚執(zhí)行時間。

SetDeadline(G,SynNode);

FindInDegree(G,indegree);

(5)祖先服務的執(zhí)行。

While w.Agent.faults>=0

{If w.Agent.status==1 then

w.Agent.faults++;

break;

else then

w.Agent.faults--;}

UpdateCreditTable(w,adjList);

(6)當就緒隊列不為空時執(zhí)行如下步驟：

While(L!=NULL)

w = L.out();

(7)根據節(jié)點性質設置服務Agent

If (Time>=w.Agent.deadline then

w.Agent.faults = k;

else break;

w.Agent.faults = Pred(w).faults--;

(8)根據執(zhí)行結果更新CreditTable

UpdateCreditTable(w,adjList);

L.add(next(w));

(9)判斷調度結果。

//超過故障容忍次數或者時間，則調度失敗

If(w.Agent.faults<0||Time

Then return false;

4 仿真實驗

4.1 仿真實驗設計

以模擬用戶設定旅游計劃的組合Web服務為例，進行仿真實驗分析。實驗中包含5個原子服務，其中，w1為旅游地天氣信息查詢；w2為到目的地的機票信息查詢；w3為旅游團查詢服務；w4為目的地的旅館信息查詢；w5為支付服務；設w1、w2、w3、w4、w5分別對應2、3、1、2、2個不同版本的服務。

4.2 仿真實驗設計

采用組合服務響應時間和容錯調度成功率作為算法性能度量標準。其中組合服務響應時間T，如式(4)所示。

(4)

仿真實驗在Matlab環(huán)境下，共進行20次試驗，并與N版本程序設計方法(多樣性容錯)以及1-out-of-N算法進行比較。仿真結果如圖9和圖10所示。

圖9 3種算法容錯調度成功率比較

圖10 3種算法服務響應時間比較

由圖9和圖10所示，N版本程序設計方法容錯調度成功率最高，但其服務響應時間較長。1-out-of-N算法則正好與之相反，服務響應時間相對較短，但容錯調度成功率也比較低。容錯Web服務選擇在調度成功率和服務響應時間方面相對均衡，雖然調度成功率略低于N版本程序設計方法，但服務響應時間的開銷有很大降低，因此綜合性能更好。

5 結束語

容錯Web服務選擇方式，通過構建組合服務調度框架，生成組合服務的關鍵路徑，并設置同步節(jié)點，兼顧了多樣性和復制方式的優(yōu)點，使得算法在調度成功率和服務響應時間上取得了較好的平衡。由于組合Web服務調度中某些子服務群體可能聚集在某個局部區(qū)域內，可以在局部范圍內維護容錯調度表，以節(jié)省信息傳遞的開銷，這將是下一步的研究內容。

[1] Nascimento A S, Rubira C M, Burrows R, et al.Designing fault-tolerant SOA based on design diversity[J].Journal of Software Engineering Research & Development, 2014,2(1):1-36.

[2] Nascimento A S,Rubira C M F,Burrows R, et al.A systematic review of design diversity-based solutions for fault-tolerant SOAs[C].Canada:International Conference on Evaluation and Assessment in Software Engineering,2013.

[3] Nascimento A S,Castor F,Rubira C M F,et al.An empirical study on design diversity of functionally equivalent Web services[C].France:International Conference on Availability,IEEE,2012.

[4] Salatge N,Fabre J C.Fault tolerance connectors for unreliable Web services[J]. IEEE Transactions on Computer Science,2007(3):51-60.

[5] Looker N,Munro M,Xu J.Increasing Web service dependability through consensus voting[J].IEEE Transactions on Computer Science,2005(2):66-69.

[6] 周偉,王麗娜.一種面向Web服務的拜占庭錯誤容忍算法[J].小型微型計算機系統,2012,33(3):89-94.

[7] 張付志,趙偉偉,周立娜.一種保障響應時間的可靠Web服務組合方法[J].小型微型計算機系統,2010,31(10):1959-1964.

[8] 林臻,燕雪峰.一種面向負載平衡的主動復制技術[J].電子科技,2012,25(4):37-40.

[9] Faci N,Abdeldjelil H,Maamar Z,et al. Using diversity to design and deploy fault tolerant Web services[J].Proceedings of the Workshop on Enabling Technologies Infrastructure for Collaborative Enterprises Wet Ice,2011,8(1):73-78.

[10] Abdeldjelil H,Faci N,Maamar Z,et al.A Diversity-based approach for managing faults in Web services[J].IEEE Transactions on Computer Science,2012, 26(1):81-88.

[11] 賴巍,郭荷清,朱娟.基于補償服務鏈的Web服務容錯機制研究與實現[J].計算機應用與軟件,2009,26(1):108-109.

[12] Zhang Jun.Efficient feasibility analysis of DAG scheduling with real-time constrains in the presence of faults[C].Xiamen:Design Automation Conference,2014.

The Fault Tolerant Web Services Selection Based on Scheduling Framework

LI Liujing1，SHAO Qing1，SHEN Ying2

(1.School of Optical-Electrical and Computer Enginnering, University of Shanghai for Science and Technology, Shanghai 200093, China;2. Shanghai Development Center of Computer Software Technology, Shanghai 200112, China)

In order to solve the problem of schedule failure in composite Web services, this paper proposed a fault tolerant scheduling algorithm. The algorithm established a framework of composite Web service. First, it designed service Agent to describe execution of Web services, then calculated the key path of the composite service and set the synchronization node according to the combined service graph. At the same time in the whole service area reliability tables were maintained and updated in time to make scheduling process effectively. Compared with the existing methods, this algorithm improves the reliability of the service scheduling and reduces the response time. The results show it is feasible.

composite Web service; key path; synchronization node; fault tolerant scheduling

2017- 02- 20

國家自然科學基金(61170277,61472256)；上海市教委科研創(chuàng)新重點基金(12zz137)；上海市一流學科建設基金(S1201YLXK)

李劉靜(1990-)，女，碩士研究生。研究方向：分布式計算等。邵清(1970-)，女，副教授。研究方向：網絡智能等。沈穎(1974-)，女，高級工程師。研究方向：Web應用開發(fā)等。

10.16180/j.cnki.issn1007-7820.2017.12.031

TP391.9

A

1007-7820(2017)12-118-05