基于事务的分布式虚拟化环境下服务替换方法

邹世辰 王慧强 吕宏武 冯光升 林俊宇

1(哈尔滨工程大学计算机科学与技术学院 哈尔滨 150001)2(中国科学院信息工程研究所 北京 100093)(zoushichen@hrbeu.edu.cn)

分布式虚拟化环境(distributed virtualized environment, DVE)[1]是一类以分布式虚拟化技术为核心的通用计算环境，具有显著的开放、共享、动态、透明等特性.受到“一切皆服务”的思想启发以及服务虚拟化技术的普及与发展，DVE下的服务数量呈现爆炸式增长，虚拟化映射后的服务通过动态组合来构建软件系统的方式已然成为主流.面对着工业、农业、制造业、服务业、教育业等领域的业务需求，服务组合的可信性保障成为一个备受关注的研究热点.由于各式各样的服务运行在开放动态的DVE中，各种异常、失效、故障均可能导致服务可信性的降低，因此需要实现服务在线演化，即服务组合在外部环境和用户需求发生变化时能够进行适应性变更，并保持服务与相关应用有效性.作为服务可信性保障的重要一环，组合服务演化是一个非常复杂的处理过程.当组成服务组合的服务组件失效时，选择与其功能相似且参数匹配服务组件进行服务替换已成为一种非常重要的技术手段.服务替换可以保证服务组合后续正常运行，避免服务可信性降低，受到工业界与学术界的广泛关注.

传统的服务替换大多采用备份路径替换[2-3]、基于功能分簇替换[4-5]等策略，这些方法与策略能够在一定程度上适应环境变化，保证系统不被中断地运行下去，但这些方法忽略服务的事务属性，缺乏对服务事务原子性和一致性的保障，直接造成了服务组合替换的正确率低、效率差，因此在实时变化的DVE中支持事务级的服务替换，提高服务异常处理的能力十分重要.但是事务级服务替换也面临着一系列的挑战，例如传统的2阶段提交机制需要对资源进行阻塞，显然不适用于运行时间跨度普遍较大的服务组合中，需要适度放宽对事务原子性、隔离性的要求来提高资源并发使用的效率.同时，服务的动态组合决定了事务粒度不可能由单个服务组件的开发者决定，动态绑定的运行方式也使得服务组合依赖关系较为复杂，如何确定事务级替换粒度以及级联补偿范围成为一个不可回避的难题.此外，大多数相关研究都是在故障或失效发生后如何触发服务替换，却对替换服务的选择上有哪些事务级的限制鲜有提及，选取具有合适属性的服务来进行替换也是软件演化与可信性保障方法中十分值得关注的.

基于以上考虑，本文提出了一种基于事务补偿的分布式虚拟化环境下服务替换方法，实现支持事务级的服务替换，维护服务组合在替换过程中的一致性为实现面向可信性保障与增强的服务组合演化提供支撑.本文的主要贡献如下：

1) 提出了一个支持事务级属性的层次化服务组合模型，使用扩展层次化有色网并结合服务事务属性来描述服务组合中复杂的数据流关系，通过层次嵌套的方式来降低模型复杂度，避免后续分析过程中状态空间爆炸问题；

2) 提出了服务事务粒度识别与服务替换补偿方法，通过数据依赖关系来有效识别服务组合事务范围，进而在服务替换时针对同一事务的服务组件进行补偿，来维护服务组合的一致性；

3) 基于事务粒度识别与服务补偿，提出了一种服务组合失效处理方法，并充分考虑候选替换服务选择的事务属性限制，为选择合适的服务组件或组合服务来替换失效部分提供指导，促使服务组合的可信性增强演化.

1 支持事务级属性的层次化服务组合模型

1.1 基本定义

为便于后续阐述和分析，本节给出一个“商务旅行”的组合服务作为实例，如图1所示.用户首先根据到达目的地距离、时间等情况选择出行交通工具，通过“预订机票”或者“预定火车票”等服务来实现，同时用户需要查询并预定一个目的地宾馆，执行“预定宾馆”服务；然后根据预定的出行方式以及酒店位置，规划出行路线，并预定出租车来完成出行.

服务组合的基本单元是操作.图1中所给出的服务活动大多为业务级服务，与只包含一个操作的简单服务不同，每个业务服务可能包含着一个或多个操作，甚至嵌套着其他业务服务.如搜索航班的业务服务中包含着预订操作、支付服务和出票操作，支付服务中还包含着支付请求、网上银行支付等操作.

由图1的实例可以看出，组合服务自身是存在着层次关系的，其间的数据依赖、控制关系更是错综复杂的，一旦某处失效，必然会导致整个组合服务的连锁反应.在预定车票的服务中，当进行到Payment时可能由于网络中断等原因导致支付失败，但是前期预订车票的操作已经被提交，就会出现车票被预订出去，但是由于支付失败未能出票，而其他用户又无法购买这张车票的情况.在无事务的服务替换过程中仅仅替换失效的支付服务，那么新启用的支付服务势必需要预订服务重新发起一次支付请求来作为输入，这会造成重复预订，进而导致数据一致性的破坏.由此可见，预订、支付、送票这一系列的服务操作必须作为一个事务，当支付服务失效时，需要对预订服务来进行补偿(即撤销预订的车票).

1.2 扩展层次化有色网

为了准确描述组合服务中层次结构以及各个部分之间数据控制关系，从而对服务组合中的事务粒度与服务替换补偿方法进行分析，本节使用扩展层次化有色网对服务组合的组件及其消息交互进行建模.首先给出一些符号的定义：

1)Type表示变量或表达式的类型.

2)Var表示表达式的变量集合.

有色Petri网通过扩展Petri网的令牌机制，使其具有颜色和类型，能够用于描述复杂的数据对象，同时也解决了普通Petri网中的二义性问题.但是使用普通有色网中单一的变迁类型难以表达服务组合中丰富的组合模式，因此引入扩展有色网ECPN(extended color Petri net)，将变迁根据其功能分为4类.

定义1. 一个ECPN是满足下列条件的八元组，ECPN=(P,T,C,A,Cd,G,E,I)，其中：

