鄧聃婷，滕 飛,2，李天瑞，楊 浩

(1.西南交通大學(xué)信息科學(xué)與技術(shù)學(xué)院， 四川 成都 610031;2.南京大學(xué)計(jì)算機(jī)軟件新技術(shù)國家重點(diǎn)實(shí)驗(yàn)室,江蘇 南京 210023)

基于MapReduce虛擬集群的能耗優(yōu)化算法*

鄧聃婷1，滕 飛1,2，李天瑞1，楊 浩1

(1.西南交通大學(xué)信息科學(xué)與技術(shù)學(xué)院， 四川 成都 610031;2.南京大學(xué)計(jì)算機(jī)軟件新技術(shù)國家重點(diǎn)實(shí)驗(yàn)室,江蘇 南京 210023)

隨著全球能源危機(jī)的出現(xiàn)，許多研究者開始關(guān)注數(shù)據(jù)中心的能耗問題。在滿足用戶需求的前提下，減少數(shù)據(jù)中心的活躍節(jié)點(diǎn)個(gè)數(shù)能夠有效地降低其能耗。傳統(tǒng)的減少活躍節(jié)點(diǎn)的方式是虛擬機(jī)遷移，但虛擬機(jī)遷移會(huì)造成極大的系統(tǒng)開銷。提出一種基于MapReduce虛擬集群的能耗優(yōu)化算法——在線時(shí)間平衡算法OTBA，能夠減少活躍物理節(jié)點(diǎn)數(shù)，有效降低數(shù)據(jù)中心的能耗，并且避免了虛擬機(jī)的遷移。通過建立云數(shù)據(jù)中心的能耗模型、用戶提交服務(wù)的排隊(duì)模型和評價(jià)作業(yè)完成質(zhì)量的作業(yè)運(yùn)行模型，確定了數(shù)據(jù)中心節(jié)能模型的目標(biāo)函數(shù)和變量因子。在線時(shí)間平衡算法是基于虛擬云環(huán)境和在線MapReduce作業(yè)的一種節(jié)能調(diào)度算法，能夠在虛擬機(jī)的生命周期和資源利用率之間做出權(quán)衡，使數(shù)據(jù)中心激活的服務(wù)器達(dá)到最少，能耗降到最低。此外，該結(jié)果通過仿真和Hadoop平臺上的實(shí)驗(yàn)得到了驗(yàn)證。

能耗優(yōu)化；虛擬機(jī)放置；在線；MapReduce；云計(jì)算

1 引言

近年來，云計(jì)算這種新型計(jì)算方式已經(jīng)成為研究和應(yīng)用的熱點(diǎn)。各種各樣的云計(jì)算產(chǎn)品層出不窮，例如，Amazon推出的彈性計(jì)算云EC2、Google推出的谷歌應(yīng)用軟件引擎AppEngine、Microsoft推出的Azure云計(jì)算平臺等。然而，這些大規(guī)模的云計(jì)算基礎(chǔ)設(shè)施使得能量消耗逐年增長。據(jù)Amazon的估計(jì)[1]，云數(shù)據(jù)中心的能耗成本占到營業(yè)總成本的42%。事實(shí)證明，數(shù)據(jù)中心除了必要的能量消耗之外，其運(yùn)行過程中存在能量浪費(fèi)現(xiàn)象，文獻(xiàn)[2]研究顯示，數(shù)據(jù)中心的物理節(jié)點(diǎn)在空閑時(shí)的功耗為滿負(fù)載時(shí)功耗的60%左右。

目前，降低云數(shù)據(jù)中心能耗的主要方法是虛擬化技術(shù)。虛擬化技術(shù)實(shí)現(xiàn)了多個(gè)虛擬機(jī)在一臺服務(wù)器上運(yùn)行，使用該技術(shù)通常采用的方法是集中管理，即使用虛擬機(jī)放置控制器對云數(shù)據(jù)中心的所有服務(wù)器上的虛擬機(jī)進(jìn)行統(tǒng)一管理[3]。其中有兩種常用的資源整合方法。第一種是根據(jù)現(xiàn)有的虛擬機(jī)需求分配活躍的服務(wù)器，放置虛擬機(jī)，并且讓剩余的未使用的服務(wù)器處于低能耗的狀態(tài)[1]。另一種是當(dāng)檢測到虛擬機(jī)放置不合理時(shí)，對不合理的虛擬機(jī)進(jìn)行遷移。盡管虛擬機(jī)的遷移可以平衡工作負(fù)載以及減少服務(wù)器的數(shù)量，但是遷移會(huì)造成服務(wù)器CPU資源的消耗，導(dǎo)致極大的系統(tǒng)開銷，有時(shí)遷移的成本甚至超過關(guān)閉服務(wù)器所帶來的收益[4]。因此，本文主要采用虛擬機(jī)放置策略降低能耗，不考慮遷移技術(shù)。

