徐劍等

摘 要： Hadoop系統(tǒng)在處理多表鏈接問題時，每輪都會將大量的中間結(jié)果寫入本地磁盤，從而嚴(yán)重降低了系統(tǒng)的處理效率。為解決該問題，提出一種“替換?查詢”方法，該方法通過對鏈接表建立索引，將預(yù)輸出的元組集替換為索引信息輸出到中間結(jié)果，以索引的形式參與多表鏈接，以此減少中間結(jié)果的I/O代價。運(yùn)用緩沖池、二次排序和多線程技術(shù)對索引信息進(jìn)行優(yōu)化管理，加快索引查詢速度。最后在TPC?H數(shù)據(jù)集上，設(shè)計了與原Hadoop的對比實(shí)驗，結(jié)果表明該方法可減少35.5%的存儲空間，提高12.9%的運(yùn)行效率。

關(guān)鍵詞： 多表鏈接； 替換?查詢； 索引； 緩沖池； 二次排序

中圖分類號： TN911?34； TP311 文獻(xiàn)標(biāo)識碼： A 文章編號： 1004?373X（2014）06?0090?05

0 引 言

隨著互聯(lián)網(wǎng)應(yīng)用的快速發(fā)展，海量數(shù)據(jù)的存儲與處理成為研究人員面臨的嚴(yán)峻挑戰(zhàn)。近年來，谷歌提出的分布式文件系統(tǒng)GFS、并行編程框架Map?Reduce?；诖?，開源社區(qū)Apache的Hadoop項目實(shí)現(xiàn)了分布式文件系統(tǒng)HDFS和并行編程框架Hadoop Map?Reduce。Hadoop因其良好的可擴(kuò)展性、高可用性以及容錯性，廣泛地應(yīng)用在IBM，百度，360，阿里巴巴等互聯(lián)網(wǎng)公司的海量數(shù)據(jù)存儲與分析應(yīng)用中，是目前使用最為廣泛的云計算平臺之一。

針對分布式計算環(huán)境中多表鏈接運(yùn)算的問題，文獻(xiàn)[1?2]提出一種在單個Map?Reduce任務(wù)中同時鏈接多個關(guān)系表的優(yōu)化算法，文獻(xiàn)[3]提出一種基于預(yù)排序的多表鏈接算法。這些算法都存在中間結(jié)果快速增加的問題，一方面，為了防止鏈接屬性缺失現(xiàn)象的出現(xiàn)，本次鏈接要盡可能的將下一步或者下幾步鏈接相關(guān)的屬性信息輸出到中間結(jié)果；另一方面，每一步鏈接操作之后，中間結(jié)果的屬性列增加，伴隨著鏈接次數(shù)的增加，輸出到中間結(jié)果的屬性列越來越多；最后，子鏈接的中間結(jié)果要被多次復(fù)制，溢寫磁盤或者網(wǎng)絡(luò)傳輸?shù)狡渌?jié)點(diǎn)。這些因素使得中間結(jié)果快速膨脹，從而導(dǎo)致大量的內(nèi)存占用，過多的磁盤溢寫和不必要的網(wǎng)絡(luò)傳輸代價，嚴(yán)重降低了系統(tǒng)性能。

為了解決多表鏈接中間結(jié)果快速增加的問題，本文提出“替換?查詢”方法，該方法具體如下，在每一次子鏈接結(jié)果集輸出到中間結(jié)果之前，系統(tǒng)對結(jié)果集中的記錄元組建立非侵入式的Hadoop分布式文件索引（Non?invasive Index of Hadoop Distributed File System，NIHDFS），在保證結(jié)果集信息完整性的前提下，用索引替代記錄元組信息并輸出到中間結(jié)果，記錄元組以索引的形式參與以后的鏈接過程；當(dāng)需要記錄元組信息時，該方法能夠通過查詢操作快速的實(shí)現(xiàn)元組信息恢復(fù)。在索引的平均長度比記錄元組的平均長度短或者鏈接表的數(shù)量較多的情況下，該方法能夠有效地減少中間結(jié)果的數(shù)據(jù)規(guī)模并降低其增長速度。

在Hadoop?1.1.2上，修改系統(tǒng)源碼并實(shí)現(xiàn)“替換?查詢”多步鏈接的處理方法，本文將改造后的系統(tǒng)命名為Hadoop?1.1.2?NIHDFS。在與原系統(tǒng)的對比實(shí)驗中，“替換?查詢”的多表鏈接處理方法，能夠有效的提升Hadoop處理多表鏈接的性能。

