面向软件即服务的负载均衡策略建模与分析

明 利，李 彤,2，秦江龙,2，郑 明，蒋旭东，谢仲文,2

(1.云南大学 软件学院，昆明 650500； 2.云南省软件工程重点实验室(云南大学)，昆明 650500)

(*通信作者电子邮箱qinjianglong@ynu.edu.cn)

面向软件即服务的负载均衡策略建模与分析

明 利1，李 彤1,2，秦江龙1,2*，郑 明1，蒋旭东1，谢仲文1,2

(1.云南大学 软件学院，昆明 650500； 2.云南省软件工程重点实验室(云南大学)，昆明 650500)

(*通信作者电子邮箱qinjianglong@ynu.edu.cn)

为提高软件即服务(SaaS)应用中资源的访问效率，提出支持SaaS服务重要特征的负载均衡策略。首先，结合SaaS服务的多租户和高度可伸缩两大特性，提出一种基于租户请求分流、在局部和全局两个层次伸缩的负载均衡策略；其次，对所提出负载均衡策略用Petri网进行建模并仿真；最后，将提出的负载均衡策略与轮询(RR)、随机和改进的最小连接(ILCS)负载均衡算法在总体响应时间和总吞吐量两方面进行比较。实验结果表明：在请求速率达到500请求/秒后，所提策略的总体响应时间和总吞吐量趋于稳定并优于另外三种算法。

软件即服务;多租户;可伸缩性;负载均衡;Petri网

0 引言

随着云计算的深入发展，软件即服务(Software as a Service, SaaS)作为一种新的软件交付方式得到了越来越广泛的关注。多租户(multi-tenancy)是SaaS的核心优势之一[1]。随着业务的发展及用户访问量的急速增长，SaaS应用必须支持可扩展性，这样才能有效利用系统资源[2]。

在云计算中，负载均衡是一项优化技术，是一种在服务器之间均衡地分配大量的请求的机制[3]，是支持SaaS应用高效分配海量请求的关键技术。它被用于提高资源利用率、减少延迟、缩短响应时间、提高系统整体性能。

文献[4]为了达到SaaS服务提供商的目标——利益最大化及客户满意度，提出了一种性价比较高的映射和调度策略，用一台虚拟机优化资源分配，同时也将服务质量(Quality of Service, QoS)参数、由不同类型的虚拟机造成的基础设施异质性及不同的服务初始时间考虑在内。文献[5]提出了一种面向租约功能类型的服务器负载模型和面向租约用户非功能需求的执行请求按需分配算法，在此基础上实现了一个面向多租约SaaS应用的负载均衡系统。文献[6]提出了改进的最小连接数算法，当检测到需要将某客户端连接进行重定向时，将此重定向连接到当前连接数最少的服务器，但是连接数最少的服务器并不一定是负载最小，所以此算法只在一定程度上实现了服务器之间的负载均衡问题。同样文献[7]也提出了一种改进的最小连接负载均衡调度算法，主要方法是实时地计算所有服务器的负载率并更新排序，当服务器超过最大负载率的时候向用户反馈错误信息并停止服务。文献[8]提出了临界加速递减请求分配策略，通过动态监测请求任务被分配后对各个服务器工作负荷造成的影响、服务器实际的工作负载状态的反馈及设定的服务器固有处理能力进行请求分配。文献[9]提出的一种基于随机理论调度模型将SaaS层描述成一种多目标的优化问题。为了提高整体性能，映射规则分析器主要负责将任务分配到合适的服务副本，弹性控制器负责云服务的弹性分配，降低了请求的积压量。文献[10]提出了改进的节流算法并用云端模拟器分析了其性能。文献[11]使用了主动监控和资源感知相结合的算法，对于每一个到来的请求都给予有效分配并将总体请求时间最小化。文献[3，12]的主要工作是对现存的启发式负载均衡算法(比如Min-Min算法[13])进行分类并在吞吐量、迁移时间、容错性等方面进行了对比研究，并且文献[3]对现有的蜜蜂觅食算法进行了扩展。

以上文献中提出的算法均从不同方面实现了负载均衡，但是到目前为止，专门针对云计算下的SaaS软件，并能体现其核心特征(如多租户、高度可伸缩性等)的负载均衡策略尚属鲜见。

SaaS环境下，一方面，一个应用往往供多个租户(租户往往是一个单位或组织)同时使用，一个租户下又拥有数量众多的用户，数量庞大的用户发出海量的请求；另一方面，SaaS作为云计算服务栈中离用户最近的一层，其背后有高度可伸缩的云资源的有力支持。在此背景下，如何提高SaaS软件响应海量请求的效率、如何充分利用云计算的高度可伸缩特征成为一个重要课题，如何设计负载均衡策略使之更好地发挥作用成为一个关键问题。

