基于蟻群算法優(yōu)化Hadoop平臺計算效能方法

(寧夏財經(jīng)職業(yè)技術(shù)學(xué)院 信息與智能工程系,銀川 750021)

0 引言

許多大型網(wǎng)站公司通過在世界各地建置大量服務(wù)器，為其它企業(yè)和民眾提供龐大服務(wù)器群的運算能力與儲存資源，讓使用者可利用任何具備網(wǎng)頁瀏覽器功能的設(shè)備，通過互聯(lián)網(wǎng)就能夠快速使用該公司所提供的軟件運算與儲存功能，而這樣的一種新型網(wǎng)絡(luò)應(yīng)用概念，就是“云計算”[1]。隨著云計算的大量建置，伴隨而來的是大數(shù)據(jù)(Big Data)[2]。而大數(shù)據(jù)對云端平臺與應(yīng)用程序所帶來了容量大、增加快、多樣性、可信度的等四個效能挑戰(zhàn)特性[3]。目前云服務(wù)的運算架構(gòu)主要是MapReduce分散式處理架構(gòu)，而Hadoop MapReduce是對應(yīng)參考MapReduce運算架構(gòu)與分布式系統(tǒng)等關(guān)鍵技術(shù)[4]，以Java程序語言實現(xiàn)同時具備分布式儲存與分布式計算能力的整合式解決方式。目前，Hadoop平臺已相當(dāng)普及，但應(yīng)用程序若是在Hadoop平臺上使用預(yù)設(shè)參數(shù)值的情況下執(zhí)行，其執(zhí)行效能將不如預(yù)期[5]。

因此，本文針對大數(shù)據(jù)在Hadoop平臺數(shù)據(jù)運算的效能問題，結(jié)合基因表達編程與蟻群算法的Hadoop平臺云計算效能的優(yōu)化研究(ACO-based Hadoop Configuration Optimization，ACO-HCO)，主要結(jié)合基因表達編程與蟻群優(yōu)化算法等相關(guān)技術(shù)，基于Hadoop的工作歷史紀(jì)錄，找出Hadoop平臺的參數(shù)與計算效能關(guān)聯(lián)模型，作為啟發(fā)式搜尋的目標(biāo)函數(shù)，并利用蟻群算法快速收斂的特性，結(jié)合Hadoop平臺參數(shù)與效能關(guān)聯(lián)模型，搜尋出一組優(yōu)化參數(shù)，從而改善應(yīng)用程序的執(zhí)行效能。

1 效能優(yōu)化機制整體架構(gòu)

由于Hadoop平臺的執(zhí)行效能除了受到Hadoop參數(shù)設(shè)定的影響之外，也會受到系統(tǒng)資源、軟件與網(wǎng)絡(luò)的影響，因此，本文所提出的ACO-HCO效能優(yōu)化機制主要有3個特性：(1)收集Hadoop工作歷史紀(jì)錄，避免產(chǎn)生額外負(fù)載，導(dǎo)致潛在的模型錯誤問題；(2)考慮參數(shù)設(shè)定與運行時間復(fù)雜的非線性關(guān)系；(3)能夠快速收斂產(chǎn)生優(yōu)化參數(shù)結(jié)果。

本文所提ACO-HCO效能優(yōu)化機制的整體架構(gòu)圖,如圖1所示。

ACO-HCO效能優(yōu)化機制的主要運作過程為三個階段：(1)在ACO-HCO特征分析階段，通過Hadoop工作特征分析器(Job Log Parser)讀取Hadoop程序輸出路徑中的工作歷史日志目錄[6]，輸出符合參數(shù)關(guān)聯(lián)建模方法所需的模型輸入數(shù)據(jù)格式；(2)在ACO-HCO參數(shù)與效能關(guān)聯(lián)建模階段，將Hadoop特征分析的結(jié)果區(qū)分為訓(xùn)練資料與測試數(shù)據(jù)集，利用基因表達編程法[7]，建立Hadoop參數(shù)與效能關(guān)聯(lián)模型；(3)在ACO-HCO參數(shù)優(yōu)化階段，蟻群算法會依據(jù)Hadoop參數(shù)與效能關(guān)聯(lián)模型，針對荷爾蒙與狀態(tài)轉(zhuǎn)換機率完成初始化，然后通過蟻群算法的啟發(fā)式搜尋過程[8]，產(chǎn)生Hadoop平臺優(yōu)化參數(shù)結(jié)果。最終，在Hadoop叢集上，針對給定的Hadoop程序、原始輸入數(shù)據(jù)與ACO-HCO的優(yōu)化參數(shù)設(shè)定，觀察Hadoop應(yīng)用程序的執(zhí)行效能變化情形。

