容器云中基于改進遺傳算法的資源分配策略

張松霖

(太原理工大學 軟件學院,山西 晉中 030600)

0 引言

隨著無服務器及微服務技術等應用的發(fā)展，容器云(Container-based Cloud)已經(jīng)成了軟件領域主流平臺[1]，與早期的虛擬機比較起來，容器很容易針對Web應用程序提供包裝、遷移和配置等服務。近年來Google和Microsoft等公司都開始在大數(shù)據(jù)中心部署大量的容器為基礎的應用。雖然服務器合并技術是一個很好的節(jié)省能量消耗的辦法，但是在容器云中服務器合并是很難達到的，因為容器云中的資源分配是兩層的資源分配：容器到虛擬機的分配和虛擬機到物理主機的分配。在早期基于虛擬機的云中擴展的服務器合并技術也無法重新再使用[2]。

為了處理好容器云中的兩層資源分配問題，必須解決好2個方面的難題：1)容器分配和虛擬機分配之間的交互問題，即最好的容器分配不一定能夠獲得最好的虛擬機分配結果，所以這兩個過程必須同時進行。2)由于每一層的分配都是多維的裝箱問題，必須處理好這類多目標優(yōu)化的NP-Hard問題[3]。

本文的研究重點是設計與實現(xiàn)一個容器云中的兩層資源分配策略Double-GA，同時Double-GA必須使云數(shù)據(jù)中心的能量消耗盡量最小。為了達到這個目標，Double-GA應用了多目標優(yōu)化智能計算的遺傳算法。遺傳算法[4-5]已經(jīng)被成功應用到組合優(yōu)化領域，它可以很好地避免早熟和收斂速度慢的問題，文獻[6-8]中遺傳算法已經(jīng)成功應用到了基于虛擬機的云資源分配領域。

Double-GA中利用遺傳算法解決容器云的資源分配主要途徑是設計出染色體的表達方式，處理好遺傳算法染色體的初始化、種群進化、交叉、變異等操作，原因是遺傳算法中好的染色體表達方式可以擴展搜索空間使得資源的分配更接近最優(yōu)解。Double-GA中采用了一個新的雙染色體的方式和新的進化操作，最后的仿真實驗結果表明，Double-GA針對其他的常見啟發(fā)式智能算法具有更好的資源分配效果與更小的能量消耗[9]。

1 相關工作

本節(jié)首先描述了容器云中服務器合并技術的相關工作，接著描述了遺傳算法在云資源分配方面的相關工作。當前容器云中的服務器合并問題被認為是一個動態(tài)問題[2]，即在客戶端有請求達到的時候服務器同時分配一個容器。文獻[10]和文獻[11]采用的是云中的一組預定義的虛擬機類型，應用首次適用啟發(fā)式算法First Fit Algorithm來分配虛擬機到物理主機。在遷移階段，根據(jù)像最小全物理主機選擇Least Full Host Selection算法[10]和首次適用物理主機選擇First Fit Host Selection算法等方式來完成容器分配。

這些策略大部分都是貪心模式的，為了可以快速分配資源。上述的啟發(fā)式算法具有2個方面的不足，首先正如文獻[2]所指出的，動態(tài)的算法比靜態(tài)的算法性能還要低，因為動態(tài)算法針對容器進行頻繁的遷移會產(chǎn)生額外的通信開銷。其次，貪心模式的啟發(fā)式算法往往只能取得局部資源分配最優(yōu)，不能得到全局資源分配最優(yōu)。另外一方面，文獻[2]建議靜態(tài)的方式來完成最初的容器分配，因為初始的分配一般會有很長時間的容忍期，盡管靜態(tài)算法可能有很長的處理時間，但是它一般比貪心算法可以獲得更加好的性能。

隨著近年來容器云的出現(xiàn)，大部分容器云都不能選擇虛擬機的類型。文獻[12]認為一個虛擬機是一個類型，每個物理主機容納不超過10個虛擬機。

