廖 彬，張 陶，于 炯，劉 繼，鐘 磊，劉 炎

(1.新疆財(cái)經(jīng)大學(xué)統(tǒng)計(jì)與信息學(xué)院，新疆 烏魯木齊 830012； 2. 新疆大學(xué)軟件學(xué)院，新疆 烏魯木齊 830008； 3. 新疆醫(yī)科大學(xué)醫(yī)學(xué)工程技術(shù)學(xué)院, 新疆 烏魯木齊 830011； 4.清華大學(xué)軟件學(xué)院, 北京 100084)

?

適應(yīng)節(jié)能與異構(gòu)環(huán)境的MapReduce數(shù)據(jù)布局策略*

廖 彬1,2，張 陶3，于 炯2，劉 繼1，鐘 磊1，劉 炎4

(1.新疆財(cái)經(jīng)大學(xué)統(tǒng)計(jì)與信息學(xué)院，新疆 烏魯木齊 830012； 2. 新疆大學(xué)軟件學(xué)院，新疆 烏魯木齊 830008； 3. 新疆醫(yī)科大學(xué)醫(yī)學(xué)工程技術(shù)學(xué)院, 新疆 烏魯木齊 830011； 4.清華大學(xué)軟件學(xué)院, 北京 100084)

大數(shù)據(jù)處理過程中產(chǎn)生的高能耗問題亟待解決，尤其是在數(shù)據(jù)量規(guī)模劇增的背景下。在對(duì)已有數(shù)據(jù)布局策略存在問題分析的基礎(chǔ)上，分析了與基于存儲(chǔ)區(qū)域劃分的節(jié)能模式及與異構(gòu)HDFS集群的不適應(yīng)、數(shù)據(jù)塊切分算法不靈活、存儲(chǔ)節(jié)點(diǎn)選擇的隨機(jī)性等幾個(gè)方面的問題，繼而提出面向節(jié)能的MapReduce數(shù)據(jù)布局策略。首先，新策略適應(yīng)將集群劃分為不同存儲(chǔ)區(qū)域(Active-Zone與Sleep-Zone)的節(jié)能模式；其次，新策略對(duì)傳統(tǒng)的數(shù)據(jù)塊數(shù)計(jì)算方法進(jìn)行了改進(jìn)，提出作業(yè)截止時(shí)間約束下的最小任務(wù)數(shù)計(jì)算方法確定數(shù)據(jù)塊數(shù)量；最后，新的存儲(chǔ)策略增加了對(duì)異構(gòu)集群環(huán)境的適應(yīng)能力，并能根據(jù)不同的作業(yè)類型進(jìn)行存儲(chǔ)節(jié)點(diǎn)的選擇。實(shí)驗(yàn)結(jié)果表明：新的數(shù)據(jù)布局策略能夠適應(yīng)異構(gòu)集群環(huán)境，達(dá)到減小MapReduce作業(yè)能耗的目的。

綠色計(jì)算;MapReduce;異構(gòu)環(huán)境; 數(shù)據(jù)布局

隨著云計(jì)算、物聯(lián)網(wǎng)、移動(dòng)互聯(lián)網(wǎng)等技術(shù)的不斷發(fā)展，數(shù)據(jù)正以前所未有的速度在不斷增長(zhǎng)和積累。數(shù)據(jù)從簡(jiǎn)單的處理對(duì)象開始轉(zhuǎn)變?yōu)橐环N基礎(chǔ)性資源，如何更好地管理和利用大數(shù)據(jù)已經(jīng)成為普遍關(guān)注的話題，同時(shí)大數(shù)據(jù)的規(guī)模效應(yīng)給數(shù)據(jù)存儲(chǔ)、管理以及數(shù)據(jù)分析帶來了極大的挑戰(zhàn)[1]。MapReduce是最流行的大數(shù)據(jù)計(jì)算模式[2]，而MapReduce對(duì)大數(shù)據(jù)的分析與處理離不開底層的分布存儲(chǔ)系統(tǒng)提供的數(shù)據(jù)存儲(chǔ)服務(wù)，目前比較著名的分布存儲(chǔ)系統(tǒng)有Google的GFS (Google File System, 谷歌分布式文件系統(tǒng))[3], HDFS (Hadoop Distributed File System, Hadoop分布式文件系統(tǒng))[4]、Lustre、MooseFs以及清華大學(xué)自主研發(fā)的CarrierFs等。其中GFS管理著Google公司百萬服務(wù)器上的海量數(shù)據(jù),基于GFS的分布式數(shù)據(jù)庫(kù)BigTable支撐著Google搜索、地圖、社交網(wǎng)絡(luò)等服務(wù)[5]。HDFS作為Hadoop底層分布式文件系統(tǒng)，由于能夠部署在通用平臺(tái)上，并且具有可擴(kuò)展性(Scalable)、低成本(Economical)、高效性(Efficient)與可靠性(Reliable)等優(yōu)點(diǎn)使其在分布式計(jì)算領(lǐng)域得到了廣泛運(yùn)用，并且已逐漸成為工業(yè)與學(xué)術(shù)屆事實(shí)上的海量數(shù)據(jù)并行處理標(biāo)準(zhǔn)[6]。

據(jù)文獻(xiàn)[7]統(tǒng)計(jì)，2007年全球數(shù)據(jù)量達(dá)到281 EB，而2007年到2011年這5年時(shí)間內(nèi)，全球數(shù)據(jù)量增長(zhǎng)了10倍。數(shù)據(jù)量的高速增長(zhǎng)伴隨而來的是存儲(chǔ)系統(tǒng)規(guī)模的不斷擴(kuò)大，這使得運(yùn)營(yíng)成本不斷的提高，其成本不僅包括硬件、機(jī)房、冷卻設(shè)備等固定成本，還包括IT設(shè)備與冷卻設(shè)備的電能消耗等其它開銷。并且，系統(tǒng)的高能耗將導(dǎo)致過量溫室氣體的排放并引發(fā)環(huán)境問題。據(jù)文獻(xiàn)[8]統(tǒng)計(jì),目前IT領(lǐng)域的二氧化碳排放量占全球的2%，而到2020年這一比例將翻番。2008年路由器、交換機(jī)、服務(wù)器、冷卻設(shè)備、數(shù)據(jù)中心等互聯(lián)網(wǎng)設(shè)備總共消耗8 680億度電,占全球總耗電量的5.3%。紐約時(shí)報(bào)與麥肯錫經(jīng)在《紐約時(shí)報(bào)》上發(fā)表了“Power, pollution and the Internet”[9],調(diào)查顯示全球的數(shù)據(jù)中心總用電量約為3 000億W，相當(dāng)于30座核電廠的出電量，而巨大的能耗中卻只有6%～12%的能耗被用于相應(yīng)用戶的請(qǐng)求。事實(shí)上，在能源價(jià)格上漲、數(shù)據(jù)中心存儲(chǔ)規(guī)模不斷擴(kuò)大的今天，高能耗已逐漸成為制約大數(shù)據(jù)快速發(fā)展的一個(gè)主要瓶頸[1]。

已有對(duì)MapReduce的數(shù)據(jù)布局研究工作的目的大多以提高M(jìn)apReduce作業(yè)的執(zhí)行效率為首要目標(biāo)，并沒有考慮到能耗因素。本文在對(duì)已有數(shù)據(jù)布局策略深入研究的基礎(chǔ)上，總結(jié)了與基于存儲(chǔ)區(qū)域劃分的節(jié)能模式及與異構(gòu)HDFS集群的不適應(yīng)、數(shù)據(jù)塊切分算法不靈活、存儲(chǔ)節(jié)點(diǎn)選擇的隨機(jī)性等幾個(gè)方面的問題；針對(duì)以上問題分別提出了對(duì)應(yīng)的解決方案。

