面向云計(jì)算數(shù)據(jù)中心的彈性資源分配算法

陳雪娟，邵亞麗

(1. 廣東理工學(xué)院信息技術(shù)學(xué)院，廣東 肇慶 526114；2. 廣東工業(yè)大學(xué)機(jī)電工程學(xué)院，廣東 廣州 510006)

1 引言

信息數(shù)據(jù)迅猛增長(zhǎng)導(dǎo)致大規(guī)模數(shù)據(jù)處理需求越來越高，作為新型的計(jì)算模型與服務(wù)模式之一，云計(jì)算技術(shù)[1]應(yīng)運(yùn)而生，其數(shù)據(jù)中心由海量計(jì)算節(jié)點(diǎn)組成，通過分配運(yùn)算任務(wù)至該數(shù)據(jù)中心，實(shí)現(xiàn)多應(yīng)用對(duì)計(jì)算性能、信息服務(wù)以及存儲(chǔ)空間的按需索取。隨著云計(jì)算快速發(fā)展，數(shù)據(jù)規(guī)模急劇膨脹，為處理策略帶來巨大挑戰(zhàn)，其中，最為突出的問題就是資源分配。

文獻(xiàn)[2]為解決認(rèn)知異構(gòu)網(wǎng)絡(luò)的干擾抑制問題，提出一種認(rèn)知異構(gòu)網(wǎng)絡(luò)中基于不完全頻譜感知的資源分配算法，經(jīng)過對(duì)干擾源的分析，構(gòu)建基于不完全頻譜感知的干擾模型，根據(jù)總功率約束、干擾約束以及用戶拓?fù)湫畔?，設(shè)計(jì)基于下行鏈路吞吐量最大化的優(yōu)化問題，通過KKT條件分析進(jìn)行簡(jiǎn)化，完成分布式資源分配算法架構(gòu)；文獻(xiàn)[3]針對(duì)超密集網(wǎng)絡(luò)中小區(qū)間干擾對(duì)終端用戶數(shù)據(jù)速率的制約問題，設(shè)計(jì)出一種超密集網(wǎng)絡(luò)中基于干擾協(xié)調(diào)的資源分配算法，根據(jù)毫微微接入點(diǎn)之間的干擾程度，完成較強(qiáng)干擾毫微微接入點(diǎn)的分簇處理，通過協(xié)作復(fù)用各簇頻譜，依據(jù)極大功率與極小速率公平性原則來分配最優(yōu)功率，實(shí)現(xiàn)資源動(dòng)態(tài)分配。

云計(jì)算之所以能夠得到大范圍應(yīng)用，關(guān)鍵原因是云數(shù)據(jù)中心資源分配技術(shù)的高效性。云計(jì)算的重要基礎(chǔ)結(jié)構(gòu)是數(shù)據(jù)中心網(wǎng)絡(luò)，起著無法代替的基礎(chǔ)設(shè)施作用，置于云計(jì)算硬件層，功能為互聯(lián)網(wǎng)應(yīng)用與服務(wù)輸送動(dòng)力。由于上述文獻(xiàn)方法資源開銷過大，缺少綜合調(diào)配數(shù)據(jù)中心資源性能，因此，本文將云計(jì)算數(shù)據(jù)中心的數(shù)據(jù)作為資源，提出一種彈性資源分配算法。引入布爾變量，區(qū)分各用戶間虛擬集群資源；轉(zhuǎn)換彈性資源分配問題為整數(shù)線性規(guī)劃問題，簡(jiǎn)化運(yùn)算流程；根據(jù)極大允許負(fù)載占比與帶寬需求按序分配，確保用戶帶寬需求，實(shí)現(xiàn)云計(jì)算數(shù)據(jù)中心彈性最大化，降低運(yùn)算復(fù)雜度。

2 云計(jì)算數(shù)據(jù)中心下彈性資源分配算法

2.1 云計(jì)算數(shù)據(jù)中心下彈性資源分配問題分析

假設(shè)下列表達(dá)式為數(shù)據(jù)中心的界定公式

G={C，L}

(1)

式中，物理節(jié)點(diǎn)設(shè)備集合與鏈路集合分別為C={Ci}和L={Lij}。其中，第i臺(tái)物理節(jié)點(diǎn)設(shè)備為Ci，數(shù)據(jù)中心的第i層、第j條鏈路為L(zhǎng)ij，因此，Gij則用于界定鏈路Lij下的子樹。

