大數(shù)據(jù)應(yīng)用中節(jié)點(diǎn)休眠結(jié)合MapReduce作業(yè)的能量感知調(diào)度方法

邵孟良 齊德昱

1(廣州南洋理工職業(yè)學(xué)院信息工程學(xué)院 廣東 廣州 510925)

2(華南理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 廣東 廣州 510006)

0 引 言

隨著大數(shù)據(jù)應(yīng)用的發(fā)展，一些企業(yè)和組織對(duì)可用數(shù)據(jù)量的需求不斷增長(zhǎng)。這對(duì)現(xiàn)有數(shù)據(jù)處理方法提出了挑戰(zhàn)，更先進(jìn)的方法和技術(shù)亟待提出以應(yīng)對(duì)大數(shù)據(jù)處理的復(fù)雜性。處理數(shù)據(jù)密集型應(yīng)用程序的主要挑戰(zhàn)之一是最大限度地降低能源成本。據(jù)統(tǒng)計(jì)，全球用于數(shù)據(jù)處理的數(shù)據(jù)中心所消耗的能源每年增長(zhǎng)超過(guò)15%，能源成本約占數(shù)據(jù)中心運(yùn)營(yíng)成本的42%。在向客戶提供服務(wù)時(shí)，數(shù)據(jù)中心最大限度地降低能耗至關(guān)重要。因此，研究能量感知調(diào)度方法具有很好的現(xiàn)實(shí)意義和實(shí)用價(jià)值[1-4]。

國(guó)內(nèi)外很多專家及學(xué)者圍繞能量感知調(diào)度方法進(jìn)行了深入的研究。文獻(xiàn)[5]分析了虛擬高性能計(jì)算集群調(diào)度策略，為每個(gè)策略提供了資源預(yù)測(cè)模型，以估算云中所需的資源、請(qǐng)求的隊(duì)列等待時(shí)間以及所需備用資源池的大小。文獻(xiàn)[6]研究了一種新的MapReduce云服務(wù)模型，使用MapReduce分析了作業(yè)創(chuàng)建集群配置，并利用截止期限認(rèn)知，允許云提供商優(yōu)化其全局資源分配并降低資源配置成本。文獻(xiàn)[7]提出了一種編程模型和一種架構(gòu)來(lái)增強(qiáng)MapReduce運(yùn)行時(shí)間，它有效地支持迭代MapReduce計(jì)算，展示了如何將模型擴(kuò)展到MapReduce的更多類應(yīng)用程序。文獻(xiàn)[8]提出了一種使用統(tǒng)計(jì)復(fù)用的協(xié)作資源配置解決方案，以節(jié)省服務(wù)器成本。文獻(xiàn)[9]提出了一種雙層按需資源分配機(jī)制，包括局部和全局的資源分配。以上方法對(duì)于數(shù)據(jù)處理過(guò)程中的能效消耗有一定的降低作用，但是當(dāng)數(shù)據(jù)量過(guò)大時(shí)，數(shù)據(jù)中心對(duì)于大規(guī)模數(shù)據(jù)處理的能耗抑制效果大大降低，因此仍有一定的改進(jìn)空間[11-12]。

基于上述分析，本文提出了一種節(jié)點(diǎn)休眠結(jié)合MapReduce作業(yè)的能量感知調(diào)度方法，有效實(shí)現(xiàn)了作業(yè)時(shí)的能耗最小化。其主要?jiǎng)?chuàng)新點(diǎn)為：

(1) 現(xiàn)有的兩個(gè)主要調(diào)度程序是Hadoop和Fair Scheduler，但這兩個(gè)調(diào)度程序在執(zhí)行MapReduce應(yīng)用程序時(shí)不考慮提高能效，而本文方法不僅用于提高M(jìn)apReduce應(yīng)用程序的能效，同時(shí)還滿足SLA；

(2) 現(xiàn)有的大多數(shù)關(guān)于MapReduce調(diào)度的研究都集中在改進(jìn)MapReduce作業(yè)執(zhí)行的完工時(shí)間，但是完工時(shí)間最小化不一定是數(shù)據(jù)中心的最佳策略，而本文算法捕獲了這些機(jī)會(huì)的同時(shí)滿足了SLA，并顯著降低了MapReduce能源成本，可以很容易地在現(xiàn)有的Hadoop系統(tǒng)中集成和部署；