1 相關(guān)工作

從2012 -2014 年Gartner 公布的技術(shù)發(fā)展趨勢(shì)報(bào)告中可以看出，綠色I(xiàn)T 技術(shù)已經(jīng)成為十大IT關(guān)鍵技術(shù)之一。通過優(yōu)化數(shù)據(jù)布局策略提升系統(tǒng)能耗效率屬于節(jié)能的分布式存儲(chǔ)系統(tǒng)研究方向之一。所以，本文首先將分布式存儲(chǔ)系統(tǒng)的節(jié)能研究進(jìn)行簡(jiǎn)要介紹，繼而針對(duì)具體的數(shù)據(jù)布局相關(guān)工作進(jìn)行闡述。

將分布存儲(chǔ)系統(tǒng)中的能耗優(yōu)化問題根據(jù)研究?jī)?nèi)容進(jìn)行劃分，可分為基于硬件的節(jié)能與基于調(diào)度的節(jié)能兩個(gè)方面[10]?；谟布墓?jié)能方法主要通過低能耗高效率的硬件設(shè)備或體系結(jié)構(gòu)，對(duì)現(xiàn)有的高能耗存儲(chǔ)設(shè)備進(jìn)行替換，從而達(dá)到節(jié)能的目的。基于硬件的節(jié)能方法效果立竿見影，且不需要復(fù)雜的能耗管理組件;但是對(duì)于已經(jīng)部署的大規(guī)模應(yīng)用系統(tǒng)，大批量的硬件替換面臨成本過高的問題。基于調(diào)度的節(jié)能通過對(duì)存儲(chǔ)資源的有效調(diào)度，在不影響系統(tǒng)性能的前提條件下將部分存儲(chǔ)節(jié)點(diǎn)調(diào)整到低能耗模式(如:休眠、降頻等)，以達(dá)到節(jié)能的目的。由于不需要對(duì)現(xiàn)有硬件體系進(jìn)行改變，基于調(diào)度的節(jié)能方法是目前分布式存儲(chǔ)節(jié)能技術(shù)的研究熱點(diǎn)。當(dāng)前，基于調(diào)度的節(jié)能研究主要集中在基于節(jié)點(diǎn)調(diào)度與數(shù)據(jù)調(diào)度兩方面。節(jié)點(diǎn)調(diào)度主要研究如何選擇存儲(chǔ)系統(tǒng)中的部分節(jié)點(diǎn)或磁盤為上層應(yīng)用提供數(shù)據(jù)服務(wù)，并讓其它節(jié)點(diǎn)進(jìn)入低能耗模式以達(dá)到降低能耗的目的。節(jié)點(diǎn)調(diào)度中被關(guān)閉節(jié)點(diǎn)的選擇與數(shù)據(jù)調(diào)度技術(shù)緊密相關(guān)，而目前已有的數(shù)據(jù)調(diào)度技術(shù)主要有基于靜態(tài)數(shù)據(jù)放置、動(dòng)態(tài)數(shù)據(jù)放置與緩存預(yù)取三種。其中基于靜態(tài)數(shù)據(jù)放置的數(shù)據(jù)調(diào)度根據(jù)固定的數(shù)據(jù)放置策略將數(shù)據(jù)存儲(chǔ)到系統(tǒng)中各節(jié)點(diǎn)上后，將不再改變其存儲(chǔ)結(jié)構(gòu)[11-15]?；趧?dòng)態(tài)數(shù)據(jù)放置的數(shù)據(jù)調(diào)度根據(jù)數(shù)據(jù)訪問頻度動(dòng)態(tài)調(diào)整數(shù)據(jù)存放的位置，將訪問頻度高與頻度低的數(shù)據(jù)遷移到不同磁盤上，對(duì)存儲(chǔ)低頻度數(shù)據(jù)的磁盤進(jìn)行節(jié)能處理以降低系統(tǒng)能耗[16-20]?；诰彺骖A(yù)取的數(shù)據(jù)調(diào)度借鑒內(nèi)存中的數(shù)據(jù)緩存思想，將磁盤中的數(shù)據(jù)取到內(nèi)存或其他低能耗輔助存儲(chǔ)設(shè)備并使原磁盤進(jìn)入低能耗模式以此達(dá)到節(jié)能的目的[21]。

研究MapReduce數(shù)據(jù)布局策略方面，已有工作主要有CoHadoop、Hadoop++及CHMJ[22-25]。CoHadoop解決了Hadoop無法把與作業(yè)相關(guān)的數(shù)據(jù)定位到同一個(gè)節(jié)點(diǎn)集合下的性能瓶頸，是對(duì)Hadoop的輕量級(jí)擴(kuò)展，目的是使得應(yīng)用層能控制數(shù)據(jù)的存儲(chǔ)。CoHadoop提高了索引(Indexing)、聚合(Grouping)、聚集(Aggregation)、縱向存儲(chǔ)(Columnar Storage)、合并(join)以及Sessionization等操作的效率。Hadoop++改進(jìn)思路與CoHadoop類似，它將同一個(gè)作業(yè)產(chǎn)生的兩個(gè)數(shù)據(jù)文件放置在一起；但是當(dāng)有新文件寫入系統(tǒng)的時(shí)，系統(tǒng)需要對(duì)數(shù)據(jù)進(jìn)行重新組織。CHMJ設(shè)計(jì)了多副本一致性哈希算法,將具有連接關(guān)系的表根據(jù)其連接屬性的哈希值在機(jī)群中進(jìn)行分布，在提升連接查詢處理中數(shù)據(jù)本地性的同時(shí),也保證了數(shù)據(jù)的可用性。并且，CHMJ在多副本一致性哈希數(shù)據(jù)分布的基礎(chǔ)上，提出了HashMapJoin 并行連接查詢處理算法，有效地提高了連接查詢的處理效率。以上對(duì)MapReduce的數(shù)據(jù)布局研究工作的目的都是以提高M(jìn)apReduce作業(yè)的執(zhí)行效率為首要目標(biāo)，并沒有考慮到能耗因素，這是本文與已有工作的最大不同之處，針對(duì)已有布局策略有可能導(dǎo)致的能耗問題，本文在第3章進(jìn)行了詳細(xì)闡述。本文研究節(jié)能的MapReduce數(shù)據(jù)布局策略，主要做了如下幾個(gè)方面的工作。

1) 歸納分析了已有的數(shù)據(jù)布局策略存在：不適應(yīng)基于存儲(chǔ)區(qū)域劃分的節(jié)能模式及異構(gòu)的HDFS集群環(huán)境，數(shù)據(jù)塊切分算法缺乏靈活性，存儲(chǔ)節(jié)點(diǎn)選擇的存在隨機(jī)性等問題。

2) 通過返回節(jié)點(diǎn)狀態(tài)矩陣中處于活動(dòng)狀態(tài)的節(jié)點(diǎn)，對(duì)通過將RACK劃分為Active-Zone與Sleep-Zone存儲(chǔ)區(qū)域的節(jié)能模式進(jìn)行了適應(yīng)。