圖1 ACO-HCO效能優(yōu)化機制的整體架構(gòu)圖

2 ACO-HCO參數(shù)關(guān)聯(lián)建模

2.1 GEP應(yīng)用設(shè)計

在GEP應(yīng)用設(shè)計部分，針對Hadoop參數(shù)設(shè)定與運行時間而言，Hadoop的運行時間ET是參數(shù)集(x0,x1,…,xn)的一個函數(shù)。根據(jù)GEP演化機制，能夠挖掘出重要Hadoop平臺參數(shù)與效能關(guān)聯(lián)模型。ACO-HCO利用GEP的染色體儲存Hadoop平臺參數(shù)，每個GEP染色體是由以Hadoop平臺參數(shù)作為輸入，經(jīng)由演化程序最終產(chǎn)生預(yù)測運行時間與實際運行時間最為接近的染色體[9]，并譯碼為表示樹，輸出形式為f(x0,x1,…,xn)。

2.2 GEP實際結(jié)果

在GEP實際結(jié)果部分，GEP算法[10]的輸入項是一組經(jīng)由Hadoop工作特征分析器所過濾產(chǎn)生的Hadoop工作的執(zhí)行樣本，作為GEP方法的模型輸入數(shù)據(jù)。而這些數(shù)據(jù)的產(chǎn)生方式是通過實驗環(huán)境的Hadoop平臺，實驗所使用的Hadoop程序包含內(nèi)建的WordCount與Sort程序，并使用5GB、10GB與15GB的輸入數(shù)據(jù)。每次實驗過程隨機調(diào)整參數(shù)設(shè)定，母種Hadoop程序執(zhí)行三次計算后的平均執(zhí)行時間。

當(dāng)GEP演化過程的世代數(shù)量從20 000個調(diào)整至80 000個時，可以得到最終染色體質(zhì)量(適應(yīng)值與訓(xùn)練樣本數(shù)量的比例)大于90%的結(jié)果。因此，實驗過程將GEP演化過程的世代數(shù)量設(shè)定為80 000個，并采用典型的基因調(diào)整活動發(fā)生概率參數(shù)，包含單點重組率(0.3)、插入轉(zhuǎn)換率(0.1)，反轉(zhuǎn)率(0.1)與基因突變率(0.44)。在完成80 000個迭代的GEP演化過程后，GEP最終輸出一個能夠代表Hadoop程序的運行時間與10個重要參數(shù)間的關(guān)聯(lián)函數(shù)：

f(x0,x1,…,xn)=

(x6+x4)×(x8+x9)

(1)

其中，a=sqrt(x0×x8+x3×x1)，b=pow(x5,(x2+x1))。當(dāng)輸入?yún)?shù)x0至x9的設(shè)定值時，即可通過上式得到Hadoop程序的預(yù)估運行時間。因此，上式將作為ACO-HCO參數(shù)優(yōu)化階段，螞蟻選擇下一個參數(shù)節(jié)點的目標(biāo)函數(shù)，預(yù)估運行時間越短的Hadoop參數(shù)節(jié)點對螞蟻的吸引力則越強。

3 ACO-HCO參數(shù)優(yōu)化算法

ACO-HCO參數(shù)優(yōu)化的執(zhí)行步驟如下：

步驟1：初始化及ACO參數(shù)設(shè)定

給定程序運行時間上限(tmax)、螞蟻數(shù)量(S)、初始荷爾蒙濃度(τ0)、探索或追隨偏向程度參數(shù)(q0)、荷爾蒙衰退參數(shù)(ρ)、荷爾蒙重要程度參數(shù)(α)、執(zhí)行時間長短重要程度參數(shù)(β)。

步驟2：建構(gòu)最佳參數(shù)節(jié)點路徑

若x0為起始狀態(tài)，則將S只螞蟻隨機放置在Hadoop參數(shù)節(jié)點上。每只螞蟻從目前所在節(jié)點出發(fā)，計算轉(zhuǎn)換規(guī)則[11]，以便選擇下一個拜訪節(jié)點、逐步完成一趟完整的里程。

