云数据中心的多维资源调度策略探析

朱欣颖

摘要：资源调度问题是数据提高运行效率的关键。然而目前大部分任务调度算法都聚焦于单一维度的资源，忽略了多维资源（CPU、Memory、Disk、Storage）同时消耗的实际情况。本文将此多维资源调度问题归纳为多维背包问题，并且提出了相应的MS调度算法。为了展示MS的优势，在WMware平台做了仿真实验，实验结果表明：MS算法能取得较高的服务器综合资源利用率。

关键词：数据中心；多维资源；资源调度

中图分类号：TP393 文献标识号：A 文章编号：2095-2163（2015）05-

Research on multi resources scheduling strategy in cloud data center

Zhu xinying

（Phycis Mechanical & Electrical Engineering， Zhoukou Normal University School ， Zhoukou Henan 466001， China）

Abstract： Resource scheduling is crucial to data centers. However， most existing scheduling algorithms focus only on on-dimensional resource， ignoring the fact that multiple resources （CPU， Memory， Storage and bandwidth） are consumed simultaneously. This paper maps such a resource scheduling problem to a multi-dimensional knapsack problem and presents MS- a relevant scheduling algorithm. To demonstrate the advantage of MS， the paper has implemented MS on VMware platform and the experimental results show that MS algorithm can achieve higher integrative resources utilization percentage of servers.

KeyWords： Data Center； Multi-dimensional Resources； Resource Scheduling

0 引言

云计算是分布式计算和虚拟化技术发展结合的产物，现已广泛应用于存储实现、信息安全、大规模复杂计算等多个领域。在IaaS模式下，来自不同地区的不同应用请求的用户无一例外地均可共享作为基础设施的云数据中心所提供的各类服务。在这种多用户分配有限资源的情况下，资源调度算法则显得尤为重要。因其不仅关乎资源利用率的高低、进而对数据中心能耗等指标形成影响，同时更对服务性能表现如SLA等具有决定性的重要作用。

虽然之前的一些文献[1-5]利用自己的调度算法取得了不错的性能指标，但是却仍存在一定的局限性。首先，上述文献仅仅考虑了单一资源模型，或者将所有资源加权抽象成一种资源[1-3]。然而事实上，每个用户的任务请求实例都将同时消耗多维资源（CPU、内存、硬盘、网络带宽...）。其次，即便一些研究已经把多维资源的消耗纳入资源调度的算法，但也仅是将约束条件由一维改为多维，而并未考虑每个资源维度的值域以及多个维度资源间的依存关系[4-5]。同时，这些研究仍然将缩短任务执行时间作为最主要的性能指标，并没有找到提高云数据中心综合资源利用率的办法。基于此，针对云数据中心，如果能够找到一种统筹协调各维度资源利用率的资源调度策略，即是降低数据中心能耗、打造绿色云的重点关键实现研究。

1 相关工作

对于独立任务间的资源调度问题，很多研究者将其归结为带约束条件的多维线性规划问题[2*3，6]。一些文献通过抽象出多维约束条件来降低资源维度以达到解决问题目的。文献[3、7]将整个服务器抽象成单一资源以便找到更高效的处理方式。然而多维度的资源模型才更为贴近、符合实际情况，而在多维资源模型中可以通过统筹利用多维资源的方式来提高服务器多维资源的综合利用率。事实上，任务在云端服务器的执行过程中对每一个维度的资源均发生着同时消耗。相应地，一些文献则致力于采用多维资源消耗模型以便取得更好的效果[4-5，8-9]。具体地，在文献[4]中，作者提出一种特殊的虚拟机匹配策略，通过保证多维资源的约束条件，从而避免资源热点争夺情况的出现。文献[5]即借助多维计算指数提出了一种网格计算环境下多用户多维资源调度模型。文献[9]的研究则是聚焦于在同构的虚拟化环境下如何提高服务性能。与上述文献不同的是，本文所提出的调度策略既考虑了多任务环境下占优资源的约束情况，同时又充分考虑了云数据中心资源池中各维度资源的稀有度情况，并经仿真验证，具有鲜明显著的性能指标优势。