3) 當(dāng)作業(yè)具有截止時(shí)間約束時(shí)，通過對(duì)MapReduce計(jì)算原理及公式的推導(dǎo)，得到了任務(wù)截止時(shí)間約束下的最小任務(wù)計(jì)算方法，從而可以有效的確定數(shù)據(jù)布局前的數(shù)據(jù)塊的切分?jǐn)?shù)量(即Map任務(wù)的數(shù)量)。

4) 已有方法采用平均主義及隨機(jī)方法確定數(shù)據(jù)塊的大小及存儲(chǔ)位置，不能很好的適應(yīng)異構(gòu)集群及不同MapReduce作業(yè)的特點(diǎn)。異構(gòu)集群環(huán)境下，本文對(duì)各異構(gòu)節(jié)點(diǎn)執(zhí)行不同MapReduce作業(yè)類型的計(jì)算能力進(jìn)行評(píng)估，提出了適應(yīng)異構(gòu)集群的數(shù)據(jù)塊大小切分方法及適應(yīng)不同作業(yè)類型的存儲(chǔ)節(jié)點(diǎn)選擇方法。

2 已有數(shù)據(jù)布局策略存在的問題

MapReduce任務(wù)執(zhí)行前首先要將任務(wù)處理的數(shù)據(jù)存儲(chǔ)到HDFS中，HDFS提供了分布、高效的數(shù)據(jù)存儲(chǔ)及訪問能力。數(shù)據(jù)文件被切分成固定大小的數(shù)據(jù)塊(Data Block)分布的存儲(chǔ)到DataNode節(jié)點(diǎn)中，其中數(shù)據(jù)塊的大小是可配置的(默認(rèn)大小為64 MB)。HDFS中數(shù)據(jù)文件只能一次寫入，并不允許對(duì)已經(jīng)寫入的數(shù)據(jù)塊進(jìn)行修改。NameNode節(jié)點(diǎn)內(nèi)存中維護(hù)著文件系統(tǒng)的目錄信息，即維護(hù)著活動(dòng)的DataNode節(jié)點(diǎn)列表及每個(gè)DataNode節(jié)點(diǎn)中所有的數(shù)據(jù)塊信息(BlockMap)。HDFS通過副本機(jī)制達(dá)到容錯(cuò)及故障恢復(fù)的目的，系統(tǒng)默認(rèn)副本系數(shù)為3，并采用基于機(jī)架感知的數(shù)據(jù)塊存儲(chǔ)策略 (如圖1所示)將數(shù)據(jù)塊布局到HDFS系統(tǒng)中[26]。

圖1 基于機(jī)架感知的數(shù)據(jù)塊存儲(chǔ)策略Fig.1 The rack-aware block replica placement policy in HDFS

機(jī)架感知的數(shù)據(jù)塊存儲(chǔ)策略首先將數(shù)據(jù)塊的第1個(gè)副本存放在創(chuàng)建該數(shù)據(jù)塊的本地DataNode上(前提條件是本地DataNode節(jié)點(diǎn)空間足夠)，此策略叫就近寫(Write Affinity)；第2個(gè)副本會(huì)被存儲(chǔ)到同第1個(gè)副本不同機(jī)架(Rack)的DataNode上；第3個(gè)副本會(huì)被存儲(chǔ)到同第2個(gè)副本同機(jī)架但不同DataNode的節(jié)點(diǎn)中。由此可見，基于機(jī)架感知的數(shù)據(jù)塊存儲(chǔ)策略使得數(shù)據(jù)塊的存儲(chǔ)位置具有較大的隨機(jī)性[27]，這種隨機(jī)的布局策略雖然能夠均衡系統(tǒng)的負(fù)載，但是同樣存在以下幾個(gè)方面的問題。

2.1 與基于存儲(chǔ)區(qū)域劃分的節(jié)能模式的不適應(yīng)

文獻(xiàn)[27]中將存儲(chǔ)區(qū)域劃分為Active-Zone與Sleep-Zone，并適時(shí)的將Sleep-Zone中的節(jié)點(diǎn)進(jìn)行休眠處理以達(dá)到節(jié)能的目的，基于機(jī)架感知的數(shù)據(jù)塊存儲(chǔ)策略在進(jìn)行數(shù)據(jù)布局時(shí)并沒有對(duì)節(jié)點(diǎn)的區(qū)域(Active-Zone與Sleep-Zone)進(jìn)行區(qū)分對(duì)待，致使不能很好的適應(yīng)節(jié)能模式的需求。

2.2 與異構(gòu)HDFS集群的不適應(yīng)

現(xiàn)有的數(shù)據(jù)放置策略并沒有考慮到系統(tǒng)中數(shù)據(jù)存儲(chǔ)節(jié)點(diǎn)的異構(gòu)性問題，基于機(jī)架感知的數(shù)據(jù)塊存儲(chǔ)策略認(rèn)為HDFS集群中所有節(jié)點(diǎn)的服務(wù)能力相同，數(shù)據(jù)按照平均主義的原則進(jìn)行切分、布局。在這種布局策略下，服務(wù)能力強(qiáng)的節(jié)點(diǎn)能夠較早的完成任務(wù)，而服務(wù)能力較弱的節(jié)點(diǎn)則需要較長(zhǎng)的時(shí)間完成任務(wù)，將引發(fā)以下兩種情況：第一，當(dāng)快任務(wù)能夠容忍慢任務(wù)時(shí)，將造成“任務(wù)等待”，即早完成的任務(wù)等待還未完成的任務(wù)。第二，當(dāng)塊任務(wù)不能容忍慢任務(wù)時(shí)，將引發(fā)Hadoop的推測(cè)執(zhí)行(Speculative Execution)機(jī)制，推測(cè)執(zhí)行機(jī)制是為了防止運(yùn)行速度慢的任務(wù)影響作業(yè)的整體執(zhí)行速度，根據(jù)推測(cè)算法推測(cè)出“拖后腿”的任務(wù)，并為該任務(wù)啟動(dòng)一個(gè)備份任務(wù)，并最終選用最先成功運(yùn)行完成任務(wù)的計(jì)算結(jié)果作為最終結(jié)果。由此可見，不論是那種情況，都會(huì)造成資源的浪費(fèi)。

2.3 數(shù)據(jù)塊切分算法不靈活

Hadoop中利用類InputFormats來定義文件是如何被切分并由Map任務(wù)使用，InputFormats為用戶提供了一種擴(kuò)展的手段，用來通過組裝定制化的分片來將一些分布的數(shù)據(jù)提供給Map任務(wù)。當(dāng)任意MapReduce任務(wù)啟動(dòng)的時(shí)，數(shù)據(jù)文件會(huì)被InputFormats切分為多個(gè)分片(splits)，每一個(gè)分片對(duì)應(yīng)了MapReduce程序中的一個(gè)Map任務(wù)。默認(rèn)情況下，不同的FileInputFormat實(shí)現(xiàn)將一個(gè)文件分成64 MB的chunk(HDFS的默認(rèn)塊大小)。Hadoop調(diào)度器盡量將Map任務(wù)調(diào)度給那些包含分片的本地副本的Datanode。大多數(shù)情況下，split與block呈一一對(duì)應(yīng)關(guān)系，數(shù)據(jù)塊block與split對(duì)應(yīng)關(guān)系如圖2所示。

圖2 數(shù)據(jù)塊block與split之間的對(duì)應(yīng)關(guān)系Fig.2 The relationship between data block and split