MapReduce是一種編程模型，用于大規(guī)模數(shù)據(jù)集的并行運(yùn)算，采用分布式處理框架，能夠在廉價(jià)機(jī)器組成的集群下保持較高的性能，其兩個(gè)特點(diǎn)將直接影響數(shù)據(jù)中心的節(jié)能效果。第一個(gè)是可擴(kuò)展性，其計(jì)算效率可通過擴(kuò)展提高；第二個(gè)是可伸縮性，這意味著每增加一個(gè)節(jié)點(diǎn)，就能將其計(jì)算能力接入到集群中，這將影響作業(yè)的執(zhí)行時(shí)間。許多云數(shù)據(jù)中心采用MapReduce模型處理數(shù)據(jù)密集型服務(wù)。一些研究者也開始研究基于MapReduce并行計(jì)算框架的節(jié)能機(jī)制，如DVFS[5]、數(shù)據(jù)放置[6]和數(shù)據(jù)壓縮[7]。

本文為了最小化基于MapReduce框架的云數(shù)據(jù)中心的能量消耗，提出一種基于MapReduce虛擬集群針對隨機(jī)作業(yè)的能耗優(yōu)化算法——在線時(shí)間平衡算法OTBA(Online Time Balance Algorithm)。OTBA在某些方面不同于傳統(tǒng)的虛擬機(jī)放置算法。該算法是為提供基礎(chǔ)設(shè)施服務(wù)的云供應(yīng)商設(shè)計(jì)的。云供應(yīng)商根據(jù)不同的CPU、內(nèi)存、存儲(chǔ)、操作系統(tǒng)等制定虛擬機(jī)類型。MapReduce用戶可根據(jù)需求定制虛擬集群，其規(guī)模和類型由用戶給出。云供應(yīng)商根據(jù)隨機(jī)到達(dá)的用戶需求，以能耗最小化為目標(biāo)，放置MapReduce虛擬集群。

本文的主要貢獻(xiàn)如下：通過建立數(shù)據(jù)中心模型、能耗模型、隨機(jī)作業(yè)模型和作業(yè)運(yùn)行模型，建立了云計(jì)算節(jié)能目標(biāo)，并提出一種針對在線模式的虛擬機(jī)放置算法。該算法根據(jù)當(dāng)前作業(yè)隊(duì)列和當(dāng)前服務(wù)器的使用情況，在線生成虛擬機(jī)放置方案，使云數(shù)據(jù)中心通過合理放置虛擬機(jī)降低能量消耗，減少活躍服務(wù)器的數(shù)目。最后，本文還通過模擬實(shí)驗(yàn)和Hadoop平臺實(shí)驗(yàn)對OTBA的性能進(jìn)行了測試，驗(yàn)證了OTBA在節(jié)能方面的有效性。

2 系統(tǒng)模型

本節(jié)介紹本文的系統(tǒng)模型，包含云數(shù)據(jù)中心模型、能耗模型、隨機(jī)作業(yè)模型和作業(yè)運(yùn)行模型。

2.1 云數(shù)據(jù)中心模型

云數(shù)據(jù)中心模型包含一個(gè)虛擬機(jī)放置控制器和很多臺同構(gòu)服務(wù)器。虛擬機(jī)放置控制器用于調(diào)配每臺服務(wù)器分配多少個(gè)虛擬機(jī)。

定義1云數(shù)據(jù)中心表示為集合DataCenter={pm1,pm2,…,pmm}。云數(shù)據(jù)中心DataCenter中包含有m臺服務(wù)器，pmi代表數(shù)據(jù)中心中任意一臺服務(wù)器。

定義2一臺服務(wù)器的物理資源用一個(gè)三維向量(r1,r2,r3)來表示。r1代表CPU的個(gè)數(shù)，r2代表Memory的大小，r3代表Storage的大小。

定義3服務(wù)器表示為集合S={vm1,…,vmn}。每臺服務(wù)器S中運(yùn)行n臺虛擬機(jī)，vmi代表任意一臺虛擬機(jī)。

定義4虛擬機(jī)的資源占用情況用一個(gè)三維向量(vr1,vr2,vr3)來表示。vr1代表虛擬機(jī)所分得的CPU個(gè)數(shù)，vr2代表虛擬機(jī)所分得的Memory大小，vr3代表虛擬機(jī)所分得的Storage的大小。

本文采用的云數(shù)據(jù)中心模型類似于Amazon EC2 IaaS平臺，云供應(yīng)商根據(jù)用戶需求提供定制虛擬主機(jī)服務(wù)。云數(shù)據(jù)中心可提供多種不同類型的虛擬機(jī)供用戶選擇，用戶根據(jù)CPU、內(nèi)存、存儲(chǔ)等參數(shù)以及自身作業(yè)特點(diǎn)選擇虛擬機(jī)。其中虛擬機(jī)種類是離散、有限的，通常由云供應(yīng)商預(yù)先設(shè)定。通常來說，云數(shù)據(jù)中心提供的虛擬機(jī)類型不會(huì)太多，例如Amazon EC2根據(jù)CPU、內(nèi)存、存儲(chǔ)和網(wǎng)絡(luò)容量等不同組合提供30種虛擬機(jī)方案，其中常用的類型僅八種。

在這個(gè)模型中，用戶提交的數(shù)據(jù)存儲(chǔ)于共用的HDFS文件系統(tǒng)中，在MapReduce作業(yè)開始時(shí)，虛擬集群從共用的HDFS集群中讀取數(shù)據(jù)。云數(shù)據(jù)中心根據(jù)用戶選定的虛擬機(jī)類型以及用戶輸入的虛擬機(jī)最小使用量，建立單獨(dú)的虛擬集群。

