李春潔， 閆瑞峰， 王 超， 周 虹，陰麗瑩

(1.佳木斯大學(xué)信息電子技術(shù)學(xué)院，黑龍江 佳木斯 154007;2.哈爾濱軸承集團計算機中心，黑龍江 哈爾濱 150036)

0 引言

Web按其所蘊涵信息的“深度”可以分為Surface Web和Deep Web.通過超鏈接訪問的靜態(tài)網(wǎng)頁、文件等稱為Surface Web;需要通過動態(tài)網(wǎng)頁技術(shù)訪問而不能直接通過超鏈接訪問的資源稱為Deep Web.Deep Web是網(wǎng)絡(luò)新信息增長的最大來源.與Surface Web相比，Deep Web中的Web數(shù)據(jù)庫不僅數(shù)量眾多，而且其信息資源可以覆蓋現(xiàn)實世界的整個領(lǐng)域.如此龐大的信息資源，如果按現(xiàn)實世界的領(lǐng)域?qū)ζ浞诸?，可以分為商業(yè)與經(jīng)濟、計算機與互聯(lián)網(wǎng)、新聞媒體、娛樂等十幾個，而這只是宏觀的分類.對Deep Web中的資源進行訪問需要注冊或者滿足某些限定的條件，通過填寫表單的方式對后臺在線數(shù)據(jù)庫進行查詢，由此得到動態(tài)頁面.除此之外，Deep Web還可以訪問非網(wǎng)頁文件，如圖片、PDF 和 Word 文檔等[1].

隨著時代的發(fā)展，網(wǎng)絡(luò)數(shù)據(jù)庫信息量以及網(wǎng)絡(luò)用戶增長迅速，用戶在訪問Web時常出現(xiàn)訪問延遲的現(xiàn)象.目前核心的解決方法是緩存技術(shù)和預(yù)取技術(shù)[2]，或者兩種技術(shù)相結(jié)合[3].現(xiàn)有的預(yù)取技術(shù)和相應(yīng)的緩存管理及替換策略大多只適用于Surface Web，減少訪問延遲多是應(yīng)用于Surface Web訪問的.由于Deep Web已經(jīng)占據(jù)主要地位，所以緩解Deep Web訪問延遲對整個網(wǎng)絡(luò)加快訪問速度有重要意義.

1 Deep Web緩存與預(yù)取

1.1 預(yù)取技術(shù)和緩存替換

用戶發(fā)起兩次Web請求的時間間隔稱之為用戶瀏覽時間.預(yù)取技術(shù)是指在用戶瀏覽時間內(nèi)就把用戶可能要訪問的頁面提前從服務(wù)器取回.當(dāng)用戶發(fā)出Web請求時，若要訪問的頁面已經(jīng)預(yù)取回且已經(jīng)存在于本地緩存中，此時能在請求的第一時間立即獲取，從而減少了用戶訪問請求后的等待時間.該技術(shù)充分利用了I/O系統(tǒng)的空閑時間，當(dāng)用戶訪問時可以減少網(wǎng)絡(luò)延遲.預(yù)取技術(shù)好壞主要是靠準(zhǔn)確率和查全率兩個性能指標(biāo)來衡量[4－5].

若在Deep Web中實施預(yù)取技術(shù)，以達到減緩訪問延遲的目的.預(yù)取回的語義緩存項存放在緩存中，當(dāng)緩存達到額定數(shù)量時，需要對緩存中的語義緩存項進行替換更新[6].為了使用戶得到準(zhǔn)確的預(yù)取結(jié)果，緩存替換策略就顯得尤為重要[7].

1.2 Deep Web預(yù)取模型與緩存

Deep Web數(shù)據(jù)集成系統(tǒng)預(yù)取體系結(jié)構(gòu)包括查詢管理、預(yù)取、Deep Web數(shù)據(jù)集成、緩存一致性管理、存儲管理、緩存替換管理等模塊，體系結(jié)構(gòu)如圖1所示.

