基于和聲算法異構Hadoop集群資源分配優化

李鋒剛, 魏炎炎, 楊龍

Li Fenggang 1,2, Wei Yanyan 1,2,Yang Long1,2

1.合肥工業大學 管理學院，合肥 230009

2.教育部過程優化與智能決策重點實驗室，合肥 230009

1. School of Management, Hefei University of Technology, Hefei 230009, China

2. Key Laboratory of Process Optimization and Intelligent Decision-making, Ministry of Education, Hefei 230009, China

1 引言

自2007年IBM宣布云計算計劃之后，云成為目前工業界和學術界研究的熱點，云計算的理念為計算資源公共化的商業實現，目前工業界有代表性的云計算實例有Google的云計算平臺、IBM的“藍云”、微軟的Azure等[1]。在云計算的數據中心成千上萬或者更多臺計算節點或服務器組成計算集群，這樣的集群有具大的處理能力，并且可以根據用戶的需求動態分配計算或者存儲資源，因此如何更有效的分配資源成為人們研究的問題。由于云計算是從網絡計算演化而來，而在網絡環境中資源分配問題又是人們研究的熱點[2]，并且云和網格在有一定的聯系的基礎上又存在很多異同，所以研究云環境中資源分配問題有一定價值。

MapReduce是云計算的編程模型和任務調試方式。Hadoop是Yahoo開發的MapReduce調試方式和GFS的開源實現?，F有的Hadoop調度器都是建立在同構集群假設前提之下，并且沒有考慮數據的區域性，但是實際情況并不是這樣[3]。考慮不同處理機計算速度，不同機器之間數據傳輸以及因數據聚集帶來I/O傳輸和網絡消耗問題[4]，如何在滿足用戶需求的條件下更好的分配資源成為一個重要問題，其分配策略的優 劣直接影響到云計算架構的工作性能和優越性。傳統MapRedcue調度策略為一種事后的控制，當出現慢節點（straggler）之后，再通過啟動備份任務的方法重新執行，雖然這種調度能普遍的提高響應時間，但是還存在一定的問題。本文考慮計算資源性能和其外部條件，利用和聲搜索算法對該計算資源的響應時間進行預測，目的為分配合適的資源到合適的計算節點，以期望能夠提高各個節點完成分配任務的時間并減少慢節點的產生，做到整體響應時間的最小化。

2 相關知識

作為分布式計算、并行計算和網格計算的發展，云計算是一種基于互聯網的商業計算模式， 它將計算任務分布在大量計算機構成的資源池上，并且以抽象虛擬和動態增長的方式為用戶提供需要的計算能力、存儲能力或其他服務。按照服務類型云計算可以分為三大類：基礎設施即服務（IaaS）、軟件即服務（SaaS）和平臺即服務（PaaS）[5]。

Hadoop是Apache開源組織的一個分布式計算框架，可在大量廉價的硬件設備組成的集群上運行應用程序，目前現有的Hadoop平臺都是以集群的同構為前提，都假設在此集群中各節點的性能和處理能力完全一樣、各節點外部環境如帶寬或網絡環境都完全一樣[6]。

MapReduce是云計算中分布式計算編程模型，其應用也是非常的廣泛，如在谷歌利用 MapReduce來做分布 Grep、分布排序、Web訪問日志分析、反射索引構建、文檔聚類、機器學習等[7]。MapReduce模型通過將輸入數據分割為許多塊，并對不同的塊執行 Map和 Reduce操作來完成整體的任務。由于每個 Map操作都針對不同的原始數據，所以 Map操作之間可以保持較高的并行性。Reduce操作是對 Map操作所產生的結果進行合并，由于每個Reduce所處理的Map中間結果是互不交叉的，所以 Reduce操作也有一定的并行性。

如下對 MapReduce處理流程做簡單介紹[5]，并如圖1所示：(1).MapReduce首先將輸入文件分成 M塊，每塊大小為 16M～64M，每塊大小可通過參數設定；(2).在處理操作中首先分配一個 Master（主控程序），Master選擇空閑的 Worker（工作機）來分配 M個Map任務和R個Reduce任務；(3).每個分配了 Map任務的 Worker讀取并處理Master分配給其的數據塊，對數據塊進行Map操作，并生成中間結果以對的形式保存至緩存；(4).保存在緩存中的中間結果將被定時寫到本地硬盤，這些臨時數據將會通過分區函數分成 R個區。中間結果在本地硬盤的位置將被發送至 Master；(5).Master通知處理 Reduce任務的 Worker節點中間結果的位置，處理Reduce的Worker從Map Worker的本地磁盤獲取相應的中間數據，根據定義的Reduce函數對中間結果依據 Key進行合并操作，并將結果輸出到輸出文件；(6).當所有Map任務和Reduce任務都完成，Master激活用戶程序，并返回輸出文件位置及列表。