2.2 能耗模型

云數(shù)據(jù)中心的能耗主要分為三個(gè)部分：服務(wù)器能耗、網(wǎng)絡(luò)能耗和冷卻設(shè)備能耗。其中，服務(wù)器是數(shù)據(jù)中心的關(guān)鍵設(shè)備，服務(wù)器能耗是云數(shù)據(jù)中心能耗的主要部分。因此，本文暫不考慮網(wǎng)絡(luò)能耗和冷卻設(shè)備能耗。

能耗是計(jì)算機(jī)系統(tǒng)一段時(shí)間內(nèi)的能量消耗[3]，單位是焦耳J，其定義如下所示：

其中,E表示服務(wù)器的總能耗消耗，由時(shí)間t和功耗p兩個(gè)因素共同決定。功耗指單位時(shí)間內(nèi)能量的消耗，反映計(jì)算機(jī)系統(tǒng)消耗能量的速率，單位是瓦特W。

本文采用文獻(xiàn)[8]給出的功耗的一般定義：

其中，Pmax為服務(wù)器滿負(fù)載時(shí)的功耗，文中將其設(shè)為250 W[1]。k取值為0.6表示服務(wù)器在空負(fù)載時(shí)的功耗為滿載時(shí)功耗的60%[8]。這說明，服務(wù)器在空閑狀態(tài)時(shí)，如果不將其關(guān)閉或休眠，服務(wù)器的能耗也很大。u(t)為資源利用率。

本文采用的模型僅支持服務(wù)器開關(guān)兩種能耗狀態(tài)。服務(wù)器無論滿負(fù)荷運(yùn)行與否，能耗為一定值。當(dāng)服務(wù)器上所有的作業(yè)執(zhí)行完畢時(shí)，服務(wù)器將進(jìn)入休眠狀態(tài)，能量消耗可忽略不計(jì)。

根據(jù)上面的描述，云數(shù)據(jù)中心能耗EDataCenter可以看作是云數(shù)據(jù)中心內(nèi)的所有服務(wù)器的能耗值之和，其定義式如下：

其中，Epmi為一臺服務(wù)器的能耗。

服務(wù)器的能耗主要由CPU、內(nèi)存、存儲(chǔ)等決定，而這些物理資源的使用又與虛擬機(jī)的放置息息相關(guān)。虛擬機(jī)的資源占用量越大，必然服務(wù)器的能耗也越大。本文重點(diǎn)考慮MapReduce虛擬集群的能耗管理問題。

2.3 隨機(jī)作業(yè)模型

在云數(shù)據(jù)中心，所有作業(yè)隨機(jī)到達(dá)，虛擬機(jī)放置控制器為作業(yè)分配虛擬集群，作業(yè)完成后釋放虛擬集群，回收服務(wù)器資源，這就是本文的隨機(jī)作業(yè)模型。

用戶提交作業(yè)的時(shí)間、作業(yè)類型和作業(yè)大小、所需要的虛擬機(jī)類型以及虛擬機(jī)的最小使用量都不同，所以這里假設(shè)所有作業(yè)都是獨(dú)立的。虛擬機(jī)的最小使用量指的是，用戶根據(jù)作業(yè)特點(diǎn)以及所采用的虛擬機(jī)類型為每一種作業(yè)制定的，用來保障作業(yè)能在截止期內(nèi)完成。

由于用戶提交時(shí)間的不同，作業(yè)到達(dá)云數(shù)據(jù)中心的時(shí)間是不確定的，這類似于現(xiàn)實(shí)生活中的排隊(duì)購票、收銀等現(xiàn)象。根據(jù)實(shí)際情況中的統(tǒng)計(jì)數(shù)據(jù)，本文采用的隨機(jī)作業(yè)模型的到達(dá)率服從泊松分布，排隊(duì)規(guī)則為單隊(duì)多服務(wù)臺規(guī)則。根據(jù)用戶提交的作業(yè)類型和作業(yè)大小的不同，通常將作業(yè)類型分為CPU密集型、I/O密集型等。作業(yè)所需要的虛擬機(jī)類型以及虛擬機(jī)的最小使用量是不同的，用戶選擇云供應(yīng)商預(yù)先設(shè)定的適合自己作業(yè)的虛擬機(jī)類型。

定義5隨機(jī)到達(dá)的作業(yè)用七維向量(λi,MTi,RTi,mi,ri,VMi,VMnumi)來表示。λi是作業(yè)平均到達(dá)率，平均到達(dá)率是單位時(shí)間內(nèi)到達(dá)任務(wù)的平均數(shù)，在[0,t]時(shí)間間隔內(nèi)任務(wù)到達(dá)的平均數(shù)量為λit。換言之，平均到達(dá)時(shí)間間隔為1/λi。如果平均到達(dá)時(shí)間間隔為1/λt小于作業(yè)預(yù)處理時(shí)間，則會(huì)造成排隊(duì)現(xiàn)象。MTi為map任務(wù)，RTi為reduce任務(wù)，這兩個(gè)值是作業(yè)在給定虛擬集群下的完成時(shí)間，是在作業(yè)預(yù)處理過程通過歷史信息估計(jì)得到的。mi是map任務(wù)大小，ri是reduce任務(wù)大小。VMi是所需要的虛擬機(jī)類型。VMnumi是用戶制定的虛擬機(jī)的最小使用量。