1 Hadoop?1.1.2?NIHDFS系統(tǒng)整體設(shè)計

原Hadoop在處理多表鏈接問題時，Map階段對輸入的記錄元組進(jìn)行鍵?值解析，解析出真實(shí)的記錄元組之后便直接進(jìn)行Map端的鏈接操作。Hadoop?1.1.2?NIHDFS系統(tǒng)則不然，在執(zhí)行Map端鏈接操作之前，系統(tǒng)要對輸入的信息依照“替換?查詢”方法進(jìn)行處理。該處理包含3個部分，分別是對鏈接表建立NIHDFS索引，替換鏈接表元組信息以及元組信息的快速查詢。他們分別由索引化模塊，替換模塊和查詢模塊來完成，如圖1所示。

T3是原始鏈接表，當(dāng)該鏈接表進(jìn)入系統(tǒng)后，先后進(jìn)行索引化和替換操作，并用記錄元組的索引信息和本次鏈接的屬性信息替換原始記錄元組，然后再進(jìn)行Map端鏈接操作。Output_1是子鏈接的鏈接結(jié)果，IndexT1_1表示鏈接表T1中某個記錄元組的索引，IndexT1_1：IndexT2_1表示鏈接表T1和T2的一條鏈接結(jié)果，其中只存儲著2條記錄對應(yīng)的索引信息。當(dāng)Output_1作為該系統(tǒng)的輸入時，該系統(tǒng)需要對其中的索引信息進(jìn)行查詢，恢復(fù)出原始記錄元組并進(jìn)行解析，然后再進(jìn)行Map端的鏈接操作。Map端和Reduce端鏈接操作的操作內(nèi)容由具體的多表鏈接算法來決定。

2 NIHDFS索引

HDFS（Hadoop Distributed File System）是被設(shè)計成適合運(yùn)行在通用硬件上的分布式文件系統(tǒng)。本文以HDFS為基礎(chǔ)，建立非侵入式的Hadoop分布式文件系統(tǒng)索引，即NIHDFS。它是根據(jù)鏈接表各記錄元組在HDFS存儲的物理位置信息建立起來的預(yù)鏈接索引。

NIHDFS主要包含文件的統(tǒng)一資源定位符（File URL），數(shù)據(jù)塊間偏移量（Block Offset），塊內(nèi)記錄偏移量（Record Offset），以及記錄元組長度（Record Length）4個部分，結(jié)構(gòu)如圖2所示。統(tǒng)一資源定位符（File URL）是文件在HDFS中存儲的邏輯路徑，該路徑可以選擇系統(tǒng)默認(rèn)值，也可以由用戶定義。數(shù)據(jù)塊偏移量（Block Offset）是索引對應(yīng)記錄所在的數(shù)據(jù)塊在文件中的起始偏移量。針對特定數(shù)據(jù)塊中的不同記錄，它們的長度和存儲的物理位置各不相同，本文用塊內(nèi)記錄偏移量（Record Offset）來存儲記錄在數(shù)據(jù)塊中的位置信息。記錄元組長度（Record Length）指記錄元組的大小。

如在HDFS中存儲著一個維表，該表在HDFS中的邏輯路徑是URL；它被HDFS切分成3個數(shù)據(jù)塊，分別是Block_A，Block_B，Block_C，起始的偏移量分別是Offset_A，Offset_B，Offset_C；某條記錄存儲在Block_B中，塊內(nèi)偏移量是Offset_rc，該記錄所對應(yīng)索引是“URL+ Offset_B + Offset_rc + Record_tmp.Length”。

由于圖2所示的索引中只包含一個數(shù)據(jù)塊信息，當(dāng)維表中的記錄元組被切分到兩個數(shù)據(jù)塊上時，根據(jù)圖2建立的索引只能夠恢復(fù)記錄元組的部分信息，這顯然是不正確的。這種情況下，本文特別設(shè)計了如圖3所示的索引，該索引中包含有2個數(shù)據(jù)塊偏移量，塊內(nèi)記錄元組偏移量和記錄元組的長度信息，因此它能夠完整的存儲記錄的位置信息。由于記錄元組的后半部分?jǐn)?shù)據(jù)存儲在第2個數(shù)據(jù)塊的起始位置上，所以記錄在第2個數(shù)據(jù)塊的塊內(nèi)記錄偏移量的值是零。

