一種基于MapReduce的分布式索引方法

摘 要：海量文本快速索引是云檢索系統(tǒng)的一個(gè)難點(diǎn)，而分布式索引程序的開發(fā)難度較大。文中提出了一種基于MapReduce的分布式索引方法，通過在Map函數(shù)中執(zhí)行文檔的解析及索引，以及在Reduce函數(shù)中合并索引數(shù)據(jù)，以減少文檔排序的工作量，提高索引效率。實(shí)驗(yàn)結(jié)果表明，該方法適用于海量數(shù)據(jù)的并行處理。

關(guān)鍵詞：海量文本；分布式；索引；MapReduce

中圖分類號(hào)：TP302文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2095-1302（2014）07-0065-02

0引言

海量數(shù)據(jù)的使用越來越受到人們的關(guān)注，如何實(shí)現(xiàn)為海量文本數(shù)據(jù)快速創(chuàng)建索引以供用戶檢索已經(jīng)成為當(dāng)前面臨的一個(gè)重要課題。傳統(tǒng)的集中式索引方案已經(jīng)無法滿足需求，隨著MapReduce機(jī)制的出現(xiàn)[1]，人們開始研究使用MapReduce進(jìn)行分布式索引的方案。現(xiàn)有的基于MapReduce的方法都局限于MapReduce的原始框架[2,3]，無法處理數(shù)據(jù)量大、不可分割的文檔，也缺乏對(duì)海量索引的管理機(jī)制。因此，通過對(duì)現(xiàn)有方法的改進(jìn)[4]，本文設(shè)計(jì)了一種面向海量大文本的MapReduce索引方法，通過實(shí)驗(yàn)測(cè)試了改進(jìn)方案的索引性能。

1MapReduce簡(jiǎn)介

MapReduce是一種通過將任務(wù)分發(fā)到多臺(tái)機(jī)器上來處理大規(guī)模數(shù)據(jù)的編程模式[5]。它最初是由Google設(shè)計(jì)的，用于利用分布式架構(gòu)來處理大數(shù)據(jù)集上的計(jì)算任務(wù)。一個(gè)MapReduce工作主要使用Map和Reduce兩個(gè)函數(shù)。Map函數(shù)接收一個(gè)鍵值對(duì)作為輸入，然后通過特定的計(jì)算輸出一組中間鍵值對(duì)。所有Map函數(shù)的輸出鍵值對(duì)將會(huì)自動(dòng)按照key進(jìn)行排序和分組，然后傳送給Reduce函數(shù)。Reduce函數(shù)將有著相同key的所有中間鍵值對(duì)進(jìn)行合并，得到最終的結(jié)果集。一般處理輸入數(shù)據(jù)的Map任務(wù)會(huì)比較多，而處理Map任務(wù)輸出數(shù)據(jù)的Reduce任務(wù)會(huì)少一點(diǎn)。Map任務(wù)和Reduce任務(wù)都可以運(yùn)行在不同的機(jī)器上來實(shí)現(xiàn)并行化，每個(gè)任務(wù)都是獨(dú)立于其他同類型的任務(wù)的，這就使得分布式應(yīng)用的開發(fā)變得輕松了許多[6]。

2MI-RM索引方法

本文設(shè)計(jì)的分布式索引方法的主要思想是：在Map函數(shù)中執(zhí)行文檔的解析及索引，而在Reduce函數(shù)中合并這些索引數(shù)據(jù)，即“Map Index–Reduce Merge”，簡(jiǎn)記為MI-RM方法。MI-RM方法采用的策略是，將文檔平均分組，每個(gè)組內(nèi)的文檔的索引數(shù)據(jù)交給一個(gè)Reduce任務(wù)來合并。Map函數(shù)輸出的中間鍵值對(duì)是，其中DocGroup表示該文檔所屬的分組，DocIndex表示該文檔的索引數(shù)據(jù)。這樣，中間鍵值對(duì)的數(shù)量就會(huì)少了很多，排序的工作量會(huì)大大地減少。

Map算法的輸入鍵值對(duì)是，即一個(gè)文檔的分組號(hào)及其存儲(chǔ)路徑。Map函數(shù)從HDFS文件系統(tǒng)得到該文檔的輸入流，并且用文檔解析器來封裝文檔輸入流，用以解析文檔格式。然后，算法即可順序讀取文檔的內(nèi)容，并將其索引到DocIndex中。索引完成后，將該文檔的索引數(shù)據(jù)按照鍵值對(duì)的格式輸出。

