祁鵬年，朱 晉，郝君慧，許豐平

(長沙理工大學(xué)經(jīng)濟與管理學(xué)院，湖南 長沙 410114)

0 引言

Hadoop 數(shù)據(jù)節(jié)點在降速的過程中，盡管系統(tǒng)依然可以運行，但任務(wù)執(zhí)行的速度很慢［1］。這樣雖不會影響任務(wù)執(zhí)行的準(zhǔn)確性，但以犧牲整體性能為代價。Hadoop 推測執(zhí)行算法，在同構(gòu)環(huán)境下通過提高任務(wù)執(zhí)行的效率來有效地提高整體性能，但在異構(gòu)環(huán)境下反而會降低系統(tǒng)性能［2］。人們希望即使在異構(gòu)環(huán)境下，Hadoop 推測執(zhí)行算法照樣可以提高系統(tǒng)性能。本文重點研究Hadoop 推測執(zhí)行算法在異構(gòu)環(huán)境下所表現(xiàn)出的性能問題以及對應(yīng)的改進算法。

1 Hadoop 推測執(zhí)行算法

1.1 基本原理

MapReduce 實現(xiàn)了作業(yè)的分割，將待執(zhí)行的作業(yè)分成一些小分片，然后執(zhí)行每一個小分片，通過作業(yè)執(zhí)行的整體時間小于順序執(zhí)行時間來提高作業(yè)執(zhí)行的效率。當(dāng)MapReduce 接收到任務(wù)時，這些任務(wù)的執(zhí)行過程對于用戶是完全透明的［3］。在某些分片執(zhí)行過程中總會存在可用但執(zhí)行效率較低的數(shù)據(jù)節(jié)點，這類分片被稱為掉隊者［4］。為了盡可能縮短計算時間，提高整體性能，MapReduce 會啟動其他運行效率較高的數(shù)據(jù)節(jié)點來處理掉隊者。MapReduce 的這種優(yōu)化策略被稱為推測執(zhí)行［5］(Speculation Execution)，被推測執(zhí)行的任務(wù)叫做后備任務(wù)。

1.2 任務(wù)處理流程

1)用(0，1)之間的數(shù)作為任務(wù)進度數(shù)，該數(shù)用于表示任務(wù)的進度情況。其中，Map 進度數(shù)和Reduce進度數(shù)是Hadoop 推測執(zhí)行算法的2 種進度數(shù)。在Map 階段，執(zhí)行進度=已完成的數(shù)據(jù)/輸入的數(shù)據(jù)［6］。而在Reduce 階段將任務(wù)分為輸入數(shù)復(fù)制階段、排序階段、歸并階段，每個階段各占1/3 的進度。每一個任務(wù)階段都會計算出一個進度數(shù)來表示任務(wù)的完成情況。

2)由設(shè)置的閾值來判斷掉隊者。

當(dāng)開始執(zhí)行所有任務(wù)時，JobTracker 會分別計算出Map、Reduce 的進度數(shù)，設(shè)置平均進度數(shù)值減0.2為閾值［7］。若某個任務(wù)同時滿足進度數(shù)低于閾值并且至少執(zhí)行1 分鐘這2 個條件，則判斷該任務(wù)為掉隊者。

3)執(zhí)行后備任務(wù)。

JobTracker 會啟動一個效率較高的節(jié)點來執(zhí)行該后備任務(wù)，若其中一個先執(zhí)行完，則另一個就被殺死。

1.3 存在的問題

同構(gòu)環(huán)境中推測執(zhí)行算法默認(rèn)滿足的條件［8］:

1)每一個節(jié)點的處理速度相同。

2)在整個運行中，每一個任務(wù)的運行速率相同。

3)后備任務(wù)的運行不會產(chǎn)生時間和資源上的消耗。

4)Map 階段，執(zhí)行進度=已完成的數(shù)據(jù)/輸入的數(shù)據(jù)。Reduce 階段將任務(wù)分為輸入數(shù)復(fù)制階段、排序階段、歸并階段，每個階段各占1/3 的進度。

5)每一個作業(yè)都是批量完成的，所以進度數(shù)較小的任務(wù)判定為掉隊者。