隨機(jī)作業(yè)模型可描述為：不同類型、不同大小的作業(yè)以一定的時(shí)間間隔到達(dá)云數(shù)據(jù)中心，云數(shù)據(jù)中心對當(dāng)前排隊(duì)的作業(yè)進(jìn)行預(yù)處理，分配虛擬集群，最后執(zhí)行作業(yè)。

2.4 作業(yè)運(yùn)行模型

作業(yè)的運(yùn)行時(shí)間是評價(jià)MapReduce集群的一個(gè)重要標(biāo)準(zhǔn)。本文通過歷史信息估計(jì)作業(yè)運(yùn)行時(shí)間，建立MapReduce作業(yè)運(yùn)行模型。

MapReduce作業(yè)由兩個(gè)階段組成：map任務(wù)階段和reduce任務(wù)階段。

在每個(gè)階段中，任務(wù)輸入數(shù)據(jù)的大小相同，如map任務(wù)階段的默認(rèn)分片大小為64 MB。同時(shí),由于采用了相同的函數(shù)，因此每個(gè)任務(wù)的處理時(shí)間基本相同，可根據(jù)歷史信息獲得其運(yùn)行時(shí)間。MapReduce作業(yè)的運(yùn)行時(shí)間主要和作業(yè)的數(shù)據(jù)量大小、虛擬機(jī)類型以及虛擬集群規(guī)模有關(guān)。因此，本文對運(yùn)行時(shí)間的估計(jì)如下：

其中，mT為該作業(yè)的map任務(wù)的平均時(shí)間，rT為reduce任務(wù)的平均時(shí)間。mNum為map任務(wù)的個(gè)數(shù)，與作業(yè)的數(shù)據(jù)量相關(guān)，rNum為reduce任務(wù)的個(gè)數(shù)，與作業(yè)的類型相關(guān)。mSlot為map槽數(shù)，與虛擬機(jī)的類型相關(guān)，一般來說虛擬機(jī)的map槽數(shù)為該虛擬機(jī)vCPU個(gè)數(shù)的兩倍，rSlot為reduce槽數(shù)。Num為分配給該作業(yè)的虛擬集群的大小。δ為作業(yè)預(yù)處理的時(shí)間。

服務(wù)器S的運(yùn)行時(shí)間為：

服務(wù)器的運(yùn)行時(shí)間等于服務(wù)器上最后一個(gè)作業(yè)完成的時(shí)間與服務(wù)器開機(jī)時(shí)間之差。

云數(shù)據(jù)中心的運(yùn)行時(shí)間為：

云數(shù)據(jù)中心的運(yùn)行時(shí)間為所有服務(wù)器的運(yùn)行時(shí)間之和。

3 虛擬集群能耗優(yōu)化策略

本節(jié)介紹的核心算法用于虛擬機(jī)放置控制器。MapReduce作業(yè)隨機(jī)到達(dá)，虛擬機(jī)放置控制器首先對已使用的服務(wù)器的剩余資源進(jìn)行判斷，如果沒有已使用的服務(wù)器或不滿足二次利用的條件，則開啟新的服務(wù)器，對其進(jìn)行一次配方生成打包算法；反之，如果滿足條件則對剩余資源加以利用，進(jìn)行二次配方生成打包算法，重復(fù)這個(gè)過程直至所有作業(yè)完成。虛擬機(jī)放置控制器在為每臺服務(wù)器放置虛擬機(jī)的過程中涉及兩個(gè)算法：配方生成打包算法和在線時(shí)間平衡算法。

3.1 配方生成打包算法

配方生成打包算法[9]是生成有序虛擬機(jī)放置方案列表并放置的過程。配方指一種填充給定物理資源的可行的虛擬機(jī)放置方案。例如，云供應(yīng)商提供三種類型的虛擬機(jī)VM1、VM2和VM3，配方可由一個(gè)向量表示〈2,1,0〉，其含義是在給定物理資源上放置2臺VM1的虛擬機(jī)、1臺VM2的虛擬機(jī)、0臺VM3的虛擬機(jī)。先根據(jù)MapReduce作業(yè)隊(duì)列、所需要的虛擬機(jī)、虛擬機(jī)資源占用情況和給定的物理資源生成基本的配方列表、再對其進(jìn)行排序，生成有序的配方列表。最后，虛擬機(jī)放置控制器根據(jù)有序配方列表、虛擬機(jī)資源池和待放置的服務(wù)器，對虛擬機(jī)進(jìn)行放置。

