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

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

中圖分類號：TP311.52

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

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

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

1 相關(guān)研究

迄今為止，對于XML的存儲以及查詢的優(yōu)化算法大部分都是在樹結(jié)構(gòu)的基礎(chǔ)上提出的。這些算法在單機(jī)上實(shí)現(xiàn)都能表現(xiàn)出不錯(cuò)的效果，但是，一旦把他們發(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整個(gè)以樹的形式讀入內(nèi)存，然后查找。優(yōu)點(diǎn)是可隨機(jī)多次查找，支持XPATH路徑查找，支持讀寫操作。缺點(diǎn)是需要加載整個(gè)XML，資源耗費(fèi)大。

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

1.2 海量XML存儲與查詢

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

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

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

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

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

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

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

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

2 海量XML文件處理方案

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

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

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

（2）每個(gè)inputSplit將在分布式并行的環(huán)境下，使用用戶指定方法分割每個(gè)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ù)以上介紹，文件實(shí)際上經(jīng)歷了兩個(gè)分割，第一次分割是將海量文件分割成許多的inputSplit，每個(gè)inpuSplit對應(yīng)于一次Map任務(wù)，多個(gè)Map任務(wù)之間并行處理。第二次分割是針對于每一個(gè)inputSplit的具體內(nèi)容，把內(nèi)容以某種形式分割成（key，value）的形式，傳遞給map（）函數(shù)處理[6]。

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

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

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

2.3 XML的索引查詢方法

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

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

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

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

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

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

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

3.1 建立海量XML索引

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

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

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

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

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

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

查詢索引就比較簡單了，因?yàn)樗饕墙Y(jié)構(gòu)化數(shù)據(jù)，按行排列，因?yàn)槊鎸Ａ繑?shù)據(jù)，索引文件可能依舊很大，所以可以通過Hadoop程序并行查詢索引，加快查詢，步驟如下：

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

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

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

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

4 實(shí)驗(yàn)結(jié)果及分析

4.1 實(shí)驗(yàn)環(huán)境

硬件環(huán)境：3臺HP電腦構(gòu)成的Hadoop集群，每個(gè)節(jié)點(diǎn)均為雙核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臺電腦均參與運(yùn)算，其中一臺兼做主節(jié)點(diǎn)。

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

4.2 實(shí)驗(yàn)結(jié)果

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

圖4 文件上傳至HDFS耗時(shí)

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

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

非索引查詢時(shí)間*n=索引查詢時(shí)間*n+建立索引時(shí)間

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

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

5 結(jié)束語

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

參考文獻(xiàn)：

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

[2]Tom White.Hadoop權(quán)威指南（2版）[M].周敏奇.北京：清華大學(xué)出版社，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]劉鵬.實(shí)戰(zhàn)Hadoop—開啟通向有云計(jì)算的捷徑[M].北京：電子工業(yè)出版社，2011.

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

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

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

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

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

基金項(xiàng)目：國家自然科學(xué)基金項(xiàng)目號11271295，湖北省教育廳科研項(xiàng)目D20131602。