其中查詢管理模塊的功能是用來進行查詢匹配，得到不同的匹配類型.針對不同的匹配類型對該查詢進行處理，將結(jié)果返回給用戶，并進行緩存項訪問量統(tǒng)計.

預(yù)取模塊采用多項式回歸預(yù)取技術(shù)，對緩存中各語義緩存項的訪問概率進行預(yù)測，根據(jù)預(yù)取閾值、預(yù)取標(biāo)志位和緩存一致性效時間來生成預(yù)取隊列，得到的預(yù)取結(jié)果集和語義緩存項將在外緩存有效數(shù)據(jù)存儲區(qū)和內(nèi)緩存有效語義緩存區(qū)中保存.

Deep Web數(shù)據(jù)集成模塊的功能是滿足用戶查詢需要，對同一領(lǐng)域的多個Web數(shù)據(jù)庫訪問和訪問結(jié)果完成集成，最后將查詢結(jié)果合并去重，在本地存儲.

圖1 Deep Web數(shù)據(jù)集成系統(tǒng)預(yù)取體系結(jié)構(gòu)

一致性管理主要功能是判斷語義緩存項及其對應(yīng)結(jié)果集是否有效，如超出有效期范圍，則需要訪問服務(wù)器重新獲得最新數(shù)據(jù).

2 基于Deep Web的緩存替換策略

2.1 緩存的位置

緩存的位置可以是Web瀏覽器，服務(wù)器或代理服務(wù)器[8].在代理服務(wù)器上實現(xiàn)的緩存機制稱為代理緩存[9].除了可以減少用戶訪問延遲之外，代理緩存還具有分析用戶的訪問模式、提高Web服務(wù)的健壯性、減輕服務(wù)器的負(fù)載、減少網(wǎng)絡(luò)流量等特點.因此代理服務(wù)器緩存是較理想的.

2.2 存儲管理

增加預(yù)取模塊的Deep Web的數(shù)據(jù)集成系統(tǒng)，將存儲區(qū)分為內(nèi)緩存區(qū)和外緩存區(qū)兩部分.

語義緩存項定義為{K，P，T，Z}i，其中 K 為用戶提交的查詢關(guān)鍵字集合，P為訪問概率預(yù)測值，T為該查詢語句有效期，Z為查詢語句是否被預(yù)取.在內(nèi)緩存中存儲最近N個周期的訪問頻率pij(j=1～N)，及其在下一周期的訪問概率預(yù)測值POP.

將預(yù)取語義緩存描述項存儲于內(nèi)緩存中，并將該區(qū)域設(shè)定為有效語義緩存區(qū);在外緩存中，有效語義緩存項的結(jié)果集在存儲部分設(shè)定為有效數(shù)據(jù)區(qū)，存儲臨時語義緩存項及對應(yīng)結(jié)果集的外緩存部分設(shè)定為臨時數(shù)據(jù)區(qū)，實際上在臨時數(shù)據(jù)區(qū)存儲的是直接訪問Deep Web獲得的查詢結(jié)果，根據(jù)緩存替換策略將內(nèi)緩存未過期的語義緩存項及其對應(yīng)結(jié)果集替換出來.

2.3 存儲管理

增加預(yù)取模塊的Deep Web的數(shù)據(jù)集成系統(tǒng)，其存儲區(qū)由內(nèi)緩存區(qū)和外緩存區(qū)兩部分組成.隨著用戶訪問Deep Web的時間和訪問量的增加，有限的內(nèi)緩存和外緩存存儲空間會達到額定值.當(dāng)產(chǎn)生新的語義緩存項時需依據(jù)替換策略替換出一些數(shù)據(jù)，保證訪問頻率高的語義緩存項及其相關(guān)數(shù)據(jù)保留在緩存中.

根據(jù)內(nèi)、外緩存的特點，對內(nèi)外緩存分別采取不同的緩存替換原則.內(nèi)緩存替換的基本思想是在新的周期，根據(jù)預(yù)取閾值α及有效期標(biāo)志T的值來進行緩存替換;外緩存替換的基本思想在用戶訪問Deep Web獲得新的查詢數(shù)據(jù)時，根據(jù)語義緩存項Pop和有效期標(biāo)志T的值進行替換.

