一种面向SaaS环境的工作流系统集成和负载均衡方法

张利永，段　荣，罗恒钰

(中国电子科学研究院，北京　100041)



工程与应用

一种面向SaaS环境的工作流系统集成和负载均衡方法

张利永，段荣，罗恒钰

(中国电子科学研究院，北京100041)

SaaS环境下的租户共用软硬件基础设施，负载均衡是实现可扩展、高性能SaaS系统的关键技术之一。本文关注SaaS环境下的工作流管理系统，研究其SaaS使能技术。首先，提出一种SaaS使能的工作流管理系统集成架构WfMS4SaaS；然后，重点研究工作流引擎的负载均衡方法，提出一种主动式的工作流引擎负载预测算法，根据引擎的当前负载和预测的执行开销调度流程执行请求。实验表明，本文的方法考虑了流程多样性带来的负载影响，可以更加公平地利用工作流引擎资源，更适合面向多租户使用的SaaS环境。

软件即服务(SaaS)；工作流；负载均衡

0　引　言

随着我军信息化建设的不断深入，军用信息系统的应用集成问题日益突出。工作流作为一种支持业务流程协同的应用集成技术在过去的二十余年中得到了广泛研究和应用，可以很好地满足信息系统之间的互联互通、相互协作等集成需求。然而，传统的工作流系统需要专门的技术支持、专业的人员维护，使得系统的建设、管理和使用成本高昂，也不满足军用信息系统一体化、服务化的要求。

近年来，“软件即服务”(Software as a service，SaaS)[1]作为一种新兴的软件基础设施构建方法和软件系统服务交付模式在民用和军用信息系统建设中得到越来越广泛的关注和应用。SaaS模式下，软件提供方以托管方式将软件部署在服务器上，用户通过网络“租用”软件的应用功能。这种模式具有管理集中化、应用网络化、用户规模化的特点，使得软件系统具有更低的建设成本、更低的应用门槛以及更好的维护性和扩展性，可以解决信息化建设过程中软件研制和使用方面的诸多问题[2]。

相对于传统的软件系统，基于SaaS的软件系统在体系架构、软件部署、运行机制、应用模式等多个方面有所不同。其中，通过运行在公共硬件和软件基础设施上的一个或多个应用实例同时满足“多租户”的使用需求，是SaaS使能软件系统的一个关键特征和必要条件[3-4]。为了使软件系统适应于SaaS环境下多租户对高性能、易扩展、性能隔离等方面的要求，需要针对软件系统的特点设计适当的负载均衡方法。

工作流管理系统(Workflow Management System，WfMS)与其他软件系统在基础运行环境、开发技术等方面具有一些共同点，已有的SaaS使能软件系统的研究工作可为WfMS系统设计提供有益的参考。但是，WfMS也有其自身组成和应用特点，面向SaaS的WfMS不是简单地将WfMS集中化、服务化，而是需要从WfMS组成架构、工作机制、使用流程等多方面进行研究。

本文主要关注面向SaaS环境的WfMS体系架构设计和负载均衡方法。首先，给出一种支持SaaS模式的工作流管理系统集成架构WfMS4SaaS；然后，提出一种工作流系统的工作负载指数，并基于该负载指数设计了流程执行调度算法，可以“公平地”利用WfMS4SaaS中的工作流引擎资源；最后，通过实现原型系统并与已有工作进行对比证明了本文负载均衡调度算法的有效性。

1　SaaS使能的WfMS集成架构-WfMS4SaaS

1.1基于服务的流程模型定义

工作流流程模型描述基本的流程定义元素和元素之间的关系[5]。随着面向服务架构(SOA)技术的发展，工作流流程模型已由传统的基于软件模块或组件的建模转变为基于服务组合和编排的建模。已有大量工作研究如何通过组合或编排web服务[6]实现特定的业务活动，典型的包括BPEL4WS[7]。本文的工作也是以Web服务作为组成工作流流程的基本活动，即基于服务的工作流，定义如下。

定义1基于服务的流程定义(PD) 是具有控制依赖和数据依赖关系的一个或多个web服务的集合，共同实现特定的业务功能。一个流程定义可以表示为PD=(S,E,ΣA,ΣCR,ΣDR)。其中，S表示开始活动，E表示结束活动。