1)P是库所的有穷集合.

2)T是变迁的有穷集合，且P∩T=∅.在扩展有色网的变迁中引入如下类型变迁.

① 服务处理变迁，当变迁被触发后调用相对应的服务来完成动作.

② 流程控制变迁，根据服务流程的状态与条件，产生不同的控制托肯，触发不同的变迁，进入不同状态.在针对并发服务时，用于协调各变迁之间的同步.从而加强网的数据流描述能力，丰富了网的语义表达功能，有助于模型的建立和理解.

③ 接口变迁，用来设置条件，判断某上层网络输出令牌的颜色和数量与子网络要求的输入令牌是否一致.

④ 空变迁，相当于空转移，满足某些特殊情况下的有色网定义.

3)C是颜色类的有穷集合.

4)A是弧的有穷集合，P∩A=T∩A=∅.

5)Cd是颜色函数，Cd:P∪T→C.

6)G是哨函数，G:T→expr且满足∀t∈T:[Type(G(t))=Bool∧Type(Var(G(t)))⊂C].

7)E是弧表达式函数，E:A→expr且满足∀a∈A:[Type(E(a))=Cd(p(a))MS∧Type(Var(E(a)))⊆C]，其中Cd(p(a))MS表示颜色集合上的所有多重集合的集合.

8)I是初始化函数，I:P→expr且满足∀p∈P:[Type(I(p))=Cd(P)MS].

由于ECPN中引入了变量和颜色，需要对变迁进行绑定.变迁的绑定是指将变迁中的每个变量用一种适当的颜色代替，并且满足弧表达式，从而使得哨函数为真.

ECPN通过对变迁的多样化，实现了对服务组合的复杂模式的描述，但是复杂的大型组合使得Petri网十分庞大复杂，因此引入层次化思想，形成扩展的层次化扩展有色网EH_CPN(extended hierarchical color Petri net)，通过分层描述，减小模型的复杂度，有效改善非层次化模型在描述大型Web服务组合时，状态迅速膨胀，使得分析变得困难的状况.

Fig. 3 The EH_CPN model of business travel service composition图3 “商务旅行”服务组合EH_CPN模型

定义2. 一个EH_CPN是满足下列条件的四元组，EH_CPN=(S,C,IC,I0)，其中：

1)S是子网的有穷集合，且满足以下条件.

① ∀s∈S，s=(ECPN,Ci,Co)，其中Ci和Co分别是输入和输出颜色的有穷集合.

② ∀si，sj∈S，si≠sj∧(Psi∩Tsi∩Asi)∪(Psj∩Tsj∩Asj)=∅.

2)C是颜色类的有穷集合.

3)IC是接口验证函数，用于测试上层网络输入的token类型和数量是否符合要求，IC:I0→expr，且满足Type(IC(I0))=Bool.

4)I0是初始状态.

服务组合由一系列的服务或服务组合通过组合控制结构组合而成，通过分析其间逻辑关系，可以将这些控制结构分为5类[6]，分别是Sequence，And-Join，Or-Join，And-Split，Or-Split.包括循环结构在内的大部分复杂控制结构均可由这5类逻辑关系以及流程控制变迁组合而成.5类控制结构如图2所示：

Fig. 2 Service composition control structure图2 服务组合控制结构

为使服务变迁在没有数据依赖时推动组合流程继续执行，在EH_CPN模型中引入控制托肯，只有当变迁获得控制托肯才能被触发.控制托肯可以单独的在网内流动，也可以和数据托肯混合流动，所构成的控制流不影响模型数据流的分析.对于需要根据服务组件的特定状态来决定服务组合控制流等复杂情况，由于需要服务组合执行引擎提供活动实例执行情况的监视结果，模型无法提供直接支持，因此本文不做讨论.图1中服务组合经过EH_CPN建模后，如图3所示.

为节省空间，图3中省略了不同层次子网间的接口变迁.通过分析模型中可以得到库所颜色集以及变迁颜色，如航班预定服务中的支付子服务组合中的变迁颜色Cd(PayRequest)={(CreditCard,FlightOrder,PaypalReq,EbankReq)|(CreditCard∧FlightOrder∧PaypalReq)∨(CreditCard∧FlightOrder∧EbankReq)}，Cd(Paypal)={(PaypalReq,PayInfo)|PaypalReq∧PayInfo}，模型其他部分的分析结果不再赘述.

1.3 事务属性

事务是一组在逻辑上属于一个单元的操作，这些操作要么全部生效，要么全部没有发生.传统的事务应当遵从ACID原则，即原子性(atomicity)、一致性(consistency)、隔离性(isolation)、持久性(durability).对于服务组合这类的跨组织协作的系统，显然需要放开一些隔离性等方面的限制，但是一致性是必须被强制要求的.由于服务组件中的表现行为、依赖关系与服务组合中的有着一定的区别，事务属性可被区分为服务的事务属性和服务组合的事务属性[7].

定义3. 服务的事务属性用于保证服务执行过程中一致性，包括关键性(pivot)、可补偿性(compensatable)和可重试性(retriable)，其中：

1) 关键性.具有关键性的服务一旦执行成功，其对系统的影响将持续下去，不可回滚或恢复，它并不保证服务一定成功执行，如果执行失败将不对已执行的服务的结果产生任何影响，记作p.

2) 可补偿性.具有可补偿性的服务被执行后，可调用另外一个相应的服务来还原已经完成的活动，一般包括向前(替换)和向后(回滚撤销)2类补偿操作，记作c.

3) 可重试性.具有可重试性的服务可以被有限次的重复调用，直至执行成功，记作r.

一般而言，如果一个服务不是可补偿或可重复的，那么它一定是关键性服务.服务的事务属性可以相互叠加，具体的可能出现的属性包括{p,c,pr,cr}.具有这些属性的服务即可称作具有事务属性的服务.

定义4. 服务组合的事务属性用于保证服务组合执行过程中一致性，包括原子性(atomic)、可补偿性(compensatable)和可重试性(retriable)，其中：

