劉　越　李錦濤　虎嵩林

1(中國(guó)科學(xué)院計(jì)算技術(shù)研究所　北京　100190)2(中國(guó)科學(xué)院大學(xué)　北京　100049)3(中國(guó)科學(xué)院信息工程研究所　北京　100093)(liuyue01@ict.ac.cn)

基于代價(jià)估計(jì)的Hive多維索引分割策略選擇算法

劉越1,2李錦濤1虎嵩林3

1(中國(guó)科學(xué)院計(jì)算技術(shù)研究所北京100190)2(中國(guó)科學(xué)院大學(xué)北京100049)3(中國(guó)科學(xué)院信息工程研究所北京100093)(liuyue01@ict.ac.cn)

摘要在能源互聯(lián)網(wǎng)、智慧城市等新興領(lǐng)域，智能終端采集的龐大數(shù)據(jù)往往需要多維分析，傳統(tǒng)企業(yè)尋求借助互聯(lián)網(wǎng)技術(shù)(如Hadoop和Hive)應(yīng)對(duì)大數(shù)據(jù)問(wèn)題.但是Hive當(dāng)前的多維索引能力較弱，無(wú)法滿足傳統(tǒng)企業(yè)的需求.針對(duì)這一問(wèn)題，提出了一種基于分布式網(wǎng)格文件的多維索引技術(shù)——DGFIndex，來(lái)提升Hive的多維查詢處理能力.但是在創(chuàng)建DGFIndex時(shí)，需要用戶指定各個(gè)索引維度的分割粒度，而分割粒度的大小與查詢性能息息相關(guān).在用戶對(duì)數(shù)據(jù)與查詢特征不熟悉時(shí)，很難選擇較優(yōu)的分割策略.為了解決這一問(wèn)題，通過(guò)建立新的MapReduce代價(jià)模型，并使用兩階段模擬退火算法為DGFIndex搜索較優(yōu)的分割策略，從而提升查詢性能，減少查詢集合的總耗時(shí).實(shí)驗(yàn)結(jié)果表明:DGFIndex可以提升Hive多維查詢性能50%～114%，對(duì)于固定的查詢集合，與人工選定分割策略比較，基于代價(jià)估計(jì)的分割策略選擇算法可以為DGFIndex快速選定較優(yōu)的分割策略，并可以使整個(gè)查詢集合的處理時(shí)間比人工方法最多減少30%.

關(guān)鍵詞Hive；MapReduce；多維索引；代價(jià)模型；模擬退火

隨著能源互聯(lián)網(wǎng)、智慧城市等領(lǐng)域技術(shù)的發(fā)展，傳統(tǒng)企業(yè)，如電力、通信、金融、制造等行業(yè)，需要處理的數(shù)據(jù)呈現(xiàn)爆炸式增長(zhǎng)，以往依靠傳統(tǒng)商業(yè)關(guān)系型數(shù)據(jù)庫(kù)的解決方案遇到了瓶頸，其寫入吞吐、橫向擴(kuò)展性與大數(shù)據(jù)分析能力都無(wú)法滿足日益增長(zhǎng)的數(shù)據(jù)存儲(chǔ)與分析需求.因此，傳統(tǒng)企業(yè)都在尋找應(yīng)對(duì)大數(shù)據(jù)挑戰(zhàn)的替代方案.而互聯(lián)網(wǎng)領(lǐng)域已經(jīng)出現(xiàn)了大量的大數(shù)據(jù)處理系統(tǒng)，如Hadoop,Spark[1],Storm等，但是由于互聯(lián)網(wǎng)應(yīng)用與傳統(tǒng)企業(yè)應(yīng)用各具特點(diǎn)，因此在將互聯(lián)網(wǎng)技術(shù)應(yīng)用于傳統(tǒng)企業(yè)時(shí)會(huì)遇到諸多挑戰(zhàn)[2-4].例如，傳統(tǒng)企業(yè)往往需要對(duì)龐大的采集類數(shù)據(jù)進(jìn)行快速的在線分析與離線批量計(jì)算，在這些計(jì)算邏輯中包含大量的多維查詢[3]，但是現(xiàn)有互聯(lián)網(wǎng)領(lǐng)域的數(shù)據(jù)處理系統(tǒng)索引能力有限，無(wú)法滿足需求.

具備靈活可擴(kuò)展性、高可用性、良好容錯(cuò)性與低成本等優(yōu)點(diǎn)的Hadoop已成為海量數(shù)據(jù)存儲(chǔ)與分析的首選方案之一.而Hadoop之上的數(shù)據(jù)倉(cāng)庫(kù)工具Hive[5]為用戶提供了類SQL查詢語(yǔ)言HiveQL，這使傳統(tǒng)企業(yè)的數(shù)據(jù)分析人員可以平滑地過(guò)渡到基于Hadoop的數(shù)據(jù)平臺(tái)上.但是傳統(tǒng)企業(yè)的數(shù)據(jù)分析邏輯包含大量的多維查詢與統(tǒng)計(jì)值分析，而Hive只支持有限的索引技術(shù)，如Compact Index等，這些索引數(shù)據(jù)過(guò)濾粒度較大，會(huì)造成過(guò)多的冗余數(shù)據(jù)讀取，查詢性能較低.為此，我們提出了一種基于分布式網(wǎng)格文件的多維索引技術(shù)——DGFIndex(distributed grid file index)[3].DGFIndex使用網(wǎng)格文件將數(shù)據(jù)空間分為很多小單元，通過(guò)小單元坐標(biāo)與對(duì)應(yīng)數(shù)據(jù)片位置的映射關(guān)系達(dá)到細(xì)粒度索引的目的.

在創(chuàng)建DGFIndex時(shí)，用戶需要指定每個(gè)索引維度的最小值與分割區(qū)間，但是在不熟悉數(shù)據(jù)與查詢特征時(shí)，選擇較優(yōu)的分割策略比較困難.如果索引維度分區(qū)粒度過(guò)小，雖然索引可以更精確地定位查詢相關(guān)數(shù)據(jù)，即減少冗余數(shù)據(jù)讀取，但是數(shù)據(jù)讀取性能較低;如果索引維度分區(qū)粒度過(guò)大，雖然數(shù)據(jù)讀取性能較高[6]，但是會(huì)造成讀取過(guò)多的冗余數(shù)據(jù)，并且數(shù)據(jù)解析與數(shù)據(jù)過(guò)濾的CPU開銷也會(huì)增大.因此，自動(dòng)地為DGFIndex選擇較優(yōu)的分割策略對(duì)查詢性能的提升至關(guān)重要，但是不同查詢間的最優(yōu)分割策略會(huì)相互影響與制約.在傳統(tǒng)企業(yè)中，多數(shù)數(shù)據(jù)分析邏輯都以存儲(chǔ)過(guò)程形式存在，即查詢集合在一定時(shí)間內(nèi)是靜態(tài)的，所以本文要解決的問(wèn)題是：對(duì)于固定的查詢集合，如何為DGFIndex選擇最優(yōu)的分割策略，從而使查詢集合耗時(shí)最短.為了解決該問(wèn)題，本文首先建立了一種新的MapReduce代價(jià)模型來(lái)評(píng)估不同分割策略對(duì)查詢開銷的影響，然后基于該代價(jià)模型提出了一種基于模擬退火的兩階段搜索算法加速分割策略的搜索過(guò)程，最終為查詢集合選擇較優(yōu)的DGFIndex分割策略，減小查詢集合的總耗時(shí).本文的主要貢獻(xiàn)將是：

