郭　靜

(中國(guó)電子科學(xué)研究院，北京　100041)

?

工程與應(yīng)用

面向私有云的業(yè)務(wù)遷移部署方法研究

郭靜

(中國(guó)電子科學(xué)研究院，北京100041)

業(yè)務(wù)合理遷移部署是私有云高效使用的前提與關(guān)鍵，然而，由于業(yè)務(wù)對(duì)資源需求突發(fā)增長(zhǎng)、部署時(shí)業(yè)務(wù)之間存在約束等因素的存在使得業(yè)務(wù)合理部署困難。為解決上述問(wèn)題，本文對(duì)業(yè)務(wù)遷移部署問(wèn)題進(jìn)行建模，充分考慮了業(yè)務(wù)系統(tǒng)的重要性差異和應(yīng)用組件之間的約束關(guān)系，采用資源預(yù)留機(jī)制來(lái)保證業(yè)務(wù)穩(wěn)定運(yùn)行，并在理論分析的基礎(chǔ)上設(shè)計(jì)了一種基于分組遺傳算法的業(yè)務(wù)遷移部署方法。方法采用分組方式對(duì)遷移方案進(jìn)行映射，首先，按照順序部署的方式生成滿足約束的初始方案，然后，綜合根據(jù)方案中物理服務(wù)器的資源利用情況、應(yīng)用組件的等級(jí)和其對(duì)資源的需求，交叉生成新的部署方案，其次，根據(jù)物理服務(wù)器的資源閑置情況，變異生成新的部署方案，并通過(guò)混合策略選擇方案來(lái)迭代搜索，最后，迭代完成后輸出最終結(jié)果。實(shí)驗(yàn)結(jié)果表明本方法能有效解決業(yè)務(wù)遷移部署問(wèn)題。

業(yè)務(wù)遷移部署；私有云；資源預(yù)留；分組遺傳算法；NP-Hard問(wèn)題

TP393

A

1673-5692(2016)02-191-08

0　引　言

隨著信息技術(shù)的不斷發(fā)展，云計(jì)算技術(shù)[1]已經(jīng)成為企事業(yè)單位實(shí)現(xiàn)應(yīng)用系統(tǒng)集約化發(fā)展的重要手段。為滿足自身業(yè)務(wù)發(fā)展的需要，提高基礎(chǔ)設(shè)施資源(計(jì)算、存儲(chǔ)等資源)的利用水平，降低系統(tǒng)運(yùn)維的成本，許多單位已經(jīng)開(kāi)展了私有云[2]的建設(shè)。當(dāng)私有云建成以后，業(yè)務(wù)系統(tǒng)需要遷移入云部署才能實(shí)現(xiàn)最終的預(yù)期效果。為此，業(yè)務(wù)合理的遷移部署已成為私有云高效使用的前提與關(guān)鍵。

在私有云中，業(yè)務(wù)系統(tǒng)對(duì)基礎(chǔ)設(shè)施資源的需求主要由虛擬機(jī)來(lái)提供，多個(gè)虛擬機(jī)共同部署在一臺(tái)物理服務(wù)器上。合理部署業(yè)務(wù)系統(tǒng)就是要將承載應(yīng)用組件的虛擬機(jī)合理的映射到私有云中的物理服務(wù)器上，并保證業(yè)務(wù)系統(tǒng)穩(wěn)定運(yùn)行，同時(shí)提高私有云中資源的利用水平。

然而，由于業(yè)務(wù)對(duì)資源需求突發(fā)增長(zhǎng)，遷移部署時(shí)業(yè)務(wù)之間存在約束等因素的存在，業(yè)務(wù)遷移部署常常面臨下列挑戰(zhàn)。