已有的數(shù)據(jù)塊大小只能由固定的配置參數(shù)進(jìn)行設(shè)置，并不能很好的適應(yīng)不同MapReduce任務(wù)的特點(diǎn)，更不能根據(jù)作業(yè)的完成時(shí)間需求及集群中各節(jié)點(diǎn)的計(jì)算能力的不同而進(jìn)行靈活的設(shè)置。

2.4 存儲(chǔ)節(jié)點(diǎn)選擇的隨機(jī)性

基于機(jī)架感知的數(shù)據(jù)塊存儲(chǔ)策略在選擇存儲(chǔ)節(jié)點(diǎn)時(shí)具有較大的隨機(jī)性，不能很好的進(jìn)行作業(yè)類型與節(jié)點(diǎn)類型之間的匹配。一方面，不同MapReduce作業(yè)對(duì)CPU、內(nèi)存、磁盤、網(wǎng)絡(luò)等資源的需求不同，而異構(gòu)HDFS集群環(huán)境下不同節(jié)點(diǎn)之間的CPU、內(nèi)存、磁盤、網(wǎng)絡(luò)等資源的服務(wù)能力不盡相同；另一方面，MapReduce作業(yè)調(diào)度時(shí)的本地優(yōu)先策略容易導(dǎo)致部分任務(wù)在不合適的節(jié)點(diǎn)上執(zhí)行(由存儲(chǔ)節(jié)點(diǎn)選擇的隨機(jī)性造成)，從而影響作業(yè)的整體進(jìn)程。由此可見，必須為不同的MapReduce作業(yè)類型所處理的數(shù)據(jù)選擇合適的存儲(chǔ)節(jié)點(diǎn)，是適應(yīng)節(jié)能的數(shù)據(jù)布局算法必須考慮的問題。

針對(duì)以上問題，本文第3節(jié)提出面向節(jié)能的MapReduce數(shù)據(jù)布局算法對(duì)問題予以解決。

3 面向節(jié)能的MapReduce數(shù)據(jù)布局策略

3.1 面向節(jié)能的數(shù)據(jù)布局策略總體流程

如圖3所示為面向節(jié)能的MapReduce數(shù)據(jù)布局策略流程圖。

圖3 面向節(jié)能的MapReduce數(shù)據(jù)布局策略流程圖Fig.3 The flow chart for energy saving MapReduce data layout strategy

首先，判斷是否處在節(jié)能模式；如果處于節(jié)能模式，則接著判斷存儲(chǔ)區(qū)域的劃分狀態(tài)；如果不處于節(jié)能模式，則采用基于機(jī)架感知的數(shù)據(jù)布局策略進(jìn)行數(shù)據(jù)的存儲(chǔ)。當(dāng)處于節(jié)能存儲(chǔ)區(qū)域劃分模式時(shí)，返回Active-Zone區(qū)域中存儲(chǔ)節(jié)點(diǎn)(參見3.2節(jié))；否則，返回集群中所有節(jié)點(diǎn)。當(dāng)作業(yè)具有截止時(shí)間約束時(shí)，通過3.3節(jié)中提出的任務(wù)截止時(shí)間約束下的最小任務(wù)計(jì)算方法確定數(shù)據(jù)塊的切分?jǐn)?shù)量；否則，按照系統(tǒng)配置參數(shù)確定數(shù)據(jù)塊數(shù)。當(dāng)系統(tǒng)為異構(gòu)集群時(shí)，通過3.4節(jié)中提出的適應(yīng)異構(gòu)集群的數(shù)據(jù)大小切分方法確定具體數(shù)據(jù)塊的大??；如果系統(tǒng)為同構(gòu)集群，數(shù)據(jù)塊的大小由系統(tǒng)參數(shù)配置確定。最后，數(shù)據(jù)塊的存儲(chǔ)節(jié)點(diǎn)根據(jù)3.5節(jié)適應(yīng)不同作業(yè)類型的節(jié)點(diǎn)選擇算法進(jìn)行確定。

3.2 支持節(jié)能存儲(chǔ)區(qū)域劃分的數(shù)據(jù)布局

我們的早期工作[27]將RACK劃分為Active-Zone與Sleep-Zone兩個(gè)存儲(chǔ)區(qū)域，根據(jù)不同數(shù)據(jù)的訪問頻率與規(guī)律計(jì)算活動(dòng)因子以配置數(shù)據(jù)的存儲(chǔ)區(qū)域，通過數(shù)據(jù)中心負(fù)載規(guī)律適時(shí)對(duì)Sleep-Zone區(qū)域中的服務(wù)器進(jìn)行休眠處理以達(dá)到節(jié)能的目的。基于機(jī)架感知的數(shù)據(jù)塊存儲(chǔ)策略在進(jìn)行數(shù)據(jù)布局時(shí)并沒有對(duì)節(jié)點(diǎn)的區(qū)域(Active-Zone與Sleep-Zone)進(jìn)行區(qū)分對(duì)待，致使不能很好的適應(yīng)節(jié)能模式的需求。在通過劃分Active-Zone與Sleep-Zone存儲(chǔ)區(qū)域節(jié)能模式下，不是所有的節(jié)點(diǎn)都處于可用狀態(tài)，必須返回處于活動(dòng)狀態(tài)的節(jié)點(diǎn)，即返回節(jié)點(diǎn)狀態(tài)矩陣[27](式1)中Smn=1(1≤m≤sm,1≤n≤i)的節(jié)點(diǎn)[27]

(1)

3.3 作業(yè)截止時(shí)間約束下的最小任務(wù)數(shù)

通過4.2節(jié)任務(wù)數(shù)對(duì)任務(wù)完成時(shí)間及能耗的影響實(shí)驗(yàn)我們發(fā)現(xiàn)：首先，理論上任務(wù)數(shù)越大作業(yè)完成時(shí)間越小，但實(shí)際上任務(wù)數(shù)目與任務(wù)完成時(shí)間之間并不呈線性關(guān)系。當(dāng)任務(wù)數(shù)量增加到某臨界點(diǎn)時(shí)，作業(yè)完成時(shí)間并不會(huì)因?yàn)槿蝿?wù)數(shù)量的增加而減小；其次，隨著任務(wù)數(shù)量的不斷增大，作業(yè)能耗不斷的增加；即完成相同作業(yè)，任務(wù)數(shù)越大，完成該任務(wù)能耗越大。由于MapReduce作業(yè)大多受到任務(wù)完成時(shí)間的約束，所以本節(jié)主要對(duì)滿足作業(yè)截止時(shí)間約束下的MapReduce作業(yè)最小分解任務(wù)數(shù)進(jìn)行建模，試圖通過減小任務(wù)數(shù)量達(dá)到節(jié)能的目的。

設(shè)某MapReduce作業(yè)J被初始化為NM個(gè)Map任務(wù)與NR個(gè)Reduce任務(wù)，并且這些任務(wù)在擁有RM個(gè)Map任務(wù)執(zhí)行資源(mapslot)與RR個(gè)Reduce任務(wù)執(zhí)行資源(reduceslot)的集群中運(yùn)行。在數(shù)據(jù)量大小與節(jié)點(diǎn)計(jì)算能力確定的情況下，能夠通過表1對(duì)Map任務(wù)完成時(shí)間進(jìn)行預(yù)測(cè)，但由于MapReduce任務(wù)由Map階段，Shuffle&Sort階段與Reduce階段組成，Shuffle&Sort階段與Reduce階段的任務(wù)完成時(shí)間無法進(jìn)行直接計(jì)算。所以，下面通過任務(wù)采樣的方法來預(yù)測(cè)作業(yè)J的完成時(shí)間，其主要步驟如下：