1) 根據(jù)采集類數(shù)據(jù)的特征與查詢特點(diǎn)，提出了一種面向Hive的分布式網(wǎng)格文件索引——DGFIndex.該索引可以減少查詢?nèi)哂鄶?shù)據(jù)讀取量，提升查詢性能.

2) 針對(duì)基于索引查詢的MapReduce處理過(guò)程的特征，提出了一種新的MapReduce代價(jià)模型，并基于此提出了一種基于模擬退火的兩階段分割策略搜索算法.

3) 在實(shí)驗(yàn)中，本文使用不同的查詢集合大小、數(shù)據(jù)集大小評(píng)測(cè)分割策略搜索算法的有效性，實(shí)驗(yàn)顯示該算法可以快速地找到較優(yōu)的分割策略，從而減少查詢集合的總耗時(shí).

1相關(guān)工作

Fig. 1　DGFIndex structure.圖1　DGFIndex結(jié)構(gòu)

在Hadoop索引研究領(lǐng)域，現(xiàn)有的研究工作主要分為2類:1)應(yīng)用于傳統(tǒng)數(shù)據(jù)分析的索引研究，如Jiang等人[7]提出了一種HDFS上的基于排序文件的一維區(qū)間索引，該索引為每個(gè)固定大小的頁(yè)建立一個(gè)索引項(xiàng)，索引表記錄該頁(yè)的最小值、最大值以及偏移量，而頁(yè)的大小由用戶指定.Dittrich等人[8]提出了Trojan Index和Trojan Join Index，前者為每個(gè)數(shù)據(jù)片保存最小值、最大值和記錄數(shù)，該數(shù)據(jù)片的大小由用戶指定，后者通過(guò)將欲連接的數(shù)據(jù)集按照連接維度共同分區(qū)存儲(chǔ)到一起來(lái)加速多表連接操作.Eltabakh等人[9]提出了Eagle-eyed elephant系統(tǒng)，該系統(tǒng)提供了多種索引機(jī)制來(lái)加速數(shù)據(jù)讀取，包括為每個(gè)數(shù)據(jù)片內(nèi)的數(shù)值和日期類型建立區(qū)間索引、為字符串類型建立倒排索引等，該數(shù)據(jù)片的大小為HDFS塊大小.Richter等人[10]提出了HAIL，該系統(tǒng)提供了一種靜態(tài)索引與一種自適應(yīng)索引，該索引為每個(gè)數(shù)據(jù)塊副本建立不同的索引結(jié)構(gòu)，在該研究工作中索引數(shù)據(jù)片的大小是固定的.2)應(yīng)用于空間數(shù)據(jù)處理的索引研究，如Aji等人[11]提出的Hadoop GIS，該系統(tǒng)提出了一種2層的索引結(jié)構(gòu)，全局索引保存維度值與對(duì)應(yīng)數(shù)據(jù)片的映射關(guān)系，在每個(gè)節(jié)點(diǎn)為每個(gè)數(shù)據(jù)片根據(jù)查詢類型按需建立局部索引.此外，Eldawy等人提出了Spatial Hadoop[12]，該系統(tǒng)也提供了一種2層索引結(jié)構(gòu)，首先使用Grid File,R-Tree或R+-Tree將數(shù)據(jù)劃分為大小相同的塊，然后為每個(gè)塊建立局部索引，全局索引保存在主節(jié)點(diǎn)的內(nèi)存中以加速索引的訪問(wèn).從上面的描述可以看出現(xiàn)有的Hadoop索引相關(guān)的研究工作，索引粒度或者由用戶指定或者設(shè)定為固定經(jīng)驗(yàn)值，并沒(méi)有考慮查詢集合的影響.

在Hadoop代價(jià)模型領(lǐng)域，Herodotou[13]為Hadoop的MapReduce任務(wù)執(zhí)行流程的各個(gè)階段提出了詳細(xì)的代價(jià)模型，該模型應(yīng)用于Hadoop最優(yōu)化參數(shù)選擇[14].Wang等人[4]提出了一種面向Hive的代價(jià)模型，用于多表連接最優(yōu)順序選擇.Lin等人[15]為MapReduce提出了一種向量形式的代價(jià)模型，并基于該代價(jià)模型估算任務(wù)耗時(shí).Wang等人[16]針對(duì)偏斜數(shù)據(jù)的GroupBy查詢和Join查詢提出了估價(jià)模型.Song等人[17]針對(duì)MapReduce中二元連接查詢提出了IO代價(jià)模型.但是以上工作沒(méi)有考慮基于索引的情況，即其Map階段的數(shù)據(jù)讀取直接使用本地順序讀取或網(wǎng)絡(luò)讀取性能指標(biāo)進(jìn)行代價(jià)估計(jì)，但是我們發(fā)現(xiàn)數(shù)據(jù)讀取性能不僅與數(shù)據(jù)片大小有關(guān)，還與讀取的查詢相關(guān)數(shù)據(jù)量有關(guān).此外，每個(gè)Mapper讀取的數(shù)據(jù)量不再等于HDFS塊大小，而是經(jīng)過(guò)索引定位后的數(shù)據(jù)量.并且，如果查詢處理需要多遍Map階段時(shí)，已有的工作往往使用一遍Map階段的耗時(shí)與遍數(shù)的乘積作為估計(jì)，但是如果存在索引的話，各個(gè)Mapper讀取的數(shù)據(jù)量是不同的，讀取數(shù)據(jù)量少的Mapper可以快速執(zhí)行完，后面未執(zhí)行的Mapper可以利用空閑出的資源馬上執(zhí)行.總之，現(xiàn)有MapReduce代價(jià)模型無(wú)法直接應(yīng)用于基于索引的MapReduce處理代價(jià)估計(jì)中.

2DGFIndex

2.1DGFIndex結(jié)構(gòu)

圖1展示了一個(gè)建立在索引維度x和y上的2維DGFIndex.DGFIndex使用網(wǎng)格文件將數(shù)據(jù)空間分為很多小單元，這些小單元稱為GFU(grid file unit).這樣，表中的記錄會(huì)按照索引維度的值落在對(duì)應(yīng)的GFU中，而所有落在同一個(gè)GFU中的記錄會(huì)被連續(xù)地存儲(chǔ)在數(shù)據(jù)文件中，稱為數(shù)據(jù)片.每個(gè)GFU在索引表中以KeyValue的形式存儲(chǔ)，GFUKey為GFU在數(shù)據(jù)空間中的左下角坐標(biāo)，GFUValue由2部分組成：header和location.header為用戶定義的預(yù)計(jì)算用戶自定義函數(shù)(user-defined function, UDF)，例如可以預(yù)計(jì)算每個(gè)GFU中數(shù)值列的sum，這樣可以極大地加速聚集值查詢;location記錄該GFU對(duì)應(yīng)數(shù)據(jù)片所在的文件名、開始偏移量和結(jié)束偏移量.例如，圖1中GFU對(duì)應(yīng)的GFUKey=10_17，如果在創(chuàng)建索引時(shí)預(yù)計(jì)算維度z的sum，則header為落在該GFU中所有記錄的sum(z)值，location為存儲(chǔ)所有落在該GFU中記錄的數(shù)據(jù)片的位置信息.在本例中，文件名為f，開始偏移為4，結(jié)束偏移為20.數(shù)據(jù)片的粒度由用戶在創(chuàng)建索引時(shí)給出的分割策略確定，分割策略包括每個(gè)索引維度的最小值和分割區(qū)間.如圖1，在創(chuàng)建該索引時(shí)，指定索引維度x的最小值為1，分割區(qū)間大小為3；而索引維度y的最小值為11，分割區(qū)間大小為2.此外，為了加快索引表的讀取，DGFIndex的索引表以KeyValue的形式保存在HBase中，這樣可以以基于鍵值的方式快速讀取索引信息.

