基于MapReduce的數(shù)據(jù)立方體分區(qū)優(yōu)化算法研究

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

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

【 關(guān)鍵詞 】 數(shù)據(jù)立方體；數(shù)據(jù)分區(qū)；數(shù)據(jù)分析

【 文獻(xiàn)標(biāo)識碼 】 A

1 引言

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

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

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

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

本文給出了基于Map-Reduce計算數(shù)據(jù)立方體的算法以及分區(qū)優(yōu)化算法，為讓數(shù)據(jù)均勻分布到各個Reduce任務(wù)，采用數(shù)據(jù)抽樣的方式?jīng)Q定采用何種分區(qū)方式，為并行計算立方體提供了一種新方式。

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

在此先介紹并行計算、數(shù)據(jù)立方體、Hadoop的相關(guān)概念，給出通用的計算數(shù)據(jù)立方體的Hadoop實現(xiàn)，在分析可能由于數(shù)據(jù)分布不平衡而導(dǎo)致的計算不平衡的基礎(chǔ)上，設(shè)計基于抽樣的分區(qū)算法。然后結(jié)合實驗對算法進(jìn)行分析。最后對當(dāng)前工作進(jìn)行總結(jié)，并提出未來的可能研究方向。

2 概念

2.1 數(shù)據(jù)立方體

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

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

取n=3，即基本關(guān)系R（A1，A2，A3，M）產(chǎn)生的立方體由以下分組構(gòu)成：

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

度量維常見的聚合函數(shù)有SUM，MAX，MIN，AVG等。聚合函數(shù)可分為三類，分別是分布式，代數(shù)式，綜合式的?？紤]對分組P中的元素進(jìn)行聚合。

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

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

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

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

2.2 MapReduce

MapReduce是基于非共享的并行計算模型，該模型能夠充分利用由多臺機(jī)器組成的計算、存儲、網(wǎng)絡(luò)資源并行地處理計算任務(wù)， 適合處理與大數(shù)據(jù)相關(guān)的統(tǒng)計分析。

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

2.3 NoSQL

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

3 算法

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

3.1 Map/Reduce實現(xiàn)

算法形式化描述：

//R由n個屬性組成的關(guān)系模式

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

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

Map（e）

{

//根據(jù)關(guān)系模式R和e產(chǎn)生中間的key

//每個輸入元素e產(chǎn)生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（）；

}

//中間結(jié)果保存到文件

Combine（k， iterator values））

{

total=0；

while（e=（values.nextvalue（））

{

total=M（total，M（e））

}

emit2file（k，total）；

}

計算最終結(jié)果并保存至hbase數(shù)據(jù)庫

Reduce （k， iterator values））

{

total=0；

while（e=（values.nextvalue（））

{

total=M（total，M（e））

}

emit2hbase（k，total）；

}

3.2 Partition實現(xiàn)

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

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

Hadoop中的Java實現(xiàn)如下：

public class HashPartitioner extends Partitioner {

public int getPartition（K key， V value，

int numReduceTasks） {

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

}

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

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

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

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

分區(qū)算法的目標(biāo)是讓各個LRi的值盡可能接近。

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

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

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

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

kmax = argmaxk∈Kf（k）

//從待分區(qū)的key集合中移除

K.remove（kmax）

//如果存在某個Ri沒有負(fù)載

if（R.length < r）

{ keylistofRi={}；

keylistofRi.add（kmax）；

//直接將該key分配給Ri

R.add（keylistofRi）；

}

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

else

{

keyListOfminLRi = argminiRi∈RLRi

R.remove（keyListOfminLRi）

keyListOfminLRi.add（kmax）

R.add（keyListOfminLRi）

}

}

return R；

這樣，分區(qū)函數(shù)P能夠?qū)i分配給Rj處理，記為P（Ki， Rj）。通過抽樣形成的分區(qū)方案存入分布式緩存當(dāng)中，每個map任務(wù)按照分布時緩存中的分區(qū)方案P（Ki， Rj）對數(shù)據(jù)進(jìn)行分區(qū)。

4 實驗

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

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

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

當(dāng)取z=0，即數(shù)據(jù)均勻分布，分區(qū)算法采用Hadoop中的缺省分區(qū)函數(shù)時，最快的Reduce任務(wù)用時130s，最慢的用時131s；當(dāng)采用自定義分區(qū)函數(shù)時，最快的用時132s，最慢的用時132.5s。

當(dāng)取z=0.6，即數(shù)據(jù)出現(xiàn)較高程度的傾斜，分區(qū)算法采用Hadoop中缺省分區(qū)函數(shù)時，最快的Reduce任務(wù)用時90s，最慢的用時331s；當(dāng)采用自定義分區(qū)算法時，最快133s，最慢的用時138s。

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

顯然，自定義分區(qū)算法在輸入數(shù)據(jù)無重復(fù)的情況下，性能與默認(rèn)的分區(qū)函數(shù)相當(dāng)，然而當(dāng)輸入大量重復(fù)，發(fā)生傾斜時，自定義分區(qū)函數(shù)獲得的性能提升非常明顯。

當(dāng)屬性維度分別從3增加為6和8時，不管采用何種分區(qū)算法，計算時間呈現(xiàn)指數(shù)級增長的趨勢，這主要和每個輸入記錄產(chǎn)生2n個中間記錄有關(guān)。

5 結(jié)束語

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

本文從優(yōu)化數(shù)據(jù)分區(qū)著手，采用抽樣方式對分區(qū)算法進(jìn)行了一定優(yōu)化，當(dāng)目標(biāo)問題為分布式或者代數(shù)式的集合函數(shù)時，能夠在一定程度上解決因為數(shù)據(jù)傾斜而導(dǎo)致的數(shù)據(jù)立方體的計算性能問題。

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