3 基于NIHDFS的“替換?查詢”方法

“替換?查詢”的多表鏈接處理是通過索引化，替換和查詢3個模塊來實(shí)現(xiàn)的，如圖1所示。

3.1 索引化

在處理多表鏈接問題時，Map?Reduce任務(wù)的輸入有2種類型，一種是前面某個Map?Reduce任務(wù)產(chǎn)生的鏈接結(jié)果，一種是原始鏈接表。由于鏈接結(jié)果中存儲的是記錄元組的索引信息，所以無需進(jìn)行索引化操作。當(dāng)輸入是原始鏈接表時，要根據(jù)NIHDFS索引結(jié)構(gòu)對表中的記錄元組建立索引。當(dāng)被索引化的記錄元組被切分到2個數(shù)據(jù)塊時，建立圖3中所示的索引。

3.2 替換

根據(jù)索引化過程中對記錄元組建立的NIHDFS索引，用索引信息和本次鏈接的鏈接屬性組成的鍵?值對替換掉原始的記錄元組，并保證替換操作的正確性和索引信息的完整性。在之后的鏈接操作中，如其他經(jīng)典的多表鏈接算法一樣，鏈接屬性主導(dǎo)著整個鏈接過程，索引信息作為附屬信息或被輸出到中間結(jié)果，或被發(fā)送到其他的節(jié)點(diǎn)。

3.3 查詢

當(dāng)Map?Reduce任務(wù)的輸入是鏈接結(jié)果時，因為鏈接結(jié)果中存儲的是記錄元組的一系列索引信息，并不包含本次鏈接的鏈接屬性信息。此時要對NIHDFS索引執(zhí)行查詢操作，到達(dá)獲取鏈接屬性信息的目的，系統(tǒng)將啟動專門線程來完成該查詢操作。

查詢過程如圖4所示，TaskTracker是多表鏈接操作的任務(wù)執(zhí)行節(jié)點(diǎn)，該節(jié)點(diǎn)中運(yùn)行著多個Map或Reduce任務(wù)，這些任務(wù)提出查詢請求并將該請求和索引信息打包發(fā)送到系統(tǒng)的文件管理中心，即NameNode。

NameNode對索引信息進(jìn)行解析，獲取文件名；查詢HDFS中隸屬于該文件的所有數(shù)據(jù)塊及副本信息，并從中隨機(jī)選擇一個數(shù)據(jù)塊來響應(yīng)查詢請求；將該數(shù)據(jù)塊的ID以及NIHDFS索引信息發(fā)送給數(shù)據(jù)塊所在的機(jī)器節(jié)點(diǎn)，即查詢服務(wù)節(jié)點(diǎn)。

查詢服務(wù)節(jié)點(diǎn)收到查詢請求信息之后，首先根據(jù)請求信息中的數(shù)據(jù)塊ID和路徑信息在本地定位到該數(shù)據(jù)塊；其次，對NIHDFS索引信息進(jìn)行解析，依據(jù)塊內(nèi)偏移量，準(zhǔn)確定位記錄元組的物理位置；最后，根據(jù)記錄元組的起始位置和記錄長度，獲取完整的元組信息，并將其回送到請求節(jié)點(diǎn)。查詢請求節(jié)點(diǎn)對接受到的記錄元組進(jìn)行解析，從中獲取本次鏈接所需的鏈接屬性信息，從而完成整個查詢流程。

當(dāng)遇到如圖4所示的索引時，需進(jìn)行兩次查詢操作，將兩次查詢結(jié)果按照先后順序整合起來，得到完整的記錄元祖信息。

4 整體系統(tǒng)優(yōu)化

4.1 NIHDFS優(yōu)化

在對NIHDFS索引執(zhí)行查詢操作是，F(xiàn)ile URL是不可或缺的。隸屬于同一個文件的所有記錄元組都對應(yīng)著一個相同的File URL，這導(dǎo)致File URL被多次重復(fù)存儲，由于File URL相對較長，多次重復(fù)存儲所占用的磁盤空間是不可忽略的。為了解決該問題，本文用哈希方法把文件標(biāo)示符集合S與File URL集合做成一一映射，用文件標(biāo)示符S替代File URL，從而減少File URL長度，降低磁盤消耗。