1) 原子性.具有原子性的服务组合中，所有服务组件执行成功后的结果均不可回滚或恢复，如果某组件失效，则所有已执行的服务组件需要被补偿，记作a；不具有原子性的服务组合用～a表示.

2) 可补偿性.具有可补偿性的服务组合中，所有服务组件都可以补偿，记作c.

3) 可重试性.具有可重试性的服务组合可以被有限次的重复调用，直至执行成功，记作r.

服务组合的事务属性也可以相互叠加，具体的可能出现的属性包括{a,c,ar,cr}.一个服务组合只要具有上述集合中任何一个属性，则这个服务组合就被称作具有事务属性的服务组合.

由于服务通常是长时间运行的，是典型的长事务，为了维持数据一致性，直接采用数据库系统中资源锁定的方式显然不适用，由此引入的服务补偿的概念来维持服务系统的一致性.

定义5. 服务补偿.在服务发生故障或失效时，用来撤销已完成的服务活动所产生的执行效果的操作.

服务补偿通常作为服务的事务性保证最有效的手段，最先由Garcia-Molina和Salem在定义的Saga模型[8]中提出来.其中每个可补偿的子事务都有一个对应的补偿块，通常由服务开发者预先提供.如果某事务发生失效，则从失效部位出发，根据服务的控制流、业务流和数据流等依赖关系确定补偿范围，按照子事务被提交的逆序调用每一个子事务对应的补偿块.由此可见，事务粒度的识别以及补偿图的生成是能否维持服务组合系统一致性的重中之重，同时由于业务级联所带来的级联补偿问题也同样对失效处理与服务替换的成功有着极大影响.

2 事务粒度识别与补偿方法

服务是典型的长事务，同时不同的服务来自不同地域、不同开发者，服务之间各种数据流、控制流错综复杂，使得业务流程中的事务粒度和范围无法由服务提供商来给定.因此为了保证支持事务的服务组合系统中数据一致性，需要先识别得到事务的粒度，进而采用服务替换、失效补偿等手段来维持服务系统的稳定运行.组合服务间的事务范围的获取主要还是由依赖关系来决定的，其中最重要的就是数据依赖关系.

2.1 数据依赖关系

服务组合中各组件之间的交互是基于XML消息报文的，因此数据依赖关系可以通过分析服务间交互信息，从报文中包含的各种变量的生成与使用情况可以获得数据流在不同服务组件之间的流动情况.与传统应用程序变量有所不同，服务组合中变量不是最小单元，而是由更小粒度的类型复合而成.结合EH_CPN模型来看，数据在服务组件间的流动可以被映射为数据托肯在变迁的流动，变量则是服务变迁消耗或生成的数据托肯集，库所则是提供了一个变量缓存的场所，通过分析定义在变迁上的颜色就可以有效地分析出带有颜色的数据托肯的消耗和生成情况，进而可以得到服务组合的数据流.由模型中的变迁颜色所得到的数据定义与使用关系，可以将服务组件间的数据依赖分为直接依赖关系和间接依赖关系.

定义6. 直接依赖关系.服务变迁ST1定义的数据被服务变迁ST2使用，那么ST1和ST2存在直接依赖关系，记作D_Dep(ST1,ST2).

服务组合中所有服务变迁间的直接依赖关系的集合可由算法1获得.

算法1. 构建直接依赖关系.

输入:服务组合EH_CPN模型SC;

输出:数据依赖集D_Dep.

ForeachtinSC

Iftnot inSTthen

continue;

Else

ForeachcinCd(t)

IfcinType(Var(AIN)) then /*AIN为变迁t的输入弧*/

Puttinuse(c); /*use(c)为颜色c所代表的变量的使用者集合*/

Else IfcinType(Var(AOUT)) then

/*AOUT变迁t的输出弧*/

Puttindef(c); /*def(c)颜色c所代表的变量的定义者集合*/

End If

End Foreach

End If

End Foreach

ForeachcinC

Ifdef(c)=∅ oruse(c)=∅

continue;

Else

Foreachst1 indef(c)

Foreachst2 inuse(c)

PutD_Dep(st1,st2) inD_Dep;

End Foreach

End Foreach

End If

End Foreach

ReturnD_Dep.

存在直接依赖关系的服务变迁之间并不一定是通过库所直接连接，之间可能间隔控制变迁、接口变迁甚至是不涉及变量消耗的服务变迁.此外需要注意的是D_Dep(ST1,ST2)不等价于D_Dep(ST2,ST1)，即依赖关系不符合交换律.但依赖关系是可传递的，从而构成了间接依赖关系.下面给出间接依赖关系的定义.

定义7. 间接依赖关系.如果服务变迁ST2利用服务变迁ST1定义的数据作为输入，进而定义了新的数据被服务变迁ST3使用，则称服务变迁ST1和ST3之间存在间接依赖关系，记作I_Dep(ST1,ST2).

定义8. 数据依赖集.所有和服务变迁ST存在直接依赖关系和间接依赖关系的服务变迁构成的集合称为数据依赖集，记作DepSet(ST).

由定义显然可知，对于STi∈DepSet(ST)，满足D_Dep(STi,ST)或者I_Dep(STi,ST).通过直接和间接的数据依赖关系，我们可以采用递归调用的方法，沿着服务变迁组合的EH_CPN模型中连接库所与变迁间的弧，逆向构建生成关于某个服务变迁ST的数据依赖集.

通过对服务组合中某个组件的数据依赖关系分析构建得到的数据依赖集，可以直观地反映出数据流影响的范围，但是由于服务组合中各部分的运行通常是并发，而数据依赖集只能体现出顺序的数据调用与被调用，无法用于分析并发分支间的数据依赖情况，因此需要对数据依赖集进行扩展，从而实现服务组合事务范围识别.

2.2 服务组合事务范围识别

