基于虛擬機動態遷移的負載均衡策略①

王 晶,何利力

(浙江理工大學 信息學院,杭州 310018)

數據中心的負載均衡問題一直是數據中心研究的熱點問題,追根究底,主要原因是資源配置問題[1],即資源利用不均衡問題.面對由大量異構設備組成的數據中心,如何實現其負載均衡成為研究熱點問題.虛擬機遷移技術是解決數據中心資源分配問題的有效解決方法,其在提供平臺有效服務的情況下對節點虛擬機資源進行調整,以提高平臺資源利用率,保證服務質量,是實現數據中心負載均衡的有效手段之一[2–4].

1 基于虛擬機遷移的負載均衡策略

1.1 相關介紹

基于虛擬機遷移技術的負載均衡策略,即將負載過高或過低的節點服務器進行相應的虛擬機遷移操作,通過調整節點服務器負載,達到整個平臺的負載均衡[3].由于任務到達具有隨機性,節點的負載也是不斷變化的,若想實現數據中心的負載均衡,則需一套虛擬機動態遷移策略,通過監測數據中心節點的負載狀況,動態地進行虛擬機遷移調整[4],從而提高節點資源利用率,改善數據中心的負載均衡.

虛擬機遷移過程可以分為兩大模塊:遷移觸發時機與遷移選擇策略.遷移時機觸發策略即根據節點資源使用狀態判斷是否達到遷移條件,從而觸發下一模塊;遷移選擇策略包括選擇待遷移虛擬機和目標節點,即確定待遷移虛擬機至其遷移目的節點的最佳方案.

遷移時機觸發策略通常使用狀態閾值法,將每種狀態設定閾值進行劃分,但在判斷遷移時機時需要避免負載瞬時值影響時機判斷的準確性,從而避免由遷移時機不準確導致的過遷移現象.狀態閾值法分為靜態閾值法與動態閾值法,由于靜態閾值法一經設定后不能根據資源使用狀態動態調整,故而存在適應性差和靈活度低問題.文獻[5]提供了一種根據數據中心整體負載量調整閾值窗口的遷移時機判決算法方法,有效解決了由靜態閾值造成的虛擬機頻繁遷移問題.文獻[6]使用以調度頻率和負載率作為反饋值的動態閾值法判定觸發時機可以有效根據資源動態變化開啟調度時機,但是未考慮數據中心整體的負載度,當數據中心接受大量任務時可能導致數據中心的整體負載度過高.文獻[7]使用負載預測的方法對未來幾期的負載進行預測,進而減少負載瞬時值的影響,但觸發時機的合理性由預測方法的準確性來決定,雖復雜算法可以提高預測的準確性,但是會增加計算資源的消耗.

遷移選擇策略旨在快速解除節點過載狀態,即如何選擇需遷移的虛擬機與目的節點,在最少遷移代價與最少遷移時間的條件下將待遷移虛擬機遷移至目的節點,調整節點資源狀態,使得數據中心回到負載均衡范圍.文獻[8]使用采用最大相關性虛擬機選擇算法(RRVMS)和多資源相關匹配目的主機選擇算法(RMRHS)對虛擬機進行遷移,即選擇最大相關虛擬機遷移到資源最小相關的目的主機上,可以有效減少遷移次數從而降低能耗,但未考慮到遷移代價和負載均衡問題.文獻[9]根據虛擬機與服務器資源的相關性與資源權重比選擇相關性大但帶寬資源利用率低的虛擬機,并考慮遷移數量以及資源匹配程度選擇目標主機,可以有效減少遷移代價.但是該方法的遷移開銷僅考慮了遷移次數,具有一定的局限性.

