鄧志龍, 段哲民, 李劉濤

?

OpenStack環(huán)境下的資源動態(tài)調度研究

鄧志龍1,3, 段哲民1, 李劉濤2

摘要：針對云計算平臺中資源調度問題,提出了基于OpenStack的虛擬機動態(tài)調度算法。算法主要采用了基于節(jié)點負載的上線和下線觸發(fā)策略和以提高服務質量和減少遷移成本的待遷移虛擬機選擇策略.為了避免群聚效應,維持系統(tǒng)的負載均衡,通過計算虛擬機對節(jié)點的需求度來衡量虛擬機與節(jié)點間的匹配度,利用匹配度制成概率輪盤的目的節(jié)點的選取策略。最后結合云計算仿真平臺CloudSim對算法工作的情況進行模擬,驗證了算法的調度質量。

關鍵詞：云計算;資源調度;負載均衡

伴隨著網(wǎng)格計算(grid computing)、面向服務(service-oriented)及虛擬化(virtualization)等技術的發(fā)展與進步,云計算在理論及技術上得到了強有力的支持和推進,逐漸成為人們關注的焦點和未來計算模式的發(fā)展趨勢。

目前,越來越多的應用服務提供商和中小型企業(yè)把應用部署到云平臺上,云平臺數(shù)據(jù)中心的數(shù)據(jù)逐漸增多,需要的服務器也逐漸增多,但是資源利用率不高的現(xiàn)象卻普遍存在于云數(shù)據(jù)中心。如何提高資源利用率、維持系統(tǒng)的負載均衡以及減少能量消耗,已逐漸成為各企業(yè)在搭建云平臺時重點考慮的問題。本文結合當前流行的開源云平臺OpenStack,對OpenStack中的資源調度算法進行了研究,在此基礎上提出了基于OpenStack的虛擬機動態(tài)調度算法,來維持云平臺系統(tǒng)運行過程中的負載均衡,同時減少能量消耗。

1OpenStack的調度策略分析

在基于OpenStack搭建的私有云或者公有云中,往往都支撐著一系列具體服務的運行。平臺數(shù)據(jù)中心負載往往很高,所以需要加入許多物理服務器來組成資源池以滿足上層的服務需求。如何分配和使用這些資源,涉及資源調度的問題,在OpenStack構架中scheduler模塊負責解決該問題。圖1為OpenStack中Nova compute的結構圖。

圖1　Nova compute結構圖

在Nova中,scheduler的實現(xiàn)機制是:從AMQP(高級消息隊列協(xié)議)隊列中接收一個RPC消息,再根據(jù)調度策略將消息轉發(fā)給其認為最合適的compute節(jié)點。Nova調度器支持多種可能的因素來決策,比如compute負載、內存使用率等,在Nova中使用比較多的是FilterScheduler調度器。FilterScheduler調度器的處理大致可以分為2個步驟:過濾(filtering)和權衡(weighting)。據(jù)指定的過濾方法(比如在指定的可用區(qū)域額內,CPU使用率小于5%,內存使用率小于20%等)對所有的可用計算節(jié)點進行過濾,得到滿足這一條件的所有計算節(jié)點的集合。然后將請求消息中指定的要求與過濾后的所有計算節(jié)點的當前特征值進行逐一對比,根據(jù)請求和計算節(jié)點的匹配度得到相應成本值(costs),將所有成本值相加得到權重值,并按照權重值的大小將計算節(jié)點進行排序,最后為要處理的消息選擇權重值最小的節(jié)點,在此節(jié)點上分配虛擬機。

OpenStack采用了快速租用的調度算法來滿足虛擬機的初始分配,但是缺乏根據(jù)節(jié)點實際運行過程中的動態(tài)調度策略,比如通過虛擬機的動態(tài)遷移來滿足系統(tǒng)的負載均衡,因此,OpenStack搭建的云平臺在運行一段時間之后,可能出現(xiàn)某些節(jié)點的負載過高,提供的服務質量下降,而其他節(jié)點可能相對空閑,負載較少,而且長時間工作在低負載的情況下,這樣不僅容易造成系統(tǒng)負載不均衡,而且浪費了大量的資源。所以,在OpenStack中需要一個動態(tài)的調度算法在運行過程中對資源進行合理調度,來補充原有算法的不足,維持系統(tǒng)的負載均衡。

2資源動態(tài)調度算法