(3) 現(xiàn)有的大多數(shù)方法都采用MapReduce作業(yè)的能量感知調(diào)度，而本文方法結(jié)合兩種能量感知的節(jié)點(diǎn)休眠M(jìn)apReduce啟發(fā)式調(diào)度算法NDMRSA-1和NDMRSA-2，以實(shí)現(xiàn)任務(wù)分配的自動(dòng)映射和任務(wù)到機(jī)器插槽的自動(dòng)歸并，從而最大限度地減少執(zhí)行應(yīng)用程序時(shí)消耗的能量。

1 方法設(shè)計(jì)

算法可以合并到數(shù)據(jù)中心更高級(jí)別的能源管理策略中。首先模擬將MapReduce任務(wù)調(diào)度為能效的問(wèn)題作為整數(shù)程序，在沒(méi)有解決該問(wèn)題最優(yōu)算法的情況下，設(shè)計(jì)了NDMRSA-1和NDMRSA-2兩種啟發(fā)式算法。NDMRSA-1和NDMRSA-2提供非?？焖俚慕鉀Q方案，使其適合部署在實(shí)際生產(chǎn)的MapReduce集群中[13]。該算法使得鏈路上的節(jié)點(diǎn)不局限于增加蘇醒時(shí)隙的次數(shù)，每個(gè)節(jié)點(diǎn)可以根據(jù)感知到的剩余能量自適應(yīng)地增加一次或多次蘇醒時(shí)隙，不僅使得節(jié)點(diǎn)的能量盡其所用，而且均衡了整個(gè)網(wǎng)絡(luò)中的量負(fù)載，從而延長(zhǎng)了整個(gè)網(wǎng)絡(luò)的工作時(shí)間。本文算法的時(shí)間復(fù)雜度是映射和減少時(shí)隙的數(shù)量、映射任務(wù)的數(shù)量和減少任務(wù)的數(shù)量的多項(xiàng)式。在Hadoop集群上進(jìn)行實(shí)驗(yàn)，以確定幾個(gè)MapReduce基準(zhǔn)測(cè)試應(yīng)用程序的能耗，例如TeraSort、Page Rank和K-means集群[14]。在廣泛的仿真研究中使用這些數(shù)據(jù)來(lái)表征本文算法的性能。實(shí)踐表明，當(dāng)前的實(shí)踐調(diào)度方法，例如完工時(shí)間最小化，產(chǎn)生的計(jì)劃具有遠(yuǎn)非最佳的能耗。將NDMRSA-1和NDMRSA-2的性能與最佳解決方案進(jìn)行比較，以便在合理的時(shí)間內(nèi)獲得最優(yōu)解。結(jié)果表明，NDMRSA-1和NDMRSA-2能夠非?？焖俚卣业浇咏顑?yōu)的解決方案。由于問(wèn)題難以解決，當(dāng)最優(yōu)結(jié)果不可用時(shí)，證明了本文算法獲得的調(diào)度的能量消耗非常接近于整數(shù)的線性規(guī)劃(LP)松弛所獲得的下界解。

1.1 MapReduce作業(yè)能量感知調(diào)度問(wèn)題

在由多臺(tái)機(jī)器組成的集群上執(zhí)行包含特定數(shù)量的map和reduce任務(wù)的MapReduce作業(yè)，作業(yè)的計(jì)算包括映射階段和歸并階段。在映射階段，每個(gè)映射任務(wù)被分配給機(jī)器上的映射槽，并處理輸入數(shù)據(jù)的一部分，從而產(chǎn)生鍵值對(duì)。在歸并階段，具有相同密鑰的鍵值對(duì)分配給歸并槽的reduce任務(wù)處理。在映射階段結(jié)束之前，作業(yè)的歸并階段不能開始[15-16]。最后，reduce階段的輸出被寫回分布式文件系統(tǒng)。在Hadoop中，作業(yè)調(diào)度由運(yùn)行作業(yè)跟蹤器進(jìn)程的主節(jié)點(diǎn)執(zhí)行，該進(jìn)程將作業(yè)分發(fā)到群集中的多個(gè)工作節(jié)點(diǎn)。每個(gè)工作人員都運(yùn)行一個(gè)任務(wù)跟蹤器進(jìn)程，并配置了固定數(shù)量的map和reduce插槽。

