基于組合調(diào)度框架的容錯Web服務(wù)選擇

李劉靜，邵 清，沈 穎

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

基于組合調(diào)度框架的容錯Web服務(wù)選擇

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

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

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

組合Web服務(wù)；關(guān)鍵路徑；同步節(jié)點；容錯調(diào)度

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

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

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

1 問題描述

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

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

(1)

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

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

(2)

2 組合服務(wù)調(diào)度框架

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

圖1 組合服務(wù)調(diào)度框架

2.1 服務(wù)Agent

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

Agent{

int key;

int credit;

WSDL feature;

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

Long cost;

Long deadline;

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

int faults; //容錯次數(shù)

}

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

圖2 服務(wù)Agent功能

2.2 置信度表

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

Typedef struct WebServiceNode{

Struct WebServiceNode *nextwsn;

//指向下一個服務(wù)的指針

Agent *info;//該服務(wù)相關(guān)信息的指針

}WebServiceNode,AdjList[MAX];

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

圖3 置信度表更新策略

2.3 組合服務(wù)調(diào)度圖

基于置信度表，形成組合服務(wù)執(zhí)行順序，建立組合服務(wù)圖。在此基礎(chǔ)上計算出關(guān)鍵路徑，并設(shè)置同步節(jié)點，最終形成組合服務(wù)調(diào)度圖。

2.3.1 組合服務(wù)圖

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

圖4 組合服務(wù)圖

2.3.2 同步節(jié)點

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

圖5 關(guān)鍵路徑

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

(3)

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

圖6 不同故障數(shù)K下的組合服務(wù)容錯調(diào)度

2.3.3 組合服務(wù)調(diào)度圖(Fault Tolerant Graph)

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

圖7 組合服務(wù)調(diào)度圖

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

圖8 組合服務(wù)的一次容錯調(diào)度路徑

3 容錯Web服務(wù)選擇算法

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

輸入組合服務(wù)圖，容忍故障數(shù)，置信度表AdjList；

輸出就緒隊列L；

(1)初始化置信度表。

Initalize: CreditTable, L, LinkList；

(2)獲取容錯調(diào)度圖的關(guān)鍵路徑。

TopLogicalOrder(G,T);

critical = CriticalPath(G);

(3)設(shè)置關(guān)鍵路徑中的同步節(jié)點。

SynNode = setSynNode(critical);

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

SetDeadline(G,SynNode);

FindInDegree(G,indegree);

(5)祖先服務(wù)的執(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)根據(jù)節(jié)點性質(zhì)設(shè)置服務(wù)Agent

If (Time>=w.Agent.deadline then

w.Agent.faults = k;

else break;

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

(8)根據(jù)執(zhí)行結(jié)果更新CreditTable

UpdateCreditTable(w,adjList);

L.add(next(w));

(9)判斷調(diào)度結(jié)果。

//超過故障容忍次數(shù)或者時間，則調(diào)度失敗

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

Then return false;

4 仿真實驗

4.1 仿真實驗設(shè)計

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

4.2 仿真實驗設(shè)計

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

(4)

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

圖9 3種算法容錯調(diào)度成功率比較

圖10 3種算法服務(wù)響應(yīng)時間比較

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

5 結(jié)束語

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

[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服務(wù)的拜占庭錯誤容忍算法[J].小型微型計算機系統(tǒng),2012,33(3):89-94.

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

[8] 林臻,燕雪峰.一種面向負載平衡的主動復(fù)制技術(shù)[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] 賴巍,郭荷清,朱娟.基于補償服務(wù)鏈的Web服務(wù)容錯機制研究與實現(xiàn)[J].計算機應(yīng)用與軟件,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)；上海市一流學科建設(shè)基金(S1201YLXK)

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

10.16180/j.cnki.issn1007-7820.2017.12.031

TP391.9

A

1007-7820(2017)12-118-05