吳俊龍，楊 清

（湖南科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，湖南 湘潭411201）

1 引言

隨著信息技術(shù)的迅猛發(fā)展，互聯(lián)網(wǎng)已深入滲透社會生活的各個方面，網(wǎng)絡(luò)接入用戶數(shù)與信息數(shù)據(jù)量的急劇增加導(dǎo)致各種網(wǎng)絡(luò)問題日益明顯，線路擁塞和服務(wù)器超載加劇了訪問延遲，嚴(yán)重影響了用戶網(wǎng)絡(luò)訪問體驗(yàn)。為解決這些問題，研究人員提出了各種解決方案，最具代表性的是Web緩存技術(shù)，該技術(shù)利用了Web訪問模式的時間局部性，可有效提升用戶網(wǎng)絡(luò)訪問體驗(yàn)。其基本原理是：代理服務(wù)器預(yù)先存儲一些網(wǎng)絡(luò)文件以備用戶訪問，若存儲空間不足，則按照某種標(biāo)準(zhǔn)將過期的網(wǎng)絡(luò)文件進(jìn)行替換，以保持文件的新鮮度，并保證緩存空間的可用性。當(dāng)有新的用戶請求到達(dá)時，代理服務(wù)器將已存儲的請求文件反饋給用戶，從而減少用戶感知的訪問延時［1，2］。

緩存替換算法是Web緩存技術(shù)的核心，可分為以下四種類型［3］：基于時間特性的替換算法、基于頻率特性的替換算法、基于文件大小的替換算法和基于成本/價值模型的替換算法。前三種類型的替換算法分別考慮了用戶訪問的時間特性、頻率特性與Web文件的大小特性，實(shí)現(xiàn)起來較為簡單，但性能較差，而基于成本/價值模型的替換算法通過綜合考慮各種影響因素為Web 對象計(jì)算緩存價值，在性能與系統(tǒng)開銷之間取得了不錯的均衡，是今后主要研究方向之一。

本文在成本/價值模型的基礎(chǔ)上，研究了Web對象之間和用戶之間的關(guān)聯(lián)性，并將協(xié)同過濾思想應(yīng)用于貪婪雙尺寸頻率緩存替換算法GDSF（Greedy Dual Size Frequency）［4］，提出一種基于協(xié)同過濾的Web 緩存替換算法GDSF－CF（Greedy Dual Size Frequency Collaborative Filtering）。該算法運(yùn)用協(xié)同過濾算法的思想考察用戶－文件以及文件－文件之間的關(guān)系，計(jì)算緩存空間中每個文件的預(yù)測訪問頻率并形成關(guān)于緩存價值的目標(biāo)函數(shù)，然后通過計(jì)算得到文件的緩存價值，最后將對最小緩存價值的文件進(jìn)行替換。

2 研究現(xiàn)狀

作為Web緩存替換策略的核心技術(shù)之一，緩存替換算法已有大量研究成果，Geetha K［5］提出了SEMA－LRU （SEMAntic and Least Recently Used）替換算法，SEMA－LRU 在LRU（Least Recently Used）的基礎(chǔ)上，依據(jù)網(wǎng)頁內(nèi)容的語義關(guān)聯(lián)和最近訪問次數(shù)來判斷是否將網(wǎng)頁替換出去。Lee D 和Kim K J［6］使用了延遲緩存替換策略保證用戶穩(wěn)定訪問體驗(yàn)，當(dāng)請求數(shù)量出現(xiàn)異常高時，代理服務(wù)器不會將網(wǎng)頁緩存，而只記錄數(shù)據(jù)的元信息，當(dāng)請求數(shù)量恢復(fù)至正常值后，再使用這些數(shù)據(jù)元信息為用戶請求數(shù)據(jù)，通過緩解服務(wù)器的負(fù)載為大多數(shù)用戶提供穩(wěn)定的服務(wù)質(zhì)量。張旺?。?］運(yùn)用成本/價值模型，在貪婪雙尺寸頻率緩存替換算法GDSF 的基礎(chǔ)上提出了一種改進(jìn)的GDSF－AI（Greedy Dual Size Frequency Access Interest）替換算法，該算法綜合考慮Web 對象的訪問特性、Web對象所屬的內(nèi)容類型以及用戶興趣，為緩存空間中的每個Web對象計(jì)算緩存價值，然后將價值最小的Web 對象從緩存空間中替換出去。