Reduce函數(shù)對(duì)同組文檔的索引數(shù)據(jù)進(jìn)行歸并。我們?cè)O(shè)計(jì)了支持自動(dòng)分片的Reduce函數(shù)，將同組的文檔索引再次分片，合并到不同的索引片中。Reduce在合并索引數(shù)據(jù)的時(shí)候，將會(huì)控制索引片的大??；如果索引片已經(jīng)達(dá)到了閥值，那么就將其作為一個(gè)獨(dú)立的索引片輸出，然后再創(chuàng)建一個(gè)新的索引片來存儲(chǔ)剩余數(shù)據(jù)，如此往復(fù)。表1和表2分別展示了MI-RM的Map和Reduce函數(shù)及其算法流程。

表1MI-RM方法的Map函數(shù)

Map

輸入 Key：被索引文檔的組號(hào)DocGroup

Value：被索引文檔的存儲(chǔ)路徑DocPath

輸出 Key：被索引文檔的組號(hào)DocGroup

Value：被索引文檔的索引數(shù)據(jù)DocIndex

1：從HDFS上獲得DocPath所指向文檔的數(shù)據(jù)流DocStream；

2：用文檔解析器封裝DocStream，獲得過濾后的文檔流FilterStream；

3：創(chuàng)建該文檔的索引DocIndex；

4：從FilterStream讀取文檔，并索引到DocIndex中；

5：輸出

表2MI-RM方法的Reduce函數(shù)

Reduce

輸入 Key：文檔組號(hào)DocGroup

Value：該組文檔的索引數(shù)據(jù)列表DocIndex-List

輸出 Key：索引片序號(hào)s-id

Value：該索引片數(shù)據(jù)Shard

1：初始化索引片序號(hào)s-id = GroupID；

2：創(chuàng)建新索引片；

3：對(duì)于DocIndex-List中的每個(gè)索引DocIndex，循環(huán)：

4：將DocIndex加入到中；

5：如果的大小超過了預(yù)設(shè)閥值：

6：輸出索引片；

7：遞增索引片序號(hào)s-id = s-id + N；

8：創(chuàng)建新索引片；

9： 結(jié)束循環(huán)；

10：輸出最后一個(gè)索引片

3測(cè)試結(jié)果

3.1測(cè)試環(huán)境

首先，我們可以搭建包含3臺(tái)機(jī)器的集群，部署Hadoop進(jìn)行分布式索引測(cè)試。操作系統(tǒng)均為Ubuntu 8.10，HDFS版本是1.9.2。

本文使用數(shù)據(jù)生成器隨機(jī)生成了18個(gè)大小為10 MB的文本進(jìn)行測(cè)試。因?yàn)闇y(cè)試環(huán)境有限，本文沒有使用大的數(shù)據(jù)量，文本的數(shù)量選擇為18是考慮到它正好是節(jié)點(diǎn)數(shù)的整數(shù)倍，可以使得任務(wù)在各節(jié)點(diǎn)上并行的運(yùn)行。

3.2結(jié)果與分析

在測(cè)試中，我們將MI-RM索引方法配置為18個(gè)Map任務(wù)和3個(gè)Reduce任務(wù)。其中每個(gè)節(jié)點(diǎn)上可以并發(fā)地執(zhí)行6個(gè)任務(wù)，也就是說，Map任務(wù)的最大并發(fā)量為6。測(cè)試結(jié)果如下：Map執(zhí)行的總時(shí)間為34.253 s，Reduce執(zhí)行的總時(shí)間為35.515 s，總的執(zhí)行時(shí)間為45.232 s，而采用集中式索引方法處理同樣的數(shù)據(jù)則需要97.232 s，該結(jié)果體現(xiàn)了MI-RM索引方法的效率要優(yōu)于傳統(tǒng)的集中式索引方法。

4結(jié)語

本文探討了一種基于MapReduce的分布式索引方法，并與集中式索引方法做了測(cè)試比較，通過實(shí)驗(yàn)表明這種方法能夠減化文檔排序的工作量，從而提高建立文本索引的效率，能夠滿足海量文本數(shù)據(jù)檢索的需求。

參 考 文 獻(xiàn)