采用預(yù)處理添加分隔符的方法對索引中的塊內(nèi)記錄元組長度信息（Record Length）進(jìn)行優(yōu)化，具體方法如下，在上傳HDFS之前，對鏈接表進(jìn)行預(yù)處理。一方面，將一條完整的記錄元組信息存儲為一行，行與行之間的回車換行符作為元組與元組之間的分隔符，用分隔符替代塊內(nèi)記錄長度。當(dāng)元組被載入內(nèi)存進(jìn)行索引化操作或者查詢服務(wù)節(jié)點(diǎn)響應(yīng)查詢請求獲取記錄元組時，都以分隔符作為元組記錄結(jié)束的標(biāo)志，而不必關(guān)心各記錄元組的長度。將記錄長度信息從索引中去掉，達(dá)到簡化索引結(jié)構(gòu)的目的。另一方面，在不同屬性之間添加分隔符，降低Map?Reduce任務(wù)解析屬性信息的難度。

4.2 查詢過程優(yōu)化

4.2.1 緩沖池法

鏈接過程中，部分記錄元組在短時間內(nèi)會被多次重復(fù)查詢，每次都要執(zhí)行完整的查詢過程，這是不必要的。本文采用緩沖池法對其進(jìn)行優(yōu)化，經(jīng)常被查詢的記錄元組存放于內(nèi)存緩存池中，當(dāng)查詢請求到來時，先檢查緩存池中是否存在該記錄元組。若存在，則直接從緩存池中提取，否則才執(zhí)行完整的查詢操作，獲取元組信息。采用LRU作為緩存池中記錄元組信息的更新算法。

4.2.2 二次排序法

在數(shù)據(jù)塊中定位記錄元組時，文件指針的移動操作是很頻繁的。由于文件指針的單向向下的移動特性，當(dāng)訪問的內(nèi)容不是按照偏移量由小到大有序時，指針無效移動次數(shù)會相當(dāng)高。本文采用二次排序的方法對系統(tǒng)進(jìn)行優(yōu)化。在原Hadoop系統(tǒng)上添加二次排序功能模塊，用以對中間結(jié)果中索引信息進(jìn)行排序。排序策略如下：依照數(shù)據(jù)塊間偏移量的大小，對數(shù)據(jù)塊從小到大進(jìn)行排序，即一次排序；同一個數(shù)據(jù)塊內(nèi)的記錄，依照塊內(nèi)記錄元組偏移量的大小，按從小到大順序進(jìn)行排序，即二次排序。有序的中間結(jié)果能夠大幅減少查詢的過程中文件指針無效移動的次數(shù)，從而提高定位效率。由于Map?Reduce過程中會對記錄元組進(jìn)行排序，二次排序在此基礎(chǔ)上進(jìn)行，開銷不大。

4.2.3 并行執(zhí)行

鏈接過程中，查詢記錄所在的物理位置集中

于數(shù)據(jù)塊的某些區(qū)域，并且在一定的時間范圍內(nèi)該區(qū)域被查詢訪問的頻率很高，本文把這樣的區(qū)域稱為查詢熱區(qū)。采用并行執(zhí)行的思想，把單個數(shù)據(jù)塊查詢熱區(qū)的數(shù)量上限設(shè)置為M，對于含有N個查詢熱區(qū)的數(shù)據(jù)塊來說，如果N≤M，那么就開啟N個線程，每一個線程中設(shè)置一個指向?qū)?yīng)熱區(qū)的文件指針，該指針只響應(yīng)本熱區(qū)的記錄元組查詢請求。當(dāng)N>M時，采用隨機(jī)的方法選取兩個相鄰的熱區(qū)并將其合并成一個熱區(qū)，同時對N執(zhí)行減一操作，直到N≤M，然后采取與N≤M時相同的操作。查詢熱區(qū)的并行執(zhí)行方法，一方面使得數(shù)據(jù)塊擁有同時響應(yīng)多個查詢請求的能力，提升查詢操作的并行度，在查詢請求集中爆發(fā)時依然能夠保證查詢效率；另一方面，它將指針的定位操作集中到數(shù)據(jù)塊的查詢熱區(qū)上，從而避免了熱區(qū)之間大量的無效指針移位，提升定位效率。

5 實(shí)驗部分

5.1 實(shí)驗環(huán)境