ΣA={Ai|i=1,2,…,n}表示业务活动集合，每个业务活动在运行时将被映射到一个web服务。

ΣCR⊆ΣA×ΣA表示活动之间的控制依赖关系集合。控制依赖关系包含顺序、并行、选择、循环四类。

ΣDR⊂ΣA×ΣA表示数据依赖关系集合。如果Ai的输出是Aj的输入，则Ai和Aj之间存在数据依赖关系，此时称Aj数据依赖于Ai.

定义2流程实例(PI) 是流程定义的一次执行，对应一个活动实例序列，可表示为PI=〈AI1,AI2,…,AIm〉。其中，AIi∈PI是流程定义中的业务活动对应的Web服务的一次执行。

1.2WfMS4SaaS集成架构

针对SaaS环境下多租户的使用特点，在传统WfMS架构的基础上，设计了一种基于元调度的WfMS集成架构，见图1所示。

图1　WfMS4SaaS集成架构

WfMS4SaaS是一个包含两层工作流引擎的集成架构。工作流引擎集群由一组工作流引擎组成，提供解析并执行工作流定义的能力。工作流元引擎是引擎集群的管理中心和租户的使用入口，提供基础的SaaS使能能力。租户可以在WfMS4SaaS中创建并保存自己的流程定义，并在管理性、安全性、可用性以及性能方面得到隔离保障。Web服务资源由外部组织提供，不属于WfMS4SaaS的组成部分。

为了支持多租户的并发使用，面向SaaS的系统架构设计需要考虑管理、定制化、安全、可用性和性能等多方面的隔离措施[8]。WfMS4SaaS中的工作流元引擎提供多种通用功能和核心服务以支持SaaS模式。“管理隔离服务”为每个租户提供查看和修改与该租户相关的数据的能力。“定制隔离服务”以“自助服务”的形式为租户提供系统配置和选项的个性化定制能力。“安全隔离服务”使租户免于遭受共用WfMS4SaaS基础设施的其他租户带来的安全风险。“可用性隔离服务”检测诊断租户引入的故障，阻止故障传播给其他租户，并提供在线修复能力。“性能隔离”避免由于部分租户的潜在不良行为对其他租户的性能造成不可预测的不利影响，保证所有租户在性能使用方面的公平性。

本文主要关注WfMS4SaaS的性能隔离方面，支持负载均衡的工作流引擎调度方法为之提供基础和必要的支持。WfMS4SaaS中实现性能隔离的关键服务包括：

(1)请求队列管理服务

请求队列服务(RequestQueueManagementService，RQMS)是对租户提出的流程执行请求的管理容器和控制器。RQMS保证租户不能获得超出其预定的性能能力。同时，RQMS设计为具有自调节能力，避免在大量并发请求下WfMS4SaaS性能过载。

(2)成员引擎管理服务

成员引擎管理服务(MemberEngineManagementService，MEMS)提供成员引擎运行参数在线配置和引擎动态接入能力，使得WfMS4SaaS具有良好的扩展性和可管理性。

(3)负载感知服务

负载感知服务(WorkloadSensingService，WSS)包含两类感知服务，一是WSS监视租户请求的数量和速率，即监视WfMS4SaaS的负载输入；二是通过驻留在成员引擎上的负载监控代理获取引擎的实际运行负载。WSS为调度决策服务提供基本依据。

(4)调度决策服务

调度决策服务(SchedulingDecisionService，SDS)通过适当的调度算法将租户的流程执行请求调度到合适的成员引擎上。从租户的角度，SDS保障流程执行的服务质量满足租户的要求；从系统的角度，SDS将流程执行带来的负载公平地分配到成员引擎上，以提高系统整体的吞吐量。

2　WfMS4SaaS负载均衡调度算法

尽管工作流管理系统的负载均衡技术可以从传统的并行计算、数据库系统、中间件系统、web服务器集群等领域借鉴很多经验，但仍然具有其自身特点带来的诸多挑战。

