面向云計算數據中心的彈性資源分配算法

陳雪娟，邵亞麗

(1. 廣東理工學院信息技術學院，廣東 肇慶 526114；2. 廣東工業大學機電工程學院，廣東 廣州 510006)

1 引言

信息數據迅猛增長導致大規模數據處理需求越來越高，作為新型的計算模型與服務模式之一，云計算技術[1]應運而生，其數據中心由海量計算節點組成，通過分配運算任務至該數據中心，實現多應用對計算性能、信息服務以及存儲空間的按需索取。隨著云計算快速發展，數據規模急劇膨脹，為處理策略帶來巨大挑戰，其中，最為突出的問題就是資源分配。

文獻[2]為解決認知異構網絡的干擾抑制問題，提出一種認知異構網絡中基于不完全頻譜感知的資源分配算法，經過對干擾源的分析，構建基于不完全頻譜感知的干擾模型，根據總功率約束、干擾約束以及用戶拓撲信息，設計基于下行鏈路吞吐量最大化的優化問題，通過KKT條件分析進行簡化，完成分布式資源分配算法架構；文獻[3]針對超密集網絡中小區間干擾對終端用戶數據速率的制約問題，設計出一種超密集網絡中基于干擾協調的資源分配算法，根據毫微微接入點之間的干擾程度，完成較強干擾毫微微接入點的分簇處理，通過協作復用各簇頻譜，依據極大功率與極小速率公平性原則來分配最優功率，實現資源動態分配。

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

2 云計算數據中心下彈性資源分配算法

2.1 云計算數據中心下彈性資源分配問題分析

假設下列表達式為數據中心的界定公式

G={C，L}

(1)

式中，物理節點設備集合與鏈路集合分別為C={Ci}和L={Lij}。其中，第i臺物理節點設備為Ci，數據中心的第i層、第j條鏈路為Lij，因此，Gij則用于界定鏈路Lij下的子樹。

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

V={Vj}

(2)

(3)

(4)

綜上所述，云計算數據中心下彈性資源分配問題的表達公式如下所示

f(E)=maximizeE

(5)

分配問題表達式對應的約束條件分別描述如下

(6)

(7)

(8)

(9)

(10)

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

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

2.2.1 線性規劃

將彈性資源分配問題轉換成整數線性規劃問題，簡化分配算法復雜性。

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

(11)

(12)

整合上列兩式得到下列帶寬資源表達式

(13)

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

(14)

將上列兩式結合代入，推導出下列式(11)改寫式

(15)

綜上，完成整數線性規劃方程構建，該方程的目標函數同式(5)，對應的約束條件分別描述如下

(16)

(17)

(18)

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

2.2.2 動態規劃

變量與約束個數過大會導致多用戶虛擬集群彈性資源分配問題無法得到有效解決，為分析線性規劃的最優性與復雜性，在各鏈路上逐級劃分數據中心，得到兩個分區后，按照從下到上的順序展開逐層運算。

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

圖1 數據中心最佳子結構示意圖

(19)

結合云計算數據中心彈性網絡架構[6]，得到下列方程組

(20)

最優解可采用下列計算公式求取：

OPT(G，U)=

(21)

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

假設輸入項為數據中心網絡拓撲結構G與虛擬集群資源V，輸出項為資源集合V的數據中心網絡占用狀態，則動態規劃下最佳分配階段流程描述如下：

2)若驗證成功，進入下一步；否則，運行終止；

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

4)當符合下列表達式時，迭代階段終止運行；反之，進入下一運算流程：

(22)

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

6)當符合下列表達式時，迭代階段終止運行；反之，則返回OPT(G，U)

(23)

2.2.3 啟發式分配

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

假設輸入項為數據中心網絡拓撲結構G與虛擬集群資源V，輸出項為資源集合V的數據中心網絡占用狀態，則啟發式下多用戶彈性資源的最佳分配流程描述如下：

2)若驗證成功，進入下一步；否則，運行終止；

