黎慧源 ，易國(guó)洪*，代 瑜 ，馮智莉

1.智能機(jī)器人湖北省重點(diǎn)實(shí)驗(yàn)室（武漢工程大學(xué)），湖北 武漢 430205；2.武漢工程大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，湖北 武漢 430205

隨著互聯(lián)網(wǎng)的發(fā)展，Web服務(wù)器的壓力越來(lái)越大，用戶對(duì)網(wǎng)頁(yè)的響應(yīng)速度要求也越來(lái)越高。為了減輕Web服務(wù)器在高并發(fā)訪問(wèn)情況下的壓力，縮短用戶訪問(wèn)Web網(wǎng)站的時(shí)間延遲，可以在Web服務(wù)器和用戶之間增設(shè)Web代理服務(wù)器。Web代理服務(wù)器將一些經(jīng)常被訪問(wèn)到的Web對(duì)象緩存在代理服務(wù)器中，當(dāng)用戶由客戶端向Web服務(wù)器發(fā)出請(qǐng)求時(shí)，請(qǐng)求將被發(fā)送到代理服務(wù)器，由代理服務(wù)器來(lái)進(jìn)行處理。如果代理服務(wù)器中已經(jīng)存有用戶請(qǐng)求的Web對(duì)象，則經(jīng)過(guò)代理服務(wù)器對(duì)緩存對(duì)象的一致性和有效性進(jìn)行判斷后，直接將有效的緩存對(duì)象返回給用戶，或者去源Web服務(wù)器上取回最新的Web對(duì)象，存儲(chǔ)在代理服務(wù)器中后，再將對(duì)象返回給用戶。當(dāng)代理服務(wù)器緩存空間不足時(shí)，緩存機(jī)制會(huì)根據(jù)緩存替換算法會(huì)將某些緩存對(duì)象移出緩存空間來(lái)存儲(chǔ)新的Web對(duì)象［1］。因此，緩存替換算法的好壞是決定代理服務(wù)器性能的重要因素之一。

最著名和最基本的緩存替換算法有最近最少使用替換（Least Recently Used，LRU）算法［2］，該算法優(yōu)先替換掉那些離上一次被訪問(wèn)時(shí)間的時(shí)間間隔最長(zhǎng)的對(duì)象。先進(jìn)先出（First In First Out，F(xiàn)IFO）算法［3］，優(yōu)先替換掉最先進(jìn)入緩存區(qū)的對(duì)象。基于對(duì)象大?。⊿ize）替換算法［4］，將緩存中最大的對(duì)象替換出去。還有最不經(jīng)常使用替換算法，該算法將自進(jìn)入內(nèi)存后使用次數(shù)最少的對(duì)象替換出去。然而，它們有一個(gè)主要的不足之處，即它們僅依賴于一種流量特性，例如訪問(wèn)頻率、駐留時(shí)間或最近訪問(wèn)時(shí)間。算法考慮的因素單一，所以造成了以上4種算法的性能有限。

考慮到以上基本算法的不足，研究者們提出了綜合考慮多因素的緩存替換算法。最小使用價(jià)值算法［5］包括 Cao 和 Irani［6］在 1997年提出貪婪雙尺寸算法，Cherkasova［7］在 1998 年提出的貪婪雙尺寸頻率（Greedy Dual Size Frequency，GDSF）算法，Lee等［8］在2001年提出的最近最少經(jīng)常使用算法，以及文獻(xiàn)［9］提出的基于保存價(jià)值的Hybrid算法。此類算法通常從文件對(duì)象的大小、訪問(wèn)頻率、訪問(wèn)延遲等多個(gè)影響緩存性能的方面進(jìn)行考慮，通過(guò)一個(gè)價(jià)值函數(shù)來(lái)計(jì)算每個(gè)對(duì)象的保存價(jià)值，當(dāng)需要發(fā)生替換緩存時(shí)，優(yōu)先將保存價(jià)值最小的對(duì)象替換出去。

