朱欣穎

摘要：資源調(diào)度問(wèn)題是數(shù)據(jù)提高運(yùn)行效率的關(guān)鍵。然而目前大部分任務(wù)調(diào)度算法都聚焦于單一維度的資源，忽略了多維資源（CPU、Memory、Disk、Storage）同時(shí)消耗的實(shí)際情況。本文將此多維資源調(diào)度問(wèn)題歸納為多維背包問(wèn)題，并且提出了相應(yīng)的MS調(diào)度算法。為了展示MS的優(yōu)勢(shì)，在WMware平臺(tái)做了仿真實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明：MS算法能取得較高的服務(wù)器綜合資源利用率。

關(guān)鍵詞：數(shù)據(jù)中心；多維資源；資源調(diào)度

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)號(hào)：A 文章編號(hào)：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 引言

云計(jì)算是分布式計(jì)算和虛擬化技術(shù)發(fā)展結(jié)合的產(chǎn)物，現(xiàn)已廣泛應(yīng)用于存儲(chǔ)實(shí)現(xiàn)、信息安全、大規(guī)模復(fù)雜計(jì)算等多個(gè)領(lǐng)域。在IaaS模式下，來(lái)自不同地區(qū)的不同應(yīng)用請(qǐng)求的用戶無(wú)一例外地均可共享作為基礎(chǔ)設(shè)施的云數(shù)據(jù)中心所提供的各類服務(wù)。在這種多用戶分配有限資源的情況下，資源調(diào)度算法則顯得尤為重要。因其不僅關(guān)乎資源利用率的高低、進(jìn)而對(duì)數(shù)據(jù)中心能耗等指標(biāo)形成影響，同時(shí)更對(duì)服務(wù)性能表現(xiàn)如SLA等具有決定性的重要作用。

雖然之前的一些文獻(xiàn)[1-5]利用自己的調(diào)度算法取得了不錯(cuò)的性能指標(biāo)，但是卻仍存在一定的局限性。首先，上述文獻(xiàn)僅僅考慮了單一資源模型，或者將所有資源加權(quán)抽象成一種資源[1-3]。然而事實(shí)上，每個(gè)用戶的任務(wù)請(qǐng)求實(shí)例都將同時(shí)消耗多維資源（CPU、內(nèi)存、硬盤、網(wǎng)絡(luò)帶寬...）。其次，即便一些研究已經(jīng)把多維資源的消耗納入資源調(diào)度的算法，但也僅是將約束條件由一維改為多維，而并未考慮每個(gè)資源維度的值域以及多個(gè)維度資源間的依存關(guān)系[4-5]。同時(shí)，這些研究仍然將縮短任務(wù)執(zhí)行時(shí)間作為最主要的性能指標(biāo)，并沒(méi)有找到提高云數(shù)據(jù)中心綜合資源利用率的辦法?；诖耍槍?duì)云數(shù)據(jù)中心，如果能夠找到一種統(tǒng)籌協(xié)調(diào)各維度資源利用率的資源調(diào)度策略，即是降低數(shù)據(jù)中心能耗、打造綠色云的重點(diǎn)關(guān)鍵實(shí)現(xiàn)研究。

1 相關(guān)工作

對(duì)于獨(dú)立任務(wù)間的資源調(diào)度問(wèn)題，很多研究者將其歸結(jié)為帶約束條件的多維線性規(guī)劃問(wèn)題[2*3，6]。一些文獻(xiàn)通過(guò)抽象出多維約束條件來(lái)降低資源維度以達(dá)到解決問(wèn)題目的。文獻(xiàn)[3、7]將整個(gè)服務(wù)器抽象成單一資源以便找到更高效的處理方式。然而多維度的資源模型才更為貼近、符合實(shí)際情況，而在多維資源模型中可以通過(guò)統(tǒng)籌利用多維資源的方式來(lái)提高服務(wù)器多維資源的綜合利用率。事實(shí)上，任務(wù)在云端服務(wù)器的執(zhí)行過(guò)程中對(duì)每一個(gè)維度的資源均發(fā)生著同時(shí)消耗。相應(yīng)地，一些文獻(xiàn)則致力于采用多維資源消耗模型以便取得更好的效果[4-5，8-9]。具體地，在文獻(xiàn)[4]中，作者提出一種特殊的虛擬機(jī)匹配策略，通過(guò)保證多維資源的約束條件，從而避免資源熱點(diǎn)爭(zhēng)奪情況的出現(xiàn)。文獻(xiàn)[5]即借助多維計(jì)算指數(shù)提出了一種網(wǎng)格計(jì)算環(huán)境下多用戶多維資源調(diào)度模型。文獻(xiàn)[9]的研究則是聚焦于在同構(gòu)的虛擬化環(huán)境下如何提高服務(wù)性能。與上述文獻(xiàn)不同的是，本文所提出的調(diào)度策略既考慮了多任務(wù)環(huán)境下占優(yōu)資源的約束情況，同時(shí)又充分考慮了云數(shù)據(jù)中心資源池中各維度資源的稀有度情況，并經(jīng)仿真驗(yàn)證，具有鮮明顯著的性能指標(biāo)優(yōu)勢(shì)。