一方面，在私有云中，一臺(tái)物理服務(wù)器通常會(huì)部署多個(gè)承載應(yīng)用組件的虛擬機(jī)，所以當(dāng)業(yè)務(wù)系統(tǒng)對(duì)資源需求突發(fā)增長(zhǎng)時(shí)，同臺(tái)機(jī)器中的業(yè)務(wù)系統(tǒng)之間會(huì)搶占資源，導(dǎo)致業(yè)務(wù)運(yùn)行的穩(wěn)定性和可靠性降低。另一方面，各個(gè)單位會(huì)根據(jù)自身業(yè)務(wù)的特點(diǎn)設(shè)計(jì)一些部署策略來(lái)保證業(yè)務(wù)整體運(yùn)行最優(yōu)，這些策略表現(xiàn)為承載不同應(yīng)用組件的虛擬機(jī)之間的約束關(guān)系。目前，已有文獻(xiàn)[3]給出了遷移入云的步驟和通用原則，但是缺少細(xì)化部署的方法，根據(jù)本文分析業(yè)務(wù)遷移部署問(wèn)題是一個(gè)NP-Hard問(wèn)題，為此如何從大量的可行部署方案中找出優(yōu)秀的方案(即，確定承載應(yīng)用組件虛擬機(jī)的部署位置)是一個(gè)挑戰(zhàn)。雖然已有研究者針對(duì)虛擬機(jī)放置或調(diào)度問(wèn)題提出了多種映射方法[4-9]，但是與傳統(tǒng)的虛擬機(jī)放置或調(diào)度不同，業(yè)務(wù)遷移入云部署不僅需要考慮業(yè)務(wù)應(yīng)用組件對(duì)基礎(chǔ)設(shè)施資源需求可能會(huì)突發(fā)增長(zhǎng)的情況，而且在部署時(shí)，還需要考慮業(yè)務(wù)應(yīng)用組件之間的相互關(guān)系。因此，難以利用上述方法來(lái)對(duì)問(wèn)題進(jìn)行求解。

為解決上述問(wèn)題，本文對(duì)業(yè)務(wù)遷移部署問(wèn)題進(jìn)行建模，在理論分析的基礎(chǔ)上設(shè)計(jì)了一種基于分組遺傳算法的業(yè)務(wù)遷移部署方法，并通過(guò)實(shí)驗(yàn)驗(yàn)證了方法的有效性。在建模上，本文充分考慮了業(yè)務(wù)系統(tǒng)的重要性差異和應(yīng)用組件之間的約束關(guān)系，采用資源預(yù)留機(jī)制來(lái)保證業(yè)務(wù)穩(wěn)定運(yùn)行。在求解方法設(shè)計(jì)上，采用分組方式對(duì)遷移方案進(jìn)行映射，首先，按照順序部署的方式生成滿足約束的初始方案，然后，綜合根據(jù)方案中物理服務(wù)器的資源利用情況、應(yīng)用組件的等級(jí)和其對(duì)資源的需求，交叉生成新的部署方案，其次，根據(jù)物理服務(wù)器的資源閑置情況，變異生成新的部署方案，并通過(guò)混合策略選擇方案以迭代搜索，最后，迭代完成后輸出最終結(jié)果。實(shí)驗(yàn)以資源利用率為評(píng)價(jià)指標(biāo)，在多組業(yè)務(wù)系統(tǒng)上驗(yàn)證了本方法的有效性。

1　業(yè)務(wù)遷移部署建模與分析

1.1業(yè)務(wù)遷移部署的步驟

合理遷移部署系統(tǒng)是實(shí)現(xiàn)業(yè)務(wù)在私有云上穩(wěn)定、可靠運(yùn)行的前提與關(guān)鍵。為實(shí)現(xiàn)這一目標(biāo)，業(yè)務(wù)系統(tǒng)的遷移部署可采用下列步驟來(lái)實(shí)現(xiàn)。

首先，對(duì)業(yè)務(wù)系統(tǒng)開(kāi)展調(diào)研與分析。確定各個(gè)系統(tǒng)對(duì)基礎(chǔ)設(shè)施資源的需求(如：對(duì)CPU、內(nèi)存、I/O、存儲(chǔ)的基本需求)，分析業(yè)務(wù)系統(tǒng)的重要程度，根據(jù)其重要性設(shè)計(jì)資源預(yù)留的大小，分析應(yīng)用組件之間的相互關(guān)系，確定應(yīng)用組件在部署時(shí)的策略(例如：為保證重要的業(yè)務(wù)系統(tǒng)擁有較高的可靠性，需要將高等級(jí)業(yè)務(wù)系統(tǒng)的應(yīng)用組件部署在多臺(tái)物理服務(wù)器上，以減少單臺(tái)物理服務(wù)器故障對(duì)業(yè)務(wù)系統(tǒng)的影響。對(duì)于低等級(jí)業(yè)務(wù)系統(tǒng)的應(yīng)用組件應(yīng)盡量部署在同臺(tái)物理服務(wù)器上，以減少對(duì)帶寬資源的占用，保持網(wǎng)絡(luò)穩(wěn)定)。

然后，根據(jù)調(diào)研結(jié)果，設(shè)計(jì)具體部署方案。在方案設(shè)計(jì)時(shí)，需要滿足分析確定的資源預(yù)留策略，并滿足應(yīng)用組件部署的約束，并保證部署方案不大于物理服務(wù)器所提供的資源能力上限，并盡可能提供私有云中的資源利用水平。

