貪婪雙尺寸頻率算法的優(yōu)化與改進

黎慧源 ，易國洪*，代 瑜 ，馮智莉

1.智能機器人湖北省重點實驗室（武漢工程大學），湖北 武漢 430205；2.武漢工程大學計算機科學與工程學院，湖北 武漢 430205

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

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

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

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

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

1 相關工作

1.1 緩存替換算法的性能指標

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

1）請求命中率

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

2）字節(jié)命中率

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

3）平均訪問延遲

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

1.2 GDSF算法

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

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

1.3 已有的GDSF改進算法

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

從時間角度來看，文件再次被訪問的可能性隨時間的延長而降低。因此在計算對象保留價值時，還應考慮對象的時間價值。GDSF算法雖然考慮了文件的訪問頻率但是沒有考慮時間因素。因此，有研究者引入了平均訪問頻度的概念，提出了GDSF-T（Greedy-Dual-Size-Frequency-Time）算法［17］。

定義在時間距離t內，Web訪問對象i的平均訪問頻度為：

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

2 GDSF-PRF算法設計

2.1 頻率因素的改進

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

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

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

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

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

2.2 GDSF-PRF算法描述

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

L為膨脹因子，初值為0，當緩存中有Web對象被替換出去時，L都會被重新賦值為那個被替換出去的對象的H(i)。

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

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

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

Begin

輸入：要訪問的文件d

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

while 緩存空閑大?。糞ize（d）

計算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ù)的設定

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

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

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

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

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

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

3 實驗與分析

3.1 實驗環(huán)境

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

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

3.2 實驗數(shù)據(jù)與參數(shù)設置

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

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

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

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

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

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

3.3 多種替換算法對比實驗

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

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

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

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

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

由實驗結果可知，當用戶訪問習慣符合Zipf規(guī)律時，其請求命中率和字節(jié)命中率與LRU、FIFO、GDSF比有顯著提高。

4 結 語

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