本實(shí)驗運(yùn)行在由五臺服務(wù)器搭建的集群上，機(jī)器均為同等配置。服務(wù)器硬件環(huán)境是：1.6 GHz的八核CPU，16 GB內(nèi)存，150 GB硬盤。軟件環(huán)境：ubuntu10.10，JDK1.6，Hadoop?1.1.2，以及Hadoop?1.1.2?NDFSI。實(shí)驗數(shù)據(jù)是TPC?H的基準(zhǔn)數(shù)據(jù)集，選用nation， region，customer，orders四張表作為輸入數(shù)據(jù)，數(shù)據(jù)規(guī)模為397.6M。

5.2 實(shí)驗內(nèi)容以及結(jié)果分析

兩個系統(tǒng)分別執(zhí)行了四張表的鏈接操作，鏈接的具體過程如圖5所示。

鏈接算法是經(jīng)典的Reduce Join算法，兩個系統(tǒng)分別執(zhí)行了五遍該算法，將各個階段的統(tǒng)計信息整合求取平均值，并將其填入表1中。由于Hadoop?1.1.2?NIHDFS系統(tǒng)的最終結(jié)果是一系列NIHDFS索引信息，需要將其恢復(fù)為記錄元組，該階段消耗的時間是t4，產(chǎn)生的中間結(jié)果是size4，原系統(tǒng)在該階段不需要做任何操作。

Hadoop?1.1.2?NIHDFS系統(tǒng)產(chǎn)生的中間結(jié)果size1，size2，size3遠(yuǎn)比原系統(tǒng)要小，鏈接操作所消耗的時間也比原系統(tǒng)要小很多，空間和時間消耗對比如圖6和圖7所示。與原系統(tǒng)相比，新系統(tǒng)空間性能提升35.5%，時間性能提升12.9%，時間和空間整體對比如圖8所示。本實(shí)驗表明，“替換?查詢”的多表鏈接處理方法能夠有效地減少中間結(jié)果的數(shù)據(jù)規(guī)模和增長速度，提升系統(tǒng)效率。

6 結(jié) 語

本文通過對記錄元組建立NIHDFS索引，用索引替代冗長的記錄元組信息參與鏈接，并對索引結(jié)構(gòu)進(jìn)行優(yōu)化，從而大大減少中間結(jié)果的數(shù)據(jù)規(guī)模。

運(yùn)用緩沖池，二次排序以及并行執(zhí)行的方法對查詢過程進(jìn)行優(yōu)化，該方法適用于鏈接表屬性較多，記錄元組長度較長的場合。

參考文獻(xiàn)

[1] AFRATI F， ULLMAN J. Optimizing joins in a map?reduce environment [C]//Proceedings of 2010 EDBT. New York： ACM， 2010： 99?110.

[2] JIANG Da?wei， TUNG A， CHEN Gang. Map?join?reduce： towards scalable and efficient data analysis on large clusters [J]. IEEE Transactions on Knowledge and Data Engineering， 2010， 23（9）： 1299?1311.

[3] LIN Yu?ting， AGRAWAL D， CHEN Chun， et a1. Llama： leveraging columnar storage for scalable join [C]// Proceedings of 2011 ACM SIGMOD International Conference on Management of Data. New York： ACM， 2011： 861?972.

[4] 趙保學(xué)，李戰(zhàn)懷，陳群，等.基于共享的MapReduce多查詢優(yōu)化技術(shù)[J].計算機(jī)應(yīng)用研究，2013（5）：74?76.

[5] 趙保學(xué)，李戰(zhàn)懷，陳群，等.可擴(kuò)展Hadoop任務(wù)分配模塊的研究與實(shí)現(xiàn)[C]//第29屆中國數(shù)據(jù)庫學(xué)術(shù)會議論文集（B輯）（NDBC2012）.合肥：知識與數(shù)據(jù)工程實(shí)驗室，2012：83?85.

[6] 林大云.基于Hadoop的微博信息挖掘[J].計算機(jī)光盤軟件與應(yīng)用，2012（1）：7?8.

[7] DEAN J， GHEMAWAT S. MapReduce： simplified data processing on large cluster [J]. Communications of the ACM， 2008， 51（1）： 107?113.

[8] 王珊，王會舉，覃雄派，等.架構(gòu)大數(shù)據(jù)：挑戰(zhàn)、現(xiàn)狀與展望[J].計算機(jī)學(xué)報，2011，34（10）：1741?1751.

5 實(shí)驗部分

5.1 實(shí)驗環(huán)境

