基于排队论的异构数据中心性能及能源管理策略

孙 健，廖 丹，李 可，巩 玉，孙 罡

(1.电子科技大学光纤传感与通信教育部重点实验室 成都 611731；2.西南交通大学信息科学与工程学院 成都 610031)

对于互联网服务与云计算不断增长的需求使数据中心内运行的服务器数量也由几百台迅速增至几万台，因此数据中心的电量开销巨大。例如，2011年，美国数据中心的能耗就达到了每年1 100万kW/h[1]，同时其低负载的数据中心能耗是最大能耗的65%左右[2]。这是因为所有的数据中心都是根据高峰时刻的负载设计的，即一个数据中心的平均负载水平只有最高负载的60%[3]。

有很多关于数据中心节能的研究[4-8]，寻找有效的方法在低工作负载时期关闭暂时无用的服务器非常重要[9-10]。当数据中心的负载增加时，这些服务器可再次开启。然而，这一项操作可能会使一些服务延迟，且对等待时间、业务阻塞率、系统平均业务数量等性能参数产生影响[9]。当服务器减少时，一些业务可能会遇到不可忽视的延迟，甚至可能堵塞。因此，在限制能耗的同时保持良好的性能有着重要的意义。

许多关于数据中心的研究都建立在所有服务器均有相同处理能力的同构环境假设上[9-10]。而实际上，数据中心会根据容量的增加以及规格的变化不断升级服务器[11]。随着时间的推移，最终数据中心将由一系列不同处理能力的异构服务器组成。在异构环境里分配业务时，不同的分配策略会导致功率效率的明显不同。譬如，一些业务在某个特定服务节点上要比在其他节点上运营得要快，这就意味着更少的处理时间以及更低的能耗。因此，在异构环境下选择需要被关闭的服务器又是一大挑战。

基于以上两点建立数据中心模型，其中排队系统为任务单独到达、任务缓存容量有限的M/M/n+m1+m2数学模型。系统中所有的服务器根据其处理能力被分为3组。假设任意发送到数据中心的业务都在合适的服务器节点中接受服务，一旦服务结束，业务离开数据中心。基于实时的负载，根据在队列长度上设置的阈值来开启备用的服务器，根据系统中的总业务数量来关闭备用服务器，从而达到动态调整服务器数量以节约能源的目的。此外，采用优化策略来寻找最佳阈值。

1 相关工作

近年来大型数据中心中的能源利用率以及性能管理获得了大量的研究关注。这些研究工作可分为两类：动态资源管理和静态资源管理。静态资源管理的实施吸引了不少研究。文献[12]阐述了一种最优化问题得到一个服务器簇中已知工作负载的最佳资源规划策略。然而，由于这种策略通过过度资源供给来满足高负载下的性能要求，该策略将消耗过量的能源。因此，近期更多的工作都围绕根据实时负载开启或关闭服务器的动态情形展开[10-11,13]。文献[10]也提出了一种动态调整运行中的服务器的方案，以寻找消耗能量与服务质量之间的平衡。文献[13]则通过建立数学模型来权衡数据中心能耗成本最小化与互联网服务利益最大化。

一些关于衡量能源与性能的研究都采取了排队论。文献[11]探讨了单服务器与多服务两种模型，其中建立时间是常值，服务时间和到达时间间隔都服从负指数分布。同时还讨论了时变到达的解决方法；文献[14]讨论了类似的问题，但它提出使用马尔科夫链来预测未来服务需求以判定需要激活的服务器数量。文献[15]提出了一种评估等待时间与功率折中的理论模型。

最领先的研究工作中已经考虑到了异构性，包括异构多核结构的评估。文献[16]探讨了在数据中心内将有限的能量分配给多个异构的服务器从而最大化性能的方法。文献[17]假设数据中心内所有服务器相同，重点研究了能耗与性能的多目标优化。本文将要探索多台异构服务器的数据中心内，性能限定情况下的能耗最优化。

2 系统模型

图1为根据不同处理能力及耗能状况分成的3组异构服务器。3组服务器的数量分别为n、m1、m2台。