首先，工作流流程的执行既涉及到工作流引擎，也涉及到由本地或远程服务实现的活动执行，需要识别出能够准确表征工作流执行的工作负载模型。其次，不同的工作流流程可能在逻辑结构和活动组成方面有较大差异，这将对WfMS造成不同的负载影响。尤其是，在SaaS环境下不同的租户请求执行不同流程的情况十分常见。因此，SaaS使能的WfMS应将工作流流程的多样性作为负载均衡设计的考虑因素之一。

2.1基本负载指数

识别并定义系统工作负载指标是设计负载均衡算法的第一步。对于基于服务的流程定义模型，其执行过程涉及到工作流引擎和web服务两方面。流程执行时，工作流引擎首先初始化一个活动实例(即映射到具体的web服务)，准备必要的输入数据，然后触发web服务的执行，图2举例给出了流程执行过程的阶段划分。由图2可见，一个活动实例的执行时间(TA)可分为两部分：工作流引擎内部执行时间(TE)和web服务执行时间(TS)。

图2　流程实例执行时间划分

当并发运行的流程实例数目(记为NPI)增加时，由于竞争使用硬件资源(如CPU、内存、磁盘IO等)和软件资源(如数据库连接、消息队列等)，TE也随之增加。经试验和分析NPI和TE之间的关系，文献[9]提出一种衡量工作流引擎负载指数并设计了调度算法LAPSA。本文将文献[9]中的负载指数称为工作流引擎的“基本负载指数”，定义如下。

定义3引擎的基本负载指数 (BasicLoadIndex，BLI) 假设最近一段时间[t-Δt,t]内引擎(E)完成的k个活动实例为{AI1,AI2,…,AIk}，对于AIi(1≤i≤k)，工作流引擎的执行时间为TEi，则引擎E在时刻t的基本负载指数记为BLI(E)，定义为：

实验表明,BLI(E) 与NPI之间具有近似的线性关系，可以反映一个引擎在不同时刻的负载状态，也可以反映不同引擎的能力差异，具有平台(软硬件环境)无关、实时性好、易于计算等特点。以基本负载指数作为引擎负载均衡的参考指标可以取得比Round-Robin调度方法更好的效果。

然而，BLI(E)没有考虑工作流流程定义的多样性。在SaaS环境下，流程定义在所包含的活动数目和逻辑关系方面可能有较大差异。因此，执行不同的流程定义为工作流引擎带来的时间开销也不相同，基本负载指数不能反映流程实例的这种差异性。

在图3的示例中，假设两个引擎E1和E2的软硬件环境相同，在时刻t，引擎E1和E2并发执行的流程实例数目分别为15个和10个。根据基本负载指数的计算方法，会有BLI(E1)>BLI(E2)。LAPSA以此作为调度参数，会将新生成的流程实例调度到引擎E2上。然而，由于存在循环控制关系，E2中的流程实例会生成并发的多个活动实例，而E1则只需完成较少的几个活动实例。因此，将新流程实例调度到E1上更为合理。因此，仅仅根据基本负载指数作为负载平衡的参考指标可能会带来“不公平”的调度结果。

图3　基本负载指数调度示例

2.2未来负载指数

基本负载指数的不足之处可以归结为两点：一是不能反映流程实例之间的差异性；二是不能反映引擎在未来一段时间内的负载状态。对此，在基本负载指数的基础上本文提出了引擎的未来负载指数，定义如下。

定义4引擎的未来负载指数 (FutureLoadIndex,FLI) 假设在时刻t，引擎E的基本负载指数为BLI(E)，并发执行中的n个流程实例分别为PI1,PI2,…,PIn。对于流程实例PIi，假设从时刻t到PIi执行结束，PIi新生成的活动实例数目为Ni，则引擎E的未来负载指数记为FLI(E)，定义为：

未来负载指数以引擎在时刻t的基本负载状态(BLI(E))和未来尚需要执行的活动实例数为基础，预测引擎在未来一段时间内的负载状态。相对于基本负载指数，这种“预先一步”的主动式负载预测方法能够更准确和更全面地反映引擎的负载状态。