DGFIndex可以良好地支持行式存儲(chǔ)與列式存儲(chǔ).例如，對(duì)于TextFile存儲(chǔ)格式，DGFIndex記錄每個(gè)數(shù)據(jù)片在文件中的開始偏移量和結(jié)束偏移量；對(duì)于RCFile存儲(chǔ)格式，每個(gè)數(shù)據(jù)片保存為其中的一個(gè)行組(row group)，DGFIndex只需記錄每個(gè)Row Group的開始偏移量.可以看出，在DGFIndex中數(shù)據(jù)片為最小讀取單位.

Fig. 2　An example of DGFIndex construction.圖2　DGFIndex創(chuàng)建過(guò)程例子

2.2DGFIndex創(chuàng)建索引過(guò)程

DGFIndex的創(chuàng)建過(guò)程為一個(gè)MapReduce任務(wù)，Map階段的計(jì)算邏輯如算法1所示，Reduce階段的計(jì)算邏輯如算法2所示.

算法1. 創(chuàng)建DGFIndex的Map函數(shù).

輸入：鍵為記錄在該數(shù)據(jù)塊中的偏移量，值為記錄record;

①idxDValues=getIdxDimValues(record);

②GFUKey=computeGFUKey(idxDValues);

③Emit(GFUKey,record).

在創(chuàng)建索引的Map階段，對(duì)于每條記錄，首先讀取其索引維度的值(行①);然后根據(jù)索引維度的值與分割策略計(jì)算其所屬的GFU，從而得到該條記錄的GFUKey(行②);最后將GFUKey與該記錄作為鍵值對(duì)發(fā)往Reduce函數(shù)(行③).

算法2. 創(chuàng)建DGFIndex的Reduce函數(shù).

輸入：鍵為GFUKey，值為具有相同GFUKey的record列表ListRecordrecordsList;

輸出：存儲(chǔ)在HBase中的索引表與重組之后的數(shù)據(jù)文件.

①startOffset=當(dāng)前輸出文件的偏移量;

②endOffset=-1;

③sliceSize=0;

④filename=當(dāng)前輸出文件的名字;

⑤header=null;

⑥ forrecordinrecordsListdo

⑦h(yuǎn)eader=precompute(record,header);

⑧sliceSize+=sizeof(record);

⑨ end for

⑩endOffset=startOffset+sliceSize;

在創(chuàng)建索引的Reduce階段，Reducer接收到具有相同GFUKey的記錄列表，即屬于同一個(gè)數(shù)據(jù)片的所有記錄，最終目的是將每個(gè)數(shù)據(jù)片按序輸出，并記錄GFUKey與數(shù)據(jù)片在文件中位置的對(duì)應(yīng)關(guān)系.同時(shí)，還需按照用戶指定的UDF預(yù)計(jì)算每個(gè)GFU中記錄對(duì)應(yīng)的值.具體地，1)初始化數(shù)據(jù)片開始偏移、結(jié)束偏移、數(shù)據(jù)片大小、輸出文件名與保存預(yù)計(jì)算值的header(行①～⑤);2)對(duì)于具有相同GFUKey的每條記錄(行⑥)，首先預(yù)計(jì)算其UDF值并累加到header中(行⑦)，然后將當(dāng)前記錄的大小累加到sliceSize中(行⑧～⑨)，待處理完整個(gè)記錄列表，計(jì)算其結(jié)束偏移量(行⑩);3)計(jì)算GFUValue，并將GFUKeyGFUValue對(duì)寫入HBase(行).至此，索引創(chuàng)建結(jié)束.

如圖2所示，假設(shè)現(xiàn)有一個(gè)數(shù)據(jù)文件，使用圖1中的分割策略創(chuàng)建DGFIndex，同時(shí)預(yù)計(jì)算sum(z)，可以看到，DGFIndex索引創(chuàng)建的過(guò)程實(shí)際為數(shù)據(jù)重組織的過(guò)程，目的為將位于同一GFU中的記錄存儲(chǔ)到一起.如9,14,0.8與8,13,0.2位于同一個(gè)GFU，經(jīng)過(guò)數(shù)據(jù)重組織后存儲(chǔ)到數(shù)據(jù)文件的連續(xù)位置.同時(shí)，創(chuàng)建了包含GFUKey與GFUValue的索引項(xiàng).

2.3基于DGFIndex的查詢處理過(guò)程

基于DGFIndex的數(shù)據(jù)查詢過(guò)程分為3步：1)索引表讀取;2)HDFS數(shù)據(jù)塊過(guò)濾;3)數(shù)據(jù)塊內(nèi)部的數(shù)據(jù)片過(guò)濾.下面分別詳細(xì)描述各步驟.

算法3. 索引表讀取.

輸入：SQL查詢qi；

輸出：查詢相關(guān)的數(shù)據(jù)片位置集合SLOCqi;

查詢子結(jié)果SubRes，如果查詢可以使用預(yù)計(jì)算的UDF時(shí)，在這一步可以通過(guò)讀取索引表得到部分查詢結(jié)果.

①idxPred=extract(qi);

②isUDFQuery=check(qi);

③ {innerKeySet,boundaryKeySet}=DGFIndex.search(idxPred);

④queryKeySet=boundaryKeySet;

⑤ ifisUDFQuerythen

⑥SubRes=KVStore.getHeader(innerKeySet);

⑦writeToTmpFile(SubRes);

⑧ else

⑨queryKeySet=queryKeySet∪InnerKeySet

⑩ end if

算法4. HDFS數(shù)據(jù)塊過(guò)濾.

輸入：輸入文件列表fileList、保存SLOCqi的臨時(shí)文件的路徑;

輸出：經(jīng)過(guò)索引過(guò)濾后的查詢qi相關(guān)的HDFS數(shù)據(jù)塊集合chosenBlocksqi.

①chosenBlocksqi=?;

②SLOCqi=readFromTmpFile();

③allBlocks=getSplits(fileList);

④ forblockinallBlocksdo

⑤ ifblock∩SLOCqi≠? then

⑥chosenBlocksqi=chosenBlocksqi∪block;

⑦ end if

⑧ end for

⑨ forblockinchosenBlocksqido

⑩slicesInBlock=getRelatedSlices

(SLOCqi);

