結(jié)合節(jié)點(diǎn)計(jì)算能力的MapReduce負(fù)載均衡方法

胡林發(fā),付曉東,2,劉 驪,劉利軍

(1.昆明理工大學(xué) 信息工程與自動(dòng)化學(xué)院,昆明 650500;2.昆明理工大學(xué) 云南省計(jì)算機(jī)技術(shù)應(yīng)用重點(diǎn)實(shí)驗(yàn)室,昆明 650500)

0 引 言

隨著互聯(lián)網(wǎng)的迅猛發(fā)展,尤其是移動(dòng)互聯(lián)網(wǎng)的應(yīng)用和大數(shù)據(jù)的普及,數(shù)據(jù)量迎來(lái)爆炸式增長(zhǎng)。MapReduce作為一種分布式計(jì)算模型,被廣泛應(yīng)用在大規(guī)模數(shù)據(jù)并行計(jì)算過(guò)程中[1-2]。目前針對(duì)MapReduce有多種實(shí)現(xiàn),如Apache的開(kāi)源Hadoop框架,將MapReduce和HDFS分布式文件系統(tǒng)進(jìn)行完美融合,深受工業(yè)界和學(xué)術(shù)界的青睞[3]。

數(shù)據(jù)均衡劃分是MapReduce框架在Shuffle階段需要解決的一個(gè)重要問(wèn)題。用戶提交的作業(yè)(Job)由一系列分別運(yùn)行在多臺(tái)機(jī)器上的Map任務(wù)(Mapper)和Reduce任務(wù)(Reducer)處理完成,作業(yè)的完成時(shí)間由運(yùn)行最慢的Reducer決定[4-5]。Hadoop系統(tǒng)默認(rèn)采用Hash分區(qū)方法,即僅根據(jù)關(guān)鍵字的哈希值和分區(qū)個(gè)數(shù)確定關(guān)鍵字的分區(qū),這種劃分方法雖然可以保證每個(gè)分區(qū)里不同關(guān)鍵字種類數(shù)大致相等,但每種關(guān)鍵字?jǐn)y帶的數(shù)據(jù)記錄條數(shù)不一定相等,這會(huì)使各分區(qū)數(shù)據(jù)總量大小相差懸殊,從而導(dǎo)致各節(jié)點(diǎn)負(fù)載不均衡問(wèn)題。研究表明,采用默認(rèn)的Hash分區(qū)方法,超過(guò)90%的作業(yè)任務(wù)出現(xiàn)了Reducer負(fù)載不均衡情況,運(yùn)行時(shí)間高出正常任務(wù)的22%-38%[6]。先完成任務(wù)的節(jié)點(diǎn)需要等待滯后節(jié)點(diǎn)任務(wù)全部完成才能結(jié)束當(dāng)前作業(yè),若中間數(shù)據(jù)過(guò)于集中在某部分Reducer任務(wù)節(jié)點(diǎn),先完成任務(wù)的節(jié)點(diǎn)必須等待其他節(jié)點(diǎn),這個(gè)過(guò)程會(huì)造成集群資源浪費(fèi),延長(zhǎng)整體作業(yè)完成時(shí)間,甚至某些節(jié)點(diǎn)因資源不足導(dǎo)致任務(wù)中斷,使作業(yè)無(wú)法繼續(xù)推進(jìn),從而帶來(lái)不好的用戶體驗(yàn)[7-8]。

文獻(xiàn)[9-10]指出,將Mapper產(chǎn)生的中間數(shù)據(jù)最優(yōu)地劃分到不同分區(qū),使各分區(qū)負(fù)載均衡是一個(gè)NP-Hard問(wèn)題。針對(duì)MapReduce框架中存在的負(fù)載均衡問(wèn)題,目前已有兩階段分區(qū)[11]、多階段分區(qū)[12-13]、數(shù)據(jù)采樣分區(qū)[14-15]、延遲分區(qū)[16]、遷移分區(qū)[17]等方法,這些方法將集群中各節(jié)點(diǎn)看作是計(jì)算能力相同的節(jié)點(diǎn),但在實(shí)際數(shù)據(jù)處理過(guò)程中不同代的硬件環(huán)境會(huì)使每個(gè)節(jié)點(diǎn)計(jì)算能力不相同[18],且不同計(jì)算節(jié)點(diǎn)的性能差異會(huì)影響整個(gè)系統(tǒng)的計(jì)算效率[19]。在異構(gòu)環(huán)境中,即使所有分區(qū)得到相同規(guī)模的數(shù)據(jù),也會(huì)因節(jié)點(diǎn)處理能力不同導(dǎo)致Reduce任務(wù)完成時(shí)間產(chǎn)生巨大差異,存在先完成任務(wù)的節(jié)點(diǎn)等待滯后節(jié)點(diǎn)的問(wèn)題,作業(yè)執(zhí)行時(shí)間因此會(huì)被延長(zhǎng),集群中部分計(jì)算資源會(huì)被閑置,從而降低了作業(yè)處理效率,浪費(fèi)了計(jì)算資源。

