利用快速無(wú)偏分層圖抽樣算法的MapReduce負(fù)載平衡方法

杜 鵑 張 卓 曹建春

1(黃河水利職業(yè)技術(shù)學(xué)院 河南 開(kāi)封 475004) 2(鄭州大學(xué) 河南 鄭州 450001)

0 引 言

隨著信息技術(shù)的飛速發(fā)展，云計(jì)算技術(shù)、大數(shù)據(jù)技術(shù)及以此基礎(chǔ)的Web、互聯(lián)網(wǎng)不斷升級(jí)，物聯(lián)網(wǎng)技術(shù)得以出現(xiàn)和發(fā)展，數(shù)據(jù)處理及信息獲取逐漸成為社會(huì)各個(gè)領(lǐng)域的核心價(jià)值取向。技術(shù)的發(fā)展導(dǎo)致數(shù)據(jù)的范圍擴(kuò)大化和來(lái)源多樣化，每時(shí)每刻人們都面臨著海量的結(jié)構(gòu)化和非結(jié)構(gòu)化數(shù)據(jù)處理問(wèn)題[1-3]。如何設(shè)計(jì)并行處理系統(tǒng)和并行數(shù)據(jù)處理算法逐漸成為了計(jì)算機(jī)及其他相關(guān)領(lǐng)域的研究熱點(diǎn)。

自大數(shù)據(jù)及相關(guān)技術(shù)誕生以來(lái)，分布式數(shù)據(jù)管理及其擴(kuò)展方法一直是數(shù)據(jù)庫(kù)研究人員的主要目標(biāo)。許多研究人員專注于設(shè)計(jì)可擴(kuò)展系統(tǒng)，用于處理和分析大規(guī)模數(shù)據(jù)。他們面臨的主要問(wèn)題是如何降低應(yīng)用程序的數(shù)據(jù)訪問(wèn)模式存在差異所造成的硬件需求。這些要求催生了新一代以鍵值(key-value)存儲(chǔ)為核心思想的系統(tǒng)。其中MapReduce編程模型因其易于開(kāi)發(fā)和便于拓展及嵌入的特點(diǎn)被業(yè)界和學(xué)術(shù)界廣泛采用[4]。

MapReduce的設(shè)計(jì)思想是將整體任務(wù)分割到各個(gè)運(yùn)算節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)處理完分配的任務(wù)之后進(jìn)行結(jié)果匯總，以實(shí)現(xiàn)并行數(shù)據(jù)的處理。它包括兩個(gè)核心部分：Map函數(shù)和Reduce函數(shù)。首先，應(yīng)用Map函數(shù)以鍵值對(duì)的形式產(chǎn)生和存儲(chǔ)中間數(shù)據(jù)列表，中間數(shù)據(jù)由其key(鍵)分區(qū)。具有相同key的所有元組的子集形成一個(gè)聚類，當(dāng)所有映射器應(yīng)用相同的函數(shù)進(jìn)行分區(qū)時(shí)，會(huì)將聚類分配給同一分區(qū)。主服務(wù)器將分區(qū)分配給reducer以便按聚類進(jìn)行處理。reduce函數(shù)接收與一個(gè)key相關(guān)聯(lián)的value，并為該key產(chǎn)生單個(gè)結(jié)果[5]。

連接操作是MapReduce中進(jìn)行數(shù)據(jù)查詢、數(shù)據(jù)分析和聯(lián)機(jī)應(yīng)用所必不可少的操作。值得注意的是，這種操作非常耗時(shí)。因此，采用高效的大數(shù)據(jù)并行連接算法可以有效地提高M(jìn)apReduce中數(shù)據(jù)查詢相關(guān)任務(wù)的效率，從而提升整個(gè)并行系統(tǒng)的運(yùn)行效率。許多文獻(xiàn)提出了在MapReduce上實(shí)現(xiàn)并行連接的方法[6-8]。大部分所提出的并行連接算法應(yīng)用基于Hash函數(shù)的分區(qū)，原因是Hadoop(最流行的MapReduce實(shí)現(xiàn))和Spark中數(shù)據(jù)分發(fā)的默認(rèn)機(jī)制是基于Hash函數(shù)，通常采用這種方法做到數(shù)據(jù)負(fù)載的平衡分配是非常困難的。在一個(gè)MapReduce的任務(wù)塊中，如果Map的輸出結(jié)果通過(guò)Hash函數(shù)進(jìn)行分區(qū)后傳遞給Reducer，首先有可能因?yàn)镠ash分區(qū)調(diào)度不能均勻分配key組導(dǎo)致負(fù)載分布傾斜；其次，即使可以做到key組的均勻分配，但每個(gè)key組中元素的不同仍會(huì)導(dǎo)致某些Reducer處理更多的數(shù)據(jù)。這種現(xiàn)象被稱為數(shù)據(jù)負(fù)載不平衡。