在最近幾年緩存替換算法也取得了一些新的研究成果。Sajeev和 Sebastian［10］在 2011 年提出了一種新的網(wǎng)絡(luò)緩存對(duì)象分類方案，該方案使用多項(xiàng)邏輯回歸技術(shù)對(duì)緩存對(duì)象進(jìn)行分類。2012年，Ali和 Shamsuddin［11］提出了基于機(jī)器學(xué)習(xí)技術(shù)的智能Web代理緩存方法，以Web代理日志文件作為訓(xùn)練數(shù)據(jù)，用支持向量機(jī)預(yù)測(cè)稍后可能重新訪問(wèn)的Web對(duì)象，與傳統(tǒng)Web代理緩存技術(shù)LRU和GDSF結(jié)合，形成名為SVM-LRU和SVM-GDSF的智能緩存方法。2015 年，Negr?o 和 Roque［12］提出了一種用于Web緩存的自適應(yīng)語(yǔ)義感知替換算法，它為緩存替換過(guò)程添加了空間維度，根據(jù)從一個(gè)對(duì)象導(dǎo)航到另一個(gè)對(duì)象所需的鏈接數(shù)量來(lái)測(cè)量對(duì)象之間的距離，發(fā)生替換時(shí)，將遠(yuǎn)離最近訪問(wèn)的頁(yè)面的對(duì)象作為移除的候選者。2017年，Benhamida和Bouallouche-Medjkoune［13］提出了使用相對(duì)頻率來(lái)替換傳統(tǒng)的訪問(wèn)頻率，相對(duì)頻率是使用文檔訪問(wèn)次數(shù)及其在緩存中的生命周期計(jì)算的。

文檔的訪問(wèn)頻率是緩存替換算法的重要考慮因素，本文引入了平均周期訪問(wèn)頻率、最近周期訪問(wèn)頻率、周期相對(duì)頻率3個(gè)特性，將周期相對(duì)頻率作為對(duì)象流行度的重要影響因子，綜合了對(duì)象大小、網(wǎng)絡(luò)帶寬因素，提出了貪婪雙尺寸周期相對(duì)頻率（Greedy Dual Size Frequency Periodic Relative Frequency，GDSF-PRF）算法，在用戶訪問(wèn)網(wǎng)頁(yè)的習(xí)慣符合 Zipf［14］定律的情況下，經(jīng)過(guò)與 LRU、FIFO、GDSF算法的實(shí)驗(yàn)對(duì)比，驗(yàn)證了GDSF-PRF在訪問(wèn)命中率和字節(jié)命中率上有更好的表現(xiàn)。

1 相關(guān)工作

1.1 緩存替換算法的性能指標(biāo)

緩存替換算法通常使用的性能評(píng)價(jià)指標(biāo)有3個(gè)：請(qǐng)求命中率、字節(jié)命中率和訪問(wèn)延遲［15］。在發(fā)生數(shù)據(jù)請(qǐng)求時(shí)，如果緩存中已經(jīng)保存了該數(shù)據(jù)，并且該緩存數(shù)據(jù)有效，可以直接將該緩存數(shù)據(jù)返回給用戶，則稱此次數(shù)據(jù)請(qǐng)求為一次命中；否則要向原始數(shù)據(jù)所在的服務(wù)器請(qǐng)求數(shù)據(jù)，此時(shí)稱為一次缺失，即未命中。

1）請(qǐng)求命中率

請(qǐng)求命中率是代理緩存服務(wù)器緩存命中的次數(shù)占用戶發(fā)出的請(qǐng)求總次數(shù)的百分比，用Rh表示。用Nr表示請(qǐng)求總次數(shù)，用Nh表示緩存命中次數(shù)，則Rh可表示為：

2）字節(jié)命中率

字節(jié)命中率是代理緩存服務(wù)器本身向用戶發(fā)出的字節(jié)數(shù)與用戶總的請(qǐng)求數(shù)之比，用Rbh表示。用Bh表示緩存命中字節(jié)數(shù)，Br表示代理接收到的用戶總請(qǐng)求字節(jié)數(shù)，則Rbh可表示為：

3）平均訪問(wèn)延遲

平均訪問(wèn)延遲是指從客戶端請(qǐng)求數(shù)據(jù)到收到數(shù)據(jù)所需的平均時(shí)間，用tal表示。平均時(shí)間越短，緩存性能越好。用Nr表示請(qǐng)求總次數(shù)，用t表示Nr次請(qǐng)求總的訪問(wèn)延遲時(shí)間，則tal可表示為：