異構(gòu)環(huán)境下的云數(shù)據(jù)中心的混合資源模型與本文研究的場(chǎng)景有相似之處。不同的是，前者過(guò)多強(qiáng)調(diào)多維資源消耗率間的公平性；后者在保證每個(gè)任務(wù)的基本資源需求的情況下，將優(yōu)化目標(biāo)定位于更高的綜合資源利用率。對(duì)于這種多維資源利用率模型，一種常用的方法是將其歸納為多維背包問(wèn)題[9]。簡(jiǎn)單地說(shuō)，多維背包模型假定背包或者箱子的各個(gè)維度具有相對(duì)固定的數(shù)值。然而事實(shí)上在云數(shù)據(jù)中心中虛擬機(jī)往往充當(dāng)著背包或者箱子的角色，這些虛擬機(jī)的各種資源能力值是可以隨時(shí)變化的。特別是在目前成熟的虛擬化平臺(tái)如Xen、VMWARE中，每臺(tái)虛擬機(jī)的各種資源的能力值均是可以根據(jù)參數(shù)靈活更改的。

2調(diào)度策略的形式化表述

2.1 形式化定義

不失一般性，在此定義一個(gè)云數(shù)據(jù)中心存在m維資源，記作R=，其中ri代表第i種資源Ri的總量。假定一個(gè)數(shù)據(jù)中心可支持n種任務(wù)類型，分別是AP1， AP2， …， APn。為了方便計(jì)算，這里設(shè)置每種任務(wù)類型下?lián)碛邢嗤瑪?shù)量的任務(wù)，并且任務(wù)直接都是獨(dú)立存在的，不存在相互依賴關(guān)系。如果一個(gè)用戶的任務(wù)需求是不一樣的，那么不同的任務(wù)所需要的多維資源向量也將是不等的。每一個(gè)任務(wù)類型j對(duì)應(yīng)一個(gè)多維資源需求向量wj，由其刻畫(huà)了j類型下的每個(gè)任務(wù)的資源需求量。研究中將j類型下的每個(gè)任務(wù)對(duì)資源Ri的需求量記作wi，j，進(jìn)而得出j類型的任務(wù)的資源需求向量wj=。另設(shè)每種任務(wù)類型下的任務(wù)需求量為μj，則一個(gè)資源調(diào)度策略即是找到一種分配策略A=，使得任務(wù)類型APj能夠運(yùn)行xj個(gè)j類型的任務(wù)實(shí)例。在一個(gè)資源能力為向量R的數(shù)據(jù)中心，假設(shè)其中存在著各種各樣的任務(wù)類型（wj，μj），那么一個(gè)調(diào)度策略就是尋找到一個(gè)合適的資源配置向量A=，使得云數(shù)據(jù)中心內(nèi)的每一個(gè)維度的資源均能獲得盡可能高的利用率。

2.2 算法模型的數(shù)學(xué)表述

由上述形式化表述可以看出，一般性的多維資源調(diào)度問(wèn)題往往可以歸納為帶有某種特殊條件的組合優(yōu)化問(wèn)題MDKP（multi-dimensional knapsack problem）。在本文的模型中，需進(jìn)行以下假設(shè)：

（1）資源消耗的穩(wěn)定性。對(duì)于一個(gè)既定的任務(wù)實(shí)例而言，在運(yùn)行過(guò)程中某些資源（如CPU、Memory等）會(huì)出現(xiàn)小幅波動(dòng)，為了更好地做到組合優(yōu)化，為此則假設(shè)任務(wù)實(shí)例對(duì)每個(gè)維度資源的消耗是平穩(wěn)的。

（2）資源的非獨(dú)占性。各個(gè)維度的資源只有在算法的分布方案形成之后才會(huì)分配給相應(yīng)的任務(wù)。在傳統(tǒng)的背包算法中，p代表物品的價(jià)值所得，這里p并未沿用傳統(tǒng)的背包物品的尺寸、獲利問(wèn)題。研究中利用符號(hào)p來(lái)表示每個(gè)任務(wù)在分配資源之后給整個(gè)分配方案帶來(lái)的效率提升。具體數(shù)學(xué)描述為：

（1）

和傳統(tǒng)背包問(wèn)題相似的地方是，本算法的目標(biāo)函數(shù)仍然是使獲利達(dá)到最大化，對(duì)應(yīng)公式為：

（2）

再加上每個(gè)維度的資源能力的限定性因素以及考慮到整個(gè)任務(wù)數(shù)量的限定，可以得出以下式子：

3 算法描述及性能評(píng)估

3.1 算法描述

一般性的多維背包是一個(gè)NP完全問(wèn)題，因此找到一種高效且具較低復(fù)雜度的算法則表現(xiàn)出迫切的現(xiàn)實(shí)必要性。文獻(xiàn)[9]的結(jié)論是貪婪算法在執(zhí)行代價(jià)以及性能表現(xiàn)上都優(yōu)于其他算法，因此研究中的MS算法正是基于傳統(tǒng)貪婪算法的改進(jìn)，從而最終獲得近似最優(yōu)解。

