許成林 楊德勝 何亮

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

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

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

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

2? 問題的形式化描述

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

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

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

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

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

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

主機(jī)資源傾斜度：其表示了主機(jī)的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），主機(jī)總資源傾斜度hostSkew = Math.abs（hostCpuSkew）+ Math.abs（hostMemSkew） + Math.abs（hostNetSkew），這里Math.abs（x）函數(shù)將獲得數(shù)值x的絕對值。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4? 實(shí)驗(yàn)仿真與分析

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

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

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

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

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

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

5? 結(jié)語

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

參考文獻(xiàn)

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

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

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

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

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

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