本文提出一種結(jié)合節(jié)點(diǎn)計(jì)算能力的劃分方法,即在數(shù)據(jù)劃分時(shí)結(jié)合節(jié)點(diǎn)計(jì)算能力,使各節(jié)點(diǎn)數(shù)據(jù)負(fù)載與節(jié)點(diǎn)自身的計(jì)算能力相匹配,并使大量數(shù)據(jù)在節(jié)點(diǎn)本地處理,降低網(wǎng)絡(luò)傳輸時(shí)延,從而提升作業(yè)的處理效率。本文的主要貢獻(xiàn)包括以下3個(gè)方面。

1)提出在異構(gòu)環(huán)境中使用Reservoir算法對(duì)Map任務(wù)產(chǎn)生的中間數(shù)據(jù)進(jìn)行抽樣,記錄樣本中關(guān)鍵字的位置和頻次,并以此建立關(guān)鍵字分布矩陣。

2)提出一種結(jié)合節(jié)點(diǎn)計(jì)算能力的分區(qū)劃分方法。在制定分區(qū)計(jì)劃時(shí),本文先采用貪心策略對(duì)關(guān)鍵字進(jìn)行初步分區(qū),使各關(guān)鍵字劃分到其頻次最高的節(jié)點(diǎn)對(duì)應(yīng)分區(qū),然后結(jié)合節(jié)點(diǎn)計(jì)算能力并考慮節(jié)點(diǎn)位置關(guān)系對(duì)初步劃分結(jié)果進(jìn)行調(diào)整,使各分區(qū)負(fù)載均衡。

3)設(shè)計(jì)了一種均衡性衡量方法,該方法綜合考慮了數(shù)據(jù)量和節(jié)點(diǎn)的計(jì)算能力值,有利于更加全面地衡量分區(qū)結(jié)果的均衡性。

1 異構(gòu)環(huán)境中負(fù)載均衡問(wèn)題

在MapReduce處理作業(yè)時(shí),作業(yè)任務(wù)分為Map和Reduce任務(wù)。執(zhí)行任務(wù)的函數(shù)均由用戶根據(jù)業(yè)務(wù)需求自定義。將集群中節(jié)點(diǎn)數(shù)記為r,節(jié)點(diǎn)集合為N={n1,n2,…,nr},分區(qū)集合為P={p1,p2,…,pr},其中pj(j=1,2…,r)為一個(gè)分區(qū)。為方便集合節(jié)點(diǎn)計(jì)算能力劃分,這里將pj分區(qū)里所有數(shù)據(jù)作為節(jié)點(diǎn)nj上Reduce任務(wù)的輸入。Map任務(wù)產(chǎn)生的中間數(shù)據(jù)為鍵值對(duì)形式,分區(qū)算法會(huì)將中間數(shù)據(jù)按照關(guān)鍵字劃分到不同分區(qū)。由Reduce任務(wù)輸入限制知,相同關(guān)鍵字的數(shù)據(jù)只能被同一個(gè)Reduce任務(wù)處理,即?i≠j且i,j=1,2,…,r,pi∩pj=?。

分區(qū)集合里每個(gè)分區(qū)的實(shí)際數(shù)據(jù)量大小為S={s1,s2,…,sr},令C={c1,c2,…,cr}表示每個(gè)節(jié)點(diǎn)的計(jì)算能力值,τ(τ>0)為可設(shè)定的閾值,當(dāng)滿足

(1)

時(shí),集群節(jié)點(diǎn)負(fù)載不均衡。

(2)

將分區(qū)劃分方法記為Π(x),則在Shuffle階段關(guān)鍵字kt會(huì)根據(jù)Π(x)計(jì)算得到分區(qū)pj←Π(kt),j=1,2,…,r,然后關(guān)鍵字kt會(huì)被劃分到分區(qū)pj中。此時(shí),其他節(jié)點(diǎn)上關(guān)鍵字為kt的數(shù)據(jù)需要通過(guò)網(wǎng)絡(luò)傳輸?shù)絥j(j=1,2,…,r),則關(guān)鍵字kt需要在網(wǎng)絡(luò)中傳輸?shù)臄?shù)據(jù)總量為

(3)

關(guān)鍵字K={k1,k2,…,kΩ}中所有關(guān)鍵字在經(jīng)過(guò)分區(qū)方法Π(x)劃分之后,共需在網(wǎng)絡(luò)中傳輸?shù)臄?shù)據(jù)總量用VTRS表示,則

(pj=Π(kt),j=1,2,…,r)

(4)

(5)

VTRS值大小取決于VLocality值大小,當(dāng)VLocality越大時(shí),VTRS越小,需要在網(wǎng)絡(luò)中傳輸?shù)臄?shù)據(jù)就會(huì)越少。