只要滿足了以上條件，在機群同構(gòu)環(huán)境中該推測執(zhí)行算法可以有效提高整體性能，將當(dāng)前響應(yīng)時間提高44%。但面對大量存在的異構(gòu)機群，該策略的高效性將不復(fù)存在。甚至?xí)斐梢韵潞蠊?］:

1)造成節(jié)點效率不佳的原因有很多，導(dǎo)致任務(wù)執(zhí)行效率差異很大。

2)一臺計算機上運行若干個虛擬機，在這些虛擬環(huán)境中使用一個固定的閾值來判斷掉隊者，會導(dǎo)致同一時刻出現(xiàn)大量的掉隊者，出現(xiàn)競爭資源和消耗時間的狀況。

3)異構(gòu)環(huán)境中的節(jié)點可能存在差異，執(zhí)行任務(wù)時也可能不是一個批次，執(zhí)行過程中可能會出現(xiàn)舊批次的某個任務(wù)比新批次的進度數(shù)要高，但是執(zhí)行速度卻比新任務(wù)慢，而在調(diào)度后備任務(wù)時可能會先調(diào)度新任務(wù)，造成有些掉隊者任務(wù)一直無法執(zhí)行。

所以，該策略在異構(gòu)環(huán)境中會導(dǎo)致過度重復(fù)執(zhí)行掉隊者任務(wù)，使得整體性能比沒有使用該策略時的性能更差。因此，Hadoop 推測執(zhí)行算法在同構(gòu)環(huán)境下可以發(fā)揮優(yōu)勢，但在異構(gòu)環(huán)境下可能無法判斷真正的掉隊者。

1.4 異構(gòu)環(huán)境下的解決方案——SALS 算法

為了彌補Hadoop 推測執(zhí)行算法在異構(gòu)環(huán)境下的諸多弊病，有人提出了自適應(yīng)負(fù)載調(diào)節(jié)算法(SALS)，它可以在一定程度上提高Hadoop 性能［10］。其核心思想如下:

1)利用公式(1)求得此刻所有運行任務(wù)的剩余時間，并將其存放在TaskQueue 中。

其中，PS 指歷史進度數(shù)，t 為歷史運行時間，而PR=PS/t，為任務(wù)執(zhí)行的歷史平均速度。

2)利用公式(2)求得閾值(NodeThreshold)，將每一個任務(wù)請求節(jié)點的進度值與該閾值相比較，小于閾值的節(jié)點存放到Queue 隊列中。

3)利用式(3)、式(4)分別求出系統(tǒng)平均負(fù)載和當(dāng)前系統(tǒng)負(fù)載。并利用式(5)求得當(dāng)前系統(tǒng)可計算后備任務(wù)數(shù)量sTask(其中，blocksize 是每一個Map 任務(wù)所處理的數(shù)據(jù)量)。

4)從TaskQueue 中讀取sTask 個后備任務(wù)，交給Queue 隊列中的前sTask 個任務(wù)執(zhí)行。

由以上可知，該算法采用了更精確的方式來判斷掉隊者并且充分考慮了系統(tǒng)負(fù)載的情況［11］，利用當(dāng)前負(fù)載量自動調(diào)節(jié)后備任務(wù)的數(shù)量，來實現(xiàn)系統(tǒng)的負(fù)載均衡。但依然存在問題，如將所有任務(wù)都放在TaskQueue 中會造成資源的浪費、忽略Reduce 任務(wù)，造成系統(tǒng)負(fù)載不準(zhǔn)確、僅采用Map 處理的數(shù)據(jù)量作為衡量系統(tǒng)負(fù)載的標(biāo)準(zhǔn)等問題［12］。

2 Hadoop 推測執(zhí)行算法優(yōu)化

由于Hadoop 推測執(zhí)行算法不適合應(yīng)用在異構(gòu)環(huán)境下，而SALS 算法在異構(gòu)環(huán)境中也存在諸多問題［13］，如:判斷掉隊者時浪費了大量的內(nèi)存空間且存在系統(tǒng)負(fù)載均衡問題。所以本文改進了Hadoop 推測執(zhí)行算法，簡稱為ESE(Enhanced Speculation Execution)算法，ESE 算法采用了不同的掉隊者判斷方法和新的負(fù)載均衡算法。利用當(dāng)前系統(tǒng)負(fù)載量自動分配后備任務(wù)執(zhí)行，以此均衡系統(tǒng)負(fù)載。