并行連接可能會(huì)受數(shù)據(jù)傾斜導(dǎo)致的負(fù)載分配不平衡的影響而降低效率[9]，這是因?yàn)檫B接操作的耗時(shí)由其運(yùn)行時(shí)間最長(zhǎng)的任務(wù)決定，也就是要等待最慢的Reduce節(jié)點(diǎn)完成數(shù)據(jù)處理任務(wù)。數(shù)據(jù)負(fù)載不平衡可能會(huì)發(fā)生在Map端或者Reduce端。發(fā)生在Map端的數(shù)據(jù)負(fù)載不平衡大致包含兩個(gè)主要原因：(1) 由需要處理的數(shù)據(jù)異構(gòu)所導(dǎo)致，當(dāng)需要處理的數(shù)據(jù)塊中半結(jié)構(gòu)化或無(wú)結(jié)構(gòu)化數(shù)據(jù)不能均勻分布時(shí)，會(huì)嚴(yán)重影響Map階段的運(yùn)行效率；(2) 存在異構(gòu)的Map任務(wù)，由于任務(wù)的多元性，不同源文件所需要的處理方式不同，Map任務(wù)的運(yùn)行效率也會(huì)有顯著差別。發(fā)生在Reduce端的數(shù)據(jù)負(fù)載不平衡可能由Map端的輸出不平衡導(dǎo)致，理想情況下分區(qū)函數(shù)會(huì)將key組均勻地分配到Reduce節(jié)點(diǎn)，但是當(dāng)key組分配不均或key組所含元素差異較大時(shí)，某些Reduce節(jié)點(diǎn)會(huì)處理更多的數(shù)據(jù)。除此之外，即使不存在Map端的傾斜問(wèn)題，Reduce端仍會(huì)由于所處理(key, value)組的數(shù)據(jù)分布或數(shù)值之間關(guān)系的不同而產(chǎn)生處理效率的差異。

連接算法的其他改進(jìn)思路是利用抽樣對(duì)數(shù)據(jù)進(jìn)行聚類處理[10]。聚類作為一種重要的大數(shù)據(jù)處理與分析方法，通過(guò)建立數(shù)學(xué)模型，按照數(shù)據(jù)之間的關(guān)聯(lián)度將需要處理的數(shù)據(jù)劃分為不同的類，并使同類數(shù)據(jù)之間的相似度最大，不同類之間的數(shù)據(jù)相似度最小。通過(guò)聚類處理，就可以根據(jù)連接屬性將來(lái)自不同區(qū)塊的數(shù)據(jù)分配到同一分片中，在進(jìn)行數(shù)據(jù)查詢時(shí)就不需要根據(jù)屬性用MapReduce來(lái)進(jìn)行連接操作。雖然聚類算法可以有效提高M(jìn)apReduce的運(yùn)行效率，但是隨著數(shù)據(jù)規(guī)模的指數(shù)級(jí)增長(zhǎng)，聚類算法本身的效率卻不高，如何提高聚類算法在大數(shù)據(jù)環(huán)境下的運(yùn)行效率成為了近期的研究熱點(diǎn)。

在進(jìn)行聚類之前進(jìn)行數(shù)據(jù)的合理的提煉是一個(gè)提高運(yùn)算效率的有效途徑。但是，一些典型的抽樣算法如NS、FFS和ES等具有面對(duì)大規(guī)模復(fù)雜關(guān)系數(shù)據(jù)時(shí)普遍存在數(shù)據(jù)過(guò)度入樣的問(wèn)題。為了快速高效地進(jìn)行抽樣，提高聚類算法應(yīng)用于大數(shù)據(jù)分布式云計(jì)算框架的執(zhí)行效率，本文提出一種新的利用快速無(wú)偏分層圖抽樣算法的MapReduce負(fù)載平衡方法。該方法通過(guò)引入無(wú)偏分層圖抽樣算法來(lái)擴(kuò)展傳統(tǒng)聚類方法，使其適應(yīng)大規(guī)模數(shù)據(jù)集的應(yīng)用，提高運(yùn)行效率。其主要工作包括：

(1) 現(xiàn)有的大多數(shù)結(jié)合了聚類和抽樣的方法中，普遍存在抽樣時(shí)過(guò)度入樣的問(wèn)題，在面對(duì)重度傾斜的數(shù)據(jù)時(shí)，算法效率偏低。本文通過(guò)引入了一種無(wú)偏分層圖算法并根據(jù)聚類結(jié)果動(dòng)態(tài)調(diào)整抽樣系數(shù)，根據(jù)數(shù)據(jù)分布屬性動(dòng)態(tài)調(diào)節(jié)抽樣比例，實(shí)現(xiàn)輸入和輸出數(shù)據(jù)的高效平衡抽樣。

(2) 根據(jù)本文方法設(shè)計(jì)了MapReduce框架下的算法流程并利用合成數(shù)據(jù)與真實(shí)數(shù)據(jù)進(jìn)行了數(shù)據(jù)處理實(shí)驗(yàn)，在負(fù)載平衡性能和算法執(zhí)行時(shí)間上與傳統(tǒng)Hash函數(shù)法、NS抽樣聚類法作了對(duì)比，驗(yàn)證了本文方法的有效性。

