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

摘 要：海量文本快速索引是云檢索系統的一個難點，而分布式索引程序的開發難度較大。文中提出了一種基于MapReduce的分布式索引方法，通過在Map函數中執行文檔的解析及索引，以及在Reduce函數中合并索引數據，以減少文檔排序的工作量，提高索引效率。實驗結果表明，該方法適用于海量數據的并行處理。

關鍵詞：海量文本；分布式；索引；MapReduce

中圖分類號：TP302文獻標識碼：A 文章編號：2095-1302（2014）07-0065-02

0引言

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

1MapReduce簡介

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

2MI-RM索引方法

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

Map算法的輸入鍵值對是，即一個文檔的分組號及其存儲路徑。Map函數從HDFS文件系統得到該文檔的輸入流，并且用文檔解析器來封裝文檔輸入流，用以解析文檔格式。然后，算法即可順序讀取文檔的內容，并將其索引到DocIndex中。索引完成后，將該文檔的索引數據按照鍵值對的格式輸出。

Reduce函數對同組文檔的索引數據進行歸并。我們設計了支持自動分片的Reduce函數，將同組的文檔索引再次分片，合并到不同的索引片中。Reduce在合并索引數據的時候，將會控制索引片的大??；如果索引片已經達到了閥值，那么就將其作為一個獨立的索引片輸出，然后再創建一個新的索引片來存儲剩余數據，如此往復。表1和表2分別展示了MI-RM的Map和Reduce函數及其算法流程。

表1MI-RM方法的Map函數

Map

輸入 Key：被索引文檔的組號DocGroup

Value：被索引文檔的存儲路徑DocPath

輸出 Key：被索引文檔的組號DocGroup

Value：被索引文檔的索引數據DocIndex

1：從HDFS上獲得DocPath所指向文檔的數據流DocStream；

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

3：創建該文檔的索引DocIndex；

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

5：輸出

表2MI-RM方法的Reduce函數

Reduce

輸入 Key：文檔組號DocGroup

Value：該組文檔的索引數據列表DocIndex-List

輸出 Key：索引片序號s-id

Value：該索引片數據Shard

1：初始化索引片序號s-id = GroupID；

2：創建新索引片；

3：對于DocIndex-List中的每個索引DocIndex，循環：

4：將DocIndex加入到中；

5：如果的大小超過了預設閥值：

6：輸出索引片；

7：遞增索引片序號s-id = s-id + N；

8：創建新索引片；

9： 結束循環；

10：輸出最后一個索引片

3測試結果

3.1測試環境

首先，我們可以搭建包含3臺機器的集群，部署Hadoop進行分布式索引測試。操作系統均為Ubuntu 8.10，HDFS版本是1.9.2。

本文使用數據生成器隨機生成了18個大小為10 MB的文本進行測試。因為測試環境有限，本文沒有使用大的數據量，文本的數量選擇為18是考慮到它正好是節點數的整數倍，可以使得任務在各節點上并行的運行。

3.2結果與分析

在測試中，我們將MI-RM索引方法配置為18個Map任務和3個Reduce任務。其中每個節點上可以并發地執行6個任務，也就是說，Map任務的最大并發量為6。測試結果如下：Map執行的總時間為34.253 s，Reduce執行的總時間為35.515 s，總的執行時間為45.232 s，而采用集中式索引方法處理同樣的數據則需要97.232 s，該結果體現了MI-RM索引方法的效率要優于傳統的集中式索引方法。

4結語

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

參 考 文 獻

[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]馮汝偉，謝強，丁秋林，等.基于文本聚類與分布式Lucene的知識檢索[J].計算機應用，2013，33（1）：186-188.

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

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

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

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

收稿日期：2014-03-31

摘 要：海量文本快速索引是云檢索系統的一個難點，而分布式索引程序的開發難度較大。文中提出了一種基于MapReduce的分布式索引方法，通過在Map函數中執行文檔的解析及索引，以及在Reduce函數中合并索引數據，以減少文檔排序的工作量，提高索引效率。實驗結果表明，該方法適用于海量數據的并行處理。

關鍵詞：海量文本；分布式；索引；MapReduce

中圖分類號：TP302文獻標識碼：A 文章編號：2095-1302（2014）07-0065-02

0引言

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

1MapReduce簡介

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

2MI-RM索引方法

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

Map算法的輸入鍵值對是，即一個文檔的分組號及其存儲路徑。Map函數從HDFS文件系統得到該文檔的輸入流，并且用文檔解析器來封裝文檔輸入流，用以解析文檔格式。然后，算法即可順序讀取文檔的內容，并將其索引到DocIndex中。索引完成后，將該文檔的索引數據按照鍵值對的格式輸出。

Reduce函數對同組文檔的索引數據進行歸并。我們設計了支持自動分片的Reduce函數，將同組的文檔索引再次分片，合并到不同的索引片中。Reduce在合并索引數據的時候，將會控制索引片的大?。蝗绻饕呀涍_到了閥值，那么就將其作為一個獨立的索引片輸出，然后再創建一個新的索引片來存儲剩余數據，如此往復。表1和表2分別展示了MI-RM的Map和Reduce函數及其算法流程。

表1MI-RM方法的Map函數

Map

輸入 Key：被索引文檔的組號DocGroup

Value：被索引文檔的存儲路徑DocPath

輸出 Key：被索引文檔的組號DocGroup

Value：被索引文檔的索引數據DocIndex

1：從HDFS上獲得DocPath所指向文檔的數據流DocStream；

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

3：創建該文檔的索引DocIndex；

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