本實(shí)驗運(yùn)行在由五臺服務(wù)器搭建的集群上，機(jī)器均為同等配置。服務(wù)器硬件環(huán)境是：1.6 GHz的八核CPU，16 GB內(nèi)存，150 GB硬盤。軟件環(huán)境：ubuntu10.10，JDK1.6，Hadoop?1.1.2，以及Hadoop?1.1.2?NDFSI。實(shí)驗數(shù)據(jù)是TPC?H的基準(zhǔn)數(shù)據(jù)集，選用nation， region，customer，orders四張表作為輸入數(shù)據(jù)，數(shù)據(jù)規(guī)模為397.6M。

5.2 實(shí)驗內(nèi)容以及結(jié)果分析

兩個系統(tǒng)分別執(zhí)行了四張表的鏈接操作，鏈接的具體過程如圖5所示。

鏈接算法是經(jīng)典的Reduce Join算法，兩個系統(tǒng)分別執(zhí)行了五遍該算法，將各個階段的統(tǒng)計信息整合求取平均值，并將其填入表1中。由于Hadoop?1.1.2?NIHDFS系統(tǒng)的最終結(jié)果是一系列NIHDFS索引信息，需要將其恢復(fù)為記錄元組，該階段消耗的時間是t4，產(chǎn)生的中間結(jié)果是size4，原系統(tǒng)在該階段不需要做任何操作。

Hadoop?1.1.2?NIHDFS系統(tǒng)產(chǎn)生的中間結(jié)果size1，size2，size3遠(yuǎn)比原系統(tǒng)要小，鏈接操作所消耗的時間也比原系統(tǒng)要小很多，空間和時間消耗對比如圖6和圖7所示。與原系統(tǒng)相比，新系統(tǒng)空間性能提升35.5%，時間性能提升12.9%，時間和空間整體對比如圖8所示。本實(shí)驗表明，“替換?查詢”的多表鏈接處理方法能夠有效地減少中間結(jié)果的數(shù)據(jù)規(guī)模和增長速度，提升系統(tǒng)效率。

6 結(jié) 語

本文通過對記錄元組建立NIHDFS索引，用索引替代冗長的記錄元組信息參與鏈接，并對索引結(jié)構(gòu)進(jìn)行優(yōu)化，從而大大減少中間結(jié)果的數(shù)據(jù)規(guī)模。

運(yùn)用緩沖池，二次排序以及并行執(zhí)行的方法對查詢過程進(jìn)行優(yōu)化，該方法適用于鏈接表屬性較多，記錄元組長度較長的場合。

參考文獻(xiàn)

[1] AFRATI F， ULLMAN J. Optimizing joins in a map?reduce environment [C]//Proceedings of 2010 EDBT. New York： ACM， 2010： 99?110.

[2] JIANG Da?wei， TUNG A， CHEN Gang. Map?join?reduce： towards scalable and efficient data analysis on large clusters [J]. IEEE Transactions on Knowledge and Data Engineering， 2010， 23（9）： 1299?1311.

[3] LIN Yu?ting， AGRAWAL D， CHEN Chun， et a1. Llama： leveraging columnar storage for scalable join [C]// Proceedings of 2011 ACM SIGMOD International Conference on Management of Data. New York： ACM， 2011： 861?972.

[4] 趙保學(xué)，李戰(zhàn)懷，陳群，等.基于共享的MapReduce多查詢優(yōu)化技術(shù)[J].計算機(jī)應(yīng)用研究，2013（5）：74?76.

[5] 趙保學(xué)，李戰(zhàn)懷，陳群，等.可擴(kuò)展Hadoop任務(wù)分配模塊的研究與實(shí)現(xiàn)[C]//第29屆中國數(shù)據(jù)庫學(xué)術(shù)會議論文集（B輯）（NDBC2012）.合肥：知識與數(shù)據(jù)工程實(shí)驗室，2012：83?85.

[6] 林大云.基于Hadoop的微博信息挖掘[J].計算機(jī)光盤軟件與應(yīng)用，2012（1）：7?8.

[7] DEAN J， GHEMAWAT S. MapReduce： simplified data processing on large cluster [J]. Communications of the ACM， 2008， 51（1）： 107?113.

[8] 王珊，王會舉，覃雄派，等.架構(gòu)大數(shù)據(jù)：挑戰(zhàn)、現(xiàn)狀與展望[J].計算機(jī)學(xué)報，2011，34（10）：1741?1751.

5 實(shí)驗部分

5.1 實(shí)驗環(huán)境