它提出了一個integer linear programming (ILP)整數(shù)線性編程方式來分配容器。如果只考慮一個預定的虛擬機類型，不僅不能適應不同類型的資源需求，而且會導致資源浪費。而且分配更加多的虛擬機會導致更多的額外開銷。從它們的算法的性能中，可以得知整數(shù)線性編程方式的處理時間開銷隨著問題尺寸幾乎呈指數(shù)增長。

容器云所面對的雙層資源分配如圖1顯示，圖1(a)是早期的基于虛擬機的資源分配，圖1(b)是現(xiàn)在常用的基于容器的資源分配。文獻[9]中提出了多目標優(yōu)化的遺傳算法來解決兩層容器云資源分配問題。它采用的是單染色體的表達方式，更好地完成了兩層資源分配，盡管如此，該方法的染色體的設計、遺傳算法的各類操作都比較限制，它不能采用交叉操作，完全依賴于局部搜索的交叉。遺傳算法中的交叉操作是可以很好的增強搜索能力的，基于此目的，本文設計了改進高效的遺傳算法Double-GA，它具有好的交叉能力，同時染色體表達與普通遺傳算法也不一樣。

圖1 容器云和虛擬機云的比較

2 問題定義與系統(tǒng)建模

在容器云中假設有N個容器的集合{1,....N}，在資源分配階段要分配到云數(shù)據(jù)中心的V{1,....V}個虛擬機上運行，然后把這些虛擬機分配到物理主機P{1,2,....P}上，如圖2所示，我們的目標是讓所有的物理主機的能量消耗AE最小。下面的公式分別計算了物理主機的能量消耗Ep和整個容器云的能量消耗AE。

(1)

f=min(AE)

(2)

f表示了目標函數(shù)，Ep在后面的公式中介紹，下面的約束條件式(3)～(4)保證了容器的整體資源需求不能超過它的目標虛擬機的處理能力。約束條件式(5)～(6) 保證了虛擬機的整體資源需求不能超過它的目標物理主機的處理能力。約束條件式(7)保證了每個容器只能被配置一次。

(3)

(4)

(5)

(6)

(7)

式(1)中的Ep是活動物理主機的能量消耗。|ucpu(p)|在物理主機的CPU利用率大于0的時候等于1，其他的情況等于0。

(8)

Eidle和Emax分別表示了物理主機在空閑和滿負載的時候的能量消耗。在Double-GA策略中，容器、虛擬機、物理主機都與裝箱問題中的兩個維度的物理資源所關聯(lián)，處理器和內(nèi)存。容器的處理器需求和內(nèi)存需求定義為Cn和Mn。虛擬機的處理器需求和內(nèi)存需求定義為VCv和VMv。物理主機的處理器計算能力和內(nèi)存大小分別定義為PCp和PMp。容器云中的資源的數(shù)量定義為區(qū)域范圍[1,2,…,R]。每個虛擬機因為處理器和內(nèi)存的額外開銷定義為OCv和OMv，額外開銷在容器云中心也表示為資源。

本策略中假設大量的虛擬機需求類型VCv和VMv組合成Typev。對于容器而言，我們認為客戶端的應用與容器是一對一的關系，這就意味著我們定義的容器的資源需求范圍在1到虛擬機最大類型數(shù)量Typev之間，一個虛擬機可以容納多個容器。

圖2 容器云中的兩層資源分配策略

兩層資源分配策略主要依賴于物理資源的利用效率情況來確定。在容器到虛擬機級別，主要體現(xiàn)在虛擬機的處理器和內(nèi)存的利用率情況。它們分別通過式(9)和式(10)完成計算。

(9)

(10)

變量xnv的取值范圍是0或1，它分別表示容器n是否被分配到虛擬機v之上。在虛擬機到物理主機級別，主要體現(xiàn)在物理主機的處理器和內(nèi)存的利用率情況。它們分別通過式(11)和式(12)完成計算。

(11)

(12)