(2)

(3)

4)記錄每個(gè)采樣Reduce任務(wù)j的完成時(shí)間TR(j)與處理數(shù)據(jù)量大小DR(j)。利用得到的采樣數(shù)據(jù)建立Reduce任務(wù)輸入數(shù)據(jù)量與完成時(shí)間的函數(shù)關(guān)系

(4)

其中，式(2)-(4)中的C表示任意節(jié)點(diǎn)dnij處理作業(yè)J時(shí)的計(jì)算能力(其值可通過訓(xùn)練獲得)。

5)計(jì)算Map階段的采樣任務(wù)平均完成時(shí)間為

(5)

6)計(jì)算Shuffle&Sort階段的采樣任務(wù)平均完成時(shí)間為

(6)

7)計(jì)算Reduce階段的采樣任務(wù)平均完成時(shí)間為

(7)

基于采樣任務(wù)的運(yùn)行結(jié)果，可預(yù)測(cè)作業(yè)J在Map階段的平均完成時(shí)間為

(8)

同樣方法，可預(yù)測(cè)Reduce階段(包含Shuffle&Sort階段)任務(wù)的平均完成時(shí)間為

(9)

值得注意的是，由于作業(yè)J在集群中運(yùn)行Shuffle&Sort的第一次操作與Map階段有重疊部分，所以式(8)中減去了重疊部分的時(shí)間。

設(shè)Tavg表示作業(yè)J的總完成時(shí)間，在式(8)與式(9)的基礎(chǔ)上，總完成時(shí)間可用式(10)進(jìn)行計(jì)算

(10)

對(duì)式(10)進(jìn)行變換，可得到式(11)

(11)

(12)

本文提出截止時(shí)間約束下的最小資源分配的計(jì)算方法，即是RM與RR值最小，通過最優(yōu)化的辦法，建立最優(yōu)化目標(biāo)函數(shù)為

(13)

利用拉格朗日乘數(shù)法求函數(shù)f(RM,RR)最小值為

(14)

(15)

由于MapReduce作業(yè)的類型是有限的，相同類型的作業(yè)Map、Shuffle&Sort與Reduce的數(shù)據(jù)量與完成時(shí)間的函數(shù)(式(5)-(7))相同。所以對(duì)于相同類型的MapReduce作業(yè)，函數(shù)式(5)-(7)具有可重用性。即通過大量的訓(xùn)練與測(cè)試，可確定不同類型作業(yè)的處理數(shù)據(jù)量與完成時(shí)間之間的函數(shù)關(guān)系。再則，通過3.4節(jié)的方法可確定任意節(jié)點(diǎn)dni的處理作業(yè)J時(shí)的計(jì)算能力。所以，式(15)可解。同樣，當(dāng)參數(shù)RM與RR值已知時(shí)，可利用式(15)確定參數(shù)NM與NR的值，即當(dāng)可用Map資源slot及Reduce資源slot數(shù)已知的情況下，可對(duì)滿足作業(yè)完成時(shí)間deadline約束條件下的最小Map任務(wù)數(shù)及Reduce任務(wù)數(shù)進(jìn)行計(jì)算。而本文中則主要取Map任務(wù)數(shù)的值，因?yàn)镸ap任務(wù)數(shù)決定了數(shù)據(jù)布局過程中數(shù)據(jù)塊的數(shù)量。

3.4 適應(yīng)異構(gòu)集群的數(shù)據(jù)大小切分

異構(gòu)環(huán)境中的數(shù)據(jù)放置策略應(yīng)當(dāng)適應(yīng)不同節(jié)點(diǎn)的計(jì)算能力之間的差異，數(shù)據(jù)塊的大小應(yīng)與存儲(chǔ)該數(shù)據(jù)塊節(jié)點(diǎn)的數(shù)據(jù)處理能力成正比。這樣的數(shù)據(jù)塊切分原則可以有效的解決異構(gòu)集群中各個(gè)節(jié)點(diǎn)處理能力的差異性問題，保證同一個(gè)作業(yè)的多個(gè)并行數(shù)據(jù)處理任務(wù)盡量在相同的時(shí)間內(nèi)完成，在有效地縮短等待時(shí)延的同時(shí)，減小“MapReduce任務(wù)等待能耗”。

設(shè)Cij表示節(jié)點(diǎn)dni處理任務(wù)taskj時(shí)的計(jì)算能力，那么Cij可表示為

(16)

其中Timeij表示節(jié)點(diǎn)dni完成任務(wù)taskj所花的時(shí)間，DataVolij表示任務(wù)所處理數(shù)據(jù)量的大小。不論是異構(gòu)還是同構(gòu)Hadoop集群，集群每個(gè)節(jié)點(diǎn)對(duì)于不同作業(yè)類型的計(jì)算能力可通過大量的訓(xùn)練得到，本文中設(shè)Cij值為已知。將訓(xùn)練后不同節(jié)點(diǎn)處理不同任務(wù)時(shí)的計(jì)算能力用表1進(jìn)行記錄。

表1 節(jié)點(diǎn)計(jì)算能力記錄表

設(shè)某MapReduce作業(yè)J被分解為n個(gè)Map任務(wù)(或由3.3節(jié)中任務(wù)截止時(shí)間約束下的最小切分方法確定)，每個(gè)Map任務(wù)映射到具有不同計(jì)算能力的節(jié)點(diǎn)資源slot上。為使這n個(gè)Map任務(wù)完成時(shí)間均衡并縮短等待時(shí)延，即適應(yīng)異構(gòu)的集群環(huán)境，數(shù)據(jù)的切分規(guī)則應(yīng)滿足(16)式

(17)

其中C1,C2,...,Cn與D1,D2,...,Dn分別表示對(duì)應(yīng)節(jié)點(diǎn)計(jì)算能力與被分配到的數(shù)據(jù)量，而D表示作業(yè)J需要處理的總數(shù)據(jù)量。

3.5 適應(yīng)不同作業(yè)類型的存儲(chǔ)節(jié)點(diǎn)選擇

不同MapReduce作業(yè)對(duì)CPU、內(nèi)存、磁盤、網(wǎng)絡(luò)等資源的需求不同，而異構(gòu)HDFS集群環(huán)境下不同節(jié)點(diǎn)之間的CPU、內(nèi)存、磁盤、網(wǎng)絡(luò)等資源的服務(wù)能力不盡相同。解決已有數(shù)據(jù)布局策略的隨機(jī)性，須為不同的MapReduce作業(yè)類型所處理的數(shù)據(jù)選擇合適的存儲(chǔ)節(jié)點(diǎn)(任務(wù)執(zhí)行節(jié)點(diǎn))。

某MapReduce任務(wù)數(shù)據(jù)塊存儲(chǔ)點(diǎn)選擇由式(18)與式(19)計(jì)算結(jié)果共同決定，其中式(19)為MapReduce任務(wù)對(duì)節(jié)點(diǎn)的評(píng)價(jià)函數(shù)，式(19)為節(jié)點(diǎn)選擇函數(shù)。

(18)

由式(19)選擇服務(wù)評(píng)價(jià)值最高的節(jié)點(diǎn)為數(shù)據(jù)存儲(chǔ)節(jié)點(diǎn)。

Max(Capacitydn1,Capacitydn2,...,Capacitydny)

(19)

以上方法需要進(jìn)行大量的計(jì)算且參數(shù)難以獲得，也可通過3.4節(jié)中提出的方法，通過大量的訓(xùn)練得到表1所示的數(shù)據(jù)記錄形式，對(duì)與不同的MapReduce作業(yè)可通過查詢已有數(shù)據(jù)，并通過式(19)決定存儲(chǔ)節(jié)點(diǎn)。

