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

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

0 引言

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

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

1.1 基本原理

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

1.2 任務(wù)處理流程

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

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

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

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

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

1.3 存在的問題

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

1)每一個(gè)節(jié)點(diǎn)的處理速度相同。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1 ESE 算法的核心思想

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

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

式(7)可求出每一個(gè)節(jié)點(diǎn)的進(jìn)度水平:

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

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

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

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

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

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

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

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

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

3 ESE 算法的實(shí)驗(yàn)證明

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

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

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

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

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

3.2 實(shí)驗(yàn)結(jié)果分析

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

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

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

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

圖2 各個(gè)節(jié)點(diǎn)在job3 上的執(zhí)行時(shí)間對(duì)比

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

4 結(jié)束語

本文提出了一種適用于異構(gòu)環(huán)境下的Hadoop 推測(cè)執(zhí)行算法，該算法避開了原算法在異構(gòu)環(huán)境下的種種弊端，用一種全新的機(jī)制實(shí)現(xiàn)了推測(cè)執(zhí)行策略;并搭建了分布式平臺(tái)驗(yàn)證新算法的性能，結(jié)果進(jìn)一步證明了新算法的合理性和可行性。本文所有結(jié)論皆由實(shí)驗(yàn)驗(yàn)證，具有一定的科學(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］陳國(guó)良.并行計(jì)算［M］.北京:高等教育出版社，2003.

［4］陸嘉恒.Hadoop 實(shí)戰(zhàn)Hadoop Action［M］.北京:機(jī)械工業(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 框架的擴(kuò)展和性能調(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 云計(jì)算［M］.北京:電子工業(yè)出版社，2013.

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

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

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

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

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

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

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

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

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

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

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