物理主機的資源的利用率體現(xiàn)其上容納的虛擬機的資源運行情況，變量yvp的取值范圍是0或1，它分別表示虛擬機v是否被分配到物理主機p之上。

3 Double-GA算法描述

這部分介紹了Double-GA策略的設計，包括染色體表達的設計，進化操作的設計和適應度函數(shù)的設計等。

3.1 總體描述

3.1.1 總體描述

Double-GA策略是以遺傳算法為基礎，在算法思路、流程和算法步驟都參考了遺傳算法和基于虛擬機的物理資源分配等技術，不同的地方是它帶有針對特定的容器云的兩層資源分配及其相關的染色體設計和操作設計。

3.1.2 染色體表達

個體的表示由于2個不同的染色體組成，一個染色體是用來做容器分配，另外一個作為虛擬機分配。圖3顯示了染色體的設計，包括算法的輸入和輸出。通過解碼過程，一個完整的容器云資源分配問題可以得到很好的解決。所有的染色體都是具有整數(shù)值的向量。在染色體的容器分配階段，每個值表示了最初的輸入的容器的索引編號，染色體的長度就是整個容器的數(shù)量。

在染色體的虛擬機分配階段，每個輸入口表示了從所有虛擬機類型中所存在的一個虛擬機類型。虛擬機分配向量的長度等于容器分配向量的長度，這是因為我們最多可以使用N個虛擬機來容納N個容器，即一對一的映射。

為了把一個輸入的個體通過遺傳算法的解碼來完成最終的分配結果，Double-GA在兩個層次中都應用了啟發(fā)式的裝箱算法中的下次適用算法(Next Fit Algorithm)，在容器到虛擬機的層次，容器都是按照順序裝載到虛擬機中。例如圖3中，在容器5裝到虛擬機0后，接下來的容器1就不能繼續(xù)裝載到容器0中了。因此我們將關閉虛擬機0，打開虛擬機1來容納容器1。被關閉的虛擬機將不能再重新檢測和被裝載。當所有的容器都被分配完成，解碼過程才結束。

圖3 容器云中的雙染色體完成資源分配

類似的，在虛擬機裝載到物理主機的層次中，也采用同樣的規(guī)則，一方面，這種染色體表示方式可以保證運用到下次適用算法來完成解碼，再不必要設計另外的約束處理方法；另一方面，這種雙染色體表示方法可以覆蓋所有的解空間，也方便我們找到最優(yōu)的容器云的資源分配。

3.1.3 初始化

對每個種群的個體而言，我們可以隨機的對索引編號，同時產(chǎn)生出容器的分配染色體序列。為了初始化虛擬機分配的染色體，這里統(tǒng)一的采用虛擬機的類型來產(chǎn)生。

3.2 交叉、變異與適應度函數(shù)

3.2.1 交叉操作

遺傳算法中設計一個好的交叉操作對提高虛擬機資源的利用效率十分關鍵，這里利用了order1交叉操作來預防可能的下一代的染色體的預早熟現(xiàn)象[13]，針對在虛擬機資源分配中使用的染色體，本文采用了單點交叉操作[14]。

order1交叉操作是從父代中隨機的選擇一個連續(xù)的序列，在另外一個父代中，把剩余的值將按照相同的順序放到孩子中。

例如圖4，容器3和容器4都被選擇，并從父代中拷貝到孩子child 1中。然后相同的容器(3和4)將被交叉輸出到父代parent2中。從父代parent2中剩余的值將從第2個切入點開始，回滾到染色體的開始。例如容器1，5和2。同樣的規(guī)則被應用到第二個孩子中。單點交叉操作首先隨機的切斷一個染色體序列成2個部分，孩子將繼承其中一個部分parent1和另外一個部分parent2。

圖4 遺傳算法中交叉操作的改進

3.2.2 變異操作

在遺傳算法中，變異操作提供了一個局部最優(yōu)解的搜索機制，它用來尋找當前個體的鄰居情況。在染色體的兩個層次分配中，Double-GA設計了這個新的變異操作來完成局部最優(yōu)解搜索。包括切換變異操作和虛擬機類型改變變異操作。

