一種基于對象屬性的Web緩存替換策略

收稿日期：2014－02－20

基金項目：國家高技術(shù)研究發(fā)展計劃(863)(2011AA010705)；國家重點基礎(chǔ)研究發(fā)展計劃(973)(2011CB302605)；國家自然科學(xué)基金(61173145， 60203021)。

作者簡介：李喬(1984-)，男，福建建甌人，博士研究生，主要研究方向：網(wǎng)絡(luò)安全、分布式處理;

何慧(1974-)，女，吉林省吉林市人，博士，副教授，主要研究方向：網(wǎng)絡(luò)計算、網(wǎng)絡(luò)安全;

方濱興(1960-)，男，江西萬年人，博士，教授，博士生導(dǎo)師，中國工程院院士，主要研究方向：網(wǎng)絡(luò)與信息安全理論與技術(shù)、并行計算、拓?fù)浒l(fā)現(xiàn)等。

摘要：為了降低訪問時延，提升用戶體驗，當(dāng)前網(wǎng)絡(luò)交互性能改進(jìn)的主要手段包括緩存技術(shù)與預(yù)取技術(shù)。當(dāng)前的緩存替換機制主要考慮對象的訪問時間與訪問頻度，然而Web對象本身存在語義性。本文首先對實際Web數(shù)據(jù)訪問情況進(jìn)行分析，發(fā)現(xiàn)訪問間隔的變化率對于命中率的影響具有更高的準(zhǔn)確性，進(jìn)而提出一種基于對象屬性的緩存替換策略，該策略通過統(tǒng)計近期緩存對象的平均訪問間隔，并結(jié)合該對象的標(biāo)簽屬性作為對象在緩存中的價值。實驗結(jié)果表明該策略比基于Aging的緩存策略和基于協(xié)作式中心化決策緩存策略提升7%-10%的命中率。

關(guān)鍵詞：Web緩存； 緩存替換； 命中率

中圖分類號：TP393文獻(xiàn)標(biāo)識碼：A文章編號：2095-2163（2014）03-0001-05

A Web Cache Replacement Policy based on Object Property

LI Qiao1， HE Hui1， FANG Binxing1，2

(1 Research Center of Network and Information Security， Harbin Institute of Technology， Harbin 150001， China;

2 Beijing University of Posts and Telecommunication， Beijing 100876， China)

Abstract：In order to decrease the access delay and improve the user experience， the current schemes include cache and prefetching technology. The current cache replacement schemes only consider the arrive time and frequency. The research finds the access interval change rate that is more valuable in predicting the new objects arrival through analyzing the real network logs. Considering this new metric， the paper proposes a novel cache replacement algorithm based on object property. Using this novel method， the cache can achieve higher byte hit ratio. The experiments result shows that the proposed method improves 7% to 10% hit rate than the ABC(AgebasedCooperativeCaching) and (APDR)contentAware Placement Discovery and Replacement schemes.

Key words：Web Cache; Cache Replacement; Hit Rate

0引言

隨著在線視頻與社交媒體技術(shù)的演進(jìn)，基于HTTP的流量成為互聯(lián)網(wǎng)流量的重要組成部分。尤其在當(dāng)前流量中大量重復(fù)數(shù)據(jù)的傳輸不僅占用帶寬資源，而且也進(jìn)一步影響用戶訪問延時。為了降低訪問時延，提升用戶體驗，Web緩存技術(shù)與Web預(yù)取技術(shù)是當(dāng)前網(wǎng)絡(luò)交互性能改進(jìn)的主要手段。對于緩存技術(shù)來說，主要分為兩個層次：服務(wù)端緩存與客戶端緩存。其中，服務(wù)端緩存技術(shù)主要是將用戶頻繁訪問的數(shù)據(jù)放置于更靠近邊緣用戶位置，從而縮短傳輸路徑，如內(nèi)容分發(fā)技術(shù)；而客戶端緩存則主要在用戶端建立本地緩存以直接響應(yīng)用戶的多次請求，如瀏覽器中的網(wǎng)頁緩存等。但無論緩存的性質(zhì)和種類，緩存替換策略均是影響緩存效率的重要因素。如何更有效地對這些數(shù)據(jù)進(jìn)行存儲與替換即已成為當(dāng)前互聯(lián)網(wǎng)的研究熱點。

1相關(guān)工作

Web的緩存管理，可分為緩存更新策略與緩存定位算法兩個重要部分。緩存更新策略主要可分成三類：

（1）基于訪問時間，以LRU（Least Recently Used）或其相似類為主；