圖1 MapReduce處理流程

下面對MapReduce容錯機制給予分析：

由于 MapReduce是在成百上千臺計算機上處理海量數據，所以需要有很好的容錯機制來保持算法的穩定性和安全性。MapReduce的容錯是基于“重新執行失敗的操作”的原則而設計。Master節點是整個 MapReduce的核心，如果不進行任何容錯機制，一旦 Master失效整個MapReduce操作將會前功盡棄。為了防止這種致命性的錯誤，Master節點會周期性設置檢查點（Checkpoint）并導出目前的控制數據。當 Master失效時將檢查最近檢查點并重新執行失敗操作。Worker失效是一種更常見的狀態。其容錯機制為：Master定期發送 ping命令以檢查 Worker的有效性，如果 Worker沒有應答，則Master將此 Worker標記為失效，并將分配給此 Worker的工作分配給其他空閑Worker重新執行。

3 問題描述及建模

如何提高MapReduce操作的效率，或者說如何花費最少的時間尋找合適的Worker來完成用戶的需求為本文的研究目的。在MapReduce的整個執行過程中，我們需要考慮如下因素對總響應時間的影響：(1).輸入文件數據分塊的大??；(2).可用Worker的數量及Map Worker和Reduce Worker的數量；(3).Master節點的自身特性如處理能力、帶寬和線路質量；(4).各個Worker的自身特性如處理能力、帶寬和線路質量；(5).待處理數據和Worker的地理位置分布；(6).中間數據和其對應的Reduce節點的地理位置分布；(7).輸出文件的位置；(8).Master節點穩定性和檢查點的設置步長；(9).Worker節點的穩定性和詢問周期；

為了簡單起見，本文根據所關注的核心問題，考慮節點的性能（處理能力）、節點的外部條件（帶寬、線路質量及位置）及輸入數據塊大小為主要因素來進行計算資源分配優化。

我們可以將在本集群中的所有可以由Master節點調度的節點域看成一個無向圖G(V,E),其中V是所有可由Master調度的節點集合，E是連接各Worker節點的網絡集合。尋找每個Map或者Reduce操作最優的Worker，也就變成在E中尋找一條最優路徑e的操作[8]。又由于每個Map或者Reduce的可選節點網絡集合是不同的，必須在V中排除那些已經分配給其他Map或者Reduce操作的非空閑節點，我們將第i次節點選擇中可用節點網絡集合記為Ei，其節點集合記為Vi。

在影響MapReduce效率的因素中有如下因素直接影響E中尋找一條最優路徑e的選擇：

1) Vi中每個節點的處理能力，由節點的性能如處理器主頻、內存大小、緩存大小和可用磁盤空間等因素決定。

2) Vi各節點的網絡狀態，如網絡帶寬和網絡延遲等。

3) 需要處理的數據塊的大小及相對Vi中各節點的位置分布。如下我們對計算節點選擇的影響因素

進行公式化，轉化為相應的時間因素：

1) 節點預計執行時間time_cost(ei)：指路徑ei盡頭的計算資源處理該作業預計耗費時間，由節點處理能力決定。節點完成任務需要的時間為節點性能中瓶頸因素所決定。

2) 網絡延遲time_delay(ei)：指路徑ei產生的最大網絡延遲。

3) 數據獲取時間time_getdata(ei)：由路徑ei的長度、網絡帶寬和數據塊的大小共同決定,和數據塊的大小及e的長度成正比關系，和網絡帶寬成反比關系。

公式化為如下形式：

考慮如上三個因素 MapReduce執行過程中節點選擇公式為：

約束條件：

其中 ei為第 i條路徑選擇,Ei為第 i次路徑選擇中可行路徑集合；time(ei)為第 i條路徑完成指定任務需要的時間；

α、β、χ為權重值，并且α+β+χ=1；CL、DL和GL為其邊界限制條件。

4 算法描述

4.1 基本和聲搜索算法（BHS）

和聲搜索算法（Harmony Search,HS）[9]是由Geem Z W等人提出的一種啟發式智能優化算法，在許多組合優化問題中得到了成功應用[10-13]。在音樂演奏中,樂師們憑借記憶, 通過反復調整樂隊中各樂器的音調, 最終達到一個美妙的和聲狀態。Geem 等人受這一現象啟發, 提出了基本和聲搜索(Basic Harmony Search, BHS) 算法。

BHS 將樂器的音調類比作優化問題的決策變量Xij, 將各樂器的和聲類比于解向量,其中n為決策變量的個數, 評價類比于目標函數F(Xi) ,和聲記憶庫HM 類比于種群, 樂曲的創作過程類比于種群進化過程[14]。和聲記憶庫的形式如下：