步驟2. HDFS數(shù)據(jù)塊過(guò)濾的步驟如算法4所示，算法4發(fā)生在InputFormat.getSplits函數(shù)中.首先初始化過(guò)濾后選定的數(shù)據(jù)塊集合chosenBlocksqi為空(行①)，并讀取算法1輸出的臨時(shí)文件，得到查詢相關(guān)數(shù)據(jù)片的位置信息(行②).然后根據(jù)輸入文件列表得到所有需要處理的數(shù)據(jù)塊(行③)，對(duì)于每個(gè)數(shù)據(jù)塊，判斷其是否包含查詢相關(guān)的數(shù)據(jù)片，如果包含則放入chosenBlocksqi，否則拋棄(行④～⑧).隨后，為chosenBlocksqi中每個(gè)選中的數(shù)據(jù)塊建立一個(gè)KeyValue對(duì)，Key為該數(shù)據(jù)塊的ID，Value為該數(shù)據(jù)塊內(nèi)所有需要讀取的數(shù)據(jù)片的偏移量，所有的KeyValue對(duì)保存在HBase一張臨時(shí)表中(行⑨).最后，返回查詢相關(guān)的數(shù)據(jù)塊

步驟3. 數(shù)據(jù)塊內(nèi)部的數(shù)據(jù)片過(guò)濾發(fā)生在RecordReader.next函數(shù)中，該函數(shù)讀取步驟2中HBase中的臨時(shí)表，得到在該塊中所有需要讀取的數(shù)據(jù)片的偏移量，然后在讀取數(shù)據(jù)時(shí)跳過(guò)不需要讀取的數(shù)據(jù)片.如果某個(gè)數(shù)據(jù)片跨塊存儲(chǔ)，此時(shí)，假設(shè)其大部分存儲(chǔ)在塊A中，則讓處理塊A的Mapper處理該數(shù)據(jù)片，以最小化遠(yuǎn)程數(shù)據(jù)讀取.當(dāng)查詢?yōu)榫奂挡樵?，則待Hive得到邊界GFU結(jié)果后，需要與算法3中內(nèi)部GFU的子結(jié)果合并得到最終結(jié)果.

如圖3所示，假設(shè)有一個(gè)SQL查詢，形式如圖3所示.1)先根據(jù)查詢謂詞，定位DGFIndex中的邊界GFU與內(nèi)部GFU，因?yàn)樵摬樵優(yōu)榫奂挡樵?，?duì)于內(nèi)部區(qū)域直接查詢HBase中header得到子結(jié)果，保存于臨時(shí)文件中.對(duì)于邊界區(qū)域，得到相關(guān)數(shù)據(jù)片在文件中的位置信息.2)根據(jù)數(shù)據(jù)片在文件中的位置信息過(guò)濾與查詢無(wú)關(guān)的數(shù)據(jù)塊，然后為每個(gè)候選數(shù)據(jù)塊保存需要讀取的數(shù)據(jù)片的偏移.3)在Mapper處理每個(gè)數(shù)據(jù)塊時(shí)，跳過(guò)查詢無(wú)關(guān)的數(shù)據(jù)片.最終得到的子結(jié)果與第1步中的子結(jié)果合并，得到最終結(jié)果.

SELECTsum(z)

FROMtable

WHEREx>5 ANDx<12 ANDy≥12 ANDy<16

Fig. 3　An example of DGFIndex-based query.圖3　DGFIndex索引查詢例子

2.4DGFIndex分割策略選擇問(wèn)題

由2.2～2.3節(jié)可以看出，分割策略的選擇與查詢性能息息相關(guān)：如果選擇細(xì)粒度的分割策略，查詢邊界區(qū)域會(huì)較小，即讀取的冗余數(shù)據(jù)量較小，而且解析數(shù)據(jù)、過(guò)濾數(shù)據(jù)的CPU開銷也較小.但是文獻(xiàn)[6]指出，數(shù)據(jù)讀取性能與數(shù)據(jù)片的大小成正比，即此情況下數(shù)據(jù)讀取性能較低；相反，如果選擇粗粒度的分割策略，雖然此時(shí)的數(shù)據(jù)讀取性能較高， 但是由于查詢邊界區(qū)域會(huì)較大，造成讀取過(guò)多冗余數(shù)據(jù)，而且，這也會(huì)造成解析數(shù)據(jù)、過(guò)濾數(shù)據(jù)的CPU開銷較大.圖4展示了不同數(shù)據(jù)片大小對(duì)查詢性能的影響(該實(shí)驗(yàn)的數(shù)據(jù)集使用存儲(chǔ)格式為RCFile的TPC-H lineitem表，大小為187 GB;查詢使用TPC-H中的Q6，實(shí)驗(yàn)環(huán)境與第4節(jié)中的描述一致，HDFS數(shù)據(jù)塊大小設(shè)置為256 MB).可以看出，對(duì)該查詢而言，32 MB為較優(yōu)的數(shù)據(jù)片大小，過(guò)小或過(guò)大的數(shù)據(jù)片都無(wú)法得到最優(yōu)的查詢性能.但是，由于不同的查詢具有不同的查詢謂詞，即不同查詢的最優(yōu)數(shù)據(jù)片大小可能不同，這就造成查詢間最優(yōu)分割策略相互影響與制約.因此，如何為DGFIndex選擇最優(yōu)的索引分割策略以最大化地提升查詢集合性能成為一項(xiàng)重要且具有挑戰(zhàn)性的任務(wù).

Fig. 4　Influence of different slice size on query performance.圖4　不同數(shù)據(jù)片大小對(duì)查詢性能造成的影響

3基于代價(jià)估計(jì)的分割策略選擇算法

3.1問(wèn)題描述

為了方便描述問(wèn)題定義與代價(jià)模型，首先預(yù)定義一些形式化符號(hào)，如表1所示.avgFieldSizek和avgRecordSize的值可以通過(guò)運(yùn)行涉及某個(gè)列的查詢，然后根據(jù)MapReduce Counter的值得到.

(1)

q∈Q:{q1,q2,…,qn},

(2)

(3)

(4)

(5)

3.2代價(jià)模型

由問(wèn)題描述可知，解決DGFIndex分割策略選擇問(wèn)題的關(guān)鍵為建立合理的代價(jià)模型以反映不同分割策略對(duì)查詢的影響.MapReduce代價(jià)模型已經(jīng)被眾多學(xué)者廣泛研究[4,13-17]，但是現(xiàn)有工作中的代價(jià)模型無(wú)法直接應(yīng)用于本工作，原因如下：

1) 以往的代價(jià)模型在建模Map階段數(shù)據(jù)讀取代價(jià)時(shí)，直接使用HDFS塊大小與固定數(shù)據(jù)讀取吞吐的商，沒(méi)有考慮不同數(shù)據(jù)片大小對(duì)讀取性能的影響與索引對(duì)數(shù)據(jù)的過(guò)濾作用.

2) 當(dāng)查詢使用的Mapper數(shù)大于集群容量時(shí)，以往的代價(jià)模型直接使用Map階段運(yùn)行的遍數(shù)與單遍代價(jià)的乘積作為Map階段的代價(jià)估計(jì).而在基于索引的查詢處理時(shí)，由于每個(gè)Mapper讀取數(shù)據(jù)量各不相同，數(shù)據(jù)量較小的Mapper可以快速執(zhí)行完，第2遍的Mapper可以馬上使用空閑的Mapper資源進(jìn)行執(zhí)行，以往的代價(jià)模型無(wú)法準(zhǔn)確描述該特性.

