基于多屬性的海量Web數據關聯存儲及檢索系統

羅 芳，李春花，周 可，黃永峰，廖正霜

(1.華中科技大學計算機科學與技術學院，湖北 武漢 430074;2.清華大學電子工程系，北京 100084)

基于多屬性的海量Web數據關聯存儲及檢索系統

羅 芳1，李春花1，周 可1，黃永峰2，廖正霜1

(1.華中科技大學計算機科學與技術學院，湖北 武漢 430074;2.清華大學電子工程系，北京 100084)

傳統的Web數據檢索一般采用全文檢索方法，該方法具有很好的靈活性，但輿情分析往往需要獲得相關的網頁屬性及統計信息。針對傳統的Web檢索方法無法滿足上述需求，基于Hadoop平臺設計并實現了一種基于多屬性的海量Web數據的關聯存儲及檢索系統，為輿情分析提供基礎檢索與統計服務。主要實現HDFS上基于屬性的網頁數據的分類和聚類存儲，解決小文件存儲同時提高數據訪問吞吐量；建立原始網頁數據與屬性數據之間的關聯映射；基于HBase的已有索引機制，結合分布式本地索引機制解決基于HBase的動態屬性多條件選擇查詢的輔助索引問題。

分類存儲；多條件選擇查詢；關聯映射；輔助索引

1 引言

海量Web數據具有非結構化、更新速度快、數據類型多樣化等特點，對數據管理系統提出了新的挑戰。分布式存儲計算環境可以有效地利用集群的資源為海量數據提供分布式存儲和計算支持，同時也帶來了許多技術上的挑戰。

Hadoop是典型的分布式存儲計算平臺，其中HDFS(Hadoop Distributed File System)[1]是分布式文件系統，能夠提供高吞吐量的數據訪問，具有良好的擴展性和數據容錯性，滿足大規模數據處理需求，可用于海量Web數據的存儲。由于HDFS適合于存儲超大數據文件(幾百MB、GB甚至TB)，不適合將單個的Web網頁數據直接保存到單個文件，因此需要對Web網頁數據進行合并存儲。為提高相關性網頁數據讀取的吞吐量，可以利用Web網頁數據之間的屬性相關性，對Web網頁進行分類歸并存儲。然而，由于HDFS不支持隨機寫操作，故只能采用追加寫方式，保證單個文件的數據整體相關性。

HBase[2]是Hadoop的一個面向列的分布式存儲系統，適合于海量結構化數據的存儲，也支持非結構化數據的存儲，也具有很好的可擴展性和容錯性。原始的網頁文件中一般存儲大量的屬性描述數據，在輿情分析系統中，如何有效地獲取、組織、管理和檢索這些屬性數據是輿情分析研究的基礎。為方便屬性數據的存儲和擴展，我們采用HBase作為屬性數據的存儲支持。由于異構源(如門戶網站、BBS、博客、微博)的網頁信息具有不同的屬性數據，屬性數據的值域又分為離散型數據域(如新聞來源)和連續型數據域(如評論數)，因此需要設計滿足不同需求的屬性數據的存儲模型，實現屬性數據和原始網頁數據的關聯存儲映射。該映射機制能夠對異構數據進行雙向定位訪問，同時減少分布式環境下的網絡開銷。

由于HBase僅支持主索引結構，無法滿足多條件選擇查詢需求。為此需要設計滿足該查詢需求的索引機制，該索引應具有較好的動態擴展性、可維護性和較高的檢索性能。由于HBase的數據存儲模型的改變，傳統的關系型數據管理系統中的輔助索引技術無法被簡單地遷移過來，因此，基于HBase屬性數據管理系統需解決以下幾個方面的問題：輔助索引應充分利用分布式計算環境的并行計算能力來提高數據分布式檢索效率；分布式環境下屬性數據的添加、刪除、修改、遷移等可以較方便地進行索引維護；保證高并發查詢效率的同時需要盡量減少網絡查詢開銷；針對輿情分析需求，該索引機制應該具有較高的數據統計能力。