將能量感知MapReduce調(diào)度問(wèn)題表示為整數(shù)程序(Energy-aware MapReduce Scheduling,EMRS-IP)，如下所示：

(2)

s.t.

(3)

(4)

(5)

(6)

Yij={0,1} ?i∈,?j∈

(7)

決策變量Xij和Yij定義如下：

(8)

(9)

1.2 節(jié)點(diǎn)休眠結(jié)合MapReduce能量感知調(diào)度算法

節(jié)點(diǎn)休眠M(jìn)apReduce能量感知調(diào)度算法主要包括兩部分：通過(guò)引入感知技術(shù)，對(duì)節(jié)點(diǎn)的剩余能量進(jìn)行動(dòng)態(tài)感知；根據(jù)感知到的結(jié)果對(duì)鏈路上節(jié)點(diǎn)的工作時(shí)間和休眠時(shí)間進(jìn)行調(diào)度，針對(duì)不同的參數(shù)，對(duì)DESS算法和其他經(jīng)典算法通過(guò)仿真實(shí)驗(yàn)進(jìn)行了對(duì)比和分析。提出的算法NDMRSA-1和NDMRSA-2將不同機(jī)器的能效差異考慮在內(nèi)，并確定MapReduce作業(yè)在插槽中的詳細(xì)任務(wù)放置，同時(shí)滿足用戶指定的截止日期要求。這些算法的設(shè)計(jì)需要一個(gè)度量，該度量表征每臺(tái)機(jī)器的能量消耗并引起機(jī)器之間的訂單關(guān)系。定義了這樣一個(gè)度量，稱為時(shí)隙j的能量消耗率。NDMRSA-1和NDMRSA-2使用不同的能耗率指標(biāo)。

(1) NDMRSA-1。使用基于能量消耗的最小比率和在時(shí)隙j上執(zhí)行任務(wù)的處理時(shí)間的能量消耗率度量，如下：

(10)

(11)

(2) NDMRSA-2。根據(jù)在時(shí)隙j上執(zhí)行的能量消耗和任務(wù)處理時(shí)間的平均比率使用能耗率指標(biāo)，如下所示：

(12)

(13)

(14)

在NDMRSA-X的每次迭代中，該比率用于任務(wù)分配過(guò)程。正如使用生產(chǎn)作業(yè)的作業(yè)分析來(lái)估計(jì)映射任務(wù)的處理時(shí)間并減少總?cè)蝿?wù)量。從工作分析中提取的該信息(pijm和pijr的值)，并由NDMRSA-X用于計(jì)算比率f。設(shè)計(jì)算法時(shí)的一個(gè)關(guān)鍵挑戰(zhàn)是用戶只指定作業(yè)的截止日期，并且沒(méi)有關(guān)于完成映射階段的截止日期的信息。但是，由于reduce任務(wù)依賴于map任務(wù)，因此算法必須根據(jù)集群中映射槽的可用性確定映射任務(wù)的合理期限，以便有效地利用其資源。本文算法找到地圖任務(wù)分配到滿足確定的地圖截止期限的地圖槽，然后找到減少任務(wù)的分配到滿足截止日期D的歸并槽，其中所有歸并任務(wù)在映射任務(wù)的截止期限之后開始。