同樣作為訪問加速技術(shù)的一種，協(xié)同過濾技術(shù)CF（Collaborative Filtering）［8］通過分析用戶的興趣與愛好，在用戶群中為指定用戶找出具有相似興趣用戶，綜合這些相似用戶對某一信息的評價，形成系統(tǒng)對該指定用戶對此信息的喜好程度預(yù)測。這種技術(shù)能夠根據(jù)相似用戶的評分來預(yù)測當(dāng)前用戶的興趣。協(xié)同過濾的核心技術(shù)是協(xié)同過濾算法，一般而言可將協(xié)同過濾算法分成兩種類型：基于內(nèi)存的協(xié)同過濾（Memory－based CF）和基于模型的協(xié)同過濾（Model－based CF）。基于內(nèi)存的協(xié)同過濾算法運(yùn)用十分廣泛，這種類型的算法可以基于用戶，也可以基于對象，或者是用戶對象兩者混合形式?；谟脩舻膮f(xié)同過濾（User－based CF）根據(jù)相似用戶的評分預(yù)測當(dāng)前用戶的評分；而基于對象的協(xié)同過濾（Item－based CF）根據(jù)相似對象的評分預(yù)測當(dāng)前用戶的評分。基于模型的協(xié)同過濾算法首先對用戶評分?jǐn)?shù)據(jù)信息進(jìn)行分析，然后在此基礎(chǔ)上進(jìn)行學(xué)習(xí)并建立一個預(yù)測模型，最后利用這個模型來進(jìn)行關(guān)于用戶評分值的預(yù)測。此種類型的預(yù)取算法通過利用統(tǒng)計(jì)方法和機(jī)器學(xué)習(xí)這兩種途徑建立模型，包括聚類模型、貝葉斯模型關(guān)系模型、線性回歸模型等。本文選用了基于內(nèi)存的協(xié)同過濾算法，通過此種類型的協(xié)同過濾技術(shù)來為貪婪緩存替換算法進(jìn)行改進(jìn)。

3 GD系列算法

GD（Greedy Dual）算法是一種基于代價的貪婪算法，在一個代理服務(wù)器的存儲空間中，有多個Web對象i，GD 替換算法根據(jù)每個Web對象緩存所需的代價為其賦值一個數(shù)值H，當(dāng)存儲空間不足需要進(jìn)行Web對象替換時，H值最小的Web對象會被最先替換出去，然后根據(jù)最小H值來調(diào)整剩余頁面的H值。但是，該類算法存在“緩存污染”問題，即存儲空間會駐留大量長時間沒有被訪問的大尺寸Web對象。

GDS（Greedy Dual Size）是一種改進(jìn)的貪婪緩存替換算法，該類算法針對GD 算法的“緩存污染”問題進(jìn)行了改進(jìn)，GDS算法使用一個優(yōu)先級序列，并且為將來的H值設(shè)置了偏差。H值的目標(biāo)函數(shù)如下所示：

其中，Value（i）為Web對象i的緩存價值；Size（i）為i的尺寸大??；L為替換變量參數(shù)，每次有Web對象被替換出去時，L都會被重新賦值為價值最小的、被替換出去的Web對象的價值H（i）。

GDS簡單明了，但是沒有考慮Web對象的內(nèi)容類型、訪問頻率、訪問時間間隔以及流行度，可能會出現(xiàn)以下情況：在存儲空間內(nèi)存在一組Web對象，根據(jù)目標(biāo)函數(shù)的計(jì)算每個Web對象具有相同的H值，但是各個對象的訪問頻率不一致，具有較高訪問頻率的Web對象反而可能會被替換出存儲空間，不符合Web 對象訪問特性的局部性規(guī)律。針對該類問題，通過為目標(biāo)函數(shù)引入Web對象的訪問頻率，提出了GDSF 算法。該算法充分考慮了Web對象的尺寸大小、緩存代價以及訪問頻率。其目標(biāo)函數(shù)如下所示：

其中，F(xiàn)r（i）為Web對象i的訪問頻率。

GDSF算法通過在目標(biāo)函數(shù)的計(jì)算中加入Web對象的訪問頻率，可有效提高緩存替換效率，但對Web對象的內(nèi)容類型、流行度以及修改頻率這幾個因素缺乏關(guān)注，GDSF算法還有進(jìn)一步改進(jìn)的空間。

4 GDSF－CF算法

4.1 算法描述

GDSF－CF替換算法將協(xié)同過濾中的項(xiàng)目作為Web對象處理，并將用戶對項(xiàng)目的評分值歸一化為用戶對文件的訪問頻率，通過相似度的計(jì)算來預(yù)測文件的用戶訪問頻率，并最終建立目標(biāo)函數(shù)計(jì)算文件的緩存價值，如以下三個步驟：