服务组合中的事务范围识别直接关系到服务替换时能否有效地维护数据一致性，只有正确识别事务粒度和范围大小，才能明确如何在服务替换后对服务组合中有数据依赖的部分进行补偿.由2.1节得到的数据依赖集仅能支持在逻辑上沿着数据流动的方向顺序找到位于失效服务前的服务，对于并行分支间存在的间接或嵌套依赖显得无能为力，因此仅靠数据依赖集来确定服务组合事务范围是不完整的.需要结合服务组合的EH_CPN模型以及前文提出的分支结构补偿处理的方法，将数据依赖集扩展成为依赖图，从而到达准确识别服务组合事务范围的效果.面向一致性维护的服务组合事务范围主要是由数据依赖关系决定，显然与失效待替换部分有着数据依赖的服务组件必须加入到事务中来，在服务替换之后需要对已完成的部分进行补偿.但由于服务组合中的控制结构复杂多样，因此需要根据服务组合过程模型的控制结构和数据依赖关系的不同来分别处理.首先定义补偿关系：

定义9. 补偿关系.如果服务变迁ST2发生服务替换后需要对变迁ST1进行补偿来维护服务组合的一致性，则称服务变迁ST1和ST2之间存在间接依赖关系，记作Comp(ST1,ST2).

由1.2节可知，组合过程的控制结构可分为Sequence，And-Join，Or-Join，And-Split，Or-Split，大部分复杂控制结构均可由这5类逻辑关系以及流程控制变迁组合而成.因此本节针对这5种最基本的控制结构，结合EH_CPN模型来对事务范围的识别作出如下处理：

1) Sequence.服务变迁ST1与ST2之间是Sequence结构时，如果ST1与ST2之间存在依赖关系，显然ST2失效时需要对ST1进行补偿，即Comp(ST1,ST2)，ST1以及ST1与ST2之间所有顺序相连的变迁都需要加入事务范围中.

2) Or-Split.由于分支结构间是互斥的，所以只有失效服务变迁所在分支被触发激活，只需将该分支内有依赖关系的服务变迁加入事务范围，不同分支间无需处理.

3) Or-Join.与Or-Split类似，如果后续服务失效时，只需对已触发完成的分支内存在数据依赖的服务变迁加入事务范围，其他分支无需处理.

4) And-Split.不妨设ST2和ST3是And-Split中并行的2个分支且ST1与ST2∧ST3构成Sequence.①如果ST2与ST1存在数据依赖，则ST2失效时需要对ST1进行补偿，即Comp(ST1,ST2)，同时由于ST1被触发补偿，ST3作为ST1并行分支，该分支上所有已完成的服务也需要被补偿，因此均需要加入事务范围；②如果ST2与ST1不存在数据依赖，则ST2失效时不需要对ST1以及ST3所在分支进行补偿，因此无需处理.

5) And-Join.不妨设ST1和ST2是And-Join中并行的2个分支，如果ST1和ST2间存在数据依赖，则Comp(ST1,ST2)，不同分支内的服务变迁需要加入事务范围进行补偿；如果ST1和ST2间不存在数据依赖，则不同分支间不需要加入事务范围进行补偿.

经过上述对于属于不同控制结构的服务变迁进行分析，可以得到服务组合中的所有事务的范围.由于篇幅限制，该算法不做具体伪代码描述.针对并行的And-Split和And-Join情况，以图4为例进行说明.图4针对图1流程中的订机票阶段进行了改动，订机票服务将根据所订机票的起飞机场不同，同时并发地预订到达起飞机场的出租车，只有在订票和订车2个支付全部成功后才能触发送机票服务，因此2个并行分支构成了And-Split和And-Join结构.当机票支付服务失效时，由于与预订服务存在着数据依赖，根据前文提出的方法，预订出租车的服务也要补偿(没有成功购买该机场出发的航班也就没有必要坐出租车去该机场).如果送票服务失效，由于只有机票支付服务与其有数据依赖，因而不需对出租车支付服务进行补偿(但由于与机票支付服务间And-Split结构，最终出租车支付服务还是需要补偿).与此同时，机票和出租车的支付服务经过合并所得到的嵌套服务，与预订服务、送票服务间构成了Sequence结构，由于各个服务间均存在数据依赖，因此这些服务共同属于一个事物范围.

Fig. 4 The compensation of And-Join and And-Split图4 And-Join和And-Split时的补偿

2.3 补偿图生成与服务失效处理

在获取服务组合中各组件之间的数据依赖关系以及确定事务范围之后，就可以对服务组合中失效部位进行替换，并生成补偿图.补偿图是是服务组合失效部位及其所在事务范围内部分构成的集合，是服务组合失效处理器进行服务替换补偿时的执行路线.补偿图实质上是在原服务组合模型的基础上，生成了一个由补偿服务构成的一个子服务组合.依赖图的生成只需要对2.2节得到的依赖图所对应的事务与原服务组合EH_CPN模型的交集，将弧的方向取反，构成补偿路线图，算法细节不再赘述.根据动态生成的补偿图，从失效替换部位对所在事务范围内的其他服务组件选取适当的补偿服务进行补偿，以维持整个服务组合系统处于语义上的一致状态.

在获得补偿图的基础上，结合服务的事务属性，本文进一步提出基于事务级服务替换的服务组合失效处理算法,详细过程如下：

算法2. 失效处理算法.

输入:服务组合EH_CPN模型SC、失效服务fs;

输出:自动失效处理结果.

Iffsis retriable Then

rebootfs;

Else

subs(fs); /*进行服务替换*/

cg=compensategraph(fs); /*构建fs的补偿图*/

Foreachstincg

Ifstis compensatable Then

compensatest; /*对补偿图内所有服务进行补偿*/

Else

Return Failed; /*如果st不能补偿，

则终止算法，等待人工介入*/

End If

End Foreach

Return Success;

End If

算法2中，首先如果失效服务具有r事务属性，说明该服务能重启，那么就先尝试重新激活该服务并运行，直到成功完成，如果不能重启则需要替换该服务，并对事务范围的其他服务进行补偿.具体补偿过程是先在事务范围内，根据失效服务生成的补偿图；然后从失效部位开始反向向前的、针对已执行完毕的服务进行补偿，如果事务范围内的某一服务或服务组合不能被补偿(不具有补偿属性或者没有补偿服务操作)，则服务失效的自动处理失败，终止算法并请求人工介入处理.