针对上述问题，本文立足SaaS的核心特征，提出一种基于租户请求分流、在局部和全局两个层次伸缩的面向SaaS服务的负载均衡策略，并以Petri网为形式化工具对策略进行建模分析。

1 本文思路

根据历史监测，业务负载通常表现趋势性、周期性和随机性，如果当系统在一年的某个特定时间内遇到大量并发请求，负载达到峰值，其性能会降低，这时若没有适当的增加系统的负载能力，系统的响应时间会变长，业务的失效率也会增加，从而导致客户满意度下降[14]，并且考虑到现有文献[4-13]中关于负载均衡研究的主要思路，鲜有结合SaaS服务特征的策略，所以本文的策略紧扣SaaS服务的多租户特征和云计算的高度可伸缩性特征，思路如下。

1)针对SaaS的多租户特性。考虑到一个SaaS应用往往供多个租户同时使用，一个租户下又拥有数量众多的用户，数量庞大的用户发出海量的请求。进一步，在SaaS环境下，不同的租户往往处于不同的物理位置，对于部分SaaS应用而言，不同的租户甚至分布于不同的国家、区域。另一方面，支撑SaaS应用的云计算技术使得响应海量请求的物理服务器也分布于不同的地理位置(每个不同地理位置的服务器集群是一个相对于全局的局部)。在此背景下，理想的情况是：发出的请求能在负载均衡机制的支持下，在网络通信代价较低的服务器上计算和响应，同时又不显著降低负载均衡器分发请求的效率。传统的通过动态监测服务器工作负荷的负载均衡策略显然无法满足要求，在SaaS环境下，本文提出基于租户请求分流的策略：首先根据网络通信代价、各个局部服务器集群的资源多少等因素建立不同租户与各个局部服务器集群之间的较优映射关系，然后根据不同请求所属的用户所在的租户，将请求分流到与该租户对应的局部服务器集群。

2)针对云计算的高度可伸缩性特性。SaaS作为云计算服务栈中离用户最近的一层，其背后有高度可伸缩的云资源的有力支持。云计算一个重要的特征和优点是：资源的高度可伸缩性，对资源的需求可以根据应用的需求动态地增加或减少。在此背景下，理想的情况是：在基于租户请求分流的策略的实施下，各个局部服务器集群都能高效地完成计算并响应，当某个局部服务器集群资源不够而导致响应时间过长时，可动态增加资源；当某个局部服务器集群资源过剩时，可动态缩减资源。但由于云计算看似源源不断的资源其本质来源于虚拟化技术[15]，因此受制于实际物理服务器的多少。因此，本文提出在局部和全局两个层次伸缩的策略：依据负载情况和拥有资源的实际情况，在局部(SaaS应用位于某个地区或专门服务于某些租户的分部服务器集群)和全局(SaaS应用的总部服务器集群)两个层次进行伸缩。首先，当检测到与请求匹配的局部服务器集群负载过重时，在局部环境增加资源，即“局部伸”以提高请求的响应速度；其次，虽然云在理论上是“资源无限”的，但毕竟受限于实际的物理资源，因此策略还增加了“全局伸缩”，当某个局部环境的物理资源无法满足要求时，将任务请求分配到某个资源充足的全局服务器上，即“全局伸”；反之，当检测到某个服务器集群资源过剩时，释放部分资源，即“局部缩”和“全局缩”。

2 面向SaaS服务的负载均衡策略分析

文献[16]中提到了SaaS应用的成熟度模型。SaaS应用的成熟度模型分为四级，其中在第四级中，为了更好地提高服务器集群的吞吐率并且降低响应延迟，在第三级的基础上增加了负载均衡机制，使系统更好地实现了可扩展性。

从架构层面分析，SaaS区别于传统技术主要表现在多租户模式和可伸缩性[17]。本文主要从SaaS服务具有的特性：多租户和可伸缩两方面着手，根据SaaS服务这两大优势，将不同租户发来的任务按一定的规则进行分配。具体过程如以下步骤所示。

1)通过多租户特征处理多租户的请求。

①将不同租户与各个服务器集群之间建立起较优的映射关系。

