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

0 引言

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

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

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

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

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

ACO-HCO效能優(yōu)化機(jī)制的主要運(yùn)作過程為三個(gè)階段：(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)練資料與測(cè)試數(shù)據(jù)集，利用基因表達(dá)編程法[7]，建立Hadoop參數(shù)與效能關(guān)聯(lián)模型；(3)在ACO-HCO參數(shù)優(yōu)化階段，蟻群算法會(huì)依據(jù)Hadoop參數(shù)與效能關(guān)聯(lián)模型，針對(duì)荷爾蒙與狀態(tài)轉(zhuǎn)換機(jī)率完成初始化，然后通過蟻群算法的啟發(fā)式搜尋過程[8]，產(chǎn)生Hadoop平臺(tái)優(yōu)化參數(shù)結(jié)果。最終，在Hadoop叢集上，針對(duì)給定的Hadoop程序、原始輸入數(shù)據(jù)與ACO-HCO的優(yōu)化參數(shù)設(shè)定，觀察Hadoop應(yīng)用程序的執(zhí)行效能變化情形。

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

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

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

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

2.2 GEP實(shí)際結(jié)果

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

當(dāng)GEP演化過程的世代數(shù)量從20 000個(gè)調(diào)整至80 000個(gè)時(shí)，可以得到最終染色體質(zhì)量(適應(yīng)值與訓(xùn)練樣本數(shù)量的比例)大于90%的結(jié)果。因此，實(shí)驗(yàn)過程將GEP演化過程的世代數(shù)量設(shè)定為80 000個(gè)，并采用典型的基因調(diào)整活動(dòng)發(fā)生概率參數(shù)，包含單點(diǎn)重組率(0.3)、插入轉(zhuǎn)換率(0.1)，反轉(zhuǎn)率(0.1)與基因突變率(0.44)。在完成80 000個(gè)迭代的GEP演化過程后，GEP最終輸出一個(gè)能夠代表Hadoop程序的運(yùn)行時(shí)間與10個(gè)重要參數(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è)定值時(shí)，即可通過上式得到Hadoop程序的預(yù)估運(yùn)行時(shí)間。因此，上式將作為ACO-HCO參數(shù)優(yōu)化階段，螞蟻選擇下一個(gè)參數(shù)節(jié)點(diǎn)的目標(biāo)函數(shù)，預(yù)估運(yùn)行時(shí)間越短的Hadoop參數(shù)節(jié)點(diǎn)對(duì)螞蟻的吸引力則越強(qiáng)。

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

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

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

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

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

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

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

(2)

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

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

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

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

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

(4)

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

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

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

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

(5)

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

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

步驟5：更新最佳路徑

若min(Ls)

步驟6：測(cè)試停止條件

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

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

4.1 實(shí)驗(yàn)準(zhǔn)備

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

4.2 WordCount效能測(cè)試

如圖2所示。

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

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

4.3 Sort效能測(cè)試

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

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

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

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

4.4 MR-based LSB效能測(cè)試

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

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

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

5 總結(jié)

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