基于服务的架构(service-oriented architecture, 简称SOA)是通过部署在不同网络节点上的服务(使用统一的接口)来实现, 其可为自包含(self-contained)、松耦合(loose coupling)的分布式系统发展提供技术指导[1].随着SOA技术的不断成熟, 很多企业把他们的全部或部分业务交由外部服务(external service)实现, 从而降低开发周期与成本.因此, 越来越多的应用程序(即组合服务, composite service)由外部服务(即组件服务, component service)采用服务组合技术组合而成[2].
比如:为了便于组织或者开发人员快速而轻松地在云环境中创建、部署和管理应用程序, 目前很多公司推出了平台即服务(platform as a service, 简称PaaS)产品, 比如, IBM公司的基于Cloud Foundry的开放云应用平台Bluemix, http://www.ibm.com/cloud-computing/cn/zh/platform/?lnk=bucl#infrastructure.通过PaaS, 组织或开发人员不仅可以把自身的API(application program interface)即组件服务发布到云环境中以供其他组织使用, 而且可以组合平台上已有的API, 以此得到增值服务, 即组合服务.因此, 通过PaaS组合组件服务可在很大程度上缩短应用程序的开发周期.但是因为PaaS上已有的组件服务由平台公司或者第三方提供, 且其执行环境为尽力而为的网络, 即不可靠的Internet, 所以由这些组件服务组合而成的组合服务在执行过程中就有可能因为网络阻塞、组件服务所在服务器宕机等问题而出现执行故障(failure).因此, 在不可靠的互联网环境中如何保证组合服务的可靠执行[3], 是一个亟待解决的问题.
软件可靠性保障技术主要有4种:故障预防(fault prevention)[4]、故障排除(fault removal)[5]、故障预测(fault forecasting)[6]、容错(fault tolerance)[7].组成组合服务的组件服务一般属于第三方, 因此很难获得其内部组成结构与代码实现, 那么试图采用故障预防和故障排除技术构造无故障的组合服务是不可行的.又因为组合服务的复杂执行环境以及组件服务的彼此独立和自由演化, 组合服务执行阶段的故障是很难预测的, 所以通过故障预测技术保障组合服务的执行也很困难.而容错技术是能在系统或部分组件出现故障时也能保障系统继续正确运行并完成其设计功能的一种技术, 同时, 容错技术通常在产生故障到最终导致系统失败(failure)的时间间隔中被采用, 目的是在已经产生系统故障的情况下避免系统失败的出现(https://en.wikipedia.org/wiki/Fault_tolerance).因此, 容错技术成为目前保证组合服务可靠执行的最有效方法.
组合服务的容错技术主要有两类:异常处理(exception handling)和事务处理(transaction)[8].前者为前向故障恢复技术(forward fault recovery), 其试图修复故障, 从而使组合服务继续执行; 后者为后向故障恢复技术(backward fault recovery), 其在故障不可被修复的情况下, 保证组合服务终止在一致状态[9], 多用于处理事务型组合服务出现的故障.事务型组合服务为一类特殊类型组合服务, 其本身或者部分片段具有原子特性, 即:要么全部执行, 要么什么也不执行.对于事务型组合服务, 当具有原子特性的组件服务出现故障时, 必须停止组合服务的继续执行, 首先回溯到一个可进行补偿的状态, 然后从此状态开始为具有原子特性的组合服务或者片段重新选择组件服务, 最后恢复组合服务地执行, 即, 需要采用事务处理容错技术.
异常处理和事务处理已被内置到BPEL(Web services business process execution language)中, 但构建BPEL容错逻辑是一件费时且易出错的工作, 其原因有两个:首先, BPEL的容错逻辑实现被嵌入到业务逻辑之中(即, 容错逻辑仅在低层的语法层实现), 使得容错逻辑的开发、维护和更新非常困难; 其次, 只有正确的故障处理逻辑才可以触发补偿(compensation)的执行, 换句话说, 组合服务能够终止在一致状态的工作留给了组合服务开发者.因此, 开发独立于业务逻辑之外的、需要补偿操作时能终止在一致状态的容错逻辑, 是当前容错方法需要解决的一个挑战.
除了确保组合服务正确执行之外, 容错技术也需确保不违反服务使用者和服务提供者之间的服务级别协议(service level agreement, 简称SLA).SLA的提出, 是用于确保服务质量(quality of service, 简称QoS)[10], 其是服务提供者和服务使用者之间正式协商的结果, 也是存在于双方之间的合约(或为合约的一部分), 是针对服务响应时间、可用性、吞吐率、优先权、责任和义务等方面达成的协议[11].SLA是一种常用的指定精确交付条件(包括功能和非功能属性)的方法, 通过其可确定哪一个服务必须或应交付.然而在实际应用过程中, SLA仅指定服务使用者与提供者之间的高层接口(top-level interface)[12], 即SLA监控工作也留给了组合服务开发者.因此, 如何在组合服务的执行过程中监控SLA, 成为当前容错方法需要解决的另外一个挑战.
为了克服上述挑战, 本文提出了一种SLA感知的组合服务容错方法(SLA-Aware fault-tolerant approach for service composition, 简称SLAFT).SLAFT容错逻辑与组合服务执行逻辑相互分离, 只有在产生故障的时候才会被触发; SLAFT采用有限状态机(finite-state machine, 简称FSM)建模和监控组合服务执行状态, 并确保产生故障时能停留在一个一致的状态, 方便进行下一步的补偿操作; 采用监控自动机(monitoring automata, 简称MA)监控组合服务执行过程中的SLA属性, 用于确保服务提供者与服务使用者之间商定的SLA; 进行补偿操作时, 采用改进的差分进化算法(differential evolution algorithm, 简称DE)快速寻找最优恢复规划.
为了验证本文所提方法SLAFT的有效性, 基于两个真实数据集:QWS(http://www.uoguelph.ca/~qmahmoud/qws/)和WS-DREAM的QoSDataset2(http://www.wsdream.net/), 我们进行了仿真实验:首先, 采用SLAFT与其他两种方法进行了实验对比, 结果表明, SLAFT方法在故障处理时间与在组合最优度上均优于对比方法; 然后, 对影响仿真结果的参数(故障规模)进行了分析, 实验结果验证了其对参数变化适应较好.
本文第1节给出本文的研究场景.第2节首先介绍SLAFT框架, 然后详细描述框架中包含的主要模块(即服务状态监控、SLA监控、恢复规划计算)的实现过程.第3节给出恢复规划计算中采用的改进差分进化算法的具体实现过程.第4节给出仿真实验, 包括实验建立、实验对比、参数分析.第5节介绍相关工作.最后一节对全文进行总结, 并展望下一步研究工作.
1 研究场景首先给出本文一个研究场景:假设用户通过PaaS开发基于位置的服务推荐系统(service recommendation system, 简称为SRS)时, 需要采用位置定位服务定位用户的位置, 进而为其推荐附近的服务(比如餐饮).由于位置定位服务是一项较难开发的服务, 且有现成的服务可供调用(如百度地图、谷歌地图等), 所以用户可直接通过PaaS集成位置定位服务, 以此来缩短SRS的开发周期.假设位置定位服务需要组合调用地图服务Map(用户所在位置的区域地图调取)和定位服务Loc(用于计算用户所在位置, 并将其精准标识在地图上).因为不同公司所用的地图不同, 且所采用的定位算法也不同, 所以在调用到一个公司的地图服务后, 必须调用其定位服务.也就是说, 地图服务和定位服务具有原子特性, 它们要么全部执行, 要么什么也不执行.假设基于组合服务的服务推荐系统的工作流如图 1所示, 本流程实现语言采用BPEL.
BPEL[13]是实现组合现有Web服务的一个事实上的工业标准, 其通过指定一个预先定义的可执行工作流来实现组合过程.通过BPEL的基本活动〈receive〉, 〈invoke〉和〈reply〉分别实现接收消息、执行组件服务和返回执行结果, 从一组消息中等待一个消息的出现, 通过〈pick〉基本活动实现.组合服务的控制流通过〈sequence〉, 〈while〉和〈if〉活动来分别实现顺序、循环和条件结构, 还可以通过〈flow〉实现并行结构.〈scope〉可以包含其他活动, 且能被关联到一个补偿句柄(compensation handler)中, 该句柄指定了补偿操作需要执行的活动区间.
图 1中, 当收到用户的请求Rec时, 启用一个〈pick〉活动(采用符号
现在, 让我们考虑这样的场景:当收到用户的请求时, 首先得到了Ser1的响应, 工作流就对此进行了调用(即需要首先调用组件服务Map1, 然后调用组件服务Loc1).但在成功调用Map1后, 发现Loc1不可用.经典的容错策略是点恢复策略(point recovery strategy), 即:对Loc1进行重试, 或者将其替换为实现同样功能的服务[14].但是, 本文主要考虑如下场景:如果Loc1确实不可用(重试策略失效), 且不存在替换服务时需要采用的容错策略.出现此类故障时就需要采用另外一种重要的容错策略, 即流恢复策略(workflow recovery strategy).其需要指定如何对现有工作流进行补偿(compensation), 并回溯到以前的状态, 且能找到一个替代执行路径, 确保组合服务的继续执行.一个好的容错策略还需要保证不违反服务使用者与服务提供者事先商定的SLA.所以, 针对流恢复策略需要解决如下问题:(1)如何对组合服务的执行状态进行建模; (2)如何在容错的过程中不违反SLA; (3)如何寻找最优替代执行路径.
2 SLA感知的事务型组合服务容错方法针对上一节的问题, 我们提出了SLA感知的事务型组合服务容错方法SLAFT.SLAFT是在正常的组合服务执行逻辑之外加入监控逻辑, 同时监控组合服务的执行状态和执行过程中的SLA属性值.当执行状态正常和不出现SLA违反时, 监控逻辑只是起到监控作用; 一旦出现错误状态和SLA违反, 就触发相应的补偿操作.SLAFT方法框架如图 2所示, 其主要包含3个模块:模块1为服务状态监控模块, 其采用有限状态机建模组合服务的执行状态, 并对执行过程中的状态进行监控, 一旦进入故障状态, 将触发模块3恢复规划计算的执行(详细分析见第2.1节); 模块2为SLA监控, 其采用监控自动机对执行过程中的SLA属性进行监控, 如果出现SLA违反, 也将触发模块3的执行(详细分析见第2.2节); 模块3为恢复规划计算, 其针对出现的故障状态和SLA属性违反, 采用改进差分进化算法计算恢复规划, 然后交由组合服务执行引擎执行, 使得组合服务能继续执行和不出现SLA违反(详细分析见第2.3节).
2.1 服务状态监控
组合服务的正常执行是从起始状态开始, 经过若干个中间状态, 最终到达结束状态.但也可能因为某些原因, 使得组合服务停留在某个中间状态无法继续执行.为了感知这些状态, 保证组合服务的正常执行, 必须对组合服务的执行状态进行监控.本文采用有限状态机建模组合服务执行状态, 并对其执行过程中的状态进行监控.本节首先给出组合服务的定义, 然后再给出有限状态机的定义, 最后叙述如何采用有限状态机建模和监控组合服务状态.
定义 1(组合服务).组合服务CS是一个三元组(Var, V0, P0), 其中, Var为一个有限变量集合, V0为集合中每个变量在其值域内的初始赋值, P0为初始赋值后组合服务工作流程.
定义1中, Var表示组合服务包含的抽象组件服务集合, 而V0是对各个抽象组件服务的初始赋值, P0为组件服务的执行顺序(如并行、串行、选择等).
定义2(有限状态机). FSM是一个五元组(Σ, S, s0, d, φ), 其中, Σ是输入符号的非空有限集合; S是非空的有限状态集合; s0是S中的一个特殊状态, 起始状态; φ是S中另外一个特殊状态, 结束状态; δ是一个从空间S×Σ到S的映射函数, 即δ:S×Σ→S.
本文采用FSM建模含有n个组件服务的组合服务的执行过程, 每个状态s的形式为(V, P).s0=({Var1→φ, Var2→φ, …}, P0), s1=({Var1→Ser1φ, Var2→φ, …}, P1), …, f=({Var1→Ser1, …, Varn→Sern, …}, Pn).其中, Vari→φ代表Vari没有被定义, Ser1, …, Sern∈Σ.状态s代表的实际意义是:随着组合服务的执行, 对抽象组件服务的逐步实例化.P为组合服务的执行流程, 可能随着执行过程有所改变, 也可能一直保持不变, 这跟抽象组件服务的具体实例化过程相关.
本文中, 我们假设FSM中存在一个错误活动(输入符号)err(err∈Σ), 其是指组合服务执行过程中遇到的一些阻碍其正常执行的问题, 比如组件服务不可用、SLA违反等.且错误活动err的输入能使得处在任何状态的FSM转换到错误状态serr(serr∈Σ).也就是说, ∀s∈S|{serr}, (s, err, serr)∈δ.
对于一个FSM F=(Σ, S, s0, δ, f), 我们采用
对于场景SRS的FSM F(SRS)如图 3所示(点划线代表的语义将在第2.3节中解释).场景SRS的BPEL活动语义是基于文献[15], 比如:对于状态s9的条件活动, 当条件为真(拥有用户历史信息)时, 活动List2被执行; 而当为假(不拥有用户历史信息)时, 活动List1被执行.也就是说, 从状态s9拥有两个可能的转移状态s10和s11.但条件语句要么为真要么为假, 一旦其值确定, 只能转移到一个状态.与条件活动类似,〈pick〉活动也拥有两个可能转移状态, 但真正执行过程中, 也只能转移到其中一个状态.图 3中, 每个状态均可以转移到状态err, 但为了增加可读性, 只画出了状态s7的错误转移状态.
如果一个状态具有备选的执行方案, 称其为迁移状态(migration state), 也就是说, 其可从当前的执行迁移到另外一个执行.迁移状态包括那些可以调用〈flow〉活动、〈pick〉活动或者非幂等性(non-idempotent)服务调用(如果对于任何相同输入参数的调用均可得到相同的结果, 则称这个服务调用是幂等的; 反之为非幂等性服务调用)的状态.在图 3中, 有效的从状态s7出发的迁移状态为s5, s3和s2.
BPEL语言自身提供补偿机制(compensation mechanism), 其采用特定的编程方式来撤销已经完成活动产生的结果.但该补偿机制具有局限性, 即, 很难保证补偿过后系统所在的状态能够满足系统的功能性要求, 之所以产生这种结果, 是因为该机制不能确定补偿后软件系统所处的状态.为了克服这个局限性, 我们分析了BPEL的每个活动可以产生的两种变化, 即内部变化(internal change)和外部变化(external change):内部变化使得系统从状态s改变到状态s', 而外部变化改变组件服务的状态.
为了撤销内部变化, 必须把一个活动执行前的状态值存储下来, 在恢复的过程中, 通过把当前的状态值s'恢复成存储的状态s, 起到了撤销内部变化的作用.外部变化仅可通过BPEL的通信活动(communication activity)来实现, 比如〈receive〉, 〈invoke〉和〈reply〉.因为通信活动是唯一能够与组件服务通信的活动, 所以为了撤销外部变化, 用户需要为每个通信活动a指定一个补偿句柄.其指定一个操作abak, 通过执行abak可以撤销活动a产生的结果, 回到a执行前的状态.例如:如图 4所示, 是为图 3中操作Loc1指定的补偿句柄, 其通过调用操作CL1来取消调用定位服务Loc1后所产生的结果, 以此来补偿因调用操作Loc1所产生的外部变化.
对于每个活动a, 都有一个相应的后向行动(backward action)abak, 其通过存储的状态值来逆转内部变化和基于补偿句柄来逆转外部变化, 以此来返回到执行a之前的状态.一个F(SRS)后向行动的例子为
为了不违反服务提供者和服务使用者事先商定的SLA, 必须对组合服务执行过程中的SLA属性进行监控.我们采用确定性有限自动机(deterministic finite automata)监控SLA属性, 本文称其为监控自动机.首先给出监控自动机的定义如下:
定义3(监控自动机).监控自动机MA为五元组(Q, Q0, Σ, δ, F), 其中, Q为状态集合, Q0⊆Q为初始状态集合, Σ为通用活动集合, δ:Q×Σ×Q为转换关系, F⊆Q为可接受状态集合.
我们采用符号Σ*表示一组有限活动序列.给定监控自动机A, 序列活动a1, a2, …, an∈Σ*是被A接受的, 如果在A中存在一条路径
给定一个SLA属性PSLA, A(PSLA)代表其的监控自动机.一个执行是被A(PSLA)接受的, 如果其违反了设定的SLA属性.也就是说, 组合服务的执行过程中, 如果出现违反了设定的SLA属性, 就会触发其的相应监控自动机.如果不违反, 就不会触发.例如:给定一个属性P1“在SRS中, 组件服务的不可用绝不会发生”, 当出现组件服务不可用时, 就会触发错误活动err.给定一系列SLA属性值, 我们定义一个组合服务CS的监控自动机为MCS= 〈A(P1), …, A(PN)〉, 其中, Pi(1≤i≤N)为SLA属性.给定L(CS)中的一个执行π, 如果π被所有的自动机A拒绝, 那么π满足MCS; 其他情况下, π违反MCS.也就是说, 当执行过程不违反SLA时, MA只起到监控作用; 而违反SLA时, MA被触发, 该信息将会被组合服务执行引擎和恢复规划计算模块收到, 将会触发相应的恢复规划计算, 以确保不产生违反SLA的执行结果.
2.3 恢复规划计算图 3中, 采用点划线(-·→)表示一次从状态s1到状态s7的执行.在状态s5, 如果服务Loc1能被成功调用, 组合服务状态将转移到s7.而如果此时因为网络或服务器故障, Loc1不能被成功调用, 组合服务将进入错误状态err, 服务状态监控模块应立刻发现此类阻碍组合服务正常执行的故障.为了从故障中恢复, 需要计算恢复规划.该恢复规划是一个指导方针, 其可使组合服务从当前错误状态补偿到一个迁移状态(采用后向行动), 然后选择一个可以到达结束状态的替代路径(采用前向行动), 以此来确保组合服务的成功执行.图 3中, 场景SRS的一个可能的恢复规划rSRS使用划线(--→)表示, 其首先采用后向行动从err状态补偿到一个转移状态s2, 然后采用前向行动从状态s2到状态s12, 即, 组合服务成功执行完成.
定义 4(恢复规划).恢复规划r是一个执行
恢复规划r的前缀为r的从状态serr开始, 到状态si(i≤n)结束的一个执行片段, 其后缀为r的从状态si开始, 至结束状态φ结束的一个执行片段.
针对场景SRS, 在转移状态s2, 根据恢复规划rSRS, 组合服务需要继续转换到状态s4.但是, 根据〈pick〉活动的语义, 其应该选择执行最先做出响应的服务.如果这样, 就违反了按照恢复规划执行组合服务的语义.因此, 根据BPEL扩展属性特征, 为〈pick〉活动扩展一个isControllable属性[16], 其允许用户通过恢复模块来指定可控制的活动.在我们的场景中, 如图 3所示, 对于状态s2, 通过设置其的isControllable属性值为真(如图 4所示), 使得〈pick〉活动选择的转换的状态可控制, 因此, 可按照恢复规划执行组合服务.除了〈pick〉活动, 在某些情况下, 用户还需要指定〈flow〉和〈if〉活动的可控性.如果〈flow〉活动被指定为可控, 那么执行引擎将忽略并发语义, 根据恢复规划按照顺序语义执行组合服务.如果〈if〉活动被指定为可控, 那么执行引擎将忽略判断语句的值, 直接按照恢复规划指定的分支执行组合服务.假如在状态s2的〈flow〉活动的isControllable属性设置为真, 而在状态s9的〈if〉活动的isControllable属性设置为假, 那么, 恢复过程将持续到状态s9, 因为〈if〉活动不可控, 恢复过程结束, 执行引擎将按照正常的执行语义执行余下的组件服务, 即, 〈if〉活动将转移到状态s10或状态s11, 取决于是否有用户历史信息.
我们称一个执行的最大可控部分为可控前缀, 对于SRS, 可控前缀从状态serr开始到状态s9结束.对于状态s9本身而言, 其为不可控的状态, 但这个状态结束了可控前缀.同样的, 我们称一个从不可控的状态开始的执行部分为不可控后缀, 尽管不可控后缀(即从状态s9到状态s11)不是恢复过程的一部分, 但其提供了一个从不可控状态开始的执行参考.在计算恢复规划过程中, 不可控后缀可以有助于找到一个以不可控状态结束的恢复规划和一个从此不可控状态开始的最好的执行后缀.因此, 在恢复过程结束和正常执行逻辑开始时, 组合服务具有较高的机会可以同时符合功能性和非功能性方面的需求.
总的来说, 恢复规划的计算可分为3个部分:(1)首先需要从状态serr开始, 补偿到一个迁移状态; (2)从此迁移状态开始, 计算一段到不可控状态的最优路径(不包括出故障的路径); (3)计算最优不可控后缀.第1部分和第2部分得到恢复规划的可控前缀, 第3部分得到不可控后缀.第1部分计算比较简单, 只需要恢复到迁移状态.恢复过程需要撤销从状态serr到迁移状态产生的内部变化和外部变化.内部变化的撤销只需要把现有状态恢复为保存的状态.对于SRS, 如图 3所示, 就是把当前状态serr恢复到状态s2.外部变化需要通过执行补偿句柄指定的操作abak, 以此撤销已执行活动产生的结果.对于SRS, 需要执行操作CL1, CM1和t来撤销已执行活动Loc1, Map1和Ser1产生的结果.第2部分和第3部分计算过程较类似, 均为组合服务片段的抽象组件服务重新寻找最优组件服务的过程.第2部分与第3部分的唯一区别就是第2部分的计算过程中需要去除出故障的路径分支.
为组合服务片段重新选择最优组件服务与对整个组合服务选择最优组件服务的过程类似, 均需要对所有的候选组件服务根据其SLA属性进行组合, 在满足SLA约束的前提下, 寻找最优组合结果.比如:对于顺序结构的组合请求, 如果其包含m个抽象组件、每个抽象组件有l个候选组件服务, 那么将会有lm种组合方法, 随着抽象组件个数的增加, 组合方法的数目会呈现指数级别增长.对仅存在一条单一路径结构尚且如此, 对存在多条路径的选择结构, 其组合方法会更多.所以, 随着抽象组件数目的增加, 采用穷举搜索算法将不可行.文献[17]分析了对组合服务寻找最优组件服务的过程可以建模为多维多选择背包问题(multichoice multidimensional knapsack problem, 简称MMKP), 且文献[18]已证明MMKP为NP-hard问题, 所以只能采用一些方法寻找近似最优解.
针对为组合服务寻找最优组件服务的问题, 已有许多学者采用不同的算法予以求解.有的学者采用穷举搜索算法, 但其仅适用抽象组件数目较少的组合服务.因为随着抽象组件数目的增加, 其组合数目呈现指数级别增长, 采用穷举搜索算法求解的时间将很长, 或者根本无法求解.有的学者采用粒子群算法[19]或者遗传算法[16], 但这两类算法的参数较多, 且不同的参数设置将产生不同的求解结果, 即结果的优劣在很大程度上依赖于参数设置.近年来, 差分进化算法因其具有参数较少、对求解结果影响较小的优势, 在多个领域得到成功应用[20-22].所以, 我们就采用改进的差分进化算法用于求解组合服务寻找最优组件服务的问题, 具体实现过程见第3节, 第4节的实验结果也验证了改进的差分进化算法优于对比算法.
3 基于改进差分进化算法的最优恢复规划我们的主要工作是基于改进的差分进化算法寻找最优恢复规划, 所以本节首先介绍经典差分进化算法, 然后再描述改进的地方, 最后说明适应度函数构造及编码方法.
3.1 差分进化算法1997年, Storn和Price在其他进化算法(evolution algorithm)的基础上提出了差分进化算法DE[23].DE是一种简单但强大的随机搜索技术, 可以对非线性、不可微、连续空间函数进行最小化, 其具有易用性、稳健性和强大的全局寻优能力.传统差分进化算法实现过程如下:
1) 种群初始化
在解空间中, 随机、均匀地产生NP个个体(种群规模), 每个个体由D(解的维数)个染色体组成, 作为第0代种群, 标记为
$ X\left( 0 \right) = \{ {X_1}\left( 0 \right), {X_2}\left( 0 \right), \ldots, {X_{NP}}\left( 0 \right)\} $ | (1) |
其中, 第i个染色体Xi(0)(i=1, 2, …, NP)的第j维取值方式为
$ {x_i}_{, j}\left( 0 \right) = {L_j} + rand\left( {0, 1} \right)({U_j}-{L_j}), i = 1, 2, \ldots, NP;j = 1, 2, \ldots, D $ | (2) |
其中, [Lj, Uj]为第j维的取值范围, rand(0, 1)为介于0和1之间的均匀分布随机数.
2) 变异
经过g-1次迭代后, 可得到第g-1代种群为X(g-1)={X1(g-1), X2(g-1), …, XNP(g-1)}.根据第g-1代种群的个体可以得到第g代种群的个体.首先进行如下变异操作得到中间体Hi(g):
$ {H_i}(g) = {X_{{p_1}}}(g-1) + F({X_{{p_2}}}(g-1)-{X_{{p_3}}}(g - 1)), 1 \le i \le NP $ | (3) |
其中,
如果变异过后的向量个体不可行(也就是说落到了搜索空间以外), 可采用文献[24]中提出的修补算子进行修补计算.
3) 交叉
为了提高种群的多样性, DE算法引入了交叉操作.与其他进化算法中基于多个来自父代中的基准个体交换染色体的交叉操作不同, DE中的交叉操作采用基准个体与变异个体进行交叉操作, 具体如下:
$ {v_{i, j}}(g) = \left\{ {\begin{array}{*{20}{l}} {{h_{i, j}}(g), \;\;\;\;\;rand(0, 1) \le CR}\\ {{x_{i, j}}(g-1), {\rm{其他 }}} \end{array}, } \right.i = 1, 2, ..., NP;j = 1, 2, ..., NP $ | (4) |
其中, CR∈[0, 1]为交叉概率, rand(0, 1)为介于0和1之间的均匀分布随机数.
4) 选择
根据适应度函数f选择Vi(g)或Xi(g-1)作为Xi(g):
$ {X_i}(g) = \left\{ {\begin{array}{*{20}{l}} {{V_i}(g), \;\;\;\;\;\;{\rm{ if }} \; f({V_i}(g)) < f({X_i}(g-1))}\\ {{X_i}(g-1), {\rm{其他 }}} \end{array}} \right., i = 1, 2, ..., NP $ | (5) |
DE的选择操作使得子代的适应度值总是好于父代的适应度值, 从而使种群始终向最优解的位置进化, 并逐步聚焦到最优解位置.
3.2 改进差分进化算法DE需要设置的参数有种群规模NP、缩放因子F和交叉概率CR.而本质上, F的取值决定差分向量的影响力, 即确定搜索步长; 交叉概率CR确定多样性, 避免出现早熟现象.所以, F和CR的设置对算法最终性能影响较大[25].因此, 本文将通过对F和CR的设置来改进传统的DE算法.关于对F和CR的设置方法, 可以分为3个类别:常数、随机、适应(包括自适应).本文是采用DE寻找最优恢复规划, 而其会因组合服务的具体执行情况而有所不同, 因此把F和CR设置为常数或者随机均不能得到较优结果, 所以本文采用自适应的方法设置F和CR的值.改进过后的差分进化算法的具体实现过程见算法1.
算法 1.改进差分进化算法IDE.
输入: Fl, Fu, CRl, CRu, Gm, NP, D;
输出:最优解best_vector.
1. X=在解空间中随机生成一个NP行D列的矩阵; //初始化种群
2. H=zeros(NP, D); //用于放置变异过后的中间值
3. V=zeros(NP, D); //用于放置交叉过后的中间值
4. X_next=zeros(NP, D); //用于放置进化过后的下一代值
5. G=1; //初始化进化代数, 用于对进化次数计数
6. while (G≤Gm) or (可接受的满意解) //Gm为设置的最大循环次数
------变异操作------
7. H=Mutation(X);
------交叉操作------
8. V=Crossover(X, H);
9. ------选择操作------
10. for i=1 to NP
11. if Fitness(V(i)) < Fitness(X(i))
12. X_next=V(i);
13. else
14. X_next=X(i);
15. endif
16. endfor
------找出第G代中适应度值最小的个体------
17. for i=1 to NP
18. fit_value(i)=Fitness(X_next(i));
19. endfor
20. (value_min, pos_min)=min(fit_value);
21. Gmin(G)=value_min; //得到第G代的最小适应度值
22. best_X(G)=X_next(pos_min); //保存第G代中得到最小适应度值的个体
23. X=X_next; //得到进化过后的下一代种群
24. G=G+1;
25. Endwhile
26. (value_min, pos_min)=min(Gmin);
27. best_value=value_min; //进化的所有代中的最小适应度值
28. best_vector=X_next(pos_min); //取得最小适应度值的个体, 即最优值
算法1中, Fl, Fu是为缩放因子设置的下限和上限, CRl, CRu是为交叉概率设置下限和上限, Gm是设置的最大循环次数.算法第1行~第5行为算法的初始化操作, 包括种群初始化、进化过程中的中间值和进化代数初始值设置.算法第6行~第25行为差分进化算法的循环迭代过程, 每次循环均经历变异操作(算法第7行)、交叉操作(算法第8行)、选择操作(算法第10行~第16行)以及保留此次循环中适应度值最小的个体(算法第17行~第24行).而结束循环的条件为超过最大迭代次数或者得到用户可接受满意解.算法中, 函数Fitness用于计算个体的适应度值, 其构造过程和具体实现过程见第3.3节.函数Mutation为变异操作, 函数Crossover为交叉操作, 这两个函数的具体实现过程如下.
1) 自适应的变异操作
对第g代种群进行变异操作时, 随机选择的3个个体按照其适应度值进行从优到劣地排序, 假设为Xb(g-1), Xm(g-1), Xw(g-1), 其对应的适应度值f(Xb(g-1))≤f(Xm(g-1))≤f(Xw(g-1))(仅考虑函数的最小化问题, 对于最大化问题, 可进行乘以-1操作后转化为最小化问题), 变异操作修改如下:
$ {H_i}(g) = {X_b}(g-1) + {F_i}({X_m}(g-1)-{X_w}(g - 1)) $ | (6) |
通过采用公式(6), 各代的每个个体均在随机选出的、上一代的3个个体中适应度最好的个体附近进行变异, 可加快收敛速度.又因为每次随机选出的适应度最好的个体不是全部相同, 所以还可以增加种群多样性, 避免陷入局部最优.
同时, 为了平衡全局搜索与局部搜索之间的矛盾, F的取值根据生成差分向量的两个个体进行自适应变化, 其取值如下:
$ {F_i} = {F_l} + ({F_u}-{F_l})\frac{{f({X_m}(g-1))-f({X_b}(g - 1))}}{{f({X_w}(g - 1)) - f({X_b}(g - 1))}} $ | (7) |
其中, Fl和Fu为F设定的上限和下限, 比如可取Fl=0.1, Fu=0.9.采用公式(7)自适应改变Fi值的原因为:当随机选取3个个体的适应度值差别较大(一般为迭代初期)时, 采用较大的缩放算子用于提高全局搜索能力; 适应度值差别较小(一般为迭代末期)时, 采用较小的缩放算子, 防止错过最优解, 即用于提高局部搜索能力.自适应的变异操作具体实现过程见算法2.
算法 2.变异操作Mutation.
输入:种群X;
输出:变异中间体H.
1. for i=1 to NP
2. (num1, num2, num3)=在区间[1, NP], 产生3个不同且不等于i的数;
3. (best, middle, worst)=
4. Fi=Fl+(Fu-Fl)x(Fitness(Xmiddle)-Fitness(Xbest))/(Fitness(Xworst)-Fitness(Xbest)); //得出第i个个体的缩放算子Fi
5. TemVector=Xbest+Fix(Xmiddle-Xworst);
6. for j=1 to D
7. if TemVector(1, j)落在解空间中
8. h(i, j)=TemVector(1, j);
9. else
10. h(i, j)=采用修补算子进行修补计算;
11. endif
12. endfor
13. endfor
14. return H
算法2是对第g-1代所有个体进行变异操作, 其中, 第2行~第4行得到第i个个体的缩放算子Fi, 根据该缩放算子, 对第i个个体进行变异操作(算法第4行).而得到的变异个体的染色体有可能落在解空间之外, 所以需要采用修补算子进行修补计算(算法第6行~第11行).最终返回均落在解空间中的变异种群.
2) 自适应的交叉操作
对适应度好的个体, 取较大的CR, 可使该个体进入下一代的几率增大; 对适应度差的个体, 取较小的CR, 加快改变其的结构, 使该个体能尽快被淘汰掉.所以, 对于每代的进化, 按照公式(8)对CR进行取值:
$ C{R_i} = \left\{ {\begin{array}{*{20}{l}} {C{R_l} + (C{R_u}-C{R_l})\frac{{{f_i}-{f_{\min }}}}{{{f_{\max }}-{f_{\min }}}}{\rm{, if }} \;\;{f_i} < \bar f}\\ {C{R_l},\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; {\rm{if }} \;{f_i} \ge \bar f} \end{array}} \right. $ | (8) |
其中, fi是个体Xi的适应度, fmin和fmax分别为当前种群中最优和最差个体的适应度,
算法 3.交叉操作Crossover.
输入:种群X, 变异中间体H;
输出:交叉中间体V.
1. fmin=min(Fitness(X)); //当前种群中最小的适应度值, 即当前最优解的适应度值
2. fmax=max(Fitness(X)); //当前种群中最大的适应度值, 即当前最差解的适应度值
3. faver=aver(Fitness(X)); //当前种群的平均适应度值
4. for i=1 to NP
5. if Fitness(X_next(i)) < faver
6. CRi=CRl+(CRu-CRi)×((Fitness(X_next(i))-fmin)/(fmax-fmin));
7. else
8. CRi=CRl;
9. endif
10. for j=1 to D
11. if rand(0, 1) > CRi
12. v(i, j)=x(i, j);
13. else
14. v(i, j)=h(i, j);
15. endif
16. endfor
17. endfor
18. return V
算法3是对g-1代种群变异过后进行的交叉操作.算法第1行~第3行得到当前种群中适应度最小、最大和平均值.如果个体的适应度值小于当前种群平均适应度值, 交叉概率按照公式(8)计算得出; 否则, 交叉概率为CRl(算法3第5行~第9行).然后, 按照交叉概率对种群进行交叉操作(算法3第10行~第15行).最终返回交叉后的种群.
3.3 适应度函数构造及编码与遗传算法和粒子群算法类似, 差分进化算法也采用适应度概念, 用来度量种群中的各个个体在优化计算中有可能达到或接近于或有助于找到最优解的优良程度, 适应度值较低的个体进入到下一代的概率较大, 而适应度值较高的个体进入到下一代的概率就相对小一些(仅针对最小化优化问题, 最大化优化问题则反之).度量个体适应度值的函数称为适应度函数, 其一般由目标函数变换而来.
针对本文问题, 我们的最终目标是找到最优恢复规划, 其优化程度由服务的SLA属性确定.而一个恢复规划通常需要考虑多个SLA属性, 所以需要对这些SLA属性进行聚合.本文沿袭我们的前期工作[19, 26-30]对QoS的聚合方法对SLA聚合, 只考虑消极指标的最小化, 对于积极指标采用乘上-1(负值计算)就可转化为消极指标[17], 并采用文献[31, 32]中对所有SLA属性进行归一化处理, 使得不同量纲的SLA属性值可以进行比较, 并采用简单加权方法构建聚合函数.
假如恢复规划中含有m个任务(对应差分进化算法中解的维数D), 每个任务需要绑定的服务需要考虑l个SLA属性, Sij表示第j个任务需要绑定服务的第i个SLA归一化后的属性值, wi表示对第i个SLA属性选择的权重(其值可根据用户偏好设置), 且
$ U = \sum\limits_{j = 1}^m {\sum\limits_{i = 1}^l {{S_{ij}}{w_i}} } $ | (9) |
那么, 最优恢复规划为使得聚合函数U取得最小值时的对m个任务的一组服务绑定, 即:
$ r = {\rm{argmin}}U $ | (10) |
也就是说, 公式(9)为本文目标函数.所以, 我们直接采用其作为适应度函数, 即构造差分进化算法的适应度函数如公式(11):
$ f = \sum\limits_{j = 1}^m {\sum\limits_{i = 1}^l {{S_{ij}}{w_i}} } $ | (11) |
构造出适应度函数后, 为了能采用差分进化算法求出最优恢复规划, 还需要对算法的个体进行编码.针对本文问题, 个体采用整数数组表示, 数组包含元素的个数为恢复规划中抽象组件的个数, 数组中的每个整数元素为抽象组件可绑定的组件服务的索引, 其最小值为1, 最大值为该组件可绑定组件服务的数目.通过循环迭代, 改变数组元素的值(经过修补和取整操作得到落到解空间的整数)等同于改变抽象组件的组件服务绑定.而差分进化算法的最终目标是根据适应度值, 计算使得适应度值取得最小值的一组组件服务索引.
算法4为适应度函数的具体实现过程, 其根据整数数组的值, 取出对应每个任务的组件服务绑定, 根据每一个组件服务经过归一化后的SLA属性值, 计算恢复规划的聚合函数值, 即适应度值.
算法 4.适应度值计算Fitness.
输入:个体x, 权重w;
输出:适应度值f.
1.根据个体x的取值, 取出对应每个任务的组件服务绑定以及每个组件服务的、经过归一化后的SLA属性值S;
2. f=0;
3. for j=1 to m
4. for i=1 to l
5. f=f+Sij×wi;
6. endfor
7. endfor
8. return f
4 仿真实验为了验证SLAFT方法的有效性, 我们进行了大量的仿真实验:首先, 将我们提出的方法与其他两种方法在故障处理时间和组合最优度两个性能指标进行了实验对比; 然后, 对FRFTA方法中的重要参数进行了分析.
4.1 实验建立我们的前期工作[30, 33, 34]也是研究组合服务容错方法, 但其是更侧重于非事务型组合服务的容错方法.事务型组合服务的容错方法与非事务型容错方法有很大不同, 所以本文延续我们的前期工作, 针对事务型组合服务的容错方法进行了研究.我们在前期实验环境的基础上进行了改进, 以更适合本文场景, 然后基于改进后的实验环境进行了本文的实验.
为了进行仿真实验, 需要有关于服务SLA的数据集, 但我们没有找到足够进行实验的相关数据.而服务的QoS也可以看做服务使用者与服务提供者事先商定的, 关于服务提供者对于其提供服务的QoS方面达成的SLA, 即QoS为SLA的一部分.所以不失一般性, 我们还继续采用两个真实的关于服务的QoS的数据集QWS和WS-DREAM的QoSDataset2进行我们的实验.
QWS[35]包含2 507个真实Web服务, 每个服务包含9个QoS属性.WS-DREAM的QoSDataset2[36, 37], 包含339个用户使用5 825个Web服务的响应时间(response time)和吞吐率(throughput).实验环境为:Intel(R) Core(TM) i5-4210U 2.39GHz, 8.0GB of RAM, Windows 8.1专业版.
本文实验中, 组合服务包含的任务数量设置为5~60, 候选服务数量设置为60.组合服务的最初的、最优任务绑定可通过已有文献[38, 39]的方法求得.组合服务执行过程为:按照组合服务的结构, 执行其的每一个组件服务.当遇到故障时, 采用容错方法排除出现的故障, 然后继续执行组合服务, 直至其全部服务均执行完成, 也就是说, 组合服务成功执行.软件可靠性(software reliability)是软件产品在规定的条件下和规定的时间区间完成规定功能的能力, 其值为软件不引起系统失效的概率, 即不出现故障的概率.所以, 组件服务的可靠性值决定了组合服务执行过程中可能出现的故障数量.仿真实验中, 我们通过设定组件服务的不同可靠性值来仿真组合服务执行过程中出现的不同故障规模.为了便于与其他方法进行比较以及说明本文所提方法的有效性, 在仿真实验中, 采用故障处理时间和组合最优度两个性能指标.具体定义如下.
定义 5(故障处理时间).在组合服务的执行过程中, 排除出现的故障所花费的时间总和Ft, 即:
$ {F_t} = \sum\limits_{i = 1}^m {f_t^i} $ | (12) |
其中, m代表执行过程中出现的故障的总次数,
定义 6(组合最优度).为组合服务的SLA聚合值, 其采用文献[31, 32]中的简单加权方法构建, 即
$ U = \sum\limits_{i = 1}^N {(0.5{r_i} + 0.5t{h_i})} $ | (13) |
因为WS-DREAM的数据集QoSDataset2只包含服务的响应时间和吞吐率, 我们只考虑这两个SLA属性, 两者的权重均设定为0.5(也可以根据用户偏好设定).公式(13)中:N为组合服务包含的任务个数; ri和thi分别为采用文献[31, 32, 40]中方法归一化后的服务i的响应时间和吞吐率; U代表组合最优度, 其值的大小代表组合服务SLA属性的优劣, 值越高, 代表SLA属性越优; 值越低, 则相反.
4.2 实验对比首先进行了实验对比, 以此来验证我们所提方法SLAFT的有效性.对比方法有两种, 分别为FACTS[9] (提出了一个容错框架FACTS, 其为事务性型组合服务的容错提供了一个包括规范、验证和执行的集成环境)和rGA[16](基于改进的遗传算法对组合服务进行补偿).不同类型的组合服务包含具有原子特性的任务数占总任务数的比率各不相同, 不失一般性, 我们仅针对比率为10%, 50%和100%的3种类型的实验(分别采用A类实验、B类实验和C类实验表示), 分别采用我们所提方法SLAFT和两种对比方法进行容错实验.WS-DREAM的QoSDataset2数据集中没有组件服务的可靠性, 所以对组件服务的可靠性均设定为0.9.对于3类实验, 分别按照任务数量从5开始, 并按照以5依次增加的规律, 采用3类方法分别进行实验.为了保证实验的公正性, 结果均取运行100次实验后的平均值.
4.2.1 A类实验结果图 5为我们所提方法SLAFT与两种对比方法FACTS和rGA对于A类实验, 不同总任务数量情况下的实验结果对比, 图 5(a)为所需故障处理时间结果, 图 5(b)为组合最优度实验结果对比.从图 5(a)和图 5(b)可以看出:采用SLAFT方法所需故障处理时间略少于rGA方法, 较少于FACTS方法; 而组合最优度略优于rGA方法, 而较优于FACTS方法.但总的来说, 3类方法差别不是特别大.分析出现这种结果的原因为:在A类实验中, 具有原子特性的任务个数占总任务个数的比率仅为10%, 即在出现故障后, 仅需要回溯较短的步长就可开始寻找最优替代路径.也就是说, 恢复规划中所含任务数量较少, 这使得整个状态空间不是很大, 所以故障处理时间均较短, 且组合最优度均较高.FACTS因没有采用启发式算法, 导致总的故障处理时间偏多和组合最优度偏低, 而同采用启发式算法的rGA和SLAFT方法, 故障处理时间较短, 组合最优度较高.且还可以看出, SLAFT略优于rGA.对比实验结果说明:虽同为启发式算法, 针对本文所提问题, 差分进化算法要优于遗传算法.
4.2.2 B类实验结果
图 6为B类实验结果, B类实验的组合服务中, 具有原子特性的任务数占总任务数的比率为50%, 与A类实验相比, 这类组合服务一旦出现故障, 其需要回溯的步数会变多, 恢复规划中包含的任务数也会增加.而随着任务数的增加, 其寻优过程中的状态空间会出现指数级别增长.这种特性导致不采用启发式算法的FACTS在任务数比较少时, 故障处理时间和rGA和SLAFT还没有太大差别(见图 6(a)); 但随着任务数的增多, 其故障处理时间增加很多, 这将使得在对时延敏感的场景下不可采用FACTS方法.rGA和SLAFT方法在任务数较少的情况下, 故障处理时间线性增加, 在任务数大于40个后, 故障处理时间增加明显.但任务数大于40的组合服务一般为较长事务, 人们对此类事务的运行时间预期也会增加.从图 6(a)和图 6(b)可知:SLAFT方法在故障处理时间略低于rGA, 在组合最优度上略高于rGA, 这说明SLAFT方法更接近最优解.与图 5(b)相比, 图 6(b)的整体结果均有所降低, 这是因为与A类实验相比, B类实验中的恢复规划任务数增多, 也就是说, 有更多的任务因故障解除了与最初的、最优组件服务的绑定, 重新绑定了次优组件服务, 这将导致组合最优度的降低.
4.2.3 C类实验结果
C类实验的组合服务中具有原子特性的任务数占总任务数的比率为100%, 也就是说, 此类组合服务在执行过程中一旦出现故障, 必须回溯到组合服务的开始, 重新绑定组件服务, 重新执行组合服务, 即恢复规划中包含任务数量会更多, 所以与A类实验和B类实验相比, 其故障处理时间增加较多(如图 7(a)所示).又因为有更多的任务因故障解除了与最初的、最优组件服务的绑定, 重新绑定了次优组件服务, 这将导致组合最优度的进一步降低(如图 7(b)所示).但总体来说, SLAFT方法更趋近最优解.
从上述3类实验结果来看, 我们所提方法SLAFT与rGA比较, 还是有一定的优势.本文研究问题为NP-hard, 在问题规模较大的情况下, 只能寻找近似最优解, 为了描述方便, 我们一般称为最优解.SLAFT和rGA均为启发式算法, 采用这两种算法求得的最终结果均不是数学意义上的最优解, 而是接近于最优解的近似解.与对比算法rGA相比, 我们所提方法SLAFT提高幅度不是特别明显, 甚至在曲线和柱状图上有交叉和各有上下的情况, 但总体上其结果略优.为了方便展示略优结果, 我们对实验结果作了进一步统计, 统计结果见表 1.
表 1根据上述3类实验的结果, 依据公式(14)计算得到SLAFT方法与对比方法的改进率:
$ I = \frac{{|{r_c}-{r_{SLAFT}}|}}{{{r_c}}} \times 100\% $ | (14) |
其中, I表示方法SLAFT与对比方法相比较的改进率, rc和rSLAFT表示对比方法和SLAFT实验结果(同一类型实验结果求和).从表 1可以看出, SLAFT方法的实验结果整体上略优于rGA.也就是说, 我们所提SLAFT方法的求解结果更接近于最优值.
4.3 参数分析作为一种容错方法, 故障规模将会直接影响实验结果.为了进一步验证我们所提方法SLAFT的性能, 需要改变故障规模大小, 以此来观察其对实验结果的影响.而故障的规模由组件服务的可靠性值确定, 所以我们改变组件服务的可靠性值, 继续进行实验.在现实生活中, 可靠性低于0.5的组件服务基本上已不可用, 所以不对其进行实验.因此, 针对参数分析实验, 设定组合服务均包含任务数为20, 每个组件服务的可靠性从0.5开始, 按照依次增加0.05的规律, 直到0.95.对包含具有原子特性的任务数占总任务数的比率从10%开始, 依次增加10%, 直至100%的组合服务分别进行实验.每类实验运行100次, 实验结果取其平均值.
图 8为不同可靠性取值的、采用SLAFT方法的故障处理时间实验结果.
从图中可以看出:随着组件服务可靠性的减小, 故障处理时间渐渐增多; 随着具有原子特性的任务数占总任务的比率的增加, 故障处理时间也随之增加.这是因为随着可靠性的降低, 出现故障的概率就会增加, 故障处理时间也随之增加.而随着原子特性任务数占总任务数比率的增加, 恢复规划中包含任务数将会增多, 寻找最佳替代路径的时间随之增加, 导致总的故障处理时间增加.而组件服务可靠性的降低将会增加故障规模, 从图 8可以看出, SLAFT方法对故障规模较大的情形也能计算出故障处理时间.而原子特性任务数占总任务数的不同比率代表了不同类型的组合服务, 图 8显示SLAFT方法针对不同类型的组合服务均适应良好.
图 9为不同可靠性取值下, 采用SLAFT方法的组合最优度实验结果.随着可靠性取值的降低或者原子特性任务数占总任务数比率的增加, 组合最优度会降低.这是因为可靠性较低时, 组件服务在执行过程中出故障的概率将增加; 而随着原子特性任务数占总任务数比率的增加, 恢复规划中包含任务数将会增多.而这两种情况都会导致组合最优度的降低.但从图 9可以看出, SLAFT方法均可计算出最终组合最优度值.
通过实验对比和参数分析可以看出:SLAFT方法与对比算法相比, 拥有较低故障处理时间的同时, 还具有较高的组合最优度, 且对不同故障规模适应良好.
5 相关工作针对事务性组合服务的事务特性与容错方法, 许多学者提出了研究思路或解决方法, 并取得了较好的成果.限于篇幅原因, 本文只对一些与本文类似的文献予以分析.
传统的服务选择方法根据组合服务的功能性需求, 满足用户要求的QoS约束, 而不考虑组合过程中的事务性约束(transactional constraints).而文献[41]认为, 事务属性是确保组合服务可靠执行的必备条件之一, 所以必须在服务选择过程中兼顾事务性属性.并提出了一种用于组合服务设计阶段的自动服务选择方法, 其在选择过程中整合(integrate)QoS和事务性需求.通过该方法为组合服务选择的每个组件服务, 在确保满足全局事务约束的前提下, 是满足局部QoS约束中最好的.文献[42]采用用户查询(user query)方法形式化定义组合服务问题, 采用扩展的CPN(colored petri-nets)技术来实现在服务选择过程中兼顾事务性属性.但上述两个文献仅在组合服务执行前的服务选择阶段考虑事务性, 其只能在组合服务能完全正确执行时才能确保事务特性, 而一旦遇到执行故障, 事务特性将无法保障.
文献[43]针对事务性组合服务提出了一种容错方法, 该方法可支持向后和向前错误恢复, 而向后错误恢复采用松弛的原子执行(relaxed atomic exectution)策略实现, 向前错误恢复采用异常处理实现.为了实现原子执行, 还提出了一种可扩展的交付协议SCP(scalable commit protlcol), 其允许一个组合服务包含异质的事务性Web服务.同时还提出了一个恢复算法, 其可以确保出现故障的组合服务的继续执行.但文献[43]提出的SCP比较低效, 可能出现资源被未知过程占用一段时间的现象.
文献[44, 45]采用CPN技术处理事务性组合服务执行过程中出现的故障.文献[44]提出了一个高效、可容错和保证事务性组合服务正确执行的框架, 该框架通过组件服务替代和补偿协议支持向前或向后的恢复, 具体实现过程采用CPN.文献[45]也提出一个框架, 名称为FaCETa(fault tolerant cws execution based on transactional properties), 其基于CPN的展开过程来处理故障.虽然CPN技术可以用来处理事务性组合执行过程中出现的故障, 但Petri-Nets构建出来的模型一般比较庞大, 且不支持构造大规模模型, 所以文献[44, 45]所提框架只适合应用于组件服务比较少的事务性组合服务的故障处理过程.
文献[9]为事务型组合服务提出了一种容错框架FACTS, 其为容错提供了一个包括规范、验证和执行的集成环境.且该框架与组合服务执行逻辑分离, 使得故障处理逻辑易于开发、维护和更新.其次, 采用ECA(event- condition-action)规则来描述何时和如何触发故障处理逻辑.另外, 提出EXTRA(exception handing+transaction)机制, 其融合了异常处理和事务技术(transaction techniques)两种容错机制, 用于增强组合服务的可靠性.EXTRA采用八类高层异常处理机制来修复组合服务执行过程中的故障, 给出了一种新的Web服务事务型分类, 分析了事务型组合服务的关键特性, 即服务转移(service transfer)和活力程度(vitality degree).同时也定义了一个协议STTP(service-transfer-based termination protocol), 其可使得组合服务产生不可修复的故障时终止在一个一致的状态.但该文献存在一些局限性:1)故障处理过程只能在组合服务的全状态空间中寻找恢复规划, 势必会导致所提方法的扩展性较差; 2)故障处理过程中没有考虑SLA属性, 而具有较低SLA属性值的恢复规划可能导致组合服务的SLA违反.
文献[16]对BPEL进行了扩充, 使之更适合应用于事务性组合服务执行过程中的补偿操作和恢复规划的执行.并对传统遗传算法进行了改进, 用于恢复规划的制定, 具体改进为:1)通过采用动态长度染色体(dynamic- length chromosomes)来保存恢复规划, 其在递归过程中可根据实际需求申请存储空间, 可降低算法的空间复杂度; 2)制定的恢复规划除了满足组合服务的QoS约束外, 且是在组合服务的部分状态空间中制定得到, 又进一步减少了算法执行时间, 使之可更容易扩展到组件服务较多的组合服务的故障处理之中或者应用到在线实时故障处理; 3)收集递归过程中的中间解信息, 结合组合服务的结构, 共同作用于后面的递归过程, 使得得到最优解的几率加大.虽然文献[16]对遗传算法进行了改进, 但遗传算法对参数取值比较敏感, 不同参数设置会得出不同结果, 且其实现较复杂的特性还是没有根本改变.所以, 与本文所提SLAFT方法相比, 文献[16]故障恢复时间较长, 且组合最优度偏低(详见第4.2节).也就是说, 虽同为启发式算法, 针对本文所提场景, 差分进化算法要优于遗传算法.
6 结论与未来工作展望针对事务性组合服务执行期间出现的故障, 本文提出了一种容错方法SLAFT.首先, SLAFT方法独立于组合服务的执行逻辑, 只有在出现故障的时候才会被触发, 因此其易于开发、维护和更新; 其次, 为了确保组合服务出现故障时能停留在一个一致的状态, SLAFT采用有限状态机建模其的执行状态, 并对其进行状态监控; 再次, 为了不违反服务使用者和服务提供者事先商定的SLA属性, 采用监控自动机进行执行监督; 最后, 进行补偿操作时, SLAFT采用改进的差分进化算法, 其可以快速且精确的找到最优恢复规划.基于两个真实数据集的实验, 验证了本文所提SLAFT方法在故障处理时间和组合最优度上均优于对比方法, 且对不同故障规模适应良好.
虽然所提SLAFT方法与其他方法相比有一定的优势, 但其也存在不足:(1)不是通过严格的数学证明SLAFT方法优于其他对比方法, 只是从实验结果上给于了验证; (2)差分进化算法的初始种群是随机生成的, 如果能找到对初始种群地生成优化算法, 有可能进一步减少算法执行时间, 进而提高容错的实时性; (3)仅在模拟环境下实现SLAFT方法, 其应如何在实际的网络环境中进行部署、其有效性如何以及是否优于其他对比算法均没有得以验证.我们未来的工作将针对存在的这些不足, 进一步提高SLAFT方法的有效性.
致谢 在此, 对提供QWS数据集的加拿大圭尔夫大学的Mahmoud博士和Al-Masri博士, 以及提供WS-DREAM数据集的中山大学的郑子彬副教授表示衷心感谢.[1] |
Delac G, Silic M, Srbljic S.A reliability improvement method for SOA-based applications.IEEE Trans.on Dependable and Secure Computing, 2015, 12(2): 136-149.[doi: 10.1109/TDSC.2014.2327971]
|
[2] |
Li G, Zhao ZF, Han YB, Liang Y. CAFISE Framework based development for service oriented applications with high adaptability. Ruan Jian Xue Bao/Journal of Software, 2006, 17(6): 1372-1380(in Chinese with English abstract).
http://www.jos.org.cn/1000-9825/17/1372.htm [doi:10.1360/jos171372] |
[3] |
Zhuang Y, Zhang PC, Li WQ, Feng J, Zhu YL. Web service QoS monitoring approach sensing to environmental factors. Ruan Jian Xue Bao/Journal of Software, 2016, 27(8): 1978-1992(in Chinese with English abstract).
http://www.jos.org.cn/1000-9825/4850.htm [doi:10.13328/j.cnki.jos.004850] |
[4] |
Yu WD. A software fault prevention approach in coding and root cause analysis. Bell Labs Technical Journal, 1998, 3(2): 3-21.
[doi:10.1002/bltj.2101] |
[5] |
Littlewood B. Stochastic reliability-growth:a model for fault-removal in computer-programs and hardware-designs. IEEE Trans.on Reliability, 1981, 30(4): 313-320.
[doi:10.1109/TR.1981.5221099] |
[6] |
Vergura S, Acciani G, Amoruso V.Inferential statistics for monitoring and fault forecasting of PV plants.In: Proc.of the Int'l Symp.on Industrial Electronics.Cambridge: IEEE, 2008.2414-2419.[doi: 10.1109/ISIE.2008.4677264]
|
[7] |
Randell B. System structure for software fault tolerance. IEEE Trans.on Software Engineering, 1975, SE-1(2): 220-232.
[doi:10.1109/TSE.1975.6312842] |
[8] |
Issarny V, Tartanoglu F, Romanovsky A, Levy N.Coordinated forward error recovery for composite Web services.In: Proc.of the Int'l Symp.on Reliable Distributed Systems.Florence: IEEE, 2003.167-176.[doi: 10.1109/RELDIS.2003.1238066]
|
[9] |
Liu A, Li Q, Huang L, Xiao M. Facts:A Framework for fault-tolerant composition of transactional Web services. IEEE Trans.on Services Computing, 2010, 3(1): 46-59.
[doi:10.1109/TSC.2009.28] |
[10] |
Wu GQ, Wei J, Huang T. A dynamic QoS assessment approach for internetware with uncertainty reasoning. Ruan Jian Xue Bao/Journal of Software, 2008, 19(5): 1173-1185(in Chinese with English abstract).
http://www.jos.org.cn/1000-9825/19/1173.htm [doi:10.3724/SP.J.1001.2008.01173] |
[11] |
Ludwig H, Keller A, Dan A, King RP, Franck R. Web Service Level Agreement (WSLA) Language Specification. Watson: IBM Corporation, 2003: 815-824.
|
[12] |
Wieder P, Butler JM, Theilmann W, Yahyapour R. Service Level Agreements for Cloud Computing. New York: Springer-Verlag, 2011: 13-20.
|
[13] |
Jordan D, Evdemon J. Web Services Business Process Execution Language Version 2.0.Vol.2. OASIS Standard, 2007.
|
[14] |
Baresi L, Guinea S. Self-Supervising bpel processes. IEEE Trans.on Software Engineering, 2011, 37(2): 247-263.
[doi:10.1109/TSE.2010.37] |
[15] |
Foster H.A rigorous approach to engineering Web service compositions[Ph.D.Thesis].London: Imperial College of London, 2006.
|
[16] |
Tan TH, Chen M, André É, Sun J, Liu Y, Dong JS.Automated runtime recovery for QoS-based service composition.In: Proc.of the Int'l Conf.on World Wide Web.New York: ACM Press, 2014.563-574.[doi: 10.1145/2566486.2568048]
|
[17] |
Alrifai M, Risse T.Combining global optimization with local selection for efficient QoS-aware service composition.In: Proc.of the Int'l Conf.on World Wide Web.New York: ACM Press, 2009.881-890.[doi: 10.1145/1526709.1526828]
|
[18] |
Parra-Hernandez R, Dimopoulos NJ. A new heuristic for solving the multichoice multidimensional knapsack problem. IEEE Trans.on Systems, Man, and Cybernetics-Part A:Systems and Humans, 2005, 35(5): 708-717.
[doi:10.1109/TSMCA.2005.851140] |
[19] |
Wang SG, Sun QB, Yang FC. Web service dynamic selection by the decomposition of global QoS constraints. Ruan Jian Xue Bao/Journal of Software, 2011, 22(7): 1426-1439(in Chinese with English abstract).
http://www.jos.org.cn/1000-9825/3842.htm [doi:10.3724/SP.J.1001.2011.03842] |
[20] |
Qin AK, Huang VL, Suganthan PN. Differential evolution algorithm with strategy adaptation for global numerical optimization. IEEE Trans.on Evolutionary Computation, 2009, 13(2): 398-417.
[doi:10.1109/TEVC.2008.927706] |
[21] |
Mallipeddi R, Suganthan PN, Pan QK, Tasgetiren MF. Differential evolution algorithm with ensemble of parameters and mutation strategies. Applied Soft Computing, 2011, 11(2): 1679-1696.
[doi:10.1016/j.asoc.2010.04.024] |
[22] |
Das S, Abraham A, Konar A. Automatic clustering using an improved differential evolution algorithm. IEEE Trans.on Systems, Man, and Cybernetics-Part A:Systems and Humans, 2008, 38(1): 218-237.
[doi:10.1109/TSMCA.2007.909595] |
[23] |
Storn R, Price K. Differential evolution-A simple and efficient heuristic for global optimization over continuous spaces. Journal of Global Optimization, 1997, 11(4): 341-359.
[doi:10.1023/A:1008202821328] |
[24] |
Wang Y, Cai Z, Zhang Q. Differential evolution with composite trial vector generation strategies and control parameters. IEEE Trans.on Evolutionary Computation, 2011, 15(1): 55-66.
[doi:10.1109/TEVC.2010.2087271] |
[25] |
Tang L, Dong Y, Liu J. Differential evolution with an individual-dependent mechanism. IEEE Trans.on Evolutionary Computation, 2015, 19(4): 560-574.
[doi:10.1109/TEVC.2014.2360890] |
[26] |
Wang SG, Sun QB, Zhang GW, Yang FC. Uncertain QoS-aware Skyline service selection based on cloud model. Ruan Jian Xue Bao/Journal of Software, 2012, 23(6): 1397-1421(in Chinese with English abstract).
http://www.jos.org.cn/1000-9825/4084.htm [doi:10.3724/SP.J.1001.2012.04084] |
[27] |
Wang SG, Sun QB, Yang FC. Reputation evaluation approach in Web service selection. Ruan Jian Xue Bao/Journal of Software, 2012, 23(6): 1350-1367(in Chinese with English abstract).
http://www.jos.org.cn/1000-9825/4051.htm [doi:10.3724/SP.J.1001.2012.04051] |
[28] |
Ma Y, Wang SG, Sun QB, Yang FC. Web service quality metric algorithm employing objective and subjective weight. Ruan Jian Xue Bao/Journal of Software, 2014, 25(11): 2473-2485(in Chinese with English abstract).
http://www.jos.org.cn/1000-9825/4508.htm [doi:10.13328/j.cnki.jos.004508] |
[29] |
Wang SG, Zhou A, Yang FC, Chang RN. Towards network-aware service composition in the cloud. IEEE Trans.on Cloud Computing, 2016.
[doi:10.1109/TCC.2016.2603504] |
[30] |
Zhang JN, Wang SG, Sun QB, Yang FC. Fast and reliable fault-tolerance approach for service composition in integration networks. Ruan Jian Xue Bao/Journal of Software, 2017, 28(4): 940-958(in Chinese with English abstract).
http://www.jos.org.cn/1000-9825/5051.htm [doi:10.13328/j.cnki.jos.005051] |
[31] |
Zeng LZ, Benatallah B, Ngu AH, Dumas M, Kalagnanam J, Chang H. QoS-Aware middleware for web services composition. IEEE Trans.on Software Engineering, 2004, 30(5): 311-327.
[doi:10.1109/TSE.2004.11] |
[32] |
Zeng LZ, Benatallah B, Dumas M, Kalagnanam J, Sheng QZ.Quality driven Web services composition.In: Proc.of the Int'l Conf.on World Wide Web.New York: ACM Press, 2003.411-421.[doi: 10.1145/775152.775211]
|
[33] |
Wang SG, Ma Y, Cheng B, Yang FC, Chang R. Multi-Dimensional QoS prediction for service recommendations. IEEE Trans.on Services Computing, 2016, 1-12.
[doi:10.1109/TSC.2016.2584058] |
[34] |
Zhou A, Wang SG, Cheng B, Zheng ZB, Yang FC, Chang R, Michael L, Buyya R. Cloud service reliability enhancement via virtual machine placement optimization. IEEE Trans.on Services Computing, 2016, 1-13.
[doi:10.1109/TSC.2016.2519898] |
[35] |
Al-Masri E, Mahmoud QH.Investigating Web services on the World Wide Web.In: Proc.of the Int'l Conf.on World Wide Web.New York: ACM Press, 2008.795-804.[doi: 10.1145/1367497.1367605]
|
[36] |
Zheng ZB, Zhang Y, Lyu MR.Distributed QoS evaluation for real-world Web services.In: Proc.of Int'l Conf.on Web Services.Miami: IEEE, 2010.83-90.[doi: 10.1109/ICWS.2010.10]
|
[37] |
Zhang YL, Zheng ZB, Lyu MR.Exploring latent features for memory-based QoS prediction in cloud computing.In: Proc.of the IEEE Symp.on Reliable Distributed Systems.Madrid: IEEE, 2011.1-10.[doi: 10.1109/SRDS.2011.10]
|
[38] |
Wang SG, Hsu CH, Liang ZJ, Sun QB, Yang FC. Multi-User Web service selection based on multi-QoS prediction. Information Systems Frontiers, 2014, 16(1): 143-152.
[doi:10.1007/s10796-013-9455-4] |
[39] |
Deng SG, Wu J, Li Y, Wu ZH. Automatic Web service composition based on backward tree. Ruan Jian Xue Bao/Journal of Software, 2007, 18(8): 1896-1910(in Chinese with English abstract).
http://www.jos.org.cn/1000-9825/18/1896.htm [doi:10.1360/jos181896] |
[40] |
Liu XZ, Huang G, Mei H. Consumer-Centric service aggregation:Method and its supporting framework. Ruan Jian Xue Bao/Journal of Software, 2007, 18(8): 1883-1895(in Chinese with English abstract).
http://www.jos.org.cn/1000-9825/18/1883.htm [doi:10.1360/jos181883] |
[41] |
El Hadad J, Manouvrier M, Rukoz M. TQoS:Transactional and QoS-aware selection algorithm for automatic Web service composition. IEEE Tran.on Services Computing, 2010, 3(1): 73-85.
[doi:10.1109/TSC.2010.5] |
[42] |
Cardinale Y, El Haddad J, Manouvrier M, Rukoz M. Web service selection for transactional composition. Procedia Computer Science, 2010, 1(1): 2689-2698.
[doi:10.1016/j.procs.2010.04.302] |
[43] |
Liu A, Huang LS, Li Q, Xiao MJ.Fault-Tolerant orchestration of transactional Web services.In: Proc.of the Int'l Conf.on Web Information Systems Engineering.Evanston: Springer-Verlag, 2006.90-101.[doi: 10.1007/11912873_12]
|
[44] |
Cardinale Y, Rukoz M.A Framework for reliable execution of transactional composite Web services.In: Proc.of the Int'l Conf.on Management of Emergent Digital EcoSystems.San Francisco: ACM Press, 2011.129-136.[doi: 10.1145/2077489.2077513]
|
[45] |
Angarita R, Cardinale Y, Rukoz M.Faceta: Backward and forward recovery for execution of transactional composite ws.In: Proc.of the Extended Semantic Web Conf.Montpellier: Springer-Verlag, 2012.343-357.[doi: 10.1007/978-3-662-46641-4_26]
|
[2] |
李刚, 赵卓峰, 韩燕波, 梁英. 基于CAFISE Framework的高适应性面向服务软件开发. 软件学报, 2006, 17(6): 1372-1380.
http://www.jos.org.cn/1000-9825/17/1372.htm [doi:10.1360/jos171372] |
[3] |
庄媛, 张鹏程, 李雯睿, 冯钧, 朱跃龙. 一种环境因素敏感的Web Service QoS监控方法. 软件学报, 2016, 27(8): 1978-1992.
http://www.jos.org.cn/1000-9825/4850.htm [doi:10.13328/j.cnki.jos.004850] |
[10] |
吴国全, 魏峻, 黄涛. 基于非确定性推理的网构软件服务质量动态评估方法. 软件学报, 2008, 19(5): 1173-1185.
http://www.jos.org.cn/1000-9825/19/1173.htm [doi:10.3724/SP.J.1001.2008.01173] |
[19] |
王尚广, 孙其博, 杨放春. 基于全局QoS约束分解的Web服务动态选择. 软件学报, 2011, 22(7): 1426-1439.
http://www.jos.org.cn/1000-9825/3842.htm [doi:10.3724/SP.J.1001.2011.03842] |
[26] |
王尚广, 孙其博, 张光卫, 杨放春. 基于云模型的不确定性QoS感知的Skyline服务选择. 软件学报, 2012, 23(6): 1397-1412.
http://www.jos.org.cn/1000-9825/4084.htm [doi:10.3724/SP.J.1001.2012.04084] |
[27] |
王尚广, 孙其博, 杨放春. Web服务选择中信誉度评估方法. 软件学报, 2012, 23(6): 1350-1367.
http://www.jos.org.cn/1000-9825/4051.htm [doi:10.3724/SP.J.1001.2012.04051] |
[28] |
马友, 王尚广, 孙其博, 杨放春. 一种综合考虑主客观权重的Web服务QoS度量算法. 软件学报, 2014, 25(11): 2473-2485.
http://www.jos.org.cn/1000-9825/4508.htm [doi:10.13328/j.cnki.jos.004508] |
[30] |
张俊娜, 王尚广, 孙其博, 杨放春. 融合网络环境下快速可靠的服务组合容错方法. 软件学报, 2017, 28(4): 940-958.
http://www.jos.org.cn/1000-9825/5051.htm [doi:10.13328/j.cnki.jos.005051] |
[39] |
邓水光, 吴健, 李莹, 吴朝晖. 基于回溯树的Web服务自动组合. 软件学报, 2007, 18(8): 1896-1910.
http://www.jos.org.cn/1000-9825/18/1896.htm [doi:10.1360/jos181896] |
[40] |
刘譞哲, 黄罡, 梅宏. 用户驱动的服务聚合方法及其支撑框架. 软件学报, 2007, 18(8): 1883-1895.
http://www.jos.org.cn/1000-9825/18/1883.htm [doi:10.1360/jos181883] |