因此需要建立新的基于索引進(jìn)行數(shù)據(jù)處理的MapReduce代價(jià)模型.圖5展示了Hive中操作符在Map階段的數(shù)據(jù)處理流程及各操作符的作用.不同分割策略只會(huì)影響RecordReader與FilterOperator的性能：對(duì)于RecordReader，分割粒度越大其讀取的數(shù)據(jù)量越大；對(duì)于FilterOperator，分割粒度越大其數(shù)據(jù)解析與數(shù)據(jù)過(guò)濾的CPU開銷越大.而FilterOperator后輸出的為符合查詢謂詞條件的記錄，不同的分割策略并不會(huì)影響該值.所以，只需要構(gòu)建Map階段數(shù)據(jù)讀取與數(shù)據(jù)處理的代價(jià)模型，即可反映不同分割策略對(duì)查詢集合性能的影響.

Fig. 5　Data process in Map phase.圖5　Map階段數(shù)據(jù)處理流程

查詢qi在分割策略SPj下，使用DGFIndex處理的代價(jià)估計(jì)建模為式(7),MapRead(SPj,qi)表示Map階段數(shù)據(jù)讀取的代價(jià)，MapCPU(SPj,qi)表示Map階段數(shù)據(jù)解析與數(shù)據(jù)過(guò)濾的CPU代價(jià).

CostModel(SPj,qi)=

(7)

Map階段數(shù)據(jù)讀取的代價(jià)估計(jì)如式(8)所示，為查詢相關(guān)的數(shù)據(jù)總量與數(shù)據(jù)讀取吞吐的商，查詢相關(guān)數(shù)據(jù)總量定義為式(9)，數(shù)據(jù)片大小定義為式(10).對(duì)每個(gè)查詢而言，不同的分割策略SPj導(dǎo)致了不同的查詢相關(guān)的GFUKey集合與不同的數(shù)據(jù)片大小，從而導(dǎo)致不同的查詢相關(guān)數(shù)據(jù)量.由于基于索引進(jìn)行查詢處理時(shí)，每個(gè)Mapper處理的數(shù)據(jù)量不同，因此處理數(shù)據(jù)量少的Mapper可以快速完成，這樣未啟動(dòng)的Mapper可以繼續(xù)使用空閑出來(lái)的資源進(jìn)行處理.并且，由于每次Mapper處理的次序與調(diào)度算法和集群中各節(jié)點(diǎn)的負(fù)載相關(guān)，因此很難事先得到Mapper處理的次序.所以，這里使用讀取查詢相關(guān)全部數(shù)據(jù)的總耗時(shí)進(jìn)行估計(jì)，這一點(diǎn)與以往的MapReduce代價(jià)模型不同.對(duì)于列式存儲(chǔ)，如RCFile,只需要讀取查詢相關(guān)的列，所以讀取的數(shù)據(jù)總量與查詢相關(guān)列的總大小成正比.

MapRead(SPj,qi)=

(8)

(9)

(10)

式(8)中數(shù)據(jù)讀取吞吐的建模過(guò)程如下：由圖6，7可以看出(該實(shí)驗(yàn)使用與圖4中實(shí)驗(yàn)相同的數(shù)據(jù)集、集群環(huán)境與參數(shù)設(shè)置)，數(shù)據(jù)讀取吞吐與數(shù)據(jù)片大小成正比，與查詢相關(guān)數(shù)據(jù)量成反比.原因?yàn)楫?dāng)數(shù)據(jù)片增大時(shí)，隨機(jī)讀操作減少，數(shù)據(jù)的順序讀取性能提升；當(dāng)查詢相關(guān)數(shù)據(jù)量增大時(shí)，單節(jié)點(diǎn)啟動(dòng)的多個(gè)Mapper對(duì)磁盤IO產(chǎn)生競(jìng)爭(zhēng)，造成讀取吞吐降低，這種情況尤其會(huì)出現(xiàn)在磁盤讀取為瓶頸時(shí)，例如同一臺(tái)物理機(jī)上的多虛擬機(jī)實(shí)例.

Fig. 6　Influence of query selectivity and slice size on data reading performance.圖6　數(shù)據(jù)讀取吞吐與查詢選擇度和數(shù)據(jù)片大小的關(guān)系

Fig. 7　Query related data size.圖7　各查詢相關(guān)數(shù)據(jù)量

本文使用Profiling技術(shù)與多項(xiàng)式擬合方法建立數(shù)據(jù)讀取吞吐與數(shù)據(jù)片大小和查詢相關(guān)數(shù)據(jù)量之間的函數(shù)關(guān)系.具體地，首先隨機(jī)生成不同查詢選擇度的查詢集合，然后通過(guò)指定不同的分割策略為數(shù)據(jù)表建立不同數(shù)據(jù)片大小的DGFIndex，通過(guò)運(yùn)行查詢集合得到讀取數(shù)據(jù)量大小與讀取耗時(shí)(通過(guò)在RecordReader中添加Counter得到)，從而得到對(duì)應(yīng)的數(shù)據(jù)讀取吞吐量，最后進(jìn)行多項(xiàng)式函數(shù)擬合.

此外，本文在建模數(shù)據(jù)讀取吞吐時(shí)，如果有數(shù)據(jù)片為跨塊讀取，并沒(méi)有考慮網(wǎng)絡(luò)遠(yuǎn)程讀取，原因有2點(diǎn)：1)因?yàn)槭褂昧舜鎯?chǔ)大部分?jǐn)?shù)據(jù)片的Mapper處理該數(shù)據(jù)片的優(yōu)化技術(shù)，遠(yuǎn)程讀取數(shù)據(jù)量較小，通過(guò)實(shí)驗(yàn)發(fā)現(xiàn)在使用8～128 MB數(shù)據(jù)片大小時(shí)，遠(yuǎn)程讀取數(shù)據(jù)量約占總讀取數(shù)據(jù)量的0～6%，因此對(duì)代價(jià)估計(jì)的影響有限.2)因?yàn)閷?duì)于列式存儲(chǔ)格式而言，如RCFile，數(shù)據(jù)片為其中的一個(gè)Row Group，而Row Group為最小讀取單元，所以較難統(tǒng)計(jì)讀取部分Row Group的時(shí)間.

Map階段的數(shù)據(jù)解析與數(shù)據(jù)過(guò)濾的CPU代價(jià)估計(jì)如式(11)所示，即讀取的記錄數(shù)與每條記錄消耗的CPU代價(jià)的乘積.經(jīng)過(guò)實(shí)驗(yàn)發(fā)現(xiàn)，每條記錄消耗的CPU代價(jià)為常量，不受其他變量的影響，在本文使用的實(shí)驗(yàn)環(huán)境中，該常量值約為3167 nsrecord.

MapCPU(SPj,qi)=

(11)

由3.2節(jié)的代價(jià)模型可以看出，首先，分割策略在2方面決定了Hive處理查詢時(shí)讀取的數(shù)據(jù)量：1)查詢相關(guān)的數(shù)據(jù)片的數(shù)量，即給定索引維度的分割區(qū)間大小與查詢謂詞，就可以得到該查詢相關(guān)的數(shù)據(jù)片數(shù)量；2)數(shù)據(jù)片大小，一旦各索引維度分割區(qū)間確定，就確定了數(shù)據(jù)片大小.其次，分割策略決定了數(shù)據(jù)讀取吞吐，給定數(shù)據(jù)片大小與查詢相關(guān)數(shù)據(jù)量，就可以根據(jù)擬合的函數(shù)得到數(shù)據(jù)讀取吞吐.最后，分割策略還決定了Map階段數(shù)據(jù)解析與過(guò)濾的CPU開銷，因?yàn)槠浯_定了讀取數(shù)據(jù)量，也就確定了記錄數(shù).