4 實(shí)驗(yàn)及結(jié)果分析

4.1 實(shí)驗(yàn)環(huán)境配置

為了對(duì)本文提出的MapReduce數(shù)據(jù)布局策略進(jìn)行實(shí)驗(yàn)分析，項(xiàng)目組搭建了擁有22個(gè)節(jié)點(diǎn)的Hadoop集群；其中NameNode與SecondNameNode分別獨(dú)立為一個(gè)節(jié)點(diǎn)，其余20節(jié)點(diǎn)為DataNode(5RACK×4DataNode)。實(shí)驗(yàn)環(huán)境拓?fù)浣Y(jié)構(gòu)如圖4所示。

圖4 實(shí)驗(yàn)環(huán)境拓?fù)浣Y(jié)構(gòu)圖Fig.4 Topology diagram of experimental environment管理節(jié)點(diǎn)2個(gè)，DataNode節(jié)點(diǎn)20個(gè)

為了控制實(shí)驗(yàn)過程中的Map任務(wù)數(shù)量，達(dá)到控制實(shí)驗(yàn)數(shù)據(jù)的統(tǒng)計(jì)與計(jì)算量的目的，特將數(shù)據(jù)塊默認(rèn)的分塊大小配置為128MB，即dfs.block.size=128MB。單個(gè)DataNode節(jié)點(diǎn)上Map與Reduce任務(wù)Slot資源槽數(shù)設(shè)置為1，即配置項(xiàng)為

mapred.tasktracker.map.tasks.maximum=1

mapred.tasktracker.reduce.tasks.maximum=1

能耗數(shù)據(jù)測(cè)量方面，實(shí)驗(yàn)采用北電電力監(jiān)測(cè)儀(USB智能版)，數(shù)據(jù)采樣頻率設(shè)置為1s/次，各節(jié)點(diǎn)能耗數(shù)據(jù)(包括瞬時(shí)功率、電流值、電壓值、能耗累加值等)可通過USB接口實(shí)時(shí)地傳輸?shù)侥芎臄?shù)據(jù)監(jiān)測(cè)機(jī)上，實(shí)現(xiàn)能耗數(shù)據(jù)的收集。實(shí)驗(yàn)總體環(huán)境描述見表2。

表2 總體實(shí)驗(yàn)環(huán)境描述

4.2 任務(wù)數(shù)對(duì)任務(wù)完成時(shí)間及能耗的影響

本實(shí)驗(yàn)采用Terasort作業(yè)，運(yùn)行過程中對(duì)Map與Reduce任務(wù)進(jìn)行不同的設(shè)置，記錄不同條件下作業(yè)的執(zhí)行時(shí)間及能耗。其中按數(shù)據(jù)量的不同分為3組：第一組，數(shù)據(jù)量為1 907.4MB并設(shè)置Map數(shù)量為40，每個(gè)split大小為47.685MB；第二組，數(shù)據(jù)量為2 861MB并設(shè)置Map數(shù)量為60，每個(gè)split大小為47.683MB；第三組，數(shù)據(jù)量為4 768.4MB并設(shè)置Map數(shù)量為80，每個(gè)split大小為59.605MB。MapReduce任務(wù)分解數(shù)與作業(yè)完成時(shí)間之間的關(guān)系如表3所示。

表3 任務(wù)數(shù)與作業(yè)完成時(shí)間之間的關(guān)系

從圖5可以看出：三組實(shí)驗(yàn)作業(yè)完成時(shí)間都隨著任務(wù)數(shù)的增大而減小，說明可以通過適當(dāng)?shù)脑龃笕蝿?wù)數(shù)量來滿足作業(yè)的deadline需求。另一方面，理論上任務(wù)數(shù)越大作業(yè)完成時(shí)間越小，但實(shí)際上任務(wù)數(shù)目與任務(wù)完成時(shí)間之間并不呈線性關(guān)系。當(dāng)任務(wù)數(shù)量增加到某臨界點(diǎn)時(shí)，作業(yè)完成時(shí)間并不會(huì)因?yàn)槿蝿?wù)數(shù)量的增加而減小(減小效果不明顯)。

圖5 任務(wù)數(shù)與作業(yè)完成時(shí)間之間的關(guān)系Fig.5 The relationship between task number and job complete time

由圖6趨勢(shì)與表4中的數(shù)據(jù)可以看出，隨著任務(wù)數(shù)量的不斷增大，作業(yè)能耗不斷的增加；即完成相同作業(yè)，任務(wù)數(shù)越大，完成該任務(wù)能耗越大。這是因?yàn)楫?dāng)任務(wù)數(shù)較多時(shí)，任務(wù)之間的數(shù)據(jù)傳輸成本增加；任務(wù)之間的關(guān)聯(lián)變得復(fù)雜，任務(wù)之間的協(xié)調(diào)成本增加，更多的任務(wù)啟動(dòng)操作及任務(wù)完成后的清理動(dòng)作，以上幾方面都導(dǎo)致了能耗的增加。圖6表明：作業(yè)被分解的任務(wù)數(shù)越少，完成相同作業(yè)所需能耗越小，作業(yè)能耗利用率越高；但是作業(yè)具有截止時(shí)間QoS約束時(shí)，需滿足作業(yè)完成時(shí)間deadline約束需求。利用3.4節(jié)提出的任務(wù)截止時(shí)間約束下的最小任務(wù)切分方法能夠計(jì)算出能耗最優(yōu)的作業(yè)分解方案，即能夠在滿足作業(yè)完成時(shí)間約束前提條件下，最小化作業(yè)執(zhí)行能耗。

圖6 任務(wù)數(shù)與作業(yè)能耗之間的關(guān)系Fig.6 The relationship between task number and energy consumption

4.3 綜合對(duì)比實(shí)驗(yàn)

為構(gòu)造出異構(gòu)集群環(huán)境，本實(shí)驗(yàn)將一組RACK中的4臺(tái)機(jī)器替換為性能較差的節(jié)點(diǎn)(配置為單核IntelPentium4 1.5GHz,512MB內(nèi)存及40GB硬盤)，即本實(shí)驗(yàn)中集群環(huán)境由兩種不同配置的節(jié)點(diǎn)組成(設(shè)配置高節(jié)點(diǎn)類型為A，配置低節(jié)點(diǎn)類型為B)。將表5中配置的MapReduce作業(yè)運(yùn)行50次，記錄各作業(yè)的運(yùn)行結(jié)果，整理出不同節(jié)點(diǎn)類型對(duì)于不同作業(yè)的計(jì)算能力，即3.4節(jié)中節(jié)點(diǎn)計(jì)算能力記錄表(表1)。

表4 任務(wù)數(shù)與作業(yè)能耗之間的關(guān)系

表5 作業(yè)類型說明

實(shí)驗(yàn)結(jié)果如表6所示。