异构环境下的云数据中心的混合资源模型与本文研究的场景有相似之处。不同的是，前者过多强调多维资源消耗率间的公平性；后者在保证每个任务的基本资源需求的情况下，将优化目标定位于更高的综合资源利用率。对于这种多维资源利用率模型，一种常用的方法是将其归纳为多维背包问题[9]。简单地说，多维背包模型假定背包或者箱子的各个维度具有相对固定的数值。然而事实上在云数据中心中虚拟机往往充当着背包或者箱子的角色，这些虚拟机的各种资源能力值是可以随时变化的。特别是在目前成熟的虚拟化平台如Xen、VMWARE中，每台虚拟机的各种资源的能力值均是可以根据参数灵活更改的。

2调度策略的形式化表述

2.1 形式化定义

不失一般性，在此定义一个云数据中心存在m维资源，记作R=，其中ri代表第i种资源Ri的总量。假定一个数据中心可支持n种任务类型，分别是AP1， AP2， …， APn。为了方便计算，这里设置每种任务类型下拥有相同数量的任务，并且任务直接都是独立存在的，不存在相互依赖关系。如果一个用户的任务需求是不一样的，那么不同的任务所需要的多维资源向量也将是不等的。每一个任务类型j对应一个多维资源需求向量wj，由其刻画了j类型下的每个任务的资源需求量。研究中将j类型下的每个任务对资源Ri的需求量记作wi，j，进而得出j类型的任务的资源需求向量wj=。另设每种任务类型下的任务需求量为μj，则一个资源调度策略即是找到一种分配策略A=，使得任务类型APj能够运行xj个j类型的任务实例。在一个资源能力为向量R的数据中心，假设其中存在着各种各样的任务类型（wj，μj），那么一个调度策略就是寻找到一个合适的资源配置向量A=，使得云数据中心内的每一个维度的资源均能获得尽可能高的利用率。

2.2 算法模型的数学表述

由上述形式化表述可以看出，一般性的多维资源调度问题往往可以归纳为带有某种特殊条件的组合优化问题MDKP（multi-dimensional knapsack problem）。在本文的模型中，需进行以下假设：

（1）资源消耗的稳定性。对于一个既定的任务实例而言，在运行过程中某些资源（如CPU、Memory等）会出现小幅波动，为了更好地做到组合优化，为此则假设任务实例对每个维度资源的消耗是平稳的。

（2）资源的非独占性。各个维度的资源只有在算法的分布方案形成之后才会分配给相应的任务。在传统的背包算法中，p代表物品的价值所得，这里p并未沿用传统的背包物品的尺寸、获利问题。研究中利用符号p来表示每个任务在分配资源之后给整个分配方案带来的效率提升。具体数学描述为：

（1）

和传统背包问题相似的地方是，本算法的目标函数仍然是使获利达到最大化，对应公式为：

（2）

再加上每个维度的资源能力的限定性因素以及考虑到整个任务数量的限定，可以得出以下式子：

3 算法描述及性能评估

3.1 算法描述

一般性的多维背包是一个NP完全问题，因此找到一种高效且具较低复杂度的算法则表现出迫切的现实必要性。文献[9]的结论是贪婪算法在执行代价以及性能表现上都优于其他算法，因此研究中的MS算法正是基于传统贪婪算法的改进，从而最终获得近似最优解。

MS算法包括两个阶段：数量定位和任务选择。在数量定位阶段，研究将多类型任务问题转换为等价的0-1背包问题。在任务选择阶段，MS算法會根据任务占优资源的不同来进行任务的合并和分发。对于每个任务类型j，研究引入log2（μj +1）个任务，相应背包问题的获利和重量则可分别表示为（pj，wi，j），（2pj，2wi，j），（4pj，4wi，j）…。值得注意的是，在获利以及重量都分别成倍增长的情况下，背包问题的效率值ej却将一直保持不变。

在接下来的任务选择阶段，研究需对任务队列实施一次排序。排序的准则是：优先按照放入背包的效率值的升序排列，如果ej值相同，则按照pj的升序进行排列。而后，即采用贪婪算法挑选出效率值最大的那个任务序列，并且检测服务器剩余资源是否能够满足此任务序列。如果剩余资源充足，则会将此任务序列添至“背包”并进入下一个循环。如果剩余资源不足，就将会寻找次小的任务包并试图将其放入“背包”，直至背包中再也无法放入任何任务序列。

3.2 性能评估

