基于Hadoop的海量xml索引查詢方案

摘 要：XML（Extensible Markup Language，可擴展標記語言）憑借其簡單、跨平臺、方便閱讀等優(yōu)點，在當今各個領(lǐng)域得到了廣泛的應(yīng)用。然而，作為數(shù)據(jù)交換標準的XML面對當今海量數(shù)據(jù)，由于結(jié)構(gòu)不易拆分等問題，其存儲和查詢性能并不理想。Hadoop的出現(xiàn)，提供了一種新的解決辦法。由于Hadoop本身并不適合類似XML格式的半結(jié)構(gòu)化文件處理，因此本文提出來一種基于Hadoop的海量XML查詢的解決方案，充分利用Hadoop的并行性能，同時還引入了高效的索引機制，很好的解決了海量XML存儲于查詢性能問題，實驗證明，該方案能達到良好的效果。

關(guān)鍵詞：Hadoop；XML；索引；查詢；海量數(shù)據(jù)

中圖分類號：TP311.52

XML是一個萬維網(wǎng)聯(lián)盟（W3C）的建議標準[1]，它被越來越多地用于在不同數(shù)據(jù)源間進行各種形式的數(shù)據(jù)交流。在最近幾年XML海量應(yīng)用正在快速增長，互聯(lián)網(wǎng)上如用戶搜索行為記錄、數(shù)據(jù)庫歷史日志記錄、數(shù)字圖書館系統(tǒng)等，在科學研究上如對歷史天氣記錄，DNA序列記錄等。這些海量XML對我們存儲、查詢、分析數(shù)據(jù)提出了更高的挑戰(zhàn)。

Hadoop是近幾年發(fā)展比較成熟的開源云計算平臺之一，憑借其可靠、高效、可伸縮的特性在互聯(lián)網(wǎng)領(lǐng)域得到了廣泛的應(yīng)用，同時也得到了學術(shù)界的普遍關(guān)注[2]。Hadoop的HDFS（Hadoop distributed file system）分布式文件系統(tǒng)和MapReduce分布式計算框架提供了高可靠性的分布式存儲和高速的海量數(shù)據(jù)計算[3]，使海量存儲XML與高效查詢XML成為可能。

但由于Hadoop對結(jié)構(gòu)化數(shù)據(jù)查詢分析比較容易，對類似于XML這種半結(jié)構(gòu)化，內(nèi)容屬性可擴展的數(shù)據(jù)查詢檢索，Hadoop也略顯無力。因此，本文提出了一種對海量XML文件半結(jié)構(gòu)化數(shù)據(jù)的分割方法，充分利用了已知的XML大致結(jié)構(gòu)，通過MapReduce編程，將海量XML文件并行處理，實現(xiàn)了海量XML查詢；同時，引入了索引機制，避免Hadoop掃描整個海量數(shù)據(jù)，大大減少了查詢時間。

1 相關(guān)研究

迄今為止，對于XML的存儲以及查詢的優(yōu)化算法大部分都是在樹結(jié)構(gòu)的基礎(chǔ)上提出的。這些算法在單機上實現(xiàn)都能表現(xiàn)出不錯的效果，但是，一旦把他們發(fā)到分布式集群上，由于樹不在完整，將無法應(yīng)用算法。

1.1 傳統(tǒng)XML存儲與查詢

對于傳統(tǒng)XML存儲，可直接存放在操作系統(tǒng)的文件系統(tǒng)上即可。

對于傳統(tǒng)XML查詢，傳統(tǒng)的查詢數(shù)據(jù)的做法有：

（1）基于Tree-Based解析：代表有DOM、JDOM、DOM4J，原理是把XML整個以樹的形式讀入內(nèi)存，然后查找。優(yōu)點是可隨機多次查找，支持XPATH路徑查找，支持讀寫操作。缺點是需要加載整個XML，資源耗費大。

