祝衍軍
(東莞職業(yè)技術(shù)學(xué)院計(jì)算機(jī)工程系,廣東 東莞 523808)
基于動(dòng)態(tài)規(guī)劃的云計(jì)算虛擬機(jī)簇聚類(lèi)方法
祝衍軍
(東莞職業(yè)技術(shù)學(xué)院計(jì)算機(jī)工程系,廣東 東莞 523808)
多虛擬機(jī)聚簇的快速高效實(shí)現(xiàn),對(duì)于云數(shù)據(jù)處理能力的提升具有重要意義。基于虛擬機(jī)聚簇的一般原理,引入動(dòng)態(tài)規(guī)劃全局優(yōu)化策略,構(gòu)建一種新的虛擬機(jī)聚簇方法。首先根據(jù)預(yù)設(shè)的虛擬機(jī)屬性判別函數(shù),對(duì)虛擬機(jī)資源執(zhí)行升序排列;進(jìn)而選取升序集合中心位置的虛擬機(jī)作為聚簇起點(diǎn),根據(jù)動(dòng)態(tài)規(guī)劃策略從兩個(gè)方向開(kāi)始進(jìn)行聚簇;聚簇的原則本著全局聚簇最優(yōu)的動(dòng)態(tài)規(guī)劃準(zhǔn)則。實(shí)驗(yàn)結(jié)果表明,基于動(dòng)態(tài)規(guī)劃的虛擬機(jī)聚簇方法,聚簇速度快,聚簇效果穩(wěn)定。
虛擬機(jī);聚簇;云計(jì)算;動(dòng)態(tài)規(guī)劃
隨著信息技術(shù)和大數(shù)據(jù)處理技術(shù)的飛速發(fā)展,人們對(duì)于信息處理和數(shù)據(jù)處理的要求越來(lái)越高,這也直接導(dǎo)致了計(jì)算任務(wù)的復(fù)雜度和難度不斷攀升[1]。在這種情況下,個(gè)人終端的計(jì)算資源很難獨(dú)立解決計(jì)算任務(wù),抑或需要花費(fèi)更大的成本來(lái)完成計(jì)算任務(wù)。為了解決上述問(wèn)題,科學(xué)家們提出了云計(jì)算模型和云服務(wù)技術(shù)。云計(jì)算模式,是在分布模式、并行模式、網(wǎng)格模式之后的又一種新型計(jì)算模式,其信息處理能力相比于以往獲得了空前提高。云端服務(wù)器不僅硬件配置好,軟件功能強(qiáng)大,而且整合了網(wǎng)絡(luò)間各種可以利用的計(jì)算資源,可以解決個(gè)人終端無(wú)法解決的復(fù)雜計(jì)算任務(wù)[2]。
為了提高云計(jì)算的效率和云服務(wù)的質(zhì)量,研究者構(gòu)建了虛擬化技術(shù)。通過(guò)虛擬化處理,一臺(tái)真實(shí)的服務(wù)器被動(dòng)態(tài)分割成多個(gè)虛擬服務(wù)器[3]。虛擬機(jī)模式的構(gòu)建,不僅大大降低了云端計(jì)算資源的管理難度,也大大提升了云端計(jì)算資源的利用效率,這對(duì)于快速高效地解決用戶(hù)的計(jì)算任務(wù)具有重要意義[4]。也正因?yàn)槿绱?,云?jì)算領(lǐng)域近年來(lái)出現(xiàn)了大量有關(guān)虛擬機(jī)部署的研究成果。李強(qiáng)等[5]指出,啟發(fā)式的搜索方法對(duì)于虛擬機(jī)部署是比較合適的,因?yàn)槠溆欣谠贫巳謨?yōu)化的實(shí)現(xiàn)。何東曉等[6]認(rèn)為,虛擬機(jī)的調(diào)度應(yīng)該綜合考慮多方面的原因,尤其是用戶(hù)的需求和云內(nèi)計(jì)算資源的利用情況,并為此構(gòu)建了一種基于多要素聚類(lèi)的虛擬機(jī)調(diào)度方案。劉進(jìn)軍和趙生慧[7]的研究結(jié)論顯示,物理服務(wù)器上的負(fù)載狀況對(duì)于虛擬機(jī)資源的分配有著重要影響,基于服務(wù)器負(fù)載去構(gòu)建虛擬機(jī)調(diào)度策略才能真正提高云端的計(jì)算效率。王光波等[8]針對(duì)云計(jì)算中虛擬機(jī)部署問(wèn)題,提出了一種基于架構(gòu)負(fù)載感知的虛擬機(jī)聚簇部署算法。
大量的虛擬機(jī)調(diào)度和部署方面的研究成果,極大地推動(dòng)了云計(jì)算技術(shù)走向成熟。當(dāng)前,一個(gè)新的熱點(diǎn)研究就是從單個(gè)虛擬機(jī)資源的部署轉(zhuǎn)變到包含多個(gè)虛擬機(jī)資源的虛擬機(jī)簇的部署[9-10]。本文將在過(guò)程研究成果的基礎(chǔ)上,借助全局優(yōu)化算法中的動(dòng)態(tài)規(guī)劃方法,對(duì)虛擬機(jī)簇的部署問(wèn)題展開(kāi)研究。
為了便于明確本文研究在云計(jì)算領(lǐng)域中的位置,以及明確本文的核心研究?jī)?nèi)容,先對(duì)虛擬機(jī)簇的概念以及云計(jì)算任務(wù)配置的整體架構(gòu)進(jìn)行闡述[11-12]。
簇,本身就帶有集合的含義[13]。所以,虛擬機(jī)簇實(shí)際上就是多個(gè)虛擬機(jī)構(gòu)成的集合。當(dāng)然,能夠進(jìn)入一個(gè)虛擬機(jī)簇的虛擬機(jī),彼此之間應(yīng)該有著某種聯(lián)系,或者同時(shí)符合了進(jìn)入該虛擬機(jī)簇的條件。虛擬機(jī)簇的聚集和部署,必然要依賴(lài)構(gòu)成云的硬件架構(gòu)。在一個(gè)云端的數(shù)據(jù)處理過(guò)程中,參與進(jìn)來(lái)的硬件資源包括:服務(wù)器主機(jī)、刀片中心、機(jī)架,數(shù)據(jù)中心等,這些硬件資源按照處理能力和在云端所處位置的差異,一般分屬于不同的層次,其結(jié)構(gòu)如圖1所示。
圖1 云數(shù)據(jù)處理的硬件架構(gòu)
在圖 1中,云數(shù)據(jù)處理的硬件架構(gòu)被分為 4個(gè)層次,每個(gè)層次中硬件設(shè)備的數(shù)量是不固定的。虛擬機(jī)的聚簇和部署要根據(jù)任務(wù)的實(shí)際需要,分別部署在服務(wù)器主機(jī)上、刀片中心上、機(jī)架上、及數(shù)據(jù)中心上,無(wú)論在哪個(gè)層次上部署,虛擬機(jī)必須達(dá)成和硬件資源的匹配。
實(shí)際上,為了提高云數(shù)據(jù)處理的效率和提高云端的服務(wù)質(zhì)量,如何將性能近似的虛擬機(jī)資源聚集在一起并和硬件資源實(shí)現(xiàn)協(xié)調(diào)的配置是關(guān)鍵,這本身是一個(gè)云端計(jì)算資源的全局優(yōu)化問(wèn)題。為此,本文將一種全局優(yōu)化理論應(yīng)用于云端的虛擬機(jī)聚簇之中,提出了基于動(dòng)態(tài)規(guī)劃的虛擬機(jī)聚簇方法。
2.1動(dòng)態(tài)規(guī)劃理論
動(dòng)態(tài)規(guī)劃全局優(yōu)化理論,是典型的將復(fù)雜問(wèn)題拆解并通過(guò)多個(gè)階段決策來(lái)實(shí)現(xiàn)的方法。對(duì)于拆解的各個(gè)階段,用變量k表示,對(duì)應(yīng)于第k個(gè)階段的狀態(tài)可用變量 xk表示。每執(zhí)行一個(gè)階段的優(yōu)化,整個(gè)系統(tǒng)的狀態(tài)就會(huì)發(fā)生一次改變,決定系統(tǒng)狀態(tài)如何向下一階段改變的策略稱(chēng)之為決策,用變量 uk表示。這樣,一個(gè)系統(tǒng)實(shí)現(xiàn)全局優(yōu)化的問(wèn)題就變成了一個(gè)系統(tǒng)全部階段狀態(tài)轉(zhuǎn)換的判斷準(zhǔn)則設(shè)計(jì)問(wèn)題,對(duì)應(yīng)會(huì)形成一個(gè)全局優(yōu)化函數(shù),即:
其中,n代表系統(tǒng)執(zhí)行全部過(guò)程可以拆分的階段總數(shù); vj表示每一個(gè)階段的判斷準(zhǔn)則函數(shù);Vk,n表示全局判斷準(zhǔn)則函數(shù)。
動(dòng)態(tài)規(guī)劃全局優(yōu)化理論,具有一個(gè)重要特點(diǎn),就是根據(jù)全局優(yōu)化策略判斷當(dāng)前狀態(tài)的決策以后,后續(xù)狀態(tài)不再受當(dāng)前狀態(tài)的影響,這也是動(dòng)態(tài)規(guī)劃理論中典型的無(wú)后效性。動(dòng)態(tài)規(guī)劃的準(zhǔn)則函數(shù)具有可分性,即:
2.2虛擬機(jī)聚簇
要解決云數(shù)據(jù)處理中的虛擬機(jī)聚簇問(wèn)題,就需要依托虛擬機(jī)的各種屬性和狀態(tài),構(gòu)建有針對(duì)性地動(dòng)態(tài)規(guī)劃全局優(yōu)化函數(shù)。因?yàn)榫鄞貑?wèn)題,就是要尋找各方面屬性接近的虛擬機(jī)構(gòu)成一個(gè)集合,以便為同類(lèi)問(wèn)題服務(wù)。所以,先對(duì)云處理系統(tǒng)中可用的虛擬機(jī)進(jìn)行排序,其排序是根據(jù)各個(gè)虛擬機(jī)屬性差異最小的原則進(jìn)行的。據(jù)此,為每個(gè)虛擬機(jī)構(gòu)建一個(gè)如下的性能判斷函數(shù),即:
其中,Num表示與此虛擬機(jī)通信的其他虛擬機(jī)數(shù)目;Bw表示此虛擬機(jī)需要的帶寬總量;Load表示此虛擬機(jī)已經(jīng)承擔(dān)的負(fù)載情況;Hard表示此虛擬機(jī)和服務(wù)器主機(jī)等硬件設(shè)施進(jìn)行匹配時(shí)所需的硬件資源;αi表示每一種子屬性在總屬性之中的權(quán)重。
Bw的計(jì)算為:
其中,bwi表示第i個(gè)和此虛擬機(jī)通信信道所需的帶寬;k表示與此虛擬機(jī)聯(lián)系的所有其他虛擬機(jī)的數(shù)目。
Hard的計(jì)算為:
其中,CPU表示此虛擬機(jī)需要硬件匹配的 CPU主頻高低;REM表示此虛擬機(jī)需要硬件匹配的內(nèi)存大小;STO表示此虛擬機(jī)需要硬件匹配的硬盤(pán)大小。
根據(jù)式(3)所構(gòu)建的排序判斷公式,云端所有可以利用的虛擬機(jī)資源就可以按照屬性差異的大小進(jìn)行一個(gè)升序的排列,從而形成一個(gè)按順序排列的虛擬機(jī)屬性集合
依托動(dòng)態(tài)優(yōu)化全局優(yōu)化策略實(shí)現(xiàn)虛擬機(jī)聚簇,其核心思路就是從中尋找處于中間位置的虛擬機(jī),然后逐漸向兩端搜索與其各方面差異最小的虛擬機(jī)聚集成簇。這個(gè)決策函數(shù)為:
至此,構(gòu)建出依托于動(dòng)態(tài)規(guī)劃全局優(yōu)化策略的虛擬機(jī)聚簇判斷準(zhǔn)則函數(shù),即:
其中,Xk和Uk的計(jì)算分別如式(3)和式(6)。
2.3虛擬機(jī)聚簇算法的流程
基于動(dòng)態(tài)規(guī)劃全局優(yōu)化的虛擬機(jī)聚簇算法的基本流程如圖2所示,具體步驟如下:
步驟 1. 設(shè)置虛擬機(jī)屬性判斷函數(shù),如式(3)所示,計(jì)算云端可利用的每一個(gè)虛擬機(jī)屬性。
步驟2. 對(duì)云端所有可以利用的虛擬機(jī),按照屬性高低進(jìn)行升序排列。
步驟3. 構(gòu)建用于聚簇判斷的動(dòng)態(tài)規(guī)劃全局優(yōu)化函數(shù)。
步驟4. 選擇升序集合中處于中間位置的虛擬機(jī),作為聚簇的起始位置。
步驟5. 執(zhí)行動(dòng)態(tài)規(guī)劃優(yōu)化的聚簇處理,從兩個(gè)方向判斷臨近虛擬機(jī)是否符合聚簇條件。滿(mǎn)足聚簇條件的,將臨近虛擬機(jī)設(shè)置為下一階段判斷的起始位置,繼續(xù)執(zhí)行聚簇判斷。不滿(mǎn)足聚簇條件的,將臨近虛擬機(jī)納入候選虛擬機(jī)集合,繼續(xù)判斷下一個(gè)虛擬機(jī)是否滿(mǎn)足聚簇條件。
步驟6. 不斷更新虛擬機(jī)的狀態(tài),重復(fù)步驟5,直到升序集合和候選集合中的所有虛擬機(jī)都執(zhí)行了聚簇判斷。
步驟7. 將形成聚簇的虛擬機(jī)歸并為一個(gè)簇,用于后續(xù)和硬件資源的匹配。沒(méi)有納入此簇的其他虛擬機(jī),可以重新執(zhí)行一個(gè)新的聚簇處理,或留用待命。
圖2 虛擬機(jī)聚簇算法流程
通過(guò)如下的實(shí)驗(yàn)過(guò)程驗(yàn)證本文提出的虛擬機(jī)聚簇方法的有效性。實(shí)驗(yàn)仿真平臺(tái)選用云計(jì)算性能測(cè)試常用的軟件CloudSim。在CloudSim平臺(tái)下,云數(shù)據(jù)處理硬件結(jié)構(gòu)的數(shù)據(jù)中心,主要依托于采取的機(jī)架數(shù)目。以一個(gè)機(jī)架配置 8個(gè)刀片中心、一個(gè)刀片中心配置16臺(tái)服務(wù)器主機(jī)的模式設(shè)置。一個(gè)數(shù)據(jù)中心下的服務(wù)器主機(jī)數(shù)量就是 128個(gè),兩個(gè)數(shù)據(jù)中心下的服務(wù)器主機(jī)數(shù)量就是256個(gè),3個(gè)數(shù)據(jù)中心下的服務(wù)器主機(jī)數(shù)量就是 512個(gè),以此類(lèi)推。在虛擬機(jī)的設(shè)置方面,設(shè)置10種類(lèi)型的虛擬機(jī),其CPU主頻、內(nèi)存、硬盤(pán)等硬件的匹配需求,如表1所示。
表1 虛擬機(jī)的設(shè)置
虛擬機(jī)和其他虛擬機(jī)通信的帶寬需求以及虛擬機(jī)上的實(shí)際負(fù)載情況,是根據(jù)系統(tǒng)設(shè)置的隨機(jī)指令更替系統(tǒng)而隨機(jī)發(fā)生變化的,以模擬云端實(shí)際虛擬機(jī)的使用情況。這種隨機(jī)變化,也就為后續(xù)的動(dòng)態(tài)規(guī)劃聚簇提供了可以判別的依據(jù)。對(duì)應(yīng)于硬件資源,每一個(gè)數(shù)據(jù)中心配置500個(gè)虛擬機(jī),500個(gè)虛擬機(jī)都按照表1的方式分為10類(lèi),每類(lèi)50個(gè)虛擬機(jī)。
分別按照Greedy算法、啟發(fā)式算法、本文提出的動(dòng)態(tài)規(guī)劃聚簇方法執(zhí)行虛擬機(jī)的聚簇處理,考察這 3種方法形成聚簇效果的時(shí)間差異,結(jié)果如圖3所示。
圖3 三種方法的聚簇時(shí)間對(duì)比
從圖 3中可以看出,本文方法和啟發(fā)式方法的聚簇時(shí)間都是增加幅度由快變慢,且本文方法在聚簇的絕對(duì)時(shí)間上明顯偏低,實(shí)現(xiàn)2 000個(gè)虛擬機(jī)的聚簇,僅僅花費(fèi)了3.2 s,而啟發(fā)式方法則花費(fèi)了近10 s。Greedy聚簇算法雖然起初的聚簇時(shí)間較低,但之后增長(zhǎng)趨勢(shì)越來(lái)越明顯,實(shí)現(xiàn)2 000個(gè)虛擬機(jī)的聚簇,時(shí)間消耗達(dá)到了11.3 s??梢?jiàn),3種方法的聚簇時(shí)間對(duì)比,明顯證實(shí)了本文方法的聚簇速度更快。
聚簇對(duì)云數(shù)據(jù)處理效率的提升是否有益,一般通過(guò)跳數(shù)來(lái)進(jìn)行衡量。如果聚簇合理,虛擬機(jī)之間的通信就會(huì)相對(duì)穩(wěn)定,跳變發(fā)生的次數(shù)少,跳數(shù)也偏低,這有利于云數(shù)據(jù)高效處理。反之,跳數(shù)越高,聚簇越不穩(wěn)定,云數(shù)據(jù)處理的效率也就會(huì)大大降低。3種方法聚簇后的跳數(shù)比對(duì)如圖4所示。
圖4 3種方法聚簇的跳數(shù)對(duì)比
從圖4中可以看出,3種方法形成的聚簇效果比對(duì),本文的方法最為理想,其跳數(shù)隨著聚簇虛擬機(jī)數(shù)量的增加出現(xiàn)的數(shù)量最少,最有利于云數(shù)據(jù)處理過(guò)程穩(wěn)定地實(shí)現(xiàn)。
隨著云計(jì)算的發(fā)展和逐步成熟,在云端實(shí)現(xiàn)大數(shù)據(jù)處理的計(jì)算任務(wù)越來(lái)越多。原本針對(duì)虛擬機(jī)部署的執(zhí)行策略,已經(jīng)逐步向多個(gè)虛擬機(jī)形成的虛擬機(jī)簇進(jìn)行部署的執(zhí)行策略轉(zhuǎn)變。本文針對(duì)虛擬機(jī)如何實(shí)現(xiàn)有效聚簇來(lái)展開(kāi)研究, 依托虛擬機(jī)簇的構(gòu)建原理和云數(shù)據(jù)處理的普適性硬件結(jié)構(gòu),引入一種動(dòng)態(tài)規(guī)劃的全局優(yōu)化策略,以實(shí)現(xiàn)虛擬機(jī)的聚簇處理。整個(gè)聚簇過(guò)程的實(shí)現(xiàn),首先設(shè)置虛擬機(jī)的屬性判斷函數(shù),進(jìn)而執(zhí)行升序排序處理,然后執(zhí)行動(dòng)態(tài)規(guī)劃全局優(yōu)化判斷策略,從升序集合的中心位置開(kāi)始向兩個(gè)方向進(jìn)行聚簇。實(shí)驗(yàn)結(jié)果表明,本文構(gòu)建的基于動(dòng)態(tài)規(guī)劃的聚簇方法,不僅實(shí)現(xiàn)了虛擬機(jī)資源的快速聚簇,而且聚簇的效果也比較合理,對(duì)于云數(shù)據(jù)處理過(guò)程穩(wěn)定的實(shí)現(xiàn)是有益的。
[1] Jayasinghe D, Pu C, Eilam T, et al. Improving performance and availability of services hosted on IaaS clouds with structural constraint-aware virtual machine placement [C]//2011 IEEE International Conference on Services Computing. Piscataway: United States, 2011: 72-79.
[2] 楊博, 劉大有, Liu J M, 等. 復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法[J].軟件學(xué)報(bào), 2009, 20(1): 54-56.
[3] Gupta R, Bose S K, Sundarrajan S, et al. A two stage heuristic algorithm for solving the server consolidation problem with item-item and bin-item incompatibility constraints [C]//SCC 08: Proceedings of the 2008 IEEE International Conference on Services Computing. Piscataway: United States, 2008: 39-46.
[4] Calheiros R N, Ranjan R, De Rose C A F, et al. CloudSim: a novel framework for modeling and simulation of cloud computing infrastructures and services, Grids-Tr-2009-1 [R]. Melbourne Australia: the University of Melbourne, Grid Computing and Distributed Systems Laboratory, 2009.
[5] 李強(qiáng), 郝沁汾, 肖利民, 等. 云計(jì)算中虛擬機(jī)放置的自適應(yīng)管理與多目標(biāo)優(yōu)化[J]. 計(jì)算機(jī)學(xué)報(bào), 2011, 34(12): 2253-2264.
[6] 何東曉, 周栩, 王佐, 等. 復(fù)雜網(wǎng)絡(luò)社區(qū)挖掘——基于聚類(lèi)融合的遺傳算法[J]. 自動(dòng)化學(xué)報(bào), 2010, 36(8): 1160-1170.
[7] 劉進(jìn)軍, 趙生慧. 面向云計(jì)算的多虛擬機(jī)管理模型的設(shè)計(jì)[J]. 計(jì)算機(jī)應(yīng)用, 2011, 31(5): 1417-1422.
[8] 王光波, 馬自堂, 孫磊, 等. 基于架構(gòu)負(fù)載感知的虛擬機(jī)聚簇部署算法[J]. 計(jì)算機(jī)應(yīng)用, 2013, 33(5): 1271-1275.
[9] Rana S, Jasola S, Kumar R. A hybrid sequential approach for data clustering using K-means and particle swarm optimization algorithm [J]. International Journal of Engineering, Science and Technology, 2010, 2(6): 167-176.
[10] Zhou W Y, Yang S B, Fang J, et al. Vmctune: a load balancing scheme for virtual machine cluster using dynamic resource allocation [C]//Grid and Cooperative Computing (GCC), 2010 9th International Conference on. IEEE, 2010: 81-86.
[11] Cui L, Li B, Zhang Y Y, et al. Hotsnap: a hot distributed snapshot system for virtual machine cluster [C]// Proceedings of the 27th International Conference on Large Installation System Administration, 2013: 59-74.
[12] 趙銀亮, 朱常鵬, 韓博, 等. 以虛擬機(jī)為核心實(shí)現(xiàn)動(dòng)態(tài)行為調(diào)整的方法[J]. 西安交通大學(xué)學(xué)報(bào), 2013, 47(6): 6-11.
[13] 孫鵬劼, 翟?shī)^樓, 劉東旭, 等. 基于Web的拉絲模仿真系統(tǒng)開(kāi)發(fā)與研究[J]. 圖學(xué)學(xué)報(bào), 2013, 6(6): 106-109.
Clustering Method of Virtual Machine in Cloud Computing Based on Dynamic Programming
Zhu Yanjun
(Department of Computer Engineering, Dongguan Polytechnic, Dongguan Guangdong 523808, China)
Fast and efficient implementation of multiple virtual machine cluster is greatly significant to enhance processing ability of cloud computing. In this paper, a new clustering method is proposed for virtual machine with general principle of virtual machine cluster and dynamic programming strategy. First, all virtual machine resources are performing in ascending order according to default discriminant function. Second, virtual machine at center position of ascending set is selected as starting point of clustering, and dynamic programming strategy begins from two directions. Clustering principles are based on dynamic programming criterion. Experimental results show that cluster method based on dynamic programming has a fast speed and a stable effect.
virtual machine; clustering; cloud computing; dynamic programming
TP 393
A
2095-302X(2015)06-0955-05
2015-06-25;定稿日期:2015-07-21
2014年度東莞職業(yè)技術(shù)學(xué)院院級(jí)科研基金資助項(xiàng)目(2014b05);東莞市高等院校、科研機(jī)構(gòu)科技計(jì)劃一般項(xiàng)目(2014106101037,2014106101033);東莞職業(yè)技術(shù)學(xué)院政校行企合作開(kāi)展科研與服務(wù)資助項(xiàng)目(ZXHQ2014d010);廣東省省級(jí)科技計(jì)劃項(xiàng)目(2014A010103002)
祝衍軍(1982–),男,湖南邵陽(yáng)人,工程師,碩士。主要研究方向?yàn)樵朴?jì)算、商業(yè)智能。E-mail:zhuyanjunhn@126.com