轉(zhuǎn)換規(guī)則如式(2)。

(2)

其中，Js(i)是位于節(jié)點i的螞蟻s尚未拜訪的鄰近節(jié)點集合，而不屬于Js(i)的節(jié)點或是拜訪過的節(jié)點，其選擇機率為0，這樣的設(shè)計可避免螞蟻重復(fù)經(jīng)過相同節(jié)點；τiu(t)為線段(i,u)在時間t的荷爾蒙濃度，ηiu是選擇候選參數(shù)值的期望值。q為(0,1)間呈現(xiàn)均勻分布的隨機數(shù)，q0為設(shè)定參數(shù)，0≤q0≤1。maxf(x)是找出高荷爾蒙濃度(τ)及GEP目標(biāo)函數(shù)最小預(yù)測運行時間成本(η)的節(jié)點u，而p為選擇下一節(jié)點的轉(zhuǎn)換機率，由下式計算得到式(3)。

當(dāng)q>q0時，雖然荷爾蒙濃度高且預(yù)測運行時間最短的節(jié)點被選擇的概率較高[12]，但因螞蟻仍以隨機方式選擇節(jié)點，因此概率最高的節(jié)點未必會被選到，因此其行為較偏向探索。當(dāng)q≤q0時，螞蟻被設(shè)定必須選擇荷爾蒙濃度高及預(yù)測運行時間短的節(jié)點，故其行為較偏向追隨。

步驟3：局部更新荷爾蒙濃度

每只螞蟻在找尋一個可行解(可能路徑)的過程中，每經(jīng)過一個邊(i,j)，即對該邊進行一次荷爾蒙更新，以避免其它螞蟻收斂在局部解，并增加路徑找尋的多樣性。更新幅度與目前這群螞蟻的表現(xiàn)及選擇結(jié)果無關(guān)，計算方式如式(4)。

τij(t+1)=(1-ρ)τij(t)+ρτ0

(4)

其中，ρ為荷爾蒙衰退比例參數(shù)，(1-ρ)為荷爾蒙殘留因子，0<ρ<1。區(qū)域更新法使拜訪過的路段的荷爾蒙減少，因此拜訪過的路徑對螞蟻的吸引力越來越小，故可誘導(dǎo)螞蟻偏向開發(fā)新路徑，避免螞蟻局限在定義狹小范圍內(nèi)[13]。返回步驟2直到每只螞蟻均產(chǎn)生一條完整路徑為式(5)。

步驟4：整體更新荷爾蒙濃度

當(dāng)所有螞蟻均完成一條完整路徑后，便執(zhí)行荷爾蒙“整體更新法”以強化目前最佳路徑的荷爾蒙濃度，計算方式如下所示：

τij(t+1)=(1-ρ)τij(t)+ρΔτij

(5)

其中：若路徑(i,j)∈T+，則Δτij=Q/L+；否則Δτij=0，而T+是先前所找到的最佳路徑，L+是先前所找到最佳路徑的總運行時間。Q為表示荷爾蒙強度的參數(shù)，在一定程度上會影響到收斂速度，一般設(shè)為100。

只有表現(xiàn)最好的那一只螞蟻才有遺留荷爾蒙的權(quán)力，原因是只在最好的解上增加費洛蒙的設(shè)計，有助于螞蟻盡快搜尋到最佳解。而目前最佳路徑未必是目前這群螞蟻所找到的，可能是先前螞蟻的搜尋成果。

步驟5：更新最佳路徑

若min(Ls)

步驟6：測試停止條件

ACO停止條件一般設(shè)定為時間到達時間上限時間tmax停止。此時，T+為找到的最佳路徑，L+為其總運行時間；否則，回到步驟2。

4 Hadoop執(zhí)行效能的比較與分析

4.1 實驗準(zhǔn)備