配方生成打包算法[9]中設(shè)置了一個(gè)排序機(jī)制，用于找出給定物理資源中最節(jié)能的配方。這個(gè)排序機(jī)制首先保證服務(wù)器的空間利用率。一個(gè)云數(shù)據(jù)中心的總能耗取決于活躍服務(wù)器的數(shù)量，以及每臺服務(wù)器的運(yùn)行時(shí)間。再優(yōu)先選擇同種類型的或完成時(shí)間相近的作業(yè)的配方，即配方包含的虛擬機(jī)種類的數(shù)量越少越好。換言之，時(shí)間平衡的配方比時(shí)間不平衡的配方更節(jié)能。不同的配方會(huì)導(dǎo)致能耗有高有低，為了減少服務(wù)器的使用數(shù)量和運(yùn)行時(shí)間，在進(jìn)行配方生成時(shí)優(yōu)先選擇系統(tǒng)利用率高和時(shí)間平衡的配方，提高數(shù)據(jù)中心的平均系統(tǒng)利用率。在打包過程中，先放置優(yōu)先級高的配方。

3.2 在線時(shí)間平衡算法OTBA

在線時(shí)間平衡算法是針對在線提交作業(yè)的云數(shù)據(jù)中心提出的。其主要過程是：MapReduce作業(yè)隨機(jī)到達(dá)，虛擬機(jī)放置控制器找出每臺服務(wù)器最節(jié)能的虛擬機(jī)放置方案，最小化云數(shù)據(jù)中心的能耗。

這個(gè)過程主要面臨如下幾個(gè)問題：第一是當(dāng)作業(yè)到達(dá)時(shí)，如何統(tǒng)計(jì)現(xiàn)有物理資源；第二是如何對已經(jīng)放置了虛擬機(jī)的服務(wù)器的剩余資源進(jìn)行判斷，即判斷是否需要開啟新的服務(wù)器；第三是如何對剩余資源可用的服務(wù)器進(jìn)行二次配方生成；第四是當(dāng)作業(yè)完成時(shí)，如何調(diào)整剩余物理資源。

對于第一個(gè)問題，本文提出的算法設(shè)置了一個(gè)物理資源表。物理資源表用于記錄當(dāng)前數(shù)據(jù)中心的服務(wù)器的資源占用情況。當(dāng)分配虛擬機(jī)時(shí)，物理資源表中記錄的物理資源減少。

對于第二個(gè)問題，本文提出的算法將當(dāng)前的服務(wù)器的剩余資源與最小虛擬機(jī)的資源占用進(jìn)行對比，如果當(dāng)前服務(wù)器的剩余資源小于最小虛擬機(jī)的資源占用，則說明剩余物理資源不可用，需要開啟新的服務(wù)器。

對于第三個(gè)問題，如果當(dāng)前服務(wù)器剩余資源大于最小虛擬機(jī)的資源占用，則說明剩余物理資源可用。假如遇到多臺剩余物理資源可用的服務(wù)器時(shí)，優(yōu)先選擇運(yùn)行完成時(shí)間相近的作業(yè)的服務(wù)器對其進(jìn)行二次配方生成。進(jìn)行二次配方生成的目的是避免資源浪費(fèi)，節(jié)約能量。

定義6時(shí)間平衡指數(shù)(timeBalance)。描述原服務(wù)器運(yùn)行時(shí)間和待分配作業(yè)的時(shí)間之間的時(shí)間差。計(jì)算公式為：

timeBalance=TPMruntime-Tnewjob

其中，TPMruntime指服務(wù)器目前的剩余運(yùn)行時(shí)間，Tnewjob指新到達(dá)作業(yè)的運(yùn)行時(shí)間。

對于第四個(gè)問題，當(dāng)作業(yè)完成時(shí)，釋放虛擬機(jī)資源，服務(wù)器收回物理資源，更新物理資源表。

算法在線時(shí)間平衡算法OTBA

輸入：作業(yè)隊(duì)列JobQueue，虛擬機(jī)資源池vp;

輸出：虛擬機(jī)分配列表。

1.同步作業(yè)隊(duì)列JobQueue和虛擬機(jī)資源池vp;

2.獲取當(dāng)前PM信息，生成物理資源表PMResourceList;

3.if有作業(yè)完成do

4. 收回虛擬集群資源，更新PMResourceList;

5.endif

6.令n=1;//表示當(dāng)前物理機(jī)

7.whilen

8. if 當(dāng)前的PM資源率大于最小VM資源利用率 do

9. 將當(dāng)前PM標(biāo)記為可用PM;

10. 計(jì)算每個(gè)可用PM的時(shí)間平衡指數(shù)timeBalance;

11. end if

12.n++;

13.end while

14.將可用PM以timeBalance由低到高排序，生成可用物理機(jī)列表PMAvailable;

15.fori=1,…,PMAvailabledo //遍歷可用物理機(jī)

16. while 虛擬機(jī)資源池vp不為空 do

17. 從PMResourceList中讀取當(dāng)前PM的資源情況;

18. 使用配方生成算法生成配方;

19. 使用打包算法為當(dāng)前PM放置VM;

20. end while

21.end for

時(shí)間平衡指數(shù)越大說明原服務(wù)器與待分配作業(yè)之間越不平衡，反之則越平衡。

