杜 鵑 張 卓 曹建春

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

0 引 言

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

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

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

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

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

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

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

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

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

1 相關(guān)研究

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

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

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

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

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

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

2.1 MapReduce算法框架

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

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

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

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

圖1 MapReduce運算流程

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

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

2.2 聚類算法

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

圖2 同一原始對象集合的不同聚類

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

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

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

表1 符號定義表

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

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

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

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

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

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

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

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

輸出：(k1,v1),其中：k1是距離最近的劃分中心點的索引，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ù)實例

Step5Output (k1,v1)

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

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

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

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

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

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

Step3while (there_is_nextv1())

obj=v1_next()；

for (inti=0;i

Array(i)+=obj；

count+=counti;

end for

Step4calcu Array/count得到新劃分中心點

Step5k2=k1，v2=新劃分中心點

Step6Output (k2,v2)

3 基于無偏分層圖抽樣的負載平衡方法

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

3.1 無偏分層圖抽樣算法模型

在圖抽樣算法中，符號定義如下。

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

整個算法的流程如算法3所示。

算法3無偏分層圖抽樣算法

輸入：抽樣比例p，點集合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é)點集合的度，得到節(jié)點的近似度分布。然后，根據(jù)近似度分布對目標(biāo)節(jié)點進行分層，Step 2中的參數(shù)x即代表要分的層數(shù)。分層結(jié)束后，利用NS算法得到x層聚類后的節(jié)點集的抽樣。最后，計算得到抽樣結(jié)果中邊的集合并與節(jié)點集抽樣結(jié)果集組成最后的抽樣子集S。

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

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

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

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

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

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

4 實驗與結(jié)果分析

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

4.1 實驗環(huán)境

硬件環(huán)境：整個MapReduce處理集群由8個節(jié)點構(gòu)成，包括1個主節(jié)點和7個從節(jié)點，節(jié)點之間通過百兆網(wǎng)絡(luò)連接，且每個節(jié)點的配置相同：硬盤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ù)據(jù)集。實驗采用從數(shù)據(jù)共享平臺獲取的包含具體事件的2 090 000篇新聞報道。各種不同事件的報道數(shù)量為：體育新聞352 000，娛樂新聞287 900，政治新聞213 500，教育新聞190 000，經(jīng)濟新聞126 900，社會新聞150 500，科技新聞159 400，文化新聞170 900，法制新聞122 800，其他新聞316 100。

4.2 實驗結(jié)果

在前述實驗環(huán)境下進行了如下對照實驗：

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

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

4.2.1MapReduce負載平衡性能評估實驗

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

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

可以看出，在負載傾斜度較低時，三種方案的程序運行時間差距不大，基于Hash的方案在無數(shù)據(jù)傾斜時具有較低的運行時間，這是因為它的算法本身執(zhí)行時間較短。隨著負載傾斜度的增加，由于負載不平衡導(dǎo)致連接操作的時長增加，基于Hash的程序運行時間明顯上升；基于NS抽樣的程序運行時間也出現(xiàn)了較為明顯的增加，這是因為在重度數(shù)據(jù)負載傾斜時，數(shù)據(jù)過度入樣的缺點得以呈現(xiàn)；基于所提出的無偏分層圖抽樣的程序執(zhí)行時間沒有出現(xiàn)明顯的增長，說明這種解決方案可以很好地在原始數(shù)據(jù)負載傾斜時平衡負載，避免產(chǎn)生連接操作延時。

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

4.2.2MapReduce聚類運行時間評估實驗

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

表2 每輪聚類運算時間及最重負載節(jié)點負載量

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

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

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

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

5 結(jié) 語

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