假設(shè)第j個(gè)用戶虛擬集群的資源為Vj=〈Nj，Bj〉，其中，虛擬集群資源Vj所請(qǐng)求的虛擬機(jī)[4]個(gè)數(shù)為Nj，資源Vj中虛擬機(jī)間的單位通信帶寬為Bj，則采用下列公式界定資源集合

V={Vj}

(2)

(3)

(4)

綜上所述，云計(jì)算數(shù)據(jù)中心下彈性資源分配問題的表達(dá)公式如下所示

f(E)=maximizeE

(5)

分配問題表達(dá)式對(duì)應(yīng)的約束條件分別描述如下

(6)

(7)

(8)

(9)

(10)

其中，目標(biāo)函數(shù)用式(5)、式(6)表示，令數(shù)據(jù)中心彈性為最大化；計(jì)算資源限制條件用式(7)、式(8)表示，令各物理節(jié)點(diǎn)設(shè)備上的虛擬機(jī)總數(shù)不大于容量ci；通信資源限制條件用式(9)、式(10)表示，令分配到各鏈路的帶寬資源不大于容量lij。

2.2 多用戶虛擬集群彈性資源分配算法

2.2.1 線性規(guī)劃

將彈性資源分配問題轉(zhuǎn)換成整數(shù)線性規(guī)劃問題，簡(jiǎn)化分配算法復(fù)雜性。

先將式(9)改寫成下列表達(dá)式

(11)

(12)

整合上列兩式得到下列帶寬資源表達(dá)式

(13)

通過拆分中間變量，得到下列不等式組

(14)

將上列兩式結(jié)合代入，推導(dǎo)出下列式(11)改寫式

(15)

綜上，完成整數(shù)線性規(guī)劃方程構(gòu)建，該方程的目標(biāo)函數(shù)同式(5)，對(duì)應(yīng)的約束條件分別描述如下

(16)

(17)

(18)

其中，通過分離各物理設(shè)備極小約束改寫式(8)，得到式(16)與(17)；通過分離各鏈路極小約束改寫式(9)，得到式(18)。若數(shù)據(jù)中心是一個(gè)完全二叉樹，所含葉子節(jié)點(diǎn)數(shù)量為n，則鏈路數(shù)量為2n-2，因此，式(16)含有約束n個(gè)，其它兩式有約束2n-2個(gè)。綜上，整數(shù)線性規(guī)劃方程中含有變量、約束各Θ(kn)個(gè)。

2.2.2 動(dòng)態(tài)規(guī)劃

變量與約束個(gè)數(shù)過大會(huì)導(dǎo)致多用戶虛擬集群彈性資源分配問題無法得到有效解決，為分析線性規(guī)劃的最優(yōu)性與復(fù)雜性，在各鏈路上逐級(jí)劃分?jǐn)?shù)據(jù)中心，得到兩個(gè)分區(qū)后，按照從下到上的順序展開逐層運(yùn)算。

假設(shè)多用戶虛擬集群資源集合V的最佳分配情況為OPT(G，U)，此時(shí)數(shù)據(jù)中心G的彈性為最大，各集群資源具有分配幾率的矢量為U=(u1，u2，…，u|V|)，其中，分配至集群資源Vi的虛擬機(jī)個(gè)數(shù)為變量ui≤Ni。

圖1 數(shù)據(jù)中心最佳子結(jié)構(gòu)示意圖

(19)

結(jié)合云計(jì)算數(shù)據(jù)中心彈性網(wǎng)絡(luò)架構(gòu)[6]，得到下列方程組

(20)

最優(yōu)解可采用下列計(jì)算公式求?。?/p>

OPT(G，U)=

(21)

上式即為多個(gè)虛擬集群彈性資源分配問題的最優(yōu)子結(jié)構(gòu)，所以，通過搜索最佳子結(jié)構(gòu)Gh，k，即可得到基于樹狀結(jié)構(gòu)的云計(jì)算數(shù)據(jù)中心最優(yōu)解OPT(G，U)。

假設(shè)輸入項(xiàng)為數(shù)據(jù)中心網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)G與虛擬集群資源V，輸出項(xiàng)為資源集合V的數(shù)據(jù)中心網(wǎng)絡(luò)占用狀態(tài)，則動(dòng)態(tài)規(guī)劃下最佳分配階段流程描述如下：

2)若驗(yàn)證成功，進(jìn)入下一步；否則，運(yùn)行終止；