2.4 替换服务选择的事务属性限制

在服务失效补偿完成之后，为了维持服务组合的继续运行，需要选择合适的服务组件或组合服务来替换失效部分.然而替换服务的选择上，传统方法大多仅是从QoS优化的角度出发，很少有考虑替换服务的事务属性.如果替换服务的事务属性选择不当，会破坏原组合服务的事务性，从而导致后续失效处理上的失败，降低了服务可信性.由于QoS最优化的替换服务可能不符合服务组合事务性要求，所以需要实现对待替换部位给出严格的事务性限制.

由于补偿是一种向前的、针对已成功执行的服务所采取的失效处理手段，所以本文在讨论事务属性限制时只需考虑与待替换服务的部分有数据依赖的服务.此外由于Or-Split与Or-Join所构成的分支结构是互斥的，在服务组合流程控制完成分支选择后实际上已经变为了一种Sequence结构，因此本文在分析待替换服务选择时只需对顺序结构和并行分支进行分析.具体分析如下：

1) 顺序结构.①如果待替换的服务变迁ST2前的服务处理变迁ST1所对应的服务/服务组合的事务属性是带有p/a的(p,pr/a,ar)，由事务属性定义可知ST1的执行效果是不能撤销，后续服务失效时不能被补偿，因此ST2必须保证执行成功，而只有r属性能保证服务肯定能够执行成功，所以ST2只能选择pr/ar和cr中任意一种属性的服务/服务组合.②如果ST1的事务属性是带有c的(c,cr)，由事务属性定义可知ST1的执行效果在后续服务失效时可以被补偿，因此ST2的事务属性不做限制.

2) 并行结构.①当待替换的服务变迁ST2和ST1构成并行分支时，如果ST1所对应的服务/服务组合的事务属性是p/a，由事务属性定义可知ST1的执行效果是不能撤销，ST2失效时不能被补偿，因此ST2必须保证执行成功，同时在ST1失效时必须能够被补偿，所以ST2只能选择cr属性的服务/服务组合.②如果ST1所对应的服务/服务组合的事务属性是pr/ar，由事务属性定义可知ST1肯定能执行成功，但不能被补偿，因此ST2必须保证执行成功，所以ST2只能选择pr/ar和cr中任意一种属性的服务/服务组合.③如果ST1所对应的服务/服务组合的事务属性是c，则ST1成功执行的效果可以撤销，但是不能保证一定成功，所以ST2必须能够在ST1失效时可以被补偿，ST2只能选择c和cr中任意一种属性的服务/服务组合.④如果ST1所对应的服务/服务组合的事务属性是cr，则ST1执行的保证一定成功，成功执行的效果可以撤销，所以ST2的事务属性不做限制.

具体的待替换服务限制如表1所示：

Table1TheTransactionAttributeLimitfortheServicetobeSubstituted

表1 待替换服务事务属性限制

对于待替换服务进行事务属性的限制，不仅能够维护原服务组合的事务不被破坏，而且通过替换合适的服务组件，可以进一步提升服务组合的事务机制的完备性，促进整个系统向着提升可信性的方向演化.

3 实验分析

本文提出了一种基于事务与补偿的服务替换方法，为了评估该方法的性能与正确性，本节将在服务组合仿真环境下与相关算法进行实验对比，通过判断服务替换触发后失效是否成功恢复为标准，在算法效率与一致性等方面来分析不同算法之间的性能差异.

3.1 实验准备

首先需要设置仿真对比实验用的场景，为了贴近实际运行环境中服务组合的构建情况与运行状态，本文采用一种人工生成与随机匹配的方式.采用这种方式的原因主要是：一方面由于服务对于用户是透明的(仅接口可见)，导致基于BPEL等规范的开源服务组合流程非常有限，难以大量收集来构造优质可靠的实验数据集；另一方面目前能够获得开源服务组合实例大多非常简单，组合包含的服务数量普遍在4个以下，不足以体现“一切皆服务”的大规模应用趋势.实验场景的生成具体而言，首先使用改进的Salama网络拓扑随机生成算法生成100个节点的服务组合运行的网络环境.服务数据采用人工生成的方式，搜索采集100个服务，每个服务含有服务名称、服务操作、参数接口、补偿服务等信息，并映射在事先随机生成的网络拓扑中，将随机拓扑中链路时延作为服务通信时延，节点时延作为服务处理时延.按照数据接口与语义匹配来随机组合服务，从而得到若干不同规模的服务组合.

目前通用的面向事务级的服务替换和恢复算法较少，因此本文在对比实验中加入了传统不支持事务级替换的Yu算法[2]，该算法将所有已完成服务视作一个事务，在服务失效时将尝试补偿全部已提交的事务.此外还选择面向长事务的失效恢复LHFR算法[9]，通过在仿真环境中向服务组合随机注入故障，触发服务替换与失效恢复的方式来与本文提出的算法比较分析.

3.2 实验结果与分析

为了验证本文提出的支持事务级的服务替换方法能够正确、有效地处理服务组合运行过程中出现的故障、失效等问题，首先需要对算法的正确性进行实验.通过对服务替换与失效处理后的服务状态一致性进行验证与分析，来证明基于事务级服务替换的失效处理方法能够正确地处理服务替换过程中服务一致性保障问题.

虽然事务的最小单位是一组在逻辑上属于一个单元的操作，但在实际服务组合系统中最小可操作粒度是组件服务或原子服务，事务可能对应单个的原子服务，也可能是多个组件服务构成的集合，因此通过服务运行信息可以获得所对应事务的运行状态信息.服务在生存周期内所处的状态包括initial，active，failed，completed，aborted，cancelled等，根据收发的报文信息以及内部逻辑运行情况，服务在不同状态间进行自动切换.在仿真服务节点上扩展加入服务状态的自动机，模拟服务所处运行状态的切换.通过随机故障注入，即随机选取服务组合中的某个部位，以不同的故障概率使服务进入failed状态来触发替换与失效恢复，根据具有的事务属性的服务所处的状态变化情况，观察该服务以及对应的事务能否通过补偿机制正确回滚至initial或者通过重启达到completed，以此来考察事务级服务替换及失效处理后服务一致性.为了有效测试服务失效处理的正确性，本实验中假设所有的服务均可以补偿.图5～6表示的是在节点数100的服务组合上，以不同的概率进行故障注入时服务一致性的评价结果.