为了计算FLI，一个关键的问题是如何计算Ni。由于流程定义中可能存在并行、选择和循环控制逻辑，流程实例的活动实例序列难以预先确定，因此难以精确计算Ni，而只能以预测的方式估算近似值。为了估算Ni，可以从两个方面入手。

一是静态预测算法：根据流程定义中活动的控制逻辑关系，计算当前执行中的业务活动到流程结束活动的距离作为Ni的估计值；

二是动态预测算法，根据已执行完毕的流程实例的活动路径，与PIi当前的活动路径对比，预测将来的活动路径，对该路径的长度求算术平均值作为Ni的估计值。

2.2.1Ni的静态预测算法

工作流流程定义可以表示为工作流图[10]，静态预测算法即基于工作流图。本文将工作流图进行了适当简化，以适应基于服务的流程定义。

定义5工作流图可表示为一个六元组WG=(ΣN,NS,NE,ΣS,ΣC,ΣE)，其中，ΣN是有限的节点集合，NS∈ΣN是流程的开始节点,NE∈ΣN是流程的结束节点,ΣS⊆ΣN是以web服务实现的活动节点(后文称为服务活动)的有限集合,ΣC⊆ΣN是选择/合并关系节点的有限集合，ΣE⊆ΣN×ΣN是代表活动节点之间控制关系的边的有限集合。

定义6最短后继活动序列 (ShortestSequenceofSuccessorActivities，SSSA)：对于流程定义PD，其工作流图为WGPD。对任意的Ai∈PD.ΣA，可以在WGPD中找到一条(或多条)从Ai到结束活动的最短路径，对每条最短路径，所有出现在该路径上的服务活动组成一个序列，称为Ai的最短后继活动序列，记为SSSA(Ai)。

2.2.2Ni的动态预测算法

对于给定的流程实例，通过对其流程定义的执行历史进行统计可以给出Ni的动态预测算法。

定义7活动路径(ActivityPath，AP) 流程实例PI是活动实例的有序集合，记为PI=〈AI1,AI2,…,AIm〉，对于任意的活动实例AIi∈PI，替换为AIi的活动定义后生成一个新的有序集合称为PI的活动路径，记为AP(PI)。

定义8后继活动路径的估计长度(EstimatedLengthofSuccessorActivityPath，ELAP)对于未结束的流程实例PI，AP(PI)=〈A1,A2,…,Aq〉，假设其流程定义为PD，PD已成功执行的流程实例集合为PIS。PI的后继活动路径的估计长度记为ELAP(PI)，计算如下：

(1)选取PIS的子集PIS′⊆PIS，满足对于任意的PIi∈PIS′，存在Aq∈AP(PIi)；

(2)如果PIS′=∅,则ELAP(PI)=0；否则按(3)计算；

(3)对于任意的PIm∈PIS′，Aq在AP(PIm)中首次和末次出现的位置序号分别为j和k，那么ELAP(PI) 计算如下：

ELAP(PI)=

2.3基于FLI的调度算法

基于工作流引擎的未来负载指数，设计了WfMS4SaaS中元引擎的调度算法，称为FSA(FLI-based Scheduling Algorithm)。在WfMS4SaaS中，负载监控组件负责计算对应成员引擎的未来负载指数FLI，元引擎收到租户的流程执行请求后，FSA将请求调度到FLI最小的成员引擎上。

3　实验验证

3.1实验环境

为了验证FSA的有效性，实现了WfMS4SaaS的原型系统，如图4所示。原型系统中包含两个流程定义和5台服务器。其中，PD1为简单的顺序流程，PD2为包含循环逻辑的复杂流程。元引擎(ME)实现了FSA、Round-Robin和LAPSA算法；成员引擎EL受限于硬件配置，提供低性能的流程执行能力；成员引擎EH1和EH2具有相同的硬件和软件配置，提供高性能的流程执行能力；另外，web服务服务器(WSS)提供web服务执行能力。硬件和软件配置见表1。

图4　实验环境

硬件配置软件配置MEELCPU:IntelP43.2G(SingleCore)MEM:1GDDR400WindowsXPTomcat5.0.28SunJVM1.5EH1EH2WSSCPU:Xeon1.6G(4Cores)MEM:4GDDRII800Windows2003Tomcat5.0.28SunJVM1.5Axis1.4