切換變異是在容器分配的染色體上隨機的選擇2個入口，并改變它們的值。這種變異可以改變2個容器的分配。虛擬機類型改變變異操作通過虛擬機分配染色體上循環(huán)，并以一定的概率統(tǒng)一的改變它們的值，這個變異操作可以改變虛擬機的類型。

3.2.3 適應度函數(shù)

4 Double-GA策略實驗與性能分析

4.1 實驗環(huán)境的設計

實驗的目標是為了測試本文的雙染色體的遺傳算法中在處理兩層容器云資源分配后云數(shù)據(jù)中心的能量消耗效果情況及時間成本，本節(jié)中利用了真實的樣本數(shù)據(jù)集[15]，同時與常見的兩種算法進行比較，單染色體算法Single-GA和最好遞減裝箱(decreased best fit algorithm,BFD)算法。

真實的數(shù)據(jù)集主要來自AuverGrid項目中的資源分配數(shù)據(jù)[15]。在容器云在硬件的配置上，采用了同等配置的物理主機，CPU的主頻為3300 MHz，內(nèi)存大小為4 GB，一共400臺，組成一個基于容器的云數(shù)據(jù)中心。為了測試不同虛擬機類型個數(shù)配置情況下容器資源分配的性能高低比較，我們設置了三個虛擬機類型集。如表1～3所顯示，每個類型集中又有不同的虛擬機需求。

表1 容器云中的虛擬機分類

表2 容器云中的虛擬機分類

表3 容器云中的虛擬機分類

第一大類虛擬機包括5種虛擬機需求(編號1～5)， 第二大類虛擬機包括7種虛擬機需求(編號1～7)，第三大類虛擬機包括10種虛擬機需求(編號1～10)。同時我們設計了四個實例數(shù)據(jù)(Instance)，如表4，為了是區(qū)別不同的容器個數(shù)。通過這樣設置，對于每個虛擬機類型設置，三個大類和四個實例數(shù)據(jù)，這些實例數(shù)據(jù)上運行的Double-GA策略一共可以包括12個實驗。

表4 虛擬機的實例設置

Double-GA策略的參數(shù)設置與基本的遺傳算法一致，也有自身的改變，見表5。在精英中配置的大小為10，在競賽中設置了大小為7。因為這些參數(shù)都是標準設置和廣泛使用的。針對單染色體遺傳算法，設置了交叉率為0.8，因為Double-GA策略的性能的提高很大程度上完全依賴于搜索的交叉。算法采用Java來實現(xiàn)，實驗運行在Intel i7 3.6 GHz處理器的云客戶端上，內(nèi)存為8 GB，操作系統(tǒng)為Linux。

表5 遺傳算法的容器云資源分配參數(shù)設置

4.2 實驗比較對象

單染色體遺傳算法在文獻[9]中有描述過兩層容器云的資源分配問題，有兩個方面的原因導致本文對它進行了實際的改進：1)它是直接基于NSGA-II多目標優(yōu)化的遺傳算法。2)它們的主要假設是允許虛擬機超負載[2]，同時可以容納某些物理資源超過利用率的虛擬機。在Double-GA策略中，虛擬機超負載是不允許的，因此，為了作為性能比較，在初始化的時候，既然不允許虛擬機超負載，在虛擬機沒有足夠的容納能力下，實驗中也不允許太多的容器被分配到一個虛擬機上。因此，針對Single-GA單染色體，虛擬機類型都是隨機的產(chǎn)生并且容器都是運行首次適用算法First Fit Algorithm來分配，交叉操作中隨機的切換兩個容器。

在遞減最好適用Best Fit Descending algorithm算法也作為本文的比較對象，在實驗的時候，由于遞減最好適用算法沒有判斷和選擇虛擬機類型的功能，為了創(chuàng)建新的虛擬機，實驗中我們一直選擇的最大的虛擬機需求類型。例如表1中的類型5，虛擬機處理需求為2 310 MHz, 內(nèi)存需求大小為2 800 MB。