針對以上問題,本文設計了一種基于虛擬機動態遷移的負載均衡策略,通過監控全局負載度與高低負載節點占比動態調整閾值從而實現對節點資源的狀態評估與遷移時機判定;使用基于負載類型感知的選擇策略,即通過考慮虛擬機與節點資源的依賴度和虛擬機貢獻度選擇待遷移虛擬機,并根據虛擬機與目的節點的資源匹配度與遷移代價選擇目的節點,實現對高負載與低負載節點的虛擬機動態調整,從而優化節點資源配置并改善數據中心負載均衡.

1.2 相關定義

本文考慮到異構節點的資源配置差異,選取CPU使用率、內存使用率和帶寬使用率作為負載指標,并將過載情況分為三種類型:CPU 過載型、內存過載型和帶寬過載型[10],從而對節點負載情況進行評估,相關定義如下:

定義1.數據中心有n個節點,第i個節點的資源配置為:ri=(cpui,rami,bandi),記節點i的CPU 利用率為CUi、內存利用率為RUi、帶寬利用率為BUi,則節點i的負載向量Ni為:

若各負載指標的權值為Ki=[k1k2k3],其中k1+k2+k3=1.則節點i的負載度為:

那么,數據中心負載度即全局負載度可由數據中心所有開啟的節點負載度的平均值表示,公式如下:

定義2.設節點負載超過高位閾值Thrh為重載;負載低于低位閾值Thrl為輕載;負載位于兩個閾值之間為適載.則表示如下:

其中,Thrcpu、Thrram、Thrband和分別為CPU、內存和帶寬的高位閾值,分別根據各自的利用率設定.Thrl則根據節點負載度進行設定.

定義3.低于低位閾值的節點集合為L;將超過高位閾值的節點組成高負載節點矩陣H,根據其過載類型使用節點狀態標記進行區分,表示如下:

其中,第i行為第i個節點的各參數值;第一行為節點的負載指標向量的轉置;第二列為節點狀態標記,值為1 表示CPU 利用率高,值為2 表示內存利用率高,值為3 表示帶寬利用率高.最后一位Num表示節點編號.

2 基于動態閾值的遷移時機判決算法

虛擬機遷移觸發時機的選擇至關重要,針對現有的靜態閾值的適應性差和靈活度低問題,本文通過分析數據中心全局負載度、高負載比率和低負載比率對實現對閾值的動態調整,從而增加遷移觸發策略的靈活性與觸發時機的合理性.

2.1 動態閾值調整方案

(1)考慮因素

本文閾值動態調整方案考慮因素共有3 個:數據中心負載度(全局負載度)、高負載比率和低負載比率.下面介紹3 種因素的求解方法及對其數據中心的影響.

① 全局負載度

全局負載度是評價數據中心整體負載情況的有效方法之一.當全局負載度過高時,數據中心整體接收大量的負載任務,此時需增加可用資源承接負載任務以均衡全局負載;當全局負載度過低時,數據中心接收的負載任務減少,此時需縮減可用資源范圍.全局負載度計算方法如下:

取t時段內的負載信息并根據公式(3)得到此時段內負載度集合{Lddc(1),Lddc(2),···,Lddc(t)};為了減小負載瞬時值的影響,剔除該集合中的m個孤立點,此時負載度集合為 {Lddc(1),Lddc(2),···,Lddc(t?m)},再采用權重法計算全局負載度,如下:

其中,l1+l2+···+lt?m=1,權重系數li按指數遞增,公式為:

為保持數據中心負載均衡度,需為數據中心設置負載均衡范圍(ωl,ωh),此范圍內數據中心負載度為適宜的,此范圍取值依據為數據中心此時段歷史負載度.

② 高負載比率與低負載比率

高低負載節點比率表現出數據中心節點利用率情況.當高負載節點數量過多時,會多次觸發遷移操作,造成虛擬機頻繁遷移,造成資源浪費,此時需要適量調高高位閾值或開啟新的節點服務器;低負載節點比率過多時,此時數據中心過多服務器資源處于未充分利用狀態,故調低低位閾值并關閉部分節點服務器.設高負載比率、低負載比率分別為Lrh和Lrl,權重系數li計算見式(9),在t時間段內,計算公式如下:

設置高負載比率(minLrh,maxLrh)和低負載比率范圍(minLrl,maxLrl)以判斷調整閾值和開啟或關閉節點的時機.

(2)調整流程

通過全局負載度與高低負載節點比率實現對狀態閾值的動態調控流程如下:

當Lddc≠(ωl,ωh)時,若m inLrl

其中,Thrh′、Thrl′分別表示調整前的高位閾值和低位閾值,τh和τl分別為高位和低位閾值的調節因子,當Lddc<ωl時,τh和τl皆為正數,當Lddc>ωh時,τh和τl皆為負數.

當Lddc<ωl且Lrl>maxLrl時,數據中心負載度偏低,此時需要選擇需要進行遷移操作的部分輕載節點,在輕載節點完成遷移操作后會關閉該節點.確定待遷移(關閉)輕載節點列表方法如下:

首先將輕載節點按負載度進行升序,此時輕載節點列表 {NL1,NL2,···,NLs},則對應節點負載值列表為{Ld1,Ld2,···,Lds},Lddc為此時的全局負載度,n為正在使用的節點總數,設需要關閉的節點為k個,則k應該滿足如下條件的最小正整數:

當Lddc>ωl且Lrh>maxLrh時,數據中心負載度偏高,此時開啟一個新的節點.

本文采用的動態閾值調整具體流程如圖1所示.

圖1 狀態閾值動態調整流程圖

2.2 遷移觸發算法

由狀態閾值可以對節點負載狀態進行評估,是判斷節點是否需要進行遷移調整的重要步驟,其評估結果是遷移觸發時機判定的重要依據.但是節點負載變化時會出現短時間內的負載抖動現象產生負載瞬時值,進而影響遷移觸發時機的判斷,降低虛擬機遷移的有效性.本文采用乘積指數加權法[11]對m期內的負載進行評估,乘積指數加權公式如下:

其中,wt為第t期權重系數.若此時為負載過載評估,則T1為 負載超過高位閾值的期數,T2為負載低于高位閾值的期數;若為負載輕載評估,則T1為負載值低于低位閾值的期數,T2為負載值高于低位閾值的期數.

根據以上狀態閾值動態調整方法結合負載值評估方法,設計了虛擬機的遷移時機判決算法,內容如算法1.

算法1.基于動態閾值的遷移時機判決算法1)收集各節點負載信息,計算監測時間內全局負載度與高低負載節點占比,判斷是否需要更新閾值,是則轉第2)步,否則轉第3)步.2)分析全局負載度與高低負載占比,調整并更新狀態閾值.3)根據狀態閾值,分別判斷各節點負載狀態.若節點負載指標高于高位負載,開啟該節點該負載指標過載評估,轉第4)步;若節點負載度低于低位負載,開啟該節點負載度輕載評估,轉第5)步;均未達到高低閾值要求為適載節點,則轉第7)步.4)對節點超過高位閾值的負載指標進行m 期的查詢并計算其評估值,若評估值達到過載要求,則判斷此節點為該指標類型過載,根據定義3,更新高負載節點矩陣H.轉第3)步,繼續循環.5)對負載度低于低位閾值的節點進行m 期的負載度查詢并計算其評估值.若m 期內評估值均達到輕載要求,則判斷此節點輕載節點,加入低負載節點列表.轉第3)步,繼續循環.6)將低負載節點列表按負載度升序,結合全局負載度,判斷是否在負載均衡范圍 中,若,則根據式(11)計算得到待遷移操作的輕載節點集合L,若 且,則啟用一個節點.7)輸出高負載節點矩陣H 與低負載節點矩陣L.(ωl,ωh)Lddc<ωl Lddc>ωl Lrh>maxLrh