2.1 ESE 算法的核心思想

跟SALS 算法利用剩余時間判斷掉隊者一樣，推測執(zhí)行算法利用進度數(shù)判斷異構(gòu)環(huán)境下的掉隊者也存在一定的盲目性。但是ESE 算法依然采用了Zaharia 利用歷史平均剩余完成時間來估算剩余時間的思想。與SALS 算法不同點在于，該算法會將任務(wù)剩余時間大于20%的任務(wù)標(biāo)識為掉隊者。任務(wù)剩余時間通過公式(1)求出。為了防止任務(wù)數(shù)量過多時，使用SALS 算法將所有任務(wù)信息都存儲到TaskQueue中，造成內(nèi)存浪費，并且受Hadoop 推測執(zhí)行算法的啟發(fā)，ESE 算法僅將Tleft(任務(wù)剩余時間)大于20%的任務(wù)信息存到TaskQueue 中，有效減少了內(nèi)存開銷。根據(jù)請求任務(wù)節(jié)點的閾值(NodeThreshod)，將其分為快節(jié)點和慢節(jié)點，而改進后的ESE 算法會選擇性能較好的快節(jié)點執(zhí)行后備任務(wù)，使得掉隊者獲得比原來更快的執(zhí)行速度。利用Zaharia 的LATE 算法［14］，取節(jié)點平均速度的1/4 作為閾值，該值可以使用式(6)求得:

其中n 為節(jié)點個數(shù)，m 指每一個節(jié)點已經(jīng)完成和正在執(zhí)行的任務(wù)的總和。PS［i］［j］表示第i 個節(jié)點上，第j 個任務(wù)的歷史平均進度值。Task［i］［j］指第i 個節(jié)點的第j 個任務(wù)，值一般設(shè)置為1，對閾值沒有影響。

式(7)可求出每一個節(jié)點的進度水平:

其中，m 是該節(jié)點上的任務(wù)總和(m=已完成任務(wù)數(shù)+沒有完成的任務(wù)數(shù))。Task［j］則是該節(jié)點上的某個任務(wù)，其值也可以設(shè)置為1。如果滿足NodePLNumber ＞NodeThreshold，即為快節(jié)點否則為慢節(jié)點。

系統(tǒng)負(fù)載量一般指的是，當(dāng)系統(tǒng)同時運行Task和Reduce 時的負(fù)載量。用Map 和Reduce 任務(wù)的數(shù)量值來確定系統(tǒng)的負(fù)載量，分別記為TaskNumber、ReduceNumber。故在t 時刻系統(tǒng)需要處理的負(fù)載量為:

系統(tǒng)平均負(fù)載是由從作業(yè)開始執(zhí)行到此刻已經(jīng)完成和正在執(zhí)行的數(shù)據(jù)量的總和的平均值，由式(9)求出。

系統(tǒng)在某時刻的負(fù)載量低于系統(tǒng)平均負(fù)載量時，允許申請新節(jié)點，否則不允許，直至低于系統(tǒng)平均負(fù)載量為止。

2.2 改進后算法的執(zhí)行流程

1)當(dāng)同時有多個節(jié)點發(fā)出請求時，首先要將每一個節(jié)點的進度水平與閾值進行比較，進而忽略慢節(jié)點的請求。然后判斷快節(jié)點是Map 請求還是Reduce請求，隨后加入到對應(yīng)的MNodeQueue 或RNode-Queue 隊列中并按照節(jié)點進度排序。C1、C2 分別用于2 個隊列的計數(shù)。

2)獲得請求任務(wù)分配的信息后，根據(jù)公式計算此刻正在運行的所有任務(wù)，大概估算每個任務(wù)的剩余時間，將剩余時間大于0.2 的任務(wù)按剩余時間排序并根據(jù)任務(wù)類型放入MTaskQueue 隊列或RTaskQueue隊列中。