1.2 GDSF算法

GDSF算法，即貪婪雙尺寸頻率緩存替換算法［16］。該算法的基本思想是使用某個(gè)目標(biāo)保存價(jià)值函數(shù)來(lái)計(jì)算出緩存中所有緩存對(duì)象的保存價(jià)值H，當(dāng)緩存剩余空間不足以保存新的對(duì)象時(shí)，根據(jù)這個(gè)H值將緩存對(duì)象由高到低進(jìn)行排序，優(yōu)先將緩存中保存價(jià)值H最低的對(duì)象替換出去。其目標(biāo)函數(shù)為：

H(i)表示第i個(gè)緩存對(duì)象的緩存價(jià)值，V(i)表示將Web對(duì)象i引入到緩存中的所需要付出的代價(jià)，如帶寬、網(wǎng)絡(luò)延遲等。L為膨脹因子，初值為0，每當(dāng)有Web對(duì)象替換出去時(shí)，L都會(huì)被重新賦值為那個(gè)被替換出去的對(duì)象的H(i)。F(i)為Web對(duì)象i的訪問(wèn)次數(shù)。該算法綜合考慮了對(duì)象大小和訪問(wèn)頻率因素，但是沒(méi)有考慮目標(biāo)的將來(lái)流行度因素，會(huì)造成較小對(duì)象且較短時(shí)間內(nèi)訪問(wèn)頻率大的緩存對(duì)象常駐在緩存空間中。

1.3 已有的GDSF改進(jìn)算法

從文件大小角度來(lái)看，在GDSF算法中，文件大小越小，文件的H值越大，文件被替換出去的可能性就越小，這就導(dǎo)致小文件被存儲(chǔ)的概率增大，大文件被替換出去的概率增大，導(dǎo)致了較低的字節(jié)命中率。因此，為了提高請(qǐng)求的命中率，降低文件大小對(duì)文件保留價(jià)值的影響程度，部分改進(jìn)方案中，將S(i)調(diào)整為log2[S(i)]，即

從時(shí)間角度來(lái)看，文件再次被訪問(wèn)的可能性隨時(shí)間的延長(zhǎng)而降低。因此在計(jì)算對(duì)象保留價(jià)值時(shí)，還應(yīng)考慮對(duì)象的時(shí)間價(jià)值。GDSF算法雖然考慮了文件的訪問(wèn)頻率但是沒(méi)有考慮時(shí)間因素。因此，有研究者引入了平均訪問(wèn)頻度的概念，提出了GDSF-T（Greedy-Dual-Size-Frequency-Time）算法［17］。

定義在時(shí)間距離t內(nèi)，Web訪問(wèn)對(duì)象i的平均訪問(wèn)頻度為：

其中，F(xiàn)r(i)表示W(wǎng)eb對(duì)象i在時(shí)間t內(nèi)，被訪問(wèn)的次數(shù)。tsys表示緩存替換發(fā)生時(shí)的系統(tǒng)時(shí)間，tstore_time表示對(duì)象i進(jìn)入緩存時(shí)的時(shí)間。改進(jìn)后的算法GDSF-T的如下：

2 GDSF-PRF算法設(shè)計(jì)

2.1 頻率因素的改進(jìn)

GDSF算法中考慮了文件的訪問(wèn)頻率因素，但是單純的考慮文件的訪問(wèn)頻率不能很好的反映文件的最近訪問(wèn)熱度和將來(lái)可能熱度，可能造成曾今某一個(gè)時(shí)段被高頻率訪問(wèn)而近期未被訪問(wèn)的文件長(zhǎng)時(shí)間駐留緩存的情況發(fā)生。因此，已經(jīng)有研究者嘗試對(duì)頻率因素的考量進(jìn)行改進(jìn)，如1.3節(jié)中提到的GDSF-T算法，該算法引入了平均訪問(wèn)頻度的概念來(lái)代替GDSF算法原有的單純的訪問(wèn)頻度因素，在文件訪問(wèn)頻率的基礎(chǔ)上增加了對(duì)文件的緩存駐留時(shí)間的考量，使得文件的平均訪問(wèn)頻度隨駐留時(shí)間的增長(zhǎng)而降低，考慮的因素更全面，但是需要記錄下每個(gè)文件初次進(jìn)入緩存的時(shí)間，造成了額外的空間消耗，并且沒(méi)有考慮到文件的最近訪問(wèn)時(shí)間。使用平均訪問(wèn)頻度可以大致的描述文件在過(guò)去的訪問(wèn)熱度，不能很好的預(yù)測(cè)文件將來(lái)可能的熱度。

