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

引言

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

1 MapReduce簡介

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

2 MI-RM索引方法

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

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

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

3 測試結(jié)果

3.1 測試環(huán)境

首先，我們可以搭建包含3臺機器的集群，部署Hadoop進行分布式索引測試。操作系統(tǒng)均Ubuntu8.10,HDFS版本是1.9.2。

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

3.2 結(jié)果與分析

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

4 結(jié)語

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

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