在執(zhí)行Reduce任務(wù)時(shí),節(jié)點(diǎn)nj(j=1,2,…,r)上處理pj分區(qū)里的數(shù)據(jù),將pj數(shù)據(jù)總量記為sj,用FoS(factor of skew)值SFoS衡量節(jié)點(diǎn)負(fù)載的均衡性,計(jì)算式為

(6)

因此,本文解決的負(fù)載均衡問(wèn)題為結(jié)合節(jié)點(diǎn)的計(jì)算能力值,尋找一種分區(qū)劃分方法Π(x),使SFoS盡可能小,讓各節(jié)點(diǎn)負(fù)載接近,同時(shí)降低網(wǎng)絡(luò)開(kāi)銷,從而提高作業(yè)的處理效率。

2 結(jié)合節(jié)點(diǎn)計(jì)算能力的負(fù)載均衡方法

針對(duì)異構(gòu)集群環(huán)境中負(fù)載不均衡問(wèn)題,本文提出結(jié)合節(jié)點(diǎn)計(jì)算能力的分區(qū)方法LBCC(load balancing in MapReduce combined with computing capacity)。在節(jié)點(diǎn)加入到集群時(shí),各節(jié)點(diǎn)上運(yùn)行測(cè)試程序,執(zhí)行默認(rèn)計(jì)算任務(wù)。將測(cè)試數(shù)據(jù)集的大小記為V,在節(jié)點(diǎn)nj上任務(wù)完成所需時(shí)間記為Tj,則可得出節(jié)點(diǎn)nj計(jì)算能力值cj=V/Tj,節(jié)點(diǎn)計(jì)算能力值集合記為C={c1,c2,…,cr}。在搭建Hadoop環(huán)境時(shí),利用配置文件core.xml配置節(jié)點(diǎn)的所屬機(jī)架信息,方便后續(xù)利用節(jié)點(diǎn)機(jī)架信息調(diào)整節(jié)點(diǎn)負(fù)載。

為使各節(jié)點(diǎn)負(fù)載均衡并降低Shuffle過(guò)程中網(wǎng)絡(luò)通信開(kāi)銷,本文在執(zhí)行用戶提交的計(jì)算作業(yè)之前,先運(yùn)行一個(gè)抽樣作業(yè)進(jìn)行數(shù)據(jù)抽樣,并統(tǒng)計(jì)樣本數(shù)據(jù)里關(guān)鍵字的位置和頻次分布,由此得到關(guān)鍵字分布矩陣M,然后結(jié)合M和節(jié)點(diǎn)計(jì)算能力值,經(jīng)過(guò)位置劃分篩選高低分區(qū)以及分區(qū)調(diào)整等步驟制定分區(qū)計(jì)劃并將其寫進(jìn)緩存文件fcache。分區(qū)計(jì)劃是計(jì)算作業(yè)分區(qū)劃分的依據(jù),使計(jì)算作業(yè)任務(wù)運(yùn)行時(shí)各節(jié)點(diǎn)負(fù)載均衡,從而提高集群資源的利用率和作業(yè)執(zhí)行效率。

2.1 運(yùn)行抽樣作業(yè)

在抽樣作業(yè)Map階段采用Reservoir抽樣算法對(duì)數(shù)據(jù)集進(jìn)行抽樣,然后在Reduce階段匯總各節(jié)點(diǎn)樣本數(shù)據(jù),依據(jù)樣本里的關(guān)鍵字位置和頻次信息建立關(guān)鍵字分布矩陣,并根據(jù)分布矩陣和節(jié)點(diǎn)計(jì)算能力信息制定分區(qū)計(jì)劃。

在抽樣作業(yè)Map任務(wù)階段,首先初始化一個(gè)關(guān)鍵字集合KL,再按行讀取數(shù)據(jù)集并將數(shù)據(jù)集中的關(guān)鍵字逐一添加進(jìn)KL中,具體過(guò)程如算法1所示。

算法1對(duì)數(shù)據(jù)集中關(guān)鍵字進(jìn)行抽樣

輸入:數(shù)據(jù)集分片β,樣本容量α。

輸出:關(guān)鍵字樣本集合KL.

1.KL←?;

2.cnt←0;

3.forlineinβdo

4.k←getKey(line);

5.cnt++;

6.ifKL.size()<αthen

7.KL.add(k);

8.else

9.t←random.nextInt(0,cnt);

10.ift<αthen

11.KL.replace(t,k);

12.end if

13.end if

14.end for

15.outputKL;

當(dāng)VLocality取最大值時(shí),VTRS取得最小值,需要在網(wǎng)絡(luò)中傳輸?shù)臄?shù)據(jù)量最少。顯然,對(duì)于任意kt,若pj←Π(kt)且滿足

(7)

時(shí),VLocality可以取最大值。這里先采用貪心方法,逐一將K={k1,k2,…,kΩ}里關(guān)鍵字分配到可以使VLocality值取最大值的分區(qū),由此得到初次劃分結(jié)果,然后在此基礎(chǔ)上將各分區(qū)里關(guān)鍵字進(jìn)行調(diào)整,使各分區(qū)負(fù)載接近分區(qū)期望值,具體過(guò)程如算法2所示。