如何平衡系統(tǒng)中各節(jié)點的負載,實現(xiàn)資源的動態(tài)調度,主要涉及以下3個問題:①虛擬機遷移的觸發(fā)機制,即哪個節(jié)點需要進行虛擬機遷移;②源節(jié)點中待遷移虛擬機的選取,即這個節(jié)點中需要遷移哪些虛擬機;③目的節(jié)點的選取[1],即將這些虛擬機遷移到哪些節(jié)點上。三者之間關系可以用圖2表示。

2.1遷移觸發(fā)策略

定義1能耗(power consumption):節(jié)點運行時消耗的電量的總和。一般情況下,一個節(jié)點的電能消耗絕大部分來自于CPU的使用,與CPU的使用率近似成以下關系[2]

(1)

式中,P為電能消耗總和,Cusage為節(jié)點CPU使用率,Fmax為滿負載情況下節(jié)點的電能消耗,k為空閑情況下節(jié)點電能消耗占滿負載情況下電能消耗的比例。由公式可以看出當Fmax確定,且k值一定時,該節(jié)點的電能消耗P的大小只取決于該節(jié)點CPU的利用率Cusage,節(jié)點從空閑到滿負載的電能消耗與CPU利用率近似成線性關系[2],如圖3所示。

圖3　節(jié)點能耗圖

從圖3可以看出,隨著CPU利用率升高,節(jié)點的能耗增加并不大,但是CPU利用率為0%(即空閑節(jié)點)的能耗卻很高,所以應在保持節(jié)點能正常運行的情況下,盡量提高節(jié)點的負載,并且將空閑出來的節(jié)點關掉,以此來有效減少電能消耗。

定義2工作負載(work load):一個節(jié)點的工作負載可以用節(jié)點的CPU使用率和內存使用率計算而得,采用加權因子W=[w1,w2]對2種資源的利用率進行加權計算,具體該節(jié)點的負載定義為WorkLoad[3]

WorkLoad=w1Cusage(t)+w2Memusage(t)

(2)

式中，Cusage為該節(jié)點在時刻t的CPU使用率,Memusage為該節(jié)點在時刻t的內存使用率,式中w1+w2=1。

定義3負載均衡度(loadbalance):用WorkLoadi表示節(jié)點i的負載,B表示系統(tǒng)負載均衡度,系統(tǒng)中有n個節(jié)點,則B可以用以下公式求得[3]

(3)

(4)

B越小,說明各節(jié)點間負載差值越小,系統(tǒng)負載越均衡。

定義4節(jié)點負載等級(nodeloadlevel):根據(jù)節(jié)點負載的大小,將各節(jié)點負載分為以下幾個等級:

表1　節(jié)點負載狀態(tài)分類

根據(jù)對節(jié)點負載定義,設定雙閾值觸發(fā)機制:基于節(jié)點負載的上線閾值觸發(fā)遷移和下線閾值觸發(fā)遷移,如圖4和圖5所示。采用雙閾值觸發(fā)主要是基于兩方面的考慮,上線閾值的設定主要是為了避免節(jié)點負載過高,無法滿足用戶需求,或者因負載過高導致節(jié)點運行出現(xiàn)故障;下線閾值的設定主要是為了盡量減少運行節(jié)點的數(shù)量,達到節(jié)能的效果。節(jié)點的負載信息包括了CPU的利用率、內存的使用率,能更加準確地描述資源的使用情況,單一的CPU利用率或內存利用率無法真實反映資源的使用情況。

圖4　上線閾值觸發(fā)遷移模擬圖

圖5　下線閾值觸發(fā)遷移模擬圖

實時更新節(jié)點負載信息容易出現(xiàn)瞬時低谷或高峰現(xiàn)象,可能節(jié)點負載瞬間超出了設定閾值,但是能在短時間內迅速恢復下來。為了避免因瞬間的振蕩而錯誤地遷移,在本文中,引入滑動窗口[4],定義滑動窗口的更新周期為W,W值也表征著窗口大小,是一個連續(xù)的時間單元。在該連續(xù)時間單元內,將節(jié)點負載值按照固定時間間隔進行采樣,采用隊列形式組織緩沖池來保存采樣數(shù)據(jù),當下一個更新周期到來時,當前緩沖區(qū)插入到隊尾,頭緩沖區(qū)將作為下一個窗口的接收數(shù)據(jù)。對于上線閾值觸發(fā),在窗口內,設定一個最大超出次數(shù)Mmax,當節(jié)點負載連續(xù)超出閾值的次數(shù)小于Mmax時,滑動窗口不會觸發(fā)報警,當節(jié)點負載連續(xù)超出閾值的次數(shù)大于Mmax時,滑動窗口發(fā)生報警,利用時間序列預測法[5]的AR模型對節(jié)點負載的下一個值進行預測,當預測值仍然超出閾值時,觸發(fā)遷移,否則,不觸發(fā)遷移。對于下線閾值觸發(fā),在窗口內,同樣設定一個最大低于次數(shù)Nmax,當節(jié)點負載連續(xù)低于閾值的次數(shù)小于Nmax時,滑動窗口不會觸發(fā)報警,當節(jié)點負載連續(xù)低于閾值的次數(shù)大于Nmax時,滑動窗口發(fā)生報警,利用時間序列預測法的AR模型對節(jié)點負載的下一個值進行預測,當預測值仍然低于閾值時,觸發(fā)遷移,否則,不觸發(fā)遷移。