首先，NDMRSA-X根據(jù)處理時(shí)間確定大型任務(wù)的分配，并根據(jù)此類任務(wù)確定映射任務(wù)截止日期。NDMRSA-X優(yōu)先考慮大型任務(wù)的原因是由于硬限期約束，以及為了避免超出規(guī)定時(shí)間的約束，大型任務(wù)的配置可能沒(méi)有多少選擇的事實(shí)。然后，NDMRSA-X嘗試通過(guò)填充較小的任務(wù)來(lái)根據(jù)截止日期填充每個(gè)時(shí)隙的剩余時(shí)間來(lái)縮小最優(yōu)性差距，這樣可以更好地利用群集中的每臺(tái)計(jì)算機(jī)。NDMRSA-X構(gòu)建兩個(gè)優(yōu)先級(jí)隊(duì)列Qm和Qr以保持映射的順序并基于其能量消耗率減少時(shí)隙。然后，它初始化映射任務(wù)的最后期限D(zhuǎn)m，并將歸并任務(wù)的期限D(zhuǎn)r設(shè)定到無(wú)窮大。在while循環(huán)的每次迭代中，算法從優(yōu)先級(jí)隊(duì)列中選擇具有最低能量消耗率(即jm和jr)的時(shí)隙，并在所選擇的時(shí)隙上進(jìn)行任務(wù)的安排。對(duì)于這些時(shí)隙，計(jì)算映射任務(wù)的處理時(shí)間與歸并任務(wù)的處理時(shí)間的比率，用f表示。然后，NDMRSA-X根據(jù)在所選插槽上的處理時(shí)間對(duì)未分配的地圖進(jìn)行排序并執(zhí)行歸并任務(wù)。通過(guò)調(diào)用ASSIGN-LARGE，根據(jù)度量f確定大型任務(wù)的分配。然后，如果插槽上有任何未分配的處理時(shí)間，它通過(guò)調(diào)用ASSIGN-SMALL來(lái)查找小任務(wù)的分配。只要插槽可用，NDMRSA-X就會(huì)為插槽分配新任務(wù)。在第一次迭代結(jié)束時(shí)，算法根據(jù)分配的映射任務(wù)和歸并任務(wù)設(shè)置最后期限。

算法1ASSIGN-LARGE()

pm=0

pr=0

Ifpimjm+pirjr≤D且pimjm≤Dm且pirjr≤Drthen

pm=pimjm

pr=pirjr

Ximjm=1

Yirjr=1

Do

Iff>1 then

pm=pm+pimjm

Ximjm=1

平衡歸并任務(wù)分配

Else

對(duì)于f<1的情況代碼省略

Whilepm+pr+pimjm+pirjr≤D且pm+pimjm≤Dm

由此可以看出中職生中存在課堂問(wèn)題行為人數(shù)較多，具有普遍性。幾乎所有學(xué)生表示有過(guò)問(wèn)題行為，有些學(xué)生則多達(dá)數(shù)種。

在分配具有最大處理時(shí)間的映射和歸并任務(wù)之后，NDMRSA-X通過(guò)調(diào)用ASSIGN-SMALL來(lái)分配能夠滿足截止期限要求的較小的映射和歸并任務(wù)。ASSIGN-SMALL選擇最小的映射任務(wù)i，并根據(jù)已分配的任務(wù)和時(shí)隙的剩余處理時(shí)間，決定分配任務(wù)i是否可行。然后，它選擇最小的歸并任務(wù)i，并檢查其分配的可行性。具體如算法2所示。

算法2ASSIGN-SMALL()

{分配小映射任務(wù)}

pm=pm+pijm

Xijm=1

{分配小歸并任務(wù)}

pr=pr+pijr

Yijr=1

然而，最小化完工時(shí)間的解決方案將選擇X13=1和X22=1以獲得2個(gè)單位的映射完成時(shí)間，并且將選擇Y11=1和Y22=1以獲得2個(gè)單位的歸并的完工時(shí)間。該解決方案導(dǎo)致總單位為4個(gè)，總能量消耗為26。兩種方法都獲得滿足截止期限要求的調(diào)度安排。但本文算法能耗降低了19%，完工時(shí)間為11。

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