（2）基于Event-Based計息：代表有SAX，STAX，原理是以流的方式順序讀取XML信息。優(yōu)點是：不需要加載整個XML，節(jié)約內(nèi)存，節(jié)約時間，速度快。缺點是：不支持多次隨機查找，不支持XPATH，只讀而不能寫。

1.2 海量XML存儲與查詢

由于是海量XML數(shù)據(jù)，數(shù)據(jù)量已超過了單臺電腦硬盤的容量，因此需要一個特殊的分布式文件系統(tǒng)，本文使用的是Hadoop的HDFS。

HDFS是一個高度容錯性的系統(tǒng)，適合部署在廉價的機器上。HDFS能提供高吞吐量的數(shù)據(jù)訪問，非常適合大規(guī)模數(shù)據(jù)集上的應(yīng)用。它有如下特點[4]：

（1）硬件故障是常態(tài)。即硬件故障是常態(tài)，而不是異常，HDFS提供了一個很好的故障檢測和自動快速恢復的容災系統(tǒng)。

（2）流式的數(shù)據(jù)訪問。即運行在HDFS之上的應(yīng)用程序必須流式地訪問它們的數(shù)據(jù)集，這樣極大的提高了分布式數(shù)據(jù)的吞吐量，便于多臺機器協(xié)同工作。

（3）大數(shù)據(jù)集。運行在HDFS之上的程序有很大量的數(shù)據(jù)集。典型的HDFS文件大小是GB到TB的級別。所以，HDFS被調(diào)整成支持大文件。

（4）一次寫入，多次讀出。一個文件一旦創(chuàng)建、寫入、關(guān)閉之后就不需要修改了。這個假定簡單化了數(shù)據(jù)一致的問題和并使高吞吐量的數(shù)據(jù)訪問變得可能。一個Map-Reduce程序或者網(wǎng)絡(luò)爬蟲程序都可以完美地適合這個模型。

（5）數(shù)據(jù)本地化運行。在靠近計算數(shù)據(jù)所存儲的位置來進行計算是最理想的狀態(tài)，尤其是在數(shù)據(jù)集特別巨大的時候。這樣消除了網(wǎng)絡(luò)的擁堵，提高了系統(tǒng)的整體吞吐量。

對海量XML查詢，我們需要對其進行特殊的分割，然后交由分布式環(huán)境進行流式計算處理。

2 海量XML文件處理方案

對于海量XML文件處理，因為HDFS分布式文件系統(tǒng)給我們海量XML文件提供了可靠而高效的存儲管理，所以，我們不必太過關(guān)心XML文件的存儲問題。因此下面著重介紹在分割查詢XML，以及通過索引提高查詢效率上的方案。

2.1 Hadoop的MapReduce處理數(shù)據(jù)流程

（1）MapReduce框架會對指定目錄的文件以用戶指定的方式分割成許多inputSplits（輸入分片），默認會以64M為單位將文件分割[5]。

（2）每個inputSplit將在分布式并行的環(huán)境下，使用用戶指定方法分割每個inputSplit具體內(nèi)容，讀取成（key，value）的形式，再交給map（）函數(shù)處理。

（3）map（）函數(shù)以（key，value）的形式輸出處理后的結(jié)果，經(jīng)過“洗牌合并”處理，即相同的key，使它對應(yīng)的value成為一組，以（key，List（value））的形式交給reduce（）函數(shù)處理。

2.2 XML的分割讀取方法

根據(jù)以上介紹，文件實際上經(jīng)歷了兩個分割，第一次分割是將海量文件分割成許多的inputSplit，每個inpuSplit對應(yīng)于一次Map任務(wù)，多個Map任務(wù)之間并行處理。第二次分割是針對于每一個inputSplit的具體內(nèi)容，把內(nèi)容以某種形式分割成（key，value）的形式，傳遞給map（）函數(shù)處理[6]。

第一次分割Hadoop默認是以64M為大小將海量數(shù)據(jù)切分成許多小InputSplit；第二次分割Hadoop默認有按行分割，按制表符分割等規(guī)則分割函數(shù)。