5：輸出

表2MI-RM方法的Reduce函數

Reduce

輸入 Key：文檔組號DocGroup

Value：該組文檔的索引數據列表DocIndex-List

輸出 Key：索引片序號s-id

Value：該索引片數據Shard

1：初始化索引片序號s-id = GroupID；

2：創建新索引片；

3：對于DocIndex-List中的每個索引DocIndex，循環：

4：將DocIndex加入到中；

5：如果的大小超過了預設閥值：

6：輸出索引片；

7：遞增索引片序號s-id = s-id + N；

8：創建新索引片；

9： 結束循環；

10：輸出最后一個索引片

3測試結果

3.1測試環境

首先，我們可以搭建包含3臺機器的集群，部署Hadoop進行分布式索引測試。操作系統均為Ubuntu 8.10，HDFS版本是1.9.2。

本文使用數據生成器隨機生成了18個大小為10 MB的文本進行測試。因為測試環境有限，本文沒有使用大的數據量，文本的數量選擇為18是考慮到它正好是節點數的整數倍，可以使得任務在各節點上并行的運行。

3.2結果與分析

在測試中，我們將MI-RM索引方法配置為18個Map任務和3個Reduce任務。其中每個節點上可以并發地執行6個任務，也就是說，Map任務的最大并發量為6。測試結果如下：Map執行的總時間為34.253 s，Reduce執行的總時間為35.515 s，總的執行時間為45.232 s，而采用集中式索引方法處理同樣的數據則需要97.232 s，該結果體現了MI-RM索引方法的效率要優于傳統的集中式索引方法。

4結語

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

參 考 文 獻

[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]馮汝偉，謝強，丁秋林，等.基于文本聚類與分布式Lucene的知識檢索[J].計算機應用，2013，33（1）：186-188.

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

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

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

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

收稿日期：2014-03-31

摘 要：海量文本快速索引是云檢索系統的一個難點，而分布式索引程序的開發難度較大。文中提出了一種基于MapReduce的分布式索引方法，通過在Map函數中執行文檔的解析及索引，以及在Reduce函數中合并索引數據，以減少文檔排序的工作量，提高索引效率。實驗結果表明，該方法適用于海量數據的并行處理。

關鍵詞：海量文本；分布式；索引；MapReduce

中圖分類號：TP302文獻標識碼：A 文章編號：2095-1302（2014）07-0065-02

0引言

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

1MapReduce簡介

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

2MI-RM索引方法

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

Map算法的輸入鍵值對是，即一個文檔的分組號及其存儲路徑。Map函數從HDFS文件系統得到該文檔的輸入流，并且用文檔解析器來封裝文檔輸入流，用以解析文檔格式。然后，算法即可順序讀取文檔的內容，并將其索引到DocIndex中。索引完成后，將該文檔的索引數據按照鍵值對的格式輸出。

Reduce函數對同組文檔的索引數據進行歸并。我們設計了支持自動分片的Reduce函數，將同組的文檔索引再次分片，合并到不同的索引片中。Reduce在合并索引數據的時候，將會控制索引片的大??；如果索引片已經達到了閥值，那么就將其作為一個獨立的索引片輸出，然后再創建一個新的索引片來存儲剩余數據，如此往復。表1和表2分別展示了MI-RM的Map和Reduce函數及其算法流程。

表1MI-RM方法的Map函數

Map

輸入 Key：被索引文檔的組號DocGroup

Value：被索引文檔的存儲路徑DocPath

輸出 Key：被索引文檔的組號DocGroup

Value：被索引文檔的索引數據DocIndex

1：從HDFS上獲得DocPath所指向文檔的數據流DocStream；

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

3：創建該文檔的索引DocIndex；

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

5：輸出

表2MI-RM方法的Reduce函數

Reduce

輸入 Key：文檔組號DocGroup

Value：該組文檔的索引數據列表DocIndex-List

輸出 Key：索引片序號s-id

Value：該索引片數據Shard

1：初始化索引片序號s-id = GroupID；

2：創建新索引片；

3：對于DocIndex-List中的每個索引DocIndex，循環：

4：將DocIndex加入到中；

5：如果的大小超過了預設閥值：

6：輸出索引片；

7：遞增索引片序號s-id = s-id + N；

8：創建新索引片；

9： 結束循環；

10：輸出最后一個索引片

3測試結果

3.1測試環境

首先，我們可以搭建包含3臺機器的集群，部署Hadoop進行分布式索引測試。操作系統均為Ubuntu 8.10，HDFS版本是1.9.2。

本文使用數據生成器隨機生成了18個大小為10 MB的文本進行測試。因為測試環境有限，本文沒有使用大的數據量，文本的數量選擇為18是考慮到它正好是節點數的整數倍，可以使得任務在各節點上并行的運行。

3.2結果與分析

在測試中，我們將MI-RM索引方法配置為18個Map任務和3個Reduce任務。其中每個節點上可以并發地執行6個任務，也就是說，Map任務的最大并發量為6。測試結果如下：Map執行的總時間為34.253 s，Reduce執行的總時間為35.515 s，總的執行時間為45.232 s，而采用集中式索引方法處理同樣的數據則需要97.232 s，該結果體現了MI-RM索引方法的效率要優于傳統的集中式索引方法。

4結語

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

參 考 文 獻

[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]馮汝偉，謝強，丁秋林，等.基于文本聚類與分布式Lucene的知識檢索[J].計算機應用，2013，33（1）：186-188.

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

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

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

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

收稿日期：2014-03-31