基于MapReduce的數據立方體分區優化算法研究

張子浪+++葛昂+++鄭家民

【 摘 要 】 文章利用并行計算框架MapReduce，探索數據立方體的計算問題。數據立方體的計算存在兩個關鍵問題，一個是計算時間的問題，另一個是立方體的體積問題。隨著維度的增加，計算時間將呈現指數級的增長，立方體的體積也是如此。盡管MapReduce是一個優秀的并行計算框架，但在處理數據傾斜時，分區算法不夠完善，導致一些計算任務時間過長，影響整個作業的完成時間。本文通過數據采樣的方式，優化數據分區，實驗結果表明，數據立方體的計算的性能明顯提升。為解決數據立方體體積過大的問題，在Reduce階段將最終的結果輸出到基于NoSQL的HBase數據庫進行存儲，HBase方便水平擴展，同時也便于日后對數據立方體的查詢。

【 關鍵詞 】 數據立方體；數據分區；數據分析

【 文獻標識碼 】 A

1 引言

在互聯網和電子商務領域，一些運營商以及電子商務平臺提供商擁有大量的用戶，并以云計算的方式向用戶提供服務，這些服務響應用戶的請求，在后端產生相應的數據，由于數據的集中儲存以及用戶的頻繁請求，使得數據量呈現快速增長。在電子政務領域，一些政府部門根據自身信息化的發展水平及業務發展的需要，將信息化系統集中部署到省級機構，各地、市通過專網訪問。這其中信息化化建設步伐更快的政府部門，在省級集中的基礎上，實行全國數據的集中。在科學試驗領域，科學家所觀測的對象也產生了大量的數據，比如天文學當中利用天文望遠鏡，只需幾天的時間，并能掃描半個天空。

就這些領域的數據產生速度而言，一些IT系統每天產生TB級的數據量，有的則多達PB級。有了大量的數據，就會產生數據挖掘的需求，包括對數據進行匯總分析。數據立方體能夠很好地表達多維的結構化數據的匯總分析，傳統的聯機分析（OLAP）技術對于立方體的計算方法也相對較為成熟。傳統的OLAP根據數據儲存方式的不同，可分為兩類：一類是ROLAP，以關系表進行多維數據的表示和存儲；另一類是MOLAP，以多維數組進行多維數據的表示和存儲。ROLAP計算數據立方體就是利用SQL中的group by語句對特定維度屬性集合的所有子集分別集合，后來引入了Cube操作，一個Cube等價于多個Group by。MOLAP計算數據立方體時基于數組對數據進行集合，一種比較成熟的算法是多路數據聚集算法。

盡管基于傳統的數據立方體的并行計算的算法比較成熟，但其不能直接應用于大數據的計算，因為由于這些大數據基于文件系統存儲，而不是基于關系型數據庫存儲或者數組，而且，其數據量也大得多。

針對大數據的分析，Google提出了map-reduce的并行計算框架，結合上千臺的廉價PC服務器，使得大數據的分析能夠在很短時間之內完成，Hadoop是基于該編程模型的開源實現。 利用Hadoop進行數據立方體進行計算的研究相對較少，有的利用Hadoop計算數據立方體，但沒有考慮數據的優化分區，直接采用Hadoop缺省的分區方式，這種方式存在缺陷，不能讓高度傾斜的數據（少數幾個鍵值出現的次數占據了非常大的比例）均勻分配給各個并行的計算任務，導致某些計算任務的輸入數據過多，從而導致其完成時間滯后于其它計算任務，影響整個作業的完成時間。

本文給出了基于Map-Reduce計算數據立方體的算法以及分區優化算法，為讓數據均勻分布到各個Reduce任務，采用數據抽樣的方式決定采用何種分區方式，為并行計算立方體提供了一種新方式。