因此，本文引入了平均周期訪問(wèn)頻率、最近周期訪問(wèn)頻率、周期相對(duì)頻率3個(gè)特性。根據(jù)文件的平均周期訪問(wèn)頻率和最近周期訪問(wèn)頻率，得到周期相對(duì)頻率，分析出文件訪問(wèn)頻率的周期走勢(shì)。對(duì)文件的訪問(wèn)頻率進(jìn)行周期性的計(jì)數(shù)，本文的訪問(wèn)周期使用次數(shù)周期N來(lái)代替時(shí)間周期，以此來(lái)避免對(duì)文件訪問(wèn)時(shí)間的存儲(chǔ)，減小空間消耗。

平均周期訪問(wèn)頻率描述的是從文件進(jìn)入緩存至今，在被訪問(wèn)過(guò)的周期里，平均每個(gè)周期被訪問(wèn)的頻率。用F(i)表示文件i進(jìn)入緩存后被訪問(wèn)的次數(shù)，Nc(i)表示文件i被訪問(wèn)過(guò)的周期數(shù)，則文件i的平均周期訪問(wèn)頻率Fa(i)表示為：

最近周期訪問(wèn)頻率描述的是文件在最近的一個(gè)周期里被訪問(wèn)的頻率。Nnow表示當(dāng)前周期從周期開(kāi)始時(shí)刻起至今的訪問(wèn)次數(shù)，F(xiàn)n(i)表示文件i在當(dāng)前周期里被訪問(wèn)的次數(shù)，則文件i的最近周期訪問(wèn)頻率Fc(i)表示為：

周期相對(duì)頻率根據(jù)文件的平均周期訪問(wèn)頻率和最近周期訪問(wèn)頻率得到，周期相對(duì)頻率描述的是文件的周期走勢(shì)。如果文件i的最近周期頻率Fc(i)小于文件i的平均訪問(wèn)周期頻率Fa(i)，則可以說(shuō)明文件i被訪問(wèn)的頻率呈下降趨勢(shì)，在未來(lái)被訪問(wèn)的相對(duì)頻率小，發(fā)生緩存替換時(shí)文件i將有更大的可能性被替換出緩存空間。如果文件i的最近周期頻率Fc(i)大于文件i的平均訪問(wèn)周期頻率Fa(i)，則可以說(shuō)明文件i被訪問(wèn)的頻率呈上升趨勢(shì)，在未來(lái)被訪問(wèn)的相對(duì)頻率大，發(fā)生緩存替換時(shí)文件i將有更小的可能性被替換出緩存空間。k為參數(shù)，可根據(jù)業(yè)務(wù)調(diào)整k的值來(lái)調(diào)整相對(duì)頻率對(duì)保留價(jià)值的的影響力度。周期相對(duì)頻率Fpr(i)的表達(dá)式如下：

2.2 GDSF-PRF算法描述

GDSF-PRF算法將GDSF算法公式（5）中的頻率 Fr(i)替換成周期相對(duì)頻率 Fpr(i)，即公式（10），目標(biāo)函數(shù)如下：

L為膨脹因子，初值為0，當(dāng)緩存中有Web對(duì)象被替換出去時(shí)，L都會(huì)被重新賦值為那個(gè)被替換出去的對(duì)象的H(i)。

V(i)為緩存空間從Web服務(wù)器獲取Web對(duì)象i需要付出的代價(jià)，本文選擇數(shù)據(jù)包的傳送個(gè)數(shù)作為代價(jià)，TCP分段大小為536 bytes，因此V(i)的計(jì)算公式如下：

式（12）中S(i)為Web對(duì)象的字節(jié)大小。

根據(jù)公式（11），可得如下GDSF-PRF算法的偽代碼：