可以看到，上面這些默認分割都無法滿足XML屬性多變，可擴展的格式要求。這里假設(shè)已知XML內(nèi)容結(jié)構(gòu)，那么可以把海量XML按照每個小部分切分，切分完整后，每個小部分仍然是獨立的XML。如對于歷史天氣的一個XML，根結(jié)點下有年月日層次關(guān)系，日結(jié)點下有天氣的屬性內(nèi)容。那么我們可以以日結(jié)點為單位切分，切分的每塊key為日結(jié)點偏移量，value為整個日結(jié)點的XML內(nèi)容。

至于具體切分方法，本文自定義了一個分割類，該類只需指定開始內(nèi)容與結(jié)束內(nèi)容，運行后，它能夠返回開始和結(jié)束之間內(nèi)容作為value和它的偏移量作為key。

2.3 XML的索引查詢方法

Hadoop作為大數(shù)據(jù)處理工具，由于采用的是流式處理方案，因此是沒有索引機制的，即只要給定的MapReduce開始運行，就會默認掃描處理整個輸入目錄或文件，使大XML文件的查詢效率極低。

針對上述問題，本文設(shè)計了索引機制，主要利用了Hadoop的HDFS文件系統(tǒng)支持隨機讀寫的特性，即知道文件偏移量（offset），能夠快速略過前面內(nèi)容，直接跳到指定偏移量位置開始操作[7]。

3 Hadoop下處理XML具體實現(xiàn)

對于海量XML處理，主要有如下幾步：

（1）上傳待處理XML文件，對待處理XML運行MapReduce框架建立索引；

（2）查詢時，先用MapReduce框架查詢索引，取出待查詢的偏移量；

（3）根據(jù)偏移量，直接讀取文件指定部分；

3.1 建立海量XML索引

上傳步驟僅僅用Hadoop命令即可完成，這里就不在贅述了，建立索引時，主要通過加入XML分割函數(shù)，來把海量數(shù)據(jù)切分成指定小段XML，再交給map（）函數(shù)處理。整體步驟如下：

（1）在MapReduce程序中設(shè)置自定義的切割函數(shù)。

（2）針對待建索引的字段配置XmlInputFormat類的屬性，即指定小片段XML數(shù)據(jù)的開頭標記和結(jié)尾標記。

（3）map（）函數(shù)接收（key，value），對value即小段XML進行SAX解析，取出我們待建立索引的內(nèi)容，將取出的數(shù)值與偏移量分別作為key和value傳遞給reduce（）函數(shù)。

（4）reduce（）函數(shù)把每個偏移量用逗號分隔，寫在一行中，與索引內(nèi)容一起作為輸出。

3.2 查詢索引和讀取偏移量位置內(nèi)容

查詢索引就比較簡單了，因為索引是結(jié)構(gòu)化數(shù)據(jù)，按行排列，因為面對海量數(shù)據(jù)，索引文件可能依舊很大，所以可以通過Hadoop程序并行查詢索引，加快查詢，步驟如下：

（1）MapReduce程序中設(shè)置按行分割。

（2）TextInputFormat把key為偏移量，value為整行內(nèi)容的鍵值對傳遞給map（）函數(shù)。

（3）map（）中截取value第一個逗號以前的內(nèi)容，對比待查詢內(nèi)容，若相同，這把value值即整行內(nèi)容傳遞給reduce（）函數(shù)。

（4）reduce（）函數(shù)中處理第一個逗號以后的內(nèi)容，得到一系列待查詢的偏移量，利用Hadoop的FSDataInputStream類方法，定位讀取指定內(nèi)容后，作為結(jié)果輸出。

4 實驗結(jié)果及分析

4.1 實驗環(huán)境

硬件環(huán)境：3臺HP電腦構(gòu)成的Hadoop集群，每個節(jié)點均為雙核Intel i3 CPU，頻率為3.3GHZ，2GB內(nèi)存，60GB硬盤，網(wǎng)絡(luò)環(huán)境是百兆以太網(wǎng)。

