可靠服务组合的协调策略与分析

-1-可靠服务组合的协调策略与分析范贵生刘冬梅陈丽琼虞慧群(华东理工大学计算机科学与工程系,上海200237)摘要：服务组合是构建复杂Web软件的有效方法，但服务事务状态的多样性使得服务组合的可靠性难以保证。为此，提出一种构造可靠服务组合的协调方法。该方法采用Petri网对工作流建模，以清晰地表达任务及任务之间的逻辑关系。在此基础上，根据服务的事务属性及服务组合的失效处理机制建立服务组合的失效处理模型，并提出一种构造可靠服务组合的协调策略及实施方法。利用Petri网相关理论证明该策略的有效性。旅游服务实例演示了协调技术的应用方法及其可行性。关键词Petri网；Web服务；服务组合；事务；可靠性本课题得到国家自然科学基金(60473055，60773094)及上海市曙光计划（07SG32）资助范贵生，男，1980年生，博士研究生，主要研究方向为软件工程，面向服务计算，形式化方法，E-mail:[e-mail]；刘冬梅，女，1970年生，博士研究生，主要研究方向为软件工程，面向服务计算，形式化方法；陈丽琼，女，1982年生，博士研究生，主要研究方向为分布式计算，嵌入式系统，形式化方法；虞慧群，男，1967年生，博士，教授，博士生导师，IEEE高级会员，ACM会员，.主要研究方向为软件工程，信息安全，形式化方法1引言随着Internet技术应用的迅速发展，基于Web服务的分布式计算模式已经成为软件发展的趋势。Web服务能够统一地封装信息、行为以及业务流程，而无需考虑应用所在的环境。通过Web服务组合来动态生成新的应用系统，以满足实际的需要，已成为Web服务技术不断向前发展的技术动力[1]。然而，Web服务事务状态的多样性使得服务组合变得更为可靠和有效之前，还有一些问题需要处理。其中关键问题就是如何构建可靠服务组合，即如何根据服务的事务属性来分配可用服务以满足服务消费者的需求。虽然传统的事务技术在数据库系统和分布式系统中得到了广泛的应用，但由于Web服务自身的松耦合性、运行时间长、长事务等特点，使其在系统的可靠性和一致性方面面临新的挑战，如何对服务的事务属性进行形式化分析成为业界广泛讨论并关注的问题[2]。Petri网作为一种直观的图形建模工具和一种具有丰富数学基础的形式化模型，可以广泛应用于描述和研究并发、异步和分布式特征的系统，并提供了一种可操作语义及定性和定量分析[3]。最近的研究表明，Petri网适合用来描述服务组合的特性[4,17]。而可靠服务组合的构建不仅可以满足服务消费者的功能需求，同时也能反应出服务的事务属性及失效处理。Petri网及其相关的分析方法为这些目标实现提供了理论基础。本文要解决的就是如何根据服务消费者的需求来动态地分配可用服务，以构建所需的可靠服务组合。为此，提出一种基于Petri网构建可靠服务组合的方法。基本思路为：首先利用Petri网对任务及任务间的关系进行建模，生成相应的工作流模型；其次针对服务的事务属性，构建服务组合的失效处理模型（ServiceComposition’sFailureProcessing,SCFP），并分析SCFP模型的动态性质，从而保证所得到模型的正确性；最后给出可靠服务组合的定义，分析可靠服务组合构造的充分必要条件，提出相应的协调策略并证明其有效性，同时给出协调策略的具体实施。本文第2节给出了工作流的Petri网模型；第3节分析服务的事务属性和服务组合的失效处理机制，生成相应的SCFP模型；第4节提出可靠服务组合的协调策略及实施方法；第5节通过具体实例说明可靠服务组合的构建与分析过程；第6节阐述了相关的研究工作；最后是结论和下一步工作。2工作流的Petri网模型服务组合的功能可以由多个独立运行的子功能构成，本文将每个子功能称为任务。在服务组合流程中，每个任务会有多个可用服务与之对应。本文假设每个服务只能完成一个任务的功能，因此在服务组合中服务和任务是一一对应的。带事务属性的服务组合流程可以从工作流和失效处理两方面进行描述[15]，工作流描述任务之间的数据通信或-2-同步，具体说明了任务组件之间的关系，直观上可以理解为一系列任务的依赖关系。而服务组合的失效处理则规约了服务运行失败时的处理机制，定义了服务的事务属性和服务的失败处理。两者主要区别是：前者假设服务还没分配，仅仅描述服务组合流程的数据依赖；后者假设服务已经分配，主要考虑服务的事务属性和服务失败处理。本节依据服务消费者提供的功能需求，利用Petri网的基本原理，按接口匹配的原则建立系统的工作流模型。2.1任务Petri网模型由于系统的功能是由一系列任务组合而成，而任务的组合又可以构成一个新的任务，如此嵌套可以构造出任意复杂的系统。因此，可利用Petri网对任务进行建模，且每个任务在运行过程中需要输入某些参数和输出一定的结果。下面给出任务的形式化定义。定义1：有界Petri网C=(P,T,F)称作任务，其中：（1）P=PSPI是一个有限库所集，PI表示任务的接口，PS表示任务的位置，其中PSPI=；（2）T是一个有限的变迁集，m≥0，并且PT≠,PT=；（3）F(P×T)(T×P)是有向弧集合，F称为流关系；PintinP1P2P3P4Pet1t2tePi1Pi2Pi3图1带有接口的任务C1在任务模型中，接口代表该任务输入或输出（参数则映射为库所中的令牌）。本文假设任务只有获得所需参数才能运行开始操作，且运行结束后统一输出参数，具体接口个数可以根据实际情况增减。图1中的任务C1有三个接口：库所Pi1和Pi2存放任务开始操作（tin）所需的参数，而库所Pi3则存放任务结束（tin）的输出结果。Pin,Pe表示任务C1的开始和结束位置。某时刻各库所中令牌的分布状况称为任务的标识，在标识M下，库所p中的令牌数量记为M(p)；变迁t在标识M下使能的，记做M[t，否则记做M[t；任意x(PT)，集合●x={y|y(PT)(y,x)F}和x●={y|y(PT)(x,y)F}分别对应于x的输入和输出；其它的定义和触发规则与基本Petri网的定义一样，具体参照文献[3]。2.2工作流模型本文采用了进程代数的一种扩展机制来描述工作流中各个任务之间的关系，形成整个系统所对应的表达式[5]。在应用算子的过程中，可以用括弧来表达作用的顺序（其中顺序算子的优先级最高）。由于模型中的循环结构，可以利用文献[6]介绍的“解循环”操作，即通过统计任务的历史数据，计算循环的平均执行次数n。因此，本文主要对任务间的顺序、选择和并发关系建模，循环结构可以通过任务的顺序执行来完成。假设Ci和Cj为两个任务，下面先描述任务间的基本关系：（1）算子表示顺序：CiCj表示任务Ci和Cj顺序运行，即Cj只有在Ci运行结束后才能开始。（2）算子+表示选择：Ci+Cj表示任务Ci和Cj只有一个可以运行。（3）算子||表示并行：Ci||Cj表示任务Ci和Cj可以同时运行，但要它们都执行结束后整个组合才算执行结束。通过采用上述的算子可以将任务间的关系描述为一个表达式。将在任务Ci运行时刻已经结束的任务称为Ci的前向任务，而Ci运行结束时还未开始的任务称为Ci的后向任务。为了区别任务的操作，在相应的变迁和库所前标注对应的任务。如任务Ci中的开始变迁，表示为Citin。如果变迁是为了描述任务间关系而引入，则不标注。顺序结构允许两个任务Ci和Cj顺序地执行，当一个任务需要用到另外一个任务的输出时就要使用顺序结构来组合。顺序运行CiCj的Petri网模型如图2所示。在Ci和Cj中引入接口Pij使得，●Pij=Cite，Pij●=Cjtin。Pij的存在使得任务Cj只能在Ci结束之后开始运行。Ci.teCj.tinPijCi.PeCj.Pin图2顺序关系的建模为了构造任务间的并行，选择和循环关系，需要分别对任务间的两对基本组件即AND-split和OR-split，AND-join和OR-join进行建模，具体的Petri网模型如图3所示（设任务Ck是Ci1,Ci2,……,Cim的共同前向/后向任务）。AND-split的Petri网模型如图3（a）所示：在Ck中引入接口Pki1,Pki2,……,Pkim，每个并行的任务Cij中引入接口Pkij。其中●Pkij=Ckte,Pkij●=Cijtin,j=1,2,……,n。OR-split的Petri网模型如图3（b）所示：在Ck和所有的选择任务中引入接口Pij使得●Pij=Ckte,Pij●={Ci1tin,Ci2tin,……,Cimtin}。AND-join的Petri网模型如图3（c）所示：在Ck中引入接口Pki1,Pki2,……,Pkim，每个并行的任务Cij中引入接口Pkij。其中Pkij●=Cktin,●Pkij=Cijte,j=1,2,……,n。OR-join的Petri网模型如图3（d）所示：在Ck和所有的选择任务中引入接口Pij使得Pij●=Cktin,●Pij={Ci1te,Ci2te,……,Cimte}。-3-Ck.PinCi1Pe(d)OR-joinCk.tinCim.tePiCk.PinCim.PinCi1.teCi1.Pe......Ci2.teCi2.PeCk.tePki1Ck.PeCi1.tinCi1.PinPkimPki2Ci2.tinCi2.PinCim.tinCim.Pin......(a)AND-splitCk.tePiCkPeCim.PinCi1.tinCi1.Pin......Ci2.tinCi2.Pin(b)OR-splitCim.tinCk.tinPki1Ci1.tePkimPki2Ci2.teCi2.PeCim.teCim.Pe......(c)AND-join图3基本组件的建模下面结合Petri网的合成运算，匹配相应的接口以构造整个系统的工作流模型。定义2：设系统中的任务Ci=(Pi,Ti,Fi)，则按照下列步骤构造的五元组=(C;P,T,F,M0)称为系统的工作流模型：（1）C={C1,C2,……,Cn}，n为系统中任务的个数；（2）依据任务间关系，合成C1,C2,……,Cn的对应接口；（3）引入变迁Tstart和库所Pstart分别描述整个系统的初始位置和开始操作，且：●Tstart={Pstart},Tstart●={Ci1Pin,Ci2Pin,……,CinPin},●Pstart=,Pstart●={Tstart}；（4）设置初始标识M0(Pstart)=1，其余库所为0。工作流模型描述整个系统所能完成的功能，对工作流模型中每个任务分配具体的服务则构成了服务组合。如果分配过程中考虑服务的事务属性，则称它为带事务属性的服务组合。本文中如无特殊说明，服务组合均指带事务属性的服务组合。下面根据所得的工作流模型构造服务组合的失效处理模型。3服务组合的失效处理模型3.1服务的事务属性由于Web服务自身的特点，使得传统的事务处理技术无法直接应用在Web服务事务的处理过程，文献[7]提出的模型指明了服务事务属性的语义，该模型是基于文献[8]所考虑的三种不同的类型的事务属性。由此可以延伸Web服务执行任务时主要有下面三种特性：可重复的（r），可补偿的（cp），不可补偿也不可重复的（p）。相应的服务事务属性可以有以下几种情况：{cp}、{p}、{r}、{r,cp}。根据服务的事务属性，可以建立如图4所示的模型。图4（a）是对可补偿的服务进行建模，PItr表示该服务事务处理的条件。库所SiPItr中有令牌表示服务组合中有其它服务失败，需要根据服务Si的事务属性进行相应的协调。而服务的输入和输出（PIin,PIe）根据实际需要可以进行增减。可补偿服务的运行过程可能处于初始、运行、结束、中断、取消、补偿和失败位置，其中Pin,Pac,Pe,Pab,Pca,Pcp,Pfa称为任务的位置库所。其它的事务属性可以用类似的方法进行描述，具体的模型如图4(b)－图4(d)。(d)r,cpPinti