1 相關(guān)研究

目前，MapReduce框架中負(fù)載傾斜不平衡而導(dǎo)致其連接操作速度較低并進(jìn)而影響整個(gè)數(shù)據(jù)運(yùn)算效率的問(wèn)題已被廣泛研究。阻礙系統(tǒng)性能提升的主要障礙之一是數(shù)據(jù)負(fù)載不平衡。目前，在MapReduce中，已有多種成熟有效的處理單個(gè)輸入數(shù)據(jù)集時(shí)負(fù)載不平衡的方法。但是，當(dāng)面對(duì)多數(shù)據(jù)集輸入的情況時(shí)，算法還是會(huì)出現(xiàn)較為明顯的效率降低。文獻(xiàn)[11]提出了利用數(shù)據(jù)直方圖技術(shù)來(lái)優(yōu)化連接操作的效率。其主要思想是利用直方圖評(píng)估數(shù)據(jù)集中的數(shù)據(jù)分布情況，獲取負(fù)載傾斜及數(shù)據(jù)集間連接屬性等關(guān)鍵信息，從而優(yōu)化連接算法。這種方法存在一些局限：從Mapper收集的統(tǒng)計(jì)數(shù)據(jù)必須很小并且需要捕獲全局?jǐn)?shù)據(jù)分布。文獻(xiàn)[12]提出了一種在發(fā)生負(fù)載不平衡后會(huì)動(dòng)態(tài)地調(diào)整數(shù)據(jù)分區(qū)，將未處理數(shù)據(jù)任務(wù)進(jìn)行重新分區(qū)，然后將新任務(wù)調(diào)度到已空閑的節(jié)點(diǎn)中去的方法。這種方法的缺點(diǎn)在于，它不會(huì)采樣任何key頻率信息，因此無(wú)法識(shí)別大的key，在任務(wù)調(diào)整時(shí)存在局限。

文獻(xiàn)[13]提出了解決MapReduce中數(shù)據(jù)負(fù)載不平衡問(wèn)題的另一種策略。通過(guò)融合新的抽樣技術(shù)，這種策略在Map處理期間僅抽樣一部分中間數(shù)據(jù)而獲得中間數(shù)據(jù)分布的精確估計(jì)。這種方法存在的主要問(wèn)題是需要根據(jù)數(shù)據(jù)集的規(guī)模動(dòng)態(tài)調(diào)整抽樣參數(shù)，否則會(huì)造成算法準(zhǔn)確性或效率的降低。文獻(xiàn)[14]提出了一種基于估計(jì)key頻率分布的抽樣策略。這種策略通過(guò)估計(jì)數(shù)據(jù)的整體分布來(lái)預(yù)先獲得分區(qū)方案，基于抽樣結(jié)果引入了兩種分區(qū)算法：聚類組合和聚類分割組合。第一種方法認(rèn)為，具有最大數(shù)量的(key，value)對(duì)的聚類被分配給具有最小數(shù)量的(key，value)對(duì)的Reducer。第二種方法假設(shè)較大的聚類被分成相等的片段，然后，每個(gè)片段被分派到每個(gè)Reducer。這種策略忽略了每個(gè)組應(yīng)由單個(gè)Reducer處理的規(guī)則，配置了額外的Reduce階段，以合并從多個(gè)Reducer生成的結(jié)果。文獻(xiàn)[15]提出了一種平衡傾斜數(shù)據(jù)塊的分裂和組合算法。該算法利用蓄水池抽樣算法來(lái)檢測(cè)key分布，根據(jù)每個(gè)Map任務(wù)中數(shù)據(jù)聚類的大小對(duì)數(shù)據(jù)聚類進(jìn)行排序，并按順序填充到相關(guān)的bucket中。值得注意的是，數(shù)據(jù)聚類超過(guò)當(dāng)前bucket的最大容量時(shí)，數(shù)據(jù)聚類將被重新劃分，從而影響抽樣效率。

以上提到的應(yīng)對(duì)數(shù)據(jù)負(fù)載不平衡的方法核心思想是重分配傾斜的數(shù)據(jù)負(fù)載以獲得負(fù)載平衡。還有一類改進(jìn)方法是改進(jìn)連接操作本身。文獻(xiàn)[16]提出了采用范圍分區(qū)而不是Hash分區(qū)來(lái)進(jìn)行負(fù)載分配的負(fù)載傾斜處理連接算法。這是一種簡(jiǎn)單的方法，能夠處理輸入數(shù)據(jù)集中的傾斜。它收集兩個(gè)關(guān)系的樣本，然后，基于樣本數(shù)據(jù)確定最傾斜關(guān)系，創(chuàng)建一個(gè)分區(qū)向量并基于分區(qū)向量劃分兩個(gè)關(guān)系。但是這種方法在確定子范圍時(shí)，沒(méi)有考慮連接結(jié)果的大小，這可能仍舊會(huì)導(dǎo)致負(fù)載不平衡的出現(xiàn)。