數(shù)據(jù)布局階段，首先按照機(jī)架感知的數(shù)據(jù)塊布局策略將6種不同的作業(yè)數(shù)據(jù)進(jìn)行分布存儲(chǔ)，數(shù)據(jù)塊大小相同，最后記錄各作業(yè)的運(yùn)行時(shí)間及能耗；再次，按照本文中提出的作業(yè)截止時(shí)間約束下的最小任務(wù)數(shù)確定Map與Reduce的任務(wù)數(shù)量，再適應(yīng)異構(gòu)環(huán)境下的數(shù)據(jù)切分(3.4節(jié))及存儲(chǔ)節(jié)點(diǎn)選擇方法(3.5節(jié))進(jìn)行數(shù)據(jù)的布局，記錄各作業(yè)的運(yùn)行時(shí)間及能耗。兩種布局策略下6種作業(yè)(作業(yè)配置參數(shù)如表5所示)的能耗及完成時(shí)間(實(shí)驗(yàn)20次平均值)對(duì)比如表7所示。

如表7所示，與異構(gòu)環(huán)境下原數(shù)據(jù)布局策略(機(jī)架感知的數(shù)據(jù)布局策略)相比較，本文的數(shù)據(jù)布局策略能夠分別提高WordCount、TeraSort、NuthIndex、K-means、PageRank及Bayes作業(yè)完成時(shí)間24.5、23.6、38.4、25.7、47.4及71.9s，提升作業(yè)完成時(shí)間3.55%、5.00%、6.22%、7.59%、10.14%和17.17%；分別節(jié)能33.31、34.41、42.29、33.47、59.7和76.14kJ，節(jié)能效率分別為3.650%、5.185%、5.186%、7.723%、10.423%和15.100%。通過分析可以發(fā)現(xiàn)本文提出的數(shù)據(jù)布局策略對(duì)于WordCount、TeraSort、NuthIndex及K-means四種作業(yè)完成時(shí)間及節(jié)能效率提升有限(5%左右)，而PageRank及Bayes有較為明顯的提升(10%以上)。分析PageRank與Bayes作業(yè)的執(zhí)行過程，發(fā)現(xiàn)Reduce任務(wù)需要等待所有Map任務(wù)完成才能開始，造成等待時(shí)延較長(zhǎng)；這是由于PageRank與Bayes作業(yè)的Map與Reduce的任務(wù)存在強(qiáng)的先后依賴關(guān)系，Reduce任務(wù)必須等待所有的Map任務(wù)完成后才能開始。而與PageRank與Bayes作業(yè)不同的是，WordCount、TeraSort、NuthIndex及K-means四種作業(yè)完成部分Map任務(wù)后Reduce任務(wù)就能夠開始執(zhí)行，所以等待時(shí)延較短。

表6 作業(yè)Map與Reduce任務(wù)的平均功耗及計(jì)算能力

1)單位為MB/s;2)單位為page/s;3)單位為sample/s

表7 不同數(shù)據(jù)布局策略下作業(yè)完成時(shí)間及能耗對(duì)比

1)機(jī)架感知策略；2)本文策略

5 結(jié)論及下一步工作

在能源價(jià)格上漲、數(shù)據(jù)中心存儲(chǔ)規(guī)模不斷擴(kuò)大的今天，高能耗已逐漸成為制約大數(shù)據(jù)快速發(fā)展的一個(gè)主要瓶頸，所以研究節(jié)能的MapReduece數(shù)據(jù)布局策略具有重要意義。已有對(duì)MapReduce的數(shù)據(jù)布局研究工作的目的大多以提高M(jìn)apReduce作業(yè)的執(zhí)行效率為首要目標(biāo)，并沒有考慮到能耗因素。本文在對(duì)已有數(shù)據(jù)布局策略深入研究的基礎(chǔ)上，總結(jié)了與基于存儲(chǔ)區(qū)域劃分的節(jié)能模式及與異構(gòu)HDFS集群的不適應(yīng)、數(shù)據(jù)塊切分算法不靈活、存儲(chǔ)節(jié)點(diǎn)選擇的隨機(jī)性等幾個(gè)方面的問題；針對(duì)以上問題分別提出了對(duì)應(yīng)的解決方案。首先，新策略適應(yīng)將集群劃分為Active-Zone與Sleep-Zone存儲(chǔ)區(qū)域的節(jié)能模式；其次，新策略對(duì)傳統(tǒng)的數(shù)據(jù)塊數(shù)計(jì)算方法進(jìn)行了改進(jìn)，提出作業(yè)截止時(shí)間約束下的最小任務(wù)數(shù)計(jì)算方法確定數(shù)據(jù)塊數(shù)量；最后，新的存儲(chǔ)策略增加了對(duì)異構(gòu)集群環(huán)境的適應(yīng)能力，并能根據(jù)不同的作業(yè)類型進(jìn)行存儲(chǔ)節(jié)點(diǎn)的選擇。為了對(duì)新的數(shù)據(jù)布局算法的有效性進(jìn)行驗(yàn)證，本文搭建了異構(gòu)集群環(huán)境，并對(duì)不同作業(yè)的完成時(shí)間及能耗進(jìn)行了測(cè)量，通過實(shí)驗(yàn)數(shù)據(jù)表明：新的數(shù)據(jù)布局策略能夠適應(yīng)異構(gòu)集群環(huán)境，達(dá)到減小MapReduce作業(yè)能耗的目的(但不同作業(yè)之間存在著差異)。

下一步主要工作是研究MapReduce作業(yè)能耗模型。MapReduce能耗模型是將來開發(fā)MapReduce作業(yè)能耗監(jiān)控及優(yōu)化軟件的理論基礎(chǔ)及關(guān)鍵技術(shù)，因?yàn)槟芎哪Ｐ湍軌驅(qū)崿F(xiàn)在作業(yè)執(zhí)行前對(duì)能耗進(jìn)行預(yù)測(cè)，執(zhí)行過程中為節(jié)能調(diào)度系統(tǒng)提供調(diào)度依據(jù)，執(zhí)行后對(duì)作業(yè)進(jìn)行能耗計(jì)算。

[1] 孟小峰，慈祥. 大數(shù)據(jù)管理: 概念、技術(shù)與挑戰(zhàn)[J]. 計(jì)算機(jī)研究與發(fā)展, 2013, 50(1):146-149.

[2]DEANJ,GHEMAWATS.MapReduce:Simplifeddataprocessingonlargeclusters[C]∥ProceedingsoftheConferenceonOperatingSystemDesignandImplementation(OSDI),NewYork:ACM, 2004: 137-150.

[3]GHEMAWATS,GOBIOFFH,LEUNGST.Thegooglegilesystem[C]∥Proceedingsof19thACMSymposiumonOperatingSystemPrinciples,NewYork:ACM, 2003:29-43.

[4]BORTHAKUD.Thehadoopdistributedfilesystem:Architectureanddesign[EB/OL]. (2007-07-01) [2011-2-12],http:∥hadoop.apache.org/common/docs/r0.18.2/hdfs_design.pdf.

[5]CHANGF,DEANJ,GHEMAWATS,etal.Bigtable:ADistributedStorageSystemforStructuredData[C]∥Proceedingsofthe7thSymposiumonOperatingSystemsDesignandImplementation(OSDI),Seattle,WA,USA, 2006: 205-218.

[6] 王鵬，孟丹，詹劍鋒，等. 數(shù)據(jù)密集型計(jì)算編程模型研究進(jìn)展[J]. 計(jì)算機(jī)研究與發(fā)展, 2010, 47(11): 1993-2002.

[7]GANTZJ,CHUTEC,MANFREDIZA,etal.Thediverseandexplodingdigitaluniverse:Anupdatedforecastofworldwideinformationgrowththrough2011 [EB/OL]. [2013-5-25],http:∥wwww.ifap.ru/library/book268.pdf.

[8]GlobalActionPlan.Aninefficienttruth[EB/OL].Globalactionplanreport, 2007 [2011-02-12],http:∥globalactionplan.org.uk.