本實(shí)驗運(yùn)行在由五臺服務(wù)器搭建的集群上，機(jī)器均為同等配置。服務(wù)器硬件環(huán)境是：1.6 GHz的八核CPU，16 GB內(nèi)存，150 GB硬盤。軟件環(huán)境：ubuntu10.10，JDK1.6，Hadoop?1.1.2，以及Hadoop?1.1.2?NDFSI。實(shí)驗數(shù)據(jù)是TPC?H的基準(zhǔn)數(shù)據(jù)集，選用nation， region，customer，orders四張表作為輸入數(shù)據(jù)，數(shù)據(jù)規(guī)模為397.6M。

5.2 實(shí)驗內(nèi)容以及結(jié)果分析

兩個系統(tǒng)分別執(zhí)行了四張表的鏈接操作，鏈接的具體過程如圖5所示。

鏈接算法是經(jīng)典的Reduce Join算法，兩個系統(tǒng)分別執(zhí)行了五遍該算法，將各個階段的統(tǒng)計信息整合求取平均值，并將其填入表1中。由于Hadoop?1.1.2?NIHDFS系統(tǒng)的最終結(jié)果是一系列NIHDFS索引信息，需要將其恢復(fù)為記錄元組，該階段消耗的時間是t4，產(chǎn)生的中間結(jié)果是size4，原系統(tǒng)在該階段不需要做任何操作。

Hadoop?1.1.2?NIHDFS系統(tǒng)產(chǎn)生的中間結(jié)果size1，size2，size3遠(yuǎn)比原系統(tǒng)要小，鏈接操作所消耗的時間也比原系統(tǒng)要小很多，空間和時間消耗對比如圖6和圖7所示。與原系統(tǒng)相比，新系統(tǒng)空間性能提升35.5%，時間性能提升12.9%，時間和空間整體對比如圖8所示。本實(shí)驗表明，“替換?查詢”的多表鏈接處理方法能夠有效地減少中間結(jié)果的數(shù)據(jù)規(guī)模和增長速度，提升系統(tǒng)效率。

6 結(jié) 語

本文通過對記錄元組建立NIHDFS索引，用索引替代冗長的記錄元組信息參與鏈接，并對索引結(jié)構(gòu)進(jìn)行優(yōu)化，從而大大減少中間結(jié)果的數(shù)據(jù)規(guī)模。

運(yùn)用緩沖池，二次排序以及并行執(zhí)行的方法對查詢過程進(jìn)行優(yōu)化，該方法適用于鏈接表屬性較多，記錄元組長度較長的場合。

參考文獻(xiàn)

[1] AFRATI F， ULLMAN J. Optimizing joins in a map?reduce environment [C]//Proceedings of 2010 EDBT. New York： ACM， 2010： 99?110.

[2] JIANG Da?wei， TUNG A， CHEN Gang. Map?join?reduce： towards scalable and efficient data analysis on large clusters [J]. IEEE Transactions on Knowledge and Data Engineering， 2010， 23（9）： 1299?1311.

[3] LIN Yu?ting， AGRAWAL D， CHEN Chun， et a1. Llama： leveraging columnar storage for scalable join [C]// Proceedings of 2011 ACM SIGMOD International Conference on Management of Data. New York： ACM， 2011： 861?972.

[4] 趙保學(xué)，李戰(zhàn)懷，陳群，等.基于共享的MapReduce多查詢優(yōu)化技術(shù)[J].計算機(jī)應(yīng)用研究，2013（5）：74?76.

[5] 趙保學(xué)，李戰(zhàn)懷，陳群，等.可擴(kuò)展Hadoop任務(wù)分配模塊的研究與實(shí)現(xiàn)[C]//第29屆中國數(shù)據(jù)庫學(xué)術(shù)會議論文集（B輯）（NDBC2012）.合肥：知識與數(shù)據(jù)工程實(shí)驗室，2012：83?85.

[6] 林大云.基于Hadoop的微博信息挖掘[J].計算機(jī)光盤軟件與應(yīng)用，2012（1）：7?8.

[7] DEAN J， GHEMAWAT S. MapReduce： simplified data processing on large cluster [J]. Communications of the ACM， 2008， 51（1）： 107?113.

[8] 王珊，王會舉，覃雄派，等.架構(gòu)大數(shù)據(jù)：挑戰(zhàn)、現(xiàn)狀與展望[J].計算機(jī)學(xué)報，2011，34（10）：1741?1751.