[1] Richard M C McCreadie， Craig Macdonald， IadhOunis. Comparing Distributed Indexing： To MapReduce or Not? [C].Proceedings of LSDS-IR Workshop， Boston， USA， 2009.8-17.

[2] IoannisKonstantinou， Evangelos Angelou， DimitriosTsoumakos et al. Distributed Indexing of Web Scale Datasets for the Cloud[C].Workshop on massive data analytics on the cloud 2010.2010：1-6.

[3] Chang F， Dean J， Ghemawat S， et al. Bigtable： A distributed storage system for structured Data[C]. Proceedings of OSDI 2006.205-218.

[4]馮汝偉，謝強(qiáng)，丁秋林，等.基于文本聚類與分布式Lucene的知識(shí)檢索[J].計(jì)算機(jī)應(yīng)用，2013，33（1）：186-188.

[5]馬燦，孟丹，熊勁，等.基于分布式索引和目錄聚合的海量小文件存儲(chǔ)研究[J].高技術(shù)通訊，2012，22（10）：1035-1040.

[6]張玥，俞昊旻，張奇，等.面向文本拷貝檢測(cè)的分布式索引[J].中文信息學(xué)報(bào)，2011，25（1）：91-97.

作者簡(jiǎn)介：邵武長(zhǎng)（1988—），男，江蘇省徐州市人，碩士研究生。主要研究方向是工業(yè)智能與仿真。

————————————————

收稿日期：2014-03-31

摘 要：海量文本快速索引是云檢索系統(tǒng)的一個(gè)難點(diǎn)，而分布式索引程序的開發(fā)難度較大。文中提出了一種基于MapReduce的分布式索引方法，通過在Map函數(shù)中執(zhí)行文檔的解析及索引，以及在Reduce函數(shù)中合并索引數(shù)據(jù)，以減少文檔排序的工作量，提高索引效率。實(shí)驗(yàn)結(jié)果表明，該方法適用于海量數(shù)據(jù)的并行處理。

關(guān)鍵詞：海量文本；分布式；索引；MapReduce

中圖分類號(hào)：TP302文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2095-1302（2014）07-0065-02

0引言

海量數(shù)據(jù)的使用越來越受到人們的關(guān)注，如何實(shí)現(xiàn)為海量文本數(shù)據(jù)快速創(chuàng)建索引以供用戶檢索已經(jīng)成為當(dāng)前面臨的一個(gè)重要課題。傳統(tǒng)的集中式索引方案已經(jīng)無法滿足需求，隨著MapReduce機(jī)制的出現(xiàn)[1]，人們開始研究使用MapReduce進(jìn)行分布式索引的方案?，F(xiàn)有的基于MapReduce的方法都局限于MapReduce的原始框架[2,3]，無法處理數(shù)據(jù)量大、不可分割的文檔，也缺乏對(duì)海量索引的管理機(jī)制。因此，通過對(duì)現(xiàn)有方法的改進(jìn)[4]，本文設(shè)計(jì)了一種面向海量大文本的MapReduce索引方法，通過實(shí)驗(yàn)測(cè)試了改進(jìn)方案的索引性能。

1MapReduce簡(jiǎn)介

MapReduce是一種通過將任務(wù)分發(fā)到多臺(tái)機(jī)器上來處理大規(guī)模數(shù)據(jù)的編程模式[5]。它最初是由Google設(shè)計(jì)的，用于利用分布式架構(gòu)來處理大數(shù)據(jù)集上的計(jì)算任務(wù)。一個(gè)MapReduce工作主要使用Map和Reduce兩個(gè)函數(shù)。Map函數(shù)接收一個(gè)鍵值對(duì)作為輸入，然后通過特定的計(jì)算輸出一組中間鍵值對(duì)。所有Map函數(shù)的輸出鍵值對(duì)將會(huì)自動(dòng)按照key進(jìn)行排序和分組，然后傳送給Reduce函數(shù)。Reduce函數(shù)將有著相同key的所有中間鍵值對(duì)進(jìn)行合并，得到最終的結(jié)果集。一般處理輸入數(shù)據(jù)的Map任務(wù)會(huì)比較多，而處理Map任務(wù)輸出數(shù)據(jù)的Reduce任務(wù)會(huì)少一點(diǎn)。Map任務(wù)和Reduce任務(wù)都可以運(yùn)行在不同的機(jī)器上來實(shí)現(xiàn)并行化，每個(gè)任務(wù)都是獨(dú)立于其他同類型的任務(wù)的，這就使得分布式應(yīng)用的開發(fā)變得輕松了許多[6]。