（2）基于訪問頻率，以LFU（Least Frequently Used）或其衍生類算法為主；

（3）基于其他屬性，以對象空間大小，對象價值度等其他度量指標(biāo)，構(gòu)造對象評價函數(shù)，以GDSF\\[1-2\\]為主。

研究中進(jìn)一步發(fā)現(xiàn)，單純對緩存對象本身屬性進(jìn)行評價計算并不足以有效提升Web數(shù)據(jù)的管理效率。文獻(xiàn)\\[3\\]針對無線網(wǎng)絡(luò)中的緩存提出一種協(xié)作式緩存替換機制，其中將對象一致性，最近命中間隔時間以及對象大小三個因素作為替換的權(quán)值因子。文獻(xiàn)\\[4\\]針對移動數(shù)據(jù)庫系統(tǒng)提出一種基于Markov圖的緩存替換策略，對目標(biāo)未來的位置進(jìn)行預(yù)測，從而將高頻數(shù)據(jù)進(jìn)行預(yù)取，提升緩存效率。然而這些方法都沒有考慮對象內(nèi)在語義屬性，本文考慮到網(wǎng)絡(luò)數(shù)據(jù)在應(yīng)用層中的表示方式，將數(shù)據(jù)本身的信息進(jìn)行融合分析作為替換的權(quán)值因子，同時結(jié)合對象的重引用間隔（Reuse Interval），對緩存對象的價值度進(jìn)行計算，由此而提升了緩存的性能。

2算法描述

為了研究Web請求的分布特征，在連續(xù)三天的校園網(wǎng)關(guān)的網(wǎng)絡(luò)日志中提取了427 936個用戶請求，其中包括167 981個不同的URL。如圖1所示，該數(shù)據(jù)集符合典型的zipfα分布，并且0.6<α<0.8。對象的訪問頻度越大，表示其熱門程度越高。提升緩存性能的關(guān)鍵在于盡量延長熱門對象在緩存中的存活時間。圖1數(shù)據(jù)集中的URL分布

Fig.1Distribution of data set第3期李喬，等：一種基于對象屬性的Web緩存替換策略智能計算機與應(yīng)用第4卷 圖2展示了在數(shù)據(jù)集中最熱的8個URL的訪問序列，y軸表示這8個URL，x軸表示在考察期三天內(nèi)每個URL出現(xiàn)的次序。由圖2可知，熱門的URL在某段時間內(nèi)都具有被訪問次數(shù)較多的特性，其中一部分URL逐漸變熱的，如url-2和url-5；一部分URL的被訪問行為則較為平滑，如url-8。而對于接近url-1的這類URL，由于其被訪問行為表現(xiàn)了一定的周期性，但周期間隔較長，在LRU的緩存策略下，將發(fā)生多次替換，從而降低緩存性能。對于接近url-7的這類URL，雖然具有一定的周期性，但其周期間隔不斷增長，在LFU策略下，該類URL的權(quán)值始終保持上升，然而其熱度卻呈現(xiàn)下降趨勢，從而導(dǎo)致緩存污染。圖2熱門URL的訪問序列

Fig.2Access Sequence of hot URLs

基于以上分析可得，熱門URL的訪問行為主要可分為以下3類情形：

（1） 訪問行為較為均勻，具有周期性，例如url-8，url-4;

（2） 訪問行為逐漸變快，如url-5;

（3） 突發(fā)性增長，如url-3，url-6。

由于LRU算法的本地局部性，采用該算法的缺陷在于無法描述對象的訪問頻度；而LFU算法雖然將頻度作為對象的權(quán)值，但由于緩存污染以及權(quán)值的單調(diào)性卻降低了緩存的性能?；诖耍疚氖紫瓤紤]將訪問間隔變化作為緩存對象的基礎(chǔ)權(quán)值。

為了更直觀地描述本文提出的算法，首先進(jìn)行以下定義。

定義1訪問間隔：緩存內(nèi)對象的重引用距離，即本次命中該對象與上次命中該對象之間相差的緩存訪問次數(shù)。

訪問間隔是一種區(qū)別于絕對頻度的緩存對象價值度的表示方法，但其與頻度一致的地方則在于都是僅僅考慮對象的命中屬性，而沒有對整個緩存對象的上下文環(huán)境乃至緩存對象本體內(nèi)在屬性進(jìn)行綜合性衡量。在Web緩存中，由于Web是根據(jù)網(wǎng)絡(luò)數(shù)據(jù)的命名規(guī)則對其進(jìn)行查詢與分發(fā)（如URL，P2P中的文件hash值），因此對這些外在的屬性進(jìn)行細(xì)致化描述，并將其作為對象價值的參考能夠進(jìn)一步提升整體緩存效率。