假设每个服务器每次只能接受单个业务，业务到达服从均值为λ的泊松分布，服务时间服从均值为µ的负指数分布，那么，该系统可以被认为是M/M/n+m1+m2的排队论模型。一个分组中的业务首先被分配给第一组的空闲服务器。如果第一组中没有空闲的服务器，那么该业务被迫进入队列等待服务器完成当前业务。服务器完成当前业务后将选取队列中的业务。

图1 系统模型

在初始阶段，系统只开启第一组服务器。如果队列中的业务数目多于θ1，也就是系统中总的业务数目多于n+θ1时，那么系统启动第二组服务器。如果系统中总的业务数目低于n，系统关闭第二组服务器。同理，在第二组服务器已经启动的情况下，如果队列中的业务数目多于θ2，第三组服务器开启。如果系统的总业务数目低于n+m1，系统将关闭第三组服务器。

由于服务器的状态可能是开启或关闭的，因此需要建立服务器的状态转移模型，如图2所示。图2a给出了第一组服务器的两种状态，即忙碌或空闲。处于忙碌状态的服务器完成了当前业务且队列中没有业务时，该服务器的状态将转为空闲。图2b展示了第二组服务器和第三组的服务器更有效节能的状态模型。该状态模型包括忙碌、空闲、关闭3个状态。系统能够根据负载实时启动、关闭第二组服务器和第三组服务器。

图2 服务器状态模型

3 分析模型

采用排队论对第2节提出的节能数据中心模型进行数学建模。系统中多个服务器的最佳开启阈值是利用排队论实现节能的关键问题之一。

3.1 马尔科夫链

图3为系统的状态转移图。由于该系统是M/M/n+m1+m2排队模型，首先要定义状态空间。在马尔科夫链中，静态概率就是系统中每个状态服从静态分布的概率。用随机变量x(i,j)表示静态概率，其中i，j分别表示系统中总的业务数量和服务器的状态。j=0时，只有第一组服务启动。j=1时，第一组服务器和第二组服务器都被启动；j=2时，第一组服务器、第二组服务器和第三组服务器都启动。基于状态空间以及状态转换，用和表示系统中服务器的3种宏观的工作状态。利用图3中的马尔科夫链和马尔科夫链的状态转移概率守恒公式，可以得出以下结论：

首先考虑系统中只有0～i+θ1个服务并且只有第一组服务器开启的情况。其宏观状态的状态转移为：

图3 状态转移图

3.2 闭型解

对3.1节的状态公式进行迭代可以得到每个系统的状态概率：

推出：

因此当n+1≤ i≤n+θ1−1时，可以得到：

当n+2≤ i≤n+θ1−1时，可得：

为了进一步简化表达式，先定义：

因而当n+θ1+1＜i＜n+m1时，有：

可求得：

当n+＜m1i＜n+m1+θ2时，有：

为了简化再定义：

当n+m1+m2≤i时，可得：

最后，以上所有概率相加之和应为1，即：

因此x(0,0)可以求出，进而各个状态的概率都可以求得。

3.3 最优化模型

当得到状态概率的值后，就可以对数据中心系统的性能进行度量了。

1)平均意义上的队列长度：

2)到达系统的每个业务平均意义上的等待时间：

下面给出本文的最优化模型。优化目标是最小化数据中心的能量消耗的同时保证数据中心系统的性能不被影响，即每个业务的平均等待时间不超过参数α。因此需要推算出系统达到最小能耗所需的最优阈值θ1和θ2。

最优化目标：

约束条件：

由式(23)和式(24)可得总功率Ptotal与参数θ1和θ2是非线性关系。即使参数θ1和θ2已知的情况下，数据中心能耗系统的各状态概率的求解仍然是一个复杂的问题。故最优的阀值θ1和θ2无法通过上述模型直接求得。因此本文采用另外一种方法，即在θ1和θ2的取值范围内通过上述方程求解系统各个状态的概率，然后通过各个状态的概率得到相应的目标函数值Ptotal，最后对比找到最优开启阈值θ1和θ2。但这是一个NP问题。因所求参数θ1和θ2与最优目标为非线性关系且随着参数θ1和θ2取值范围的扩大，求解复杂度和方程的次数均呈指数增长。

4 实验与结果分析

4.1 仿真方案