本文進(jìn)行了大量實(shí)驗(yàn)來(lái)研究算法NDMRSA-1和NDMRSA-2的性能。將NDMRSA-1和NDMRSA-2的性能與OPT(文獻(xiàn)[5]優(yōu)化EMRS-IP問(wèn)題所得的最優(yōu)解)以及MSPAN(文獻(xiàn)[6]以Makespan最小化為目標(biāo)函數(shù)的EMRS-IP問(wèn)題最優(yōu)解)的性能進(jìn)行比較，其中OPT獲得最小化能量消耗的最佳解決方案。本文方法均適用于大規(guī)模數(shù)據(jù)處理，但對(duì)于增長(zhǎng)較快的數(shù)據(jù)量，需要做進(jìn)一步的實(shí)驗(yàn)以驗(yàn)證該方法對(duì)于大規(guī)模數(shù)據(jù)后處理的有效性。由于所求解問(wèn)題的復(fù)雜性，OPT可能在部分情況下無(wú)法找到最優(yōu)解，因此需要通過(guò)將二元決策變量變?yōu)檫B續(xù)決策變量來(lái)呈現(xiàn)EMRS-IP線性規(guī)劃松弛的結(jié)果。EMRS-IP的LP松弛稱為EMRS-LP，它將NP難優(yōu)化問(wèn)題(EMRS-IP)轉(zhuǎn)換為可在多項(xiàng)式時(shí)間內(nèi)解決的相關(guān)問(wèn)題。EMRS-LP通過(guò)允許將每個(gè)任務(wù)部分分配給機(jī)器來(lái)給出EMRS-IP的最佳解決方案的下限。因此，OPTEMRS-LP≤OPTEMRS-IP，其中OPTEMRS-LP是EMRS-LP的最佳解決方案，OPTEMRS-IP是EMRS-IP的最佳解決方案。然而，每個(gè)任務(wù)的這種部分分配(通過(guò)解決EMRS-IP的松弛而獲得)不是該問(wèn)題的解決方案，并且不能在實(shí)踐中使用。使用EMRS-LP的解決方案(EMRS-IP的松弛)作為EMRS-IP的下限，并將其與其他算法獲得的解決方案進(jìn)行比較。用L-BOUND表示解決EMRS-LP并在解上產(chǎn)生下界的算法。此外，還介紹了最小化完工時(shí)間MSPAN的結(jié)果，以顯示MapReduce調(diào)度的當(dāng)前實(shí)踐與考慮節(jié)能目標(biāo)的最佳解決方案的距離。通過(guò)最優(yōu)地求解與MapReduce完工時(shí)間最小化問(wèn)題相對(duì)應(yīng)的IP(與ERMSA-IP中相同的約束，但目標(biāo)是完工時(shí)間最小化)來(lái)獲得MSPAN。由于MSPAN在幾種情況下無(wú)法找到最優(yōu)解，因此實(shí)現(xiàn)了一種用于完工時(shí)間最小化的貪婪算法，稱為G-MSPAN。G-MSPAN安排機(jī)器上的任務(wù)，以便平衡所有機(jī)器的處理時(shí)間。它將更長(zhǎng)的任務(wù)分配給更快的機(jī)器以保持平衡。

為了分析NDMRSA-1和NDMRSA-2的性能，提出了小規(guī)模和大規(guī)模的實(shí)驗(yàn)。在小規(guī)模實(shí)驗(yàn)中，比較了小型MapReduce作業(yè)的NDMRSA-1、NDMRSA-2、OPT和MSPAN的性能。然而，對(duì)于大型工作，即使在24小時(shí)后也無(wú)法獲得OPT和MSPAN的最佳結(jié)果，因此比較了NDMRSA-1、NDMRSA-2、L-BOUND和G-MSPAN的性能。NDMRSA-1、NDMRSA-2、OPT、L-BOUND、MSPAN和G-MSPAN算法使用C++實(shí)現(xiàn)。OPT、MSPAN和L-BOUND使用IBM ILOG CPLEX Optimization Studio Multiplatform Multilingual eAssembly提供的API實(shí)現(xiàn)。

2.1 實(shí)驗(yàn)設(shè)置