2.4 緩存替換策略

增加預(yù)取模塊的Deep Web的數(shù)據(jù)集成系統(tǒng)，采用多項式回歸預(yù)測模型策略，對保存在內(nèi)緩存中的各語義緩存項預(yù)測訪問概率.根據(jù)內(nèi)緩存替換策略的基本思想，新周期到來時更新內(nèi)緩存中的有效語義緩存存儲區(qū)存儲的各語義緩存項的POP值.POP小于閾值α?xí)r，如果T在有效期內(nèi)，則該緩存項及其結(jié)果集移動至臨時數(shù)據(jù)存儲區(qū);如果T已超出有效期，則刪除該緩存項及其對應(yīng)的結(jié)果集.

外緩存的臨時語義緩存區(qū)，用戶訪問 Deep Web獲得新的查詢數(shù)據(jù)時，根據(jù)外緩存替換的基本思想，若臨時語義緩存區(qū)已滿，則替換POPmin，替換超出有效期T的語義緩存項及對應(yīng)結(jié)果集.

3 結(jié)束語

目前研究的預(yù)取技術(shù)中的緩存管理及緩存替換多是針對Surface Web，而且存在一些缺陷，例如對網(wǎng)頁的大小和獲取網(wǎng)頁的延遲等因素沒有考慮，當(dāng)換入緩存中的文檔副本較大時，可能會替換出多個較小的文檔副本，影響緩存的命中率.經(jīng)過實驗測試發(fā)現(xiàn)，Deep Web數(shù)據(jù)集成系統(tǒng)未加入預(yù)取技術(shù)，和在代理服務(wù)器端采用多項式回歸預(yù)取技術(shù)，且根據(jù)本文提出的存儲管理方案進行管理，在緩存數(shù)量為100條時，查詢響應(yīng)時間最高降低比率為38.23%，最低降低比率為27.32%，預(yù)取準(zhǔn)確率為44%;緩存數(shù)量為450條時，用戶的查詢響應(yīng)時間達到最低，查詢響應(yīng)時間最高降低比率為40.33%，最低降低比率為28.12%，預(yù)取準(zhǔn)確率達到了62%.由此可見對緩存的管理符合Deep Web的特點，原理簡單清晰、易于實現(xiàn)，明顯提高用戶訪問的速度.

[1]劉偉，孟小峰，孟衛(wèi)一.Deep Web數(shù)據(jù)集成研究綜述[J].計算機學(xué)報.2007，9(30):1475 －1489.

[2]Xu Huanqing，Wang Yongcheng.A Web Pre－fetching Model Based on Analyzing User Access Pattern[J].Journal of Soft ware.2003，14(6):1142 －1147.

[3]Shi L，Han Y，Ding X，et al.An SPN Based Integrated Model for Web Prefetching and Caching[J].Journal of Computer Science and Technology.2006，21(4):482－489.

[4]Christos B.Predictive Prefetching on the Web and Its Potential Impact in the Wide Area[J].World Wide Web .2004，7(2):143－179.

[5]Shi Lei，Han Yingjie，Ding Xiaoguang，et al.An SPN －based Integrated Model for Web Prefetching and Caching[J].Journal of Computer Science and Technology.2006，21(4):482 －489.

[6]石磊，孟彩霞，韓英杰.基于預(yù)測的Web緩存替換策略[J].計算機應(yīng)用.2007，27(8):1842 －1845.

[7]SHIL，DNG XG，WEIL，etal.An Adaptive PPM Prediction Model[J].Journal of Computational Information Systems.2006，2(2):633－638.

[8]尹挺然，王珍娥，周頔.基于主動網(wǎng)絡(luò)的最佳緩存位置計算[J].科學(xué)技術(shù)與工程.2007，21(7):5688－5960.

[9]Domenech J，Gil J A，Sahuquillo J，et al.Web Prefetching Performance Metrics:A Survey[J].Performance Evaluation.2006，63(9):988－1004.