a)首先根据租户ID判断其物理位置：当有来自多个租户发来的多种请求时，首先根据租户ID判断其物理位置，因为SaaS软件的物理服务器集群也分布于不同的地理位置，所以将物理位置一样的租户的请求分配给物理上距其最近的SaaS软件的物理服务器集群，这样租户与执行请求的服务器集群之间可以建立起优化的关联关系，减少网络通信代价。

b)其次将同一物理位置的租户的请求进行分类：使用聚类的方法计算租户请求的相似度值，并设定一个阈值，如果相似度值小于已设定的阈值，则可以将这些租户的请求分配给与租户请求匹配程度最高的服务器集群。假设来自A…N的同一物理位置的租户的请求集合分别为X…Z,则相似度值μ=(X∩Y∩…∩Z)/(X∪Y∪…∪Z)。

c)计算服务器集群的当前负载状况：当前等待队列中的请求数量与服务器处理请求的速率的比值。

②建立起映射关系以后，按照服务器集群的当前负载状况(如果服务器集群处于正常负载水平，即还没到达瓶颈期)，并根据不同请求所属的用户所在的租户及其请求的相似度，将请求分流到与该租户对应的服务器集群。

2)利用SaaS软件的可伸缩性处理多租户的请求。

①如果与租户请求匹配程度最高的服务器集群达到瓶颈期，则利用SaaS的高可伸缩性这一优势先进行“局部扩展”——在局部环境增加用于处理租户请求的服务器(局部备用服务器)，如果局部有备用服务器处于正常负载能力范围内甚至是空闲，则利用局部备用服务器进行请求处理以缩短响应时间。

②虽然云资源在理论上是无限的，然而其受制于实际的物理资源，所以如果局部范围内没有可利用的服务器资源或者已被占用，则要在全局环境增加用于处理租户请求的服务器(全局备用服务器)，进行“全局扩展”，如果全局环境有处于正常负载范围内的甚至是空闲的服务器，则放入此服务器的等待队列中。

③如果局部及全局服务器目前都已不具备处理请求的能力，资源不足，则多租户的请求暂停处理，直到有服务器可以处理请求为止。

本文中2)提到的局部扩展及全局扩展体现了云计算的核心特征之一——可伸缩性中的“伸”这一特性。

图1为多租户的请求处理方法的活动图。

图1 多租户请求处理活动图

当然，局部和全局的服务器不可能永远处于满载的状态，当负载过低又被租户占用时，需要对服务器进行释放——即“局部缩”和“全局缩”，以便下次方便服务，所以进行资源回收并更好地处理已经分配出去的服务器是必要的。同时，资源回收要根据实际情况选择性能较好的回收策略，否则回收程度过大或者过小都会产生不良影响[18]。这恰恰体现了云计算的核心特征之一——可伸缩性中的“缩”这一特性。

3 基于随机Petri网的调度策略分析

3.1 基于Petri网的建模思路

本文基于图1对所提出的调度策略进行Petri网建模，建模思路如下：1)选用随机Petri网(StochasticPetriNet,SPN)作为建模的主要形式化工具。Petri网具有直观的图形表示，又具有严格的数学基础，而随机Petri网是通过给P/T网的每个变迁相关联一个实施速率得到的模型。大多数随机Petri网的性能分析是建立在其状态空间与马尔可夫链同构的基础上的。2)通过引入随机Petri中的时间变迁和瞬时变迁，可以将请求进行确定性地分发，而基本Petri网中的分发都是非确定性的。

3.2 相关定义

关于Petri网和随机Petri网的基本知识，这里只引用和本文相关的几个概念，其他的可以参考文献[19-21]。

定义1 三元组N=(S,T;F)为一个Petri网的充分必要条件是：

1)S∪T≠∅;

2)S∩T=∅;

3)F⊆(S×T)×(T×S);

其中：S是N的库所有限集；T是N的变迁有限集；F是N的有向弧集，称为N的流关系。

定义2 连续时间SPN=(S,T;F,W,M0，λ)。其中(S,T;F,W,M0)是一个P/T系统，变迁平均实施速率的集合为λ=(λ1，λ2，…,λn)。λi是变迁ti∈T的平均实施速率，表示在可实施的情况下单位时间内平均实施次数，单位是次数/单位时间。特别地，有时实施速率可能依赖于标识，是标识的函数。

要对系统性能进行分析，首先使用随机Petri网构造出系统模型，然后同构出该模型的马尔可夫链(Markov Chain， MC)，最后在基于MC的稳定状态概率下得到所要分析的系统性能指标。在求得稳态概率的基础上，可进一步分析一些性能指标。

1)库所中的平均token数，它可以看作是租户请求的队列长度，可利用此数值估算设备或者资源的利用率等：

