云計算資源池負載均衡調(diào)度策略研究

許成林 楊德勝 何亮

摘? 要：本文研究資源池下的主機負載均衡算法，包括CPU、內(nèi)存與網(wǎng)絡(luò)負載3個方面。資源池下主機負載均衡主要包括兩個階段，包括新建資源池和更新資源池。這兩個階段有一定的共通性，即都考慮了資源池下主機多項資源的負載均衡;但是也存在顯著差異。新建資源池時進行負載均衡不用考慮虛擬機遷移操作;更新資源池時卻必須考慮，因虛擬機在主機之間進行遷移將根據(jù)虛擬機內(nèi)存變化量的大小而短暫地暫停虛擬機，根據(jù)SLA（服務(wù)等級協(xié)議）的相關(guān)要求，虛擬機在線遷移操作是存在一定代價的，本文定義其為虛擬機遷移代價。本文在資源池狀態(tài)變化時不光考慮了主機CPU、內(nèi)存與網(wǎng)絡(luò)三種資源的負載均衡，同時還為盡量減小虛擬機遷移代價做了特別優(yōu)化。

關(guān)鍵詞：云計算? 負載均衡? 遺傳算法? 策略研究

中圖分類號：U416.214? ? ? ? ? ? ? ? ? ? ? ? 文獻標(biāo)識碼：A? ? ? ? ? ? ? ? ? 文章編號：1674-098X（2020）07（b）-0106-07

Abstract： This paper studies the host load balancing scheduling strategy in the resource pool，including CPU， memory and network load. There are two main stages of load balancing in the resource pool， including creating resource pool and updating resource pool. There is a certain commonality between the two stages， that is， the load balancing of multiple host resources in the resource pool is considered， but there are also significant differences. Load balancing when creating a new resource pool does not consider virtual machine migration; Resource pool updates must be considered， however， as the virtual machine migrates between hosts， the virtual machine will be temporarily suspended， and the time to suspend depends on the size of change in the virtual machine memory. According to relevant requirements of SLA （service level agreement）， virtual machine online migration operation has a certain cost， which is defined as virtual machine migration cost in this paper. This paper not only considers load balancing of host CPU， memory and network when resource pool state changes， but also makes special optimization to minimize the migration cost of virtual machine.

Key Words： Cloud computing; Load balancing; Genetic algorithm; Strategy research

1? 相關(guān)研究

目前國內(nèi)外學(xué)者對資源池下的主機負載均衡提出了多種方法：（1）根據(jù)雙向螞蟻記錄分配資源這一理念提出了一種改進的蟻群算法，但是其將多目標(biāo)算法函數(shù)簡單處理成了單目標(biāo)算法函數(shù)，這可能導(dǎo)致從主機外部看其可能處于負載均衡狀態(tài)，但從其內(nèi)部的CPU、內(nèi)存以及網(wǎng)絡(luò)負載著卻可能處于失衡狀態(tài)，同時其也未考慮虛擬機遷移代價的問題;（2）提出了一種基于雙向反饋的蟻群算法的負載均衡調(diào)度策略，但研究時發(fā)現(xiàn)為每只螞蟻建立自己的正反向結(jié)構(gòu)集合會導(dǎo)致占用太多的資源，并在信息素局部更新時會導(dǎo)致收斂的速度加快從而無法獲得全局最優(yōu)解;（3）提出了基于一種改進的遺傳算法的資源池負載均衡策略，但是其只考慮了CPU與磁盤I/O這兩個方面，對于當(dāng)前需要考慮更多維度的實際情況已不再適合;（4）提出了一種基于服務(wù)器資源權(quán)重的方法將多維資源的負載函數(shù)轉(zhuǎn)換成單一維度負載函數(shù)，但其過多地考慮了人為設(shè)置的因素，通常在基于FC-SAN的資源池中，作為計算節(jié)點的主機需同時考慮CPU、內(nèi)存及網(wǎng)絡(luò)負載，而并不是僅僅關(guān)注某一項;（5）采用輪詢調(diào)度算法對虛擬機進行分配以實現(xiàn)資源池負載均衡，其使用局部調(diào)度而不能實現(xiàn)全局優(yōu)化，同時其也未考慮虛擬機遷移成本的問題。