4.3 實驗結果與性能分析

4.3.1 能量消耗的比較

這個部分顯示了三個容器云資源分配算法在能量消耗方面的比較，圖5和圖6顯示三個算法一天24小時內(nèi)在Instance3和Instance4數(shù)據(jù)集上的平均能量消耗比較，單位為千瓦特小時。這里只顯示了2個實例因為instance1和instance2在數(shù)據(jù)上基本和instance3類似。圖中表示遞減最好適用算法BFD是容器云中整體能量消耗最大的，單染色體遺傳算法Single-GA性能比BFD算法好，所有的測試實例數(shù)據(jù)中，本文的雙染色體Double-GA遺傳算法性能最優(yōu)。

圖5 Intance3數(shù)據(jù)下的能量消耗比較

圖6 Intance4數(shù)據(jù)下的能量消耗比較

該實驗數(shù)據(jù)還表明容器云的能量消耗因為資源分配方式的不同而不同，遞減最好適用算法BFD的性能變化不受虛擬機類型個數(shù)的影響，因為它一直在使用最大的虛擬機需求。另外，最好適用算法BFD是一個不可逆轉的算法，這就意味著相同的容器輸入，那么得到的能量消耗一直是相同的。

4.3.2 擴展性能的比較

表6顯示了隨著容器個數(shù)不斷的增加，三個算法運行后的能量消耗的性能比較。雙染色體遺傳算法在各個實例數(shù)據(jù)情況下都比其他的2個算法能量消耗要節(jié)能，而且從圖中可以看出隨著容器數(shù)量增加，能量消耗都是穩(wěn)步的緩慢增加，沒有急劇的變化，這點證明Double-GA擴展性能較好。

4.3.3 虛擬機利用個數(shù)情況

表7顯示了在實例Instance3和實例Instance4條件下的平均虛擬機個數(shù)利用情況，從這里可以看出，BFD算法的虛擬機利用個數(shù)一直是最小的，因為它默認情況下選擇了能力最大虛擬機。能力最大的虛擬機在物理主機中大約占有70%的總資源。這就意味著BFD算法條件下只有70%的物理資源利用效率，因為物理主機只能容納一個需求最大的虛擬機。單染色體算法和雙染色體算法比BFD算法可以利用更加多的虛擬機個數(shù)，因為在遺傳算法檢測使用的虛擬機類型的時候，大部分情況下遺傳算法可以找到能力需求互相補充的虛擬機。我們還發(fā)現(xiàn)遺傳算法可以一直尋找到互相補充的虛擬機類型，同時能提高資源利用效率。在測試樣例中，本文的雙染色體遺傳算法可以利用好更加多的虛擬機，間接的提高了物理資源利用效率，具有更低的能量消耗。

表6 三類容器云資源分配算法的時間消耗比較

表7 容器云中平均虛擬機利用數(shù)量比較

另外一個結論是提供過多的虛擬機類型可能會產(chǎn)生副面影響，因為多余的虛擬機類型將擴展最優(yōu)解的搜索空間，形成比較壞的適應度函數(shù)，導致降低效率。表7中實例Instance3表明本文的雙染色體遺傳算法如果檢測7個虛擬機類型，它的性能差于樣例Instance4的10個虛擬機類型。例如在實例Instance4中，由于容器的數(shù)量比較大，搜索也接著變大，兩類遺傳算法的性能都有降低。

5 結束語

本文建立了容器云中的兩層物理資源分配問題的數(shù)學模型，提出了一個基于雙染色體的改進遺傳算法來解決容器云的資源分配問題，真實的實驗樣本數(shù)據(jù)結果表明雙染色體算法明顯優(yōu)于單染色體和遞減最好適用算法。本文的容器云資源分配策略可以供其他云服務提供商構造節(jié)能綠色云數(shù)據(jù)中心做為參考。