（1）運(yùn)用協(xié)同過濾算法生成用戶對于Web對象的預(yù)測訪問次數(shù)；

（2）考慮齊普夫定律參數(shù)與訪問時間間隔因素建立Re（i）參數(shù)；

（3）結(jié)合上述各項(xiàng)參數(shù)建立關(guān)于Web對象緩存價值的目標(biāo)函數(shù)。

下面就GDSF－CF算法的原理做出具體描述：

（1）形成相似Web對象集合。

①計(jì)算Web 對象之間的相似性。訪問過Web對象i與Web對象j的用戶可形成用戶Ui，j，Ui，j＝Ui∩Uj，c為Ui，j中的任意一個用戶。計(jì)算i，j之間的相似度可以使用皮爾孫算法，如公式（1）所示：

其中，sim（i，j）為i、j之間的相似度，Vc，i與Vc，j分別是用戶c訪問i與j的統(tǒng)計(jì)次數(shù)，和分別為每個用戶訪問i與j的平均統(tǒng)計(jì)次數(shù)。由于緩存空間中的Web對象具有相對穩(wěn)定性，即新進(jìn)入的Web對象不會被立即替換出緩存空間，因此可在系統(tǒng)處于離線時計(jì)算對象之間的相似度，然后將所得數(shù)值存放于數(shù)據(jù)列表中。

②形成每個Web對象的相似集合。對緩存空間中任意Web對象k，在整個對象集合上進(jìn)行搜索，選取并集合與k相似度最高的前H個Web對象，作為k的相似對象集SIk。

③計(jì)算預(yù)測訪問次數(shù)Va，k。設(shè)用戶a與用戶b分別訪問過不同的Web對象，這些Web對象的并集為Ia，b，Ia，b＝Ia∪Ib，有Web對象k和n，k∈Ia，b，n∈SIk，目標(biāo)用戶a未訪問過k，可通過SIk預(yù)測用戶a訪問k的次數(shù)Va，k，如公式（4）所示：

通過公式（4）可計(jì)算出緩存空間內(nèi)任意用戶對于緩存空間中任意Web對象i的預(yù)測訪問次數(shù)，其值可用V（i）來表示。

（2）計(jì)算Re（i）頻率參數(shù)。

本文考慮到緩存空間中的Web對象有可能被用戶再次訪問，為此設(shè)置了一個相關(guān)參數(shù)Re（i），Re（i）與用戶訪問頻率因素相關(guān)，Web對象的流行度、訪問頻率和用戶訪問請求之間的時間間隔均對用戶再次訪問的概率有較大影響。結(jié)合齊普夫（Zipf）定律［8］以及本文提出的用戶預(yù)測訪問次數(shù)參數(shù)V（i）來對用戶訪問頻率因素Re（i）進(jìn)行計(jì)算，如公式（5）所示：

其中，V（i）是用戶訪問i的預(yù)測次數(shù)，δT（i）是用戶請求i的時間間隔，β是齊普夫定律中的參數(shù)。

（3）計(jì)算節(jié)省數(shù)據(jù)包的價值。

將Web對象i引入緩存空間也需考慮付出的代價值，通常在緩存策略中考慮以下三種類型的代價值：常數(shù)、延遲時間和數(shù)據(jù)包個數(shù)。為了準(zhǔn)確衡量因使用緩存替換算法而節(jié)省下來的數(shù)據(jù)包傳送個數(shù)，本文選擇數(shù)據(jù)包的傳送個數(shù)作為代價，其代價值為Value（i）。因TCP分段大小為536bytes，Value（i）的計(jì)算如公式（6）所示：

（4）形成計(jì)算緩存價值的目標(biāo)函數(shù)。

根據(jù)以上關(guān)于各種因素的計(jì)算，在貪婪雙尺寸頻率替換算法GDSF 的基礎(chǔ)上，本文提出了一種結(jié)合協(xié)同過濾技術(shù)的緩存替換算法GDSF－CF。在緩存替換過程中，該算法利用目標(biāo)函數(shù)公式計(jì)算Web對象的緩存價值并對最小緩存價值的對象進(jìn)行替換。其目標(biāo)函數(shù)如公式（7）所示：

其中，參數(shù)L是一個膨脹因子，Value（i）為獲取Web對象i所需的代價，Size（i）為Web對象i的尺寸大小。