最后，采用人工部署或工具部署的方式將應(yīng)用組件部署到私有云中，并對(duì)部署的業(yè)務(wù)應(yīng)用進(jìn)行測(cè)試優(yōu)化。

從上述步驟可以看出，設(shè)計(jì)遷移部署方案是整個(gè)過(guò)程的核心與關(guān)鍵。為此，下面將主要對(duì)設(shè)計(jì)階段的業(yè)務(wù)遷移入云部署問(wèn)題進(jìn)行建模分析。

1.2業(yè)務(wù)遷移部署問(wèn)題建模

根據(jù)上述描述可知，在設(shè)計(jì)階段業(yè)務(wù)遷移入云部署問(wèn)題就是根據(jù)云中物理服務(wù)器的能力和各個(gè)應(yīng)用組件之間的部署策略，以及資源預(yù)留方案，設(shè)計(jì)部署方案使得業(yè)務(wù)系統(tǒng)能夠穩(wěn)定運(yùn)行，并實(shí)現(xiàn)云中的資源利用水平最大化。為此，該問(wèn)題的建模描述如下。

業(yè)務(wù)遷移入云部署問(wèn)題：已知有若干個(gè)業(yè)務(wù)應(yīng)用系統(tǒng)需要遷移至私有云中，這些系統(tǒng)共需n臺(tái)虛擬機(jī)來(lái)承載其應(yīng)用組件。其中，業(yè)務(wù)系統(tǒng)對(duì)n臺(tái)虛擬機(jī)的資源需求為{R1，R2，…，Ri,…,Rn}，Ri= (ri1,ri2,…,rit)是t維向量，代表承載應(yīng)用組件的虛擬機(jī)i對(duì)t種資源的需求。假設(shè)云中共有M臺(tái)同構(gòu)的物理服務(wù)器用于虛擬機(jī)部署，每臺(tái)物理服務(wù)器提供的資源能力為P=(p1，p2，…，pt)，則業(yè)務(wù)遷移入云部署問(wèn)題就是計(jì)算一種合理的遷移部署方法，使得業(yè)務(wù)系統(tǒng)的應(yīng)用組件在遷移入云后能夠在虛擬機(jī)中穩(wěn)定運(yùn)行，且使得私有云中的資源利用具有較高水平，并滿足下列約束條件。

約束條件1：資源預(yù)留約束

為防止應(yīng)用組件對(duì)基礎(chǔ)設(shè)施資源需求突發(fā)增長(zhǎng)，物理服務(wù)器資源利用率過(guò)高影響業(yè)務(wù)運(yùn)行的問(wèn)題，物理服務(wù)器在部署承載應(yīng)用組件的虛擬機(jī)時(shí)需要預(yù)留一定資源。根據(jù)業(yè)務(wù)系統(tǒng)的重要程度和其對(duì)運(yùn)行穩(wěn)定性要求的差異，業(yè)務(wù)系統(tǒng)可被劃分成若干個(gè)等級(jí)，每個(gè)虛擬機(jī)的等級(jí)與其承載業(yè)務(wù)系統(tǒng)的應(yīng)用組件等級(jí)相同。假設(shè)業(yè)務(wù)系統(tǒng)分為k個(gè)等級(jí)，則物理服務(wù)器需要預(yù)留資源分別為{L1,L2,…,Lk}。其中，Lk=(lk1,lk2,…,lkt)是t維向量，代表第k級(jí)應(yīng)用組件對(duì)物理服務(wù)器t類資源的預(yù)留要求。當(dāng)物理服務(wù)器同時(shí)部署了多個(gè)等級(jí)的虛擬機(jī)時(shí)，則其資源預(yù)留情況需按照這些虛擬機(jī)的最高等級(jí)進(jìn)行預(yù)留。

約束條件2:容斥約束

根據(jù)業(yè)務(wù)系統(tǒng)入云部署的一些特殊要求，遷移部署通常會(huì)設(shè)計(jì)相應(yīng)策略，它們表現(xiàn)為承載不同應(yīng)用組件的虛擬機(jī)之間的容斥關(guān)系(即，虛擬機(jī)必須(或不能)部署在同一臺(tái)物理服務(wù)器中)。例如：對(duì)某類資源需求較高的業(yè)務(wù)組件不能部署在同一物理服務(wù)器中，某些低等級(jí)業(yè)務(wù)系統(tǒng)的應(yīng)用組件應(yīng)盡量部署在同臺(tái)物理服務(wù)器上。假設(shè)虛擬機(jī)之間的容斥關(guān)系由z條依賴約束D={d1,d2,…,dz}和v條沖突約束C={c1,c2,…,cv}組成，則可行的部署方案都要滿足這些約束條件。其中，任意依賴約束關(guān)系dz由3維向量表示，反映了虛擬機(jī)a與虛擬機(jī)b需要部署在同一臺(tái)物理機(jī)上。任意沖突約束關(guān)系cv由3維向量表示，反映了虛擬機(jī)q與虛擬機(jī)w不能部署在同一臺(tái)物理服務(wù)器上。