Begin

輸入：要訪問(wèn)的文件d

if數(shù)據(jù)d not in cache

while 緩存空閑大小＜Size（d）

計(jì)算H，得到最小Hmin值的文件i

L=Hmin

移出i文件

存入文件d

F（d）=1，F(xiàn)n（d）=1，Nc（i）=1

Nnow=Nnow+1

F（i）=F（i）+1

Fn（i）=Fn（i）+1

if Nnow等于N

if Fn（i）大于0

Nc（i）=Nc（i）+1

Nnow=1，F(xiàn)n（i）=1；

end

2.3 算法參數(shù)的設(shè)定

GDSF-PRF需要預(yù)先設(shè)定的參數(shù)：

1）參數(shù)k決定了相對(duì)頻率對(duì)保留價(jià)值的影響程度，設(shè)定的k值需要使得保留價(jià)值與相對(duì)頻率的影響度相近，一般選取1到5之間的奇數(shù)。

2）訪問(wèn)周期N的設(shè)置。訪問(wèn)周期N用來(lái)確定更新的次數(shù)間隔。N的大小會(huì)影響更新的頻率，進(jìn)而影響系統(tǒng)的開(kāi)銷和數(shù)據(jù)存放在緩存中的時(shí)間。達(dá)到一個(gè)次數(shù)周期后需要對(duì)所有數(shù)據(jù)進(jìn)行一次遍歷，因此達(dá)到N次訪問(wèn)的時(shí)間間隔應(yīng)該大于遍歷與更新數(shù)據(jù)系統(tǒng)所需要的時(shí)間開(kāi)銷。N的設(shè)置也和業(yè)務(wù)的數(shù)據(jù)流行度隨時(shí)間的變化快慢有關(guān)。如果按緩存對(duì)象被訪問(wèn)的次數(shù)對(duì)緩存對(duì)象進(jìn)行由高到低的排序，用r來(lái)代表緩存對(duì)象在排序表中的序號(hào)，用f來(lái)表示該緩存對(duì)象被訪問(wèn)的頻率，則當(dāng)網(wǎng)站的數(shù)據(jù)符合齊普夫（Zipf）定律時(shí)，r和f的乘積是一個(gè)常數(shù)，該常數(shù)用C來(lái)表示。這種規(guī)律用公式可表示為：

根據(jù) M L Hanley［18］有關(guān) James Joyce Ulysses的用詞數(shù)據(jù)統(tǒng)計(jì)發(fā)現(xiàn)，Zipf定律的常數(shù)C乘以10與訪問(wèn)總次數(shù)很接近。若服務(wù)器緩存可以存儲(chǔ)m個(gè)對(duì)象，排名第m的對(duì)象周期內(nèi)被訪問(wèn)的次數(shù)為n次，訪問(wèn)周期為N，根據(jù)Zipf定律有：

為了讓訪問(wèn)次數(shù)最低的一個(gè)對(duì)象在一個(gè)訪問(wèn)周期里面都至少能被訪問(wèn)到一次，即n≥1，就需要滿足

如若緩存服務(wù)器能緩存100個(gè)平均大小的文件，即m=100，則次數(shù)周期N可設(shè)置為1 000。

3 實(shí)驗(yàn)與分析

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

實(shí)驗(yàn)使用的Web服務(wù)器配置為：Intel Xeon L5520的2.4 GHz處理器2個(gè)，16 GB的RAM，10 MB帶寬，運(yùn)行Windows Server 2008系統(tǒng)。

代理服務(wù)器的配置為Intel Xeon L5520 2.4 GHz處理器，1 GB的RAM，4 MB帶寬，運(yùn)行Red Hat Linux 9.0系統(tǒng)。代理服務(wù)器上使用squid反向代理實(shí)現(xiàn)，修改Squid中/src/repl目錄下的緩存替換算法的源碼，即可實(shí)現(xiàn)不同緩存算法的對(duì)比。

3.2 實(shí)驗(yàn)數(shù)據(jù)與參數(shù)設(shè)置

