云計算資源池負載均衡調度策略研究

許成林 楊德勝 何亮

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

關鍵詞：云計算? 負載均衡? 遺傳算法? 策略研究

中圖分類號：U416.214? ? ? ? ? ? ? ? ? ? ? ? 文獻標識碼：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? 相關研究

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

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

2? 問題的形式化描述

2.1 資源池負載均衡調度的數學模型

資源池中主要包含了計算、存儲與網絡資源，本文不考慮存儲，而計算資源包括主機的CPU與內存，網絡資源則表示主機的帶寬。

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

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

虛擬機：定義CPU核數為vmCpuNum，內存大小為vmMemSize，網絡帶寬使用量vmNetUseWidth，CPU使用率為vmCpuUseRatio，內存使用率為vmMemUseRatio;則CPU使用量vmCpuUseNum = vmCpuNum*vmMemUseRatio，內存使用量vmMemUseSize = vmMemSize*vmMemUseRatio。

主機：定義CPU總核數為hostCpuTotalNum，總內存大小為hostMemTotalSize，總網絡帶寬為hostNetBandTotalWidth;設空閑CPU資源為hostCpuFreeNum，空閑內存資源為hostMemFreeSize，空閑網絡帶寬為hostNetBandFreeWidth;由此可得主機CPU使用率hostCpuUseRatio = 1-hostCpuFreeNum/hostCpuTotalNum，內存使用率hostMemUseRatio = 1-hostMemFreeSize/hostMemTotalSize，網絡帶寬使用率hostNetUseRatio = 1-hostNetBandFreeWidth/hostNetBandTotalWidth。

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

2.2 應用場景和范圍

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

3? 算法的調度模型

3.1 遺傳算法的關鍵元素

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

種群：一定規模個體的集合。

種群規模：種群中個體的總數量。

基因：資源池下一個具體虛擬機的具體位置（在某臺主機上）以及其對資源池CPU、內存與網絡資源的具體使用量。

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

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

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

代數：種群迭代的次數。

3.2 新建資源池過程調度算法

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

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

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

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

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

3.3 更新資源池過程調度算法

在更新資源池狀態時，本文將以盡量少的虛擬機遷移成本來達到一個符合預期的資源池負載均衡狀態為目標進行算法設計。

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

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

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

4? 實驗仿真與分析

4.1 實驗環境及參數設置

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

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

4.2 調度策略模型仿真與分析

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

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

5? 結語

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

參考文獻

[1] 呂燕兵，王靜宇，吳金明.云計算資源負載均衡調度優化算法研究[J].內蒙古科技大學學報，2017，36（2）：181-186.

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

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

[4] 顏恩鋒.基于遺傳算法優化BP神經網絡的基坑變形研究[J].中國水運（下半月），2019，19（4）：72-73，76.

[5] 杜吉成.云數據中心基于負載權重的負載均衡調度算法[J].研究與開發，2013（12）：7-11.

[6] 張超. 混合群智能優化算法研究及應用[D].北京：北京科技大學，2018.