文獻(xiàn)[17]提出了用于在MapReduce中實(shí)現(xiàn)連接的隨機(jī)算法，利用了兩個(gè)輸入關(guān)系之間的交叉積空間。使用連接矩陣，在兩個(gè)關(guān)系S和T之間建模連接操作。關(guān)系S被隨機(jī)分成m塊，T被分成n塊。矩陣中的行表示m塊中的一個(gè)，而列表示n塊中的一個(gè)。矩陣空間被一些矩形覆蓋，它們中的每一個(gè)都確定了Reducer所覆蓋的塊。為了平衡Reducer的工作量，Reducer應(yīng)該覆蓋相同數(shù)量的單元格。在該方法中，關(guān)系S的m塊中的每一個(gè)必須與關(guān)系T的n塊中的每一個(gè)連接，這意味著高重復(fù)輸入的產(chǎn)生。對(duì)于必須使用更多Reducer的更大型關(guān)系而言，它變得更加嚴(yán)重，導(dǎo)致更多的重復(fù)。針對(duì)這種情況，文獻(xiàn)[17]提出了一種減少重復(fù)的方法，它需要額外的MapReduce作業(yè)來(lái)收集數(shù)據(jù)統(tǒng)計(jì)信息，不估計(jì)連接輸出分布。因而，很容易在Reduce端出現(xiàn)負(fù)載傾斜。

文獻(xiàn)[18]提出了另一種策略以解決并行連接數(shù)據(jù)負(fù)載不平衡的問(wèn)題。該策略通過(guò)引入多級(jí)負(fù)載平衡算法來(lái)考慮輸入和輸出數(shù)據(jù)的特性。此外，還將輸入和輸出分布表示為矩陣并通過(guò)使用一類等權(quán)重直方圖將矩陣劃分成具有幾乎相同權(quán)重的區(qū)域來(lái)避免高輸入元組重復(fù)。

2 MapReduce框架及并行聚類連接算法

2.1 MapReduce算法框架

MapReduce是一個(gè)簡(jiǎn)單強(qiáng)大的編程模型，可用于實(shí)現(xiàn)分布式應(yīng)用程序和大規(guī)模數(shù)據(jù)分析[4]。該框架基于兩個(gè)函數(shù)：

map(k1,υ1)→list(k2,υ2)

reduce(k2,list(υ2))→list(k3,υ3)

Map函數(shù)和Reduce函數(shù)都需要由用戶編寫實(shí)現(xiàn)。map函數(shù)有兩個(gè)輸入?yún)?shù)，即key：k1，以及與之相關(guān)的value：υ1。它生成一個(gè)中間(key，value)對(duì)的列表(list)。MapReduce框架根據(jù)k2的值來(lái)劃分列表，其中具有相同k2值的所有鍵值對(duì)都屬于同一組。Reduce函數(shù)也有兩個(gè)輸入?yún)?shù)，一個(gè)中間key(k2)和一個(gè)與k2相關(guān)的中間值的列表list_v(υ2)。一個(gè)完整的MapReduce運(yùn)算流程如圖1所示。

圖1 MapReduce運(yùn)算流程

在一次MapReduce任務(wù)中，各個(gè)Map函數(shù)并行執(zhí)行，首先根據(jù)輸入的數(shù)據(jù)生成(k1,v1)對(duì)，然后經(jīng)過(guò)Map處理后得到(k2,v2)對(duì)，并將中間結(jié)果儲(chǔ)存在本地磁盤上。經(jīng)過(guò)中間shuffle過(guò)程排序后，得到Reduce函數(shù)的輸入(k2,list_v2)對(duì)。具有相同鍵的數(shù)據(jù)交由同一Reduce節(jié)點(diǎn)處理。各個(gè)Reduce函數(shù)也是并行執(zhí)行的，數(shù)據(jù)經(jīng)過(guò)Reduce函數(shù)處理后得到最終結(jié)果及相應(yīng)(k3,v3)對(duì)。

MapReduce中的連接操作是基于key中的一個(gè)或多個(gè)字段將兩個(gè)或者多個(gè)數(shù)據(jù)塊組合成為一個(gè)整體的過(guò)程，其目的是在多個(gè)數(shù)據(jù)集中得到在一定條件的約束下的結(jié)果集。數(shù)據(jù)傾斜主要在連接操作階段導(dǎo)致數(shù)據(jù)負(fù)載分配不平衡，對(duì)MapReduce數(shù)據(jù)處理的效率產(chǎn)生影響。為了提取目標(biāo)數(shù)據(jù)集的數(shù)據(jù)屬性，減少在分配時(shí)端產(chǎn)生負(fù)載不平衡，本文采用聚類算法代替Hash算法；為了減少非必要數(shù)據(jù)量，同時(shí)在目標(biāo)數(shù)據(jù)集端采樣時(shí)平衡采樣后的結(jié)果集負(fù)載，本文引入帶有抽樣系數(shù)動(dòng)態(tài)調(diào)節(jié)機(jī)制的無(wú)偏分層圖抽樣算法對(duì)目標(biāo)數(shù)據(jù)進(jìn)行預(yù)處理。