3.2实验1：引擎能力差异较大时的调度

图5　Round-Robin算法调度结果

图6　LAPSA算法调度结果

图7　FSA算法调度结果

3.3实验2：引擎能力差异较小时的调度

在SaaS环境下，更常见的场景是将不同的流程定义在性能能力相对一致的引擎上执行，调度算法的“公平性”是关注的重点。我们设计了评估调度算法“公平性”的指标参数，称为“引擎时间开销偏向度”，定义如下。

定义8引擎时间开销偏向度(Partiality of Engine’s Time Cost ，PEC)假设ES={E1,E2,…,En}表示一组性能能力一致的引擎集合，根据调度算法A将一组请求RS调度到ES中的引擎上，对于任意的Ei∈ES，执行流程实例的总时间开销记为∑TEi，{∑TE1,∑TE2,…,∑TEn}的标准差称为算法A执行请求集合RS的引擎时间开销偏向度，记为PEC(A)。

好的调度算法应该公平地利用性能一致的引擎能力，PEC的值也应越小。实验中，模拟两个租户C1和C2发送不同的流程执行请求。C1每隔随机的800～1 500 ms向元引擎ME发送执行PD1的请求，请求总数为100；C2每隔随机的800～1 500 ms向元引擎ME发送执行PD2的请求，请求总数也为100，ME将请求调度到EH1orEH2。相同的实验进行了5次，根据日志记录统计计算PEC，见表2和表3。

表2　LAPSA算法的PEC(5次实验)

表3　FSA算法的PEC(5次实验)

LAPSA算法的PEC平均值为488.75，FSA算法的PEC平均值为169.28。由此可见，FSA根据预测的成员引擎的未来负载，以“提前一步”的方式作出调度决策，有利于避免引擎大的负载波动。在引擎性能能力较为一致的环境中持续执行不同的工作流流程，FSA相比LAPSA能够更加公平地将负载调度到引擎上，因此更加适合SaaS环境。

4　相关工作

如同其他领域中的负载平衡，工作流管理系统的负载均衡也可分为静态负载均衡和动态负载均衡两大类。

静态负载均衡基于对系统的不变因素进行预先判断，并事先写好所有的策略，因此，在系统固定的情况下，负载的分布也是事先确定的。文献[11]针对局域网中的引擎数量可以确定的工作流管理系统，提出一种基于哈希映射的工作流引擎负载平衡方法。该方法为每一个工作流引擎与一个值段做映射，通过一个哈希函数对流程实例的ID计算哈希值，根据该值所处的值段，将该流程实例调度到相对应的引擎上执行。通过控制引擎所映射的值段的长度可以控制调度到该引擎上的流程实例的数目。

尽管实现简单，静态负载均衡方法带来诸多缺点。首先，人工静态评估引擎的能力十分困难，也不准确；其次，不能适应引擎运行时能力动态变化的特性；最后，当宿主环境发生变化时(如硬件配置变化)，需要人工修改调度策略，而不能通过自调节的方式满足SaaS系统可扩展性和可管理性的要求。

动态负载均衡方法可以根据系统的一些实时状态自动地动态调整调度策略，解决静态方法的缺点。[9] 提出一种支持WfMS动态负载均衡的负载指数(本文称为基本负载指数BLI)。该方法的优点包括：一是BLI可以以极小的系统开销方便地从WfMS中获取，二是BLI适合评估运行于不同软硬件配置环境中的WfMS的负载水平，三是BLI能够反映引擎当前的实时负载情况。BLI的主要不足是未考虑流程之间的差异性，详见前文所述。

本文基于“提前一步”的工作流引擎负载预测思路，研究并提出一种主动式的动态负载均衡调度方法。该方法在保留[9]中方法优点的基础上，考虑流程多样性带来的负载影响，更加适合面向多租户使用的SaaS环境。

5　结　语

SaaS使能系统的关键问题之一是如何为不同的租户提供性能隔离，良好的负载均衡技术可以为系统带来更好的扩展性和更高的性能，是实现性能隔离的基本要求。