MS算法包括兩個(gè)階段：數(shù)量定位和任務(wù)選擇。在數(shù)量定位階段，研究將多類型任務(wù)問(wèn)題轉(zhuǎn)換為等價(jià)的0-1背包問(wèn)題。在任務(wù)選擇階段，MS算法會(huì)根據(jù)任務(wù)占優(yōu)資源的不同來(lái)進(jìn)行任務(wù)的合并和分發(fā)。對(duì)于每個(gè)任務(wù)類型j，研究引入log2（μj +1）個(gè)任務(wù)，相應(yīng)背包問(wèn)題的獲利和重量則可分別表示為（pj，wi，j），（2pj，2wi，j），（4pj，4wi，j）…。值得注意的是，在獲利以及重量都分別成倍增長(zhǎng)的情況下，背包問(wèn)題的效率值ej卻將一直保持不變。

在接下來(lái)的任務(wù)選擇階段，研究需對(duì)任務(wù)隊(duì)列實(shí)施一次排序。排序的準(zhǔn)則是：優(yōu)先按照放入背包的效率值的升序排列，如果ej值相同，則按照pj的升序進(jìn)行排列。而后，即采用貪婪算法挑選出效率值最大的那個(gè)任務(wù)序列，并且檢測(cè)服務(wù)器剩余資源是否能夠滿足此任務(wù)序列。如果剩余資源充足，則會(huì)將此任務(wù)序列添至“背包”并進(jìn)入下一個(gè)循環(huán)。如果剩余資源不足，就將會(huì)尋找次小的任務(wù)包并試圖將其放入“背包”，直至背包中再也無(wú)法放入任何任務(wù)序列。

3.2 性能評(píng)估

為了明確獲悉算法的性能表現(xiàn)，研究小組開(kāi)展了一系列實(shí)驗(yàn)。實(shí)驗(yàn)中的若干參考比照算法分別是：（1） 基于隊(duì)列服務(wù)的FCFS（First Come First Service） （2） DRF（Dominant Resource Fairless） 多維資源調(diào)度中的經(jīng)典平衡算法。本文的仿真實(shí)驗(yàn)建立在WMware平臺(tái)之上。數(shù)據(jù)中心的資源能力值設(shè)置如下：8 000個(gè)CPU核心，8 000GB內(nèi)存，80T硬盤以及2500M的網(wǎng)絡(luò)帶寬。這個(gè)能力值比較貼近一個(gè)中型的數(shù)據(jù)中心，同時(shí)還是很多文獻(xiàn)研究中的標(biāo)準(zhǔn)實(shí)驗(yàn)配置。為了貼近真實(shí)情況，仿真時(shí)假定任務(wù)的到來(lái)服從泊松分布，平均時(shí)間間隔為5秒鐘。每種任務(wù)的類型都以各自獨(dú)立的泊松分布進(jìn)入到任務(wù)隊(duì)列中。每個(gè)任務(wù)的執(zhí)行時(shí)間則服從60s至90s的U型分布，而且每次仿真都將產(chǎn)生5 000個(gè)任務(wù)實(shí)例，實(shí)驗(yàn)結(jié)果的平均統(tǒng)計(jì)值如圖1所示。

圖1 三種算法在每個(gè)維度的資源利用率對(duì)比

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

圖1顯示無(wú)論如何隨機(jī)變換任務(wù)序列，在每個(gè)維度上MS算法幾乎都是領(lǐng)先于DRF和FCFS的。FCFS的性能則因受限于固定的先到先服務(wù)模式，其具體表現(xiàn)較差。而DRF卻因?yàn)楸ＷC了占有資源的公平性，從而呈現(xiàn)了不錯(cuò)的整體表現(xiàn)性能，甚至在某個(gè)資源維度上近似于超越了MS算法。但由于DRF算法的前提是經(jīng)典的max-min場(chǎng)景，并且每個(gè)用戶的任務(wù)請(qǐng)求是無(wú)限量的，但必須指出的是，這一假設(shè)卻是和數(shù)據(jù)中心的實(shí)際情況具有一定差距的，由此即已造成這種經(jīng)典的多維資源分配算法在本文仿真環(huán)境中的表現(xiàn)將會(huì)遜色于MS算法。

4 結(jié)束語(yǔ)

本文討論了多維約束條件下的多維資源的有效利用問(wèn)題。研究將此問(wèn)題形式化為帶約束條件的多維背包問(wèn)題，并且提出了MR算法。MR算法可以將具有不同資源需求向量的任務(wù)群組合優(yōu)化在一起，從而達(dá)到服務(wù)器資源的高效合理的利用。仿真實(shí)驗(yàn)表明MR算法在不同的任務(wù)序列中的表現(xiàn)性能是穩(wěn)定且高效的，整體性能相比于DRF和FCFS算法更是占據(jù)了明顯優(yōu)勢(shì)。研究小組今后的工作方向是細(xì)化MR算法的粒度，使其能夠應(yīng)用于細(xì)粒度的工作流調(diào)度平臺(tái)。

參考文獻(xiàn)

[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.