实验环境为C++，电脑配置为3.0 GHz Intel CPU、4 GB内存。本文所有仿真结果中服务器的能耗按照文献[13]给出的Intel Xeon E5320进行计算。表1给出了本文所有仿真结果的参数设置。

表1 仿真参数设置

表中，N表示服务器总数，α表示平均等待时间，表示第k组服务器的工作功率，表示第k组服务器的空载功率。

4.2 运行结果

图4反应了系统消耗功率和等待时间随时间变化的情况，其中总等待时间被设置为90 s。同时，该图从一定程度上反应了本文提出的服务器调度方案的原理。仔细观察该图可以发现，在系统刚启动时，平均等待时间随着业务数目的增大而加长。这是因为更多的业务进入队列等待执行，因此平均等待时间加长。然而，当业务数目增加到一定程度，即队列中的业务数目超过阈值θ1时，平均等待时间开始急剧缩短。这是因为第二组服务器的开启，队列中的业务被第二组服务器执行。同理，当总业务数超过N+θ1+θ2时，第三组服务器启动。同时，系统能耗随着第一组服务器和第二组服务的开启而增大。当第三组服务器开启后，系统能耗基本保持稳定，但是当第三组服务器关闭后，系统能耗降低。这是因为随着工作服务器数目的增加，系统能耗增加。为了能够清楚的看到系统能耗情况，图中的实线框给出了稳定的系统能耗，实线框的左边框对应的时刻是第三组服务器关闭的时刻。

图5为不同参数阀值下的系统能耗值。从图中不同阀值的能耗曲线可得，虚线所代表的系统功率值大多数情况下稳定在150 W左右。而实线大多数情况下稳定在250 W左右。而虚线时参数θ1和θ2最大，实线时参数最小。因此可以推断出如下结论：1)参数值θ1和θ2设置较大时，系统功率变小。因为较大的参数值会减少开启的服务器个数；2)当阈值θ1和θ2较高时，功率消耗的抖动也更加频繁。由此可得当阈值较低的时候，功率的波动会更加频繁。

为了探讨参数λ和μ与系统功率的关系。图6分析了不同λ和μ情况下的系统功率情况。除了参数λ和μ不同以外，其他参数都是固定不变的。可以看出系统消耗总功率在同一组参数的情况下是随着组数的增长而下降的。当在增大参数μ时，系统的平均服务时间会加长。这将导致系统的等待队列变长。因此会唤醒第二组和第三组服务器加入工作中，故第二组和第三组的功率会增加。当增大参数λ时，系统的业务到达率会变大，这将导致队长减小。因此第二组和第三组的服务器被打开的概率减小，故其能耗降低。

图4 系统消耗功率与等待时间随时间的变化图

图5 θ1 与θ2下系统消耗的功率随时间变化的示意图

图6 不同λ与μ组合下的系统总消耗功率

本文除了测试不同分组的功率消耗，还与文献[15]提出的策略对比了总功耗，如图7所示。尽管在两种策略下，系统的功率在100个周期内都在不停的变化，但本文策略的抖动频率相比于文献[15]所提策略较低，即本文策略的系统稳定性更好，而本文策略在起初位置的突起，是由系统中任务到达的随机性引起的。

图8再一次测试了两种策略的系统功率，可看出本文策略不再有激凸部分，而文献[15]提出的策略却因为随机的任务到达环境出现了突起。但两次仿真中，本文策略的抖动频率都比文献[15]的策略低。

此外，从两次仿真结果可以看出，两种策略的平均功率相差不大，但是本文策略可以使系统处于更加稳定的状态，系统的平均能耗和服务器的状态都会尽量维持稳定。在传统的大型数据中心内，为了满足业务峰值时期的需要，所有服务器都处于开启状态，因此即使是全部空闲的低负载时期，系统的最低功率依然有450 W，而本文策略的平均功耗大约是350 W。由此可见，本文策略节约了20%以上的能源，达到了本文的节能目标。

图7 系统功率对比图

图8 系统功率对比图

5 结束语

