基于组合调度框架的容错Web服务选择

李刘静，邵 清，沈 颖

(1.上海理工大学 光电信息与计算机工程学院，上海 200093；2.上海计算机软件技术开发中心,上海 200112)

基于组合调度框架的容错Web服务选择

李刘静1，邵 清1，沈 颖2

(1.上海理工大学 光电信息与计算机工程学院，上海 200093；2.上海计算机软件技术开发中心,上海 200112)

组合Web服务是互联网提供服务的一种重要方法，而由于Web服务和网络环境的不确定性会导致服务调度失败。传统的调度算法没有兼顾调度可靠性和及时性的平衡，存在一定的局限性。文中结合多样性和复制方式，提出了基于组合调度的容错Web服务选择框架。该算法通过设计服务Agent，根据组合Web服务依赖关系生成组合服务图，计算出组合Web服务的关键路径。在此基础上设置同步节点，同时通过置信度表记录服务地址和置信度，以保证在容忍一定故障数的情况下实现组合Web服务的及时调度。与传统调度方式相比，算法在保证调度可靠性的前提下降低了调度响应时间。最后通过实验验证了该容错调度框架的可行性。

组合Web服务；关键路径；同步节点；容错调度

组合Web服务是互联网提供服务的一种重要方法。然而由于Web服务本身以及网络环境中存在的各种问题会导致组合Web服务调度失败。

传统调度方法主要采用两种容错方式：复制和多样性[1-4]。N版本程序设计，通过将不同版本程序执行结果进行选举，最终选取多数一致的结果作为调度结果集。1-out-of-N算法是选取其中一个版本进行执行，如果调度失败，再继续选择下一个版本进行执行，直到成功为止[5-8]。复制方式由于网络开销大，重复出错等问题，有一定的局限性。采用多样性实现组合Web服务容错模型虽然解决了复制方式存在的局限性问题[9-10]，但实际容错环境中并不是每个服务都有多个实现版本，因此并不完全适用。文献[11]根据组合服务的置信度来选取多版本服务中的版本，提高了调度的可靠性，但忽略了不是所有Web服务都具有多个版本。

针对上述问题,从组合服务调度框架的建立入手，提出了一种面向组合Web服务的容错调度框架，能较好地实现调度快速性和容错性之间的平衡。

1 问题描述

组合Web服务中的服务以及服务之间关系可以抽象成数据对象和数据关系。其中数据对象用来描述每个Web服务本身，数据关系如式(1)所示，用来描述服务间的关系

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

(1)

用P(Wi,Wj)表示从Wi～Wj的弧，谓词P用来定义弧的意义或信息。在组合Web服务中P可以表示执行时间或者执行条件。

定义1置信度，是指调度成功次数在所有调度次数中所占的比例。Web服务能够在容忍时间范围内正常提供服务，即为一次成功的调度。用R表示置信度，如式(2)所示

(2)

2 组合服务调度框架

组合服务调度框架是容错调度算法的执行基础，其生成逻辑如图1所示。

图1 组合服务调度框架

2.1 服务Agent

服务Agent的属性用来描述Web服务的执行状态，具体定义如下：

Agent{

int key;

int credit;

WSDL feature;

Bollean syn; //是否为同步节点

Long cost;

Long deadline;

Int status; //执行结果

int faults; //容错次数

}

其中，syn表示该服务是否被设置为同步节点；Credit表示该服务执行成功的次数，初始值在服务注册时给出。服务Agent遵循一组简单的行为规则同时存储Web服务的相关信息，如图2所示。

图2 服务Agent功能

2.2 置信度表

组合Web服务中不同服务有着不同的置信度。将各服务的引用地址按置信度排序，组织成一张置信度表，作为调度版本选择的依据。置信度表定义如下

Typedef struct WebServiceNode{

Struct WebServiceNode *nextwsn;

//指向下一个服务的指针

Agent *info;//该服务相关信息的指针

}WebServiceNode,AdjList[MAX];