本文的第2節將介紹相關的研究工作；第3節詳細描述Hadoop平臺下實現Web屬性數據關聯存儲與檢索的相關技術，包括Web數據的分類聚類存儲算法，屬性數據和原始網頁數據的關聯映射和定位技術，HBase輔助索引機制的構建、維護和檢索算法，以及整個系統實現的主要流程；第4節中給出了相關的實驗結果；最后對本文進行歸納總結。

2 相關工作

2.1 小文件合并存儲和定位技術

對于小文件問題，Hadoop自身提供了三種解決方案[1]：Hadoop Archive、Sequence File和CombineFileInputFormat。這三種方法不能自動刪除原始小文件，且不能將動態增加的數據合并到已歸類的文件。WebGIS[3]結合數據的相關特征，將相鄰地理位置的小文件合并成大文件，把小于16 MB的文件作為小文件進行合并處理，將其合并成64 MB的數據塊并構建索引。BlueSky[4]主要基于HDFS存放教學PPT文件、視頻文件及一些文件快照，此方法的合并準則十分簡單，要求合并的文件具有明確相關性和本地性。但是，考慮網頁數據具有海量且關聯不確定性特點，不應將合并后的文件的大小限制在較小范圍；同時，需要采用相關的聚類算法來確定網頁之間的關聯性，實現合并存儲。

2.2 網頁數據的分類聚類算法

由于輿情分析[5]中網頁的主題和時間是非常重要的查詢屬性，本文實現了對網頁數據進行基于主題和時間的分類。在文件合并的過程中考慮文件的相關性，采用相關的聚類算法對網頁文件進行分類合并存儲，可以有效提高網頁數據訪問的吞吐量。

在對網頁數據進行基于屬性的歸并存儲過程中，需要對網頁進行預處理，獲得網頁的文本向量表示。常用的文本表示方法有：布爾模型、向量空間模型、語義模型和生成模型LDA(Latent Dirichlet Allocation)。實現主題分類的過程中，主要采用經典的SVM(Support Vector Machine)模型[6]。利用聚類算法對文本進行聚類存儲。有許多經典的聚類算法[6]，如劃分聚類、層次聚類、密度聚類等?？紤]Web數據海量、動態等特點，本文采用聚類算法實現海量Web數據的合并存儲，并基于MapReduce框架實現并行化。

2.3 云數據管理的輔助索引機制

云環境下輔助索引機制主要分為集中式和分布式兩種方案[7]。集中式方案中，被索引字段上的所有值被全局排序并集中管理。檢索過程中首先在全局排序的索引結構中找到符合的索引項；然后定位到對應的數據節點；再根據該節點的聚集索引定位到完整記錄。該方案沒有充分利用集群的整體計算能力，限制了查詢的性能。分布式索引方案在各數據節點獨立建立各自管理的局部數據索引，但對于任何一個檢索請求，都會分別發送到各個數據節點進行并發查詢，在高并發查詢環境下顯然增加了無用的數據節點?；诜制粓D的索引方案[8]為數據檢索提供了較好的支持，但針對不斷更新的海量數據，該索引機制具有一定的使用限制。

3 基于屬性的Web數據關聯存儲

3.1 原始網頁數據的歸并存儲

3.1.1 網頁原始數據的關聯存儲過程

首先基于主題和時間等屬性對原始網頁數據進行分類存儲，下面以如表1所示的新浪新聞信息網頁為例進行說明。

Table 1 Partial Sina-news instances

以時間和主題為劃分標準，對原始網頁數據進行分類，其中主題列表基于《中文新聞信息分類標準及代碼》[5]構建，得到如圖1所示的網頁數據存儲結構。其中InfoWebSet是基于網頁的其他屬性(網頁來源、發布媒體、評論數、信息關鍵字)，通過基于MapReduce的聚類算法對同一分類下的網頁數據進行聚類存儲。聚類屬性的選擇主要是為了滿足輿情統計需求[9]。

Figure 1 Organization structure of webpage based on HDFS圖1 網頁數據在HDFS中的組織結構

3.1.2 網頁數據歸并存儲算法

(1)基于主題的網頁數據分類算法。