本文研究了多台异构服务器的数据中心的动态调度机制。首先，使用排队论寻找多台异构服务器的数据中心内功率消耗与平均服务等待时间之间的关系，在保证一定的平均服务等待时间的系统性能前提下，给出了最小化能耗的最优化问题。最后，使用仿真实验证明了本文提出的调度机制可显著改善系统能耗，该方法提供了一种在数据中心级别上权衡功率与性能的有效分析方案。接下来的工作将会使用现实的记录来证明本文的仿真结果，并改进本文的算法来寻找适用于可容纳上百或上千台服务器的大型数据中心的最优解。

[1]BROWN R E, BROWN R, MASANET E, et al.Report to congress on server and data center energy efficiency: Public law 109-431[R].Ernest Orlando Lawrence Berkeley National Laboratory.Berkeley, USA: [s.n.], 2007.

[2]GREENBERG A, HAMILTON J, MALTZ D A, et al.The cost of a cloud: Research problems in data center networks[J].ACM SIGCOMM Computer Communication Review, 2008, 39(1): 68-73.

[3]BENSON T, AKELLA A, MALTZ D.Network traffic characteristics of data centers in the wild[C]//Internet Measurement Conference (IMC).Melbourne, Australia:[s.n.], 2010.

[4]DENG X, WU D, SHEN J, et al.Eco-aware online power management and load scheduling for green cloud datacenters[J].IEEE Systems Journal, 2016, 10(1): 78-87.

[5]ZHANG Q, SHI W.Energy-efficient workload placement in enterprise datacenters[J].Computer, 2016, 49(2): 46-52.

[6]ROSSI F, XAVIER M, ROSE C, et al.E-eco: Performanceaware energy-efficient cloud data center orchestration[J].Journal of Network and Computer Applications, 2017, 78:83-96.

[7]XU G, DAI B, HUANG B, et al.Bandwidth-aware energy efficient flow scheduling with SDN in data center networks[J].Future Generation Computer Systems, 2017, 68:163-174.

[8]KIM J, CHANG H, JUNG Y, et al.Energy conservation effects of a multi-stage outdoor air enabled cooling system in a data center[J].Energy and Buildings, 2017, 138:257-270.

[9]MAZZUCCO M, DYACHUK D, DETERS R.Maximizing cloud providers revenues via energy aware allocation policies[C]//IEEE International Conference on Cloud Computing.Miami, Florida: IEEE, 2010.

[10]DYACHUK D, MAZZUCCO M.On allocation policies for power and performance[C]//11th ACM/IEEE International Conference on Grid Computing (Grid 2010)-Energy Efficient Grids, Clouds and Clusters Workshop.Brussels,Belgium: IEEE, 2010.

[11]GANDHI A, GUPTA V, HARCHOL-BALTER M, et al.Optimality analysis of energy-performance trade-off for server farm management[J].Performance Evaluation, 2010,67(11): 1155-71.

[12]ZHENG X, CAI Y.Optimal server provisioning and frequency adjustment in server clusters[C]//IEEE 39th International Conference on Parallel Processing Workshops.[S.l.]: IEEE, 2010.

[13]GHAMKHARI M, MOHSENIAN-RAD H.Energy and performance management of green data centers: a profit maximization approach[J].IEEE Transactions on Smart Grid, 2013, 4(2): 1017-1025.

[14]GUENTER B, JAIN N, WILLIAMS C.Managing cost,performance and reliability tradeoffs for energy-aware serverprovisioning[C]//IEEE International Conference on Computer Communications.[S.l.]: IEEE, 2011.

[15]SCHWARTZ C, PRIES R, TRAN-GIA P.A queuing analysis of an energy-saving mechanism in data centers[C]//IEEE International Conference on Information Networking (ICOIN).[S.l.]: IEEE, 2012.

[16]WANG W, LUO J, SONG A, et al.Heterogeneity aware optimal power allocationin data center environments[J].Pervasive Computing and the Networked World, 2013,7719: 513-528.

[17]LI K.Optimal power allocation among multiple heterogeneous servers in a data center[J].Sustainable Computing: Informatics and Systems, 2012, 2(1): 13-22.

[18]INTEL CORP.Intel math kernel library 10.0-linpack[EB/OL].[2016-05-10].http://www.intel.com/cd/software/products/ asmo-na/eng/266857.htm, 2007.