(1)

2)token概率密度函数:

(2)

其中Mj∈[M0≻且Mj(s)=i。

3.3 基于多租户和可伸缩的负载均衡SPN模型

图2为基于多租户和可伸缩的SPN模型。在图2中，白色长方形表示时间变迁，黑色长方形表示瞬时变迁，白色圆圈表示随机Petri网中的库所，库所中的黑色圆点代表token，token的数量指请求的队列长度，实线框1和框2表示局部备用服务器集群，虚线框1和框2表示全局备用服务器集群，根据云的特点，其中局部备用服务器和全局备用服务器都为n台，受篇幅影响，本文在图2的基于多租户和可伸缩的负载均衡SPN模型中的备用服务器集群只分别画出两台，其他备用服务器集群用省略号表示。

首先对此模型作如下约定：1)所有服务器集群，即处理请求的变迁si，ri，mi，它们的处理速率是独立指数分布的；2)租户的请求不分优先级，即请求获得处理的概率是相等的；3)任一类租户请求的到达为泊松过程，一个到来的请求可以根据租户的特征将其分配给服务器集群中处理此类请求的服务器，当请求队列已满，则拒绝接收任何新到来的请求；4)1≤i≤n。

为不失一般性，假设租户可以分为z类，服务器集群数为n。下面对图2中各个库所及变迁的具体意义进行详细说明：

1)T1表示不同租户请求的到达，其平均到达速率为λi。考虑到SaaS租户往往来自于不同的物理位置，并具有不同的特征，与此同时，SaaS应用的物理服务器集群往往也分布于不同的地理位置；因此，当不同特征租户的请求到达的时候，变迁T1执行并由x1进行分配，这样经租户ID和特征分类过的多租户请求能够在较短时间内得到处理，由此能够在很大程度上为租户和执行请求的服务器集群之间建立起优化的关联关系，减少响应时间。

2)x1表示由变迁T1执行后到来的租户请求进行分配的库所，它根据变迁ti所关联的可实施谓词及实施概率来决定将租户请求放入哪个队列。

3)ti表示对库所x1中的所有租户请求进行分配的变迁。

4)fi表示接收经过分类后的请求的库所，它根据变迁ei和wi所关联的可实施谓词及实施概率来决定将租户请求放入到fi的某一个队列中，设其容量为f_buffi。

5)ei和wi表示对已经分类好的请求的分配变迁，以决定是将请求放入与租户请求匹配程度最高的服务器集群(亦或是局部服务器集群)进行处理还是放入全局服务器集群。

6)pi表示将用局部服务器集群处理的请求的缓冲队列，设其容量为p_buffi。

7)di指的是如果ri服务器处于正常负载水平，则通过di的执行将pi中已有的租户请求放入此类服务器的缓冲队列ai。

8)ai表示与租户请求匹配程度最高的服务器集群的缓冲队列，设其容量为a_buffi。

9)bi表示局部备用服务器集群的缓冲队列，如果pi中请求较多，并且ri吞吐量变低，则通过oi的执行将请求放入其中，设其容量为b_buffi。

10)ri表示局部环境下可以在正常负载水平下处理租户请求的服务器集群，其平均处理速率为r_vi。

11)si表示在局部环境下将对租户请求进行处理的变迁，即局部备用服务器集群，其平均处理速率为s_vi。

12)ki表示全局环境下的缓冲队列，设其容量为k_buffi。

13)ii表示为全局范围内可以为租户请求提供的资源，资源数为1。

14)mi表示为SaaS服务供应商提供的全局环境下的备用服务器集群，其平均出处理速率为m_vi。

15)c1表示租户请求处理结束，设其容量为c_buffi。

16)g1的含义：g1点火后将会把c1中的token释放掉，防止c1中的token数量超过其容量。

为了更加具体地说明本文提出的策略模型是如何执行的，下面给出执行过程的伪代码(如图2所示)：

输入：多租户请求到达的速率、变迁(服务器集群)ri,si,mi的平均处理速率及服务器队列长度阈值。

输出：库所ai,bi,ki中的平均token数(队列长度)及变迁si,ri,mi吞吐量。

为了保证基于多租户和可伸缩的负载均衡SPN模型在仿真过程中能成功执行完所有租户请求，将库所c1与变迁T1相连，箭头指向T1，其中在c1中设置服务器队列长度阈值16，同时将g1删除，这样可以构成一个循环网，只有当服务器队列中的所有租户请求被执行完成后才终止。

步骤1 变迁T1点火，多租户的请求到达在x1；