Fig. 5 Number of transaction recovery图5 事务恢复的个数

图5分别记录了通过补偿(compensate，C)机制回滚恢复服务一致性的事务个数和通过重启(reboot，R)完成事务恢复的个数，图6记录了事务恢复的成功率.通过实验结果可以看出，在故障率较低的条件下，服务组合中的事务能够通过重启成功执行或者补偿来恢复到初始状态，呈现出较好的事务恢复成功率；当故障率增高时，事务恢复的成功率有所下降，但均能维持在85%以上较好的恢复成功率.有实验验证结果可以看出，本文提出的算法可以很好地维护事务服务状态，有效保障服务替换过程中服务一致性.

Fig. 6 Transaction recovery success rate图6 事务恢复的成功率

下面通过在仿真环境下测试服务组合运行时间，来说明事务级服务替换算法对于维持服务一致性，支撑服务组合系统稳定运行的关键作用.同样假设服务组合中所有的服务组件都可以补偿.选取5组不同规模的服务组合，在每组服务组合中选择相同的位置、以不同的故障注入率下进行随机故障注入，触发失效处理，记录服务组合的平均执行时间，其中包括服务正常时间以及服务失效时进行替换与补偿的时间.为体现算法的性能优势，将本文算法与传统Yu算法、LHFR算法进行对比，由于传统的Yu算法不支持事务范围识别，因此Yu算法将整个服务组合视作一个事务，在失效处理时对全部已提交的部分进行补偿.图7～9显示了在包含20，40，60，80，100服务组件的服务组合中，故障注入概率1%，2%，3%条件时，分别引入本文算法与Yu算法、LHFR算法后服务组合的平均执行时间.

Fig. 7 Average execution time of service composition (fault injection probability 1%)图7 服务组合的平均执行时间(故障注入概率1%)

Fig. 8 Average execution time of service composition (fault injection probability 2%)图8 服务组合的平均执行时间(故障注入概率2%)

Fig. 9 Average execution time of service composition (fault injection probability 3%)图9 服务组合的平均执行时间(故障注入概率3%)

由实验结果可以看出，随着服务规模的增大以及故障率的提高，服务运行时间呈现出增长的趋势，但总体而言支持事务级服务替换与失效处理方法在运行时间上要明显优于Yu算法，这是由于支持事务级的算法能够按照事务粒度划分，识别事务补偿的范围，降低失效恢复时间.其中本文算法在服务运行时间上要微弱地优于LHFR算法，这是由于失效恢复时，本文算法能够识别出与失效服务存在数据依赖，会导致一致性缺损的服务并补偿，有效控制影响范围，而并非像LHFR算法一样采用按照服务执行历史进行完全回滚的方法来进行失效处理，从而省去了维护庞大的服务执行历史图的时间，降低了服务组合的平均执行时间.

下面对服务替换与失效处理过程中的人工介入率进行考察，来分析算法性能.本实验中假设所有的服务中有不同的概率是关键性服务，是不可以补偿的，一旦失效恢复失败就会终止算法并请求人工介入处理.该实验设置为在一段时间内重复运行服务组合，一旦失效自动恢复失败触发人工介入，则记录下来并重启整个服务组合继续运行.人工介入率就是记录服务组合在失效发生后不能自动进行替换与补偿处理，需要人工介入的次数与总运行次数的比率.越低则说明算法自动化程度越高，失效处理的性能越好.假设在包含60个服务组件的服务组合中有10%的概率是不可补偿的，图10显示了故障注入概率分别为1%，2%，3%时，分别引入本文算法与Yu算法、LHFR算法后服务组合的人工介入率.

Fig. 10 Manual intervention rate图10 人工介入率

从实验结果可以看出，在介入率指标上本文提出的算法明显较好，这是由于本文算法引入替换属性限制，通过事务级服务替换实现了面向一致性维持的服务组合演化，提升服务组合系统的可信性保障能力，使得服务的自动失效恢复的成功率有了提高，减少了因无法补偿而需要人工介入进行干预的概率，从而缩短失效恢复所需时间，提升整个服务组合系统的MTTF(mean time to failure).同时也可以看出关键性服务越多，说明服务事务性越差，在发生失效触发替换时难以自动进行补偿处理来维护一致性.

由于服务组合是动态绑定，且实际环境中服务运行情况十分复杂，测试服务替换算法需要服务监控、服务选择与匹配、故障注入等技术的协同合作，显然超出本文研究范围.本文实验用的仿真环境中虽然忽略了服务组合在实际专业应用背景下的业务流程与需求，但足以验证算法的正确性与有效性.

4 相关工作分析

服务替换是在服务发现与服务匹配的基础上的，选择替换用的服务势必需要进行服务匹配，以满足用户对于替换服务功能属性方面的需求，因此分析服务发现与匹配相关研究十分有必要.Zhou等人[10]将面向服务计算环境下的服务划分为EP(effect-providing)服务和DP(data-providing)服务，通过建立域本体模型来对DP服务进行分类，并通过计算服务向量距离来实现服务聚类，以便用户发现与选择匹配.但是服务替换并不单纯等同于服务匹配，因为服务是一个动态绑定运行的过程，服务组合中各组件之间通过消息报文实现业务通信与数据交换，为保障服务组合的整体可信性，服务替换过程需要综合考虑组合上下文、服务接口兼容等多方面的因素.