根據(jù)上述描述，業(yè)務(wù)遷移部署問(wèn)題的數(shù)學(xué)符號(hào)及物理意義的對(duì)應(yīng)關(guān)系如表1所示。

表1　數(shù)學(xué)符號(hào)及物理意義

根據(jù)上述描述，求解業(yè)務(wù)遷移入云部署問(wèn)題就是對(duì)下列數(shù)學(xué)模型進(jìn)行求解。

問(wèn)題的目標(biāo)：業(yè)務(wù)遷移部署后，私有云中的資源利用水平最大化。

(1)

資源預(yù)留約束：

(2)

容斥約束：

(3)

(4)

1.3模型分析

根據(jù)業(yè)務(wù)遷移入云部署的數(shù)學(xué)建?？梢钥闯?，本問(wèn)題是一個(gè)典型的組合優(yōu)化問(wèn)題。為更好的對(duì)模型進(jìn)行求解，本文對(duì)問(wèn)題的求解難度進(jìn)行分析，發(fā)現(xiàn)業(yè)務(wù)遷移部署問(wèn)題屬于NP-Hard問(wèn)題，模型的目標(biāo)只與業(yè)務(wù)使用私有云中物理服務(wù)器數(shù)量相關(guān)，詳細(xì)描述見(jiàn)定理1與定理2。

定理1 ：業(yè)務(wù)遷移入云部署問(wèn)題是一個(gè)NP-Hard問(wèn)題。

證明：已知虛擬機(jī)放置問(wèn)題通常被建模成裝箱問(wèn)題，該問(wèn)題無(wú)法在多項(xiàng)式時(shí)間內(nèi)精確求解[10](即，該問(wèn)題是NP-Hard問(wèn)題)。該問(wèn)題就是在物理服務(wù)器的能力約束下，尋找一種虛擬機(jī)放置方案使得資源利用最高。

與業(yè)務(wù)遷移入云問(wèn)題相比，當(dāng)本問(wèn)題的資源預(yù)留策略為空，且承載應(yīng)用組件的虛擬機(jī)不存在容斥約束關(guān)系時(shí)。虛擬機(jī)放置問(wèn)題可以看作是本問(wèn)題的一個(gè)特例。

假設(shè)業(yè)務(wù)遷移入云部署問(wèn)題可以在多項(xiàng)式時(shí)間內(nèi)精確求解，則虛擬機(jī)放置問(wèn)題也可以在多項(xiàng)式時(shí)間內(nèi)精確求解，所以假設(shè)條件不成立。為此，業(yè)務(wù)遷移入云部署問(wèn)題無(wú)法在多項(xiàng)式時(shí)間內(nèi)精確求解。即：業(yè)務(wù)遷移入云部署問(wèn)題是NP-Hard問(wèn)題，證明完畢。

定理2 ：業(yè)務(wù)入云部署后的資源利用率最高與云中使用的物理服務(wù)器數(shù)量最少等價(jià)。

證明：根據(jù)上述建?？芍?，當(dāng)業(yè)務(wù)完成遷移部署后，云中資源利用率最高就是要最大化公式(1)的取值。

由于業(yè)務(wù)應(yīng)用只能部署一次，所以等式(5)成立。即：

(5)

(6)

2　基于分組遺傳算法的業(yè)務(wù)遷移部署方法

由于業(yè)務(wù)遷移入云部署問(wèn)題是NP-Hard問(wèn)題，所以難以給出精確的方法來(lái)對(duì)問(wèn)題進(jìn)行求解。為此，本文借鑒虛擬機(jī)調(diào)度的相關(guān)方法，結(jié)合本問(wèn)題的特點(diǎn)設(shè)計(jì)一種基于分組遺傳算法的業(yè)務(wù)遷移部署方法(AGroupingGeneticAlgorithmforSystemMigrationandDeployment，簡(jiǎn)稱GGASMD)。