隨著算法應用的越來越廣泛，也有一些學者對算法進行了改進，以尋求更好的計算結果和性能。對 HS算法的改進主要集中在兩個方面：一方面為動態調節算法中的某些參數;另一方面是在變量微調時改變隨機數的選取方式[15]。本文在實驗中將同時應用基本和聲算法和一種改進的和聲算法優化資源分配問題。

4.2 算法流程

BHS 從隨機產生的和聲記憶庫開始，通過對和聲記憶庫思考、隨機選擇音調，以及和聲調節來產生新解，再通過新解與和聲記憶庫中的最差解比較來決定是否更新和聲記憶庫，和聲搜索算法解決問題分為以下步驟：(1).問題公式化； (2).算法參數設置；(3).隨機的記憶庫初始化；(4).隨機選擇、記憶的考慮、調整；(5).記憶庫更新；(6).算法迭代及終止。

4.3 算法參數設置

1).和聲記憶庫的大?。℉MS）:指此算法同時處理的解向量的個數；(2).創作次數（MI）:即算法迭代的次數；(3).和聲記憶庫思考概率（HMCR）:指和聲搜索算法從記憶庫中取值概率，則以（1-HMCR）的概率從變量定義域中取值對和聲記憶庫進行更新；(4).音調微調概率（PAR）:為對從記憶庫中取出的值進行微調的概率，則以（1-PAR）的概率保持記憶庫原來的數據不變。在BHS中一些固定的參數值被應用到問題的求解中，也有一些研究者提出了可變的參數，如PAR隨著迭代的進行線性增長，這樣可以一定程度上提高算法性能。動態PAR參數式為（t為迭代的次數）：

(5).調節頻寬（FW）:無論是對和聲記憶庫中還是定義域中取出的值進行微調的頻寬。改進的和聲搜索算法中有些將FW隨著迭代的進行指數遞減，參數公式為：

4.4 記憶庫（HM）的初始化

為了保證算法的收斂速度和有效性，初始和聲記憶庫必須保證種群的分散性和均勻性。初始和聲記憶按下式均勻產生：

其中Xij為第i個候選解向量中第j個決策變量的取值。rand[0,1]為在0到1上的均勻分布隨機數。

4.5 新和聲的生成

新和聲是基于記憶考慮、隨機選擇和微調擾動3個規則產生的。記憶考慮可按如下的公式生成新和聲變量：

其中rand()為在[0,1]上均勻分布隨機數，當特定情況下rand()的值小于HMCR，則第i個變量從和聲記憶庫中已存在的Xi中取值;否則從Xi的值域Ωi中隨機選擇。

微調擾動以如下規則進行：

若隨機數rand()

4.6 記憶庫的更新

對于最小化問題，以如下規則更新和聲記憶庫：

4.7 迭代終止

當迭代次數達到預先設定的 MI次之后，則算法迭代終止，和聲記憶庫中最優解為求解問題的最終解。

5 算法仿真及結果分析

由于真實Hadoop平臺及其計算資源性能和外部環境度量的復雜性，并且云環境局部可以看作一個特殊的網格，因此我們利用Gridsim[16]來仿真云計算的局部域，以檢查我們算法的有效性。Gridsim在大規模分布式計算機集群仿真中非常常見，并且仿真效果也比較理想。本文通過Gridsim的GridResource類模擬云計算中的計算資源和網絡資源，并通過設定GridResource類中參數不同來模擬異構節點;通過GridInformationServices來管理這些模擬的資源。

為了比較算法的有效性，我們在用GridResource模擬的外部環境相同的情況下，將文中（1）式和（2）式在GridBroker中構造如下三種不同的策略來進行計算資源的選擇，并比較各種策略的有效性和適用性。

三種策略及其參數設定：

A1：隨機選擇計算資源：第i次節點選擇中可用節點網絡Ei中可用路徑數為Ci，則我們以[0,Ci]的均勻分布對計算節點進行隨機選擇。

A2：基本和聲搜索算法：我們將基本和聲搜索算法參數設置為HMS=6，HMCR=0.9，PAR = 0.1，MI=Ci。

A3：改進的和聲搜索算法：為了獲得更好的收斂效果，我們利用動態調節算法參數的方法來改進和聲搜索算法，設置其參數如下：HMS=5,HMCR=0.9，PARmin=0.01，PARmax=0.99，MI=Ci。

我們對1GB的文本應用MapReduce進行WordCount操作，數據塊大小為32M，同時最大任務數（同時可并行運行的任務數，Task）為50。分別模擬集群中節點數量分別為25、40、50、75、100、200，且各節點的計算能力、網絡帶寬和位置并不完全相同。完成MapReduce的所有任務需要的時間如下表1所示（單位秒(s)，表頭A表示集群中節點數量、B表示三種不同分配策略）。