对此，学术界和工业界开展了大量的研究，而综合来看，服务替换的方法大致可以分为面向功能的服务替换和面向QoS保障的服务替换.在面向功能的服务替换方面，文献[11]对服务控制流进行建模来描述服务间复杂的异步通信，从服务行为的角度来对服务替换的正确性进行研究，并给出几种死锁状态的处理方法，从而保证服务替换过程中每个参与组合的服务都是正确，解决服务组合中交互的复杂性所带来服务行为分析难题.服务行为兼容性对服务替换的成功也是非常重要的，Jin等人[12]提出基于服务上下文的行为替换度分析方法，使用Petri网对服务进行建模，通过分析待替换服务的变迁序列来生成局部服务行为限制条件，并选择符合条件的服务来进行替换.文献[13]则是通过对服务工作流进行建模，提出一种服务组合上下文信息的采集方法，找出服务组件的K层和K域上下文邻居，并根据服务接口的依赖关系，基于上下文编辑距离匹配来进行服务替换分析，提高替换服务的召回率和准确率.文献[14]则是使用Pi演算的方法来对移动云计算系统下的服务进行建模分析，通过分析服务兼容性以及服务行为模拟能力来选择合适的替换服务，有效避免分析过程空间爆炸的问题.而在面向QoS保障的服务替换上，文献[15]提出一种基于云模型的服务动态替换方法，通过计算由于动态变化的网络环境导致服务组合QoS不确定度来定位服务替换位置，重配置服务来保证满足用户QoS需求，从而有效保障服务可信性.文献[16]提出了一个通用服务模型并通过QoS相等度的概念来对服务间的语义相等关系进行描述，在此基础上提出语义替换机制来实现异构环境下服务替换，有效维持服务稳定运行.Santhanam等人[17]则是通过建立偏好度网络来描述由非功能的QoS属性所蕴含的用户偏好，从而为优质替换服务的识别与选择来提供指导，维护服务组合的整体功能表现.在此基础上，文献[18]通过对服务组件进行迭代替换，实现服务的动态自适应，从而应对在功能性需求不变时，用户对于安全性、开销等非功能QoS需求的动态变化.

以上这些服务替换方法提出了一些有效的服务替换策略，一定程度地保障服务运行，但这些方法仍然存在着种种问题，其中最为严重的是替换后的服务正确率低.究其原因是现有方法大多关注替代服务的功能是否近似、接口是否兼容等，忽略了动态运行的服务与生俱来的事务属性，尤其是一致性.在服务发生替换后未及时处理服务一致性缺损问题，内存驻留数据并未被释放，从而导致服务替换后，服务组合的故障与失效不仅没有得到抑制，反而出现扩散的趋势，导致服务的可信性持续下降.由此可见，引入事务机制来分析服务组合中的失效处理和替换机制显得尤为重要.

随着虚拟化技术与分布式计算环境的发展与普及，大多数服务通常需要保持长期运行不稳定的分布式虚拟化环境中，是一种典型的长事务(long running transaction)，因此传统事务机制先提交再执行、“非全则无”的方式存在系统效率低下、恢复困难等问题，势必导致服务无法持续性的提供服务，反而加剧服务可信性恶化的趋势，因此需要将传统非层次的事务模型扩展为层次性的高级事务模型，其中比较有代表性的包括Sagas事务模型[8]、ACTA事务模型[19]等.

而在事务处理协议方面，Web服务协调事务(Web services-coordinationtransaction，WS-CT)和业务事务协议(business transaction protocol，BTP)是现有Web服务事务协议的2个主要协议.WS-CT包含WS-Coordination，WS-Atomic Transac-tion，WS-Business Activity这3个规范协议的规范集，可广泛用于处理短期存在的原子事务以及长期运行的业务活动；BTP使用2阶段提交协议，通过参数化2阶段协议，部分参与者可以先提交而其余终止的事务，但是BTP协议并非是针对服务事务协调而专门开发的协议.Yao等人[20]为了使BTP协议能够支持长事务，对其提出了一些改进并设计实现了一个事务处理系统，通过服务中间商来实现长事务的协调处理.这些对BTP协议中的事务改进并没有提到补偿的概念，WS-CT协议业务事务中定义了相关的补偿机制，但其对在分布式环境下的恢复方法却言之甚少.

此外，还有大量文献对服务事务性以及补偿机制展开研究.Zamani等人[21]针对无状态的服务与有状态的事务之间的差异与联系进行了阐述，通过分析SOA下异构的事务性需求，建立了一个包含事务补偿能力的、面向服务的事务处理模型，但是该模型还尚不完整，缺少对复杂业务流程下服务补偿机制的设计与实现.印莹等人[6]充分考虑服务间的多关系与事务特性，提出了一种主动伺机的事务级服务替换方法，但是该算法是由QoS收益模型驱动并分析事务补偿代价，后续替换服务仅从QoS保障的角度进行选择，没有考虑替换服务的事务属性对于服务组合系统的影响.

综合来看，现有研究可以在一定程度上保证服务事务的一致性，在服务在发生故障情况下，能够以动态演化的方式保障服务可信性，但目前服务事务处理还存在以下问题：

1) 算法扩展性差，目前支持事务级替换方法与补偿机制大多是针对具体应用而开发的专用算法与机制，缺少针对算法扩展性与通用性的考虑，一旦脱离针对的环境，这些方法与机制难以适用.

2) 事务粒度设置，在对Web服务进行设计时我们很难确定一个事务被设计成多大是最合适的.小事务可以减轻在补偿机制上所付出的代价，提高效率；而大事务在设计上比较简单，可以减少业务过程开发费用.

3) 替换服务的事务性，大部分服务事务及失效处理的研究集中在服务组合事务粒度与事务范围识别上，很少有考虑替换服务事务性，缺少从事务性限制的角度出发来选择替换服务的.一旦选择了事务性不合适的服务来进行替换，导致服务组合系统的事务粒度被破坏，难以维持后续运行上的一致性，进而导致失效处理后的可信性降低.

本文针对以上不足进行了一定程度的补充，充分考虑了服务的事务属性，从服务组件间的数据流的角度切入，分析事务粒度与事务范围.通过选择具有合适事务属性的替换服务，提升服务组合的可信性保障能力是本文解决的关键问题.

5 结 论