本文將資源池分為新建與更新兩種狀態(tài)。對于新建資源池，本文使用了類似遺傳算法種群初始化的方法對解空間進行初始化以保證解空間的多樣性，之后基于模擬退火算法循環(huán)遍歷處理前面通過遺傳算法得到的解，最后在滿足預(yù)設(shè)的資源池負載均衡條件后終止循環(huán)，并輸出當(dāng)前最優(yōu)解;對于更新資源池，可以通過預(yù)設(shè)的資源池負載均衡條件來動態(tài)調(diào)整資源池整體的虛擬機遷移成本，這給予實際生成環(huán)境極大的靈活性。

2? 問題的形式化描述

2.1 資源池負載均衡調(diào)度的數(shù)學(xué)模型

資源池中主要包含了計算、存儲與網(wǎng)絡(luò)資源，本文不考慮存儲，而計算資源包括主機的CPU與內(nèi)存，網(wǎng)絡(luò)資源則表示主機的帶寬。

從資源池中包括的對象而言，主要包括作為計算節(jié)點的主機以及運行在主機上的虛擬機，同時將資源池整體抽象為一個對象。本文假定資源池中存在n個主機以及m個虛擬機?，F(xiàn)在進行以下定義：

映射方案：包含了資源池下所有主機與虛擬的映射關(guān)系，用F表示，則F={scheme1，scheme2，scheme3，……，schemen }，其中Fs（1≤s≤n）表示第s個映射方案。

虛擬機：定義CPU核數(shù)為vmCpuNum，內(nèi)存大小為vmMemSize，網(wǎng)絡(luò)帶寬使用量vmNetUseWidth，CPU使用率為vmCpuUseRatio，內(nèi)存使用率為vmMemUseRatio;則CPU使用量vmCpuUseNum = vmCpuNum*vmMemUseRatio，內(nèi)存使用量vmMemUseSize = vmMemSize*vmMemUseRatio。

主機：定義CPU總核數(shù)為hostCpuTotalNum，總內(nèi)存大小為hostMemTotalSize，總網(wǎng)絡(luò)帶寬為hostNetBandTotalWidth;設(shè)空閑CPU資源為hostCpuFreeNum，空閑內(nèi)存資源為hostMemFreeSize，空閑網(wǎng)絡(luò)帶寬為hostNetBandFreeWidth;由此可得主機CPU使用率hostCpuUseRatio = 1-hostCpuFreeNum/hostCpuTotalNum，內(nèi)存使用率hostMemUseRatio = 1-hostMemFreeSize/hostMemTotalSize，網(wǎng)絡(luò)帶寬使用率hostNetUseRatio = 1-hostNetBandFreeWidth/hostNetBandTotalWidth。

主機資源傾斜度：其表示了主機的CPU、內(nèi)存與網(wǎng)絡(luò)的使用率與資源池平均CPU利用率、內(nèi)存利用率、網(wǎng)絡(luò)利用率之差，包括CPU傾斜度hostCpuSkew=100*（ hostCpuUseRatio - poolAvgCpuUseRatio） ，內(nèi)存傾斜度hostMemSkew =100*（hostMemUseRatio- poolAvgMemUseRatio），網(wǎng)絡(luò)傾斜度hostNetSkew = 100*（hostNetUseRatio- poolAvgNetUseRatio），主機總資源傾斜度hostSkew = Math.abs（hostCpuSkew）+ Math.abs（hostMemSkew） + Math.abs（hostNetSkew），這里Math.abs（x）函數(shù)將獲得數(shù)值x的絕對值。

2.2 應(yīng)用場景和范圍

在本文中，主要考慮資源池使用共享FC-SAN（光纖存儲）作為虛擬機磁盤文件的場景，主機使用HBA卡與光纖存儲交換機連接，光纖存儲交換機再與FC-SAN連接。通常主機使用的HBA卡（光纖存儲卡）以及與其連接的存儲光纖交換機的讀寫帶寬都比FC-SAN本身提供的讀寫速率高很多，所以主機磁盤I/O主要取決于FC-SAN本身的讀寫速率（底層磁盤陣列的讀寫速率），不論是一臺主機還是兩臺主機，瓶頸不在主機而在FC-SAN上，所以本文不考慮主機磁盤I/O的負載均衡。