3)對(duì)于每個(gè)葉子節(jié)點(diǎn)存在Ci∈C，記錄葉子節(jié)點(diǎn)層彈性，搜索可占用的矢量U′，且各矢量均滿足不等式U′≤U；

4)當(dāng)符合下列表達(dá)式時(shí)，迭代階段終止運(yùn)行；反之，進(jìn)入下一運(yùn)算流程：

(22)

5)自下而上逐層搜索Sk，l∈GC，解得非葉子節(jié)點(diǎn)Gk，l的劃分彈性，探索各向量U′彈性，且各矢量均滿足不等式U′≤U；

6)當(dāng)符合下列表達(dá)式時(shí)，迭代階段終止運(yùn)行；反之，則返回OPT(G，U)

(23)

2.2.3 啟發(fā)式分配

當(dāng)樹狀數(shù)據(jù)中心處于遍歷階段時(shí)，通過極大允許負(fù)載占比，明確可行分配形式，并根據(jù)帶寬需求采用貪婪法[7-8]按序分配，確保用戶帶寬需求的同時(shí)，實(shí)現(xiàn)云計(jì)算數(shù)據(jù)中心彈性最大化，使運(yùn)算復(fù)雜度下降。

假設(shè)輸入項(xiàng)為數(shù)據(jù)中心網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)G與虛擬集群資源V，輸出項(xiàng)為資源集合V的數(shù)據(jù)中心網(wǎng)絡(luò)占用狀態(tài)，則啟發(fā)式下多用戶彈性資源的最佳分配流程描述如下：

2)若驗(yàn)證成功，進(jìn)入下一步；否則，運(yùn)行終止；

3)計(jì)算數(shù)據(jù)中心的極大允許負(fù)載，選取具有最大允許負(fù)載的節(jié)點(diǎn)作為根節(jié)點(diǎn)；

4)按照根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的順序，逐層分配虛擬機(jī)；

5)基于各鏈路的負(fù)載占比，逐層分配虛擬機(jī)；

6)當(dāng)U≠0時(shí)，開始迭代操作：按照鏈路從左至右的順序，搜索所有滿足U′≤U的向量；

7)若向量U′的彈性是E≠-∞，則采用arg minf(U′)來分配向量U′；

9)更新向量U=U-U′，運(yùn)行結(jié)束；

10)輸出數(shù)據(jù)中心網(wǎng)絡(luò)占用狀態(tài)。

經(jīng)過上述彈性資源分配流程，既簡(jiǎn)化了分配算法的計(jì)算復(fù)雜度，還解決了多用戶虛擬集群的彈性資源分配問題，而且令用戶帶寬需求得到保證，實(shí)現(xiàn)了資源的最佳分配。

3 彈性資源分配算法性能評(píng)估

3.1 實(shí)驗(yàn)環(huán)境

選取word count與sort作為基準(zhǔn)測(cè)試作業(yè)，根據(jù)實(shí)際分布與輸入數(shù)據(jù)，確定系統(tǒng)運(yùn)行負(fù)載，采用維基百科文本數(shù)據(jù)作為word count作業(yè)數(shù)據(jù)，而sort數(shù)據(jù)則由隨機(jī)產(chǎn)生器得來?；谖墨I(xiàn)[2]、[3]方法與本文算法，利用隨機(jī)產(chǎn)生器架構(gòu)相同作業(yè)序列，得到200個(gè)作業(yè)，抵達(dá)時(shí)間與指數(shù)隨機(jī)過程擬合，設(shè)置平均間隔為20秒。選用TPC-W作為實(shí)驗(yàn)的基準(zhǔn)程序，并編寫出軟硬件相關(guān)配置。

3.2 彈性值對(duì)比分析

基于三層樹狀數(shù)據(jù)中心拓?fù)浣Y(jié)構(gòu)，各機(jī)架物理節(jié)點(diǎn)設(shè)備為k個(gè)，劃分各物理設(shè)備為多個(gè)含有一個(gè)虛擬機(jī)的計(jì)算資源部分，容量范圍是0到100個(gè)，將數(shù)據(jù)集分解成10組步長(zhǎng)為25的分區(qū)。通過模擬不同基準(zhǔn)測(cè)試作業(yè)下文獻(xiàn)方法與本文算法的虛擬集群彈性值，得到如圖2所示的比對(duì)結(jié)果。

圖2 各方法彈性值對(duì)比示意圖