由于互聯(lián)網(wǎng)數(shù)據(jù)主要通過URL進(jìn)行定位，而URL的命名通常具備一定的語義，例如體育類相關(guān)的網(wǎng)頁URL往往包含sport，音樂類包含music等。如圖3所示，對于sports.sina.com.cn/cba的解析首先通過CDN提供的DNS服務(wù)器對域名sina.com.cn進(jìn)行解析，而后根據(jù)sports重定向到存放sports相關(guān)的服務(wù)器上，最后通過URI定位到存儲cba的服務(wù)器。一般而言，對于用戶興趣劃分的一級目錄命名較為一致，而對于二級，三級（如cba，nba等）目錄的命名則未必相同，這就表示對URL只進(jìn)行一層分析即可，所消耗的代價也極低。而且CDN運營商本身也已經(jīng)根據(jù)不同的一級目錄將數(shù)據(jù)分別放置于不同的服務(wù)器上，由此來實現(xiàn)分發(fā)效率的提升。圖3URL解析過程

Fig.3The procedure of URL parsing在此，將URL中包含的部分語義信息作為緩存對象的價值計算參數(shù)，對URL中的域名與一級目錄進(jìn)行分析，并對緩存對象的熱度進(jìn)行計算。同時，時間敏感性是網(wǎng)絡(luò)數(shù)據(jù)訪問的典型特征，大多熱門資源的熱度伴隨時間呈現(xiàn)出整體下降趨勢。文中將緩存空間標(biāo)記為S={obj1，obj2，...，objn}，S=n，則新到達(dá)一個objn+1后，緩存管理機制將原空間S中價值最低的objmin替換為objn+1。

Web中的緩存是典型的網(wǎng)絡(luò)分布式緩存系統(tǒng)，同時該緩存系統(tǒng)作為實時在線系統(tǒng)，對緩存對象價值度的計算時間的要求也較高?；诖?，考慮將對象訪問歷史、應(yīng)用層數(shù)據(jù)信息、用戶的分散度作為綜合熱度的影響因素，盡可能提升未來一段時間內(nèi)緩存效率。本文所用符號參數(shù)如表1所示。對象obji的被訪問歷史可以描述為Hobj={ad_value，reqset}，其中ad_value是對象的平均訪問間隔值，間隔越小說明被訪問得越頻繁；reqset={}，i∈N，N為訪問該對象的用戶數(shù)。為了對緩存內(nèi)容熱門度進(jìn)行多維衡量，可將obj_dnval，obj_idxval，actn作為對象熱度的評價參數(shù)。一般而言，域名的熱度表示該網(wǎng)站在整個域內(nèi)的熱門程度以及影響力，而以往單純采用url的價值度并未考慮到網(wǎng)站熱度對用戶未來訪問的影響，例如A網(wǎng)站內(nèi)a頁面被訪問10次，而B網(wǎng)站中b頁面也被訪問10次，而A的總訪問次數(shù)為100，B的總訪問次數(shù)為10，那么a在未來被訪問的概率應(yīng)當(dāng)大于b，這是由于A的知名度更高，隨之A中的頁面被訪問的概率也更高。類似地，對象標(biāo)簽價值度對衡量緩存內(nèi)容的熱度也具有參考價值，例如標(biāo)簽為q的對象被訪問100次，標(biāo)簽為p的被訪問10次，則對于被訪問10次的標(biāo)簽為q的對象a，其價值度也應(yīng)大于訪問數(shù)為10標(biāo)簽為p的對象b。文中則采用公式（1）計算對象的域名價值度與標(biāo)簽價值度。具體公式為：

obj_dnval=obj_dn∑ni=1obj_dn，

obj_idxval=obj_idx∑ni=1obj_idx（1）

表1參數(shù)描述

Tab.1Parameter Description參數(shù)描述obji第i個對象reqseti訪問第i個對象的用戶集合，是1個二元組集合reqsetval第i個對象的行為屬性值，與reqset有關(guān)wvali第i個對象的綜合權(quán)值，即綜合熱門度actn第n個用戶的活躍度Hobj對象的被訪問歷史，是1個2元組集合obj_url對象的urlobj_dn對象的域名訪問密度obj_idx對象url中的標(biāo)簽訪問密度，一般為第1級索引ufreqik第k個用戶訪問對象i域名的頻度dh_table域名哈希表，存放域名被訪問次數(shù)obj_dnval對象域名的熱度obj_idxval對象標(biāo)簽的熱度