由此可知，一旦給定分割策略SPj，就可以對(duì)查詢集合Q中的每個(gè)qi進(jìn)行代價(jià)估計(jì)，從而衡量分割策略的優(yōu)劣.但是，由于候選分割策略的搜索空間大小正比于多個(gè)維度可選方案的乘積，并且對(duì)于每種分割策略，都要計(jì)算整個(gè)查詢集合的代價(jià)估計(jì)，因此遍歷搜索最優(yōu)的分割策略將會(huì)花費(fèi)較長(zhǎng)的時(shí)間.為了加快搜索過(guò)程，本文提出了一種基于模擬退火的兩階段搜索算法來(lái)尋找較優(yōu)的分割策略.

3.3基于模擬退火的兩階段分割策略搜索算法

由于分割策略選擇過(guò)程為多個(gè)索引維度分割區(qū)間選擇組合問(wèn)題，為了避免搜索陷入局部最優(yōu)解，本文選擇模擬退火算法進(jìn)行搜索.基于模擬退火的分割策略搜索算法分為2個(gè)階段：粗粒度近似搜索與細(xì)粒度精確搜索.第1階段找到近似最優(yōu)解，第2階段減小搜索步長(zhǎng)，在近似最優(yōu)解周圍搜索精確“最優(yōu)解”.這里的最優(yōu)解并非實(shí)際的最優(yōu)分割策略，因?yàn)檫@取決于代價(jià)模型的準(zhǔn)確性，而代價(jià)模型本身為估算值.

算法過(guò)程如算法5所示:

算法5. 基于模擬退火的兩階段搜索算法.

輸入：查詢集合Q;

輸出：較優(yōu)的分割策略.

①minIntrls=currentItrls=getInitial-

Interval();

②minCost=currentCost=getCost

(currentIntrls);

③ whiletemp>1 do

④newIntrls=getNeighbor(currentIntrls,temp);

⑤newCost=getCost(newIntrls);

⑥ ifnewCost

⑦acceptRatio=1;

⑧ else

⑩ end if

算法6. 得到當(dāng)前分割策略的鄰居算法.

輸入：當(dāng)前的分割策略currentIntrls、當(dāng)前的溫度temp;

輸出：當(dāng)前分割策略的鄰居.

①newIntrls=clone(currentIntrls)

② iftemp>10 then

③ratio=1;

④ else

⑤ratio=0.1;

⑥ end if

⑦ forkthintrlinnewIntrls(kfrom 1 to

idxNum) do

⑧random=random();

⑨ ifrandom>0.5 then

從算法6過(guò)程可以看出，迭代次數(shù)由初始溫度temp與冷卻速率coolingRate決定：temp越小，coolingRate越大，迭代次數(shù)越少，收斂速度越快，但是可能得不到最優(yōu)解;反之，則可能增加算法搜索時(shí)間.在下面的實(shí)驗(yàn)中，設(shè)置temp=200，coolingRate=0.01.

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

4.1實(shí)驗(yàn)環(huán)境與測(cè)試集

1) 硬件環(huán)境.本次實(shí)驗(yàn)使用由32個(gè)虛擬機(jī)節(jié)點(diǎn)組成的集群環(huán)境，每個(gè)虛擬機(jī)節(jié)點(diǎn)具有12核CPU、26 GB內(nèi)存、600 GB磁盤.其中一個(gè)節(jié)點(diǎn)作為MapReduce計(jì)算框架的主節(jié)點(diǎn)JobTracker，一個(gè)節(jié)點(diǎn)作為HDFS的主節(jié)點(diǎn)NameNode，一個(gè)節(jié)點(diǎn)作為HBase的主節(jié)點(diǎn)HMaster.其他節(jié)點(diǎn)作為從節(jié)點(diǎn)，運(yùn)行DataNode,TaskTracker.Hive與NameNode運(yùn)行在同一節(jié)點(diǎn).

2) 軟件環(huán)境.每個(gè)節(jié)點(diǎn)使用CentOS 7.0,JDK 1.7.0_65 64bit.使用Hadoop-1.2.1,HBase-0.94.23(用于存儲(chǔ)DGFIndex的索引表).DGFIndex實(shí)現(xiàn)在Hive-0.14.0中.HDFS塊大小設(shè)置為256 MB，Hadoop,Hive與HBase的其他配置參數(shù)都使用默認(rèn)值.

3) 測(cè)試集.本實(shí)驗(yàn)使用TPC-H測(cè)試集中的lineitem表與Q6，使用被廣泛使用的RCFile與ORC作為文件存儲(chǔ)格式，不同數(shù)據(jù)集大小如表2所示.本實(shí)驗(yàn)為lineitem表在l_discount,l_quantity和l_shipdate上建立三維索引，各維度的基數(shù)如表3所示.查詢集合由隨機(jī)生成的Q6構(gòu)成，集合中的查詢具有不用的選擇度，本實(shí)驗(yàn)使用2個(gè)查詢集合：30個(gè)隨機(jī)查詢構(gòu)成的集合QSet30與50個(gè)隨機(jī)查詢構(gòu)成的集合QSet50.選擇該測(cè)試集的原因有3點(diǎn)：1)TPC-H被廣泛地用于數(shù)據(jù)倉(cāng)庫(kù)類系統(tǒng)的評(píng)測(cè)工作，因此使用該測(cè)試集的結(jié)果具有可比性；2)由于在Hive中，索引只作用于過(guò)濾單表讀取時(shí)查詢無(wú)關(guān)的數(shù)據(jù)，所以選擇單表數(shù)據(jù)集足以評(píng)測(cè)索引的數(shù)據(jù)過(guò)濾性能，并且lineitem表是該測(cè)試集中最大的表；3)Q6是TPC-H中典型的多維查詢，可以充分測(cè)試DGFIndex的多維數(shù)據(jù)索引能力.此外，在本實(shí)驗(yàn)中，在運(yùn)行每個(gè)查詢前都會(huì)清空操作系統(tǒng)的緩存并重啟Hadoop，以保證索引定位的數(shù)據(jù)從磁盤讀取，從而避免緩存對(duì)結(jié)果造成的影響.并且，查詢集合中每個(gè)查詢都會(huì)運(yùn)行3次，在結(jié)果中使用3次結(jié)果的平均值，以減弱集群不穩(wěn)定對(duì)結(jié)果造成的影響.

Table 2　Data Size

Table 3　Cardinality of Index Dimensions

Fig. 8　Query cost time of Data-Medium.圖8　Data-Medium上的查詢耗時(shí)

4.2DGFIndex的性能