算法2制定分區(qū)計(jì)劃

輸入:二維矩陣M=[mtj]Ω×r,C={c1,c2,…,cr}.

輸出:分區(qū)計(jì)劃P={p1,p2,…,pr}.

1.pj←?(j=1,2,…,r);

2.fort←1 toΩdo

3.mtj←max{mt1,mt2,…,mtr};

4.j←getNodeIndex(mtj);

5.pj←pj.add(kt);

6.end for

8.PH←?,PL←?;

9.forj←1 tordo

12.ifsj>ejthen

13.PH←PH∪{pj};

14.else

15.PL←PL∪{pj};

16.end if

17.end for

18.forh←1 toPH.size() do

19.pi←PH.get(h);

20.forktinpido

21.pj←getMinNearPartition(PL,pi);

22.pj.add(kt);

24.PL.remove(pj);

25.end if

26.pi.remove(kt);

28.break;

29.end if

30.end for

31.end for

32.outputP={p1,p2,…,pr}.

算法2中,第2—第6行表示依次將關(guān)鍵字kt劃分到kt頻次最大的節(jié)點(diǎn)對(duì)應(yīng)分區(qū)上, 直到所有關(guān)鍵字劃分完畢,得到初步劃分結(jié)果P={p1,p2,…,pr}。此時(shí),VLocality取最大值,需要在網(wǎng)絡(luò)中傳輸?shù)臄?shù)據(jù)量最小。然而,此時(shí)并沒(méi)有考慮節(jié)點(diǎn)負(fù)載均衡性,還需要對(duì)初步分區(qū)計(jì)劃進(jìn)行調(diào)整。對(duì)于分區(qū)pj(j=1,2,…,r),sj為pj分區(qū)里數(shù)據(jù)總量,每個(gè)節(jié)點(diǎn)負(fù)載期望值用ej表示,ej表達(dá)式為

(8)

算法2中第7—第17行表示將分區(qū)按照實(shí)際負(fù)載是否高于均衡值劃分為高分區(qū)和低分區(qū),若分區(qū)sj>ej則將pj加入高分區(qū)集合PH,否則加低分區(qū)集合PL。逐漸從高分區(qū)里移出關(guān)鍵字?jǐn)?shù)據(jù),當(dāng)高分區(qū)的實(shí)際總數(shù)據(jù)量低于期望值時(shí)則停止移出。第18—第30行表示收集高分區(qū)里的關(guān)鍵字,并且將從高分區(qū)移出的關(guān)鍵字逐一分配給PL中的低分區(qū),從而使低分區(qū)數(shù)據(jù)量逐漸接近期望值。若在關(guān)鍵字調(diào)整的過(guò)程中,當(dāng)某低分區(qū)實(shí)際數(shù)據(jù)量高于均衡值時(shí),則將該低分區(qū)移出集合PL。

算法2中g(shù)etMinNearPartition方法是為了在集合PL中尋找離分區(qū)pi最近的節(jié)點(diǎn)分區(qū),首先在PL中尋找與pi同一機(jī)架且分區(qū)負(fù)載最小的分區(qū),若存在直接返回,不存在則在其他機(jī)架上尋找,具體過(guò)程如算法3。

算法3getMinNearPartition方法實(shí)現(xiàn)

輸入:低分區(qū)集合PL,分區(qū)pi.

輸出:PL中離pi最近的分區(qū)p.

1.p←null;

2.flag←0;

3.forpjinPLdo

4.ifrack(pi)=rack(pj) then

5.ifp!=null&&getLoad(p)>getLoad(pj)

||p=nullthen

6.p←pj;

7.flag←1;

8.end if

9.end if

10.end for

11.ifflag=1 then

12.returnp;

13.end if

14.returnminLoad(PL);

算法3中第3—第10行表示在集合中尋找與分區(qū)pi關(guān)聯(lián)節(jié)點(diǎn)ni同一機(jī)架的其他節(jié)點(diǎn)對(duì)應(yīng)分區(qū),其中,第4行rack方法的作用是獲取分區(qū)的機(jī)架位置,第5行g(shù)etLoad方法表示求取分區(qū)的實(shí)際負(fù)載大小,分區(qū)pj的負(fù)載計(jì)算方法可表示為

(9)

算法3中第11—第14行表示如果在PL中找到了合適分區(qū)就直接返回,若沒(méi)有找到則利用minLoad方法求取整個(gè)PL集合中負(fù)載最小的分區(qū)作為返回結(jié)果。

