基于补偿业务生成图的组合服务异常处理方法研究精

第 31 卷第 8 期计 算 机 学 报Vol. 31 No.12008 年 8 月CHINESE JOURNAL OF COMPUTERSAug. 2008基于补偿业务生成图的组合服务异常处理方法研究尚宗敏崔立真王海洋史玉良（山东大学计算机科学与技术学院济南 250101）摘要为提高组合 Web 服务执行的一致性、可靠性，提出一种基于补偿业务生成图的组合服务异常处理方法.基于业务流程中任务间补偿依赖关系，讨论了补偿业务生成图的自动生成问题.重点讨论了补偿任务、补偿目标和服务转让应用模式，并相应地介绍了支持框架和相关技术.在此基础上设计了补偿依赖关系、补偿业务生成图的自动生成及组合服务执行过程中异常处理算法.当业务流程出现异常采取向前或向后恢复处理时，该方法在保证补偿实现的同时，兼顾补偿服务不存在或补偿服务代价过高的问题.提高了业务流程执行过程中的自动化水平和自适应能力.仿真结果证实,该方法保证了异常发生时组合服务执行的可靠性和一致性.关键词 Web 服务;业务流程；异常处理;补偿业务生成图中图法分类号 TP311Research on Excepti on Han dli ng of Composite ServicesBased on Compe nsati on Bus in ess Process GraphShang Zong-Min Cui Li-Zhen Wang Hai-Yang Shi Y u-Liang（School of Computer Science and Technology, Shandong University, Jinan 250101Abstract To enforce consistency and reliability of composite Web services at run-time, this paper proposes a novel approach based oncompensation business process graph to addressing the problem of exception handling in composite services. According to compensationdependencies among tasks in business processes, the automatic generation of compensation business process graph is proposed.Compensation task, compensation goal and application model of service transfer are discussed in detail, and the relevant supportinginfrastructure and technique are introduced. Based on this, algorithms for automatic generation of compensation dependency andcompensation business process graph, as well as algorithm for exception handling during execution of composite services, are proposed.When exceptions are handled with forward- or backward-recovery methods during execution of composite services, the approach canguarantees compensation achieving, and also gives consideration to the problem that there are no compensation services or the cost toachieve compensation is too expensive. The mechanism described here improves self-adjustability and stability of composite services in thecourse of deployment and execution. Simulations prove that the approach can efficiently guarantee the consistency and reliability of compositeservices at run-time.Keywords Web services; business process; exception handling; compensation business process graph1 引言随着面向服务计算体系架构（Service-orientedarchitecture, SOA）的进一步推广和应用，将分布于Internet 中不同企业发布的 Web 服务有效组合，形成 满足软件开发者需求的服务流程，已经成为目前分布式计算研究的热点.由于 Web 服务具有异构、松耦合、 自治和动态的特性，由 Web 服务组合而成的业务流程 （简称业务流程）如何保证应用一致性，即在失败、异 常等情况下，组合服务的执行能结束于一致状态，是Web 服务组合应用的一个关键问题.软件服务协作中的事务支持可保证多个服务的 交互与协同获得可靠、一致的执行效果2,因此事务处理是系统应用一致性研究采用的一种重要方式.传统事务模型中“全有或全无”的原子性质由于过于 严格，无法适用于长运行、松耦合和自治的组合Web服务应用环境3.于是许多研究对传统事务模型进行 扩展，通过放宽事务的原子特性，来保证应用的一致 性2,4,5即业务流程的执行或者正常结束，或者通过补 偿取消已完成服务的执行效果.其中，事务的属性主 要靠可补偿和可重试来刻画.但是，这些研究中应用 一致性的保证是在一定前提条件下实现的：或者假设收稿日期：2008-04-05.本课题得到国家自然科学基金（60673130）和山东省自然科学基金（Y2007G38）资助.尚宗敏，男,1969 年生，博士研究生，主要研究方向为 Web 服务、工作流、事务处理.E-mail:.崔立真，男,1976 年生，博士，讲 师，主要研究方向为工作流、软件体系结构、分布式计算.E-mail:.王海洋，男,1965 年生，教授，博士生导师,主要研究方向为数据库、工作流、软件工程.史玉良，男,1978 年生，博士，讲师，主要研究方向为 Web 服务、工作流、数据库理论.8 期尚宗敏等：基于补偿业务生成图的组合服务异常处理方法研究2业务流程中每个服务都有相应的补偿服务与之绑定4；或者过于关注服务提供者的业务实现细节5,以牺牲 Web 服务的自治性为代价；或者在服务组合构建阶 段检查所选择服务的事务属性，通过组建可靠的业 务流程，来保证应用的一致性.另外，这些研究多集中 在业务流程的设计阶段，不能涵盖执行阶段的一致性 保障.由于处于一种动态、分布的环境,Web 服务可能 随时产生和消亡，网络的不稳定也会造成服务调用的 延时和随时的连接中断，另外 Web 服务自身也可能出 现故障，这都会造成业务流程运行时异常经常发生.为实现业务流程执行的一致性，异常处理机制作为解 决事务 ACID 过于严格的一种折衷方法被广泛采纳.一些通用的 Web 服务组合语言，如 BPEL4WS 对于异 常处理提供了异常捕获方法和异常的补偿机制，异常的处理措施由业务的开发者自己定义.但是在应用设计阶段预见所有的异常是很困难的7，尤其是处理那些不可预见的异常，因此在应用的执行阶段处理发生 的异常就显得非常重要 .当异常发生时，可采取向后 恢复或向前恢复方式来处理异常8.向后恢复是终止业务流程的执行并对已经执行完毕的服务进行补偿，流程可回退到初始状态.向前恢复是选择一个可替代 的服务来保证业务流程的继续执行.但是，如果业务流程的执行越过了不可补偿点，流程的回退将破坏原 子特性，违背流程执行的一致性.因此，补偿机制的有 效实现是异常处理的关键问题 .现实应用中，用户一般希望异常发生时应用系 统能够自动进行处理.从流程管理角度岀发，通常采 取调整业务流程模型或调整流程实例的方法9.而对web 服务组合而成的业务流程进行调整需要设计者 与用户的人工干预，无法满足快速多变的市场竞争需 求.如何在原先应用系统不变前提下，结合 web 服务动态、灵活、自治的特点在运行实例层面实现异常 处理，保证系统的继续执行，是组合服务走向实际应 用的一种有效途径.基于上述问题，本文提岀了一种组合服务执行 过程中基于补偿业务生成图的异常处理方法，实现组合服务执行的一致性和可靠性.主要思想是：将业务 层分为描述业务流程的功能业务层和描述补偿业务 生成图的补偿业务层，并与 Web 服务所在的服务层进 行分离，来定义多层的组合服务执行模型.根据业务流程中任务间的控制关联，定义业务流程中任务间的 补偿依赖关联，依据此补偿依赖关联建立补偿业务层 的补偿业务生成图.当组合服务执行发生异常时，不 需修改服务组合的业务流程，即描述业务功能的业务 层保持不变，在补偿业务层辅助下，通过服务层的 web服务等价替换、补偿、服务转让等操作，实现组合服 务在用户可接受的代价范围内回退或继续执行，确保组合服务执行的一致性.本文组织如下：本节介绍了研究背景；第 2 节是 相关工作的介绍；然后，基于提岀的组合服务执行模 型,通过定义业务流程逻辑模型，第 3 节给岀了补偿依 赖关系的自动生成算法；接下来第 4 节分别介绍了补 偿业务生成图及一种基于转让服务的补偿实现方法；第5节给岀基于补偿业务生成图的组合服务执行异 常处理算法；第 6 节通过一个旅行组合服务应用场景，对本方法的算法进行了仿真实验和结果分析；最后对 全文内容进行总结.2 相关工作许多研究通过高级事务模型来实现松散、长运 行系统中的ACID 事务管理例如 SagaS4采用补偿器 从语义上取消已完成的操作，应用发生失败时，系统能够回退到初始状态该思想已被 BPEL4WS10、WSCI11等标准采纳.但是，该模型假设所有服务都能 提供补偿功能，而且仅仅靠回退来处理异常也是不够 的.异常发生时，应用系统可能不希望回退到初始状 态,而希望处理这些异常继续向前执行(向前恢复).为实现组合 Web 服务应用的一致性，有关研究 将事务处理技术的可靠性，与工作流技术灵活的协同 能力相结合12,基于客户可接受终止状态(acceptabletermination states, ATS)来刻画异常发生后事务的松 弛原子性.但该方法仅局限于服务组合的设计阶段，没有涵盖运行阶段的执行保障，例如失败恢复等.而 且由设计者定义所有的 ATS 难度较大，与实际应用还 存在差距.为解决服务组合设计与实际应用之间的差距，有关研究利用恢复机制来保障服务组合的可靠性，如从组合服务的执行日志入手，采用挖掘技术来发现组 合服务模型和事务行为.然后，基于这些挖掘信息，根 据相应规则对不合理的组合服务进行恢复13但这些研究还是局限于服务组合的设计阶段，没有涉及运 行阶段的执行保障.在组合 Web 服务应用中，补偿作为一种常用的 回退恢复机制，得到了许多研究者关注.补偿机制最 早由 Gray14提岀，并被广泛应用于高级事务模型 (ATMs)15和事务工作流16中，以维持放松的原子特 性.在 ATMs 中,当事务 T 成功执行后，补偿事务 C 可 以消除其执行结果的影响.在事务工作流中，为业务流程中的每个任务定义了一个补偿任务，当已经提交的任务需要恢复时，相应的补偿任务被调用.但已有 的补偿机制与具体 Web 服务关联过于密切，而且对不3计算机 学 报2008 年具备补偿功能的 Web 服务没有有效解决方法虽有研 究提岀了多补偿方法17,来弥补补偿机制过于单一 问题,但仍然没有很好解决与具体Web 服务关联密切的问题.Hagen C.等通过定义组合服务自身的原子范 围(atomicity sphere)来实现业务流程的原子性要求，该方法可在参与业务流程的服务没有隐藏其业务细 节时,检查流程中每个服务的原子范围，构建可靠的组合服务，提高应用的一致性.但是，由于服务发布者 有自己独立的验证方法，协作时仍存在违背全局原子 范围的问题.Ye C. Y.等在该工作基础上，提岀了一种 基于进程代数的方法18,从私有进程构建原子等价 公共视图(atomicity-equivalent public view).即使某些 服务提供者隐藏了其业务实现细节，仍能通过对公共 视图组合的检查，建立原子范围的全局分析，从而创建可靠的业务流程.该方法对服务提供者增加了限制 需要其公开私有流程的公共视图.另外，这些研究仅涉及流程设计阶段应用一致性的实现，不能涵盖流程 执行阶段的一致性问题.Russell N.等19在对异常进行分类基础上，提岀 了基于流程的信息系统(Process-aware InformationSystems, PAIS)20中多种异常处理策略，与本文类似，主要考虑流程实例执行时的异常处理，但在补偿处理 时假设每个任务有相应的补偿操作，没有考虑补偿操 作不存在情况下的异常处理问题.ADEPT 系统21基于一系列调整操作来支持运行期间系统的自适应和 异常处理，主要是从工作流管理角度岀发，研究流程 模板层和流程实例层的动态调整，以及两个层面调整 后的相互影响问题.对已经执行完毕操作的回退、补 偿等问题考虑较少.3 补偿依赖关系3.1 组合服务执行模型首先我们将业务层分为描述业务流程的功能业 务层和描述补偿业务生成图的补偿业务层，并与 Web 服务所在的服务层进行分离，来定义多层的组合服务 执行模型.在功能业务层，基于 BPEL4WS 标准来定义 和管理业务流程中任务及任务之间的交互. BPEL4WS 是一种类工作流语言，通过模型和语法定 义,基于流程参与者之间的交互，来描述业务流程的行为.在补偿业务层，根据功能业务层的业务流程中 任务间补偿依赖关联，描述了相对应的补偿任务及补 偿目标等属性，以便查找相应的补偿服务.在服务层，通过对提供不同功能的服务进行分簇，将实现相同功 能的服务聚集，成为一类服务类型，便于等价服务的 查找与替换.而对某个具体服务，其功能的实现是通 过Web服务某个操作来完成的，并与业务层中相应任 务绑定.图 1 描述了业务层中业务流程任务之间及补 偿任务之间的关联关系，以及服务层中相应的服务和绑定的具体 Web 服务操作.从图 1 可看出，业务层中的服务调用可通过 WSDL 来描述，无论是功能业务层中的任务还是补偿 业务层中的补偿任务，都通过调用跨越单个或多个 Web 服务的操作来实现.为简单起见，假定每个任务 与一个 WSDL 描述的 Web 服务关联.WSDL通过定义 一种XML语法来描述网络服务，实现消息交换.在一 个WSDL 文档中，定义了几种类型的接口，每个接口 作为 Web服务的静态接口 .接口类型由多个操作组成 以输入或输出消息的形式来描述.业务流程中任务的 执行可转换为对WSDL操作的调用.服务层图 1 组合服务执行模型定义 1(业务流程的任务状态转移图).由于 Web 服务具有自治特性，在业务流程执行过程中难以对其 完全控制.根据 Web服务暴露给业务层的属性，将业 务流程中任务的状态定义为 :initial, active, fail, abort, cancel, complete.其状态转移图如图 2 所示.任务的初始状态为 initial,表示实现此任务的Web 服务已经就绪；向所绑定的 Web 服务发送 active() 激活命令，使其开始执行，此时任务的状态转为 active; 当 Web 服务执行成功，向所关联的任务发送 complete。消息，任务的状态转为 completed;若 Web 服 务执行失败，向所关联的任务发送fail()消息,任务的状态变为 failed;另外，可通过 abort()命令终止所绑定 的 Web服务，任务的状态变为aborted;也可通过cancel()命令取消正在执行中的Web 服务，任务进入cancelled 状态.failedfail()initial :activate(). active :图 2 任务状态转移图酒卿八Completedcancel。can celledabort。8 期尚宗敏等：基于补偿业务生成图的组合服务异常处理方法研究4图 2 中引发状态转移的命令分为两类：active(),abort(),cancel()由负责业务流程执行的协调器触发产生;fail(),complete()由 Web 服务内部自动产生.3.2 基于补偿依赖关系的业务流程逻辑模型本文采用 BPEL4WS 标准对 Web 服务环境中业 务流程进行定义的方法17，对描述业务功能的业务 流程进行定义.服务组合被视为一个业务流程，业务 流程中每个任务与服务层的某类服务相关联，并通过具体 Web 服务操作的执行来实现.定义 2 (业务流程逻辑模型Business processlogic model, BPLM).是功能业务层中各类任务相互 关联而形成的逻辑结构图.业务流程逻辑模型描述为 有向无环连通图,BPLM=G( T, E,仁 fout, CP, s, t)其中:1)任务集合T =t1,t2,.,tm.其中：tiWT(1 *：i States表示了集合 T 中每 个任务的状态类型,States= initial, active, failed, completed,aborted, cancelled,对应于图 2 状态转移 图中的所有状态.业务流程执行前所有任务的状态为 initial ;7) 函数prec,succ:T 2T获取业务流程逻辑模型中某个任务的前序和后继任务.若(ti,tj) E，则ti为tj的前序任务，而tj为ti的后继任务.8)ts是 BPLM 的起始任务,满足tsT，且prec(ts)=null.目前，支持业务流程描述和定义的协议或标准 有很多，如 BPEL4WS, BPML 和 OWL-S 等，其目标是 将业务流程定义和具体的服务实现相分离业务流程中使用的控制依赖关系依据 BPEL4WS 的定义共有 5个，分另U用 sequence, switch, while, flow 和 pick 来表示 顺序、选择、循环、并行及事件选择逻辑关系.与BPEL4WS 相对照，定义 2 中 sequence 与 BPEL4WS 中sequence对应； And-Split和 And-Join分别对应于 flow 中 start和 end 标签；Or-Split 和 Or-Join 分别对应 于 switch 或 pick中的 start 和 end 标签.而 while 操作 可通过转换为 sequence等方式来实现.根据业务流程逻辑模型中任务间的控制关系，给岀五种基本的补偿依赖公式：(F1) Lconnatetj，当且仅当()，二sequence Afin() sequence，即任务 ti和 tj之间是 sequence 关联；(F2)匚connate 2tj 当且仅当优代)Sd SpHt tj, tk-succ(ti),即tj与 tj、tk间是 And-Split 关联；(F3) (titj)compensatetk，当且仅当 fm(tk) = And -Join,三 prec(tk),即 I、tj与 tk间是 And _Join 关联；(F4)ti compensate(fk)，当且仅当 fout(ti)=OrSplit tj,tk 5succ(ti),即 ti与jtk间是 Or _Split 关联；(F5) *)compensatetk，当且仅当九)丄一 Join* 占三 prec(tk),即 ti、tj与 tk间是 Or -Join 关联.例 1.如图 3 所示的一个旅行组合服务，其中每 个任务的描述如下：任务t1表示获取客户的旅行需求 信息，任务t2表示订购航空公司的机票，任务t3表示预定某地的酒店，任务t4表示订租某地的岀租汽车，任务t5表示客户接受该旅行方案，任务t6是信用卡支 付，任务t7是银行转账，任务t8是通过特快专递给客 户相关票据.其中任务t2,t3,t4是并行关系，任务t6，t7是选择关系.该服务组合的业务流程逻辑模型为BPLM=G( T, E, fin, fout, CP, s, ti),其中 :Tt1,t2,t3，t4,t5，t6,t7，t8，Eei,e2，e3，e4，e5，e6，e7，S，e9，ei0fin(ti) Mnull,fout(ti) And Split,fm(t2)= fut(t2)sequence,fin(t3)fin(t4)fin(t5) fin(t6)fin(t7)fin(t8)compensatet5，-：t compensate 8Jt2eiCP =ti=fout(t3) sequence,= fut(t4)=sequence,兰 AndJoin, fout(t5)=Or -Split,=fout(t6) - sequence,二 foutD-sequence, Or-Join, fut(t8)=null,compensate(t2X/4)，(t2/V4)compensate心冲7)，心 57)5计算机 学 报2008 年图 3 一个旅行服务例子例 i 中可以看岀，在业务流程逻辑模型定义中9tie2A t3e5t5e3e6g8- t7ei08 期尚宗敏等：基于补偿业务生成图的组合服务异常处理方法研究6仅描述了相邻任务间的补偿依赖关系，而不相邻的任 务间没有体现依赖关系.实际应用中不相邻任务间也 存在补偿依赖关联.以图 3 旅行组合服务为例，当与任 务 t2绑定的 Web 服务执行发生异常时，即订购航空公 司的机票没有成功，业务流程须回退恢复时，应立即中.TP 和 EP 的并集经过进一步计算后即为整个业务流程的补偿依赖关系集合.算法 1.补偿依赖关系自动生成算法.输入:业务流程任务集合 T,有向边集合 E输岀:补偿依赖关系 CP取消与任务 ta(预定宾馆)和 t4(租车)绑定的 Web 服务 的执行；如果与任务 t3或 t4绑定的 Web 服务已经执行 完毕，则应对其采取补偿操作，取消已执行结果的影算法步骤：1. TP_；EP_CP2. for eachtI三 T响.由此可见，虽然任务 t2，t3，t4不相邻，之间也存在补偿 依赖关系.另外，假设与任务 t6绑定的 Web 服务执行 发生异常，业务流程须回退恢复时，不仅相邻的 t5与 t6有补偿依赖关系，不相邻的 t2，t3，t4也与 t6存在补偿依 赖关联，也要执行相应的补偿操作.因此，有必要对定 义 2 中的补偿依赖进行扩展另外，考虑到业务流程中 任务间控制关系数目较多，完全由用户来定义不太现 实,有必要设计相应的算法来自动生成任务间的补偿 依赖关系.在算法设计前，首先给岀几个定义和公式.定义 3.终止依赖关联和取消依赖关联abortYcancel t Ybrttj:表示与任务tj绑定的 Web 服务执行l|abort jj失败，业务流程须回退恢复时，必须终止尚未开始执 行的与任务t绑定的 Web 服务.ItIcanceltj:表示与任务tj绑定的 Web 服务执行失败,业务流程须回退恢复时，必须终止正在执行 的与任务t绑定的 Web 服务.I3.If fut(t )= sequence 4.for tsucc(tIfIn(tj) sequence5.TP：TP .ticompensatetj6.If fout(ti)丄And _Splitforall tjWsucQtiX7.TPTP _.tcompensate(tjsucc(ti)tj)8.If fIn(tI)丄 And _Jo In for all tjW prec(tI)9.TPTP _.( t(t )tj)compensatet10.If fout(tI)丄Or Splitfor all tj：5succ(tI)11.TPTP 一Jcompensate12.If fIn(tI) =0r Jo I n for all tz prec(tI)13.TPr TP1(t.prec(t.)tj)compensatetI14. m15. each(tcompensate(jj) TP16.17.18.19. for j =1 to m for k =1 to mIf j -k and (tj,tk)兰 EEPEP 一tjcompensatetk_J(tjcanceltk根据以上定义，可得到如下公式20. for each ( tI)21.mt ) WTPcompensate k /(F5)t|compensatecompensatetk= t|compensate22.23.其中：(t,tk) .-E)(F7)tjcompensate(tjtk)tj compensatetk-： tcancel kcompensatetjcanceltj土for I -：1 to mfor j =1 to mIf I -j and(ti,tj)EEP f EPticompensatetj- tIcanceltj_ti aborttj24. =tj= tk=tk其中:(tj,tk) -E)(F8) (tI厂 tj)compensatetk tIcompensatetjcanceltjYbt.abort jcompensate11cancelt Ybrttabort I25.CPTP_. EP；26. foreach(ti compensatetj) J CP27.If tk1 (tjcompensatetk)and(ti,tkbE28. CPlCP_.ti compensatetk29. =ti=弋=tj=5=tj其中：(t ,tj) -E)30. return CP3.3 补偿依赖关系自动生成算法下面给岀补偿依赖关系的自动生成算法根据3.2 节的介绍，分两步来设计算法.基本思想为：对业务 流程中的所有任务，首先根据公式(F1)-(F5),产生相邻 任务的补偿依赖关系，置入集合 TP 中;然后根据公式算法分析：对于一个业务流程 BPLM,假设|T|=n,BPLM 中前序任务(后继任务)数目为 m,根据业务流 程中任务间的控制关系，可知：%ax= n-2；mmin=1(起始任务除外).在算法执行时，生成相邻任务间补偿依赖关系 (2-14行)的时间复杂度为0(n2);而生成不相邻任务 间补偿依赖关系(15-29 行)的时间复杂度为0(n3).因 此，补偿依赖关系生成算法的时间复杂度为0(n3).(F6)-(F8),对集合 TP 中的补偿依赖关系进行计算，得 到不相邻任务间的补偿依赖关系，并置入集合 EP4.补偿业务生成图如前文所述，采用补偿方式消除已执行结果的影响，是利用向后恢复方法处理异常，保证业务流程7计算机 学 报2008 年8 期尚宗敏等：基于补偿业务生成图的组合服务异常处理方法研究8执行一致性的重要前提而业务流程中不可补偿点的 存在,妨碍了异常发生时流程的恢复.不可补偿点产 生主要有两方面原因：一是补偿需要付岀较大代价，不能在客户可接受的范围内恢复到未执行前的状 态；二是没有提供相应的补偿功能，无法消除已执行结果的影响.补偿不一定是某个已执行服务的简单逆操作，补偿可能由单个服务来实现，也可能由几个服务的组 合来实现由于 Web 服务具有自治、动态的特性，对某 个已执行完毕的 Web 服务进行补偿操作时，面对的情 况比较复杂:(1)补偿可由该Web服务提供的方法来 实现;(2)补偿由其他 Web服务提供的方法来实现；(3) 需要几个 Web 服务进行组合，共同来实现补偿功 能；(4)补偿实现时需要付出一定的代价(时间、费用等)；(5)没有提供单个 Web 服务或组合 Web 服务来实 现补偿功能.为实现业务流程执行回退时的补偿，确保业务流程执行的一致性和可靠性，提岀一种补偿业务生成 图方法，来实现异常发生时已执行服务的补偿本节介绍了补偿业务生成图，下节给岀了基于补偿业务生 成图的异常处理算法.补偿业务生成图的基本思想是: 在业务流程设计阶段定义客户可接受的每个任务的 补偿代价(时间、费用等).当业务流程中已执行完毕 的任务需要补偿时，根据与该任务绑定的 Web 服务执 行结果，为其补偿任务的目标(goal)赋值通过该目标 或对其进行分解产生的子目标，查找并绑定相应的补 偿服务，通过补偿服务的执行，最终达到补偿目的.对 没有提供单个或组合 Web 服务来实现补偿功能的情 况，提出一种服务转让的应用模式基于现有的 Web服务应用模型，对已经完成的 Web 服务执行结果进行 转换、封装和发布，供有相同需求的服务请求者调用.通过对 Web 服务执行结果的转让，达到消除执行结果 影响的目的.4.1 基于目标的补偿任务根据前文提岀的业务流程执行模型，与功能业务层中任务一一对应，在补偿业务层定义补偿任务.补偿任务可基于补偿目标属性值，在服务层查找符合要求的补偿服务，在用户可接受的代价范围内实现其 补偿功能由于目前的 web 服务标准 WSDL、UDDI、 SOAP 都不具备机器可以理解的语义信息，为了能使机器理解并自动处理信息，人们进行了以 RDF,OWL 为基础的下一代 Web 研究，利用语义 Web 服务技术使 服务语义可以被人机之间、机器之间相互理解.目前大多数研究利用语义方法(如 OWL-S)对服务的特征 进行描述.我们基于应用领域本体(例如旅游领域本 体)来定义补偿任务：定义 4(补偿任务 Compensation Task, CT).定义 为三元组:CT=(OO, CG, CS),其中：1) OO 是本体概念集合，是领域专家定义的 Web 服务组合的领域本体集合.例如旅游领域本体有机票、酒店、目的地等.2) CG 是目标集合.表示补偿任务的补偿目标集 合，包含多个本体概念.例如旅游领域中，用户可能需 要退订机票、退订酒店等，CG OO.CCGt,CGt2,.,CGtm，其中tiWBPLM .T(1兰i兰m),CGt表示与任务ti相关的补偿目标，其值在流程构 建阶段确定.3) CS是初始条件集合.描述已经执行完毕的 Web服务的执行结果，作为补偿服务执行的初始条件. 包含多个本体概念，例如机票日期、航班号、机型、 仓位、出发城市、目标城市、票价等，CS OO.CS mCSt1,CSt2,.,CStm，其 中tiWB P LMT(1兰i Em)，CSt,表示与任务ti的补偿服务相关的初始条件，其值 在与任务ti绑定的 web 服务执行完毕后确定.4.2 补偿目标的分解业务流程中补偿功能的实现，实际上是补偿任 务中一系列目标的实现过程，即通过领域本体库和Web 服务匹配器去寻找合适的补偿服务，这些补偿服 务都是通过 OWL-S 语言来描述的.但实际应用中，可 能寻找不到实现补偿目标的补偿服务.比如图 3 中信用卡支付(任务 t6)的补偿目标依赖于三个补偿目标：退机票钱、退酒店订金和退租车订金，而 t6的补偿目标不会由任何一个 Web 服务来完成.我们将 t6视为一 个高层的目标(VirtulGoal),这个目标可分解成退机票 钱、退酒店订金和退租车订金三个子目标.定义 5(子目标 sub-goal).目标 g 可分解为多个子 目标，g丄.每个子目标记为gi=SubOf (g) (i =1,2,.,n),子目标gi是目标g的 部分实现.组成目标 g 的子目标之间存在以下三种关联：SEQUENCE(gi,gj):子目标gi必须在gj执行 前得到实现,也称gj优先于gj,记为g. g2;AND(gi,gj)：子目标gi和g必须同时实现；XOR(gi,gj)：子目标gj和g只有一个需要被 实现也称gi和gj是互斥的；我们借鉴 HTN(Hierarchical Task Network)22,23技术中的任务分解机制，为没有寻找到补偿服务的高 层目标(VirtulGoal)专门定义一个特殊补偿服务，称为虚 Web 服务(Virtual WebService).该服务由领域专家 制定，是一个 web 服务，其发布与访问方式与普通 Web 服务相同，实现高层目标分解为子目标的目的.9计算机 学 报2008 年采用 Virtual WebService 的好处是利用 Web 服务的特 点,可将补偿服务的实现与应用系统脱离，在不修改原系统的情况下达到补偿目的；缺点是：需要领域专 家的人工干预.通过高层目标的分解，相应也造成补偿任务定 义中的CG 及 CS 内容的变化，于是可按照高层目标分 解的子目标，将该补偿任务分解为子补偿任务集合.子补偿任务的定义参见补偿任务，不再赘述.4.3 服务转让业务流程实际执行中，某些与任务绑定的Web服务执行完毕后是不能补偿的，例如根据客户的个性 化需求为其制造的特殊产品.依据 Web 服务应用环境 的特点，我们采用一个服务代理，将那些已经执行完 毕且不能补偿的服务执行结果进行转换和封装，作为一种新的 Web 服务(转让服务)来发布，供其他有相同 需求的服务请求者调用当有相同需求的服务请求者 调用该转让服务后，服务代理将通知原服务提供商，并将有关信息反馈给原服务提供商.服务转让也适用 于补偿代价过高的 Web 服务，该方法的实现框架如图 4 所示,转让服务的定义如下：定义6(转让服务Transfer Service, TS).定义为 四元组，TS=(OO, TD, TS, TC).1) 00 是本体概念集合(参见定义 4);2) TD 是转让服务的功能性描述,TD OO;3) TS 是原服务提供商对 web 服务的定义与描述, 包括原服务的 ID、服务名称、服务的商业实体以及服务的文本描述;4) TC 是转让代价约束集合，表示用户在服务转4.4 补偿业务生成图定义 7(补偿业务生成图 compensation businessprocess graph, CBPG). CBPG=G(CT, CE, CW, Cf, CC), 其中：1) CT 是补偿任务，见定义 4;2) CE 是有向边集合，表示补偿任务间的依赖关系e =(ct ,ctj)三CE表示了补偿任务cti和ctj之间存在补偿依赖.由于两个补偿任务间可存在多种类型 的补偿依赖，因此两个补偿任务间可能存在多条边.3) CW 是与补偿任务匹配的补偿服务集合.CW 4CWct,CWct2，.,CWctm，其 中cti：二CT(1乞m),CW表示与补偿任务ctj绑定的 Web 服务.有两种赋Cti值方式：一是静态赋值，在流程构建阶段，若与任务ti绑定的 Web 服务具备补偿功能，则将此 Web 服务的有 关信息赋值给CW;二是动态赋值，在流程执行阶段cti根据补偿任务cti的补偿目标CGt和初始条件CS属性值，利用 web 服务匹配器寻找合适的补偿服务CWcti.4)映 射 函 数Cf :CE ：CTypeCTypeT-：tY-brt.表示边 CE 所连接的两compensate cancel，abort J个补偿任务间依赖关系的类型.5) CC 是补偿代价约束集合，表示客户对于补偿 目标实现的可接受代价.在为补偿任务cti选择相应 补偿服务时，要充分考虑 CC 的约束值.由于补偿代价存在多种属性，客户对补偿代价 属性值的接受能力不同，因此要根据客户的代价可 接受程度，提供一个满意程度最高的补偿服务来实现 补偿目标.本文提供一个补偿代价度量模型来评价补 偿目标的满意程度，为补偿服务的优先选择提供定量 化的依据.利用补偿代价得到的补偿目标质量度量对 客户而言仅是一种参考24.可通过定义更多的指标 来构造复杂的度量函数，但是这样也使系统更为复杂目前，我们提岀的补偿代价度量模型主要考虑时间代 价(time)和费用代价(cost)两种属性.对于某一补偿服务的补偿代价度量值用以下公nM (cs)i生i 个代价属性最大值.度量值M(cs)越大，表示补偿服 务cs越符合客户的接受范围.M (cs)为负，表示补偿服务cs不在客户可接受的范围内.例如，假定退订酒 店的补偿服务csh代价属性取值为Qcost=5%,Qime=2sec;代价属性最大值分别为QcoaX=100%,Qtimax=10sec;客户可接受的代价属性分别为QcAst=10%，式来计算:其中,n 代表了代价属性总数目，w可0,1是依据客户偏好对第 i 个代价属性赋予的权重，QjA是客户可接受的第 i 个代价属性值，是预先规定的第-WinZ Wkk8 期尚宗敏等：基于补偿业务生成图的组合服务异常处理方法研究10Qte=3sec;权重Wc o亍0.8，wtime=0.6.利用上面公式计算补偿服务cs,的补偿代价度量值M (csj =0.07.与补偿任务类似，转让服务也有相同的代价度 量模型.下面给岀补偿业务生成图的构造算法，基本思想是：基于业务逻辑模型中的所有任务及之间的补偿 依赖关系，产生补偿业务生成图中的补偿任务、补偿 目标及补偿代价约束.对那些已经与流程中任务绑定 的 Web 服务，若提供补偿功能，则作为相应补偿任务 的补偿服务(静态赋值).若某任务不需补偿，则在补偿 业务生成图中去掉以该任务作为起点的有向边 算法 2.补偿业务生成图构造算法.输入:业务流程任务集合 T，补偿依赖关系集合 CP，所 有任务的补偿目标集合CG,补偿代价约束集合 CC输出:补偿业务生成图 CBPG算法步骤：1. CBPG.CT.CG CG，CBPG.CT.CS -,CBPG CC CC，CBPG.CE _ 彳;2. for eachtiWT3.if binding (ti,w) and compensate (w) =true4.CBPG.CWtiw;5.CBPG.CW CBPG.CW _,CBPG.CWct6.7.for each(ti compensatetj)CP8.if neednotcompensatqtj =false9.CBPG.CECBPG.CE 一( cti compensateCtj)10. 11.foreach(ti aborttj). CP or (1canceltj) - CP12.CBPGCECBPGCE cti話。“ ctj) orCBPG.CE- CBPG.CE 一(Cti cancelctj)13. 14. return CBPG算法分析：算法的时间复杂度主要与业务流程 任务集合 T 中的任务数目(步骤 2)及集合 CP 中的补 偿依赖关系数目(步骤 7、11)有关，假定 max(|T|,|CP|)= n,则算法 2 的时间复杂度为 0(n).另外，该算法虽生成了补偿任务之间的依赖关 联,但还不是完整的补偿业务生成图，其中许多属性值在业务流程执行过程中或在异常发生时确定(见算法 3).主要有以下几种情况：(1) 补偿任务的初始条件集合 CS,仅在某 web 服 务(Wi)执行完毕后，才能获得与该 web 服务相关的补 偿任务(cti)的初始条件值(cstj);(2) 异常发生任务(ti)需执行补偿时，若与其绑定的 web 服务没有提供补偿操作，则根据相应补偿任务 (cti)的目标CGt和初始条件CS,利用 web 服务匹配 器寻找合适的补偿服务并赋值给CW(动态赋值);(3) 异常发生时，对那些高层补偿目标(不能寻找 到相应的补偿服务，但可分解为存在补偿服务的子目 标),通过虚 Web 服务分解该目标，组合所有子目标的 补偿服务并赋值给CWct;(4)异常发生时，对那些不可补偿或补偿代价过 高(用户不能接受)的任务，通过转让服务的形式进行 发布与转让.5.基于补偿业务生成图的组合服务异常处理我们将组合服务执行过程中与Web 服务执行有关的异常分为两类：I类异常指接收到与任务绑 定 Web 服务执行失败的消息，或在规定时间内没有接 收到所绑定的Web 服务执行相关的信息(由于网络 故障、 Web 服务不可用、Web 服务自身故障等原因), 造成业务流程无法继续执行而产生的异常；H类异常指与任务绑定的 Web 服务执行完毕，但是由于执行结 果不符合用户的要求，或者其他原因造成业务流程向 后恢复而产生的异常.对这两类异常分别采用向前恢 复(等价服务替换)和向后恢复(服务补偿)方法进行 处理，重点讨论第H类异常情况下如何通过补偿来消 除执行结果的影响，保证组合服务执行的一致性.定义 8(等价服务 equivalent service).设s和s.为不同的Web 服务，如果按照应用语义，它们实现相 同的功能，则称si与s.互为等价服务，也称两者的功 能等价.函数。(得到实现业务流程中任务ti的所有等价服务集合.如何实现等价服务的聚集和分簇，找到一个满 意程度最高的Web服务,有关研究提出了多种解决办 法.如基于 Web业务生成图，根据服务的 QOS 属性, 使用混合粒子算法来查找最优的服务组合25等.由于不是本文重点，对此不展开论述.以下提岀一种算法，利用一个异常处理引擎(compensator)监控业务流程的执行，并处理执行过程 中发生的异常.算法基本思想是：当检测到业务流程 中与任务绑定的 Web 服务执行完毕，则立即将其执行 结果作为初始条件赋给补偿业务生成图中相应的补 偿任务;当检测到业务流程中某任务 tf状态变 为”failed”,或开始执行后，在规定时间内任务tf状态没有发生改变(I类异常)，则选择实现相同功能的等 价服务,激活并执行；当检测到业务流程中某任务 tf发 生异常，业务流程须回退并进行补偿时(H类异常),分三类情况来处理：1)若任务 tf不可补偿,则通过服务 转让达到补偿等同目的；2)若目标CG为高层目标，tf则调用领域专家为其制定的虚 Web 服务，根据分解成 的子目标寻找相应的补偿服务；3)若补偿业务生成图 中补偿任务 ctf存在绑定的补偿服务，直接调用执行 此补偿服务；否则首先根据补偿任务的初始条件CSt,寻找实现目标CG-的 Web 服务,作为补偿业务 生成图的补偿服务CWct然后调用执行.最后，对补11计算机 学 报2008 年偿业务生成图中与任务ctf有补偿依赖关联的其他补偿任务，激活其终止、取消或补偿等操作.算法 3. compensator。.输入:业务流程任务集合 T,任务状态 s,补偿业务生成 图CBPG.输岀:记录补偿任务、转让服务执行成功或失败信息 算法步骤：1. upon watching s(tj) =completed 2. for all binding (t, w) 3.CBPG.CT.CS, :resultsof w4. 5. upon watching s(t,) = failed or getT (t,) .tim6.select anothersjOe(ti)and bind(ti,Sj);7. send active() toti;8. s(ti) active;9. 10.upon watching needcompesatefor(tf) Mrueand s(tf) =completed11.if cannotcompensatetf)12.publish the result of tfwith TS;13.record service transfer information of tf;14.15.else if isVirtulGo al(CGh)16.for each(subCG 三 divide(CGt)17.search(subcw) by subCG ;18.CBPG.CWctCBPG.CWctf_.subcw19.excute( subcw);20.record execution informatio n of subcw21.22.else23.if not exit(CBPG.CWctf)24.search(cw) accordingt o CS” byCG” ;25.CBPG.C%. cw26.excut&CBPG.CWcj ；27.record execution informatio n ofCBPGCWctf;28.29.for each(tj |(cti cancelctf).二 CBPG.CE ands(ti) = active30.send cancel() to ti;31.s(tj)cancelled32.for each(ti) |(cti abortctf)三 CBPG.CEands(ti) initial 33.send abort () to ti;34.s(ti)aborted35.for eachti) |(cti CompensateCtf声 CBPG.CE36.needcompersatefor (ti) true37.return handling informatio n records ;38.算法分析：该算法的时间复杂度与补偿业务生成图中边及补偿任务的数目相关，若 max(|CBPG.CE|,|CBPGCT|)=n,则时间复杂度为O(n).另外，除了考虑自身的时间复杂度，该算法还与补偿服务的查找和执 行的时间复杂度密切相关.定义 9(可自恢复的业务流程).对于一个服务 组合的业务流程 P 当与任务绑定的 Web 服务执行发 生异常时，若向前恢复处理不成功，业务流程无法继 续执行；或向后恢复处理时，某些正在执行或准备执 行的 Web 服务不能被及时终止，或已经执行结束的 Web 服务不能通过补偿来消除执行结果的影响.那么 称业务流程 P 的执行是不可自恢复的，否则称 P 的执 行是可自恢复的.定理 1.业务流程在执行中应用算法3 可满足自travel processticket serviceshotel servicesbank servicesT4:user con firmT5:payhenton acco unt:Pticket paymentcompe nsati on图 5 一个旅行服务组合应用例子start5)ticket queryand orderbook ticket compe nsati onbook hotelcompe nsati onhotel queryand order(：312)hotel payme ntcompe nsati onsplit/jo in Andsplit/joi n Or flow .com muni cati on .8 期尚宗敏等：基于补偿业务生成图的组合服务异常处理方法研究12恢复.证明：采用反证法，假设业务流程 P 中与任务ti绑定的 Web服务执行发生异常时,P不满足自恢复.根据定义 9,可知有以下三种原因：(1) 业务流程 P 无法向前恢复.而根据算法 3,compensator 会选择一个等价服务替代原绑定服务来实现任务ti.若不存在替代服务或选择的替代服务执 行失败,业务流程会向后恢复，执行补偿操作回到执 行的初始状态；(2) 业务流程 P 向后恢复时，某些正在执行或准备执行的 Web 服务不能被终止.易知：当与任务ti绑定 的 Web服务执行发生异常时，业务流程 P 中正在执行 的是那些与ti并行的任务所绑定的 Web 服务.根据业 务流程逻辑模型的定义，这些任务与ti之间是通过And-Split 或 And-Join 来间接关联的(Or-Split 或 Or-Join 关联中，只选择一个任务来执行)，因此由 3.2 节中公式(F7,F8)及算法 1 中第 15-24 行，可知这些并 行任务间建立了终止依赖关联abort和取消依赖关联cancel.而 compensator 算