軟件環(huán)境：操作系統(tǒng)均為32位 Linux Fedora 14（內(nèi)核版本為2.6.35），JDK版本為1.6，Hadoop版本為0.202。

3臺電腦均參與運算，其中一臺兼做主節(jié)點。

數(shù)據(jù)集由XMark中XML生成工具產(chǎn)生，其中XMark是針對XML查詢檢索性能測量的一套工具，實驗結(jié)果均是5組后測量時間取的平均值。

4.2 實驗結(jié)果

（1）上傳海量文件。由圖4看到相比傳統(tǒng)的XML文件直接交給操作系統(tǒng)管理，Hadoop首先要上傳海量數(shù)據(jù)至HDFS，由于HDFS是分布式冗余管理文件，所以上傳還是比較耗時的。

圖4 文件上傳至HDFS耗時

（2）查詢時間。從圖5時間對比（不包含建立索引時間）可以看出，索引查詢在小于500MB時，查詢優(yōu)勢還不太明顯，當大于500MB后，查詢時間依舊能維持在20 s左右，說明，索引查詢能很好的提高查詢速度，這點在XML數(shù)據(jù)量較大的查詢上顯得尤為突出。

（3）考慮建立索引時間。若考慮建立索引時間，且只查詢一次，那么索引查詢的優(yōu)勢將不存在了，但是考慮到索引能夠重復利用，且查詢也不可能是一次性的。為了分析索引優(yōu)勢，我們列出如下等式：

非索引查詢時間*n=索引查詢時間*n+建立索引時間

我們解出n畫出圖6，這里n代表著查詢n次，索引查詢的優(yōu)勢時間彌補建立索引時間。當查詢次數(shù)小于n次，非索引查詢總時間較短；當查詢次數(shù)大于n次，索引查詢總時間會較短，且優(yōu)勢在后面會越來越明顯。

從圖6可以看出，在XML數(shù)據(jù)比較大的情況，查詢兩次，即可抵消建立索引的時間開銷。

5 結(jié)束語

本文從實際需求出發(fā)，對比傳統(tǒng)方案的缺點，提出了一種更適合海量XML數(shù)據(jù)處理的解決方案。經(jīng)小型模擬實驗，此方案能夠很好的解決某些海量XML存儲與查詢問題，同時具備良好的性能，在大型hadoop集群上，相信會有更好的表現(xiàn)。當然，該解決方案現(xiàn)階段只適合一些已知的，結(jié)構(gòu)簡單的海量XML，以后的研究目標將把XML樹編碼加入到索引用以支持更通用的XML結(jié)構(gòu)查詢。同時，在建立索引方面，目前正在研究如何在上傳時建立索引，若成功，則可大大減少索引查詢的總共耗時。

參考文獻：

[1]Yang，M.J.XML學習指南[M].北京：機械工業(yè)出版社，2008.

[2]Tom White.Hadoop權(quán)威指南（2版）[M].周敏奇.北京：清華大學出版社，2011.

[3]Tom White. Hadoop The Definitive Guide 2nd Edition [M].Oreilly，2010.

[4]Apache. Welcome to Apache Hadoop[OL].2011.http：//hadoop.apache.org/.

[5]劉鵬.實戰(zhàn)Hadoop—開啟通向有云計算的捷徑[M].北京：電子工業(yè)出版社，2011.

[6]劉鵬.云計算[M].北京：電子工業(yè)出版社，2011.

[7]董長春.基于Hadoop的倒排索引技術(shù)的研究[D].沈陽：遼寧大學，2011.

[8]付志超.基于Map/Reduce的分布式智能搜索引擎框架研究[D].北京：北京郵電大學，2008.

作者簡介：危奇（1989-），男，湖北武漢人，工學碩士，研究方向：云計算；萬立（1977-），男，湖北武漢人，副教授，博士，研究方向：神經(jīng)網(wǎng)絡(luò)。

作者單位：武漢紡織大學數(shù)學與計算機學院，武漢 430073

基金項目：國家自然科學基金項目號11271295，湖北省教育廳科研項目D20131602。