數據立方體有多種，完整數據立方體，冰山立方體，封閉立方體。冰山立方體和封閉立方體考慮了數據立方體的體積，減少不必要的存儲。由于封閉立方體或者冰山立方體中的某一個子立方體很可能就是一個完整的立方體，因此，計算完整立方體的過程不可避免，而且，完整立方體也是其它立方體的基礎。所以本文研究完整立方體的計算。

在此先介紹并行計算、數據立方體、Hadoop的相關概念，給出通用的計算數據立方體的Hadoop實現，在分析可能由于數據分布不平衡而導致的計算不平衡的基礎上，設計基于抽樣的分區算法。然后結合實驗對算法進行分析。最后對當前工作進行總結，并提出未來的可能研究方向。

2 概念

2.1 數據立方體

實體關系模型主要應用于在關系型數據庫中，這樣的二維數據模型比較適合事務處理，但是不適合數據的在線分析。在數據倉庫當中，往往需要從多個角度對數據進行分析，因此需要多維的數據模型，數據立方體就是用來描述多維數據模型的。

給定基本關系R（A1，A2，A3，…，An，M），由R產生的數據立方體是R的屬性的所有的可能組合，n個屬性產生2n個組合。A1，A2，A3，…，An為立方體的屬性維，M為度量維，M是一個數字函數，描述數據以何種方式進行聚合或者計算。

取n=3，即基本關系R（A1，A2，A3，M）產生的立方體由以下分組構成：

{（A1，A2，A3），（A1，A2），（A1，A3），（A2，A3），（A1），（A2），（A3），（）}。

度量維常見的聚合函數有SUM，MAX，MIN，AVG等。聚合函數可分為三類，分別是分布式，代數式，綜合式的。考慮對分組P中的元素進行聚合。

分布式的聚合函數：，Pi（i=1，2，3，…n）為P的兩兩不相交的子集，即∪Pni=1=P并且□ij，i≠j，Pi∩Pj=?，如果存在函數G，使得F（P）=G（F（P1）， F（P2）， …，F（Pn）），那么稱聚合函數F為分布式式函數。COUNT（）， MIN（）， MAX（），SUM（）都是分布式函數。除了COUNT函數外，其余三個幾個函數F=G。對于COUNT函數而言，G=SUM，即COUNT（P）=SUM（COUNT（P1）， COUNT（P2）， COUNT（P3），…， COUNT（Pn））。endprint

代數式聚合函數：Pi（i=1，2，3，…n）為P的兩兩不相交的子集，∪Pni=1=P并且□ij，i≠j，Pi∩Pj=?，如果存在函數G和函數H（對于所有的Pi，H函數返回一個k元組），使得F（P）=G（H （P1）， H（P2）， …，H （Pn）），那么稱聚合函數F為分布式式函數。AVG函數就是代數式函數，對每個每個Pi，H函數返回一個二元組（sumi，counti），G函數對所有的sumi及counti分別相加，然后相除產生整體的平均值，即 。

整體式聚合函數：既不是分布式的函數以及代數式的函數稱之為整體式聚合函數。

在對一個大的數據集進行聚合時，如果聚合函數是分布式函數或者代數式函數，那么可以采用分而治之的思想，可以將大的數據集為眾多小的數據集，然后對每個小的數據集進行計算，最后對中間的計算結果進行匯總，從而得到整體的計算結果。

2.2 MapReduce

MapReduce是基于非共享的并行計算模型，該模型能夠充分利用由多臺機器組成的計算、存儲、網絡資源并行地處理計算任務， 適合處理與大數據相關的統計分析。

MapReduce并行計算模型與其它并行計算相比，主要有兩個特點：一是其對串行任務與并行任務的隔離，以及計算任務能夠在各個計算節點上獨立地進行；二是編程模型簡潔，學習成本低。MapReduce將計算分為兩個階段：Map階段和Reduce階段。首先，一個大的輸入文件被分割成M塊，分別由m個并行運行的Map任務進行處理，每個map任務以鍵值對的形式接收輸入，對于每一個記錄，將其轉為的形式，然后由reduce任務進行處理，輸出鍵值對。