4.2 算法流程

為方便介紹GDSF－CF算法替換流程，首先設(shè)置如下參數(shù)：

L：為初始閾值，當(dāng)有最小緩存價值H（i）min的Web對象從緩存空間中替換出去時，L會被重新賦值，其值為H（i）min；

fr（i）：用戶訪問Web對象i的次數(shù)，初始值為1；

Value（i）：引入Web 對象i至緩存空間所需付出的代價；

Ctotal：緩存空間的總大??；

Cused：已使用的緩存空間大?。?/p>

Size（i）：Web對象i的尺寸大小。

GDSF－CF具體流程如下所示：

（1）初始參數(shù)，令L＝0，Cused＝0。

（2）如果緩存空間中已有用戶請求的Web對象i，則令fr（i）增加1，即fr（i）＝fr（i）＋1，Cused的值不發(fā)生改變。

（3）如果緩存空間中不存在用戶請求的Web對象i，則表示用戶請求沒有被命中，此時用戶請求將會轉(zhuǎn)交至遠(yuǎn)程Web服務(wù)器，通過與Web服務(wù)器的直接連接獲取Web對象i，然后將此Web對象i保存至緩存空間中，待下次使用。

此時令fr（i）＝1，即Web對象i訪問次數(shù)為1，根據(jù)替換算法的目標(biāo)函數(shù)公式（8）計(jì)算Web對象i的緩存價值H（i），由于緩存空間發(fā)生改變，有：

依據(jù)剩余空間大小，接下來會有兩種狀況：

①Cused≤Ctotal，表明剩余緩存空間充裕，則可以將Web對象i直接放入緩存空間中，無需進(jìn)行緩存替換。

②Cused＞Ctotal，剩余緩存空間不足，Web對象i無法放入緩存空間，需要進(jìn)行緩存替換以釋放空間?？稍诰彺婵臻g中選取n個緩存價值H（i）的Web 對 象，形 成Web 對 象 組i1，i2，…，in，這 組Web對象滿足以下兩個條件：

按照用戶請求的Web對象i所處位置，分為以下兩種情況：

a Web對象i位于這一組Web對象中，表明i的緩存價值很小，沒必要進(jìn)行緩存，也無需替換緩存空間中的任何對象，恢復(fù)Cused值至原值即可。

b Web對象i不處于這一組Web對象中，表明i的緩存價值超過了這組對象，則令L取值為這一組Web對象中最大的緩存價值H（i），其值為H（i）max，Cused的取值也發(fā)生變化，計(jì)算公式如下：

然后計(jì)算出L與Cused的數(shù)值，從緩存空間中替換出這n個對象i1，i2，…，in，最后將Web對象i保存至緩存空間中，完成緩存過程。

GDSF－CF算法的偽代碼如下所示：

算法1 GDSF－CF算法

5 仿真實(shí)驗(yàn)

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

仿真實(shí)驗(yàn)使用了SimpleScalar模擬器［9］作為仿真平臺，輸入數(shù)據(jù)采用來自銳捷緩存加速器RGPowerCache W5中的訪問日志，共473 134條請求記錄，日志總?cè)萘繛?99 MB，整個實(shí)驗(yàn)在一臺DELL服務(wù)器上進(jìn)行，該服務(wù)器配置為至強(qiáng)E7520 1.866GHz處理器，16GB DDR3內(nèi)存，運(yùn)行Red Hat Linux 9.0系統(tǒng)。

5.2 測試數(shù)據(jù)和實(shí)驗(yàn)分析

首先，按照不同的文件擴(kuò)展名，將各類型的Web加以區(qū)分，確定各種類型的Web文件在所有用戶請求記錄中所占的比例。Web文件類型可分為文本、圖像、音頻、視頻、程序和其他六種類型，經(jīng)處理后得到的結(jié)果如表1所示。

Table 1 Types of Web objects表1 Web對象類型

隨后，將用戶的服務(wù)器訪問日志發(fā)送至日志處理程序，經(jīng)過處理后輸出為SimpleScalar模擬器可以處理的格式，然后輸入至SimpleScalar的Simcache模擬器進(jìn)行仿真實(shí)驗(yàn)。本文采用了SIZE、LRU 與GDSF 這三種經(jīng)典緩存替換算法與GDSF－CF算法進(jìn)行性能對比。

表2為仿真實(shí)驗(yàn)所得到的各種算法命中率HR比較結(jié)果。