算法2初步劃分過(guò)程中,需要遍歷分布矩陣M中所有行,時(shí)間復(fù)雜度為O(Ω·r)。在分區(qū)篩選過(guò)程中遍歷分區(qū)集合P={p1,p2,…,pr},時(shí)間復(fù)雜度為O(r)。在分區(qū)調(diào)整時(shí),需要先將高分區(qū)進(jìn)行排序,這個(gè)過(guò)程時(shí)間復(fù)雜度取決于采用的排序算法,本文采用快速排序,所以時(shí)間復(fù)雜度為O(ΩlogΩ)。在將高分區(qū)里部分關(guān)鍵字調(diào)整到低分區(qū)時(shí),需要通過(guò)算法3尋找合適分區(qū),最好的情況下只有少量關(guān)鍵字需要進(jìn)行調(diào)整,時(shí)間復(fù)雜度為O(r),而在最壞的情況下,大量關(guān)鍵字需要進(jìn)行調(diào)整,此時(shí)時(shí)間復(fù)雜度為O(Ω·r)。綜上,算法2的時(shí)間復(fù)雜度為O(ΩlogΩ)。

整個(gè)抽樣作業(yè)的輸出分區(qū)計(jì)劃為P={p1,p2,…,pr}。為方便計(jì)算作業(yè)利用分區(qū)計(jì)劃進(jìn)行分區(qū),這里將其轉(zhuǎn)化為以關(guān)鍵字kt為鍵、以kt所屬分區(qū)編號(hào)為值的鍵值對(duì)形式,并將其寫入到緩存文件。

2.2 執(zhí)行計(jì)算作業(yè)任務(wù)

計(jì)算作業(yè)以全量數(shù)據(jù)為輸入,并按照制定的計(jì)劃進(jìn)行分區(qū)。在Mapper階段讀取緩存文件fcache,并將其轉(zhuǎn)化為以關(guān)鍵字kt為鍵、分區(qū)編號(hào)為值的鍵值對(duì)結(jié)構(gòu),將其記為F。分區(qū)方法Π(kt)首先在F中查找是否存在關(guān)鍵字kt,若存在則直接輸出分區(qū)pj(j=1,2,…,r),否則按照Hash方法得到pj,分區(qū)流程如圖1所示。

圖1 分區(qū)劃分流程圖Fig.1 Partition flow chart

由于在抽樣過(guò)程中,可能存在少量頻率較小的關(guān)鍵字可能沒(méi)有被抽樣到,所以在這里使用Hash方法作為輔助方法。任意關(guān)鍵字kt根據(jù)Π(kt)計(jì)算得到分區(qū)pj后,將關(guān)鍵字kt與其攜帶的數(shù)據(jù)寫入到pj分區(qū)文件中。在計(jì)算作業(yè)Reduce階段各計(jì)算節(jié)點(diǎn)分別從Map任務(wù)節(jié)點(diǎn)拉取屬于本節(jié)點(diǎn)的中間數(shù)據(jù)分區(qū)文件,并運(yùn)行Reduce任務(wù),直至任務(wù)運(yùn)行結(jié)束,輸出作業(yè)的計(jì)算結(jié)果。

3 實(shí) 驗(yàn)

本文LBCC方法在分區(qū)劃分時(shí)考慮各節(jié)點(diǎn)計(jì)算能力的同時(shí),對(duì)網(wǎng)絡(luò)傳輸開(kāi)銷進(jìn)行了優(yōu)化。為驗(yàn)證本文方法效果,采用NoLFA方法[20]、SBaSC方法[21]和DEFH(default Hash)方法對(duì)比。NoLFA方法基于LEEN思想并結(jié)合了節(jié)點(diǎn)計(jì)算能力的差異性,適用于異構(gòu)集群環(huán)境,但其與本文方法相比有以下幾點(diǎn)不同:①NoLFA方法直接在計(jì)算作業(yè)執(zhí)行過(guò)程中通過(guò)主節(jié)點(diǎn)獲取關(guān)鍵字頻次信息,這增加了主節(jié)點(diǎn)負(fù)擔(dān),降低了集群元數(shù)據(jù)處理效率,本文使用抽樣作業(yè)得到關(guān)鍵字頻次分布信息,避免了元數(shù)據(jù)處理效率降低問(wèn)題;②分區(qū)計(jì)劃制定時(shí),NoLFA方法直接按照LEEN方法思想進(jìn)行處理,而本文方法在做了一次初步劃分之后,對(duì)低分區(qū)進(jìn)行調(diào)整,可以快速使最低分區(qū)總數(shù)量達(dá)到均衡值,而且本文方法分區(qū)均衡性比NoLFA方法更好;③本文方法在調(diào)整分區(qū)負(fù)載過(guò)程中同時(shí)考慮了節(jié)點(diǎn)計(jì)算能力和節(jié)點(diǎn)位置差異,能更好地適應(yīng)異構(gòu)集群環(huán)境。SBaSC方法使用了貪心方法思想劃分分區(qū),達(dá)到了均衡各節(jié)點(diǎn)負(fù)載的目的并且提升了作業(yè)計(jì)算效率,但其將集群中所有節(jié)點(diǎn)看作相同的計(jì)算能力,忽略了各節(jié)點(diǎn)處理能力的差異性。