互聯(lián)網(wǎng)用戶訪問(wèn)習(xí)慣符合Zipf定律，為了測(cè)試算法性能，本文選取的實(shí)驗(yàn)數(shù)據(jù)集參數(shù)如表1所示。表2描述的是代理服務(wù)器不同的緩存容量對(duì)應(yīng)的訪問(wèn)周期N的設(shè)定。公式（10）中的參數(shù)k設(shè)置為3。

表1 測(cè)試數(shù)據(jù)集參數(shù)Tab.1 Parameters of test data set

實(shí)驗(yàn)緩存容量為10 MB～80 MB，測(cè)試不同緩存容量下，各種算法的命中率，訪問(wèn)對(duì)象一個(gè)訪問(wèn)周期內(nèi)的訪問(wèn)次數(shù)設(shè)定如表2所示。

表2 訪問(wèn)次數(shù)與緩存大小的關(guān)系Tab.2 Relationship between access cycle and cache size

對(duì)象集合包含對(duì)象100個(gè)，總大小為100 MB。高頻對(duì)象指訪問(wèn)頻率占請(qǐng)求頻率80%的對(duì)象，低頻對(duì)象指訪問(wèn)頻率占請(qǐng)求頻率20%的對(duì)象，高頻對(duì)象和低頻對(duì)象的比例符合Zipf定律，即“二八原則”，高頻對(duì)象有20個(gè)，低頻對(duì)象有80個(gè)。

在放置請(qǐng)求集合時(shí)為了滿足Zipf定律，即20%的內(nèi)容會(huì)占有80%的訪問(wèn)量，用JAVA程序在100個(gè)文件中隨機(jī)選取20個(gè)文件，對(duì)這20個(gè)文件進(jìn)行800次訪問(wèn)，對(duì)其他文件進(jìn)行200次訪問(wèn)，并隨機(jī)打亂訪問(wèn)順序，以此生成一組符合Zipf規(guī)律的訪問(wèn)序列，請(qǐng)求集合總大小約為1 GB。

3.3 多種替換算法對(duì)比實(shí)驗(yàn)

對(duì) LRU、FIFO、GDSF、GDSF-PRF算法進(jìn)行請(qǐng)求命中率和字節(jié)命中率的比較。Web服務(wù)器存放100個(gè)文件，設(shè)定緩存容量分別為Web服務(wù)器文件總大小的10%，20%，依次至80%，對(duì)緩存進(jìn)行1000次 訪 問(wèn) ，分 別 調(diào) 用 LRU、FIFO、GDSF、GDSF-PRF算法，得到它們的請(qǐng)求命中率和字節(jié)命中率。

圖1為4種緩存替換算法的請(qǐng)求命中率比較，GDSF-PRF的請(qǐng)求命中率比其他3種替換算法有明顯提高，尤其在緩存容量占30%時(shí)，GDSF-PRF的請(qǐng)求命中率比位于第二的FIFO提高了30%。

圖1 多種替換算法的請(qǐng)求命中率Fig.1 Request hit ratio of replacement algorithms

圖2為4種緩存替換算法的字節(jié)命中率比較。由圖2可知，GDSF-PRF的字節(jié)命中率僅在緩存容量為10%以下時(shí)，比LRU算法略低，在緩存容量為10%以上時(shí)，字節(jié)命中率比其他3種替換算法有所提高，尤其在緩存容量占30%時(shí)，GDSF-PRF的字節(jié)命中率比位于第二的FIFO提高了32%。

圖2 多種替換算法的字節(jié)命中率Fig.2 Byte hit ratio of replacement algorithms

由實(shí)驗(yàn)結(jié)果可知，當(dāng)用戶訪問(wèn)習(xí)慣符合Zipf規(guī)律時(shí)，其請(qǐng)求命中率和字節(jié)命中率與LRU、FIFO、GDSF比有顯著提高。

4 結(jié) 語(yǔ)

以上比較和分析了LRU、FIFO、GDSF系列算法，在GDSF算法的基礎(chǔ)上，提出了GDSF-PRF算法，然后利用實(shí)驗(yàn)對(duì)比，證明了此算法的有效性。下一步的研究將是在緩存替換發(fā)生之前，增加預(yù)測(cè)模型，通過(guò)預(yù)測(cè)手段進(jìn)一步減小Web服務(wù)器的壓力。