2MI-RM索引方法

本文設(shè)計(jì)的分布式索引方法的主要思想是：在Map函數(shù)中執(zhí)行文檔的解析及索引，而在Reduce函數(shù)中合并這些索引數(shù)據(jù)，即“Map Index–Reduce Merge”，簡(jiǎn)記為MI-RM方法。MI-RM方法采用的策略是，將文檔平均分組，每個(gè)組內(nèi)的文檔的索引數(shù)據(jù)交給一個(gè)Reduce任務(wù)來合并。Map函數(shù)輸出的中間鍵值對(duì)是，其中DocGroup表示該文檔所屬的分組，DocIndex表示該文檔的索引數(shù)據(jù)。這樣，中間鍵值對(duì)的數(shù)量就會(huì)少了很多，排序的工作量會(huì)大大地減少。

Map算法的輸入鍵值對(duì)是，即一個(gè)文檔的分組號(hào)及其存儲(chǔ)路徑。Map函數(shù)從HDFS文件系統(tǒng)得到該文檔的輸入流，并且用文檔解析器來封裝文檔輸入流，用以解析文檔格式。然后，算法即可順序讀取文檔的內(nèi)容，并將其索引到DocIndex中。索引完成后，將該文檔的索引數(shù)據(jù)按照鍵值對(duì)的格式輸出。

Reduce函數(shù)對(duì)同組文檔的索引數(shù)據(jù)進(jìn)行歸并。我們?cè)O(shè)計(jì)了支持自動(dòng)分片的Reduce函數(shù)，將同組的文檔索引再次分片，合并到不同的索引片中。Reduce在合并索引數(shù)據(jù)的時(shí)候，將會(huì)控制索引片的大??；如果索引片已經(jīng)達(dá)到了閥值，那么就將其作為一個(gè)獨(dú)立的索引片輸出，然后再創(chuàng)建一個(gè)新的索引片來存儲(chǔ)剩余數(shù)據(jù)，如此往復(fù)。表1和表2分別展示了MI-RM的Map和Reduce函數(shù)及其算法流程。

表1MI-RM方法的Map函數(shù)

Map

輸入 Key：被索引文檔的組號(hào)DocGroup

Value：被索引文檔的存儲(chǔ)路徑DocPath

輸出 Key：被索引文檔的組號(hào)DocGroup

Value：被索引文檔的索引數(shù)據(jù)DocIndex

1：從HDFS上獲得DocPath所指向文檔的數(shù)據(jù)流DocStream；

2：用文檔解析器封裝DocStream，獲得過濾后的文檔流FilterStream；

3：創(chuàng)建該文檔的索引DocIndex；

4：從FilterStream讀取文檔，并索引到DocIndex中；

5：輸出

表2MI-RM方法的Reduce函數(shù)

Reduce

輸入 Key：文檔組號(hào)DocGroup

Value：該組文檔的索引數(shù)據(jù)列表DocIndex-List

輸出 Key：索引片序號(hào)s-id

Value：該索引片數(shù)據(jù)Shard

1：初始化索引片序號(hào)s-id = GroupID；

2：創(chuàng)建新索引片；

3：對(duì)于DocIndex-List中的每個(gè)索引DocIndex，循環(huán)：

4：將DocIndex加入到中；

5：如果的大小超過了預(yù)設(shè)閥值：

6：輸出索引片；

7：遞增索引片序號(hào)s-id = s-id + N；

8：創(chuàng)建新索引片；

9： 結(jié)束循環(huán)；

10：輸出最后一個(gè)索引片

3測(cè)試結(jié)果

3.1測(cè)試環(huán)境

首先，我們可以搭建包含3臺(tái)機(jī)器的集群，部署Hadoop進(jìn)行分布式索引測(cè)試。操作系統(tǒng)均為Ubuntu 8.10，HDFS版本是1.9.2。