3.1 數(shù)據(jù)集

為測(cè)試傾斜度對(duì)算法性能的影響,實(shí)驗(yàn)采用人工數(shù)據(jù)集和2個(gè)公開(kāi)數(shù)據(jù)集。人工數(shù)據(jù)集是使用程序生成不同傾斜率的數(shù)據(jù)集[22],實(shí)驗(yàn)時(shí)將人工數(shù)據(jù)集上傳到HDFS系統(tǒng),并讓其分散在不同節(jié)點(diǎn)上進(jìn)行存儲(chǔ),每組實(shí)驗(yàn)均基于該數(shù)據(jù)集執(zhí)行單詞統(tǒng)計(jì)任務(wù)。2個(gè)公開(kāi)數(shù)據(jù)集分別為維基百科數(shù)據(jù)集[2]和社交網(wǎng)絡(luò)數(shù)據(jù)集LiveJournal[21]。維基百科數(shù)據(jù)集包含了大量的文本數(shù)據(jù)信息,實(shí)驗(yàn)時(shí)在對(duì)該數(shù)據(jù)集進(jìn)行預(yù)處理后將其作為單詞統(tǒng)計(jì)作業(yè)的輸入。LiveJournal數(shù)據(jù)集中包含了大約1億個(gè)用戶社交網(wǎng)絡(luò)數(shù)據(jù),實(shí)驗(yàn)中使用該數(shù)據(jù)集作為關(guān)聯(lián)用戶數(shù)目統(tǒng)計(jì)作業(yè)的輸入。

3.2 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)采用物理節(jié)點(diǎn)與虛擬節(jié)點(diǎn)結(jié)合的方式,模擬異構(gòu)集群環(huán)境中不同計(jì)算能力節(jié)點(diǎn)環(huán)境。每組實(shí)驗(yàn)涉及到的物理機(jī)節(jié)點(diǎn)配置為I3、8核、16 GByte內(nèi)存、500 GByte磁盤空間,虛擬機(jī)節(jié)點(diǎn)在I5機(jī)器上搭建,單個(gè)虛擬節(jié)點(diǎn)分配4核、8 GByte內(nèi)存、100 GByte磁盤空間,Hadoop版本為2.10,所有節(jié)點(diǎn)均采用CentOS 6.9系統(tǒng),物理機(jī)節(jié)點(diǎn)和虛擬節(jié)點(diǎn)個(gè)數(shù)分別由實(shí)驗(yàn)需求確定。

3.3 數(shù)據(jù)傾斜程度對(duì)性能影響

通常關(guān)鍵字頻次服從Zipfian分布[4],在關(guān)鍵字列表K={k1,k2,…,kΩ}中,排在λ(λ=1,2,…,Ω)位置的關(guān)鍵字出現(xiàn)頻率f(λ)可以表示為

(10)

(10)式中,z≥0為傾斜程度控制參數(shù),z值越大則表示數(shù)據(jù)集中關(guān)鍵字的頻次分布越集中,當(dāng)z=0時(shí)表示關(guān)鍵字頻率相同,即所有關(guān)鍵字頻次均勻分布。

分別設(shè)置人工生成不同傾斜率數(shù)據(jù)集傾斜度z=0.2、z=0.4、z=0.6、z=0.8、z=1.0五組實(shí)驗(yàn),實(shí)驗(yàn)前準(zhǔn)備一個(gè)關(guān)鍵字個(gè)數(shù)為20 000的單詞列表,各關(guān)鍵字根據(jù)(10)式得到關(guān)鍵字頻率f(λ)。在向輸出文件里寫數(shù)據(jù)時(shí),f(λ)作為關(guān)鍵字kλ寫入的概率,以此生成包含10億單詞的數(shù)據(jù)文件。

配置不同分區(qū)算法并提交單詞統(tǒng)計(jì)作業(yè)。搭建包含2個(gè)物理節(jié)點(diǎn)和3個(gè)虛擬節(jié)點(diǎn)的Hadoop集群環(huán)境,通過(guò)文件配置使每個(gè)節(jié)點(diǎn)既是DataNode節(jié)點(diǎn)又是NodaManager節(jié)點(diǎn)。實(shí)驗(yàn)結(jié)果匯總信息如表1、圖2—圖3所示。

表1 在不同傾斜度下的FoS值Tab.1 FoS value at different skew degree

表1展示的是在不同傾斜度數(shù)據(jù)集作為輸入的情況下各種算法得到的FoS值(表1中,除傾斜度外的數(shù)值為實(shí)際數(shù)值乘以10-5)。不難發(fā)現(xiàn),在各種傾斜度下,本文LBCC方法FoS值最小,即均衡性表現(xiàn)最好,可以使各節(jié)點(diǎn)負(fù)載更加均衡。DEFH方法在各種傾斜度下FoS值都最大,均衡性最差,這樣會(huì)導(dǎo)致集群匯中部分節(jié)點(diǎn)負(fù)載遠(yuǎn)高于其他節(jié)點(diǎn),從而降低作業(yè)的執(zhí)行效率。NoLFA方法FoS值比LBCC方法高,最大可以是LBCC方法的236.2倍,說(shuō)明此時(shí)NoLFA分區(qū)結(jié)果節(jié)點(diǎn)負(fù)載均衡程度遠(yuǎn)不如本文LBCC方法。