該方法的基本思想就是首先隨機(jī)產(chǎn)生若干組遷移部署方案，然后，通過(guò)模擬自然進(jìn)化的過(guò)程，利用選擇、交叉、變異等操作迭代生成最終方案?？紤]到承載虛擬機(jī)的數(shù)量多于物理服務(wù)器的數(shù)量，本算法采用分組方式對(duì)遷移方案進(jìn)行映射，在算法設(shè)計(jì)上，本文不僅考慮了業(yè)務(wù)系統(tǒng)的等級(jí)和組件之間的容斥約束關(guān)系，還根據(jù)問(wèn)題特點(diǎn)設(shè)計(jì)了交叉、選擇等搜索操作，具體如下章節(jié)所述。

2.1虛擬機(jī)集合生成

由于部分承載應(yīng)用組件的虛擬機(jī)需要放置在一臺(tái)物理服務(wù)器中，所以為保證所有搜索方案滿足依賴約束。算法根據(jù)依賴約束將必須部署在同一物理服務(wù)器的多個(gè)虛擬機(jī)看作一個(gè)超級(jí)虛擬機(jī)來(lái)進(jìn)行部署。其中，超級(jí)虛擬機(jī)svo的組成可根據(jù)規(guī)則1來(lái)確定。超級(jí)虛擬機(jī)遵守其包含虛擬機(jī)的所有排斥約束，超級(jí)虛擬機(jī)的資源需求是其包含虛擬機(jī)需求的總和，超級(jí)虛擬機(jī)的等級(jí)為其包含虛擬機(jī)的最高等級(jí)。

規(guī)則1 ：?a∈svo∧?b∈svo

其中，與等價(jià)。

于是按照規(guī)則1將滿足依賴約束的虛擬機(jī)形成超級(jí)虛擬機(jī)，并構(gòu)成新的虛擬機(jī)集合。這樣業(yè)務(wù)遷移入云部署的方案將根據(jù)虛擬機(jī)集合搜索獲得。

2.2方案編碼映射

方案編碼映射是算法搜索求解問(wèn)題的前提，為更好的對(duì)業(yè)務(wù)遷移入云部署問(wèn)題進(jìn)行求解，本文采用分組方式[11]來(lái)對(duì)部署方案進(jìn)行映射，以克服編碼過(guò)長(zhǎng)對(duì)問(wèn)題求解的影響。本文將每個(gè)物理服務(wù)器映射為遺傳算法的一個(gè)基因位，虛擬機(jī)(或超級(jí)虛擬機(jī))在物理服務(wù)器上的部署方式構(gòu)成了基因的信息(即，基因值)。具體如圖1所示。

圖1　方案編碼映射

在上圖中，物理服務(wù)器和虛擬機(jī)共同構(gòu)成了分組遺傳算法中個(gè)體的一個(gè)基因。

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

適應(yīng)度函數(shù)是評(píng)價(jià)部署方案優(yōu)劣指標(biāo)，為指導(dǎo)算法向最優(yōu)的方案進(jìn)行搜索，本文根據(jù)定理2采用公式(7)來(lái)評(píng)價(jià)方案的優(yōu)劣。即：

(7)

在等式(7)中，X是業(yè)務(wù)遷移入云部署的方案，F(xiàn)(X)代表方案所用物理服務(wù)器的數(shù)量。

2.4初始部署方案生成

為有效求解業(yè)務(wù)遷移入云的部署方案，本文采用順序部署的策略來(lái)生成初始方案。首先在虛擬機(jī)集合中隨機(jī)生成虛擬機(jī)的部署順序，然后，根據(jù)虛擬機(jī)的部署順序，利用下列步驟對(duì)當(dāng)前待部署的虛擬機(jī)或超級(jí)虛擬機(jī)進(jìn)行部署，生成初始方案。

步驟1：對(duì)于當(dāng)前待部署虛擬機(jī)i(或超級(jí)虛擬機(jī)svi)，判斷當(dāng)前物理服務(wù)器是否能夠滿足虛擬機(jī)(或超級(jí)虛擬機(jī))對(duì)資源的需求，并滿足資源預(yù)留約束和沖突約束。若滿足則執(zhí)行步驟2，否則執(zhí)行步驟3。

步驟2：從滿足約束的候選物理服務(wù)器中選擇資源利用率最高的設(shè)備進(jìn)行部署。其中，物理服務(wù)器j在部署虛擬機(jī)i(或超級(jí)虛擬機(jī)svi)后的綜合利用率，可由公式(8)計(jì)算。

(8)

步驟3：選擇一個(gè)新物理服務(wù)器來(lái)部署虛擬機(jī)或超級(jí)虛擬機(jī)。

2.5交叉操作