本實(shí)驗(yàn)中，在RCFile上創(chuàng)建Hive原生索引Compact Index與DGFIndex，此外，本實(shí)驗(yàn)還與ORC[6]中的索引進(jìn)行對(duì)比.ORC是Hive目前最新的列式存儲(chǔ)格式，內(nèi)嵌了索引功能.Compact Index與ORC中索引的數(shù)據(jù)過(guò)濾效果與索引維度數(shù)值在文件中的分布有關(guān)，對(duì)于均勻數(shù)據(jù)集TPC-H來(lái)說(shuō)，兩者的性能較差.為了提升兩者的索引性能，事先使用并行Order By對(duì)兩者的數(shù)據(jù)表在索引維度上進(jìn)行全排序預(yù)處理.圖8,9展示了在不同數(shù)據(jù)集大小與不同查詢選擇度下的各種索引的查詢性能.

Fig. 9　Query cost time of Data-Large.圖9　Data-Large上的查詢耗時(shí)

從實(shí)驗(yàn)結(jié)果可以看出，相對(duì)不使用任何索引的RCFile，Compact Index可以提升2～7倍查詢性能，DGFIndex可以提升4.7～15倍查詢性能,并且，DGFIndex比Compact Index的查詢性能提升了50%～114%.原因有2點(diǎn)：1)Compact Index只能在HDFS數(shù)據(jù)塊級(jí)別過(guò)濾查詢無(wú)關(guān)數(shù)據(jù)，這會(huì)造成讀取過(guò)多的冗余數(shù)據(jù)；而DGFIndex可以在細(xì)粒度的數(shù)據(jù)片級(jí)別過(guò)濾查詢無(wú)關(guān)的數(shù)據(jù)，從而大幅降低冗余數(shù)據(jù)的讀取，提升查詢性能.2)Compact Index讀取索引的方式為啟用額外的MapReduce任務(wù)全表掃描的方式，索引讀取效率較低；而DGFIndex使用基于鍵值的方式，只需讀取查詢相關(guān)的鍵，讀取效率較高.此外，相比于不使用索引的ORC，其內(nèi)的索引提升1.6～2.6倍查詢性能.DGFIndex比ORC中的索引查詢性能提升了8%～28%，而對(duì)于點(diǎn)查詢來(lái)說(shuō)，分別提升了1.2倍和2.2倍.可以看出，DGFIndex在低選擇度時(shí)的優(yōu)勢(shì)更明顯，原因?yàn)椋航?jīng)過(guò)索引定位后，DGFIndex使用了比ORC更少的Mapper.

4.3分割策略選擇算法的有效性

Fig. 10　Cost time of QSet30.圖10　QSet30在不同數(shù)據(jù)片大小下的查詢耗時(shí)

本實(shí)驗(yàn)使用RCFile作為底層存儲(chǔ)格式.圖10,11展示了不同數(shù)據(jù)量下基于代價(jià)估計(jì)的分割策略選擇算法得到的分割策略的查詢集合耗時(shí)與人工指定不同數(shù)據(jù)片大小的分割策略的查詢集合耗時(shí)對(duì)比結(jié)果，其中后綴為opt的為本文提出算法選擇的分割策略對(duì)應(yīng)的數(shù)據(jù)片大小.Data-Small下人工指定的分割策略(對(duì)應(yīng)索引維度l_quantity,l_discount,l_shipdate)分別為[2,0.01,60]，[4,0.01,60]，[4,0.01,120]，[4,0.02,115]與[8,0.02,115].Data-Medium下人工指定的分割策略分別為[2,0.01,29]，[2,0.01,58]，[4,0.01,59]，[8,0.01,58]與[12,0.01,73].Data-Large下人工指定的分割策略為[1,0.01,24]，[2,0.01,24]，[2,0.01,47]，[4,0.01,52]與[4,0.01,97].由本文算法得到的較優(yōu)分割策略如表4所示.

Fig. 11　Cost time of QSet50.圖11　QSet50在不同數(shù)據(jù)片大小下的查詢耗時(shí)

DataSetData-SmallData-MediumData-LargeQSet30[6,0.01,115][5,0.01,78][2,0,01,78]QSet50[9,0.01,83][9,0.01,49][3,0.01,49]

由結(jié)果可以看出，人工指定分割策略方法在選擇不同分割策略時(shí)性能各有差異，并且索引粒度太大或太小都無(wú)法得到較優(yōu)的性能，因此在用戶不熟悉數(shù)據(jù)與查詢特征時(shí)較難選擇較優(yōu)的分割策略.相反，基于代價(jià)估計(jì)的分割策略選擇算法可以根據(jù)查詢集合自動(dòng)地得到較優(yōu)的分割策略，從結(jié)果可以看出與人工指定方法相比，最多可以減少查詢集合耗時(shí)30%.

4.4基于代價(jià)估計(jì)的分割策略選擇算法收斂速度

圖12展示了基于遍歷算法、模擬退火與人工選擇分割策略選擇算法的耗時(shí)，這里假設(shè)人工選擇的耗時(shí)為1 s.

Fig. 12　Cost time of splitting policy search algorithm.圖12　分割策略選擇算法耗時(shí)

從圖12可以看出,基于模擬退火的算法比遍歷算法快12～24倍，在短時(shí)間內(nèi)搜索到較優(yōu)的索引分割策略.此外，基于遍歷算法的分割策略選擇算法的耗時(shí)與多個(gè)索引維度基數(shù)的乘積成正比，因?yàn)槠湫枰闅v每一種可能的分割策略的可行性.而在本實(shí)驗(yàn)中，索引維度的基數(shù)都較小，如果應(yīng)用中遇到更大基數(shù)的索引維度，如浮點(diǎn)類型維度，則遍歷算法的耗時(shí)是不可接受的.如果根據(jù)數(shù)據(jù)與查詢特征人為選取分割策略，雖然可以快速選定，但是較難選擇較優(yōu)的分割策略.

5結(jié)束語(yǔ)

本文針對(duì)采集類數(shù)據(jù)與查詢特征，提出了一種面向Hive的多維索引技術(shù)—DGFIndex，該索引以細(xì)粒度過(guò)濾查詢無(wú)關(guān)的數(shù)據(jù)大幅減少冗余數(shù)據(jù)讀取，其查詢性能比Hive原生索引Compact Index提升50%～114%，比ORC中的索引提升8%～28%，并極大地提高了點(diǎn)查詢的性能.

但是在創(chuàng)建DGFIndex時(shí)，需要人為指定各索引維度分割區(qū)間大小，在對(duì)查詢與數(shù)據(jù)特征不熟悉情況下，用戶很難選擇最優(yōu)的索引分割策略.針對(duì)該問(wèn)題，本文首先提出了一種新的MapReduce代價(jià)模型，基于該模型提出了一種基于模擬退火的兩階段分割策略搜索算法，實(shí)驗(yàn)證明該算法可以在較短的時(shí)間內(nèi)得到較優(yōu)的分割策略.

本文提出的代價(jià)模型沒(méi)有考慮數(shù)據(jù)分布維度，在數(shù)據(jù)分布不均勻時(shí)，對(duì)DGFIndex而言，各數(shù)據(jù)片的大小會(huì)出現(xiàn)不同.在這種情況下，使用查詢相關(guān)GFUKey的數(shù)量估算查詢相關(guān)數(shù)據(jù)量會(huì)不精確，需要得到數(shù)據(jù)片在文件中的布局來(lái)估算該值.但是由于需要記錄更多的信息，因此代價(jià)估計(jì)計(jì)算的速度會(huì)減慢，分割策略的搜索速度也會(huì)大大減慢.在未來(lái)的工作中，我們將會(huì)在代價(jià)模型中引入數(shù)據(jù)分布維度，并優(yōu)化在該種情況下分割策略搜索的速度.