表3為為仿真實(shí)驗(yàn)所得到的各種算法字節(jié)命中率BHR 比較結(jié)果。

本文采用了以下兩種指標(biāo)衡量替換算法的性能：請求命中率HR（Hit Rate）和字節(jié)命中率BHR（Byte Hit Rate）

圖1表示的是輸入的日志文件在緩存相對大小分別 為1%、2%、3%、5%、10%、20%的條件下，GDSF－CF算法命中率與其他算法命中率的比較。當(dāng)緩存相對大小處于0%～5%時，GDSF－CF 的命中率從0.377上升至0.472，命中率隨著緩存相對大小的增加而持續(xù)提高，最高可達(dá)到0.512，但是命中率不會一直持續(xù)增加，而是逐漸趨于平穩(wěn)。相對于GDSF算法的命中率，GDSF－CF 的命中率提升了12%。

Table 2 Results of hit rate表2 算法命中率HR

Table 3 Results of byte hit rate表3 算法字節(jié)命中率BHR

Figure 1 Comparison of hit rate圖1 算法命中率比較

圖2 表示的是在緩存相對大小分別為1%、2%、3%、5%、10%、20%的條件下，GDSF－CF算法字節(jié)命中率與其他算法字節(jié)命中率的比較。當(dāng)緩存相對大小處于5%～10%時，GDSF－CF 的字節(jié)命中率從0.381 上升至0.420，最大可以達(dá)到0.423。與命中率的增幅情況相類似，字節(jié)命中率不會一直持續(xù)增加，而是逐漸趨于平穩(wěn)。相對于GDSF算法，GDSF－CF的字節(jié)命中率提升了9%。

Figure 2 Comparison of byte hit rate圖2 算法字節(jié)命中率比較

6 結(jié)束語

Web緩存技術(shù)是提升用戶訪問體驗(yàn)、優(yōu)化帶寬使用率的快速捷徑。緩存替換算法是Web緩存研究中的核心問題之一，由于替換算法的性能對環(huán)境因素的設(shè)置相當(dāng)敏感，不同設(shè)置環(huán)境下導(dǎo)致替換效果具有差異性。本文綜合考慮各項(xiàng)因素對Web對象的影響，針對GDSF 算法在預(yù)測方面的不足，提出了基于協(xié)同過濾的緩存替換算法GDSF－CF。實(shí)驗(yàn)結(jié)果表明，GDSF－CF 算法較GDSF 算法具有更好的命中率和字節(jié)命中率。

［1］ World Internet Usage and Population Statistics［R］.NY：Internet World Stats，2009.

［2］ Deshpande S.Systems and methods for implementing a cache model：U S Patent Application 10/737，543［P］.2003－12－16.

［3］ Song Bing.Research on web prefetch and web cache model［D］.Zhengzhou：Zhengzhou University，2006.（in Chinese）

［4］ Cherkasova L.Improving www proxies performance with greedy－dual－size－frequency caching policy［R］.H P Laboratories Report No HPL－98－69R1.Palo Alto：Hewlett－Packard Laboratory，1998.

［5］ Geetha K.SEMALRU：An implementation of modified web cache replacement algorithm［C］∥Proc of Nature ＆Biologically Inspired Computing，2009：1406－1410.

［6］ Lee D，Kim K J.A study on improving web cache server performance using delayed caching［C］∥Proc of 2010International Conference on Information Science and Applications（ICISA），2010：1－5.

［7］ Zhang Wang－jun.Research of web cache replacement policy and pre－fetching［D］.Hefei：University of Science and Technology of China，2011.（in Chinese）

［8］ Fan Bo，Cheng Jiu－jun.Multiple similarity between users in collaborative filtering recommendation algorithm ［J］.Computer Science，2012，39（1）：23－26.（in Chinese）

［9］ Ma Hai－feng，Yao Nian－min，F(xiàn)an Hong－bo.Cache performance simulation and analysis under SimpleScalar platform［C］∥Proc of International Conference on New Trends in Information and Service Science，2009：607－612.

附中文參考文獻(xiàn)：

［3］ 宋冰.Web 預(yù)取與緩存一體化模型研究［D］.鄭州：鄭州大學(xué)，2006.

［7］ 張旺俊.Web 緩存替換策略與預(yù)取技術(shù)的研究［D］.合肥：中國科學(xué)技術(shù)大學(xué)，2011.

［8］ 范波，程久軍.用戶間多相似度協(xié)同過濾推薦算法［J］.計(jì)算機(jī)科學(xué)，2012，39（1）：23－26.