本文针对目前的服务组合替换算法无法很好地应对替换过程中不一致的问题，导致服务替换失败的情况，提出了一种支持事务级属性的层次化服务组合模型，使用扩展层次化有色网并结合服务事务属性来描述服务组合中复杂的数据流关系，通过数据依赖关系来有效识别服务组合事务范围，进而在服务替换时针对同一事务的服务组件进行补偿，并充分考虑候选替换服务选择的事务属性限制，维护服务组合的稳定运行.仿真实验结果验证了本文方法的正确性和有效性.

在下一步工作中，尝试将事务级的服务替换与服务补偿方法与服务状态监控结合，建立一套完整的服务运行时动态演化原型系统，同时通过对服务运行状态和运行历史模式进行挖掘，从而能够实现对服务失效的提前预警，进一步提高服务动态自适应以及可信性保障能力.

[1]Wang Huiqiang, Zou Shichen, Lin Junyu, et al. A dependable service path searching method in distributed virtualized environment using adaptive bonus-penalty micro-canonical annealing[C] //Proc of the 2nd IEEE Int Conf on Cyber Security and Cloud Computing (CSCloud). Piscataway, NJ: IEEE, 2015: 530-539

[2]Yu Tao, Lin K. Adaptive algorithms for finding replacement services in autonomic distributed business processes[C] // Proc of IEEE ISADS 2005. Piscataway, NJ: IEEE, 2005: 427-434

[3]Yu Tao, Zhang Yue, Lin K. Efficient algorithms for Web services selection with end-to-end QoS constraints[J]. ACM Trans on the Web, 2007, 1(1): No.6

[4]Du Yuyue, Xue Jie, Li Yancheng. Substitution and analysis of service composition based on service clusters[J]. Acta Electronica Sinica, 2014, 42(11): 2231-2238 (in Chinese)(杜玉越, 薛洁, 李彦成. 基于服务簇的服务组合替换与分析[J]. 电子学报, 2014, 42(11): 2231-2238)

[5]Du Yuyue, Gai Junjing, Zhou Mengchu. A Web service substitution method based on service cluster nets[J/OL]. Enterprise Information Systems. [2016-12-01]. http://dx.doi.org/10.1080/17517575.2016.1172347

[6]Yin Ying, Zhang Bin, Zhang Xizhe. An active and opportunistic service replacement algorithm orienting transactional composite service dynamic adaptation[J]. Chinese Journal of Computers, 2010, 33(11): 2147-2162 (in Chinese)(印莹, 张斌, 张锡哲. 面向组合服务动态自适应的事务级主动伺机服务替换算法[J]. 计算机学报, 2010, 33(11): 2147-2162)

[7]El Hadad J, Manouvrier M, Rukoz M. TQoS: Transactional and QoS-aware selection algorithm for automatic Web service composition[J]. IEEE Trans on Services Computing, 2010, 3(1): 73-85

[8]Garcia-Molina H, Salem K. Saga[M]. New York: ACM, 1987

[9]Ren Yi, Guan Jianbo, Ao Qi, et al. LHFR: A hierarchical failure recovery algorithm for long running transaction[J]. Journal of Computer Research and Development, 2010, 47(10): 1805-1811 (in Chinese)(任怡, 管剑波, 敖琦, 等. LHFR: 面向长事务的层次式失效恢复算法[J]. 计算机研究与发展, 2010, 47(10): 1805-1811)

[10]Zhou Zhangbing, Sellami M, Gaaloul W, et al. Data providing services clustering and management for facilitating service discovery and replacement[J]. IEEE Trans on Automation Science and Engineering, 2013, 10(4): 1131-1146

[11]Parnjai M C S J. Behavioral service substitution: Analysis and synthesis[D]. Berlin: Humboldt-Universität zu Berlin, 2013

[12]Jin Jun, Hu Jingjing, Cao Yuanda, et al. Behavioral compatibility analysis for context-independent service substitution[C] //Proc of the 7th China Grid Annual Conf. Piscataway, NJ: IEEE, 2012: 121-127

[13]Chan N N, Gaaloul W, Tata S. Composition context matching for Web service recommendation[C] //Proc of IEEE Int Conf on Services Computing (SCC). Piscataway, NJ: IEEE, 2011: 624-631

[14]Wang Peng, Yang Ling, Li Guowen, et al. A novel substitution judgment method for mobile cloud computing application system components[C] //Proc of the 6th IEEE Int Conf on Cloud Computing Technology and Science (CloudCom). Piscataway, NJ: IEEE, 2014: 911-916

[15]Gong Yan, Huang Lin, Han Ke. Service dynamic substitution approach based on cloud model[C] // Proc of the 1st Int Conf on Advanced Data and Information Engineering (DaEng-2013). Berlin: Springer, 2014: 563-570

[16]Ibrahim N, Mou⊇l F L, Frénot S. Semantic service substitution in pervasive environments[J]. International Journal of Services, Economics and Management, 2014, 6(4): 283-309

[17]Santhanam G R, Basu S, Honavar V. Web service substitution based on preferences over non-functional attributes[C] //Proc of IEEE Int Conf on Services Computing (SCC). Piscataway, NJ: IEEE, 2009: 210-217

[18]Santhanam G R, Basu S, Honavar V. Preference based service adaptation using service substitution[C] //Proc of the 2013 IEEE/WIC/ACM Int Joint Conf on Web Intelligence (WI) and Intelligent Agent Technologies (IAT)-Volume 01. Piscataway, NJ: IEEE, 2013: 487-493

[19]Chrysanthis P K, Ramamritham K. Synthesis of extended transaction models using ACTA[J]. ACM Trans on Database Systems, 1994, 19(3): 450-491

[20]Yao Zhilin, Han Lu, Zhang Jinting, et al. Long term Web service oriented transaction handling improvement of BTP protocol[M] //Frontier and Future Development of Information Technology in Medicine and Education. Dordrecht, Netherlands: Springer Netherlands, 2014: 889-898

[21]Zamani A S, Gupta P K. SOA-based distributed system in online transaction processing[J]. Journal of Information Sciences and Computing Technologies, 2015, 4(1): 258-264