在64個(gè)處理器的Hadoop集群上進(jìn)行了大量實(shí)驗(yàn)，并測(cè)量了幾個(gè)MapReduce HiBench基準(zhǔn)測(cè)試工作負(fù)載的能量消耗和執(zhí)行時(shí)間。HiBench是英特爾為Hadoop提供的綜合基準(zhǔn)測(cè)試套件，用于表征在數(shù)據(jù)中心運(yùn)行的基于MapReduce的數(shù)據(jù)分析的性能。HiBench包含十個(gè)工作負(fù)載，分為四類：微基準(zhǔn)、Web搜索、機(jī)器學(xué)習(xí)和分析查詢。從不同的類別中選擇三個(gè)工作負(fù)載，TeraSort、Page Rank和K-means集群，如表3所示。集群由四個(gè)Intel節(jié)點(diǎn)組成，其中一個(gè)節(jié)點(diǎn)作為主節(jié)點(diǎn)，兩個(gè)節(jié)點(diǎn)具有24 GB內(nèi)存，16個(gè)2.4 GHz Intel處理器和1 TB硬盤驅(qū)動(dòng)器，另外兩個(gè)節(jié)點(diǎn)有16 GB內(nèi)存，16個(gè)2.4 GHz Intel處理器和1 TB硬盤。該集群總共有80 GB內(nèi)存，64個(gè)處理器，4 TB存儲(chǔ)空間和1 Gbps的網(wǎng)絡(luò)速度。為每個(gè)處理器設(shè)置了一個(gè)映射槽和一個(gè)歸并槽。使用Wattsup PRO ES.Net功率計(jì)進(jìn)行能量測(cè)量。輸入電壓在50 Hz 100～250 V時(shí)，最大功率為1 800 W。測(cè)量精度為±2.0%，記錄之間選定的時(shí)間間隔為1 s。

表3 選定的HiBench工作負(fù)載

每個(gè)工作負(fù)載都包含map和reduce任務(wù)。對(duì)于每個(gè)工作負(fù)載，收集其開始時(shí)間、完成時(shí)間、消耗功率和其他性能指標(biāo)。使用240個(gè)工作負(fù)載進(jìn)行工作分析。一次只運(yùn)行一個(gè)工作，并收集能量測(cè)量和執(zhí)行時(shí)間。由于reduce任務(wù)僅在完成所有map任務(wù)的執(zhí)行后才執(zhí)行，因此map和reduce任務(wù)之間沒(méi)有重疊。根據(jù)收集的工作檔案，生成了四個(gè)小型MapReduce工作，具有用于250秒的最小規(guī)模實(shí)驗(yàn)，以及24個(gè)大型MapReduce工作，用于大規(guī)模實(shí)驗(yàn)的截止時(shí)間為1 500秒。因?yàn)閷?duì)于生產(chǎn)工作，截止時(shí)間的選擇是由用戶決定的，專門選擇截止日期以獲得可行的時(shí)間表。組成這些作業(yè)的map和reduce任務(wù)的執(zhí)行時(shí)間和能量消耗是從均勻分布生成的，均勻分布的平均能耗和地圖的平均執(zhí)行時(shí)間平均，并減少?gòu)膶?shí)驗(yàn)中描述的作業(yè)中提取的任務(wù)。圖1顯示了實(shí)際和模擬架構(gòu)的map和reduce任務(wù)的能量需求。每個(gè)節(jié)點(diǎn)的能量消耗范圍顯示為填充框，其中框的底部和頂部分別代表最小和最大能量消耗。對(duì)于模擬的體系結(jié)構(gòu)，每個(gè)節(jié)點(diǎn)的能量消耗在一個(gè)范圍內(nèi)生成，該范圍的邊界在圖中表示為水平線。仿真實(shí)驗(yàn)是在具有90 GB RAM的AMD 2.93 GHz六核雙處理器系統(tǒng)上進(jìn)行的，這些系統(tǒng)是Wayne State Grid System的一部分。

圖1 任務(wù)在實(shí)際和仿真架構(gòu)中的能量需求

2.2 結(jié)果分析

2.2.1小尺度實(shí)驗(yàn)

分析了NDMRSA-1、NDMRSA-2、OPT和MSPAN的四個(gè)小型MapReduce TeraSort作業(yè)的性能，包含10 737 418個(gè)記錄，映射任務(wù)和歸并任務(wù)的數(shù)量如表4所示。例如，最小的工作(45M，45R)有45個(gè)映射任務(wù)和45個(gè)歸并任務(wù)。

表4 小尺度實(shí)驗(yàn)的TeraSort工作負(fù)載