本文在緩存對象的替換過程中，考慮訪問者屬性進(jìn)一步細(xì)致化對替換與否進(jìn)行決策。reqsetval在本質(zhì)上是一種概率值計算，由表1可知reqset是一個由用戶活躍度和訪問頻度二元組構(gòu)成的序列，而研究設(shè)定的目標(biāo)則在于通過分析該序列得到該對象在未來出現(xiàn)的概率，并且對象價值度與概率值正直接相關(guān)。reqsetval的計算如式（2）所示，該式表示當(dāng)用戶活躍度較低時，即使總訪問頻度價值也不一定能夠超過用戶活躍度高的訪問對象的價值，且顯然可得reqsetval<1。對象總價值度wval的計算則如公式（3）所示，式中將用戶行為與對象屬性作為訪問間隔的權(quán)值參數(shù)，將對象熱度進(jìn)行了更細(xì)粒度的計算。式（3）中的α、β是對應(yīng)的調(diào)節(jié)參數(shù)，可以針對不同的網(wǎng)絡(luò)需求進(jìn)行設(shè)定。

reqsetvali=∑Nk=1actk·ufreqkN·∑Nk=1ufreqk，(actk<1)（2）

wvali=(α·obj_dnvali+obj_idxvali2+

β·reqsetvali)·ad_valuei（3）

通過以上分析，給出熱度計算算法。如算法1所示，首先通過查詢域名與標(biāo)簽的哈希表，得到對象屬性的權(quán)值，其次通過查詢用戶行為表得到用戶活躍度，最后通過公式（3）得到最終的對象熱度wval。假設(shè)域名總數(shù)為M，標(biāo)簽總數(shù)為K，用戶數(shù)為N，則該算法所需的空間為O(M+K+N*M)。而時間復(fù)雜度的計算則由于查詢的過程主要通過hash函數(shù)進(jìn)行，查詢時間為O(C)，其中的C為常數(shù)。通過設(shè)置每個用戶的總訪問次數(shù)，可以使公式（1）的計算時間為常數(shù)級，而公式（3）的時間復(fù)雜度上限為O(N*M)，即該對象被所有用戶都訪問過。因此，算法的時間復(fù)雜度上限即為O(N*M)。在實際部署中，百萬級域名與千萬級用戶數(shù)的網(wǎng)絡(luò)規(guī)模下，整個存儲空間大約為10GB數(shù)量級。

多維度融合熱度計算的算法如下：

Input:對象obj，域名哈希表dh_tab，標(biāo)簽哈希表ix_tab，用戶活躍表ac_tab；

Output:對象熱度obj_hvalue

1.解析obj所對應(yīng)的域名obj.dn，標(biāo)簽obj.idx，訪問者id；

2.對obj.dn和obj.idx進(jìn)行hash計算得到dnhash與idxhash；

3.if dnhash 在dh_tab中 then

4.得到obj_dn；

5.else

6.在dh_tab中插入dnhash；

7.end if

8.if dnidx 在ix_tab中then

9.得到obj_idx；

10.else

11.在ix_tab中插入idxhash；

12.end if

13.更新dh_tab和ix_tab中對應(yīng)的值；

14.根據(jù)公式（1）計算分別得到其域名與標(biāo)簽熱度obj_dnval，obj_idxval；

15.通過用戶id在ac_tab中查詢對應(yīng)活躍度；

16.根據(jù)公式（2）得到obj的行為屬性值reqsetvali；

17.根據(jù)公式（3）得到obj的wvali。

3實驗

文中采用校園網(wǎng)關(guān)采集的數(shù)據(jù)作為實驗數(shù)據(jù)，其中用戶的請求共計427 636條，對象大小在1MB~100MB之間隨機均勻分布。在實驗中，使用幾種已有的內(nèi)容管理策略與本文的BCV（Based on Content Value）算法進(jìn)行比較。比較后的分析結(jié)果如下。

（1）基于鄰居交換的緩存策略CCB\\[5\\]。該策略采用協(xié)作式替換方法，在替換時查詢鄰居節(jié)點的緩存列表，優(yōu)先替換鄰居已存儲的資源。

（2）基于Aging的緩存策略ABC\\[6\\]。該策略目標(biāo)是為了減少網(wǎng)絡(luò)延遲以及資源發(fā)布者的負(fù)載，通過在傳輸路徑中動態(tài)修改資源年齡的協(xié)作式緩存機制將熱度最高的資源放置于網(wǎng)絡(luò)最邊緣。