[9]TIMESNY.Power,PollutionandtheInternet[EB/OL]. [2013-5-20],http:∥www.nytimes.com/2012/09/23/technology/data-ceneters-waste-vast-amounts-of-energy-belying-industry-image.html.

[10] 于炯，廖彬，張?zhí)?，? 云存儲(chǔ)系統(tǒng)節(jié)能研究綜述[J]. 計(jì)算機(jī)科學(xué)與探索, 2014, 8(9): 1025-1040.

[11]GREENANKM,LONGDDE,MILLEREL,etal.ASpin-upSavedisEnergyEarned:AchievingPower-Efficient,Erasure-CodedStorage[C]∥Proceedingsofthe4thWorkshoponHotTopicsinSyetmsDependability(HotDep‘08),SanDiego,USA, 2008.

[12]WEDDLEC,OLDHAMM,QIANJ,etal.Agear-shiftingpower-awareraid[J].ACMTransactionsonStorage, 2007, 3(3): 1553-1569.

[13]LID,WANGJ.ConservingenergyinconventionaldiskbasedRAIDsystems[C]∥Proceedingsofthe3rdInternationalWorkshoponStorageNetworkArchitectureandParallelI/Os(SNAPI’05).Piscataway,NJ:IEEE, 2005: 65-72.

[14]YAOXY,WANGJ.Rimac:Anovelredundancy-basedhierarchicalcachearchitectureforenergyefficient,highperformancestoragesystems[C]∥Proceedingsofthe1stACMSIGOPS/EuroSysEuropeanConferenceonComputerSystems(EuroSys'06),Leuven,Belgium, 2006.NewYork,USA:ACM, 2006: 249-262.

[15]PINHEIROE,BIANCHINIR,DUBNICKIC.Exploitingredundancytoconserveenergyinstoragesystems[C]∥ProceedingsofthejointinternationalconferenceonMeasurementandmodelingofcomputersystems(SIGMetrics’06/Performance’06),SaintMalo,France, 2006.NewYork,USA:ACM, 2006: 15-26.

[16]COLARELLID,GRUNWALDD.Massivearraysofidledisksforstoragearchives[C]∥Proceedingsofthe2002ACM/IEEEconferenceonSupercomputing(SC’02),Baltimore,USA, 2002.LosAlamitos,CA,USA:IEEEComputerSocietyPress, 2002: 1-11.

[17]NARAYANAND,DONNELLYA,ROWSTRONA.Writeoff-loading:Practicalpowermanagementforenterprisestorage[J].ACMTransactionsonStorage, 2008, 4(3): 253-267.

[18]STORERM,GREENANK,MILLERE,etal.Pergamum:Replacingtapewithenergyefficient,reliable,disk-basedarchivalstorage[C]∥Proceedingsofthe6thUSENIXConferenceonFileandStorageTechnologies(2008),SanJose,USA, 2008.Berkeley,CA,USA:USENIXAssociation, 2008: 1-16.

[19]ZHUQB,CHENZF,TANL,etal.Hibernator:Helpingdiskarrayssleepthroughthewinter[C]∥Proceedingsofthe20thACMSymposiumonOperatingSystemsPrinciples(SOSP’05),Brighton,UK, 2005.NewYork,NY,USA:ACM, 2005: 177-190.

[20]VASICN,BARISITSM,SALZGEBERV.Makingclusterapplicationsenergy-aware[C]∥Proceedingsofthe1stWorkshoponAutomatedControlforDatacentersandClouds(ACDC’09),Barcelona,Spain, 2004.NewYork,NY,USA:ACM, 2009: 37-42.

[21]ZHUQB,DAVIDFM,DEVARAJCF,etal.Reducingenergyconsumptionofdiskstorageusingpower-awarecachemanagement[C]∥Proceedingsofthe10thInternationalConferenceonHigh-PerformanceComputerArchitecture(HPCA’04),Madrid,Spain,Piscataway,NJ,USA:IEEE, 2004: 118-129.

[22]MOHAMEDY,TIANYY,OZCANF,etal.CoHadoop:flexibledataplacementanditsexploitationinHadoop[C]∥ProceedingsoftheVLDBEndowmentVLDB2011,2011, 4(9): 575-585.

[23]DITTRICHJ,QUIANE-RUIZJA,JINDALA,etal.Hadoop++:Makingayellowelephantrunlikeacheetah(withoutitevennoticing) [C]∥ProceedingsofthePVLDB2010,2010,3(1/2):518-529.

[24]ZHAOYR,WANGWP,MENGD,etal.Adatalocalityoptimizationalgorithmforlarge-scaledataprocessinginHadoop[C]∥ProcessingsoftheISCC2012, 2012: 655-661.

[25] 趙彥榮，王偉平，孟丹，等. 基于Hadoop的高效連接查詢處理算法CHMJ[J]. 軟件學(xué)報(bào), 2012, 23(8): 2023-2041.

[26] 廖彬，于炯，張?zhí)?，? 基于分布式文件系統(tǒng)HDFS的節(jié)能算法[J]. 計(jì)算機(jī)學(xué)報(bào), 2013, 36(5): 1047-1064.

[27] 廖彬，于炯，孫華，等. 基于存儲(chǔ)結(jié)構(gòu)重配置的分布式存儲(chǔ)系統(tǒng)節(jié)能算法[J]. 計(jì)算機(jī)研究與發(fā)展, 2013, 50(1): 3-18.

An Energy-Efficient and Heterogeneous Environment Adaptive Data Layout Strategy for MapReduce

LIAOBin1,2,ZHANGTao3,YUJiong2,LIUJi1,ZHONGLei1,LIUYan4

(1. College of Statistics and Information, Xinjiang University of Finance and Economics, Urumqi 830012, China; 2. School of Software, Xinjiang University, Urumqi 830008, China; 3. Department of Medical Engineering and Technology, Xinjiang Medical University, Urumqi 830011, China; 4. School of Software, Tsinghua University, Beijing 100084, China)

The problem of high energy consumption producing from big data processing is an important issue that needs to be solved, especially under the background of data explosion. Based on analyzing problems of the existing data layout policy, the problems of the in adaptation of energy-saving mode based on storage area division and heterogeneous HDFS cluster, the inflexibility of data block segmentation algorithm, the randomness of storage node selection, proposing a data layout strategy orienting to energy conservation are analyzed. Firstly, the new strategy divides the cluster into two different storage areas to meet the needs of saving energy: Active-Zone and Sleep-Zone; secondly, the new strategy has made improvements on traditional data block computing method, proposes a minimum number of jobs calculation method to determine the number of data blocks; at last, the new strategy can increase the adaptability of the heterogeneous cluster environment and can choose the appropriate storage nodes according to different job types. Experimental results show that the new data layout strategy can adapt to the heterogeneous cluster environment and reach the goal of reducing energy consumption for MapReduce jobs.

green computing; MapReduce; heterogeneous environment; data layout

10.13471/j.cnki.acta.snus.2015.06.011

2014-12-07 基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目(61562078, 61262088, 71261025)；新疆財(cái)經(jīng)大學(xué)博士啟動(dòng)基金資助項(xiàng)目(2015BS007)

廖彬(1986年生)，男；研究方向：綠色計(jì)算、數(shù)據(jù)庫(kù)系統(tǒng)理論及數(shù)據(jù)挖掘；E-mail:liaobin665@163.com

TP

A

0529-6579(2015)06-0055-12