步骤2 经过判断租户的ID，识别出其所在物理位置，根据物理位置将请求分别分发到指定的库所fi；

步骤3 到达fi之后判断与租户请求匹配度最高的服务器集群缓冲队列ai中的平均token数是否小于bi和ki中的数量；

步骤4 if (N(ai)

与ai对应的服务器集群ri处理租户请求；

步骤5 if (N(bi)

与bi对应的服务器集群si处理租户请求；

步骤6 if (N(ki)

与ki对应的服务器集群mi处理租户请求；

步骤7 继续执行步骤2～6，直至所有请求被处理完毕。

3.4 基于多租户和可伸缩的负载均衡调度策略性能指标描述

基于多租户和可伸缩的负载均衡SPN模型的性能可由图2中的ti，ei，wi，oi，di的可实施谓词及实施概率进行描述。

1)变迁ti的可实施谓词为：根据第2章中的相似度值μ可知：

Y(ti)：∀i,1≤i≤n, (M(fi)

变迁ti的实施概率为：

2)变迁ei的可实施谓词为：

Y(ei):∀i,1≤i≤n,M(pi)

变迁ei的实施概率为：

3)变迁wi的可实施谓词为：

Y(wi):∀i,1≤i≤n, (M(ki)p_buffi)

变迁wi的实施概率为：

4)变迁di的可实施谓词为：

Y(di):∀i,1≤i≤n,M(ai)

变迁di的实施概率为：

5)变迁oi的可实施谓词为：

Y(oi):∀i,1≤i≤n, (M(ai)>a_buffi)∧ (M(bi)

变迁oi的实施概率为：

图2 基于多租户和可伸缩的负载均衡SPN模型

4 实验仿真和分析

4.1 实验环境、参数设置及实施方案说明

仿真程序使用JDK1.8.0_45和随机Petri网建模工具SPNP[20]开发，运行在一台CPU为IntelCorei7，主频为3.40GHz，4GB内存的PC上。

为了简化模型的求解，模型中参数的设置参考文献[20]中的方法，服务器队列长度阈值为16(经实验表明，当队列长度阈值超过16，则会出现状态空间爆炸)，变迁si,ri,mi的平均处理速率均设为3.0，多租户请求T1到达的速率设为9个值，分别为5.0，10.0，30.0，50.0，80.0，100.0，500.0，1 000.0，3 000.0。

实施方案：本文主要是对提出的负载均衡策略与轮询(RoundRobin,RR)算法、随机算法和文献[11]中提出的改进的最小连接(ImprovedLeast-ConnectionScheduling,ILCS)算法的总体响应时间和总吞吐量进行对比，对于这四种算法的数据获得过程，都是用SPNP软件首先对其进行建模，其次用C语言代码进行实现，并求得库所的平均token数及时间变迁的吞吐量，其会随着请求到达速率的变化而变化。进而利用这些数据，根据4.2节中的公式求得四种调度策略的总体响应时间及总吞吐量。

本文策略所采用的模型如图2所示，执行过程如3.3节中的伪码所示，由于篇幅限制，另外三种算法的模型不再画出。对另外三种算法建模的时候，在同样的实验环境下采取了与本文相同的时间变迁数量、平均处理速率、多租户请求达到的速率和队列长度阈值，用C语言代码对变迁的点火进行控制，且C代码的实现是按照这三种算法的思想具体实现。

4.2 模型评价标准

在一般的SPN模型中，性能指标可以通过模型的稳定状态概率求得。系统设计者在研究一种新的调度策略的时候，一定要考虑到一系列因素，比如系统类型和用户需求等，根据系统的类型，用户和设计者一定希望调度策略可以达到以下目标：吞吐量最大化、避免无限推迟甚至饥饿现象、响应时间和利用率之间达到一个平衡等[22]。在本文中，通过分析基于多租户和可伸缩性的负载均衡SPN模型的总体响应时间和吞吐量来评价系统的性能。总体响应时间和吞吐量可以分别表示如下。

1)令P[M]为情态M的稳态概率，则在稳态下变迁t的吞吐量可以表示为：

(3)

其中：E是使变迁t能够点火的所有情态集，u为变迁t的实施速率，u取不同的值时则吞吐量不同。

2)根据图2的SPN模型可以得知其总吞吐量TH为：

(4)

其中：TH(t)在式(3)中求出，表示稳态下变迁t的吞吐量，在本文中，t指si,ri,mi(1≤i≤n)。

3)图2的SPN模型总体响应时间RT为：

4.3 结果与分析