上述算法可以通過動態閾值判斷遷移時機并得到高負載與低負載節點列表,即確定需進行遷移選擇策略的節點.

3 基于負載類型感知的遷移選擇算法

基于動態閾值的遷移時機判決算法確定了需進行虛擬機遷移操作的高負載與低負載節點列表,本節的遷移選擇算法包含兩個方面:待遷移虛擬機的選擇算法和目的節點的選擇算法,旨在選擇合適的待遷移虛擬機與目的節點,解除節點過載與輕載狀態.

3.1 虛擬機選擇算法

根據過載節點內所有虛擬機使用資源情況,選擇合適的待遷移在虛擬機遷移過程中至關重要.本文將過載情況根據過載資源類型進行劃分,以最少遷移次數為目標,那么待遷移虛擬機的選擇即可描述為節點遷移走后某虛擬機后過載資源回到適載范圍(即不超過此資源類型的高位閾值),使用以下公式描述:

其中,Ntype為節點資源為type類型的指標,為虛擬機在n時段所使用的平均資源利用率向量.除了滿足此條件,還需考慮其他方面因素,如下:

(1)虛擬機與節點的資源依賴度

考慮到最快解決過載狀態,引入虛擬機與節點的資源依賴度來評價虛擬機使用節點的資源情況,按過載類型尋找該類型資源依賴度高的虛擬機.虛擬機與節點的資源的依賴度Rtype定義如下:

其中,Vi為虛擬機在i時刻的某指標資源利用率,Ni為節點在i時刻的該指標資源利用率,Rtype越大則表示該虛擬機與此節點的該指標類型資源的依賴越高.

(2)虛擬機當前內存帶寬比

虛擬機遷移的核心考慮因素是虛擬機內存頁的遷移,此外還易受到節點帶寬因素的影響,故而在遷移開銷最小化的目的下選取虛擬機當前內存帶寬較小的虛擬機,公式如下:

其中,Ri為此節點i的可用內存;Bi為此節點i可用帶寬;vramj為虛擬機j的內存.

(3)虛擬機負載貢獻度

虛擬機負載貢獻度表現出此虛擬機使用此節點資源情況,此值越大則表示該虛擬機使用的資源越多.已知虛擬機在n時段所使用的平均資源利用率向量為V,該節點的負載指標的權值為K,則該虛擬機在此節點上的負載貢獻度用式(16)描述:

若限定了某種資源類型Lc的值越大則代表另外虛擬機使用的兩種資源越多.

由式(13)至式(16)可以得到影響虛擬機選擇的3 個指標值,為了獲得較少的遷移時間與遷移開銷,使用式(17)對這3 個指標值進行處理.

選擇待遷移虛擬機時將虛擬機按照此參考值升序排列,選取此參考值小的虛擬機可獲得最少的遷移次數、較少遷移時間與遷移代價.

為了方便為待遷移虛擬機選擇目的節點(即下一小節),為待遷移虛擬機計算資源比,即以下公式:

由虛擬機使用資源比可以得到此虛擬機的資源偏向類型.

考慮到以上問題,本文以最快解決節點過載問題為目的,選取遷移時間最短的虛擬機,算法表達如算法2.

算法2.待遷移虛擬機選擇算法1)根據節點評估得到的高負載節點列表,獲取高負載節點信息.2)根據此節點過載類型,根據式(13)計算一次遷移可使得該節點解除過載情況的待篩選虛擬機集合.3)根據式(14)計算待篩選虛擬機集合中各虛擬機的此類資源依賴度,并按遞減排序.4)根據式(15)計算各虛擬機的內存帶寬比;根據式(16)計算虛擬機的負載貢獻度.5)根據式(17)選擇虛擬機作為待遷移虛擬機并計算其資源比,加入待遷移虛擬機列表.

若節點是由于輕載需進行遷移,則直接獲取其上運行的虛擬機,計算其資源偏向比并加入待遷移虛擬機列表.