圖2(a)顯示了考慮四種算法調(diào)度的作業(yè)的能耗。結(jié)果表明，NDMRSA-1和NDMRSA-2獲得了與OPT最優(yōu)解能量消耗接近的映射和歸并任務(wù)的分配。OPT、NDMRSA-1和NDMRSA-2能夠安排任務(wù)，能耗分別比MSPAN平均低41.0%、38.9%和39.2%。例如，NDMRSA-1、NDMRSA-2、OPT和MSPAN獲得的工作負(fù)荷(48M，48R)的總能量消耗分別為5 356 J、5 396 J、5 233 J和8 687 J。雖然希望使用OPT作為調(diào)度程序來(lái)降低成本，但OPT的緩慢執(zhí)行使得在實(shí)踐中使用它是不可行的。此外，由于運(yùn)行時(shí)間過(guò)長(zhǎng)，在調(diào)度大數(shù)據(jù)作業(yè)時(shí)幾乎不可能使用OPT。NDMRSA-1和NDMRSA-2是安排大數(shù)據(jù)工作的非?？焖俸蛯?shí)用的替代方案，可將能耗降低39%。但是，MSPAN獲得的能耗遠(yuǎn)遠(yuǎn)不是最優(yōu)解決方案，因此不適合以最小化能耗為目標(biāo)來(lái)安排MapReduce作業(yè)。

(a) 能量消耗

(b) 執(zhí)行時(shí)間

圖2(b)顯示了算法的執(zhí)行時(shí)間。結(jié)果表明，NDMRSA-1和NDMRSA-2在比OPT和MSPAN顯著更少的時(shí)間內(nèi)發(fā)現(xiàn)分配。NDMRSA-1和NDMRSA-2在比OPT小6個(gè)數(shù)量級(jí)的時(shí)間內(nèi)獲得解決方案。例如，工作負(fù)荷(48M，48R)的NDMRSA-1、NDMRSA-2、OPT和MSPAN的執(zhí)行時(shí)間分別為0.001 s、0.001 s、673.7 s和839.3 s。

圖3詳細(xì)地介紹了映射任務(wù)和歸并任務(wù)的能耗。當(dāng)歸并任務(wù)的數(shù)量大于映射任務(wù)的數(shù)量時(shí)，NDMRSA-1和NDMRSA-2能夠捕獲更多用于歸并任務(wù)的節(jié)能的優(yōu)化機(jī)會(huì)。更詳細(xì)地，NDMRSA-1、NDMRSA-2、OPT和MSPAN獲得的工作負(fù)荷(48M，64R)的映射任務(wù)的能量消耗分別為3 130 J、3 090 J、2 897 J和4 751 J，而工作負(fù)載為(48M，64R)時(shí)歸并任務(wù)的能量消耗則分別為3 547 J、3 527 J、3 448 J和5 972 J。但是，當(dāng)工作負(fù)載具有比歸并任務(wù)更多的映射任務(wù)(例如，工作負(fù)載(60M，45R))時(shí)，NDMRSA-1和NDMRSA-2為映射任務(wù)節(jié)省更多能量。通過(guò)使用NDMRSA-X(圖3(a)所示)獲得的工作負(fù)荷(60M，45R)的映射任務(wù)的能量消耗更接近于針對(duì)相同工作量的歸并任務(wù)(圖3(b)所示)的能量消耗的最佳能量消耗。這是因?yàn)閷?duì)于此工作負(fù)載，映射任務(wù)的負(fù)載大于歸并任務(wù)的負(fù)載，即f>1。對(duì)于工作負(fù)荷(45M，60R)，則有f<1，NDMRSA-X導(dǎo)致能量消耗接近于歸并任務(wù)的最佳能量。這顯示了比率f對(duì)能量消耗的影響。

(a) 映射任務(wù)

(b) 歸并任務(wù)

2.2.2大尺度實(shí)驗(yàn)

分析了NDMRSA-1、NDMRSA-2、L-BOUND和G-MSPAN的性能，針對(duì)三種類型的基準(zhǔn)測(cè)試(TeraSort、Page Rank和K-means集群)，考慮了每個(gè)的8個(gè)大型MapReduce作業(yè)。表5給出了map任務(wù)和reduce任務(wù)。

表5 大尺度實(shí)驗(yàn)的工作負(fù)載