OTBA展示了如何針對隨機(jī)到達(dá)的作業(yè)獲取虛擬機(jī)分配列表。首先獲取作業(yè)隊(duì)列及虛擬機(jī)資源池，再根據(jù)當(dāng)前服務(wù)器信息生成物理資源表。當(dāng)虛擬機(jī)資源池不為空時(shí)，遍歷已使用的服務(wù)器，對其剩余資源進(jìn)行判定，假如沒有滿足條件的或沒有已使用的服務(wù)器，則開啟新的服務(wù)器，對其進(jìn)行一次配方生成。如果有多個(gè)滿足條件的服務(wù)器，優(yōu)先選擇這些服務(wù)器與待分配作業(yè)之間時(shí)間平衡指數(shù)小的，對選出的服務(wù)器進(jìn)行二次配方生成，并更新虛擬機(jī)資源池，如果虛擬機(jī)資源池不為空，則重復(fù)上述過程，直至虛擬機(jī)資源池為空，作業(yè)全部完成。在執(zhí)行過程中，如果有作業(yè)完成，則收回虛擬集群資源，更新物理資源表。

4 實(shí)驗(yàn)和分析

本節(jié)將在線時(shí)間平衡算法OTBA與在線裝箱算法OBBA(Online Binning-Based Algorithm)、在線最佳擬合算法OBFA(Online Best-Fit Algorithm)和在線首次擬合算法OFFA(Online First-Fit Algorithm)[10]進(jìn)行對比。在線裝箱放置算法OBBA是基于裝箱算法思想的一種針對在線處理模式的能耗優(yōu)化算法，其主要過程如下：當(dāng)作業(yè)到達(dá)時(shí)，首先對作業(yè)的執(zhí)行時(shí)間進(jìn)行估計(jì)，再將作業(yè)執(zhí)行時(shí)間與非空閑的服務(wù)器的剩余時(shí)間進(jìn)行對比，如果作業(yè)執(zhí)行時(shí)間在服務(wù)器剩余時(shí)間的T范圍之內(nèi)(T為OBBA設(shè)置的時(shí)間間隔)，則對該服務(wù)器進(jìn)行分配，反之則開啟新的服務(wù)器。在線最佳擬合算法OBFA也是一種針對在線處理模式的能耗優(yōu)化算法，其主要過程是：當(dāng)作業(yè)到達(dá)時(shí)，首先挑選出滿足虛擬機(jī)資源分配條件的服務(wù)器，再對挑選出的服務(wù)器按照資源利用率進(jìn)行排序，資源利用率高的服務(wù)器優(yōu)先級高；如果沒有已使用的物理服務(wù)器或無滿足虛擬機(jī)資源分配條件的服務(wù)器，則開啟新的服務(wù)器。在線首次擬合算法OFFA的基本過程與OBFA類似，區(qū)別在于OFFA每次都是從第一臺服務(wù)器開始匹配。

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

為了驗(yàn)證算法的有效性，本文首先設(shè)計(jì)了一個(gè)仿真實(shí)驗(yàn)。算法的仿真框架由Java實(shí)現(xiàn)。本文的仿真框架模擬一個(gè)云數(shù)據(jù)中心，MapReduce作業(yè)隨機(jī)到達(dá)，虛擬機(jī)放置控制器為作業(yè)分配虛擬集群。當(dāng)服務(wù)器上的作業(yè)全部完成時(shí)，其虛擬機(jī)全部關(guān)閉，此時(shí)服務(wù)器調(diào)至休眠狀態(tài)。

在本文的模擬中，假設(shè)數(shù)據(jù)中心有足夠多的服務(wù)器資源，以滿足所有運(yùn)行的MapReduce作業(yè)建立各自所需的虛擬集群，假設(shè)數(shù)據(jù)中心的所有服務(wù)器是同構(gòu)的。云用戶根據(jù)作業(yè)的特點(diǎn)決定所采用虛擬機(jī)的類型，并為每一種作業(yè)制定虛擬機(jī)最小使用量，通過定義輸入數(shù)據(jù)大小和map/reduce函數(shù)來初始化MapReduce作業(yè)。

本文的實(shí)驗(yàn)中，模擬了100個(gè)作業(yè)，其中包含八種類型，如表1所示。每種類型作業(yè)所需要的虛擬機(jī)不同，這些虛擬機(jī)的資源占用情況如表2所示；Input Size代表每種作業(yè)的輸入數(shù)據(jù)大小，從6 GB到20 GB中隨機(jī)選?。籚Mnum代表虛擬機(jī)最小使用量，從8到14的整數(shù)中隨機(jī)選?。籑T代表map任務(wù)時(shí)間，從10 s到30 s中隨機(jī)選取;RT代表reduce任務(wù)時(shí)間，從20 s到40 s中隨機(jī)選??；每種類型的作業(yè)隨機(jī)到達(dá)，即每個(gè)時(shí)刻到達(dá)的作業(yè)類型在八種類型中隨機(jī)獲取，這樣的設(shè)置避免了不同類型的作業(yè)所占比例對實(shí)驗(yàn)結(jié)果的影響；虛擬集群中每個(gè)虛擬結(jié)點(diǎn)的map槽數(shù)為2或4，reduce槽數(shù)為1或2。

Table 1 Job types表1 作業(yè)類型

Table 2 VM types表2 虛擬機(jī)類型