利用所建置的Hadoop實驗叢集環(huán)境，比較ACO-HCO機制、經(jīng)驗法則(RoT)、Starfish機制以及預(yù)設(shè)的Hadoop參數(shù)(Default)下Hadoop執(zhí)行效能。通過配置不同的Hadoop平臺參數(shù)后，在Hadoop實驗叢集環(huán)境，分別執(zhí)行典型的WordCount、Sort效能測試工具程序與特殊應(yīng)用的MR-based LSB程序。其中，WordCount與Sort效能測試工具程序的輸入數(shù)據(jù)量區(qū)分為5GB、10GB、15 GB與20GB四個實驗量級，輸入資料的形態(tài)為文字內(nèi)容，而MR-based LSB程序的輸入數(shù)據(jù)固定為1 500張載體影像圖片文件(Lena.bmp)，用以比較藏密與取密的運行效能的差異。每組實驗執(zhí)行3次，并取運行時間的平均值作為執(zhí)行效能結(jié)果。

4.2 WordCount效能測試

如圖2所示。

圖2 WordCount程序執(zhí)行效能比較

在四種不同輸入數(shù)據(jù)的量級下，ACO-HCO機制的WordCount程序執(zhí)行效能比默認(rèn)值Hadoop平臺執(zhí)行效能的效能改善率為49%，比經(jīng)驗法則的執(zhí)行效能的效能改善率為34%，比Starfish機制的執(zhí)行效能的效能改善率為10%。其中，在輸入數(shù)據(jù)級距為20GB時，最大效能的效能改善率能夠達到53%。

4.3 Sort效能測試

不同機制下Sort程序的執(zhí)行效能比較如圖3所示。

圖3 Sort程序執(zhí)行效能比較

從圖3可以看出，在四種不同輸入數(shù)據(jù)量級下，ACO-HCO的執(zhí)行效能比默認(rèn)值Hadoop平臺的執(zhí)行效能的效能改善率為37%，比經(jīng)驗法則的執(zhí)行效能的效能改善率為30%，比Starfish機制的執(zhí)行效能的效能改善率為20%。其中，在輸入數(shù)據(jù)級距為20GB時，最大效能的效能改善率為44%。

ACO-HCO機制執(zhí)行WordCount程序與Sort程序的效能差異主要原因是由于兩者在執(zhí)行時對系統(tǒng)資源的使用特性不同所導(dǎo)致，WordCount程序執(zhí)行時是屬于CPU密集的運算工作；而Sort程序是屬于中等CPU但硬盤I/O密集的運算工作，由于本文所建置的虛擬化Hadoop實驗環(huán)境，由虛擬化軟件管理共享式磁盤，所有VM都必須在隊列中排隊等候磁盤I/O存取，因此，執(zhí)行硬盤I/O密集的Sort程序時，效能改善率會明顯下降。

4.4 MR-based LSB效能測試

ACO-HOC與經(jīng)驗法則、Starfish機制在藏密效能與取密的效能方面的比較，如圖4所示。

圖4 MR-based LSB程序執(zhí)行效能比較

從圖4可以看出，ACO-HOC 相比于經(jīng)驗法則和Starfish機制的效能改善率分別為6%與3%。由于MR-based LSB程序所處理的輸入數(shù)據(jù)型態(tài)是圖片文件，有別于輸入數(shù)據(jù)型態(tài)為文字型的WordCount與Sort程序能夠?qū)⑤斎霐?shù)據(jù)進行切割處理，MR-based LSB程序的Map任務(wù)在產(chǎn)生Key-Value數(shù)據(jù)文件時，是以整個載體圖像文件做為Vaule的部分，必須耗量大量讀取與寫入本機硬盤I/O的處理時間，因此，ACO-HOC的效能改善率明顯下降。

5 總結(jié)

在Hadoop平臺使用預(yù)設(shè)參數(shù)值執(zhí)行Hadoop應(yīng)用程序會存在效能不佳、人工效能調(diào)校執(zhí)行效率差。ACO-HCO機制通過自動化效能調(diào)校Hadoop平臺參數(shù)，改善Hadoop應(yīng)用程序的執(zhí)行效能，屬于通用性較高的效能調(diào)整方法。ACO-HCO效能優(yōu)化機制主要利用GEP演化機制輸入Hadoop歷史工作紀(jì)錄，建立Hadoop參數(shù)與效能關(guān)聯(lián)模型，并實作蟻群優(yōu)化算法進一步搜尋最佳化參數(shù)設(shè)定。實驗結(jié)果顯示，ACO-HCO機制與采用默認(rèn)值時相比較，能夠明顯改善Hadoop應(yīng)用程序的執(zhí)行效能。此外，ACO-HCO機制也比目前極具代表性的Hadoop參數(shù)優(yōu)化方法，能夠提供更好的執(zhí)行效能。