Figure 2 Parallelization of web page associated-storage based on MapReduce model圖2 網頁歸并存儲的MapReduce并行化實現

由于網頁數據源的異構性，需要采用相關的分類算法對網頁進行主題分類。本文主要利用基于貝葉斯理論的SVM模型對網頁數據進行分類，實現過程中針對不同的異構源(新聞網站、博客、BBS、微博)，首先選取新浪新聞網站、新浪博客、天涯論壇和新浪微博已確定分類的數據作為訓練集，獲取SVM分類器；以其他動態增長的網頁數據作為樣本，采用SVM模型對樣本數據進行分類，從而確定網頁數據的存儲路徑。該過程主要通過Map函數完成。Map函數實現的主要工作如下：

① 根據待爬的URL獲取原始網頁Page(i)。

② 對原始網頁進行預處理獲得特征向量。

③ 利用SVM訓練模型得到網頁分類，獲取存儲目錄Dir_path(j)。

④ 以Dir_path(j)為key，Page(i)作為value輸出給Reduce函數進行聚類，完成網頁數據歸并存儲。

(2)基于多屬性的網頁數據聚類算法。

本文基于K-means算法[10]對同主題下的網頁數據進行基于屬性的聚類。選擇K-means算法實現網頁數據聚類存儲具有以下優點：K-means算法復雜度低，速度快，實現簡單，滿足海量數據的聚類需求，能保證聚類效率；根據聚類目的和聚類結果將網頁數據存儲到對應的文件中，故需要使用排他型聚類算法，K-means算法滿足這種需求；可以簡單地滿足動態網頁數據的聚類需求。

聚類過程主要在Reduce函數中實現，輸入的key為文檔所屬目錄的絕對路徑，value為該路徑下的所有文檔。主要完成以下工作：

① 對每個路徑下的所有文檔進行聚類。

② 計算每個聚類中心New_center(i)與已有的K個聚類中心的距離。

③獲得與New_center(i)距離最近的聚類Old_center(j):若距離小于閾值t1，讀取Old_center(j)的存儲路徑Path(j)，將New_center(i)的所有網頁數據追加到Path(j)；否則，為該聚類在該目錄下創建新的存儲文件Path(m)，將new_center(i)的所有網頁數據追加到Path(m)中。

(3)算法實現。

上面主要闡述了采用Map/Reduce框架實現網頁數據合并存儲的主要工作。其中Map函數主要完成了對網頁數據的分類，獲得其存儲的目錄；Reduce函數主要對同分類下的網頁數據聚類，根據聚類結果將網頁數據追加存儲到對應的HDFS文件中。Map過程的偽代碼如下：

voidmap(ImmutableBytesWritableibw, Resultresult, Contextcontext)

{

Stringurl=getUrl(ibw);/*get url from HBase*

Pagepage=getWebPage(url);//download webpage

DocVectordocVector=getVector(page);

SVMersvm=getSVM();//get svm classifier

Clscid=SVM(docVecto,svm);//training by SVM

PathdirPath=getPath(cid); /*get storage path with cid*/

Context.write(new Text(dirPath), new Text(page));

}

Reduce過程的偽代碼如下：

voidreduce(TextdirPath, Iterator〈Text〉pages, Contextcontext)