为了明确获悉算法的性能表现，研究小组开展了一系列实验。实验中的若干参考比照算法分别是：（1） 基于队列服务的FCFS（First Come First Service） （2） DRF（Dominant Resource Fairless） 多维资源调度中的经典平衡算法。本文的仿真实验建立在WMware平台之上。数据中心的资源能力值设置如下：8 000个CPU核心，8 000GB内存，80T硬盘以及2500M的网络带宽。这个能力值比较贴近一个中型的数据中心，同时还是很多文献研究中的标准实验配置。为了贴近真实情况，仿真时假定任务的到来服从泊松分布，平均时间间隔为5秒钟。每种任务的类型都以各自独立的泊松分布进入到任务队列中。每个任务的执行时间则服从60s至90s的U型分布，而且每次仿真都将产生5 000个任务实例，实验结果的平均统计值如图1所示。

图1 三种算法在每个维度的资源利用率对比

Fig.1Comparison of resource utilization with three algorithms in each dimension

图1显示无论如何随机变换任务序列，在每个维度上MS算法几乎都是领先于DRF和FCFS的。FCFS的性能则因受限于固定的先到先服务模式，其具体表现较差。而DRF却因为保证了占有资源的公平性，从而呈现了不错的整体表现性能，甚至在某个资源维度上近似于超越了MS算法。但由于DRF算法的前提是经典的max-min场景，并且每个用户的任务请求是无限量的，但必须指出的是，这一假设却是和数据中心的实际情况具有一定差距的，由此即已造成这种经典的多维资源分配算法在本文仿真环境中的表现将会逊色于MS算法。

4 结束语

本文讨论了多维约束条件下的多维资源的有效利用问题。研究将此问题形式化为带约束条件的多维背包问题，并且提出了MR算法。MR算法可以将具有不同资源需求向量的任务群组合优化在一起，从而达到服务器资源的高效合理的利用。仿真实验表明MR算法在不同的任务序列中的表现性能是稳定且高效的，整体性能相比于DRF和FCFS算法更是占据了明显优势。研究小组今后的工作方向是细化MR算法的粒度，使其能够应用于细粒度的工作流调度平台。

参考文献

[1] ISARD M， PRABHAKARAN V， CURREY J， et al. Quincy： Fair scheduling for distributed computing clusters [C]//Proc. of the ACM SIGOPS 22nd symposium on Operating systems principles （SOSP）， Montana： ACM， Oct. 2009：89-95.

[2] MERKLE D， MIDDENDORF M， SCHMECK H. Antcolony optimization for resourceconstrained project scheduling[J].IEEE Transactions on Evolutionary Computation， 2002，10（4）：89-93.

[3] PADALA P， SHIN K， ZHU X， et al. Adaptive control of virtualized resources in utility computing environments[C]//Proc. of the 2nd ACM SIGOPS/EuroSys European Conference on Computer Systems， Lisbon： ACM， Apr. 2007：65-68.

[4] SINGH A， KORUPOLU M， MOHAPATRA D， Serverstorage virtualization： Integration and load balancing in data centers[C]//Proc. of IEEE/ACM Supercomputing， Los Angeles： IEEE/ACM， May， 2008， 237-242.

[5] KHOO B B， VEERAVALLI B， HUNG T， et al. A multi-dimensional scheduling scheme in a Grid computing environment[J]. Journal of Parallel and Distributed Computing， 2007， 15（3）：170-175.

[6] ZAHARIA M， BORTHAKUR D， SARMA J S， et al. Delay scheduling： A simple technique for achieving locality and fairness in cluster scheduling[C]//European Conference on Computer Systems （EuroSys）， Berlin：ACM， Apr. 2010： 87-96.

[7] ARON M， DRUSCHEL P， ZWAENEPOEL W. Cluster reserves： a mechanism for resource management in cluster-based network servers[C]//Proc. of the ACM Sigmetrics International Conference on Measurement and Modeling of Computer Systems， Seoul： ACM， Jun. 2000：252-257.

[8] GAROFALAKIS M N， IOANNIDIS Y E. Multidimensional resource scheduling for parallel queries[C]//Proc. of the international conference on Management

of data（SIGMOD）， Toronto： ACM， Sep.1996：323-329.

[9] STILLWELL M， SCHANZENBACH D， VIVIEN F， et al. Resource allocation algorithms for virtualized service hosting platforms[J]， Journal of Parallel and Distributed Computing，2010，9：106-110.