摘 要：随着IT技术的发展，互联网上服务数量逐渐增多，web服务器的数量也急剧膨胀。当请求到达时，如何合理进行调度，成为了研究的热点。以往人们常常关注于服务质量的需求，然而，近年来，随着系统能耗的迅速增长，如何提高能量效率，成为了亟待解决的问题。本文结合能量效率与服务质量，研究web服务器负载均衡问题中，能量效率与服务质量的共同优化问题。本文提出在线分布式负载均衡算法，无需对请求到达分布进行假设或预测，能够在逼近最优能量效率时，同时保障服务质量。数学证明及基于实际数据的实验，均表明了本文算法的有效性。

关键词：web服务器；调度；能量效率；服务质量

1 引言

随着IT技术的发展和应用，越来越多的web服务被发布在互联网上。承载这些服务的服务器的数量也急剧增大。当服务请求到达时，如何将该服务请求调度到合适的服务器上，成为了工业界和学术界的研究热点。以往人们考虑的因素主要有服务质量，如降低响应时间、提高吞吐率等。然而，近年来，随着服务器集群规模的增大，它们消耗的能量也剧烈增长。如何提高能源效率，降低运营开销，也吸引了人们的关注。因此，本文结合服务质量和能源效率，解决web服务器负载均衡问题中，服务质量和能源效率的共同优化问题。

事实上，服务质量的优化和能源效率的优化，存在着折中和平衡。要提高服务质量，常用的方法是采用更多的服务器、让服务器运行在更高的工作频率，不停地处理服务请求。在这种情况下，可以得到更小的响应时间，更高的吞吐率。然而，能耗不可避免地会增大，导致服务器的运营开销增大。

因此，本文研究服务质量和能源效率的折中，解决如何在提高能源效率的情况下，提高服务质量的负载均衡问题。

以往的负载均衡方法，大多需要假设或者预测服务请求到达的分布。如假设请求到达的分布服从泊松分布，请求服务的时间服从指数分布等。在此假设基础上，一些已有技术采用排队论的模型来刻画系统的请求到达以及服务的过程。还有一些技术采用马尔科夫模型来完成请求调度和服务管理。然而，在实际系统中，请求到达的过程往往具有波动性和突发性。因此，这些假设和预测的准确性很难保证。此外，随着互联网上服务越来越受欢迎，服务及服务器的数目急剧增多，负载均衡问题面临状态空间爆炸的挑战。因此，应用集中式的方法，如组合优化、动态优化等，会面临复杂度高、求解效率低的问题。

本文提出一种在线分布式的负载均衡算法。该算法不需要对请求到达过程分布和服务过程分布进行假设或预测，可以直接基于当前的状态，完成负载均衡的决策。基于李雅普诺夫优化理论，通过引入任意的参数 来实现服务质量与能源效率的折中，我们证明了本文的算法可以以 逼近最优能源效率，以 逼近服务质量。算法时间复杂度是多项式时间。此外，我们基于实际系统的web请求和服务质量数据，进行了实验验证。本文第2节介绍了具体的web服务器负载均衡建模、算法以及算法分析。第3节展开实验对算法进行了验证。最后，第4节总结了全文。

2 WEB服务器负载均衡

2.1 服务器负载均衡模型

如图1所示，是基本的服务请求调度和管理框架图。每一类服务都有不同的候选服务，分布在不同的服务器上。提供冗余的候选服务，有利于提高可用性和可靠性。代理主要负责服务发现，状态管理。当服务请求到达时，代理通过搜索发布的服务，找到和服务请求相匹配的候选服务，并且将这些请求分发给合适的候选服务。每个服务器上都有一个管理器，管理服务的开关状态，以及服务器的运行频率。

考虑系统中一共有类服务，用集合表示。第类服务的候选服务集合用表示，代表服务器集合。为了更具一般性，我们考虑异构的服务器。代表服务到服务器的映射。其中，表示服务器上部署了第类服务；否则，。用表示部署了服务的所有服务器的集合。将系统建模成离散时间的系统，每个时间槽用表示。表示每个时槽的长度。是第类服务每时槽内到达的请求个数。代理将这些请求调度到具体的服务器上。用表示在时刻，第类请求被调度到第台服务器的个数。那么，。每个请求的收益用表示。

用代表在服务器上的服务的状态。表示对应的服务是开着的；反之，表示该服务关着。用表示服务器在时刻的运行频率。所有可行的频率用集合表示。每台服务器在时刻的平均功率用表示。其中，是静态能耗，和是系统常数，和分别代表服务器的利用率和工作频率。定义作为服务器上分配给服务的资源比例，那么有，。除下服务器的能耗，系统中还有一大部分开销用于冷却设施。用Power Usage Efficiency (PUE)表示系统总体能耗与服务器能耗的比值。那么系统在时刻的平均能量开销用表示，其中是时槽每单位电量的平均收费。系统的能源效率用表示。