2.3 NoSQL

關系型數據庫自20世紀70年代誕生以來，在企業和政府的信息化建設中得到了廣泛的應用，今天關系型數據依然發揮著重要的作用。然而，對于以PB衡量的大數據，關系型數據庫不能很好地應對。這些數據的特點的是數據類型多樣，包括結構化、半結構化，非結構化的數據，另一個特點是數據量大。非關系型的NoSQL數據庫適合這類數據的存儲。NoSQL具有三個特點：一是以Key-Value作為存儲模型；二是保證數據的最終一致性；三是在保證應用不間斷的情況下方便實現水平擴展。NoSQL數據庫主要包括Cassandra、HBase、mongoDB等。這三種作為NoSQL數據庫中的主流代表，在很多生產系統中得到了應用，在處理大數據時，能保持很好的性能，都是較為成熟的產品。當然，這幾種NoSQL數據庫的系統架構不一樣，側重點也不一樣。HBase的文件系統基于HDFS，能與Hadoop的MapReduce并行計算框架無縫集成。由于本文選用的是Hadoop的MapReduce并行計算框架，因此NoSQL數據庫采用HBase。

3 算法

算法除了實現MapReduce中的map接口和reduce接口之外，還實現了getPartition分區接口。Map函數根據關系模式R的n個屬性（A1，A1，A3，...，An），形成2n個所有屬性的可能組合，再取得相應屬性的值作為鍵值，這樣，在map階段，每條輸入記錄將產生2n個中間的鍵值對。為保證每個Reduce任務的負載大致相同，分區算法通過抽樣的方式，統計每個鍵出現的頻率，以每個鍵的頻率之和度量分區的負載，盡可能讓每個分區的負載大致相等。Combine函數根據具有分布式或者代數式性質的函數M對數據進行聚合，把中間結果中具有相同key進行合并，形成一個鍵值對。Reduce的實現相與Combine相似，只是在輸出的時候有差異，Reduce將最終結果保存至HBase數據庫。

3.1 Map/Reduce實現

算法形式化描述：

//R由n個屬性組成的關系模式

R={A1，A2，A3…，An}

//e為輸入文件中一條記錄

Map（e）

{

//根據關系模式R和e產生中間的key

//每個輸入元素e產生2n-1個key

emitKeyBySubSetOfR（0，n，R，e）

}

emitKeyBySubSetOfR（begin，end，R）

{

//計算包含R[i]的子集

for（i=begin；i

{

stack.push（R[i]）；

}

//i自增，計算不包含R[i]的子集

emitKeyBySubSetOfR（i+1，end）；

//I為R的一個子集

I={}

for（each o in stack）

{

I=I∪o

}

//元素e取I中的屬性形成鍵值k

k=I（e）

emit（k，e）

stack.pop（）；

}

//中間結果保存到文件

Combine（k， iterator values））

{

total=0；

while（e=（values.nextvalue（））

{

total=M（total，M（e））

}

emit2file（k，total）；

}

計算最終結果并保存至hbase數據庫

Reduce （k， iterator values））

{

total=0；

while（e=（values.nextvalue（））

{

total=M（total，M（e））

}

emit2hbase（k，total）；

}

3.2 Partition實現

每個Map任務會輸出一系列的以鍵值對（）形式的記錄，然后由Reduce任務進行處理。由于存在多個Reduce任務，具體的一條記錄由哪個Reduce任務處理，是由分區函數決定的。Hadoop中缺省采用hash函數對Map任務輸出記錄的鍵值進行分區，由于每個分區只由一個Reduce任務處理，因此分區的數量等于Reduce任務的數量，每個Reduce任務處理一個分區。分區函數的形式描述為：

hash （Hash code （Intermediate-key） % numReduceTasks）

Hadoop中的Java實現如下：