2.2 聚類算法

聚類是指將物理或抽象元素分組到由相似元素組成的集合中的過(guò)程。每一個(gè)集合中的元素相似性越高，集合之間的元素差別越大，則聚類的效果越好。聚類算法的概念如圖2所示。按照不同的劃分方法，同樣一組原始元素，可以得到多種聚類結(jié)果。

圖2 同一原始對(duì)象集合的不同聚類

通過(guò)聚類，可以得知具有某些特征的元素在空間中的分布情況，對(duì)應(yīng)到數(shù)據(jù)處理上，相當(dāng)于從數(shù)據(jù)屬性中挖掘數(shù)據(jù)整體的分布特征及數(shù)據(jù)集之間的聯(lián)系。聚類算法在很多領(lǐng)域得到了廣泛的應(yīng)用，根據(jù)類的劃分方法不同，聚類算法又分為很多類型，例如層次聚類/劃分聚類、互斥聚類/模糊聚類、完全聚類/部分聚類。其中，劃分聚類可以將數(shù)據(jù)的集合劃分成互不重疊的子集，保證每個(gè)數(shù)據(jù)元素只存在于一個(gè)子集當(dāng)中，非常適合應(yīng)用于MapReduce框架中，本文主要選擇K-means劃分聚類算法在MapReduce中加以實(shí)現(xiàn)。

2.3 MapReduce中的劃分聚類連接算法實(shí)現(xiàn)

首先列出K-means劃分聚類算法中的基本符號(hào)定義如表1所示。

表1 符號(hào)定義表

K-means算法是一種常用的劃分聚類算法。在確定n個(gè)劃分中心點(diǎn)之后，它可以將m個(gè)待聚類的數(shù)據(jù)塊劃分到n個(gè)集合中并最終得到具有較高集合內(nèi)相似度和較低集合間相似度的聚類結(jié)果。算法首先從所有待聚類對(duì)象中隨機(jī)選定n個(gè)作為初始劃分中心點(diǎn)，然后將剩余的對(duì)象按照與中心點(diǎn)的距離分配到n個(gè)數(shù)據(jù)集合并計(jì)算每個(gè)數(shù)據(jù)集合的距離均值。這個(gè)過(guò)程一直迭代到判別函數(shù)收斂為止。

將K-means算法對(duì)應(yīng)到MapReduce框架：Map函數(shù)負(fù)責(zé)將待聚類的數(shù)據(jù)塊分配給距離最近的劃分中心點(diǎn)；Reduce函數(shù)負(fù)責(zé)更新劃分中心點(diǎn)。

Map函數(shù)：所有儲(chǔ)存在分布式存儲(chǔ)系統(tǒng)上的待聚類數(shù)據(jù)自動(dòng)分割并廣播給所有的Map任務(wù)節(jié)點(diǎn)。根據(jù)全局劃分中心點(diǎn)集合Cn={ci|ci∈X,i=1,2,…,m}，在每一個(gè)Map任務(wù)中計(jì)算出與對(duì)象具有最近距離的中心點(diǎn)并產(chǎn)生由距離最近的劃分中心點(diǎn)索引及對(duì)象本身組成的中間值。

Map過(guò)程結(jié)束后，對(duì)分配到同一個(gè)數(shù)據(jù)集中的數(shù)據(jù)進(jìn)行合并后送給Reduce函數(shù)。

Reduce函數(shù)：根據(jù)輸入的數(shù)據(jù)計(jì)算所有被分配到同一個(gè)數(shù)據(jù)集合中的數(shù)據(jù)總和及總數(shù)目，產(chǎn)生新的劃分中心點(diǎn)用于下一次迭代計(jì)算。

Map函數(shù)具體算法流程如算法1所示。

算法1Map函數(shù)算法

輸入：劃分中心點(diǎn)集，每行數(shù)據(jù)起始位置的偏移量k，行數(shù)據(jù)v。

輸出：(k1,v1),其中：k1是距離最近的劃分中心點(diǎn)的索引，v1是行數(shù)據(jù)本身。

Step1初始化Distance_min=Double.MAX_VALUE

Step2初始化index