本文使用數(shù)據(jù)生成器隨機(jī)生成了18個(gè)大小為10 MB的文本進(jìn)行測(cè)試。因?yàn)闇y(cè)試環(huán)境有限，本文沒有使用大的數(shù)據(jù)量，文本的數(shù)量選擇為18是考慮到它正好是節(jié)點(diǎn)數(shù)的整數(shù)倍，可以使得任務(wù)在各節(jié)點(diǎn)上并行的運(yùn)行。

3.2結(jié)果與分析

在測(cè)試中，我們將MI-RM索引方法配置為18個(gè)Map任務(wù)和3個(gè)Reduce任務(wù)。其中每個(gè)節(jié)點(diǎn)上可以并發(fā)地執(zhí)行6個(gè)任務(wù)，也就是說，Map任務(wù)的最大并發(fā)量為6。測(cè)試結(jié)果如下：Map執(zhí)行的總時(shí)間為34.253 s，Reduce執(zhí)行的總時(shí)間為35.515 s，總的執(zhí)行時(shí)間為45.232 s，而采用集中式索引方法處理同樣的數(shù)據(jù)則需要97.232 s，該結(jié)果體現(xiàn)了MI-RM索引方法的效率要優(yōu)于傳統(tǒng)的集中式索引方法。

4結(jié)語

本文探討了一種基于MapReduce的分布式索引方法，并與集中式索引方法做了測(cè)試比較，通過實(shí)驗(yàn)表明這種方法能夠減化文檔排序的工作量，從而提高建立文本索引的效率，能夠滿足海量文本數(shù)據(jù)檢索的需求。

參 考 文 獻(xiàn)

[1] Richard M C McCreadie， Craig Macdonald， IadhOunis. Comparing Distributed Indexing： To MapReduce or Not? [C].Proceedings of LSDS-IR Workshop， Boston， USA， 2009.8-17.

[2] IoannisKonstantinou， Evangelos Angelou， DimitriosTsoumakos et al. Distributed Indexing of Web Scale Datasets for the Cloud[C].Workshop on massive data analytics on the cloud 2010.2010：1-6.

[3] Chang F， Dean J， Ghemawat S， et al. Bigtable： A distributed storage system for structured Data[C]. Proceedings of OSDI 2006.205-218.

[4]馮汝偉，謝強(qiáng)，丁秋林，等.基于文本聚類與分布式Lucene的知識(shí)檢索[J].計(jì)算機(jī)應(yīng)用，2013，33（1）：186-188.

[5]馬燦，孟丹，熊勁，等.基于分布式索引和目錄聚合的海量小文件存儲(chǔ)研究[J].高技術(shù)通訊，2012，22（10）：1035-1040.

[6]張玥，俞昊旻，張奇，等.面向文本拷貝檢測(cè)的分布式索引[J].中文信息學(xué)報(bào)，2011，25（1）：91-97.

作者簡(jiǎn)介：邵武長(zhǎng)（1988—），男，江蘇省徐州市人，碩士研究生。主要研究方向是工業(yè)智能與仿真。

————————————————

收稿日期：2014-03-31

摘 要：海量文本快速索引是云檢索系統(tǒng)的一個(gè)難點(diǎn)，而分布式索引程序的開發(fā)難度較大。文中提出了一種基于MapReduce的分布式索引方法，通過在Map函數(shù)中執(zhí)行文檔的解析及索引，以及在Reduce函數(shù)中合并索引數(shù)據(jù)，以減少文檔排序的工作量，提高索引效率。實(shí)驗(yàn)結(jié)果表明，該方法適用于海量數(shù)據(jù)的并行處理。

關(guān)鍵詞：海量文本；分布式；索引；MapReduce

中圖分類號(hào)：TP302文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2095-1302（2014）07-0065-02

0引言

海量數(shù)據(jù)的使用越來越受到人們的關(guān)注，如何實(shí)現(xiàn)為海量文本數(shù)據(jù)快速創(chuàng)建索引以供用戶檢索已經(jīng)成為當(dāng)前面臨的一個(gè)重要課題。傳統(tǒng)的集中式索引方案已經(jīng)無法滿足需求，隨著MapReduce機(jī)制的出現(xiàn)[1]，人們開始研究使用MapReduce進(jìn)行分布式索引的方案?，F(xiàn)有的基于MapReduce的方法都局限于MapReduce的原始框架[2,3]，無法處理數(shù)據(jù)量大、不可分割的文檔，也缺乏對(duì)海量索引的管理機(jī)制。因此，通過對(duì)現(xiàn)有方法的改進(jìn)[4]，本文設(shè)計(jì)了一種面向海量大文本的MapReduce索引方法，通過實(shí)驗(yàn)測(cè)試了改進(jìn)方案的索引性能。