为了验证基于多租户和可伸缩性的负载均衡策略的可行性，进行了一组仿真实验，将此策略与RR、随机调度算法及ILCS算法进行性能比较。

表1和表2分别是在稳态概率下SPN模型中库所的平均token数及时间变迁的吞吐量。由表1和表2可知，当请求速率(每秒请求到达数)持续增大的时候，本文策略的SPN模型中的库所的平均token数及时间变迁的吞吐量越来越大，但是当请求速率增大到一定程度时候，其保持基本平衡，这说明本文策略的稳定性较好，当租户的请求源源不断的到来的时候先局部后全局的策略仍然可以保证请求被处理。关于RR算法、随机调度算法和ILCS算法得到的库所平均token数及时间变迁的吞吐量，在此只列出其总体响应时间和总吞吐量数据，如表3所示。

为了更加直观，图3和图4表现出了四种调度策略在请求速率不断增大的情况下的总体响应时间和总吞吐量。

表1 稳态概率下SPN模型中的平均token数

表2 稳态概率下SPN模型中的服务器总吞吐量

表3 四种算法的总体响应时间和总吞吐量对比结果

图3是实施四种调度策略时随着请求速率增加其总吞吐量变化的曲线。从图3中可以看出，随着请求速率的持续增加，四种调度策略的总吞吐量都在增加，但是请求速率达到30请求/s时，本文调度策略的吞吐量达到基本平衡，即请求速率即使再不断增大，其吞吐量呈小幅度上升，当请求速率达到500请求/s时，其吞吐量基本保持不变；然而当请求速率达到100请求/s时，RR算法和随机算法的吞吐量大幅度下降，因为这两种算法都没有考虑到服务器当前的连接数，进而导致其吞吐量不稳定，服务器间的负载不均衡；ILCS算法的总吞吐量在请求速率达到100请求/s之前呈上升趋势，略高于本文策略的吞吐量，但是在100请求/s之后开始呈小幅度下降趋势，略低于本文策略的吞吐量，因为ILCS算法定时地评估各个服务器的负载状态，处理性能极值等，同时还评估新请求的归一化负载率，整体来说，ILCS算法与本文的策略的性能相差较小，在请求速率达到1 000请求/s后几近重合。

图4为四种调度策略的总体响应时间对比。由图4可知，随着请求速率的持续增加，本文调度策略的响应时间在增加，当请求速率达到500请求/s时，系统的响应时间趋于稳定，即请求速率即使再不断增大，其响应时间基本保持不变，因为本文策略可以对租户请求进行更合理的分配，当负载持续增加的时候，可以进行局部伸缩甚至是全局伸缩，并且可以保证租户的请求总是能被处理而不至于拥塞过度，从而使整体负载水平保持平衡，体现出了SaaS的优势；而随着请求速率的不断增加，RR调度算法和随机调度算法的总体响应时间急剧上升，因为在这种情况下，系统的处理能力逐渐达到饱和而引起更多的租户请求得不到处理进而导致请求积压和总体响应时间增加；ILCS算法的总体响应时间略高于本文策略的总体响应时间，又优于RR和随机算法的总体响应时间，但是其波动稍大，稳定性较差。

图3 四种调度策略的总吞吐量对比

图4 四种调度策略的总体响应时间对比

因此从以上分析可以得知，从整体上来说，本文提出的调度策略性能较优于RR调度算法、随机调度算法和ILCS算法。

5 结语

随着云计算的深入发展，SaaS必然作为一种新的软件交付方式成为时代的潮流，并且借助负载均衡机制支持更多的租户并实现更好的可扩展性。本文介绍了一种基于随机Petri网的面向SaaS服务的负载均衡机制，实现了针对多租户和可伸缩性的负载均衡策略，在一定程度上提高了资源利用率并降低了系统开销，缩短了执行时间，并且避免了传统的负载均衡机制的不足。同时与轮询调度、随机调度和ILCS算法进行比较，结果表明，本文提出的算法的整体性能较好。如何在提高效率的同时也提高服务质量，降低拒绝概率，并且对模型进行精化与分解将是下一步研究课题的重点，同时将对负载类型分类并在SaaS平台上进行模拟实验。

)

[1] 白海石.WindowsAzure实战[M].北京：机械工业出版社,2014:4-80.(BAIHS.WindowsAzureinAction[M].Beijing:ChinaMachinePress, 2014:4-80.)

[2]GUOCJ,SUNW,HUANGY,etal.Aframeworkfornativemulti-tenancyapplicationdevelopmentandmanagement[C]//CEC2007:Proceedingsofthe9thIEEEInternationalConferenceonE-CommerceTechnology.Washington,DC:IEEEComputerSociety, 2007: 551-558.