Step3for (i=0，i

calcud(v,ci)；

ifd(v,ci)

Distance_min=d(v,ci)；

index=i；

end if

Step4k1=index，v1=行數(shù)據(jù)實(shí)例

Step5Output (k1,v1)

Reduce函數(shù)具體算法流程如算法2所示。

算法2Reduce函數(shù)算法

輸入：(k1,v1),其中：k1是距離最近的劃分中心點(diǎn)的索引，v1求和運(yùn)算后的部分和。

輸出：(k2,v2),其中：k2是距離最近的劃分中心點(diǎn)的索引，v2是新劃分中心點(diǎn)。

Step1初始化Array記錄v1中每個(gè)部分和每個(gè)維度的和

Step2初始化count對(duì)來(lái)自不同主機(jī)的中間數(shù)據(jù)集的計(jì)數(shù)部分counti求和

Step3while (there_is_nextv1())

obj=v1_next()；

for (inti=0;i

Array(i)+=obj；

count+=counti;

end for

Step4calcu Array/count得到新劃分中心點(diǎn)

Step5k2=k1，v2=新劃分中心點(diǎn)

Step6Output (k2,v2)

3 基于無(wú)偏分層圖抽樣的負(fù)載平衡方法

為了解決可能在連接操作中出現(xiàn)的負(fù)載不平衡問(wèn)題，本文引入無(wú)偏分層圖抽樣的方法。該算法由傳統(tǒng)的NS算法發(fā)展而來(lái)，在傳統(tǒng)NS算法的基礎(chǔ)上，加入了采樣系數(shù)動(dòng)態(tài)優(yōu)化，可以克服傳統(tǒng)NS算法抽樣時(shí)不能很好地保留數(shù)據(jù)集屬性及過(guò)度入樣的問(wèn)題。

3.1 無(wú)偏分層圖抽樣算法模型

在圖抽樣算法中，符號(hào)定義如下。

將圖表示為G=(V,E)，其中：V表示圖的節(jié)點(diǎn)集合V=(v1,v2，…，vn)；E表示圖的邊集合E=(e1,e2，…，en)；D=(d1,d2，…，dn)定義為圖中所有節(jié)點(diǎn)的度集合[19]。|V|表示節(jié)點(diǎn)集合中節(jié)點(diǎn)的數(shù)量，|E|表示邊集合中邊的數(shù)量。S=(VS,ES)表示抽樣得到的結(jié)果集，很明顯S是G的子集。p(0≤p≤1)表示抽樣比例。N表示抽樣點(diǎn)集合。

整個(gè)算法的流程如算法3所示。

算法3無(wú)偏分層圖抽樣算法

輸入：抽樣比例p，點(diǎn)集合N，邊集合E。

輸出：抽樣結(jié)果S=(Vs，Es)

Step1初始化Vs，Es

Step2k-means=k-means(distance，x)

Step3(Ndegree1，Ndegree2，…，Ndegreex)=k-means，run(D)

Step4Vdegree1=NS(p，Ndegree1)；

Vdegree2=NS(p，Ndegree2)；

?

Vdegreex=NS(p，Ndegreex)；

Step5Vs=Vdegree1∪Vdegree2∪…∪Vdegreex

Step6calcu ES(s-N,t-N)

Step7OutputS=(Vs，Es)

首先，利用K-means算法聚類目標(biāo)節(jié)點(diǎn)集合的度，得到節(jié)點(diǎn)的近似度分布。然后，根據(jù)近似度分布對(duì)目標(biāo)節(jié)點(diǎn)進(jìn)行分層，Step 2中的參數(shù)x即代表要分的層數(shù)。分層結(jié)束后，利用NS算法得到x層聚類后的節(jié)點(diǎn)集的抽樣。最后，計(jì)算得到抽樣結(jié)果中邊的集合并與節(jié)點(diǎn)集抽樣結(jié)果集組成最后的抽樣子集S。

相比于傳統(tǒng)的NS算法，無(wú)偏分層圖抽樣算法在抽樣的過(guò)程中加入了目標(biāo)節(jié)點(diǎn)度分布的考慮，可以有效地降低抽樣誤差。通過(guò)K-means算法首先獲得目標(biāo)節(jié)點(diǎn)集的近似度分布，可以用于指導(dǎo)抽樣規(guī)模的選取，使不同度的節(jié)點(diǎn)的入樣比例更加合理，從而使得抽樣結(jié)果集在保證保留節(jié)點(diǎn)集屬性的同時(shí)分布更加均勻。

3.2 基于無(wú)偏分層圖抽樣的負(fù)載平衡Map-Reduce框架實(shí)現(xiàn)

如圖3所示是基于無(wú)偏分層圖抽樣的MapReduce數(shù)據(jù)處理框架。

圖3 無(wú)偏分層圖抽樣MapReduce數(shù)據(jù)處理框架

首先，在m個(gè)Map節(jié)點(diǎn)上對(duì)大規(guī)模數(shù)據(jù)集進(jìn)行無(wú)偏分層圖抽樣，并執(zhí)行 K-means聚類，產(chǎn)生由劃分中心點(diǎn)索引和抽樣結(jié)果構(gòu)成的鍵值對(duì)送到n個(gè)Reduce節(jié)點(diǎn)；然后，使用 Reduce 程序合并來(lái)自m個(gè)節(jié)點(diǎn)的結(jié)果，獲得數(shù)據(jù)集的分布信息，產(chǎn)生新的劃分中心點(diǎn)。數(shù)據(jù)集分布信息作為調(diào)整抽樣系數(shù)的依據(jù)，新的劃分中心點(diǎn)用來(lái)進(jìn)行下一輪的聚類操作；其次，將數(shù)據(jù)分布信息及新的劃分中心點(diǎn)送回Map節(jié)點(diǎn)進(jìn)行下一輪抽樣和聚類。如果結(jié)束條件未能使判別函數(shù)收斂，則重復(fù)上述過(guò)程。判別函數(shù)主要由抽樣評(píng)價(jià)函數(shù)及數(shù)據(jù)負(fù)載評(píng)價(jià)函數(shù)構(gòu)成，在這里不作為重點(diǎn)討論。

經(jīng)過(guò)上述迭代過(guò)程的處理后，原始的大規(guī)模數(shù)據(jù)會(huì)在分層圖抽樣的操作下得到合理簡(jiǎn)化，并且由于抽樣規(guī)模在數(shù)據(jù)集分布信息的指導(dǎo)下進(jìn)行了動(dòng)態(tài)的調(diào)整，可以使得Map端和Reduce端的數(shù)據(jù)負(fù)載趨于平衡的分布。

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

為了驗(yàn)證本文數(shù)據(jù)處理算法的有效性，進(jìn)行了不同算法方案下的大數(shù)據(jù)處理的實(shí)驗(yàn)，對(duì)基于Hash法、NS抽樣方法、本文方法的MapReduce大數(shù)據(jù)處理算法進(jìn)行了對(duì)比實(shí)驗(yàn)。在合成數(shù)據(jù)集和真實(shí)數(shù)據(jù)集下，對(duì)比了采用不同算法的MapReduce大數(shù)據(jù)處理程序面對(duì)不同數(shù)據(jù)傾斜度的目標(biāo)數(shù)據(jù)集時(shí)的負(fù)載平衡能力以及程序本身聚類運(yùn)算耗時(shí)。

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

硬件環(huán)境：整個(gè)MapReduce處理集群由8個(gè)節(jié)點(diǎn)構(gòu)成，包括1個(gè)主節(jié)點(diǎn)和7個(gè)從節(jié)點(diǎn)，節(jié)點(diǎn)之間通過(guò)百兆網(wǎng)絡(luò)連接，且每個(gè)節(jié)點(diǎn)的配置相同：硬盤500 GB，內(nèi)存4 GB，處理器為雙核Inter(R)Pentium(R)CPU@3.7 GHz。

軟件環(huán)境：Linux；安裝Hadoop 2.2.0版本；采用JDK1.7編譯。

數(shù)據(jù)選擇：

(2) 真實(shí)數(shù)據(jù)集。實(shí)驗(yàn)采用從數(shù)據(jù)共享平臺(tái)獲取的包含具體事件的2 090 000篇新聞報(bào)道。各種不同事件的報(bào)道數(shù)量為：體育新聞352 000，娛樂(lè)新聞287 900，政治新聞213 500，教育新聞190 000，經(jīng)濟(jì)新聞126 900，社會(huì)新聞150 500，科技新聞159 400，文化新聞170 900，法制新聞122 800，其他新聞316 100。

4.2 實(shí)驗(yàn)結(jié)果

在前述實(shí)驗(yàn)環(huán)境下進(jìn)行了如下對(duì)照實(shí)驗(yàn)：

(1) 利用WorldCount程序測(cè)試不同數(shù)據(jù)傾斜程度下的合成數(shù)據(jù)集處理所需要的時(shí)間以對(duì)比三種算法在不同數(shù)據(jù)傾斜情況下的負(fù)載平衡性能。

(2) 利用真實(shí)數(shù)據(jù)集測(cè)試不同方法下的聚類運(yùn)行時(shí)間以對(duì)比三種算法的聚類程序執(zhí)行效率。

4.2.1MapReduce負(fù)載平衡性能評(píng)估實(shí)驗(yàn)

圖4所示為不同數(shù)據(jù)負(fù)載傾斜度下，基于Hash算法、傳統(tǒng)NS算法及無(wú)偏分層圖算法的MapReduce大數(shù)據(jù)處理程序運(yùn)行時(shí)間。實(shí)驗(yàn)中，Map和Reduce節(jié)點(diǎn)的數(shù)量都設(shè)置為7。

圖4 不同數(shù)據(jù)負(fù)載傾斜度下程序的運(yùn)行時(shí)間

可以看出，在負(fù)載傾斜度較低時(shí)，三種方案的程序運(yùn)行時(shí)間差距不大，基于Hash的方案在無(wú)數(shù)據(jù)傾斜時(shí)具有較低的運(yùn)行時(shí)間，這是因?yàn)樗乃惴ū旧韴?zhí)行時(shí)間較短。隨著負(fù)載傾斜度的增加，由于負(fù)載不平衡導(dǎo)致連接操作的時(shí)長(zhǎng)增加，基于Hash的程序運(yùn)行時(shí)間明顯上升；基于NS抽樣的程序運(yùn)行時(shí)間也出現(xiàn)了較為明顯的增加，這是因?yàn)樵谥囟葦?shù)據(jù)負(fù)載傾斜時(shí)，數(shù)據(jù)過(guò)度入樣的缺點(diǎn)得以呈現(xiàn)；基于所提出的無(wú)偏分層圖抽樣的程序執(zhí)行時(shí)間沒(méi)有出現(xiàn)明顯的增長(zhǎng)，說(shuō)明這種解決方案可以很好地在原始數(shù)據(jù)負(fù)載傾斜時(shí)平衡負(fù)載，避免產(chǎn)生連接操作延時(shí)。