交叉操作是遺傳算法進(jìn)行全局搜索的重要步驟，本文利用交叉操作產(chǎn)生新的部署方案。為產(chǎn)生良好的部署方案，本文采用文獻(xiàn)[12]的交叉框架，首先確定交叉點(diǎn)位置，然后對(duì)部分基因進(jìn)行交換。為避免算法快速陷入局部最優(yōu)解，根據(jù)問(wèn)題的特點(diǎn)，本文根據(jù)物理服務(wù)器的資源利用水平來(lái)選擇交叉的位置，并設(shè)計(jì)回填策略來(lái)產(chǎn)生新的部署方案。對(duì)于待交叉操作的部署方案，具體處理可由下列步驟完成。

步驟1：從部署方案中選擇交叉操作的基因位。綜合計(jì)算方案中物理服務(wù)器的資源利用率，并按概率方式選擇部署片段(即，基因位)進(jìn)行交叉操作。其中，部署方案中物理服務(wù)器j的資源綜合利用率URj可利用公式(9)計(jì)算獲得，每個(gè)物理服務(wù)器被選擇的概率P(URj)由公式(10)計(jì)算獲得。

(9)

(10)

步驟2：將基因位插入到另一部署方案中。首先，消除與交叉基因位相重復(fù)的虛擬機(jī)以及相應(yīng)物理服務(wù)器，然后，對(duì)由刪除而造成孤立的虛擬機(jī)進(jìn)行重新部署。本文采用下列回填策略重新部署。先按照虛擬機(jī)承載應(yīng)用的等級(jí)和資源需求情況進(jìn)行排序，再按照2.3節(jié)的步驟對(duì)其進(jìn)行部署。優(yōu)先部署承載高等級(jí)應(yīng)用組件的虛擬機(jī)，對(duì)于相同等級(jí)的虛擬機(jī)，則優(yōu)先部署資源需求量高的虛擬機(jī)，其中，資源需求高低T(Ri)可利用公式(11)來(lái)衡量，取值越高則資源需求越高。

(11)

2.6變異操作

變異操作是遺傳算法局部搜索的有效步驟。為更好的求解問(wèn)題，該操作將對(duì)方案中某臺(tái)物理服務(wù)器放置的虛擬機(jī)(或超級(jí)虛擬機(jī))進(jìn)行重新部署，部署方式與2.5節(jié)的回填方式相同。其中，被選擇的物理服務(wù)器將由概率方式產(chǎn)生，方案中每臺(tái)物理服務(wù)器被選擇的概率將由其剩余的資源情況決定，具體如公式(13)所示。

(12)

(13)

其中，UUj表示物理服務(wù)器j的t類剩余資源的綜合情況，P(UUj)代表物理服務(wù)器在變異操作中被選擇的概率，其剩余資源越多，被選擇的概率就越高。

2.7選擇操作

為實(shí)現(xiàn)算法對(duì)問(wèn)題方案的迭代搜索，選擇操作將從上代種群中選擇若干方案用于產(chǎn)生新部署方案。為了產(chǎn)生較好的新部署方案，本文采用混合策略來(lái)對(duì)部署方案進(jìn)行選擇。具體步驟如下：

首先，使用精英策略，按比例π來(lái)保留適應(yīng)度值高的方案。假設(shè)算法的種群規(guī)模為N，則保留π×N個(gè)適應(yīng)度最高的方案。

然后，在剩余的方案中，根據(jù)方案的適應(yīng)度值計(jì)算其被選擇的概率，并使用賭輪盤法進(jìn)行選擇。剩余方案Xo被選擇的概率為P(Xo)，其計(jì)算方法如公式(14)所示。

(14)

其中，Rest代表剩余方案，Xg是剩余方案中的成員，F(xiàn)(Xg)是其適應(yīng)度。

2.8算法的執(zhí)行步驟

根據(jù)上述描述，本文算法采用下列步驟來(lái)對(duì)業(yè)務(wù)遷移部署問(wèn)題進(jìn)行求解。

步驟1：虛擬機(jī)集合生成。根據(jù)應(yīng)用組件之間的依賴部署關(guān)系，按照依賴約束生成超級(jí)虛擬機(jī)，并與剩余虛擬機(jī)構(gòu)成虛擬機(jī)集合。

步驟2：初始化設(shè)置。設(shè)置種群規(guī)模、最大迭代次數(shù)、變異概率、精英選擇比例，輸入物理服務(wù)器的能力、不同等級(jí)應(yīng)用的資源預(yù)留要求、承載應(yīng)用組件的虛擬機(jī)(或超級(jí)虛擬機(jī))對(duì)資源的需求、虛擬機(jī)之間的沖突約束，并按照2.4節(jié)的方法生成初始部署方案，計(jì)算方案的適應(yīng)度。