2.2待遷移虛擬機選取策略

虛擬機的選取策略就是決定從源節(jié)點上選取哪些虛擬機進行遷移。在選取虛擬機前,必須確保該虛擬機實例保存在NFS共享存儲中,在此基礎上才能實現(xiàn)在線遷移。

首先,進行虛擬機的遷移必須要考慮用戶服務質量,而用戶服務質量主要取決于服務器CPU使用率,盡量選擇CPU使用率高的虛擬機進行遷移,剩下的用戶才能享用更多的CPU資源。虛擬機CPU使用率是第一個考慮因素。其次,在選擇虛擬機遷移的時候要考慮遷移成本,遷移成本主要由遷移時間決定。虛擬機在線遷移過程中,目的節(jié)點會根據(jù)共享存儲里的待遷移虛擬機文件生成一個虛擬機,然后源節(jié)點將待遷移虛擬機的內存向目的節(jié)點拷貝,同時記錄下內存臟頁,內存拷貝結束后,開始拷貝內存臟頁,直到大部分的內存同步后,暫停待遷移虛擬機,將該虛擬機未同步的內存及CPU狀態(tài)同步到目的節(jié)點上,之后目的節(jié)點上的虛擬機開始運行。因此待遷移虛擬機的內存決定了遷移時間。在遷移過程中虛擬機內存的使用是第二個考慮因素。

定義一個節(jié)點上每個虛擬機CPU使用量占該節(jié)點CPU總量的百分比為Ci,虛擬機內存使用量占該節(jié)點內存總量的百分比為Mi,Ui為CPU使用率和內存使用率的比值,即

(5)

通過上面分析,在選取虛擬機時,該虛擬機的Ci越大越好,Mi越小越好,即Ui越大越好。在選取虛擬機前,先將該節(jié)點上虛擬機的Ui進行排序,選取Ui最大的虛擬機進行遷移。

2.3目的節(jié)點選取策略

在遷移策略中,目的節(jié)點的選取尤為重要,它直接影響系統(tǒng)數(shù)據(jù)中心運行節(jié)點的負載均衡情況。如果選取的目的節(jié)點不合理,可能導致不必要的遷移,或者二次遷移,從而增加系統(tǒng)運行負擔及系統(tǒng)能耗。

經(jīng)過虛擬機遷移觸發(fā)以及待遷移虛擬機的選取,將待遷移的虛擬機構成集合V=(V1,V2,…,Vn),選擇第二等級的節(jié)點構成資源池C=(C1,C2,…,Cn)。本文中用CPU使用率、內存、網(wǎng)絡帶寬的三維向量來描述虛擬機和目的節(jié)點的資源。定義遷移虛擬機i對目的節(jié)點j的資源需求向量Dijvm=(dijcpu,dijmem,dijnet),計算公式如下:

(6)

(7)

(8)

式中，i-need表示虛擬機i所需的CPU資源、內存資源、帶寬資源,j-total表示節(jié)點j的CPU資源、內存資源、帶寬資源的總量,j-use表示節(jié)點j的CPU資源、內存資源、帶寬資源已使用量,j-reserve表示節(jié)點j的CPU資源、內存資源、帶寬資源的預留量。只有dijcpu,dijmem,dijnet的值均在(0,1)時,才能滿足遷移虛擬機對節(jié)點的資源需求。如果這3個值有1個大于1,則該節(jié)點不能作為該虛擬機的目的節(jié)點,將該節(jié)點從此虛擬機的遷移目的節(jié)點集合中刪除,剩余的節(jié)點構成該虛擬機遷移的資源池。根據(jù)虛擬機對CPU、內存以及網(wǎng)絡帶寬的需求比例關系,設定權值向量W=(W1,W2,W3),對3種資源需求進行加權計算,得到虛擬機i對節(jié)點j的需求量Sij

(9)