實(shí)驗(yàn)過程如下：作業(yè)到達(dá)時(shí)，記錄其到達(dá)時(shí)刻，分別按四種算法對到達(dá)作業(yè)進(jìn)行虛擬機(jī)分配，根據(jù)需要開啟服務(wù)器并記錄其開啟時(shí)刻以及開啟數(shù)目。作業(yè)完成時(shí)，查看所開啟的服務(wù)器是否還有其他作業(yè)運(yùn)行，如果有，繼續(xù)運(yùn)行；如果沒有，關(guān)閉服務(wù)器，并記錄其關(guān)閉時(shí)刻。服務(wù)器的活躍時(shí)間為服務(wù)器關(guān)閉時(shí)刻減去開啟時(shí)刻。當(dāng)100個(gè)作業(yè)全部完成時(shí)，仿真實(shí)驗(yàn)結(jié)束。

圖1為四種算法的能量消耗圖。如圖1所示，隨著系統(tǒng)中MapReduce作業(yè)的增加，這四種算法的能耗增加。從圖1中可明顯看出，在剛開始的時(shí)候，即作業(yè)剛開始提交時(shí)，四種算法的能耗差異不大，隨著時(shí)間的增加，作業(yè)的提交量增加，四種算法出現(xiàn)差異。OTBA在相同條件下能耗最低，并且作業(yè)越多，OTBA的優(yōu)勢越明顯。在實(shí)驗(yàn)過程中，本文還監(jiān)測到，OTBA的活躍服務(wù)器數(shù)目相對穩(wěn)定并且偏低。這說明，OTBA是四種算法里最節(jié)能并且空間利用率最高的，因?yàn)镺TBA設(shè)置了兩個(gè)機(jī)制，其中一個(gè)與時(shí)間平衡相關(guān)：對剩余資源可用，且時(shí)間平衡度高的服務(wù)器賦予高優(yōu)先級；另一個(gè)機(jī)制與空間利用率相關(guān)：對已使用的服務(wù)器的剩余資源判斷，若剩余資源可用，則定會(huì)對其加以利用，以提高空間利用率

Figure 1 Energy consumption among OTBA,OBBA,OBFA, and OFFA圖1 OTBA、OBBA、OBFA、OFFA能量消耗圖

4.2 Hadoop平臺實(shí)驗(yàn)

為了進(jìn)一步說明虛擬機(jī)分配算法的有效性，本文又在Hadoop平臺上進(jìn)行了一次平臺實(shí)驗(yàn)。本文實(shí)驗(yàn)所使用的服務(wù)器都是同構(gòu)的，服務(wù)器機(jī)器型號為DELL(Xeon E5506/四核心/12 GB/600 GB)，操作系統(tǒng)為Redhat 5.4，Hadoop版本為Hadoop-1.1.0。所有服務(wù)器使用千兆以太網(wǎng)進(jìn)行連接。

在平臺實(shí)驗(yàn)中，本文設(shè)計(jì)了三種不同類型的虛擬機(jī)，其資源占用情況如表3所示。每臺服務(wù)器為每種類型的虛擬機(jī)存儲(chǔ)虛擬機(jī)鏡像，當(dāng)請求該類型的虛擬機(jī)時(shí)，實(shí)例化虛擬機(jī)。本文提供了三種不同類型的作業(yè)：wordcount、sort、terasort。這三個(gè)作業(yè)都是經(jīng)典的MapReduce基準(zhǔn)測試用例，作業(yè)描述如表4所示。

Table 3 VM resources表3 虛擬機(jī)資源占用情況

圖2展示了Hadoop平臺下四種算法的能量消耗。平臺實(shí)驗(yàn)得到了與仿真實(shí)驗(yàn)相同的結(jié)果：剛

Table 4 Job description of MapReduce表4 MapReduce作業(yè)描述

提交作業(yè)時(shí)，四種算法能耗相同，隨著提交作業(yè)的增多，逐漸出現(xiàn)差異。由圖2可知，OTBA為四種算法中能耗最低的。從實(shí)驗(yàn)統(tǒng)計(jì)的服務(wù)器數(shù)目可知，OTBA的服務(wù)器數(shù)目穩(wěn)定，且相對較少。

Figure 2 Energy consumption among OTBA,OBBA,OBFA, and OFFA on Hadoop platform圖2 Hadoop：OTBA、OBBA、OBFA、OFFA能量消耗圖

5 結(jié)束語

本文針對云數(shù)據(jù)中心的能量消耗問題，建立云數(shù)據(jù)中心模型，結(jié)合作業(yè)到達(dá)的隨機(jī)性和排隊(duì)模型建立隨機(jī)作業(yè)模型，分析系統(tǒng)的能量消耗建立能量模型，根據(jù)MapReduce作業(yè)的執(zhí)行特點(diǎn)建立評價(jià)作業(yè)完成質(zhì)量的作業(yè)運(yùn)行模型，最后提出一種在線的虛擬機(jī)分配算法——在線時(shí)間平衡算法OTBA。實(shí)驗(yàn)表明，本文提出的在線時(shí)間平衡算法在保證性能的前提下，能夠大幅降低云數(shù)據(jù)中心的能量消耗，并且減少其活躍服務(wù)器的數(shù)目。本文考慮的云數(shù)據(jù)中心的服務(wù)器都是同構(gòu)的，而現(xiàn)實(shí)的數(shù)據(jù)中心使用的都是廉價(jià)的服務(wù)器，不能保證同構(gòu)。因此，下一步的工作重心是研究異構(gòu)環(huán)境下的在線虛擬機(jī)分配策略。