3.2 目的節點選擇算法

目的節點的選取即為虛擬機選取合適的目的節點,即虛擬機安置問題,高效的目的節點選擇算法有利于提高整個平臺的穩定性和資源的高效利用.要考慮的因素主要有虛擬機與目的節點的資源匹配度以及遷移代價.

虛擬機與目標節點的資源匹配度主要用來度量節點剩余資源與待虛擬機所需資源的承接情況.考慮到資源利用的均衡性,依據虛擬機資源偏向優先為其配置該資源剩余度高的節點.匹配度描述如下:

其中,m表示當前有m個虛擬機正在遷移到該臺服務器上,Tbest為設定的節點承載虛擬機遷移的最大數目;Lci為第i個虛擬機的資源需求量;

選擇目的節點必須要考慮的一個問題就是虛擬機的遷移代價,這代表者虛擬機遷移過程中的資源損耗,若是遷移代價過高,則會造成資源浪費.虛擬機到目的節點的遷移代價與兩者距離有關,其遷移代價由式(20)定義:

其中,Nitarget指Vi的目的節點,Njsrc為Vi的源節點;為V(i到目)的節點和源節點上剩余虛擬機Vj的 通信距離;為虛擬機之間的通信量.

根據以上內容,設計目標節點選擇算法表達可見算法3.

算法3.目標節點選擇算法1)根據節點評估得到的適載節點列表,由負載度遞增排序,得到待選節點列表.2)根據式(19)計算待選節點列表計算虛擬機與節點的匹配度,并按遞減排序.3)按照匹配度順序根據式(20)分別計算遷移代價.4)選取匹配度高且遷移代價最小的節點為目的節點.

4 實驗驗證與分析

4.1 實驗準備

為了驗證基于虛擬機動態遷移的負載均衡策略的有效性,采用CloudSim 仿真平臺進行仿真驗證.建立含有異構節點的數據中心,并配置多規格虛擬機,為使仿真使用的物理機和虛擬機負載更接近現實情況,使用PlanetLab 項目中提供的虛擬機監測數據作為實驗負載,模擬數據中心進行虛擬機遷移的仿真實驗,實驗配置如表1.

表1 實驗配置表

為了比較本文策略的仿真效果,使用以下指標對遷移策略的性能進行分析:

1)虛擬機遷移次數.實驗中,由于虛擬機個數、負載和位置的變化,導致節點的負載動態變化,虛擬機遷移策略影響著虛擬機的遷移次數,故獲取指定時間內的虛擬機遷移次數,用來觀測系統的虛擬機的遷移頻率,是判斷虛擬機遷移策略性能的重要指標.

2)數據中心平均負載度.數據中心負載度是衡量數據中心負載情況與資源分配情況的有效指標,若負載度保持較低水平則說明較多節點存在過多的空閑資源,即資源分配不均衡,若此指標數值過高,則說明存在大量過載節點.

3)平均SLAV (Service Level Agreement Violation,SLAV).平均 SLAV 即平均服務等級協議違例率,用來評價用戶服務質量水平的常用指標之一,該值越低則表示用戶服務質量越高.由于本文算法綜合考慮了節點的CPU 資源、內存資源和帶寬資源,使用多維度平均SLAV 計算方法,如式(21):

其中,表示虛擬機需求的type類型資源量,為虛擬機type類型資源的實際使用量.K為一個周期內的違約次數.

4.2 實驗分析

為了比較本文算法的仿真效果,將使用兩個對比方案進行實驗對比.對比方案分別為:瞬時遷移觸發策略搭配最大相關性選擇策略的虛擬機遷移策略(以下稱策略1)與文獻[9]中的基于雙門限與資源需求相關性匹配的虛擬機遷移算法(以下稱策略2).針對虛擬機遷移的兩個模塊進行兩組實驗,第一組為遷移觸發策略比較實驗,用以分析本策略中基于動態閾值的負載評估算法觸發遷移時機的合理性;第二組實驗為遷移策略性能比對實驗,分析比較3 種不同的遷移策略效果,并對本文策略進行綜合評價.