（3）基于協(xié)作式中心化決策緩存策略APDR\\[7\\]。該策略通過建立內(nèi)容上一跳路由表，進(jìn)而產(chǎn)生每個內(nèi)容的多播樹，只有對該數(shù)據(jù)的第一個請求到達(dá)時會轉(zhuǎn)發(fā)至上游節(jié)點，并等待該響應(yīng)的數(shù)據(jù)到達(dá)后轉(zhuǎn)發(fā)給剩余請求的端口。同時，在緩存替換策略中采用定期更新與LFU結(jié)合的策略以防止數(shù)據(jù)污染。

如圖4所示，隨著緩存空間的增大，每種緩存策略的字節(jié)命中率都不斷提升，但由圖4可以看出隨著緩存增大，本文提出的BCV算法優(yōu)勢較為明顯，這是由于提出的算法考慮了內(nèi)容對象的空間大小以及融合熱度，而APDR雖然命中率也較高，但其關(guān)注的因素在于匯聚用戶的請求，并未將路由器種類納入研究范圍。

圖4緩存命中率對比

Fig.4Comparison of hit ratio4結(jié)束語

本文主要對當(dāng)前Web緩存系統(tǒng)中的替換策略進(jìn)行改進(jìn)，提出基于內(nèi)容價值度的緩存替換算法，該算法考慮到Web對象中隱含的語義屬性，并將其作為對象的價值度參數(shù)實行了統(tǒng)一計算，進(jìn)一步提升了緩存效率。實驗表明，文中設(shè)計的算法比其他策略高出7%-10%的命中率。

參考文獻(xiàn)：

\\[1\\]JIN S， BESTAVROS A. GreedyDual* Web caching algorithm: exploiting the two sources of temporal locality in Web request streams\\[J\\]. Computer Communications， 2001， 24(2): 174-183.

［2］CHERKASOVA L， CIARDO G. Role of aging， frequency and size in Web caching replacement strategies\\[C\\]//Proceedings of the 9th International Conference on High-Performance Computing and Networking， Amsterdam， The Netherlands， 2001:114-123.

［3］JOY P T， JACOB K P. A key based cache replacement policy for cooperative caching in mobile ad hoc networks\\[C\\]// Proceedings of IEEE 3rd International Conference on Advance Computing Conference， 2013: 383-387.

［4］CHAVAN H， SANE S， KEKRE H B. A Markov-graph cache replacement policy for mobile environment\\[C\\]// Proceedings of International Conference on Communication， Information Computing Technology， 2012:1-6.

［5］DONG L J， ZHANG Y， RAYCHAUDHURI D. Enhance content broadcast efficiency in routers with integrated caching\\[C\\]// Proceedings of 16th IEEE ISCC， Kerkyra， Corfu， Greece， 2011:320-322.

［6］MING Z， XU M， WANG D. Age-based cooperative caching in information centric networks\\[C\\]//Proceedings of IEEE INFOCOM Workshop on Emerging Design Choices in Name-Oriented Networking. Orlando， FL， USA， 2012:268-273.

［7］劉外喜， 余順爭， 蔡君，等. ICN 中的一種協(xié)作緩存機制\\[J\\]. 軟件學(xué)報， 2013， 24(8): 1947-1962.王慶斌.航材需求預(yù)測的研究\\[J\\]. SCIENCE TECHNOLOGY INFORMATION科技信息，2013年（1）.

\\[2\\]劉衛(wèi)紅，崔振霞.基于BP神經(jīng)網(wǎng)絡(luò)的藥品采購資金管理研究 \\[J\\]. 中國鄉(xiāng)鎮(zhèn)企業(yè)會計 ，2012，20(1): 70-71.

\\[3\\]白斌飛.基于神經(jīng)網(wǎng)絡(luò)理論的線性時間序列預(yù)測研究\\[D\\].成都：西南交通大學(xué)，2005.

\\[4\\]程剛，張珣，汪壽陽. 原油期貨價格對現(xiàn)貨價格的預(yù)測準(zhǔn)確性分析\\[J\\]. 系統(tǒng)工程理論與實踐，2009（8）：12-18.

\\[5\\]沈巍. 股票價格預(yù)測模型研究\\[J\\].. 財經(jīng)問題研究，2009（7）：90-93.

\\[6\\]吳清亮，董輝，張政，等. 基于神經(jīng)網(wǎng)絡(luò)對航材備件需求率的預(yù)測分析\\[J\\]. 兵工自動化，2009 ( 1 ):12-13.