3)計算數據中心的極大允許負載，選取具有最大允許負載的節點作為根節點；

4)按照根節點到葉子節點的順序，逐層分配虛擬機；

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

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

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

9)更新向量U=U-U′，運行結束；

10)輸出數據中心網絡占用狀態。

經過上述彈性資源分配流程，既簡化了分配算法的計算復雜度，還解決了多用戶虛擬集群的彈性資源分配問題，而且令用戶帶寬需求得到保證，實現了資源的最佳分配。

3 彈性資源分配算法性能評估

3.1 實驗環境

選取word count與sort作為基準測試作業，根據實際分布與輸入數據，確定系統運行負載，采用維基百科文本數據作為word count作業數據，而sort數據則由隨機產生器得來。基于文獻[2]、[3]方法與本文算法，利用隨機產生器架構相同作業序列，得到200個作業，抵達時間與指數隨機過程擬合，設置平均間隔為20秒。選用TPC-W作為實驗的基準程序，并編寫出軟硬件相關配置。

3.2 彈性值對比分析

基于三層樹狀數據中心拓撲結構，各機架物理節點設備為k個，劃分各物理設備為多個含有一個虛擬機的計算資源部分，容量范圍是0到100個，將數據集分解成10組步長為25的分區。通過模擬不同基準測試作業下文獻方法與本文算法的虛擬集群彈性值，得到如圖2所示的比對結果。

圖2 各方法彈性值對比示意圖

根據圖2的展示結果可知，相對兩種文獻方法而言，隨著總資源請求量的上升，本文算法對彈性具有更大的影響力，請求的資源數量與集群資源之間呈正相關，當集群間的組合利用率下降時，就會導致彈性減?。辉诓煌鶞蕼y試作業擁有相同集群量時，各集群對應的彈性值不盡相同，較大規模集群資源的彈性值遠小于較小規模的彈性值；從各方法彈性值的較大差異中可以看出，本文算法在大規模數據中心中具有比文獻方法更優越的大量集群請求支持性能。

3.3 利用率對比分析

針對sort基準測試作業，根據以下資源利用率標準，選取資源處理手段：

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

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

圖3所示為各方法的云計算數據中心資源利用情況。

圖3 資源利用率

根據圖3波形圖可以看出，對比文獻方法，本文算法經過在各鏈路上逐級劃分數據中心并逐層運算，維持了較好的資源利用標準，波形振幅較小，說明該算法使數據中心資源得到了平穩且有效的利用。

3.4 平均響應時長對比分析

基于平均響應時長的評估指標，其上限主要是對于各層次的響應時間來說的，文獻方法與本文算法的平均響應時長對比示意圖如圖4所示。

圖4 平均響應時長

根據圖4的對比曲線圖可以看出，本文算法的應用請求平均響應時長較文獻方法更短，且大部分情況低于基準響應時長。究其原因是本文算法依據極大允許負載占比，明確了可行的分配形式，并根據帶寬需求實施按序分配。

4 結論

云計算技術發展日趨成熟，憑借易用性與可靠性等諸多優勢得到廣泛應用，但隨之而來的還有為云平臺帶來巨大壓力與負載的指數倍級海量數據，有效處理作業調度與資源分配問題，防止因惡性資源競爭引發瓶頸，有著重要的現實意義與研究價值，為此，本文以云計算數據中心為平臺，設計彈性資源分配算法。實際應用中，云計算數據中心將伸縮虛擬機資源權限賦予給用戶，

在今后的工作中，應針對彈性資源管理服務的合理計價問題，展開更深遠的探索討論；真實的云平臺用戶、需求與應用類型是多種多樣的，應根據不同用戶需求或不同應用特征，探究出更具適用性的分配算法；數據中心網絡的拓撲結構形式較多，今后將就不同結構的數據中心，構建對應的有效分配算法，并深入探索復雜度更低的最優解；由于預測虛擬請求時會發生估計過高或過低情況，故設定下一個研究方向為彈性資源分配近似算法，通過按需分配確保彈性資源配置。