3)計算某一時刻的系統(tǒng)負(fù)載值L 和平均負(fù)載值，若L 小于平均負(fù)載值，執(zhí)行步驟4)，否則一段時間后繼續(xù)執(zhí)行步驟3)。

4)計算sTask 的值(sTask=系統(tǒng)負(fù)載-系統(tǒng)平均負(fù)載)，以及Map 可以分配到的任務(wù)數(shù)量x=× sTask 和Reduce 分配到的任務(wù)數(shù)量y=×sTask。將MTaskQueue 的前x 個任務(wù)分配給MNodeQueue 隊列中的前x 個節(jié)點，而RTaskQueue也是同理，并分別更新隊列中的信息。

3 ESE 算法的實驗證明

本文通過實驗證明新Hadoop 推測執(zhí)行算法的可行性。在異構(gòu)環(huán)境下搭建分布式平臺，整個集群由8個節(jié)點組成，其中一個節(jié)點為主控節(jié)點(Master)，而剩余節(jié)點為工作節(jié)點(Slave)。在該配置下對改進后的新算法，原推測執(zhí)行算法以及SLAS 算法進行性能比較，由此得出一些重要的結(jié)論。

3.1 實驗環(huán)境搭建及參數(shù)配置

將這8 個節(jié)點組成一個小型局域網(wǎng)，相關(guān)參數(shù)如表1 所示。

表1 集群相關(guān)參數(shù)

安裝完操作系統(tǒng)、JDK 等相關(guān)軟件之后再安裝Hadoop 并實現(xiàn)相應(yīng)的配置。首先為每一個節(jié)點創(chuàng)建一個用戶組hadoop-user，并在該用戶組下創(chuàng)建Hadoop 用戶。然后修改每個節(jié)點的/etc/hosts 目錄并在NameNode 節(jié)點的配置文件中添加集群中所有節(jié)點的IP 地址和主機名。最后需要配置SSH 以及在所有的電腦上完成Hadoop 的配置。

3.2 實驗結(jié)果分析

本實驗借助Hadoop 自帶的字?jǐn)?shù)統(tǒng)計程序，對改進后的推測執(zhí)行算法、SALS 算法、Hadoop 推測執(zhí)行算法以及不使用推測執(zhí)行算法在實驗中的響應(yīng)時間以及每個節(jié)點的負(fù)載情況進行對比。基本思想是:先統(tǒng)計輸入文件中的所有單詞數(shù)目信息，然后匯總所有的統(tǒng)計結(jié)果［15］。本實驗將3 個job 同時提交，并保證其他所有的參數(shù)都相同，得到了圖1 的實驗結(jié)果。

圖1 異構(gòu)環(huán)境下各算法性能對比

由圖1 可知:在異構(gòu)環(huán)境下Hadoop 自帶的推測執(zhí)行算法處理數(shù)據(jù)的能力遠(yuǎn)低于SALS 算法和改進后的推測執(zhí)行算法甚至低于不使用推測執(zhí)行時的數(shù)據(jù)處理能力。這一事實說明Hadoop 推測執(zhí)行算法不適合應(yīng)用于異構(gòu)環(huán)境中［16］。除此之外，還可以得知改進后的Hadoop 推測執(zhí)行算法在處理job1、job2、job3 時所耗費的時間明顯比SALS 算法少。這是因為將任務(wù)寫入TaskQueue 中時，有一部分經(jīng)過判斷不需要寫入隊列，因此節(jié)省了操作時間。雖然改進后的Hadoop 推測執(zhí)行算法相比于SALS 算法響應(yīng)時間只有小部分提高，但整體來看比SALS 算法更高效。

根據(jù)實驗結(jié)果，進一步對比分析了各個節(jié)點在執(zhí)行任務(wù)中所需的時間，如圖2 所示。

圖2 各個節(jié)點在job3 上的執(zhí)行時間對比