1MapReduce簡(jiǎn)介

MapReduce是一種通過將任務(wù)分發(fā)到多臺(tái)機(jī)器上來處理大規(guī)模數(shù)據(jù)的編程模式[5]。它最初是由Google設(shè)計(jì)的，用于利用分布式架構(gòu)來處理大數(shù)據(jù)集上的計(jì)算任務(wù)。一個(gè)MapReduce工作主要使用Map和Reduce兩個(gè)函數(shù)。Map函數(shù)接收一個(gè)鍵值對(duì)作為輸入，然后通過特定的計(jì)算輸出一組中間鍵值對(duì)。所有Map函數(shù)的輸出鍵值對(duì)將會(huì)自動(dòng)按照key進(jìn)行排序和分組，然后傳送給Reduce函數(shù)。Reduce函數(shù)將有著相同key的所有中間鍵值對(duì)進(jìn)行合并，得到最終的結(jié)果集。一般處理輸入數(shù)據(jù)的Map任務(wù)會(huì)比較多，而處理Map任務(wù)輸出數(shù)據(jù)的Reduce任務(wù)會(huì)少一點(diǎn)。Map任務(wù)和Reduce任務(wù)都可以運(yùn)行在不同的機(jī)器上來實(shí)現(xiàn)并行化，每個(gè)任務(wù)都是獨(dú)立于其他同類型的任務(wù)的，這就使得分布式應(yīng)用的開發(fā)變得輕松了許多[6]。

2MI-RM索引方法

本文設(shè)計(jì)的分布式索引方法的主要思想是：在Map函數(shù)中執(zhí)行文檔的解析及索引，而在Reduce函數(shù)中合并這些索引數(shù)據(jù)，即“Map Index–Reduce Merge”，簡(jiǎn)記為MI-RM方法。MI-RM方法采用的策略是，將文檔平均分組，每個(gè)組內(nèi)的文檔的索引數(shù)據(jù)交給一個(gè)Reduce任務(wù)來合并。Map函數(shù)輸出的中間鍵值對(duì)是，其中DocGroup表示該文檔所屬的分組，DocIndex表示該文檔的索引數(shù)據(jù)。這樣，中間鍵值對(duì)的數(shù)量就會(huì)少了很多，排序的工作量會(huì)大大地減少。

Map算法的輸入鍵值對(duì)是，即一個(gè)文檔的分組號(hào)及其存儲(chǔ)路徑。Map函數(shù)從HDFS文件系統(tǒng)得到該文檔的輸入流，并且用文檔解析器來封裝文檔輸入流，用以解析文檔格式。然后，算法即可順序讀取文檔的內(nèi)容，并將其索引到DocIndex中。索引完成后，將該文檔的索引數(shù)據(jù)按照鍵值對(duì)的格式輸出。

Reduce函數(shù)對(duì)同組文檔的索引數(shù)據(jù)進(jìn)行歸并。我們?cè)O(shè)計(jì)了支持自動(dòng)分片的Reduce函數(shù)，將同組的文檔索引再次分片，合并到不同的索引片中。Reduce在合并索引數(shù)據(jù)的時(shí)候，將會(huì)控制索引片的大小；如果索引片已經(jīng)達(dá)到了閥值，那么就將其作為一個(gè)獨(dú)立的索引片輸出，然后再創(chuàng)建一個(gè)新的索引片來存儲(chǔ)剩余數(shù)據(jù)，如此往復(fù)。表1和表2分別展示了MI-RM的Map和Reduce函數(shù)及其算法流程。

表1MI-RM方法的Map函數(shù)

Map

輸入 Key：被索引文檔的組號(hào)DocGroup

Value：被索引文檔的存儲(chǔ)路徑DocPath

輸出 Key：被索引文檔的組號(hào)DocGroup

Value：被索引文檔的索引數(shù)據(jù)DocIndex

1：從HDFS上獲得DocPath所指向文檔的數(shù)據(jù)流DocStream；

2：用文檔解析器封裝DocStream，獲得過濾后的文檔流FilterStream；

3：創(chuàng)建該文檔的索引DocIndex；