實驗一.遷移觸發策略對比組

合理的遷移觸發策略可以有效判斷虛擬機遷移時機,并通過觸發時機的合理性減少由于節點負載不均衡導致的服務效率問題.通常通過觀測虛擬機遷移次數,從而分析遷移觸發策略的性能.

本實驗組使用3 種觸發策略并在同一種選擇策略的條件下進行實驗,通過收集一段時間內不同虛擬機數量下的虛擬機遷移次數進行可視化分析.3 種觸發策略分別為:策略1 中的瞬時觸發方式、策略2 中的雙門限觸發方式和本文動態閾值觸發方式.實驗結果如圖2所示.

圖2 虛擬機遷移次數對比圖

由圖2可見,隨著虛擬機數目的增加,3 種觸發策略下的虛擬機遷移次數也逐漸增加.其中,由瞬間觸發策略下的虛擬機遷移頻率曲線斜率最大且增長速度明顯高于其他兩種策略,動態閾值觸發策略下的虛擬機遷移頻率最為平緩,由此可見使用基于動態閾值的負載評估算法進行遷移時機判斷更能有效減少由瞬時峰值導致的虛擬機遷移,更有效解決由于虛擬機頻繁遷移導致的資源浪費問題.

實驗二.遷移策略性能比對組

將本文遷移策略、策略1 和策略2 的實驗效果進行分析比較,主要從數據中心的負載度和平均SLAV進行比較.不同虛擬機數量下的數據中心的負載度對比圖如圖3所示.

圖3 數據中心負載度對比圖

隨著虛擬機數目的增加,3 種遷移策略下的數據中心負載度逐漸增加,由策略1 下的數據中心負載度曲線增長最快且波動最明顯,本文遷移策略下的數據中心負載度增長最慢且趨勢平緩,可見本文考慮虛擬機和節點過載資源的依賴關系和虛擬機負載貢獻度的虛擬機選擇算法配合根據虛擬機與目的節點資源匹配度和遷移代價的目的節點選擇算法在保持數據中心負載均衡方面是有效的.

保證數據中心處于較高水平的服務質量也是評價虛擬機遷移策略效果的必要的指標.本文通過分析平均SLAV 對3 種遷移策略下的服務質量進行評價,不同虛擬機數量下的平均SLAV 比較圖如圖4所示.

圖4 數據中心平均SLAV 對比圖

由圖4可見,隨著虛擬機數目的增加,3 種遷移策略下的數據中心平均SLAV 呈現不同程度的波動趨勢,策略1 的平均SLAV 曲線波動明顯,策略2 其次,本文策略具有最平穩的變化趨勢,由此可見,本文策略可以有效地保證數據中心的SLAV 的違背率,并提供較為穩定的服務質量.

綜上所述,本文基于動態閾值的負載評估算法可以有效合理地對遷移時機進行判斷并有效減少負載瞬時變化引起的遷移問題;基于負載類型感知的選擇策略包括根據虛擬機與節點過載資源的依賴關系與虛擬機負載貢獻度的虛擬機選擇算法與根據待遷移虛擬機與目的節點的資源匹配度與遷移代價的目的節點選擇算法在保證服務質量與數據中心負載均衡方面是有效的.

5 結論與展望

本文針對數據中心異構節點設計了一種基于虛擬機動態遷移的負載均衡策略,旨在通過解決異構節點鐘各資源利用率不均衡問題達到數據中心負載均衡.設計了基于動態閾值的負載評估算法用于判斷遷移時機與基于負載類型感知的選擇策略.實驗證明,本文遷移策略可以有效減少虛擬機遷移頻率,保證服務質量并改善數據中心的負載均衡能力.