表1 Task=50,MI=Ci時仿真實驗數據

由仿真實驗結果表1我們可以看出，應用和聲搜索算法（A2、A3）進行計算資源分配要比隨機選擇策略（A1）在響應時間上有很大優勢；而基本和聲搜索算法（A2）和改進和聲搜索算法（A3）在執行效率上基本相同，后者稍優。根據如上數據我們可畫出如圖2所示仿真結果曲圖（耗時單位為秒）。

圖2 Task=50,MI=Ci時仿真結果曲線圖

圖2中橫坐標表示集群中節點的數量，縱坐標表示Map-Reduce執行完設定Task需要的時間。從圖2可以看出，當節點數小于Task數目時，隨著節點數目增多至Task數目附近耗時下降明顯；當節點數目大于任務數目時，隨著節點數目的增多，對總耗時沒有顯著的影響?？紤]和聲搜索算法迭代次數MI對實驗結果的影響，我們在其他條件不變的情況下設置Mi=2Ci，再次進行實驗，得到結果如表2：

表2 Task=50,MI=2Ci時仿真實驗數據

由兩次實驗可以看出隨著迭代次數的增加完成所有任務的耗時有稍量下降，可以通過適當提高迭代次數獲得更好的資源分配效果，但是效果并不顯著。

5 結束語

異構Map-Reduce環境中資源分配策略直接影響到其響應時間，如何利用有效的策略將計算任務分配到計算資源是亟待解決的問題。文中對計算資源分配問題進行建模，利用和聲搜索算法來優化資源分配，以期縮短MapReduce的整體響應時間，提高云計算平臺的效率。從仿真結果可能看出，此算法明顯優于資源的隨機選擇策略，并且可以利用改進的和聲搜索算法獲得比基本和聲算法稍好的性能。

[1]. 田宏偉,解福,倪俊敏. 云計算環境下基于粒子群算法的資源分配策略[J]. 計算機技術與發展,2011. 21(12):22-25.

[2].梁俊斌,蘇德富.基于云模型的網格資源分配策略[J]. 計算機工程與應用,2005(5):147-150.

[3]. Jiong, X., et al. Improving MapReduce performance through data placement in heterogeneous Hadoop clusters[C]. 2010 IEEE International Symposium on Parallel&Distributed Processing, Workshops and Phd Forum, Atlanta, GA, USA, 2010/4/19-23.

[4].陳全. 異構環境下自適應的 Map-Reduce調度[J]. 計算機工程與科學, 2009. 31(A1),168-175.

[5].劉鵬, 慈祥. 云計算[M]. 北京: 電子工業出版社,2010:2-3/14-17.

[6].Dean,J.et al,MapReduce:Simplified Data Processing on Large Clusters[J].Communications of the ACM, 2008. 51(1):107-113.

[7].Lammel, R. Google's MapReduce programming model-Revisited[J].Science of Computer Programming , 2008. 70(1): 1-30.

[8].華夏渝, 鄭駿, 胡文心. 基于云計算環境的蟻群優化計算資源分配算法[J]. 華東師范大學學報（自然科學版）,2010(1): 127-134.

[9]. ZW, G., K. JH, and L. GV. A new heuristic optimization algorithm: harmony search.Simulation[J], 2001, 76(2): 60-68.

[10]. Z. Geem, J. Kim, G. Loganathan. Harmony search optimization: application to pipe network design[J]. International Journal of Model Simulation, 2002, 22(2): 125–133.

[11].Geem, Z.W. Optimal cost design of water distribution networks using harmony search[J].Engineering Optimization, 2006,38(3):259-277.

[12].Fesanghary, M. et al. Hybridizing harmony search algorithm with sequential quadratic programming for engineering optimization problems[J]. Computer Methods in Applied Mechanics and Engineering,2008,197(33–40):3080-3091.

[13].武磊,潘金科,等. 求解零空閑流水線調度問題的和聲搜索算法[J]. 計算機集成制造系統,2009,15(10): 1960-1967.

[14]. Xiao-Zhi, G.. A New Harmony Search method in optimal wind generator design[C]. XIX International Conference on Electrical Machines - ICEM 2010,Rome,2010/9/6-8:(1-6).

[15].雍龍泉. 和聲搜索算法研究進展. 計算機系統應用[J], 2011. 20(7):244-248.

[16].Buyya, R. and M. Murshed. GridSim: a toolkit for the modeling and simulation of distributed resource management and scheduling for Grid computing[J]. Concurrency and Computation:Practice and Experience,2002,14(13-15): 1175-1220.