3? 算法的調(diào)度模型

3.1 遺傳算法的關(guān)鍵元素

個體：資源池下主機與虛擬機的一個具體的映射方案Fs（1≤s≤n）為個體。

種群：一定規(guī)模個體的集合。

種群規(guī)模：種群中個體的總數(shù)量。

基因：資源池下一個具體虛擬機的具體位置（在某臺主機上）以及其對資源池CPU、內(nèi)存與網(wǎng)絡(luò)資源的具體使用量。

最佳適應(yīng)度：本文定義主機的適應(yīng)度函數(shù)為主機資源傾斜度的負相關(guān)函數(shù)，當(dāng)主機資源總傾斜度以及主機的單項資源傾斜度越小則表示越接近負載均衡的目標(biāo)。但由于主機總傾斜度與單項資源傾斜度可能存在沖突，本文將以預(yù)設(shè)條件來使主機的資源使用情況盡量達到預(yù)期效果。

變異：本文定義將虛擬機從一個主機遷移到另一個主機為變異，變異后將導(dǎo)致源主機與目標(biāo)主機的各自的總傾斜度以及CPU、內(nèi)存與網(wǎng)絡(luò)傾斜度發(fā)生變化。在本文中變異包含兩種：第一種是朝著資源池整體傾斜度減小的方向變異，這種變異將會快速地收斂解空間;第二種是朝著資源池整體傾斜度增大的方向變異，這是為了避免陷入局部最優(yōu)解。

交叉：不同個體間互換基因的操作，因為在這里一個個體就是一個資源池下所有主機與虛擬機的映射方案，而適應(yīng)度高的個體在交叉后有很大機率不會變得更好，為了減少計算時間將不使用這種操作。

代數(shù)：種群迭代的次數(shù)。

3.2 新建資源池過程調(diào)度算法

如圖1，算法主流程的第一步是初始化種群，在這一步中，首先初始化待部署的虛擬機以及資源池中存在的主機，遍歷虛擬機以及主機，在所有主機的CPU、內(nèi)存與網(wǎng)絡(luò)資源都不超載的情況下構(gòu)建一個原始映射方案;然后以這個原始映射方案為基礎(chǔ)，通過高概率隨機基因變異的方式最終獲取一定規(guī)模的映射方案集合即種群。

如圖1，算法主流程的第二步是遍歷整個種群中的所有個體，為每個個體開啟一個子處理流程，從此處開始并發(fā)處理每個種群中的所有個體-映射方案。個體處理子流程的具體步驟如圖2。

如圖2，個體處理子流程的第一步是對個體進行有條件的變異，此處的變異操作將以減小源主機與目標(biāo)主機總資源傾斜度為目標(biāo)，這樣即可減小資源池的總體傾斜度以達到增加主機與資源池適應(yīng)度的效果。當(dāng)這個映射方案的適應(yīng)度不再發(fā)生變化的時候，就進行個體處理子流程中的第二步處理。

個體處理子流程第二步的處理過程如下：對當(dāng)前個體，選擇出主機傾斜度以及CPU、內(nèi)存與網(wǎng)絡(luò)的單項傾斜度不符合預(yù)設(shè)條件的主機集合并進行遍歷，假設(shè)當(dāng)前主機為Hi，獲取Hi上運行的所有虛擬機，分別選擇出vmCpuUseNum、vmMemUseSize、vmNetUseWidth最大的虛擬機集合，取這三者中最大的那個值對應(yīng)的虛擬機Vbiggest，獲取整個資源池中虛擬機數(shù)量最多那個主機Hmost，虛擬機數(shù)量多表示其上運行的單臺虛擬機的CPU、內(nèi)存與網(wǎng)絡(luò)利用率更小，因此可以形成較多的組合。將Hi上的虛擬機Vbiggest與Hmost中的多臺虛擬機進行交換，例如：假設(shè)此時Vbiggest是基于vmCpuUseNum的，那么就從Hmost中對虛擬機以vmCpuUseNum從小到大進行排序，循環(huán)處理排序后的虛擬機列表，對每個虛擬機的vmCpuUseNum進行累加求和，設(shè)此值為vmCpuSumUseNum，當(dāng)vmCpuSumUseNum >Vbiggest.vmCpuUseNum時循環(huán)終止，然后進行虛擬機的交換操作。此虛擬機交換操作會增加資源池整體的不均衡度，但對整個資源池負載均衡方案的尋找是有好處的。其好處之一是會將某項資源消耗較大的虛擬機分散到資源池中不同的主機上;好處之二讓集合H_V中的主機上運行更多的虛擬機，這樣通過后續(xù)的操作則更有可能達到預(yù)期的負載均衡狀態(tài)。當(dāng)需要進行交換的主機完成一次遍歷后，檢測終止條件2，如果為否則返回到個體處理子流程的第一步開始循環(huán)整個子流程，直到滿足終止條件2，此時保存當(dāng)前個體，并結(jié)束當(dāng)前的子流程。