[3]PATHAKKK,YADAVPS,TIWARIR,etal.Amodifiedapproachforloadbalancingincloudcomputingusingextendedhoneybeealgorithm[J].InternationalJournalofResearchReviewinEngineeringScienceandTechnology, 2012, 3(1): 12-19.

[4]WUL,GARGSK,BUYYAR.SLA-basedresourceallocationforSoftwareasaServiceprovider(SaaS)incloudcomputingenvironments[C]//Proceedingsofthe2011 11thIEEE/ACMInternationalSymposiumonCluster,CloudandGridComputing.Washington,DC:IEEEComputerSociety, 2011: 195-204.

[5] 汪德帅，张一川，张斌,等.面向多租约SaaS应用的负载均衡机制研究与实现[J].小型微型计算机系统,2012,33(1):71-77.(WANGDS,ZHANGYC,ZHANGB,etal.Researchandimplementationofloadbalancingmechanismformulti-tenantSaaSapplication[J].JournalofChineseComputerSystems, 2012, 33(1): 71-77.)

[6]AVERSAL,BESTAVROSA.LoadbalancingaclusterofWebservers:usingdistributedpacketrewriting[C]//IPCCC’ 00:Proceedingsofthe2000IEEEInternationalConferenceonPerformance,Computing,andCommunications.Piscataway,NJ:IEEE, 2000: 24-29.

[7] 陈燕升,张赞波,任江涛.改进的最小链接负载均衡调度算法[J].计算机系统应用,2015,24(7):88-92.(CHENYS,ZHANGZB,RENJT.Improvedminimumlinkloadbalancingschedulingalgorithm[J].ComputerSystems&Applications, 2015, 24(7): 88-92.)

[8] 郭成城,晏蒲柳.一种异构Web服务器集群动态负载均衡算法[J].计算机学报,2005,28(2):179-184.(GUOCC,YANPL.Adynamicload-balancingalgorithmforheterogeneousWebservercluster[J].ChineseJournalofComputers, 2005, 28(2): 179-184.)

[9] 赵少卡,李立耀,徐聪,等.基于SaaS的弹性云平台优化调度策略设计[J].计算机应用研究,2014,31(2):422-425.(ZHAOSK,LILY,XUC,etal.ElasticcloudplatformoptimalschedulingstrategydesignbasedonSaaS[J].ApplicationResearchofComputers, 2014, 31(2): 422-425.)

[10]DOMANALSG,REDDYGRM.Loadbalancingincloudcomputingusingmodifiedthrottledalgorithm[C]//Proceedingsofthe2013IEEEInternationalConferenceonCloudComputinginEmergingMarkets.Piscataway,NJ:IEEE, 2013: 1-5.

[11]RATHORER,SHARMAV,GOLAKK.Anewapproachforloadbalancingincloudcomputing[J].InternationalJournalofEngineeringandComputerScience, 2014, 2(5): 1636-1640.

[12]MEHMOODM,SATTARK,KHANAH,etal.Loadbalancingapproachincloudcomputing[J].JournalofInformationTechnology&SoftwareEngineering, 2015, 5(3): 100153.

[13]KOKILAVANIT,AMALARETHINAMDIG.Loadbalancedmin-minalgorithmforstaticmeta-taskschedulingingridcomputing[J].InternationalJournalofComputerApplications, 2011, 20(2): 43-49.

[14] 熊伟,李兵,陈军,等.一种基于预测控制的SaaS系统自适应方法[J].计算机学报,2016,39(2):364-376.(XIONGW,LIB,CHENJ,etal.Aself-adaptionapproachbasedonpredictivecontrolforSaaS[J].ChineseJournalofComputers, 2016, 39(2): 364-376.)

[15] 牟权,叶保留,陆桑璐.基于云计算的普适服务集成平台技术研究[EB/OL].[2016-03-15].http://www.itfront.cn/attachment.aspx?attachmentid=3072.(MOUQ,YEBL,LUSL.Atechnologyresearchofpervasiveserviceintegrationplatformbasedoncloudcomputing[EB/OL].[2016-03-15].http://www.itfront.cn/attachment.aspx?attachmentid=3072.)

[16] 叶伟.互联网时代的软件革命:SaaS架构设计[M].北京:电子工业出版社,2009:32-47.(YEW.TheSoftwareEvolutionoftheInternetAge:SaaSArchitectureDesign[M].Beijing:PublishingHouseofElectronicsIndustry, 2009: 32-47.).

