張松霖

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

0 引言

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

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

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

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

1 相關(guān)工作

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

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

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

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

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

圖1 容器云和虛擬機(jī)云的比較

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

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

(1)

f=min(AE)

(2)

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

(3)

(4)

(5)

(6)

(7)

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

(8)

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

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

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

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

(9)

(10)

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

(11)

(12)

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

3 Double-GA算法描述

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

3.1 總體描述

3.1.1 總體描述

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

3.1.2 染色體表達(dá)

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

在染色體的虛擬機(jī)分配階段，每個(gè)輸入口表示了從所有虛擬機(jī)類型中所存在的一個(gè)虛擬機(jī)類型。虛擬機(jī)分配向量的長(zhǎng)度等于容器分配向量的長(zhǎng)度，這是因?yàn)槲覀冏疃嗫梢允褂肗個(gè)虛擬機(jī)來容納N個(gè)容器，即一對(duì)一的映射。

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

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

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

3.1.3 初始化

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

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

3.2.1 交叉操作

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

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

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

圖4 遺傳算法中交叉操作的改進(jìn)

3.2.2 變異操作

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

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

3.2.3 適應(yīng)度函數(shù)

4 Double-GA策略實(shí)驗(yàn)與性能分析

4.1 實(shí)驗(yàn)環(huán)境的設(shè)計(jì)

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

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

表1 容器云中的虛擬機(jī)分類

表2 容器云中的虛擬機(jī)分類

表3 容器云中的虛擬機(jī)分類

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

表4 虛擬機(jī)的實(shí)例設(shè)置

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

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

4.2 實(shí)驗(yàn)比較對(duì)象

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

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

4.3 實(shí)驗(yàn)結(jié)果與性能分析

4.3.1 能量消耗的比較

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

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

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

該實(shí)驗(yàn)數(shù)據(jù)還表明容器云的能量消耗因?yàn)橘Y源分配方式的不同而不同，遞減最好適用算法BFD的性能變化不受虛擬機(jī)類型個(gè)數(shù)的影響，因?yàn)樗恢痹谑褂米畲蟮奶摂M機(jī)需求。另外，最好適用算法BFD是一個(gè)不可逆轉(zhuǎn)的算法，這就意味著相同的容器輸入，那么得到的能量消耗一直是相同的。

4.3.2 擴(kuò)展性能的比較

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

4.3.3 虛擬機(jī)利用個(gè)數(shù)情況

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

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

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

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

5 結(jié)束語

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