如圖1，在主流程中，當(dāng)所有個體處理子流程都結(jié)束之后，此時種群表示為映射方案的集合Fnew = {Snew1，Snew2，Snew3，……，Snewn }，其中Fs（1=

3.3 更新資源池過程調(diào)度算法

在更新資源池狀態(tài)時，本文將以盡量少的虛擬機遷移成本來達到一個符合預(yù)期的資源池負載均衡狀態(tài)為目標(biāo)進行算法設(shè)計。

如圖3，算法主流程的第一步是初始化當(dāng)前的資源池狀態(tài)，通過這一步可以獲取資源池下所有虛擬機與主機在當(dāng)前狀態(tài)的映射關(guān)系，本文設(shè)這個映射關(guān)系為Schemeold。因為后續(xù)子流程中虛擬機調(diào)度存在隨機性，因此在主流程的第二步則可并發(fā)開啟n個子處理流程。當(dāng)所有子流程都處理完成之后，因為都時滿足資源池負載均衡條件的，所以直接選取遷移成本最小的那個映射方案即可。

如圖4，算法子流程的第一步，首先選擇出不滿足資源池負載均衡預(yù)設(shè)的主機必須達到的限制條件時的主機集合HV，遍歷這些主機并進行以下處理。在這里引入MIGRATE_MULTIPLE（強制遷移倍數(shù)），此處理將會引起資源池整體傾斜度的增加，為了避免MIGRATE_MULTIPLE過大引起資源池傾斜嚴(yán)重，其值將從1開始，并以0.02的步長緩慢遞增，在越小的MIGRATE_MULTIPLE完成對主機集合HV的處理則表示需要遷移的虛擬機越少，資源池的整體遷移成本越小。當(dāng)處理完集合HV中的主機之后，將判定此時是否滿足終止條件2，如果滿足則保存此時的映射關(guān)系Schemebest并結(jié)束整個子流程，如果不滿足則跳轉(zhuǎn)到主流程中的第三步從新基于資源池當(dāng)前的映射關(guān)系Schemetmp進行處理。

如圖4，算法子流程的第二步將先獲取映射關(guān)系Schemetmp下不滿足負載均衡條件的主機集合Hnotbalance，將遍歷Hnotbalance中所有主機上的所有虛擬機（此處將優(yōu)先獲取源主機上不在方案Schemeold中存在映射關(guān)系的虛擬機進行處理，這樣可減小遷移代價），計算將源主機Hi上的虛擬機V_ij遷移到目標(biāo)主機Hm上時，Hi與Hm二者的整體資源傾斜度之和是否會減小，如果會減小則進行遷移。終止條件1表示資源池整體傾斜度不再變化，如果滿足終止條件1，則終止循環(huán)并進行終止條件2的判斷。終止條件2將主要判定當(dāng)前映射方案中所有主機的傾斜度是否都已滿足預(yù)設(shè)的資源池負載均衡限條件，例如：任意主機的整體資源傾斜度不超過10，且其上CPU、內(nèi)存與網(wǎng)絡(luò)的單項資源傾斜度均不超過5，通過這兩者的相互制約，可以讓資源池中的主機整體處于負載均衡狀態(tài)。另外，通過修改這兩個值，比如兩者都增大，則可以更多地避免虛擬機遷移，以此來降低更新資源池狀態(tài)時的整體遷移成本。如果此時終止條件2不滿足，則跳轉(zhuǎn)至算法子流程的第一步并繼續(xù)處理;如果終止條件2滿足，則保存此時的映射關(guān)系Schemebest并結(jié)束整個子流程。