圖2 不同傾斜度下本地化率值Fig.2 Locality value at different skew degree

圖3 不同傾斜度下執(zhí)行時(shí)間Fig.3 Execution time at different skew degree

由圖2可見(jiàn),在相同數(shù)據(jù)量下,隨著關(guān)鍵字頻次傾斜度的增加,Locality值呈下降趨勢(shì),即需要在網(wǎng)絡(luò)中傳輸?shù)臄?shù)據(jù)量逐漸增加。DEFH方法、SBaSC方法變化幅度比較小,因其沒(méi)有考慮網(wǎng)絡(luò)開(kāi)銷優(yōu)化,這2種方法需要在網(wǎng)絡(luò)中傳輸?shù)臄?shù)據(jù)量占總數(shù)據(jù)量20%左右。當(dāng)傾斜率較高時(shí),LBCC方法Locality值會(huì)比NoLFA稍低,這是由于在數(shù)據(jù)傾斜率較高時(shí)部分關(guān)鍵字在各節(jié)點(diǎn)分布不均勻,本文方法在調(diào)整分區(qū)過(guò)程中,為了使各分區(qū)均衡性更好,會(huì)結(jié)合節(jié)點(diǎn)計(jì)算能力和節(jié)點(diǎn)位置信息將部分關(guān)鍵字調(diào)整到最低分區(qū),會(huì)犧牲一部分Locality值,相對(duì)于NoLFA方法在傾斜率較高時(shí)Locality值會(huì)存在一定差距,但比其他方法本地化率更高。

由圖3可見(jiàn),在數(shù)據(jù)總量相同且節(jié)點(diǎn)個(gè)數(shù)一定情況下,作業(yè)執(zhí)行時(shí)間也隨之增大。LBCC方法結(jié)合節(jié)點(diǎn)計(jì)算能力將中間數(shù)據(jù)更加均衡地劃分,縮短了整體作業(yè)的完成時(shí)間。LBCC方法相較于NoLFA、SBaSC、DEFH方法在效率上都有較大提高。

3.4 節(jié)點(diǎn)個(gè)數(shù)對(duì)性能影響

為測(cè)試異構(gòu)環(huán)境下節(jié)點(diǎn)個(gè)數(shù)對(duì)算法性能的影響,實(shí)驗(yàn)環(huán)境初始設(shè)置為1個(gè)物理節(jié)點(diǎn)和2個(gè)虛擬節(jié)點(diǎn)共3個(gè)節(jié)點(diǎn),之后每組實(shí)驗(yàn)在此基礎(chǔ)上依次增加1個(gè)物理節(jié)點(diǎn)和1個(gè)虛擬節(jié)點(diǎn),節(jié)點(diǎn)個(gè)數(shù)依次設(shè)置為3、5、7、9、11個(gè)。本次實(shí)驗(yàn)分別采用維基百科數(shù)據(jù)集和社交網(wǎng)絡(luò)LiveJournal數(shù)據(jù)集,每次配置好環(huán)境后,將數(shù)據(jù)集上傳到HDFS文件系統(tǒng),數(shù)據(jù)文件會(huì)以塊的形式分散存儲(chǔ)在集群中各節(jié)點(diǎn)上。實(shí)驗(yàn)中每種算法運(yùn)行多次后求取各項(xiàng)指標(biāo)平均值,匯總信息如表2—表3、圖4—圖7所示。

表2 在維基百科數(shù)據(jù)集上FoS值Tab.2 FoS value for different number of data nodes on Wikipedia dataset

表3 在LiveJournal數(shù)據(jù)集上FoS值Tab.3 FoS value for different number of data nodes on LiveJournal dataset

由表2—表3可知,在不同節(jié)點(diǎn)個(gè)數(shù)實(shí)驗(yàn)環(huán)境中,無(wú)論采用哪種數(shù)據(jù)集作為作業(yè)的輸入,本文LBCC方法分區(qū)結(jié)果的FoS值最低,即均衡性表現(xiàn)最好,可以使各節(jié)點(diǎn)負(fù)載更加均衡。本文LBCC方法在調(diào)整各節(jié)點(diǎn)負(fù)載時(shí)考慮了節(jié)點(diǎn)計(jì)算能力,讓各分區(qū)之間的負(fù)載與節(jié)點(diǎn)自身計(jì)算能力相匹配,與其他各節(jié)點(diǎn)負(fù)載相均衡。 DEFH方法根據(jù)關(guān)鍵字哈希值進(jìn)行劃分,并沒(méi)有考慮各節(jié)點(diǎn)的負(fù)載均衡性,所以FoS值比較大。另外在異構(gòu)環(huán)境中,SBaSC沒(méi)有考慮節(jié)點(diǎn)的計(jì)算能力,所以導(dǎo)致各節(jié)點(diǎn)負(fù)載差異也很大。