步驟3：交叉操作產(chǎn)生新的部署方案。根據(jù)方案中物理服務(wù)器的資源利用率，使用概率方式選擇交叉基因，并按照2.5節(jié)的步驟生成新的部署方案，并計(jì)算方案的適應(yīng)度。

步驟4：按照變異概率，利用變異操作產(chǎn)生新的部署方案。根據(jù)方案中每個(gè)物理服務(wù)器的剩余資源情況，按概率方式選擇，并對(duì)其承載的虛擬機(jī)或(超級(jí)虛擬機(jī))進(jìn)行重新部署。

步驟5：采用混合策略從種群中選擇方案進(jìn)行下一次迭代搜索。首先根據(jù)精英選擇比例選擇適應(yīng)度最高的方案，然后，利用賭輪盤法選擇剩余的方案。

步驟6：判斷算法是否滿足停止條件，若滿足則輸出遷移部署方案，否則執(zhí)行步驟3。

3　實(shí)驗(yàn)仿真

為驗(yàn)證本文所提方法的有效性，實(shí)驗(yàn)在多次仿真的基礎(chǔ)上，以算法生成部署方案的資源利用率為評(píng)價(jià)指標(biāo)綜合分析算法的有效性。其中，業(yè)務(wù)系統(tǒng)的等級(jí)、數(shù)量、應(yīng)用組件規(guī)模和對(duì)資源的需求情況將采用隨機(jī)方式生成，資源利用率包括CPU、內(nèi)存、I/O、存儲(chǔ)以及綜合利用率，綜合利用率可由公式(1)計(jì)算獲得，對(duì)比分析算法為貪婪業(yè)務(wù)遷移部署方法(GreedyAlgorithmforSystemMigrationandDeployment，簡(jiǎn)稱GASMD)。該方法直接利用2.1.5節(jié)的回填策略進(jìn)行部署，具體步驟是首先對(duì)虛擬機(jī)集合中的虛擬機(jī)或超級(jí)虛擬機(jī)進(jìn)行排序，然后，采用2.1.4節(jié)的部署方法進(jìn)行部署。

為驗(yàn)證本方法的有效性，本文隨機(jī)生成四組數(shù)據(jù)來(lái)對(duì)比分析算法部署的效果。其中，每組數(shù)據(jù)中的業(yè)務(wù)等級(jí)都分為核心、重要、一般，業(yè)務(wù)系統(tǒng)對(duì)資源的需求包括CPU、內(nèi)存、I/O和存儲(chǔ)，數(shù)據(jù)規(guī)模情況及所需虛擬機(jī)的數(shù)量如表2所示。

表2　業(yè)務(wù)系統(tǒng)的規(guī)模及所需虛擬機(jī)的數(shù)量

為保證實(shí)驗(yàn)結(jié)果的可靠性，實(shí)驗(yàn)將分析算法執(zhí)行多次的平均值，GGASMD和GASMD針對(duì)不同組業(yè)務(wù)系統(tǒng)生成的部署方案效果如圖2-圖6所示。其中，圖2-圖6分別是GGASMD和GASMD生成業(yè)務(wù)部署方案的CPU利用率、內(nèi)存利用率、I/O使用率、存儲(chǔ)利用率和對(duì)資源的綜合利用率。

圖2　算法生成部署方案的CPU利用率

從圖2可以看出與GASMD相比，GGASMD生成的方案擁有較高的CPU利用率。

圖3　算法生成部署方案的內(nèi)存利用率

從圖3可以看出與GASMD相比，GGASMD生成的方案擁有較高的內(nèi)存利用率。

圖4　算法生成部署方案的I/O使用率

從圖4可以看出與GASMD相比，GGASMD生成的方案擁有較高的I/O使用率。

圖5　算法生成部署方案的存儲(chǔ)利用率

從圖5可以看出與GASMD相比，GGASMD生成的方案擁有較高的存儲(chǔ)利用率。

圖6　算法生成部署方案對(duì)資源的綜合利用率

從圖6可以看出與GASMD相比，GGASMD生成的方案擁有較高的綜合利用率。

綜上所述GGASMD算法能更好的對(duì)業(yè)務(wù)系統(tǒng)進(jìn)行部署，以滿足業(yè)務(wù)遷移入云的要求。

4　結(jié)　語(yǔ)

針對(duì)私有云中的業(yè)務(wù)遷移部署問(wèn)題，本文在考慮了業(yè)務(wù)對(duì)資源需求突發(fā)增長(zhǎng)、業(yè)務(wù)系統(tǒng)的重要性和應(yīng)用組件之間的約束關(guān)系的基礎(chǔ)上，對(duì)該問(wèn)題進(jìn)行建模并進(jìn)行理論分析，根據(jù)問(wèn)題特點(diǎn)設(shè)計(jì)了一種基于分組遺傳算法的業(yè)務(wù)遷移部署方法，并通過(guò)實(shí)驗(yàn)驗(yàn)證了本方法的有效性。