对于服务质量，本文考虑最受用户关注的指标：等待时间。根据little公式，等待时间与队列长度成正比。因此，本文用队列长度来刻画响应时间。在时刻，服务器上的服务的缓存请求个数，即队列长度用表示。本文考虑在长期时间段内的平均能量效率及队列长度。系统中长期时间的平均队列用。为了降低等待时间，我们致力于降低队列长度。

那么，web负载均衡模型可以建立成如下的优化模型：

    (1)

s.t.

   (2)

   (3)

    (4)

   (5)

这个优化模型涉及到很多不可预测的未来信息，如请求到达等。因此很难采用离线的算法求解。此外，随着服务和服务器的数量急剧增大，采用集中式的算法将面临时间复杂度高、效率低的问题。针对这些挑战，基于李雅普诺夫优化方法，我们将提出在线分布式的负载均衡算法，在2.2节中介绍。

2.2 在线分布式负载均衡算法

用代表队列矩阵。定义李雅普诺夫函数如下：。代表系统在时刻开始的拥塞情况。为了减小队列长度，我们致力于降低。定义李雅普诺夫漂移如下：结合队列长度与能量效率，我们定义综合函数为队列减能量效率：。下面给出定理1，证明该综合函数存在上限。

定理1.在每个时槽，针对任何算法，对于所有的，任意的参数值，如果每个时槽内到达的请求数存在上限，那么队列减能量效率综合函数存在上界：

(6)

我们优化队列减能量效率的上界，即(6)的右边。我们提出在线分布式负载均衡算法，可以将该问题分解成子问题，然后并行地求解。进一步，我们将在下一节证明，该算法可以逼近最优能量效率，同时减小队列长度。

在每个时槽的开始，在线分布式负载均衡算法制定如下决策，来最小化队列减能量效率的上界，(1) 请求分发，即决定给每一个候选服务分发多少个服务请求；(2) 服务管理及动态调频，即决定服务的开关状态，并且决定CPU的运行频率。下面具体说明。

(1) 请求分发。在每个时槽，在线分布式负载均衡算法决定请求分发，来最小化(6)式右边的第二项，也即等价于最大化它的相反数。更进一步，不同服务的请求之间是独立的，因此该问题可以分解成，针对每个自服务，求解请求分发的子问题。也即化简成对于每一类服务，求解如下问题：    (7)

s.t.   (8)

(7)-(8)可以看成一个扩展的最大权重问题。每个时槽，给每个子服务分配的请求数量的权重是。因此最优的决策是将所有的请求分配到的值最大的服务上，也即是，

其中，代表值最大的服务对应的角标。

(2)服务管理及服务器动态调频。我们的算法制定服务管理决策变量与动态调频决策变量来最小化(6)式右边的第三项。类似的，这可以转化成最大化其相反数。因为变量和在不同服务器之间是相互独立的，我们可以将该问题转换为对每一台服务器，并行的解决如下问题：

 (9)

s.t.  (10)

  (11)

问题(9)-(11)涉及到二元变量，因此它是一个扩展的混合整数规划问题。接下来，我们将充分发掘问题的特点，在多项式时间内解决该问题，并且能够保证求得最优解。

针对每一个给定的，原来的目标函数(9)可以改写成：

令。考虑到表达式对变量来说是一个常数，因此，对于给定的，(9)-(11)可以转化成，对于每个服务器，解决如下问题：      (12)

s.t.   (13)

(12)-(13)是一个二元整数规划问题。当，

决策变量被设置为1；否则，决策变量被设置为0。因此，原问题(9)-(11)可以通过枚举每个对应的最优解，然后将这些最优结果进行比较，得到最终的最优解。具体的算法如算法1-3所示。

算法1：在线分布式负载均衡算法(DOSM)

1：在每个时槽的开始，观察当前队列状态。

2：针对每一类服务，并行地解决最大权重问题(7)-(8)。

3：针对每一台服务器，并行地解决混合整数优化问题(9)-(11)。

4：

5：返回步骤1。

算法2：针对每类服务的最大权重问题

1： ；

2： ；

3：for all  do

4：计算；

5： if  then

6：；

8：；

9：end if

10：end for

11：for all  do

12：if  then

13：；

14：else

15：；

16： end if

17：end for

算法3：针对每台服务器的混合整数优化问题

1. ；

2. for all  do

3.for  to do

4.if  then

5.；

6.else

7.；

8.end if

9. end for

10.if  then

11.；

12.；

13. for  to do

14.；

15.end for

16.end if

17.end for

18. ；

19. for  to do

20.；

21. end for

下面考虑最坏情况下，该负载均衡算法的时间复杂度。包括两个部分，(1)请求分发，(2)服务管理与服务器动态调频。在请求分发部分，不同服务的请求分发决策可以并行进行；该过程涉及到对所有的进行一次遍历，因此时间复杂度为。服务管理与服务器动态调频部分，类似地，我们的算法可以针对每一个服务器进行并行决策。用表示，在所有，数量的最大值。针对每一个给定的，需要步操作来解决该二元整数规划问题，因此该部分的时间复杂度是。算法总体的时间复杂度是，是多项式时间的。