{//clustering new Pages

intk=Configuration.get(“cluster_num”); /*get k number*/

intt1=Configuration.get(“cluster_distance”);

List〈Center〉centers=get_k_center(pages,k);

List〈Cluster〉clusters=kmeans_training(pages,k,centers); //get clusters byk-means

List〈ClusterCenter〉old_centers=get_oldcenter(dirPath);

FOR (Clustercluster:clusters)

{//compute cluster distance to old clusters

Centercenter=getCenter(cluster);

Centermincenter=getMin(center,old_centers);

IF (distance(center,mincenter)

{/*ifdistance

TextPathtextPath=getTextPath(mincenter,dirPath);

append(textPath,cluster); }

ELSE

{//create new cluster file and append data into it

TextPathtextPath=newTextPath(++k,dirPath);

append(textPath,cluster);/*append data to file*/}

}//endFor

/*output cluster path info to database for further retrieval*/

}

3.2 屬性數據的存儲

3.2.1 屬性數據的類型

(1)從網頁中解析獲得的屬性數據：URL、標題、發布時間、媒體來源、評論人數、參與人數、網頁正文的關鍵字(主要通過對正文、標題進行分詞、過濾無效詞等獲得)；

(2)原始網頁數據分類聚類獲得的屬性：主題，原始網頁在HDFS中的存儲路徑，原始網頁在聚類文件中的偏移量。

3.2.2 屬性數據的存儲模型

為充分利用分布式并行計算能力，采用HBase作為屬性數據的存儲支持[11]。在基于HBase固有索引機制的基礎上構建良好的分布式輔助索引機制，需要設計良好的屬性數據存儲模型[12]。表2是屬性數據在HBase中的存儲模型。

Table 2 A storage model of attributes data based on HBase

根據Web數據更新速度快和輿情分析需求，在設計屬性數據存儲模型時優先考慮時間屬性，同時考慮到異構網頁源的屬性特征不同，因此將HBase中的表名設計為SOURCE_YYYY屬性。同時，為保證索引和被索引數據的操作具有事務性，每個索引以RowKey索引單元，基于HBase存儲，且使用相同的RowKey作為其存儲的行關鍵字，保證索引與被索引的數據在同一個RegionServer上。由于網頁數據具有更新的特點，我們可充分利用HBase的時間戳機制來存儲更新。

同時，我們在數據庫中采用相關字段來存儲對應原始網頁數據的位置信息，使得該系統能夠在獲得屬性數據的同時支持查看完整的原始網頁數據。

3.3 HBase輔助索引的構建

基于HBase原有的主索引方式設計分布式本地索引。索引以RowKey為主鍵，對相同的RowKey中的屬性數據建立本地索引，構建的索引數據基于HBase存儲，且與被索引的數據共享相同的RowKey，保證在分布式環境下，當屬性數據發生遷移時，對應的索引數據也能始終遷移到相同的節點上，可減少檢索過程中的網絡開銷。同時，為了充分利用分布式節點的計算能力，我們在各個RegionServer上構建本地檢索模塊，利用本地索引，對局部時間域的數據進行并行檢索，最后將各節點返回的數據求并即得到了整體時間域的數據檢索。

表3是本文設計的屬性索引存儲模型。從中可以看出，將屬性索引和屬性數據采用無差別存儲，屬性數據采用Url列族名，屬性索引采用Index列族存儲，對相同表中相同RowKey下的屬性數據進行索引。這樣就可以利用分布式節點的計算能力對被檢索的屬性進行分布式檢索然后歸并。

Table 3 Storage model of attributes’ indexing

為了提高多條件檢索的效率，實際系統中一般采用聯合索引機制存儲索引，再采用對應的決策樹查詢算法進行本地數據檢索。針對輿情需求，被索引的屬性數據主要包括：媒體來源和檢索網頁的關鍵字。下面給出基于HBase的多屬性條件選擇查詢算法：

輸入：用戶需要查詢的屬性域{Attr1,Attr2, …,Attrn};

輸出：滿足查詢條件的網頁屬性數據對象集合。

步驟1 接收用戶輸入的屬性參數。

步驟2 根據用戶選擇的網頁源和年閾值(默認是有時間范圍的)確定所需檢索的數據表；根據時間的月/日來確定RowKey的startRowKey和endRowKey，獲取需要檢索的RegionServer，將其他查詢參數進行連接封裝到查詢請求中并發送到對應RegionServer。

步驟3 采用RegionServer自帶的類對請求進行反序列化，生成需要的請求對象，解析請求對象中包含的查詢參數。

步驟4 針對各查詢參數循環構造查詢條件，再調用Get()方法返回查詢結果。

步驟5 在RegionServer上對返回的數據進行布爾運算求交集，為了加快處理速度，存儲時對數據進行排序存儲以提高效率。

步驟6 利用交集數據循環構造查詢條件進行Get()查詢，返回最終數據給客戶端。

步驟7 客戶端對不同時間域的數據進行求交并返回、顯示對應的屬性數。

3.4 Web數據關聯存儲及檢索系統框架圖

前面主要介紹了本系統實現的關鍵技術，系統的整體框架圖如圖3所示。

Figure 3 Associated storage and retrival system framework of massive web data based on attributes圖3 基于屬性的海量Web數據關聯存儲和檢索系統框架

系統從功能上分為：存儲層、計算層和服務層。其中，存儲層主要分為對原始非結構化信息的存儲、結構化屬性信息的存儲及索引數據的存儲。計算層主要包括數據的聚類存儲模塊，屬性數據和原始網頁數據之間的關聯映射模塊，數據的檢索、結果的緩存和統計模塊，由于Web數據具有更新特點，故還建立了對應的更新模塊，主要針對更新數據進行處理。最上層則是服務層，主要對下面相關的處理模塊進行封裝。給供分析人員提供執行相關檢索和統計的API，為后期的輿情分析提供基礎服務，同時構建了一個用戶查詢界面提供功能展示服務。

4 實驗

按照以上設計思想，本文實現了基于多屬性檢索的Web信息查詢系統。由于我們的數據關聯存儲和檢索系統主要是為輿情分析提供基礎服務，主要提供了相關查詢統計和網頁獲取的API接口。圖4給出了對新浪某類新聞在2010～2012年的新聞發布數的統計結果。

Figure 4 A trend statistics of certain SinaNews topic圖4 新浪某分類新聞的走勢統計

本文還搭建了一個功能演示界面，如圖5所示。圖5中查詢設定的參數有：時間范圍參數是2010年7月1日到2013年4月1日，信息來源為新浪新聞，查詢的主題為軍事，檢索的關鍵詞為“釣魚島”，返回了相關的查詢結果，點擊可以在下方查看某新聞的內容和相關的屬性信息，右圖還給出了以時間為維度的頻率統計圖，另外下方的url還支持查看原始網頁來源。

Figure 5 Web data retrieval demo based on multi-attributes圖5 基于多屬性的Web數據檢索系統

5 結束語

本文基于Hadoop和HBase平臺，設計并實現了一種基于屬性的海量Web數據的關聯存儲和檢索系統。主要做了如下工作：對爬取的原始網頁數據采用分類聚類算法實現歸并存儲，使用HDFS作為原始網頁存儲庫。該方法使得基于屬性檢索的結果數據在原始網頁存儲庫中也具有位置相關性，能夠提高原始數據讀取的吞吐量；從原始信息網頁中抽取出屬性數據，以時間為閾值進行基于HBase的存儲，設計了相關的屬性數據存儲模型；在屬性數據和原始網頁數據之間建立關聯映射；基于屬性數據的存儲模型設計了屬性數據的索引模型，并使用分布式節點中的本地計算能力實現對多屬性的選擇查詢。最終實現了對海量Web數據的基于屬性的關聯存儲和檢索系統。該系統的相關算法設計和索引效率有待改進，結合全文檢索能力可以進一步完善整體系統的功能，這將是我們后期需要展開的工作。

[1] Apache Hadoop project[EB/OL].[2012-09-10]. http://hadoop.apache.org.

[2] Apache HBase project [EB/OL].[2012-11-25]. http://hb- ase.apache.org.

[3] Liu Xu-hui, Han Ji-zhong, Zhong Yun-qin, et al. Implementing WebGIS on Hadoop:A case study of improving small file I/O performance on HDFS[C]∥Proc of CLUSTER, 2009:1-8.

[4] Dong Bo, Qiu Jie, Zheng Qing-hua, et al. A novel approach to improving the efficiency of storing and accessing small files on Hadoop:A case study by PowerPoint files[C]∥Proc of the 2010 IEEE International Conference on Services Computing, 2010:65-72.

[5] Qian Ai-bing. A model for analyzing public opinion under the web and its implementation[J]. Information Analysis and Research, 2008(4):49-55.(in Chinese)

[6] Zhang Xue-gong. Pattern recognition[M]. 3rd ed. Beijing:Tsinghua University Press, 2010.(in Chinese)

[7] Hbase-transactional-tableindexed[EB/OL].[2002-10-26]. h-ttps://github.com/hbase-trx/hbase-transactional-tableindexed.

[8] Meng Bi-ping, Wang Teng-jiao, Li Hong-yan, et al. Regional bitmap index:A secondary index for data management in could computing environment[J]. Chinese Journal of Computers,2012,35(11):2306-2316.(in Chinese)

[9] Wang Ming-yan. Keyword and key concept extraction technique based on web page[D]. Beijing:Beijing University of Technology,2003.(in Chinese)

[10] Jiang Xiao-ping, Li Cheng-hua, Xiang Wen, et al. Parallel implementingk-means clustering algorithm using MapReduce programming mode[J]. Journal of Huazhong University of Science and Technology(Natural Science Edition),2011,39( Sup Ⅰ):120-124.(in Chinese)

[11] Yu Ge, Gu Yu, Bao Yu-bin, et al. Large scale graph data processing on cloud computing environments[J]. Chinese Journal of Computers,2011,34(10):1753-1767.(in Chinese)

[12] He Yun-feng, Yu Jun-qing, Tang Jiu-fei, et al. Video data organization and management based on MPEG-7[J]. Journal of Wuhan University(Natural Science Edition),2010, 56(6):711-716.(in Chinese)

附中文參考文獻:

[5] 錢愛兵.基于主題的網絡輿情分析模型及其實現[J]. 情報分析與研究, 2008(4):49-55.

[6] 張學工.模式識別[M].第3版. 北京：清華大學出版社,2010.

[8] 孟必平,王騰蛟,李紅燕,等. 分片位圖索引:一種使用于云數據管理的輔助索引機制[J]. 計算機學報, 2012,35(11):2306-2316.

[9] 王明燕,基于WEB頁面的關鍵詞與關鍵概念提取技術[D]. 北京:北京工業大學, 2003.

[10] 江小平,李成華,向文,等.k-means聚類算法的MapReduce并行化實現[J]. 華中科技大學學報(自然科學版),2011，(Sup Ⅰ)39:120-124.

[11] 于戈,谷峪,鮑玉斌,等. 云計算環境下的大規模圖數據處理技術[J].計算機學報,2011,34(10):1753-1767.

[12] 何云峰,于俊清,唐九飛,等. 基于MPEG-7的視頻數據組織與管理[J]. 武漢大學學報(理學版) ,2010,56(6):711-716.

LUO Fang,born in 1989,MS candidate,her research interests include cloud storage, and big data.

An associated storage and retrieval system of massive Web data based on multi-attributes

LUO Fang1,LI Chun-hua1,ZHOU Ke1,HUANG Yong-feng2,LIAO Zheng-shuang1
(1.School of Computer Science and Technology,Huazhong University of Science and Technology,Wuhan 430074;2.Department of Electronic Engineering,Tsinghua University,Beijing 100084,China)

Traditional Web Retrievals commonly use the full-text search method which has good flexibility. However, as the analysis of public opinion usually needs relative information of web attributes and statistics, the traditional retrieval method can not satisfy it well. An associated storage and retrieval system based on the Hadoop platform is designed and implemented, which can offer good basic service for the analysis of public opinion. Firstly, the associated storage of web data based on HDFS is realized by machine learning. Secondly, the problem of small files storage together with the access efficiency of associated data is solved. Thirdly, the mapping between original web data and the extracted attributes is established. Finally, the retrieval of dynamic multiple attributes based on the existed indexing on HBase and the distributed local indexing are realized.

category storage;multi-conditions selectable query;associated mapping;secondary indexing

2013-06-08;

2013-10-20

國家863計劃資助項目(2012AA011004)；清華大學自主科研項目基金(20111081023)

1007-130X(2014)03-0404-07

TP391.3

A

10.3969/j.issn.1007-130X.2014.03.005

羅芳(1989-),女,安徽郎溪人，碩士生，研究方向為云存儲和大數據。E-mail:fsailuo@gmail.com

通信地址：430074 湖北省武漢市華中科技大學計算機科學與技術學院

Address:School of Computer Science and Technology,Huazhong University of Science and Technology,Wuhan 430074,Hubei,P.R.China