4：從FilterStream讀取文檔，并索引到DocIndex中；

5：輸出

表2MI-RM方法的Reduce函數(shù)

Reduce

輸入 Key：文檔組號(hào)DocGroup

Value：該組文檔的索引數(shù)據(jù)列表DocIndex-List

輸出 Key：索引片序號(hào)s-id

Value：該索引片數(shù)據(jù)Shard

1：初始化索引片序號(hào)s-id = GroupID；

2：創(chuàng)建新索引片；

3：對(duì)于DocIndex-List中的每個(gè)索引DocIndex，循環(huán)：

4：將DocIndex加入到中；

5：如果的大小超過了預(yù)設(shè)閥值：

6：輸出索引片；

7：遞增索引片序號(hào)s-id = s-id + N；

8：創(chuàng)建新索引片；

9： 結(jié)束循環(huán)；

10：輸出最后一個(gè)索引片

3測(cè)試結(jié)果

3.1測(cè)試環(huán)境

首先，我們可以搭建包含3臺(tái)機(jī)器的集群，部署Hadoop進(jìn)行分布式索引測(cè)試。操作系統(tǒng)均為Ubuntu 8.10，HDFS版本是1.9.2。

本文使用數(shù)據(jù)生成器隨機(jī)生成了18個(gè)大小為10 MB的文本進(jìn)行測(cè)試。因?yàn)闇y(cè)試環(huán)境有限，本文沒有使用大的數(shù)據(jù)量，文本的數(shù)量選擇為18是考慮到它正好是節(jié)點(diǎn)數(shù)的整數(shù)倍，可以使得任務(wù)在各節(jié)點(diǎn)上并行的運(yùn)行。

3.2結(jié)果與分析

在測(cè)試中，我們將MI-RM索引方法配置為18個(gè)Map任務(wù)和3個(gè)Reduce任務(wù)。其中每個(gè)節(jié)點(diǎn)上可以并發(fā)地執(zhí)行6個(gè)任務(wù)，也就是說，Map任務(wù)的最大并發(fā)量為6。測(cè)試結(jié)果如下：Map執(zhí)行的總時(shí)間為34.253 s，Reduce執(zhí)行的總時(shí)間為35.515 s，總的執(zhí)行時(shí)間為45.232 s，而采用集中式索引方法處理同樣的數(shù)據(jù)則需要97.232 s，該結(jié)果體現(xiàn)了MI-RM索引方法的效率要優(yōu)于傳統(tǒng)的集中式索引方法。

4結(jié)語

本文探討了一種基于MapReduce的分布式索引方法，并與集中式索引方法做了測(cè)試比較，通過實(shí)驗(yàn)表明這種方法能夠減化文檔排序的工作量，從而提高建立文本索引的效率，能夠滿足海量文本數(shù)據(jù)檢索的需求。

參 考 文 獻(xiàn)

[1] Richard M C McCreadie， Craig Macdonald， IadhOunis. Comparing Distributed Indexing： To MapReduce or Not? [C].Proceedings of LSDS-IR Workshop， Boston， USA， 2009.8-17.

[2] IoannisKonstantinou， Evangelos Angelou， DimitriosTsoumakos et al. Distributed Indexing of Web Scale Datasets for the Cloud[C].Workshop on massive data analytics on the cloud 2010.2010：1-6.

[3] Chang F， Dean J， Ghemawat S， et al. Bigtable： A distributed storage system for structured Data[C]. Proceedings of OSDI 2006.205-218.

[4]馮汝偉，謝強(qiáng)，丁秋林，等.基于文本聚類與分布式Lucene的知識(shí)檢索[J].計(jì)算機(jī)應(yīng)用，2013，33（1）：186-188.

[5]馬燦，孟丹，熊勁，等.基于分布式索引和目錄聚合的海量小文件存儲(chǔ)研究[J].高技術(shù)通訊，2012，22（10）：1035-1040.

[6]張玥，俞昊旻，張奇，等.面向文本拷貝檢測(cè)的分布式索引[J].中文信息學(xué)報(bào)，2011，25（1）：91-97.

作者簡(jiǎn)介：邵武長(zhǎng)（1988—），男，江蘇省徐州市人，碩士研究生。主要研究方向是工業(yè)智能與仿真。

————————————————

收稿日期：2014-03-31