顯然,Sij在(0,1)內,Sij越大,將該虛擬機遷移至該節(jié)點后,該節(jié)點的狀態(tài)越趨近于達到上限。這樣的遷移,會導致其他虛擬機的Sij較小而無法找到合適的目的節(jié)點,擁有更多資源的節(jié)點卻無法接收到遷移的虛擬機,無法滿足負載均衡。在此,定義虛擬機i對節(jié)點j的匹配度Mij

(10)

同樣,Mij也在(0,1)內,Mij越大,虛擬機i對該節(jié)點j的需求越高,虛擬機遷移到該節(jié)點的可能性越大,虛擬機i和節(jié)點j的匹配度越高。

資源多、性能好的節(jié)點能匹配到相對多的虛擬機,此時就容易引起群聚效應,為避免群聚效應的發(fā)生,采用概率輪盤來進行目的節(jié)點的選擇。

定義虛擬機i最終選擇目的節(jié)點j的概率為Pij

(11)

式中,Mij為虛擬機i對節(jié)點j的匹配度。共有n個目的節(jié)點可以選取。其中

(12)

虛擬機i可以根據(jù)選擇節(jié)點j的概率制定概率輪盤,如圖6所示。

圖6　虛擬機1的選擇概率輪盤

每個遷移的虛擬機都有1個選擇概率輪盤。在實現(xiàn)過程中,可以通過1個(0,1)的隨機數(shù)字來判斷所在的區(qū)間,實現(xiàn)虛擬機目的節(jié)點的選取。

由圖6可知,資源越多、性能越好的節(jié)點在輪盤上占用的空間越大,指針最后指向該區(qū)域的可能性也就越大,從而該節(jié)點被選為目的節(jié)點的概率較大。而資源少的節(jié)點在輪盤上占用的空間少,被選為目的節(jié)點的概率也就小。這樣,很大程度上改善了系統(tǒng)負載均衡,也在一定程度上減少了群聚效應的發(fā)生。

3實驗仿真

為驗證本文提出的虛擬機動態(tài)遷移算法的性能,本文采用云計算仿真軟件CloudSim[6]進行仿真驗證。在實驗中,配置了100個節(jié)點,為了更加真實模擬云平臺中資源的異構性,將這100個節(jié)點分成4組,每組25個節(jié)點,組內節(jié)點的配置相同,不同組間的配置不同,具體配置情況如表2所示。

表2　實驗節(jié)點配置

為所有節(jié)點提供300臺虛擬機,每臺虛擬機的CPU在100～200MIP中隨機產生,內存在1～2G中隨機產生,帶寬在5～10Mbps中隨機產生。將這300臺虛擬機隨機安置在這100個節(jié)點上,對500個相互獨立的任務集進行處理,每個任務長度在150 000～200 000中隨機產生。

在節(jié)點負載公式(2)中,設置w1=w2=0.5,監(jiān)控節(jié)點負載,如有觸發(fā)遷移,則動態(tài)地進行虛擬機遷移。每隔100s統(tǒng)計1次節(jié)點的資源利用情況和節(jié)點的負載及系統(tǒng)的負載均衡度。雙閾值觸發(fā)動態(tài)遷移策略與無遷移策略、上線觸發(fā)動態(tài)遷移策略及下線觸發(fā)動態(tài)遷移策略的實驗對比如圖7所示。

圖7　負載均衡統(tǒng)計圖

由于各節(jié)點分配的任務不同,各節(jié)點的負載也不同,遷移次數(shù)隨系統(tǒng)運行時間的增加而增加,傳統(tǒng)的無遷移策略的負載均衡度值要明顯高于有遷移策略的負載均衡度值。負載均衡度值越大,系統(tǒng)負載越不均衡。上線觸發(fā)策略和下線觸發(fā)策略的值要高于雙閾值遷移策略,說明減少低負載節(jié)點使用和高負載節(jié)點資源使用能有效改善系統(tǒng)的負載均衡。

節(jié)點能量消耗主要與CPU使用率有關,假設每個節(jié)點的CPU使用率為0%時,消耗電能175W,CPU使用率為100%時,消耗電能250W,忽略遷移過程中電能消耗,分別對無遷移策略、上線觸發(fā)動態(tài)遷移發(fā)策略、下線觸發(fā)動態(tài)遷移策略及雙閾值動態(tài)遷移觸發(fā)策略的系統(tǒng)仿真大約20min,結果對比如圖8所示。

圖8　能耗對比圖