[17]TSAIWT,BAIXY,HUANGY.Software-as-a-Service(SaaS):perspectivesandchallenges[J].ScienceChinaInformationSciences, 2014, 57(5): 1-15.

[18] 杜垚,郭涛,陈俊杰.云环境下机群弹性负载均衡机制[J].计算机应用,2013,33(3):830-833.(DUY,GUOT,CHENJJ.Fleetelasticloadbalancingmechanismincloudenvironment[J].JournalofComputerApplications, 2013, 33(3): 830-833.)

[19] 吴哲辉.Petri网导论[M].北京：机械工业出版社,2006:1-65.(WUZH.IntroductionofPetriNet[M].Beijing:ChinaMachinePress, 2006:1-65.)

[20] 林闯.随机PETRI网和系统性能评介[M].2版.北京：清华大学出版社,2005:19-62.(LINC.StochasticPetriNetandPerformanceEvaluationofSystems[M].2nded.Beijing:TsinghuaUniversityPress, 2005: 19-62.)

[21] 李彤.软件并行开发过程[M].北京：科学出版社,2003:11-15.(LIT.ConcurrentDevelopmentProcessesofSoftware[M].Beijing:SciencePress, 2003: 11-15.)

[22]SINGHA,GOYALP,BATRAS.AnoptimizedroundrobinschedulingalgorithmforCPUscheduling[J].InternationalJournalonComputerScience&Engineering, 2010, 2(7): 2383-2385.

ThisworkispartiallysupportedbytheNaturalScienceFoundationofChina(61379032, 61262024, 61462092),theScienceandTechnologyProgramofScientificResearchFoundationinEducationDepartmentofYunnanProvince(2014Y12).

MING Li, born in 1989, M.S.candidate.Her research interests include software dynamic evolution, cloud computing.

LI Tong, born in 1963, Ph.D., professor.His research interests include software engineering, software process.

QIN Jianglong, born in 1984, Ph.D., lecturer.His research interests include software process, software evolution.

ZHENG Ming, born in 1992, M.S.candidate.His research interests include software evolution, cloud computing.

JIANG Xudong, born in 1986, M.S.candidate.His research interests include software evolution, software process.

XIE Zhongwen, born in 1982, Ph.D., lecturer.His research interests include software dynamic evolution, cloud computing, software process.

SaaS-oriented modeling and analysis of load balancing strategy

MING Li1, LI Tong1,2, QIN Jianglong1,2*, ZHENG Ming1, JIANG Xudong1, XIE Zhongwen1,2

(1.SchoolofSoftware,YunnanUniversity,KunmingYunnan650500,China;2.KeyLaboratoryinSoftwareEngineeringofYunnanProvince(YunnanUniversity),KunmingYunnan650500,China)

To improve the efficiency of resource access in Software as a Service (SaaS) applications, a load balancing strategy combined with the important features of SaaS service was proposed.Firstly, the load balancing strategy was proposed by combining multi-tenancy and high scalability in SaaS service based on the distribution of request and global and local scalability.Secondly, the load balancing strategy model was constructed and simulated by a Petri net.Finally, this strategy was compared with Round Robin (RR), stochastic algorithm and Improved Least-Connection Scheduling (ILCS) load balancing algorithm in response time and throughput.The experimental results show that the response time and throughput of the proposed strategy become stable and they are superior to the other three algorithms after the request rate reaches 500 per second.

Software as a Service (SaaS); multi-tenancy; scalability; load balancing; Petri net

2016-07-18;

2016-08-14。

国家自然科学基金资助项目(61379032, 61262024, 61462092)；云南省教育厅科学研究基金理(工)科资助项目(2014Y012)。

明利(1989—)，女，河南安阳人，硕士研究生，主要研究方向：软件动态演化、云计算； 李彤(1963—)，男，河北石家庄人，教授，博士生导师，博士，CCF会员，主要研究方向：软件工程、软件过程； 秦江龙(1984—)，男，云南安宁人，讲师，博士，CCF会员，主要研究方向：软件过程、软件演化； 郑明(1992—)，男，安徽安庆人，硕士研究生，主要研究方向：软件演化、云计算； 蒋旭东(1986—)，男，湖南邵阳人，硕士研究生，主要研究方向：软件演化、软件过程； 谢仲文(1982—)，男，福建漳州人，讲师，博士，CCF会员，主要研究方向：软件动态演化、云计算、软件过程。

1001-9081(2017)01-0024-07DOI:10.11772/j.issn.1001-9081.2017.01.0024

TP

A