通過(guò)上述實(shí)驗(yàn)結(jié)果，可以看出基于無(wú)偏分層圖抽樣算法的MapReduce在處理重度傾斜的數(shù)據(jù)時(shí)有很好的負(fù)載平衡效果。

4.2.2MapReduce聚類運(yùn)行時(shí)間評(píng)估實(shí)驗(yàn)

表2所示為每一輪聚類運(yùn)算的耗時(shí)、具有最大負(fù)載的Map/Reduce節(jié)點(diǎn)負(fù)載量和該輪聚類的運(yùn)行時(shí)間。實(shí)驗(yàn)中，Map和Reduce節(jié)點(diǎn)的數(shù)量都設(shè)置為7。

表2 每輪聚類運(yùn)算時(shí)間及最重負(fù)載節(jié)點(diǎn)負(fù)載量

可以看出，相比于其他兩種方法，基于Hash的MapReduce聚類每一輪都有較長(zhǎng)的運(yùn)行時(shí)間，對(duì)應(yīng)的負(fù)載最重節(jié)點(diǎn)的負(fù)載量也明顯高于另外兩種方法?；贜S抽樣的方法和基于無(wú)偏分層圖抽樣的方法運(yùn)行時(shí)間和負(fù)載最重節(jié)點(diǎn)負(fù)載量差距不明顯。這說(shuō)明在處理實(shí)驗(yàn)中的目標(biāo)真實(shí)數(shù)據(jù)集時(shí)，采用傳統(tǒng)NS采樣及本文算法都獲得了不錯(cuò)的負(fù)載平衡結(jié)果，并且采用了無(wú)偏分層圖抽樣算法后聚類算法的總體耗時(shí)并沒(méi)有因算法方案而增加。結(jié)合合成數(shù)據(jù)集下的實(shí)驗(yàn)結(jié)果，本文算法的MapReduce負(fù)載平衡方法可以在不增加聚類算法整體耗時(shí)的情況下，明顯改善MapReduce在處理嚴(yán)重傾斜的數(shù)據(jù)時(shí)的由于負(fù)載分配不平衡所導(dǎo)致的算法效率低下問(wèn)題。