參考文獻(xiàn)

[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(xiàn). 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-），男，中國社會科學(xué)院研究生院，MBA，工程師；主要研究方向和關(guān)注領(lǐng)域：多維數(shù)據(jù)聚合。

葛昂，男，北京大學(xué)，MBA，高級工程師；主要研究方向和關(guān)注領(lǐng)域：數(shù)據(jù)挖掘、企業(yè)架構(gòu)。

鄭家民，男，北京航空航天大學(xué)，軟件工程，高級工程師；主要研究方向和關(guān)注領(lǐng)域：數(shù)據(jù)挖掘、企業(yè)架構(gòu)。endprint

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

當(dāng)取z=0，即數(shù)據(jù)均勻分布，分區(qū)算法采用Hadoop中的缺省分區(qū)函數(shù)時，最快的Reduce任務(wù)用時130s，最慢的用時131s；當(dāng)采用自定義分區(qū)函數(shù)時，最快的用時132s，最慢的用時132.5s。

當(dāng)取z=0.6，即數(shù)據(jù)出現(xiàn)較高程度的傾斜，分區(qū)算法采用Hadoop中缺省分區(qū)函數(shù)時，最快的Reduce任務(wù)用時90s，最慢的用時331s；當(dāng)采用自定義分區(qū)算法時，最快133s，最慢的用時138s。

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

顯然，自定義分區(qū)算法在輸入數(shù)據(jù)無重復(fù)的情況下，性能與默認(rèn)的分區(qū)函數(shù)相當(dāng)，然而當(dāng)輸入大量重復(fù)，發(fā)生傾斜時，自定義分區(qū)函數(shù)獲得的性能提升非常明顯。

當(dāng)屬性維度分別從3增加為6和8時，不管采用何種分區(qū)算法，計算時間呈現(xiàn)指數(shù)級增長的趨勢，這主要和每個輸入記錄產(chǎn)生2n個中間記錄有關(guān)。

5 結(jié)束語

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

本文從優(yōu)化數(shù)據(jù)分區(qū)著手，采用抽樣方式對分區(qū)算法進(jìn)行了一定優(yōu)化，當(dāng)目標(biāo)問題為分布式或者代數(shù)式的集合函數(shù)時，能夠在一定程度上解決因為數(shù)據(jù)傾斜而導(dǎo)致的數(shù)據(jù)立方體的計算性能問題。

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

參考文獻(xiàn)

[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(xiàn). 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-），男，中國社會科學(xué)院研究生院，MBA，工程師；主要研究方向和關(guān)注領(lǐng)域：多維數(shù)據(jù)聚合。

葛昂，男，北京大學(xué)，MBA，高級工程師；主要研究方向和關(guān)注領(lǐng)域：數(shù)據(jù)挖掘、企業(yè)架構(gòu)。

鄭家民，男，北京航空航天大學(xué)，軟件工程，高級工程師；主要研究方向和關(guān)注領(lǐng)域：數(shù)據(jù)挖掘、企業(yè)架構(gòu)。endprint

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

當(dāng)取z=0，即數(shù)據(jù)均勻分布，分區(qū)算法采用Hadoop中的缺省分區(qū)函數(shù)時，最快的Reduce任務(wù)用時130s，最慢的用時131s；當(dāng)采用自定義分區(qū)函數(shù)時，最快的用時132s，最慢的用時132.5s。

當(dāng)取z=0.6，即數(shù)據(jù)出現(xiàn)較高程度的傾斜，分區(qū)算法采用Hadoop中缺省分區(qū)函數(shù)時，最快的Reduce任務(wù)用時90s，最慢的用時331s；當(dāng)采用自定義分區(qū)算法時，最快133s，最慢的用時138s。

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

顯然，自定義分區(qū)算法在輸入數(shù)據(jù)無重復(fù)的情況下，性能與默認(rèn)的分區(qū)函數(shù)相當(dāng)，然而當(dāng)輸入大量重復(fù)，發(fā)生傾斜時，自定義分區(qū)函數(shù)獲得的性能提升非常明顯。

當(dāng)屬性維度分別從3增加為6和8時，不管采用何種分區(qū)算法，計算時間呈現(xiàn)指數(shù)級增長的趨勢，這主要和每個輸入記錄產(chǎn)生2n個中間記錄有關(guān)。

5 結(jié)束語

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

本文從優(yōu)化數(shù)據(jù)分區(qū)著手，采用抽樣方式對分區(qū)算法進(jìn)行了一定優(yōu)化，當(dāng)目標(biāo)問題為分布式或者代數(shù)式的集合函數(shù)時，能夠在一定程度上解決因為數(shù)據(jù)傾斜而導(dǎo)致的數(shù)據(jù)立方體的計算性能問題。

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

參考文獻(xiàn)

[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(xiàn). 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-），男，中國社會科學(xué)院研究生院，MBA，工程師；主要研究方向和關(guān)注領(lǐng)域：多維數(shù)據(jù)聚合。

葛昂，男，北京大學(xué)，MBA，高級工程師；主要研究方向和關(guān)注領(lǐng)域：數(shù)據(jù)挖掘、企業(yè)架構(gòu)。

鄭家民，男，北京航空航天大學(xué)，軟件工程，高級工程師；主要研究方向和關(guān)注領(lǐng)域：數(shù)據(jù)挖掘、企業(yè)架構(gòu)。endprint