public class HashPartitioner extends Partitioner {

public int getPartition（K key， V value，

int numReduceTasks） {

return （key.hashCode（） & Integer.MAX_VALUE） % numReduceTasks；

}

Hash函數能夠保證每個分區中鍵（Key）的數量大致相同。假設有k個不同的鍵，由r個reduce任務處理，分區函數能夠保證每個reduce任務處理鍵的數量為k/r。然而由于有的鍵（Key）頻繁出現，即很多記錄具有相同的鍵值，顯然，分區中包含這樣的鍵其數據量要大的多，所需的計算時間也更長。

建設有6個鍵，分別是K1，K2，K3，K4，K5，K6，每個鍵包含的記錄數分別為1，2，3，4，5，6，這6個鍵由3個Reduce任務處理。采用hash分區策略，會形成3個分區，Partition1包含K1和K4，Partition2包含K2和K5，Partiton3包含K3和K6。盡管每個分區包含鍵的數量都為2，但是每個分區的數據量不一致。Partition1包含5條記錄，Partition2包含7條記錄，Partiton3包含9條記錄。理想的情況應該是每個分區包含7條記錄。

為了達到圖2中均勻分區的效果，需要自定義分區函數。分區函數需要事先知道鍵的分布頻率，如果數據集比較大，掃描整個數據集并求出各個鍵的分布頻率，所需的時間比較長。可對數據集進行抽樣，只針對一小部分數據進行統計，數據抽樣的時間與整個計算任務的時間相比，可忽略不計。

假設一個數據集中包含k個不同Key，鍵值分別為K1，K2，K3，…，Kk，其出現的頻率為f（ki），共有r個Reduce任務。每個Reduce任務的負載定義為其相應的分區的大小，分區大小可用該分區內記錄數量大數目衡量，即分區內各個Key的頻率之和。

分區算法的目標是讓各個LRi的值盡可能接近。

R=new ArrayList（）；//初始時，每個Reduce的負載為0

K = {K1， . . . ， Kk}；//K為待分區的key的集合

While（K.length>0）//如果還有Key沒有分配到某個Reduce中

{ //選取頻率數最大的分配給某個Ri

kmax = argmaxk∈Kf（k）

//從待分區的key集合中移除

K.remove（kmax）

//如果存在某個Ri沒有負載

if（R.length < r）

{ keylistofRi={}；

keylistofRi.add（kmax）；

//直接將該key分配給Ri

R.add（keylistofRi）；

}

//如果所有的Ri都有負載，那么將該key分配給目//前負載最小的Ri

else

{

keyListOfminLRi = argminiRi∈RLRi

R.remove（keyListOfminLRi）

keyListOfminLRi.add（kmax）

R.add（keyListOfminLRi）

}

}

return R；

這樣，分區函數P能夠將Ki分配給Rj處理，記為P（Ki， Rj）。通過抽樣形成的分區方案存入分布式緩存當中，每個map任務按照分布時緩存中的分區方案P（Ki， Rj）對數據進行分區。

4 實驗

為測試數據立方體計算的空間需求和性能，采用8個節點組成的Hadoop集群，每個節點的CPU為4核3.1GZ，內存為4GB，本地存儲為500G，操作系統環境為Windows Server 2003。每個節點分別運行一個Map任務和Reduce任務，輸入數據為根據Zipf分布人工合成，數據的傾斜程度通過參數z值控制，z的取值范圍是[0，1]，較大的z值表明更高的傾斜程度。

每個輸入Map接收500萬條記錄，輸入數據共4000萬條記錄。每個記錄包含4個屬性，其中一個屬性的類型為數字，作為度量維度，另三個為字符類型，作為屬性維。聚合函數采用具有分布式函數特性的sum函數。

為在數據抽樣的比例和精確性之間進行平衡，通過多次試驗，發現以5%的比例進行抽樣時，誤差較小。按這個比例進行數據抽樣時，數據抽樣的完成時間為[5-8]s，這個時間與幾百秒的計算任務而言，可忽略不計，以下有關完成時間的描述，均未將抽樣時間計算在內。

當取z=0，即數據均勻分布，分區算法采用Hadoop中的缺省分區函數時，最快的Reduce任務用時130s，最慢的用時131s；當采用自定義分區函數時，最快的用時132s，最慢的用時132.5s。

當取z=0.6，即數據出現較高程度的傾斜，分區算法采用Hadoop中缺省分區函數時，最快的Reduce任務用時90s，最慢的用時331s；當采用自定義分區算法時，最快133s，最慢的用時138s。

隨著z取更高的值，兩個分區算法性能差異明顯，一度出現缺省分區函數比自定義分區函數慢6倍的情況。

顯然，自定義分區算法在輸入數據無重復的情況下，性能與默認的分區函數相當，然而當輸入大量重復，發生傾斜時，自定義分區函數獲得的性能提升非常明顯。

當屬性維度分別從3增加為6和8時，不管采用何種分區算法，計算時間呈現指數級增長的趨勢，這主要和每個輸入記錄產生2n個中間記錄有關。

5 結束語

本文基于開源的Hadoop框架對完整數據立方體的計算進行了初步探索。Hadoop并行計算框架非常優秀，簡化了并行計算的編程模型，使得并行數據立方體的計算很容易實現。然而，數據立方體的計算性能非常重要，數據分區是影響性能的一個重要因素，因為并行計算的前提是各個計算任務的負載大致相同。Hadoop的缺省分區機制在多數場合能夠讓每個Reduce任務的負載大致相同，然而在數據高度傾斜的情況容易導致計算偏斜。

本文從優化數據分區著手，采用抽樣方式對分區算法進行了一定優化，當目標問題為分布式或者代數式的集合函數時，能夠在一定程度上解決因為數據傾斜而導致的數據立方體的計算性能問題。

在系統架構方面，選用HBase存儲數據立方體，以便水平擴展，應對數據立方體積快速增加的問題。實驗結果表明，性能提升明顯。此外，影響Hadoop的性能的因素有很多，比如集群的數量和集群中計算節點的數量，每個計算節點中運行的map任務和reduce任務的數量，以及網絡帶寬的情況，還有數據復制因子的影響，這些在未來的研究中也會涉及到。

參考文獻

[1] Lammel， R.： Googles MapReduce Programming Model - Revisited[J]. Science of Computer Programming 70，2008， 1-30.

[2] Dean， J. and Ghemawat， S. Mapreduce： simplified data processing on large clusters[J]. COMMUNICATIONS OF THE ACM 51，2008.

[3] B. Gufler， N. Augsten， A. Reiser， and A. Kemper. Handling.

data skew in mapreduce. In The First International Conference on Cloud Computing and Services Science，2011，574-583.

[4] J. Gray， S. Chaudhuri， A. Bosworth， A. Layman， D. Reichart， M.Venkatrao，F. Pellow， and H. Pirahesh. Data Cube： A Relational Operator Generalizing Group-By， Cross-Tab and Sub-Totals[J].

Data Mining and Knowledge Discovery， 1996， 29-53.

[5] S. Ibrahim， H. Jin， L. Lu， S. Wu， B. He， and L. Qi. LEEN：Locality/Fairness-Aware Key Partitioning for MapReduce in the Cloud. In Cloud Computing Technology and Science （CloudCom）， 2010 IEEE Second International Conference on，2010，17-24.

作者簡介：

張子浪 （1978-），男，中國社會科學院研究生院，MBA，工程師；主要研究方向和關注領域：多維數據聚合。

葛昂，男，北京大學，MBA，高級工程師；主要研究方向和關注領域：數據挖掘、企業架構。

鄭家民，男，北京航空航天大學，軟件工程，高級工程師；主要研究方向和關注領域：數據挖掘、企業架構。endprint

為在數據抽樣的比例和精確性之間進行平衡，通過多次試驗，發現以5%的比例進行抽樣時，誤差較小。按這個比例進行數據抽樣時，數據抽樣的完成時間為[5-8]s，這個時間與幾百秒的計算任務而言，可忽略不計，以下有關完成時間的描述，均未將抽樣時間計算在內。

當取z=0，即數據均勻分布，分區算法采用Hadoop中的缺省分區函數時，最快的Reduce任務用時130s，最慢的用時131s；當采用自定義分區函數時，最快的用時132s，最慢的用時132.5s。

當取z=0.6，即數據出現較高程度的傾斜，分區算法采用Hadoop中缺省分區函數時，最快的Reduce任務用時90s，最慢的用時331s；當采用自定義分區算法時，最快133s，最慢的用時138s。

隨著z取更高的值，兩個分區算法性能差異明顯，一度出現缺省分區函數比自定義分區函數慢6倍的情況。

顯然，自定義分區算法在輸入數據無重復的情況下，性能與默認的分區函數相當，然而當輸入大量重復，發生傾斜時，自定義分區函數獲得的性能提升非常明顯。

當屬性維度分別從3增加為6和8時，不管采用何種分區算法，計算時間呈現指數級增長的趨勢，這主要和每個輸入記錄產生2n個中間記錄有關。

5 結束語

本文基于開源的Hadoop框架對完整數據立方體的計算進行了初步探索。Hadoop并行計算框架非常優秀，簡化了并行計算的編程模型，使得并行數據立方體的計算很容易實現。然而，數據立方體的計算性能非常重要，數據分區是影響性能的一個重要因素，因為并行計算的前提是各個計算任務的負載大致相同。Hadoop的缺省分區機制在多數場合能夠讓每個Reduce任務的負載大致相同，然而在數據高度傾斜的情況容易導致計算偏斜。

本文從優化數據分區著手，采用抽樣方式對分區算法進行了一定優化，當目標問題為分布式或者代數式的集合函數時，能夠在一定程度上解決因為數據傾斜而導致的數據立方體的計算性能問題。

在系統架構方面，選用HBase存儲數據立方體，以便水平擴展，應對數據立方體積快速增加的問題。實驗結果表明，性能提升明顯。此外，影響Hadoop的性能的因素有很多，比如集群的數量和集群中計算節點的數量，每個計算節點中運行的map任務和reduce任務的數量，以及網絡帶寬的情況，還有數據復制因子的影響，這些在未來的研究中也會涉及到。

參考文獻

[1] Lammel， R.： Googles MapReduce Programming Model - Revisited[J]. Science of Computer Programming 70，2008， 1-30.

[2] Dean， J. and Ghemawat， S. Mapreduce： simplified data processing on large clusters[J]. COMMUNICATIONS OF THE ACM 51，2008.

[3] B. Gufler， N. Augsten， A. Reiser， and A. Kemper. Handling.

data skew in mapreduce. In The First International Conference on Cloud Computing and Services Science，2011，574-583.

[4] J. Gray， S. Chaudhuri， A. Bosworth， A. Layman， D. Reichart， M.Venkatrao，F. Pellow， and H. Pirahesh. Data Cube： A Relational Operator Generalizing Group-By， Cross-Tab and Sub-Totals[J].

Data Mining and Knowledge Discovery， 1996， 29-53.

[5] S. Ibrahim， H. Jin， L. Lu， S. Wu， B. He， and L. Qi. LEEN：Locality/Fairness-Aware Key Partitioning for MapReduce in the Cloud. In Cloud Computing Technology and Science （CloudCom）， 2010 IEEE Second International Conference on，2010，17-24.

作者簡介：

張子浪 （1978-），男，中國社會科學院研究生院，MBA，工程師；主要研究方向和關注領域：多維數據聚合。

葛昂，男，北京大學，MBA，高級工程師；主要研究方向和關注領域：數據挖掘、企業架構。

鄭家民，男，北京航空航天大學，軟件工程，高級工程師；主要研究方向和關注領域：數據挖掘、企業架構。endprint

為在數據抽樣的比例和精確性之間進行平衡，通過多次試驗，發現以5%的比例進行抽樣時，誤差較小。按這個比例進行數據抽樣時，數據抽樣的完成時間為[5-8]s，這個時間與幾百秒的計算任務而言，可忽略不計，以下有關完成時間的描述，均未將抽樣時間計算在內。

當取z=0，即數據均勻分布，分區算法采用Hadoop中的缺省分區函數時，最快的Reduce任務用時130s，最慢的用時131s；當采用自定義分區函數時，最快的用時132s，最慢的用時132.5s。

當取z=0.6，即數據出現較高程度的傾斜，分區算法采用Hadoop中缺省分區函數時，最快的Reduce任務用時90s，最慢的用時331s；當采用自定義分區算法時，最快133s，最慢的用時138s。

隨著z取更高的值，兩個分區算法性能差異明顯，一度出現缺省分區函數比自定義分區函數慢6倍的情況。

顯然，自定義分區算法在輸入數據無重復的情況下，性能與默認的分區函數相當，然而當輸入大量重復，發生傾斜時，自定義分區函數獲得的性能提升非常明顯。

當屬性維度分別從3增加為6和8時，不管采用何種分區算法，計算時間呈現指數級增長的趨勢，這主要和每個輸入記錄產生2n個中間記錄有關。

5 結束語

本文基于開源的Hadoop框架對完整數據立方體的計算進行了初步探索。Hadoop并行計算框架非常優秀，簡化了并行計算的編程模型，使得并行數據立方體的計算很容易實現。然而，數據立方體的計算性能非常重要，數據分區是影響性能的一個重要因素，因為并行計算的前提是各個計算任務的負載大致相同。Hadoop的缺省分區機制在多數場合能夠讓每個Reduce任務的負載大致相同，然而在數據高度傾斜的情況容易導致計算偏斜。

本文從優化數據分區著手，采用抽樣方式對分區算法進行了一定優化，當目標問題為分布式或者代數式的集合函數時，能夠在一定程度上解決因為數據傾斜而導致的數據立方體的計算性能問題。

在系統架構方面，選用HBase存儲數據立方體，以便水平擴展，應對數據立方體積快速增加的問題。實驗結果表明，性能提升明顯。此外，影響Hadoop的性能的因素有很多，比如集群的數量和集群中計算節點的數量，每個計算節點中運行的map任務和reduce任務的數量，以及網絡帶寬的情況，還有數據復制因子的影響，這些在未來的研究中也會涉及到。

參考文獻

[1] Lammel， R.： Googles MapReduce Programming Model - Revisited[J]. Science of Computer Programming 70，2008， 1-30.

[2] Dean， J. and Ghemawat， S. Mapreduce： simplified data processing on large clusters[J]. COMMUNICATIONS OF THE ACM 51，2008.

[3] B. Gufler， N. Augsten， A. Reiser， and A. Kemper. Handling.

data skew in mapreduce. In The First International Conference on Cloud Computing and Services Science，2011，574-583.

[4] J. Gray， S. Chaudhuri， A. Bosworth， A. Layman， D. Reichart， M.Venkatrao，F. Pellow， and H. Pirahesh. Data Cube： A Relational Operator Generalizing Group-By， Cross-Tab and Sub-Totals[J].

Data Mining and Knowledge Discovery， 1996， 29-53.

[5] S. Ibrahim， H. Jin， L. Lu， S. Wu， B. He， and L. Qi. LEEN：Locality/Fairness-Aware Key Partitioning for MapReduce in the Cloud. In Cloud Computing Technology and Science （CloudCom）， 2010 IEEE Second International Conference on，2010，17-24.

作者簡介：

張子浪 （1978-），男，中國社會科學院研究生院，MBA，工程師；主要研究方向和關注領域：多維數據聚合。

葛昂，男，北京大學，MBA，高級工程師；主要研究方向和關注領域：數據挖掘、企業架構。

鄭家民，男，北京航空航天大學，軟件工程，高級工程師；主要研究方向和關注領域：數據挖掘、企業架構。endprint