4.3 算法的局限性及解決方案

由于本文方法首先是利用K-means算法聚類目標(biāo)節(jié)點(diǎn)集合的度，得到節(jié)點(diǎn)的近似度分布，因此在處理某些特定數(shù)據(jù)集時(shí)可能會(huì)由于K-means算法本身的局限影響整個(gè)算法數(shù)據(jù)處理效率。例如在處理沒(méi)有明確類別及聚類中心的數(shù)據(jù)時(shí)，隨機(jī)給定的分類數(shù)和聚類點(diǎn)可能對(duì)最終結(jié)果造成很大的影響，只能處理數(shù)值型的數(shù)據(jù)，對(duì)數(shù)據(jù)集中的異常點(diǎn)非常敏感等。針對(duì)不易分類及確定聚類點(diǎn)的情況，可以考慮采用K-means算法的改進(jìn)算法K-means++或ISODATA進(jìn)行優(yōu)化設(shè)計(jì)；在處理屬性型數(shù)據(jù)時(shí)，可以采用由K-means算法擴(kuò)展而來(lái)的K-modes算法；針對(duì)存在異常數(shù)據(jù)點(diǎn)的情況，可以采用數(shù)據(jù)預(yù)處理的方法，如LOF等將異常數(shù)據(jù)剔除，或者采用K-mediods算法；針對(duì)多種數(shù)據(jù)混合的數(shù)據(jù)集，可以采用K-prototypes算法進(jìn)行聚類。

由于本文的主要研究對(duì)象是無(wú)偏分層圖算法在MapReduce中的應(yīng)用，因此重點(diǎn)討論了使用較為廣泛的K-means算法的情況。

5 結(jié) 語(yǔ)

為了解決MapReduce框架連接操作中由于數(shù)據(jù)傾斜而導(dǎo)致的運(yùn)行效率下降問(wèn)題，本文提出一種基于無(wú)偏分層圖采樣的MapReduce負(fù)載平衡方法。該方法將抽樣算法與聚類算法有機(jī)結(jié)合，在獲取數(shù)據(jù)分布情況的前提下進(jìn)行抽樣操作，能夠同時(shí)提高聚類和抽樣算法的效率。通過(guò)標(biāo)準(zhǔn)Zipf數(shù)據(jù)集和真實(shí)數(shù)據(jù)集下的數(shù)據(jù)處理對(duì)比實(shí)驗(yàn)，驗(yàn)證了本文方法的有效性和高效性。未來(lái)，將進(jìn)行更大規(guī)模復(fù)雜數(shù)據(jù)集的實(shí)驗(yàn)以驗(yàn)證和改善本文方法。