根據(jù)圖2的展示結(jié)果可知，相對(duì)兩種文獻(xiàn)方法而言，隨著總資源請(qǐng)求量的上升，本文算法對(duì)彈性具有更大的影響力，請(qǐng)求的資源數(shù)量與集群資源之間呈正相關(guān)，當(dāng)集群間的組合利用率下降時(shí)，就會(huì)導(dǎo)致彈性減??；在不同基準(zhǔn)測(cè)試作業(yè)擁有相同集群量時(shí)，各集群對(duì)應(yīng)的彈性值不盡相同，較大規(guī)模集群資源的彈性值遠(yuǎn)小于較小規(guī)模的彈性值；從各方法彈性值的較大差異中可以看出，本文算法在大規(guī)模數(shù)據(jù)中心中具有比文獻(xiàn)方法更優(yōu)越的大量集群請(qǐng)求支持性能。

3.3 利用率對(duì)比分析

針對(duì)sort基準(zhǔn)測(cè)試作業(yè)，根據(jù)以下資源利用率標(biāo)準(zhǔn)，選取資源處理手段：

1)若每分鐘資源利用率大于80%，則增加應(yīng)用資源；

2)若每分鐘資源利用率小于30%，則減少應(yīng)用資源。

圖3所示為各方法的云計(jì)算數(shù)據(jù)中心資源利用情況。

圖3 資源利用率

根據(jù)圖3波形圖可以看出，對(duì)比文獻(xiàn)方法，本文算法經(jīng)過在各鏈路上逐級(jí)劃分?jǐn)?shù)據(jù)中心并逐層運(yùn)算，維持了較好的資源利用標(biāo)準(zhǔn)，波形振幅較小，說明該算法使數(shù)據(jù)中心資源得到了平穩(wěn)且有效的利用。

3.4 平均響應(yīng)時(shí)長(zhǎng)對(duì)比分析

基于平均響應(yīng)時(shí)長(zhǎng)的評(píng)估指標(biāo)，其上限主要是對(duì)于各層次的響應(yīng)時(shí)間來說的，文獻(xiàn)方法與本文算法的平均響應(yīng)時(shí)長(zhǎng)對(duì)比示意圖如圖4所示。

圖4 平均響應(yīng)時(shí)長(zhǎng)

根據(jù)圖4的對(duì)比曲線圖可以看出，本文算法的應(yīng)用請(qǐng)求平均響應(yīng)時(shí)長(zhǎng)較文獻(xiàn)方法更短，且大部分情況低于基準(zhǔn)響應(yīng)時(shí)長(zhǎng)。究其原因是本文算法依據(jù)極大允許負(fù)載占比，明確了可行的分配形式，并根據(jù)帶寬需求實(shí)施按序分配。

4 結(jié)論

云計(jì)算技術(shù)發(fā)展日趨成熟，憑借易用性與可靠性等諸多優(yōu)勢(shì)得到廣泛應(yīng)用，但隨之而來的還有為云平臺(tái)帶來巨大壓力與負(fù)載的指數(shù)倍級(jí)海量數(shù)據(jù)，有效處理作業(yè)調(diào)度與資源分配問題，防止因惡性資源競(jìng)爭(zhēng)引發(fā)瓶頸，有著重要的現(xiàn)實(shí)意義與研究?jī)r(jià)值，為此，本文以云計(jì)算數(shù)據(jù)中心為平臺(tái)，設(shè)計(jì)彈性資源分配算法。實(shí)際應(yīng)用中，云計(jì)算數(shù)據(jù)中心將伸縮虛擬機(jī)資源權(quán)限賦予給用戶，

在今后的工作中，應(yīng)針對(duì)彈性資源管理服務(wù)的合理計(jì)價(jià)問題，展開更深遠(yuǎn)的探索討論；真實(shí)的云平臺(tái)用戶、需求與應(yīng)用類型是多種多樣的，應(yīng)根據(jù)不同用戶需求或不同應(yīng)用特征，探究出更具適用性的分配算法；數(shù)據(jù)中心網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)形式較多，今后將就不同結(jié)構(gòu)的數(shù)據(jù)中心，構(gòu)建對(duì)應(yīng)的有效分配算法，并深入探索復(fù)雜度更低的最優(yōu)解；由于預(yù)測(cè)虛擬請(qǐng)求時(shí)會(huì)發(fā)生估計(jì)過高或過低情況，故設(shè)定下一個(gè)研究方向?yàn)閺椥再Y源分配近似算法，通過按需分配確保彈性資源配置。