本文主要关注SaaS使能的工作流管理系统，重点研究性能隔离技术，设计了一种面向SaaS环境的工作流管理系统集成架构，研究了工作流引擎的负载均衡方法，提出了一种主动式的调度算法。实验表明本文的方法十分适合SaaS环境下的工作流管理系统。

然而，SaaS使能的工作流管理系统尚有诸多问题有待进一步研究，包括与本文相关的Ni的更加精确的预测算法、系统的自调节机制，也包括需专题开展的管理隔离、定制隔离、安全隔离等多方面的多租户支持技术。

[1]G. Carraro and F. Chong, Software as a Service (SaaS): An Enterprise Perspective, Microsoft2. Corporation, http://msdn2.microsoft.com/, October 2006.

[2]颜世刚，张振中. 基于SaaS的军用软件开发模式研究[J]. 微处理机，2012(1)

[3]G. Gianforte, Multiple-Tenancy Hosted Applications: The Death and Rebirth of the Software Industry, Right Now Technologies Inc., www.rightnow.com, 2005.

[4]F. Chong, G. Carraro and R. Wolter, Multi-Tenant Data Architecture, Microsoft Corporation, http://msdn2.microsoft.com/, 2006.

[5]WfMC, Interface 1: Process Definition Interchange-Process Model[M], Ver. 1.1, Oct. 1999.

[6]W3C, Web Services Architecture Requirements. http://www.w3.org/TR/wsa-reqs, 2002.

[7]T. Andrews, F. Curbera, H. Dholakia, Y. Goland, J. Klein, etc., Business Process Execution Language for Web Services Version 1.1, BEA Systems, IBM Corporation, Microsoft Corporation, SAP AG, and Siebel Systems (2002), DeveloperWorks (updated February 1, 2005), http://www.ibm.com/developerworks/library/specification/ws-bpel.

[8]C. J. Guo, W. Sun, Y. Huang, Z. H. Wang, B. Gao, A Framework for Native Multi-Tenancy Application Development and Management[J]. In Proceedings of CEC/EEE 2007. pp.551-558

[9]L. Jin, F. Casati, M. Sayal, et al. Load balancing in distributed workflow management system[J]. SAC’01: Proceedings of the 2001 ACM symposium on Applied computing, New York, NY, USA, 2001, 522-530.

[10]W. Sadiq and M.E. Orlowska, Applying Graph Reduction Techniques for Identifying Structural Conflicts in Process Models[C], In Proceedings of the 11th International Conference on Advanced Information Systems Engineering (CAiSE ’99), Berlin, 1999, pp.195-209.

[11]T. Bauer, M. Reichert, P. Dadam: Intra-Subnet Load Balancing in Distributed Workflow Management Systems[J]. Int. J. Cooperative Inf. Syst. 12(3): 295-324. 2003

张利永(1980—)，河北人，博士，主要研究方向为综合电子信息系统软件的总体设计和集成技术；E-mail: sosoict@qq.com

段荣(1977—)，吉林人，硕士，主要研究方向为系统软件总体设计与集成技术；

罗恒钰(1986—)，河北人，博士，主要研究方向为系统软件总体设计与集成技术。

A Method for Workflow System Integration and Load Balancing in a SaaS Environment

ZHANG Li-yong

(China Academy of Electronics and Information Technology, Beijing 100041,China)

Achieving load balancing is essential to ensure better scalability and higher performance for a SaaS environment, in which requests from different tenants are satisfied concurrently by a single service instance over shared hosting resources. In this paper we focus on SaaS-enabling workflow management system (WfMS). First, we explore some key issues in architecting a WfMS that enables SaaS model and propose our prototype-WfMS4SaaS. Then we propose a proactive load balancing algorithm, by which requests from different tenants are scheduled according to workflow engines’ current capability and the predicted cost of executing the process instances. The experimental results show that the algorithm can distribute workload more fairly when continually executing diverse workflow processes on uniform workflow engines than the formerly presented ones, and thus more suitable for SaaS Environment.

SaaS; workflow; load balancing

10.3969/j.issn.1673-5692.2016.04.015

2016-06-01

2016-07-10

TP315

A

1673-5692(2016)04-417-08