置信度表生成过程中，对于已经存在的Web服务，根据其置信度，通过使用一个中间WebServiceNode完成插入操作。随着置信度的变化，服务在表中的位置会及时更新。置信度表更新策略如图3所示。

图3 置信度表更新策略

2.3 组合服务调度图

基于置信度表，形成组合服务执行顺序，建立组合服务图。在此基础上计算出关键路径，并设置同步节点，最终形成组合服务调度图。

2.3.1 组合服务图

Web服务之间的关系包括并列、顺序、选择等，由此构造出组合Web服务执行优先关系的组合服务图。如图4所示，其中顶点表示Web服务，弧线上的P表示时间开销。

图4 组合服务图

2.3.2 同步节点

关键路径(Critical Path)是指组合服务图中服务从开始到结束的最长路径[12]。根据迪杰斯特拉算法求出图4的关键路径，如图5所示。

图5 关键路径

同步节点(SynNode)是指关键路径中入度大于出度的节点。在组合Web服务中同步节点越多，能容忍的故障就越多，但同时也会造成调度时间的增加。同步节点中有两个重要参数：一个是截止时间(用DT表示)，规定同步节点前驱服务的执行时间不超过截止时间；另一个是同步节点激活时间(用AT表示)，是指其前驱节点中所有服务调度的最晚完成时间，如式(3)所示

(3)

其中，i表示同步节点j所有前驱节点。设W1执行时间T1=10 ms，W2执行时间T1=100 ms，开始执行时间AT=500 ms， 组合服务运行截止时间是DT=850 ms，重执行时间开销是m=25 ms。根据同步节点激活时间可以得到不同故障数K下组合服务容错调度结果，如图6所示。

图6 不同故障数K下的组合服务容错调度

2.3.3 组合服务调度图(Fault Tolerant Graph)

组合Web服务中有些服务有多个版本，有些没有。对于没有多版本的Web服务采用重执行方式，由此可以构建组合服务调度图。以图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)设置关键路径中的同步节点。

SynNode = setSynNode(critical);

(4)计算同步节点在容忍时间内的的最晚执行时间。

SetDeadline(G,SynNode);

FindInDegree(G,indegree);

(5)祖先服务的执行。

While w.Agent.faults>=0

{If w.Agent.status==1 then

w.Agent.faults++;

break;

else then

w.Agent.faults--;}

UpdateCreditTable(w,adjList);

(6)当就绪队列不为空时执行如下步骤：

While(L!=NULL)

w = L.out();

(7)根据节点性质设置服务Agent

If (Time>=w.Agent.deadline then

w.Agent.faults = k;

else break;

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

(8)根据执行结果更新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环境下，共进行20次试验，并与N版本程序设计方法(多样性容错)以及1-out-of-N算法进行比较。仿真结果如图9和图10所示。

图9 3种算法容错调度成功率比较

图10 3种算法服务响应时间比较

由图9和图10所示，N版本程序设计方法容错调度成功率最高，但其服务响应时间较长。1-out-of-N算法则正好与之相反，服务响应时间相对较短，但容错调度成功率也比较低。容错Web服务选择在调度成功率和服务响应时间方面相对均衡，虽然调度成功率略低于N版本程序设计方法，但服务响应时间的开销有很大降低，因此综合性能更好。

5 结束语

容错Web服务选择方式，通过构建组合服务调度框架，生成组合服务的关键路径，并设置同步节点，兼顾了多样性和复制方式的优点，使得算法在调度成功率和服务响应时间上取得了较好的平衡。由于组合Web服务调度中某些子服务群体可能聚集在某个局部区域内，可以在局部范围内维护容错调度表，以节省信息传递的开销，这将是下一步的研究内容。

[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)；上海市教委科研创新重点基金(12zz137)；上海市一流学科建设基金(S1201YLXK)

李刘静(1990-)，女，硕士研究生。研究方向：分布式计算等。邵清(1970-)，女，副教授。研究方向：网络智能等。沈颖(1974-)，女，高级工程师。研究方向：Web应用开发等。

10.16180/j.cnki.issn1007-7820.2017.12.031

TP391.9

A

1007-7820(2017)12-118-05