2.3 算法最优性分析

我们证明该负载均衡算法可以实现能量效率与队列长度之间的任意折中，无线逼近最优的能量效率，同时绑定住队列长度。根据每个时槽内到达的请求数目存在上限这一假设，目标函数存在上限和下限。我们在定理2中证明在我们的算法下，平均能量效率与队列长度均存在界限。

定理2：如果存在满足，其中是系统的容量域，那么在我们的算法下，对于任意的参数的值，平均队列长度存在上限：(14)

同时，平均能量效率存在下限：

(15)

其中是定理1中定义的常数。

定理2证明了在我们算法下，能量效率与队列长度之间存在的的折中。通过增大参数，算法得到的能量效率可以逼近最优值，但此时队列长度也会增大。在实际情况下，可以根据供应商的需求，设定具体的值。

3 实验验证

3.1. 实验数据

3.1.1. 负载数据

我们采用两组实际系统中的负载数据，来验证我们的算法。

第一组负载数据来自LHC Computing Grid (LCG)。这个项目是一个全球项目，包括40多个国家的170多个计算中心。LCG的数据由伦敦帝国理工学院的e-Science小组提供。记载的数据从2005年11月20日到11月30日，持续了11天的时间。从数据中，可以找到请求的提交时间、持续时间和资源需求。我们运用聚类的方法，根据持续时间和资源需求，将这些请求分成20类。每一类请求有50个候选服务。系统中一共有200台服务器。

第二个负载数据来自Blaise Pascal University of Clermont-Ferrand的LPC项目。LPC项目是EGEE项目(Enabling Grids for E-science in Europe)的一部分。我们同样从LPC数据中选择了11天的数据，接着根据持续时间和资源需求，把这些请求分成20类。

为了和电价更新时间一致(后面介绍)，我们将每个时槽的长度 设置为300秒。因此，在我们的实验中，一共有3,168个时槽。基于请求提交时间的记录，我们可以得到在每一个时槽中，请求到达的个数。图2显示了LCG数据中，每个时槽内请求到达的个数。可以看出，请求到达过程随着时间抖动。图3显示了LPC的负载数据。服务的速率设置为持续时间的倒数。

3.1.2. 电价数据

我们从纽约独立电力运营商的网站上获得了实际的电价数据(单位是$/MWHr)。这个网站每隔300秒，更新一次电价。为了和负载数据一致，我们从网站数据中选择了3,168个电价数据。图4中显示了3,168个时槽的电价数据。可以看出，电价存在周期性的波动，其周期大概为250个时槽，约等于一天的时间。

3.2. 实验结果

基于3.1节中介绍的数据，我们将本文提出的DOSM算法与其他三种算法进行比较：(1) Best Effort 算法，算法中，只要服务器上有未完成的服务请求，那么服务器就运行在最大的频率，并且所有的服务都开启，而其余的请求分发算法，和我们的算法一致；(2) Load-balanced 算法，请求按每个服务器的容量比例进行分发，而服务管理和动态调频部分和我们提出的算法一致；(3) 随机算法，即请求随机地分发给每个服务器，而其余部分和我们的算法一致。

图5显示了LCG系统在不同算法下的平均能量效率与队列长度。从图5可以看出，我们提出的算法能够得到最高的能量效率，这显示了我们的算法的有效性。而且我们的算法，队列长度比Load-balanced算法和随机算法的都低。结合能量效率与队列长度，我们的算法在稍微牺牲队列长度的情况下，能够实现最大的能量效率，最小的系统消耗。Best Effort算法的能量效率比Load-balanced算法和随机算法的都高，因为Best Effort算法能够在短时间内服务完请求，降低能量消耗。Load-balanced算法，其能量效率比随机算法还低，而队列长度比随机算法还高。这表明，Load-balanced算法在实际系统中，并不是一个好的算法。

图6显示了LPC系统中，我们的算法和其他三种算法的平均能量效率与队列长度。可以得出，我们算法的能量效率是所有算法中最高的，我们算法的队列长度，比Best Effort算法稍微高些，但比Load-balanced算法和随机算法小。同样地，Load-balanced算法在能量效率与队列长度两方面，都没有优势。

表1显示了在LCG和LPC系统下，这四种算法的执行时间(s)。针对每一个实验，我们运行了20次，来计算平均值。从表中可以看出，我们的DOSM算法和其他三个算法的执行时间差别不大。Best Effort算法的执行时间比其他算法算法执行时间稍小。

4 结论

本文研究web服务器的负载均衡问题。结合能量效率与服务质量，我们提出了在线分布式负载均衡算法，能够实现能量效率与服务质量的折中，在逼近最优能量效率的情况下，保障服务质量。我们的算法不需要对请求到达的分布或者请求服务过程分布进行假设或者预测，可以仅基于当前状态进行在线决策。算法能够并行执行，大大提高效率，降低执行时间。数学证明以及基于实际数据的实验，都表明了我们的算法的有效性。 

分享让更多人看到