[1] Beloglazov A, Abawajy J, Buyya R. Energy-aware resource allocation heuristics for efficient management of data centers for cloud computing[J]. Future Generation Computer Systems, 2012, 28(5):755-768.

[2] Chase J S,Anderson D C,Thakar P N, et al. Managing energy and server resources in hosting centers[J]. ACM SIGOPS Operating Systems Review,2001,35(5):103-116.

[3] Dong Jian-kang,Wang Hong-bo.Issa environment to improve energy efficiency and network performance method for virtual machine placement[J].Communications Journal, 2014,34(1):78-81.(in Chinese)

[4] Liu H,Jin H,Xu C-Z, et al. Performance and energy modeling for live migration of virtual machines[J]. Cluster computing, 2013, 16(2):249-264.

[5] Wirtz T, Ge R. Improving MapReduce energy efficiency for computation intensive workloads[C]∥Proc of the IEEE International Green Computing Conference and Workshops (IGCC),2011:1-8.

[6] Xie R,Jia X,Yang K,et al. Energy saving virtual machine allocation in cloud computing[C]∥Proc of the IEEE 33rd International Conference on Distributed Computing Systems Workshops (ICDCSW), 2013:132-137.

[7] Leverich J, Kozyrakis C. On the energy inefficiency of Hadoop clusters[J]. ACM SIGOPS Operating Systems Review, 2010, 44(1):61-65.

[8] Li Qiang, Hao Qin-fen, Xiao Li-min, et al. Adaptive management and multi-objective optimization for virtual machine placement in cloud computing[J]. Chinese Journal of Computer, 2011,34(12):2253-2264.(in Chinese)

[9] Teng Fei, Deng Dan-ting, Yu Lei, et al. An energy-efficient VM placement in cloud datacenter[C]∥Proc of 2014 IEEE International Conference on High Performance Computing and Communications (HPCC), 2014:173-180.

[10] Cardosa M, Singh A,Pucha H,et al.Exploiting spatiotemporal tradeoffs for energy-aware MapReduce in the cloud[J].IEEE Transactions on Computers,2012,61(12):1737-1751.

附中文參考文獻(xiàn):

[3] 董建康, 王洪波. Issa環(huán)境下改進(jìn)能源效率和網(wǎng)絡(luò)性能的虛擬機(jī)放置方法[J]. 通信學(xué)報(bào), 2014, 34(1):71-81.

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

DENGDan-ting,born in 1990,MS candidate,her research interest includes cloud computing scheduling.

滕飛(1984),女，山東泰安人，博士，講師，CCF會(huì)員(E200030587M)，研究方向?yàn)樵朴?jì)算、并行計(jì)算和工作流調(diào)度。E-mail:fteng@swjtu.edu.cn

TENGFei,born in 1984,PhD,lecturer，CCF member(E200030587M)，her research interests include cloud computing,parallel computing, and workflow scheduling.

Anenergy-savingalgorithmforMapReduce-basedvirtualcluster

DENG Dan-ting1,TENG Fei1,2,LI Tian-rui1,YANG Hao1

(1.School of Information Science and Technology,Southwest Jiaotong University,Chengdu 610031;2.State key Laboratory for Novel Software Technology,Nanjing University,Nanjing 210023,China)

In the global energy crisis, many researchers begin to pay close attention to the problem of data centers’ energy consumption. On the premise of meeting the users’ demand, reducing the active nodes of adata center can effectively reduce the whole energy consumption. Virtual machine migration is a traditional way to reduce active nodes, but causes huge system cost. An energy-saving algorithm for MapReduce-based virtual cluster, named Online Time Balance Algorithm (OTBA), is proposed. The proposed algorithm can reduce the number of active physical nodes, reduce the energy consumption effectively, and avoid migrating the virtual machines. The objective function and the variable factors are determined by building the energy consumption model, the queue model and the MapReduce performance model. Since OTBA is based on virtual cloud environment and online MapReduce, it can make a tradeoff between the runtime of virtual machines and the resource utilization so as to minimize the number of the activated physical servers in the data center and the energy consumption. At last, the algorithm is validated through experiments in simulation environment and on Hadoop platform.

energy efficiency;VM placement;online;MapReduce;cloud computing

1007-130X(2014)11-2054-07

2014-06-10;

：2014-08-21

國家自然科學(xué)基金資助項(xiàng)目(61202043);網(wǎng)絡(luò)智能信息處理四川省高校重點(diǎn)實(shí)驗(yàn)室開放課題資助項(xiàng)目(SZJJ2014-049)

TP393.027

：A

10.3969/j.issn.1007-130X.2014.11.002

鄧聃婷(1990),女，四川成都人，碩士生，研究方向?yàn)樵朴?jì)算調(diào)度。E-mail:dengdanting5@163.com

通信地址：610031 四川省成都市二環(huán)路北一段111號西南交通大學(xué)信息科學(xué)與技術(shù)學(xué)院

Address:School of Information Science and Technology,Southwest Jiaotong University,Chengdu 610031,Sichuan,P.R.China