[1]王棟, 芮平亮. 云霧環(huán)繞的數(shù)據(jù)中心全景剖析[J]. 中國(guó)電子科學(xué)研究院學(xué)報(bào), 2011, 06(3):324-327.

[2]李小寧,李磊,金連文,等.基于OpenStack構(gòu)建私有云計(jì)算平臺(tái)[J].電信科學(xué),2012,28(9):1-8.

[3]尹樂(lè)杰. 基于云計(jì)算平臺(tái)的應(yīng)用系統(tǒng)遷移的研究與應(yīng)用[D]. 廈門大學(xué), 2012.

[4]Li,Bo,etal.EnaCloud:AnEnergy-SavingApplicationLivePlacementApproachforCloudComputingEnvironments[C].Proceedingsofthe2009IEEEInternationalConferenceonCloudComputingIEEEComputerSociety, 2009:17-24.

[5]Sun,Xin,etal.Multi-dimensionalResourceIntegratedSchedulinginaSharedDataCenter[C].DistributedComputingSystemsWorkshops(ICDCSW), 2011 31stInternationalConferenceonIEEE, 2011:7-13.

[6]Meng,Xiaoqiao,etal.EfficientresourceprovisioningincomputecloudsviaVMmultiplexing[C].Proceedingsofthe7thInternationalConferenceonAutonomicComputing, 2010:11-20.

[7]李強(qiáng), 郝沁汾, 肖利民,等. 云計(jì)算中虛擬機(jī)放置的自適應(yīng)管理與多目標(biāo)優(yōu)化[J]. 計(jì)算機(jī)學(xué)報(bào), 2011,34(12):2253-2264.

[8]劉志飄, 王尚廣, 孫其博,等. 一種能量感知的虛擬機(jī)放置智能優(yōu)化算法[J]. 華中科技大學(xué)學(xué)報(bào):自然科學(xué)版, 2012(S1):398-402.

[9]肖鵬, 劉洞波, 屈喜龍. 云計(jì)算中基于能耗比例模型的虛擬機(jī)調(diào)度算法[J]. 電子學(xué)報(bào), 2015(2):305-311.

[10]AjiroY,TanakaA.ImprovingPackingAlgorithmsforServerConsolidation[C].InternationalComputerMeasurementGroupConference. 2007:399-406.

[11]FalkenauerE.Ahybridgroupinggeneticalgorithmforbinpacking[J].JournalofHeuristics, 2010, 2(1):5-30.

[12]FalkenauerE.TappingtheFullPowerofGeneticAlgorithmthroughSuitableRepresentationandLocalOptimization:ApplicationtoBinPacking.SpringerBerlinHeidelberg, 1995.P167-182.

郭靜(1982—)，女，安徽省全椒人，博士，工程師，主要研究方向?yàn)樵朴?jì)算與大數(shù)據(jù)。

E-mail：itianmei@qq.com

Research on System Migration and Deployment Method for Private Cloud

GUOJing

(ChinaAcademyofElectronicsandInformationTechnology，Beijing，100041)

Migratinganddeployingthesystemsreasonableiscrucialforemployingprivatecloudefficiently.However，itisdifficulttodeploythesesystems,becausethefactorssuchasgrowthofemergencyresourcedemandandconstraintbetweenthedeployingsystems.Inthispaper，amodelwasbuiltbytakingaccountoftheimportanceofdifferentsystemsandtheconstraintbetweentheapplicationcomponents,andguaranteesbusinessstabilitybyreservingresource.Thenagroupinggeneticalgorithmforsystemmigrationanddeploymentisproposedbasedonproblemanalysis.First,itencodesthemigrationschemebygroup,andgenerateinitialsolutionbydeploytheapplicationonebyone.Then,itgeneratesthenewschemebycrossoveroperationaccordingtotheresourceutilization,levelofapplicationandresourcedemand.Next,itgeneratesthenewschemebymutationoperationaccordingtotheidleresourcesofphysicalserver,andchosenschemeforiterativesearchwithahybridselectoperation.Atlast，itoutputthefinialmigrationschemeafteriterativesearch.Theexperimentresultsshowtheeffectofthismethod.

systemmigrationanddeployment;privatecloud;resourcereservation;groupinggeneticalgorithm;NP-Hardproblem

10.3969/j.issn.1673-5692.2016.02.014

2016-02-21

2016-03-26