大數據應用中節點休眠結合MapReduce作業的能量感知調度方法

邵孟良 齊德昱

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

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

0 引 言

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

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

基于上述分析，本文提出了一種節點休眠結合MapReduce作業的能量感知調度方法，有效實現了作業時的能耗最小化。其主要創新點為：

(1) 現有的兩個主要調度程序是Hadoop和Fair Scheduler，但這兩個調度程序在執行MapReduce應用程序時不考慮提高能效，而本文方法不僅用于提高MapReduce應用程序的能效，同時還滿足SLA；

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

(3) 現有的大多數方法都采用MapReduce作業的能量感知調度，而本文方法結合兩種能量感知的節點休眠MapReduce啟發式調度算法NDMRSA-1和NDMRSA-2，以實現任務分配的自動映射和任務到機器插槽的自動歸并，從而最大限度地減少執行應用程序時消耗的能量。

1 方法設計

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

1.1 MapReduce作業能量感知調度問題

在由多臺機器組成的集群上執行包含特定數量的map和reduce任務的MapReduce作業，作業的計算包括映射階段和歸并階段。在映射階段，每個映射任務被分配給機器上的映射槽，并處理輸入數據的一部分，從而產生鍵值對。在歸并階段，具有相同密鑰的鍵值對分配給歸并槽的reduce任務處理。在映射階段結束之前，作業的歸并階段不能開始[15-16]。最后，reduce階段的輸出被寫回分布式文件系統。在Hadoop中，作業調度由運行作業跟蹤器進程的主節點執行，該進程將作業分發到群集中的多個工作節點。每個工作人員都運行一個任務跟蹤器進程，并配置了固定數量的map和reduce插槽。

將能量感知MapReduce調度問題表示為整數程序(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 節點休眠結合MapReduce能量感知調度算法

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

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

(10)

(11)

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

(12)

(13)

(14)

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

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

算法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

平衡歸并任務分配

Else

對于f<1的情況代碼省略

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

由此可以看出中職生中存在課堂問題行為人數較多，具有普遍性。幾乎所有學生表示有過問題行為，有些學生則多達數種。

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

算法2ASSIGN-SMALL()

{分配小映射任務}

pm=pm+pijm

Xijm=1

{分配小歸并任務}

pr=pr+pijr

Yijr=1

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

2 實驗結果及分析

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

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

2.1 實驗設置

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

表3 選定的HiBench工作負載

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

圖1 任務在實際和仿真架構中的能量需求

2.2 結果分析

2.2.1小尺度實驗

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

表4 小尺度實驗的TeraSort工作負載

圖2(a)顯示了考慮四種算法調度的作業的能耗。結果表明，NDMRSA-1和NDMRSA-2獲得了與OPT最優解能量消耗接近的映射和歸并任務的分配。OPT、NDMRSA-1和NDMRSA-2能夠安排任務，能耗分別比MSPAN平均低41.0%、38.9%和39.2%。例如，NDMRSA-1、NDMRSA-2、OPT和MSPAN獲得的工作負荷(48M，48R)的總能量消耗分別為5 356 J、5 396 J、5 233 J和8 687 J。雖然希望使用OPT作為調度程序來降低成本，但OPT的緩慢執行使得在實踐中使用它是不可行的。此外，由于運行時間過長，在調度大數據作業時幾乎不可能使用OPT。NDMRSA-1和NDMRSA-2是安排大數據工作的非常快速和實用的替代方案，可將能耗降低39%。但是，MSPAN獲得的能耗遠遠不是最優解決方案，因此不適合以最小化能耗為目標來安排MapReduce作業。

(a) 能量消耗

(b) 執行時間

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

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

(a) 映射任務

(b) 歸并任務

2.2.2大尺度實驗

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

表5 大尺度實驗的工作負載

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

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

(a) 能量消耗

(b) 執行時間

由上述所有結果可以得出結論，NDMRSA-1和NDMRSA-2獲得的節點休眠MapReduce作業調度顯著降低了能耗，并且需要較少的執行時間，因此非常適合在數據中心調度大數據應用程序。此外，NDMRSA-1和NDMRSA-2獲得的調度方案提供了接近最佳的節能效果。結果表明，在為數據中心的能效調度MapReduce工作時，完工時間最小化并不一定是最佳策略。這是因為數據中心有義務根據SLA提供所請求的服務，此類協議可能提供顯著的優化機會從而可以降低能源成本。這種能源成本的降低是數據中心采用所提出的調度算法的一個很大的動力。

3 結 語

本文提出了一種節點休眠結合MapReduce作業的能量感知調度方法。能夠找到接近最佳的工作調度，平均消耗的能量比通過最小化完工時間的通用實踐調度程序獲得的調度少約40%，獲得接近最優的解決方案，從而顯著節省能量。

未來的研究方向是為多個MapReduce作業設計和實施分布式調度程序，并關注從源節點到目標節點的雙向延遲問題。