圖4(a)顯示了NDMRSA-1、NDMRSA-2、OPT和MSPAN的能量消耗。NDMRSA-1和NDMRSA-2獲得的能量消耗非常接近所有情況的下限，這反過(guò)來(lái)意味著NDMRSA-1和NDMRSA-2解決方案甚至更接近最優(yōu)解。這顯示了通過(guò)NDMRSA-1和NDMRSA-2獲得的解近似最優(yōu)解。在某些情況下，NDMRSA-1獲得了更好的結(jié)果。然而，結(jié)果表明，NDMRSA-1和NDMRSA-2能夠找到需要比G-MSPAN獲得的能量平均少35.6%和35.8%的能量的調(diào)度方案。這種能耗降低可能是數(shù)據(jù)中心將NDMRSA-1和NDMRSA-2納入調(diào)度Map-Reduce工作以降低成本的一個(gè)很大的動(dòng)力。將NDMRSA-1和NDMRSA-2在大規(guī)模實(shí)驗(yàn)中獲得的能量節(jié)省量與G-MSPAN獲得的節(jié)能量進(jìn)行比較。隨著map和reduce任務(wù)總數(shù)的增加(從250到1 020)，工作負(fù)載的總能耗增加。此外，圖4顯示了對(duì)任務(wù)數(shù)量的敏感性分析。通過(guò)固定映射任務(wù)的數(shù)量，同時(shí)增加歸并任務(wù)的數(shù)量，可以觀察到總能量消耗的增加。例如，顯示前三個(gè)工作負(fù)載的此行為，其中映射任務(wù)的數(shù)量為120，歸并任務(wù)的數(shù)量為120到500。

圖4(b)顯示了算法的執(zhí)行時(shí)間。NDMRSA-1、NDMRSA-2和MSPAN在所有選定的MapReduce作業(yè)中查找結(jié)果的時(shí)間不到1 s。注意，下限結(jié)果是通過(guò)求解LP松弛而不是NDMRSA-1P獲得的。呈現(xiàn)LP松弛結(jié)果的L-BOUND的執(zhí)行時(shí)間是多項(xiàng)式的。此外，隨著map和reduce任務(wù)總數(shù)的增加，L-BOUND的執(zhí)行時(shí)間增加。例如，對(duì)于(1 280，120R)和(120M，500R)兩個(gè)工作負(fù)載，L-BOUND的執(zhí)行時(shí)間有所增加。但是，對(duì)于(120M，500R)和(250M，120R)兩個(gè)工作負(fù)載，其執(zhí)行時(shí)間有所降低。NDMRSA-1和NDMRSA-2的執(zhí)行時(shí)間遵循相同的行為。

(a) 能量消耗

(b) 執(zhí)行時(shí)間

由上述所有結(jié)果可以得出結(jié)論，NDMRSA-1和NDMRSA-2獲得的節(jié)點(diǎn)休眠M(jìn)apReduce作業(yè)調(diào)度顯著降低了能耗，并且需要較少的執(zhí)行時(shí)間，因此非常適合在數(shù)據(jù)中心調(diào)度大數(shù)據(jù)應(yīng)用程序。此外，NDMRSA-1和NDMRSA-2獲得的調(diào)度方案提供了接近最佳的節(jié)能效果。結(jié)果表明，在為數(shù)據(jù)中心的能效調(diào)度MapReduce工作時(shí)，完工時(shí)間最小化并不一定是最佳策略。這是因?yàn)閿?shù)據(jù)中心有義務(wù)根據(jù)SLA提供所請(qǐng)求的服務(wù)，此類協(xié)議可能提供顯著的優(yōu)化機(jī)會(huì)從而可以降低能源成本。這種能源成本的降低是數(shù)據(jù)中心采用所提出的調(diào)度算法的一個(gè)很大的動(dòng)力。

3 結(jié) 語(yǔ)

本文提出了一種節(jié)點(diǎn)休眠結(jié)合MapReduce作業(yè)的能量感知調(diào)度方法。能夠找到接近最佳的工作調(diào)度，平均消耗的能量比通過(guò)最小化完工時(shí)間的通用實(shí)踐調(diào)度程序獲得的調(diào)度少約40%，獲得接近最優(yōu)的解決方案，從而顯著節(jié)省能量。

未來(lái)的研究方向是為多個(gè)MapReduce作業(yè)設(shè)計(jì)和實(shí)施分布式調(diào)度程序，并關(guān)注從源節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的雙向延遲問(wèn)題。