由圖2 可知:雖然job3 執(zhí)行的時間是固定的，但該任務(wù)在每一個節(jié)點上的執(zhí)行時間幅度較大，導(dǎo)致系統(tǒng)負(fù)載不均衡，使得有些節(jié)點任務(wù)過重而有些節(jié)點過早完成。使用Hadoop 推測執(zhí)行算法與不使用相比較得知，不使用時盡管運行時間較長但各節(jié)點基本同步，所以比使用該算法有更好的負(fù)載均衡。這進一步證明，異構(gòu)環(huán)境下不適合啟用推測執(zhí)行算法。此外，比較改進后的推測執(zhí)行算法與SALS 算法，可以知道二者作業(yè)執(zhí)行的時間相同，但在每個節(jié)點上執(zhí)行的時間上下波動，改進后的算法比SALS 更平穩(wěn)，這就說明改進后的Hadoop 推測執(zhí)行算法在解決系統(tǒng)負(fù)載均衡方面明顯優(yōu)于SALS 算法。同時也證明了改進后的推測執(zhí)行算法確實具有高效性。

4 結(jié)束語

本文提出了一種適用于異構(gòu)環(huán)境下的Hadoop 推測執(zhí)行算法，該算法避開了原算法在異構(gòu)環(huán)境下的種種弊端，用一種全新的機制實現(xiàn)了推測執(zhí)行策略;并搭建了分布式平臺驗證新算法的性能，結(jié)果進一步證明了新算法的合理性和可行性。本文所有結(jié)論皆由實驗驗證，具有一定的科學(xué)依據(jù)。

［1］Apache Software Foundation.Hadoop 0.20.2 API［DB/OL］.http://hadoop.apache.org/common/docs，2015-03-01.

［2］Tom White.Hadoop 權(quán)威指南［M］.周敏奇，王曉玲，譯.2 版.北京:清華大學(xué)出版社，2011.

［3］陳國良.并行計算［M］.北京:高等教育出版社，2003.

［4］陸嘉恒.Hadoop 實戰(zhàn)Hadoop Action［M］.北京:機械工業(yè)出版社，2011.

［5］Anderson T E，Culler D E，Patternson D A.A case for NOW［J］.IEEE Micro，1995，15(1):54-64.

［6］李鑫.Hadoop 框架的擴展和性能調(diào)優(yōu)［D］.西安:西安建筑科技大學(xué)，2012.

［7］Chuck Lam.Hadoop in Ation［M］.Manning Publications，2010.

［8］曹英.大數(shù)據(jù)環(huán)境下Hadoop 性能優(yōu)化的研究［D］.大連:大連海事大學(xué)，2013.

［9］趙書蘭.典型的Hadoop 云計算［M］.北京:電子工業(yè)出版社，2013.

［10］韓晶.大數(shù)據(jù)服務(wù)若干關(guān)鍵技術(shù)研究［D］.北京:北京郵電大學(xué)，2013.

［11］張密密.MapReduce 模型在Hadoop 實現(xiàn)中的性能分析及改進優(yōu)化［D］.成都:電子科技大學(xué)，2010.

［12］沈案.異構(gòu)分布式系統(tǒng)中基于DVS 的節(jié)能調(diào)度算法研究與實現(xiàn)［D］.長沙:湖南大學(xué)，2013.

［13］馮艷紅.實時多任務(wù)集成調(diào)度算法的研究［D］.保定:華北電力大學(xué)，2005.

［14］王峰.Hadoop 集群作業(yè)的調(diào)度算法［J］.程序員，2009(12):119-121.

［15］周鋒，李旭偉.一種改進的MapReduce 并行編程模型［J］.科協(xié)論壇(下半月)，2009(2):65-66.

［16］孫廣中，肖鋒，熊曦.MapReduce 模型的調(diào)度及容錯機制研究［J］.微電子學(xué)與計算機，2007，24(9):178-180.

［17］曹廷.一個異構(gòu)多核調(diào)度算法及其實現(xiàn)［D］.西安:西安電子科技大學(xué)，2011.

［18］余利華.分布式數(shù)據(jù)存儲和處理的若干技術(shù)研究［D］.杭州:浙江大學(xué)，2008.

［19］王意潔，孫偉東，周松，等.云計算環(huán)境下的分布存儲關(guān)鍵技術(shù)［J］.軟件學(xué)報，2012，23(4):962-986.

［20］李建江，崔健，王聃，等.MapReduce 并行編程模型研究綜述［J］.電子學(xué)報，2011，39(11):2635-2642.