參考文獻(xiàn)

[1]Zaharia M, Chowdhury M, Franklin M, et al. Spark: Cluster computing with working sets[C] //Proc of the 2nd USENIX Workshop on Hot Topics in Cloud Computing (HotCloud 2010). Berkeley, CA: USENIX Association, 2010: 10

[2]Hu Songlin, Liu Wantao, Rabl T, et al. DualTable: A hybrid storage model for update optimization in Hive[C] //Proc of the 31st IEEE Int Conf on Data Engineering (ICDE 2015). Piscataway, NJ: IEEE, 2015: 1340-1351

[3]Liu Yue, Hu Songlin, Rabl T, et al. DGFIndex for smart grid: Enhancing Hive with a cost-effective multidimensional range index[C] //Proc of the 40th Int Conf on Very Large Data Bases (VLDB 2014). New York: ACM, 2014: 1496-1507

[4]Wang Yue, Xu Yingzhong, Liu Yue, et al. QMapper for smart grid: Migrating SQL-based application to Hive[C] //Proc of the ACM SIGMOD Int Conf on Management of Data (SIGMOD 2015). New York: ACM, 2015: 647-658

[5]Thusoo A, Sarma J S, Jain N, et al. Hive: A warehousing solution over a map-reduce framework[C] //Proc of the 35th Int Conf on Very Large Data Bases (VLDB 2009). New York: ACM, 2009: 1626-1629

[6]Huai Yin, Ma Siyuan, Lee Rubao, et al. Understanding insights into the basic structure and essential issues of table placement methods in clusters[C] //Proc of the 40th Int Conf on Very Large Data Bases (VLDB 2014). New York: ACM, 2014: 1750-1761

[7]Jiang Dawei, Ooi B C, Shi Lei, et al. The performance of MapReduce: An in-depth study[C] //Proc of the 36th Int Conf on Very Large Data Bases (VLDB 2010). New York: ACM, 2010: 472-483

[8]Dittrich J, Quiane-Ruiz J A, Jindal A, et al. Hadoop++: Making a yellow elephant run like a cheetah (without it even noticing)[C] //Proc of the 36th Int Conf on Very Large Data Bases (VLDB 2010). New York: ACM, 2010: 515-529

[9]Eltabakh M, Ozcan F, Sismanis Y, et al. Eagle-eyed elephant: Split-oriented indexing in Hadoop[C] //Proc of the 16th Int Conf on Extending Database Technology (EDBT/ICDT 2013). New York: ACM, 2013: 89-100

[10]Richter S, Quiane-Ruiz J A, Schuh S, et al. Towards zero-overhead static and adaptive indexing in Hadoop[J]. The VLDB Jounal, 2014, 23(3): 469-494

[11]Aji A, Wang Fusheng, Vo H, et al. Hadoop GIS: A high performance spatial data warehousing system over MapReduce[C] //Proc of the 39th Int Conf on Very Large

Data Bases (VLDB 2013). New York: ACM, 2013: 1009-1020

[12]Eldawy A, Mokbel M. A demonstration of spatial Hadoop: An efficient MapReduce framework for spatial data[C] //Proc of the 39th Int Conf on Very Large Data Bases (VLDB 2013). New York: ACM, 2013: 1230-1233

[13]Herodotou H. Hadoop performance models[R]. Pittsburgh, PA: arXiv preprint, 2011

[14]Herodotou H, Badu S. Profiling, what-if analysis, and cost-based optimization of MapReduce programs[C] //Proc of the 37th Int Conf on Very Large Data Bases (VLDB 2011). New York: ACM, 2011: 1111-1122

[15]Lin Xuelian, Meng Zide, Xu Chuan, et al. A practical performance model for Hadoop MapReduce[C] //Proc of 2012 IEEE Int Conf on Cluster Computing (Cluster 2012). Piscataway, NJ: IEEE, 2012: 231-239

[16]Wang Youwei, Wang Weiping, Meng Dan. Query optimization by statistical approach for Hive data warehouse[J]. Journal of Computer Research and Development, 2015, 52(6): 1452-1462 (in Chinese)(王有為, 王偉平, 孟丹. 基于統(tǒng)計(jì)方法的Hive數(shù)據(jù)倉(cāng)庫(kù)查詢優(yōu)化實(shí)現(xiàn)[J]. 計(jì)算機(jī)研究與發(fā)展, 2015, 52(6): 1452-1462)

[17]Song Jie, Li Tiantian, Zhu Zhiliang, et al. Research on I/O cost of MapReduce join[J]. Journal of Software, 2015, 26(6): 1438-1456 (in Chinese)(宋杰, 李甜甜, 朱志良, 等. MapReduce連接查詢的I/O代價(jià)研究[J]. 軟件學(xué)報(bào), 2015, 26(6): 1438-1456)

Liu Yue, born in 1988. PhD candidate. Student member of China Computer Federation. His research interests include distributed system and database system.

Li Jintao, born in 1962. Professor and PhD supervisor. His research interests include multimedia technology, virtual reality technology, and pervasive computing technology.

Hu Songlin, born in 1973. Professor and PhD supervisor. Senior member of China Computer Federation. His research interests include service computing, distributed system and middleware.

A Cost-Based Splitting Policy Search Algorithm for Hive Multi-Dimensional Index

Liu Yue1,2, Li Jintao1, and Hu Songlin3

1(InstituteofComputingTechnology,ChineseAcademyofSciences,Beijing100190)2(UniversityofChineseAcademyofSciences,Beijing100049)3(InstituteofInformationEngineering,ChineseAcademyofSciences,Beijing100093)

AbstractIn the domain of energy Internet, smart city, etc, the massive smart devices collect large amount of data every day, and traditional enterprises need to perform lots of multi-dimensional analysis on these data to support decision-making. Recently, these enterprises try to solve the big data problem with technologies from Internet companies, for example, Hadoop and Hive etc. However, Hive has limited multi-dimensional index ability, and cannot satisfy the requirements of high-performance analysis in traditional enterprises. In this paper, we propose a distributed grid file based multi-dimensional index—DGFIndex to improve the multi-dimensional query performance of Hive. However, DGFIndex needs user to specify the splitting policy when creating index, which is not trivial for user when they are not familiar with data and query pattern. To solve it, we propose a novel MapReduce cost model to measure the DGFIndex-based query performance on specific splitting policy, a two-phase simulated annealing algorithm to search for the suitable splitting policy for DGFIndex, and finally decrease the total cost time of query set. The experimental results show that, DGFIndex improves 50%～114% query performance than original Compact Index in Hive. For static query set, compared with manual-specifying partition policy, our algorithm can choose suitable interval size for each index dimension, and decrease the cost time of query set at most 30%.

Key wordsHive; MapReduce; multi-dimensional index; cost model; simulated annealing

收稿日期：2015-12-21；修回日期：2016-02-02

基金項(xiàng)目：國(guó)家自然科學(xué)基金項(xiàng)目(61070027)

通信作者：虎嵩林(husonglin@iie.ac.cn)

中圖法分類號(hào)TP311.132

This work was supported by the National Natural Science Foundation of China (61070027).