圖4 在維基百科數(shù)據(jù)集上不同節(jié)點(diǎn)個(gè)數(shù)下的本地化率Fig.4 Locality value for different number of nodes on Wikipedia dataset

圖5 在LiveJournal數(shù)據(jù)集上不同節(jié)點(diǎn)個(gè)數(shù)下的 本地化率Fig.5 Locality value for different number of nodes on LiveJournal dataset

由圖4—圖5可見(jiàn),隨著節(jié)點(diǎn)的增加,Locality值總體上呈下降趨勢(shì)。文獻(xiàn)[5]指出,相同關(guān)鍵字的頻次在集群中各節(jié)點(diǎn)均勻分布時(shí),數(shù)據(jù)本地化率取決于節(jié)點(diǎn)的個(gè)數(shù),即VLocality=1/r,在數(shù)據(jù)值上將與公式計(jì)算的結(jié)果相等。由此可知,隨著節(jié)點(diǎn)個(gè)數(shù)的增加,Locality值會(huì)隨之下降。在不同節(jié)點(diǎn)個(gè)數(shù)環(huán)境下,NoLFA方法和LBCC方法的分區(qū)結(jié)果中本地化率比較接近,SBaSC和DEFH方法由于沒(méi)有考慮網(wǎng)絡(luò)開(kāi)銷優(yōu)化,Locality值比較低,需要在網(wǎng)絡(luò)中傳輸?shù)臄?shù)據(jù)量比較大。數(shù)據(jù)集LiveJournal上關(guān)鍵字的頻次比較集中,大量的關(guān)鍵字?jǐn)y帶的數(shù)據(jù)可以在節(jié)點(diǎn)本地進(jìn)行處理,不需要通過(guò)網(wǎng)絡(luò)傳輸?shù)狡渌?jié)點(diǎn),所以通過(guò)LBCC和NoLFA方法得到的Locality值比較高。

由圖6—圖7可見(jiàn),隨著節(jié)點(diǎn)個(gè)數(shù)的增加,任務(wù)完成時(shí)間逐漸降低。另外,在每組實(shí)驗(yàn)中,本文LBCC方法在效率上優(yōu)于其他分區(qū)方法。圖7中NoLFA和LBCC方法相較于圖6差別較大,這是由于使用NoLFA和LBCC方法可以使社交網(wǎng)絡(luò)LiveJournal數(shù)據(jù)集絕大部分在節(jié)點(diǎn)本地處理,另外在異構(gòu)環(huán)境中,考慮了節(jié)點(diǎn)負(fù)載均衡性,使各節(jié)點(diǎn)的負(fù)載與節(jié)點(diǎn)計(jì)算能力相匹配。在維基百科數(shù)據(jù)集上,LBCC方法在作業(yè)運(yùn)行效率上比NoLFA方法提高7.0～15.4百分點(diǎn),比SBaSC方法提高17.9～23.1百分點(diǎn),比DEFH方法提高11.0～30.8百分點(diǎn)。在社交網(wǎng)絡(luò)LiveJournal數(shù)據(jù)集上,LBCC方法在效率上比NoLFA方法提高2.8～7.6百分點(diǎn),比SBaSC方法提高8.1～15.4百分點(diǎn),比DEFH方法提高10.1～15.9百分點(diǎn)。

圖6 在維基百科數(shù)據(jù)集上不同數(shù)據(jù)節(jié)點(diǎn)下 任務(wù)完成時(shí)間Fig.6 Execution time for different nodes on the Wikipedia dataset

圖7 在LiveJournal數(shù)據(jù)集上不同數(shù)據(jù)節(jié)點(diǎn)下 任務(wù)完成時(shí)間Fig.7 Execution time for different number of nodes on LiveJournal dataset

4 結(jié)束語(yǔ)

本文提出通過(guò)Reservoir抽樣方法獲取Map產(chǎn)生的中間數(shù)據(jù)分布信息,然后結(jié)合節(jié)點(diǎn)計(jì)算能力解決MapReduce在分區(qū)過(guò)程中的負(fù)載均衡問(wèn)題。實(shí)驗(yàn)結(jié)果表明,本文方法得到的分區(qū)結(jié)果會(huì)使各節(jié)點(diǎn)負(fù)載更為均衡,提高了作業(yè)處理效率,同時(shí)優(yōu)化了網(wǎng)絡(luò)傳輸代價(jià)。本文方法在集群異構(gòu)的環(huán)境中具有良好的性能優(yōu)勢(shì),計(jì)算效率相對(duì)于現(xiàn)有分區(qū)方法有顯著提升,為MapReduce計(jì)算模型負(fù)載均衡提供了一種更加高效的解決方案。