一種基于Value均值的MapReduce任務(wù)分配策略

薛愈潔

(太原學(xué)院,山西 太原 030001)

0 引言

大數(shù)據(jù)是巨量數(shù)據(jù)集合,與傳統(tǒng)數(shù)據(jù)不同,其不僅數(shù)據(jù)量龐大,數(shù)據(jù)維度高,而且數(shù)據(jù)結(jié)構(gòu)復(fù)雜,處理難度大,因此對(duì)大數(shù)據(jù)的精確高效處理一直都是研究的熱點(diǎn)。目前,分布式計(jì)算是解決大數(shù)據(jù)難題的重要方法,由google公司提出的MapReduce編程思想是并行與分布式計(jì)算的重要思想[1-2],是一種簡化的并行計(jì)算模型,其核心是“分而治之”——將數(shù)據(jù)處理流程進(jìn)行Map過程和Reduce過程的高度抽象劃分,雖然兩者的計(jì)算相互獨(dú)立,但是又通過Map輸出與Reduce輸入相互聯(lián)系。

大多數(shù)并行與分布式計(jì)算平臺(tái)對(duì)于MapReduce編程思想都有相應(yīng)的實(shí)現(xiàn)[3]——常見的有Hadoop平臺(tái)與Spark平臺(tái),該類平臺(tái)將內(nèi)部并行運(yùn)行機(jī)制進(jìn)行封裝,使算法設(shè)計(jì)邏輯與具體實(shí)現(xiàn)流程相對(duì)獨(dú)立,將程序并行運(yùn)行在分布式系統(tǒng)上[4],提高了程序設(shè)計(jì)的高效性。作為較成熟的編程思想,目前對(duì)MapReduce編程思想主要研究集中在借助現(xiàn)有的分布式計(jì)算機(jī)平臺(tái),對(duì)已有算法的可并行化研究,優(yōu)化數(shù)據(jù)處理過程,提高數(shù)據(jù)處理性能,實(shí)現(xiàn)處理效果的提升[5-6],而對(duì)于MapReduce自身的任務(wù)分配機(jī)制研究不夠充分。利用MapReduce思想,在數(shù)據(jù)處理過程中,容易出現(xiàn)相同的Map值的Value集合數(shù)據(jù)量差別巨大的情況,導(dǎo)致不同的Reduce任務(wù)工作量不同,造成集群負(fù)載不均衡問題,相對(duì)降低了數(shù)據(jù)處理效率。目前大多數(shù)并行與分布式計(jì)算平臺(tái)通過靜態(tài)HDFS文件系統(tǒng)的數(shù)據(jù)塊容量解決任務(wù)分配不均衡問題,但效果有待提高。為了能更好地提升MapReduce框架的計(jì)算性能,本文通過分析MapReduce思想中Map任務(wù)與Reduce任務(wù)處理機(jī)制,針對(duì)MapReduce思想中Reduce任務(wù)所在節(jié)點(diǎn)的負(fù)載不均衡現(xiàn)象,提出一種基于Value均值的MapReduce任務(wù)分配策略,通過制定Value均值收斂規(guī)則,使Value集合能夠相對(duì)均勻地分布于不同Reduce任務(wù)中,使Reduce任務(wù)計(jì)算節(jié)點(diǎn)負(fù)載趨于均衡,不僅提高了數(shù)據(jù)處理效率,而且具有廣泛性。

1 MapReduce思想

1.1 基本原理

MapReduce編程思想[7-8]的核心是將單個(gè)復(fù)雜的任務(wù)劃分為多個(gè)簡單的任務(wù)分別進(jìn)行處理,分為Map任務(wù)與Reduce任務(wù)。Map任務(wù)主要用于數(shù)據(jù)格式化處理,將數(shù)據(jù)格式化為鍵值對(duì)的形式,Reduce任務(wù)負(fù)責(zé)接收鍵值對(duì),將相同Key值的Value值進(jìn)行歸并,得到

1.2 處理過程

圖1 MapReduce處理過程Fig.1 The processing of MapReduce

由圖1可知,不同Map任務(wù)會(huì)產(chǎn)生不同的Key,Reduce任務(wù)會(huì)將相同Key值的Value值進(jìn)行合并。每個(gè)Reduce任務(wù)會(huì)處理相同Key值的Value值集合,不同Key值的Value集合被分配到不同的Reduce任務(wù)中,導(dǎo)致Reduce任務(wù)量不同。

定義1:在MapReduce任務(wù)中,若不同key值所劃分的Reduce任務(wù)量相差不大,則Reduce任務(wù)所在節(jié)點(diǎn)的負(fù)載相差不大,稱Reduce任務(wù)分配相對(duì)均衡狀態(tài)(RBS狀態(tài));反之,則稱Reduce任務(wù)分配相對(duì)不均衡狀態(tài)(RIS狀態(tài))。

2 Key值標(biāo)簽

2.1 傳統(tǒng)任務(wù)分配(Traditional Task Allocation,TTA)

傳統(tǒng)的MapReduce中Map任務(wù)不改變Key值,將原始數(shù)據(jù)格式化成鍵值對(duì)形式,經(jīng)過MapReduce的Shuffle階段,在Reduce計(jì)算節(jié)點(diǎn)上生成集合所包含的數(shù)據(jù)量不同,特別是復(fù)雜數(shù)據(jù)集,產(chǎn)生的List往往相差很大。有集合S1、S2舉例如下:

={object1,object2,object3,…，objectn}(n為10＾6數(shù)量級(jí))

={object1,object2,bject3,…objectm}(m為10＾9數(shù)量級(jí))

數(shù)據(jù)處理時(shí),兩組List分別分配于不同的Reduce任務(wù)中,即位于不同的計(jì)算節(jié)點(diǎn),忽略節(jié)點(diǎn)計(jì)算能力的差異,理想情況下,兩集合數(shù)據(jù)進(jìn)行相同處理時(shí),時(shí)間開銷T存在以下關(guān)系:

T(S2)=T(S1)×10＾3。

由此可得,處理集合S2的時(shí)間開銷T(S2)大于處理集合S1的時(shí)間開銷T(S1),為T(S1)的10＾3倍。

2.2 基于Key值任務(wù)分配(Key-Traditional Task Allocation,KTTA)

傳統(tǒng)任務(wù)分配算法(TTA)無法均衡不同Reduce任務(wù)的數(shù)據(jù)集合,導(dǎo)致每個(gè)Key值的Reduce任務(wù)待處理的數(shù)據(jù)量存在差異。針對(duì)上述問題,提出基于Key值的任務(wù)分配策略(KTTA),Map任務(wù)執(zhí)行完畢后,Value任務(wù)先計(jì)算每個(gè)集合元素?cái)?shù)量N,并計(jì)算該集合元素個(gè)數(shù)的平均值Mean。每個(gè)值與均值的差異小于某個(gè)閾值ε,則進(jìn)行K-means運(yùn)算。

其主要過程如下:

步驟1:輸入數(shù)據(jù)集InputDataSet(IS),通過Map任務(wù),將IS數(shù)據(jù)集輸出為鍵值對(duì)形式。

步驟2:獲取每個(gè)key值所對(duì)應(yīng)的集合的元素?cái)?shù)量N,取所有N的平均值Mean。

步驟3:通過Map任務(wù),將所有大于ε的List