云數據中心的多維資源調度策略探析

朱欣穎

摘要：資源調度問題是數據提高運行效率的關鍵。然而目前大部分任務調度算法都聚焦于單一維度的資源，忽略了多維資源（CPU、Memory、Disk、Storage）同時消耗的實際情況。本文將此多維資源調度問題歸納為多維背包問題，并且提出了相應的MS調度算法。為了展示MS的優(yōu)勢，在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 引言

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

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

1 相關工作

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

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

2調度策略的形式化表述

2.1 形式化定義

不失一般性，在此定義一個云數據中心存在m維資源，記作R=，其中ri代表第i種資源Ri的總量。假定一個數據中心可支持n種任務類型，分別是AP1， AP2， …， APn。為了方便計算，這里設置每種任務類型下?lián)碛邢嗤瑪盗康娜蝿眨⑶胰蝿罩苯佣际仟毩⒋嬖诘模淮嬖谙嗷ヒ蕾囮P系。如果一個用戶的任務需求是不一樣的，那么不同的任務所需要的多維資源向量也將是不等的。每一個任務類型j對應一個多維資源需求向量wj，由其刻畫了j類型下的每個任務的資源需求量。研究中將j類型下的每個任務對資源Ri的需求量記作wi，j，進而得出j類型的任務的資源需求向量wj=。另設每種任務類型下的任務需求量為μj，則一個資源調度策略即是找到一種分配策略A=，使得任務類型APj能夠運行xj個j類型的任務實例。在一個資源能力為向量R的數據中心，假設其中存在著各種各樣的任務類型（wj，μj），那么一個調度策略就是尋找到一個合適的資源配置向量A=，使得云數據中心內的每一個維度的資源均能獲得盡可能高的利用率。

2.2 算法模型的數學表述

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

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

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

（1）

和傳統(tǒng)背包問題相似的地方是，本算法的目標函數仍然是使獲利達到最大化，對應公式為：

（2）

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

3 算法描述及性能評估

3.1 算法描述

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

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

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

3.2 性能評估

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

圖1 三種算法在每個維度的資源利用率對比

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

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

4 結束語

本文討論了多維約束條件下的多維資源的有效利用問題。研究將此問題形式化為帶約束條件的多維背包問題，并且提出了MR算法。MR算法可以將具有不同資源需求向量的任務群組合優(yōu)化在一起，從而達到服務器資源的高效合理的利用。仿真實驗表明MR算法在不同的任務序列中的表現性能是穩(wěn)定且高效的，整體性能相比于DRF和FCFS算法更是占據了明顯優(yōu)勢。研究小組今后的工作方向是細化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.