基于多項(xiàng)式回歸預(yù)取技術(shù)緩存管理的研究①

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

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

0 引言

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

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

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

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

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

若在Deep Web中實(shí)施預(yù)取技術(shù)，以達(dá)到減緩訪問(wèn)延遲的目的.預(yù)取回的語(yǔ)義緩存項(xiàng)存放在緩存中，當(dāng)緩存達(dá)到額定數(shù)量時(shí)，需要對(duì)緩存中的語(yǔ)義緩存項(xiàng)進(jìn)行替換更新[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ù)集成、緩存一致性管理、存儲(chǔ)管理、緩存替換管理等模塊，體系結(jié)構(gòu)如圖1所示.

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

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

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

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

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

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

2.1 緩存的位置

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

2.2 存儲(chǔ)管理

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

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

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

2.3 存儲(chǔ)管理

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

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

2.4 緩存替換策略

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

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

3 結(jié)束語(yǔ)

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

[1]劉偉，孟小峰，孟衛(wèi)一.Deep Web數(shù)據(jù)集成研究綜述[J].計(jì)算機(jī)學(xué)報(bào).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ù)測(cè)的Web緩存替換策略[J].計(jì)算機(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]尹挺然，王珍娥，周頔.基于主動(dòng)網(wǎng)絡(luò)的最佳緩存位置計(jì)算[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.