4? 實驗仿真與分析

4.1 實驗環(huán)境及參數(shù)設(shè)置

為了評估本文所描述資源池負載均衡調(diào)度策略的有效性與可行性，自己基于Java編寫了一套資資源池運行的仿真程序。程序的核心對象就是資源池、主機與虛擬機，其相關(guān)屬性及屬性間的關(guān)系在3.1小節(jié)已詳細描述。本文設(shè)置主機的相關(guān)配置為：CPU 128核，內(nèi)存256GB，虛擬機調(diào)度使用到的管理網(wǎng)絡(luò)帶寬為1000Mb/s;虛擬機配置則主要有4C8GB、8C16GB及16C32GB 3個檔次，網(wǎng)絡(luò)速率在1000Mb/s 中沒有限制。

按照以上模板分別生成200、400、600、800、1000臺虛擬機，對應(yīng)的主機數(shù)量為15、35、50、70、85臺;這些虛擬中的CPU使用率、內(nèi)存使用率與網(wǎng)絡(luò)占用速率都是在不超載的范圍內(nèi)保持隨機性。

4.2 調(diào)度策略模型仿真與分析

新建資源池時調(diào)度策略可配置的一些參數(shù)有：種群規(guī)模populatioSize;映射方案局部變異次數(shù)countVar，其主要應(yīng)用于初始化種群;資源池整體傾斜度hostSkew，單項資源可承受傾斜度：errorRange。經(jīng)過反復(fù)驗證：設(shè)置populatioSize=200，countVar=60， hostSkew=8，errorRange=4時，可快速獲得負載均衡方案，如圖5，可以看出隨著虛擬機數(shù)量的增加，資源池整體傾斜度基本呈線性增長，而且其中每臺主機的整體傾斜度不超過8且單項資源傾斜度均小于4，可見映射方案的負載均衡性于實用性都較好。

更新資源池時調(diào)度策略可配置的一些參數(shù)有：資源池整體傾斜度hostSkew，單項資源可承受傾斜度：errorRange。資源池更新前狀態(tài)與這兩個參數(shù)同時作用，對負載均衡時的資源池傾斜度以及資源池整體遷移代價密切相關(guān)。整個調(diào)度策略是在進行資源池負載均衡的過程中盡可能不遷移與初始化映射方案中在同一臺主機上的虛擬機來減小資源池整體遷移代價。如圖6，使用了減少遷移代價的處理方式時比沒使用的基本會少60%左右的遷移成本。

5? 結(jié)語

本文針對云計算資源池的負載均衡調(diào)度問題，提出了一種虛擬機的調(diào)度方案。首先將資源池的負載均衡分為新建與更新兩個階段，在處理新建資源池的負載均衡時使用了遺傳算法，在處理資源池狀態(tài)更新之后的負載均衡時同時考慮了相應(yīng)策略以減小資源池整體遷移代價。最后通過資源池仿真程序進行實驗，通過實驗結(jié)果表明了本文所述調(diào)度策略的有效性與可用性都較好。

參考文獻

[1] 呂燕兵，王靜宇，吳金明.云計算資源負載均衡調(diào)度優(yōu)化算法研究[J].內(nèi)蒙古科技大學(xué)學(xué)報，2017，36（2）：181-186.

[2] 欒志坤，牛超.云數(shù)據(jù)中心中負載均衡的虛擬機調(diào)度方法[J].計算機與現(xiàn)代化，2017（5）：24-36.

[3] 洪越.遺傳算法在隨機分布控制中的應(yīng)用綜述[J].現(xiàn)代工業(yè)經(jīng)濟和信息化，2018（17）：69-70.

[4] 顏恩鋒.基于遺傳算法優(yōu)化BP神經(jīng)網(wǎng)絡(luò)的基坑變形研究[J].中國水運（下半月），2019，19（4）：72-73，76.

[5] 杜吉成.云數(shù)據(jù)中心基于負載權(quán)重的負載均衡調(diào)度算法[J].研究與開發(fā)，2013（12）：7-11.

[6] 張超. 混合群智能優(yōu)化算法研究及應(yīng)用[D].北京：北京科技大學(xué)，2018.