由圖8看出,下線觸發(fā)策略和雙閾值觸發(fā)策略消耗的電能要明顯低于無遷移策略和上線觸發(fā)策略;所以,減少低負載節(jié)點的使用和關閉空閑節(jié)點能很好地起到節(jié)能效果。同時,上線觸發(fā)策略消耗的電能低于無遷移策略,說明平衡各節(jié)點的資源使用率也能達到一定的節(jié)能效果。

4結論

本文針對云平臺中資源調度問題,結合開源云OpenStack,給出了在OpenStack下進行虛擬機動態(tài)調度算法的具體設計。算法主要解決了虛擬機動態(tài)調度過程中遷移的觸發(fā)問題,源節(jié)點中待遷移虛擬機的選擇問題以及目的節(jié)點的選擇問題。最后結合云計算仿真平臺CloudSim對算法工作的情況進行模擬,驗證了算法的調度質量。

參考文獻：

[1]李強,郝沁汾,肖利民,等. 云計算中虛擬機放置的自適應管理與多目標優(yōu)化[J]. 計算機學報, 2011, 34(12): 2253-2264

LiQiang,HaoQinfen,XiaoLimin,etal.AdaptiveManagementandMulti-ObjectOptimizationforVirtualMachinePlacementinCloudCompution[J].ChineseJournalofComputer, 2011, 34(12): 2253-2264 (inChinese)

[2]HuL,JinH,LiaoX,etal.Magnet:ANovelSchedulingPolicyforPowerReductioninClusterwithVirtualMachines[C]∥Proceedingsofthe2008IEEEInternationalConferenceonClusterComputing, 2008: 13-22

[3]方義秋,唐道紅,葛君偉. 云環(huán)境下基于虛擬機動態(tài)遷移的調度策略研究[J]. 微電子學與計算機,2012,29(4): 45-48

FangYiqiu,TangDaohong,GeJunwei.ResearchonScheduleStrategyBasedonDynamicMigrationofVirtualMachinesinCloudEnvironment[J].MicroelectronicsandComputer, 2012, 29(4): 45-48 (inChinese)

[4]閆朝升,張承江,馬英. 基于滑動窗口的時間序列數(shù)據(jù)流分析與預測技術研究[J]. 黑龍江大學自然科學學報, 2006, 23(6): 863-867

YanZhaosheng,ZhangChengjiang,MaYing.StudyonRegressinAnalysisandPredictionofTime-SeriesDataStreamsUsingSlidingWindows[J].JournalofNaturalScienceofHeiLongJiangUniversity, 2006, 23(6): 863-867 (inChinese)

[5]徐慧娟,周世健,魯鐵定. 自回歸AR模型整體最小二乘分析[J]. 江西科學, 2011,29(5): 543-545

XuHuijuan,ZhouShijian,LuTieding.ARModelofTotalLeastSquareEstimationofInstability[J].JiangxiScience, 2011, 29(5): 543-545 (inChinese)

[6]BuyyaR,RanjanR,CalheirosRN.ModelingandSimulationofScalableCloudComputingEnvironmentsandtheCloudSimToolkit:ChallengesandOpportunities[C]∥Proceedingsofthe7thHighPerformanceComputingandSimulationConference, 2009: 1-11

Research of Dynamic Scheduling of Resources under the Environment of OpenStack

Deng Zhilong1, 3, Duan Zhemin1, Li Liutao2

1.School of Electronics Information, Northwestern PolytechnicalUniversity Xi′an, 710072, China 2.School of Automation, Northwestern PolytechnicalUniversity Xi′an, 710072, China 3.Digtal Informetion Technlogy Department, Shanxi Yacnth Vocation, Coltege, Xi′an, 710068, China

Abstract:A new virtual machine dynamic resources scheduling algorithm based on OpenStack is proposed to optimize scheduling of resources problems under the cloudcomputing platforms. Algorithm mainly adopts the online and offline trigger strategy based on node load and the VM selection strategy to improve the quality of service and reduce the cost of migration. In order to avoid the cluster effect and maintain the balanced workload in the system, the paper evaluates the matched-degree by calculating the VM demand for the node, and then determines the final destination node by the roulette of probability which is made by matched-degree. Finally, the cloud computing simulation platform CloudSim is used to simulate the algorithm and verify the quality of scheduling algorithm.

Keywords:Cloud computing; Resource scheduling; Load balancing

收稿日期：2016-03-01

基金項目：國家自然科學基金(61471299)資助

作者簡介：鄧志龍(1976—),西北工業(yè)大學博士研究生，主要從事信息與信號檢測、識別、處理及系統(tǒng)控制等方面的研究。

中圖分類號：TP391.4

文獻標志碼：A

文章編號:1000-2758(2016)04-0650-06