唐 榜，吳 玨，楊福軍，楊 雷

(1.西南科技大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，四川 綿陽 621000; 2.中國空氣動力研究與發(fā)展中心 計算空氣動力研究所，四川 綿陽 621000)

0 引言

Web緩存技術(shù)通過將Web資源保存在緩存中，減少了網(wǎng)絡(luò)擁塞和服務(wù)器資源的負載，有效地提高了網(wǎng)站的響應(yīng)能力[1]。Web緩存技術(shù)充分利用了時間局部性原理，通過代理服務(wù)器緩存用戶經(jīng)常訪問的 Web 資源，降低了用戶訪問時的頁面響應(yīng)延遲，屬于主動緩存技術(shù)的一種。而緩存替換技術(shù)通過設(shè)定緩存閾值，當(dāng)緩存的大小達到閾值時就會觸發(fā)緩存替換策略，對緩存中的內(nèi)容進行替換。因此，能夠預(yù)測用戶未來可能訪問的資源，并提前將其放入緩存中的緩存預(yù)取技術(shù)得到了廣泛的應(yīng)用[2]。在僅使用緩存替換機制的服務(wù)器中，緩存的容量是制約Web響應(yīng)速度的關(guān)鍵因素，面對大量Web訪問時的緩存命中率一般都比較低。面對有限的緩存空間和大量的Web訪問，基于空間局部性原理的緩存預(yù)取技術(shù)能夠很好地彌補緩存替換算法的局限性，顯著提高了緩存命中率，極大地降低了訪問延遲。

緩存替換算法的準確性是決定緩存替換性能的關(guān)鍵。學(xué)者們對Web訪問數(shù)據(jù)的很多特征進行了廣泛研究，并利用這些特征和特性對Web緩存替換方法進行改進。文獻[3]調(diào)研發(fā)現(xiàn)基于頻率(過去對象的引用次數(shù))、新近度(距最后一次引用所經(jīng)過的時間)、大小(對象的大小)和成本(從服務(wù)器獲取對象的延遲和帶寬成本)的緩存替換方案效果更為理想。

目前，緩存替換算法一般分為兩大類：一類是基于特征統(tǒng)計的方法，典型的有最近最少使用算法(LRU)、最少使用頻次算法(LFU)、貪婪對偶大小算法[4](GDS，greedy dual size)和貪婪對偶大小頻率算法[5](GDSF,GDS-frequency)等。其中，LRU算法會刪除最近最少使用的對象，并將新的對象填入空出的緩存中。LFU算法會使用一個計數(shù)器來計算對象的使用頻率，并刪除最近最不頻繁使用的對象。以上兩種方法只考慮了對象的其中一個數(shù)據(jù)特征來進行緩存替換，適用場景單一，因此準確度較低。而GDS算法考慮了對象的局域性、大小、延遲、替換代價等因素，綜合替換權(quán)值最小的對象。GDSF算法在GDS算法的基礎(chǔ)上加入了頻率因素，改進了GDS算法的性能。另一類是基于預(yù)測的方法，通過機器學(xué)習(xí)模型來預(yù)測會被再次訪問的對象，并提前將其放入緩存中。文獻[6]使用樹樸素貝葉斯分類器對Web數(shù)據(jù)進行分類，預(yù)測可能被再次訪問的Web對象，結(jié)合LRU算法提高了緩存替換的效率。文獻[7]根據(jù)用戶的訪問日志提取多種特征作為訓(xùn)練數(shù)據(jù)集，通過訓(xùn)練SVM分類器將預(yù)測為不會再次訪問的緩存對象刪除以留出緩存空間。文獻[8]提出了一種結(jié)合GDSF算法和支持向量機(SVM)重新訪問概率預(yù)測的Web緩存替換策略。文獻[9]提出了一種用來評估Web對象訪問的空間局部性算法，提高了緩存替換策略的性能。文獻[10]使用隨機索引方法和權(quán)重分配策略機制的Web對象聚類的方法增強Web代理緩存的性能。

而高斯混合模型(GMM，gaussian mixed model)由多個高斯分布函數(shù)線性組合而成，理論上高斯混合模型可以擬合出任意類型的分布，因此在諸多領(lǐng)域都有應(yīng)用。文獻[11]使用神經(jīng)網(wǎng)絡(luò)與GMM相結(jié)合，學(xué)習(xí)點云的生成空間來生成新穎的點云形狀。文獻[12]使用GMM對醫(yī)療文本數(shù)據(jù)進行聚類分析，實現(xiàn)帕金森病的早期預(yù)測。

盡管一些工作使用機器學(xué)習(xí)模型通過固定窗口內(nèi)的訪問頻率等特征對緩存替換模型進行訓(xùn)練，但是由于Web訪問存在較高的時間相關(guān)性，將長時間內(nèi)的訪問頻率及訪問新近性作為特征進行緩存替換的方法，無法較好地捕獲時間序列數(shù)據(jù)所擁有的時間相關(guān)性。而循環(huán)滑動窗口機制在處理時間序列數(shù)據(jù)上能夠起到能夠降低運算量、劃分時間周期的作用[13-14]，提高對時間序列數(shù)據(jù)的處理效果。

基于以上分析，本文采用基于循環(huán)滑動窗口的GMM模型對Web日志數(shù)據(jù)進行聚類分析，結(jié)合LRU緩存替換算法對緩存對象進行替換。利用循環(huán)滑動窗口策略學(xué)習(xí)一段時間內(nèi)的Web訪問數(shù)據(jù)特征，可以更好地捕獲Web訪問數(shù)據(jù)的時間相關(guān)性，從而使模型獲得更好的預(yù)測結(jié)果。在進行緩存替換時，將GMM聚類分析預(yù)測的結(jié)果與LRU算法進行結(jié)合，在保證了較好的計算性能的同時，緩存替換的命中率也比傳統(tǒng)算法更佳。實驗結(jié)果證明了本文方法的有效性。

1 模型概述

高斯混合模型可以看作是由K個單高斯模型組合而成的模型。由于高斯分布具有良好的數(shù)學(xué)性質(zhì)和優(yōu)秀的計算性能，能夠很好地刻畫參數(shù)空間中數(shù)據(jù)的分布及其特性，在擬合數(shù)據(jù)分布時有很強的建模能力，因此在數(shù)據(jù)科學(xué)界被廣泛使用。高斯混合模型結(jié)合了參數(shù)估計法和非參數(shù)估計法的優(yōu)點，并使用了期望最大(EM，expectation maximization)算法進行訓(xùn)練。由于高斯混合模型使用多個高斯分布的組合來刻畫數(shù)據(jù)的分布，在模型中的樣本點足夠豐富的情況下，任意精度上的連續(xù)分布都能被高斯混合模型所擬合。

當(dāng)樣本數(shù)據(jù)是一維數(shù)據(jù)時，高斯混合模型為每個類別下的特征分布都假設(shè)了一個服從高斯分布的概率密度函數(shù)如公式(1)所示：

(1)

其中：μ為數(shù)據(jù)均值(期望)，σ為數(shù)據(jù)標準差(Standard deviation)。

當(dāng)樣本數(shù)據(jù)是多維數(shù)據(jù)(Multivariate)時，高斯分布遵從的概率密度函數(shù)如公式(2)所示：

(2)

其中:μ為數(shù)據(jù)均值(期望)，∑為協(xié)方差(Covariance)，D為數(shù)據(jù)維度。

高斯混合模型包含的K個子模型就是混合模型的隱變量(hidden variable，α1,α2,…,αk)。一般來說，一個混合模型可以使用任何概率分布，這里使用高斯混合模型是因為高斯分布具備很好的數(shù)學(xué)性質(zhì)以及良好的計算性能。因此高斯混合模型的概率分布表示如公式(3)所示：

(3)

對于多維數(shù)據(jù)的每個觀測點來說，由于事先不知道它所屬的分布，因此無法使用最大似然法來求導(dǎo)獲得使最大似然函數(shù)最大的參數(shù)。最大期望算法(expectation maximization algorithm, EM算法)是一種常用的高斯混合模型參數(shù)估計方法, 由Dempster等人于1977年提出，用于求解含有隱變量(Hidden variable)的概率模型參數(shù)的最大似然估計。在初始時隨機生成K個高斯分布，然后不斷地迭代EM算法，直至似然函數(shù)變化不再明顯或者達到了最大迭代次數(shù)為止。因此，本文選擇EM算法作為迭代算法對高斯混合模型的參數(shù)進行求解。

EM算法的迭代更新過程分為如下幾步：

1)初始化參數(shù)：定義分量數(shù)目K，對每個分量k設(shè)置αk,μk和∑k的初始值。

2)E-step：在給定的多維高斯分布下，根據(jù)參數(shù)初始值或上一輪的迭代值來計算對數(shù)似然函數(shù)的期望及后驗概率，計算每個數(shù)據(jù)j來自子模型k的可能性，如式(4)所示：

k=1,2,...,K

(4)

3)M-step：根據(jù)E-step中得到的后驗概率計算新一輪迭代的模型參數(shù)，將似然函數(shù)最大化以獲得新的參數(shù)值。計算過程如下：

(5)

(6)

(7)

4)計算對數(shù)似然函數(shù)：

(8)

5)檢查參數(shù)或者對數(shù)似然函數(shù)是否收斂，若不收斂則返回第2)步。

2 基于GMM的緩存替換策略

2.1 Web緩存框架

圖1展示了基于高斯混合模型的Web緩存替換算法框架。當(dāng)代理服務(wù)器收到用戶的訪問請求后，用戶與代理服務(wù)器進行通信，并將請求記錄保存到日志文件中。代理服務(wù)器將收集的日志構(gòu)建成數(shù)據(jù)集發(fā)送到預(yù)測模塊進行數(shù)據(jù)預(yù)處理和預(yù)測[15]。文獻[16]展示了高斯混合模型結(jié)合時間序列方法在處理具有時間特征的數(shù)據(jù)上有較好的效果。

預(yù)測模塊的作用是將數(shù)據(jù)集中的數(shù)據(jù)進行預(yù)處理，經(jīng)過數(shù)據(jù)過濾和特征提取等方式將得到的數(shù)據(jù)放入GMM預(yù)測模型進行學(xué)習(xí)，預(yù)測數(shù)據(jù)是否應(yīng)該被放入緩存中。而替換模塊的作用是統(tǒng)一管理緩存中的對象，根據(jù)緩存的請求命中情況，對緩存的內(nèi)容進行替換。當(dāng)代理服務(wù)器接收到用戶的訪問請求后，首先在緩存中檢索是否存在用戶請求的對象。若該對象存在，則直接返回給用戶。若該對象不存在，則將請求轉(zhuǎn)發(fā)至源服務(wù)器，獲取到請求對象后由源服務(wù)器將該對象返回給用戶。通過獲取預(yù)測模塊中GMM模型的預(yù)測結(jié)果，結(jié)合LRU緩存替換策略判斷是否將用戶請求的對象拷貝到代理服務(wù)器的緩存中，以提高緩存中Web對象的訪問效率。

本文使用的GMM模型在獲得日志數(shù)據(jù)后通過聚類分析計算每個Web對象被重新訪問的概率，將可能被再次訪問的數(shù)據(jù)替換到代理緩存中。當(dāng)Web對象被標記為可訪問時，結(jié)合其文件大小等特征將其分別放置在替換隊列的不同位置，直到緩存未命中時通過LRU算法進行緩存替換。通過GMM對Web對象的預(yù)測結(jié)果來決定將其放在緩存隊列的位置，以實現(xiàn)更為高效的緩存替換。算法1顯示了基于高斯混合模型的緩存替換算法的具體流程。

圖1 基于GMM的緩存替換模塊架構(gòu)圖

算法1：緩存替換算法

參數(shù)：Size為目標大小，Object為目標地址，CachedSeq為緩存隊列，Capacity為緩存大小，Used_capacity為已使用的緩存大小，Will_visit為是否會再次訪問。

1. If (Size > Capacity)

2.緩存未命中

3. Get Object // 從代理服務(wù)器獲取Object

4. If (Object存在于緩存中)

5.緩存命中

6.將Object移動至CachedSeq的頭部位置

7. End if

8. If (Object不存在于緩存中)

9.緩存未命中

10. End if

11. While (Size + Used_capacity > Capacity)

12.獲取CachedSeq尾部節(jié)點

13.從緩存中刪除尾節(jié)點存儲的Web對象

14.更新CachedSeq

15. End While

16.通過GMM預(yù)測得到Object的Will_visit

17. If (Will_visit=1 && Size < Capacity*0.3)

18.將Object移動至CachedSeq的頭部位置

19. Else if (Will_visit = 1 && Size >=Capacity*0.3)

20.將Object移動至CachedSeq的中間位置

21. End if

22. If (Will_visit=0)

23.將Object移動至CachedSeq的尾部位置

24. End if

2.2 特征提取

在代理服務(wù)器中, 用戶訪問信息會記錄在代理日志中。Web日志文件中包含了多種訪問信息，如用戶IP地址、訪問的URL及端口、請求方式、請求時間，訪問對象字節(jié)大小等。但是數(shù)據(jù)中包含一定數(shù)量的無效數(shù)據(jù)(訪問失敗、地址失效等)，因此需要對數(shù)據(jù)集進行預(yù)處理。一方面，將Web日志文件數(shù)據(jù)集進行了過濾, 去除不相關(guān)的訪問及錯誤的Web請求，抽取有用的數(shù)據(jù)來進行特征提取。另一方面，Web數(shù)據(jù)集的構(gòu)建是從日志代理文件中提取所需的信息，考慮到訪問具有時序性，使用了循環(huán)滑動窗口機制對數(shù)據(jù)集進行了分段處理，從中提取并計算出可以用作聚類分析的特征。經(jīng)過預(yù)處理后的具體參數(shù)如表1所示。

表1 預(yù)處理后的參數(shù)列表

其中：x1表示訪問Web對象的時間，x2表示訪問Web對象的地址，x3表示訪問Web對象的大小，x4表示W(wǎng)eb對象被訪問的頻次，x5表示W(wǎng)eb對象上一次訪問距離現(xiàn)在的時間差，若Web對象首次被訪問，x5會被初始化為-1。以上參數(shù)均從原始數(shù)據(jù)集計算獲得。而x6表示循環(huán)滑動窗口內(nèi)Web對象最近一次訪問的時間間隔 (Recency)，x7表示循環(huán)滑動窗口內(nèi)Web對象的訪問頻次。若Web對象在滑動窗口內(nèi)首次出現(xiàn)，則x6初始化為滑動窗口的長度，x7初始化為1。x6和x7的計算方式如式(9)和式(10)所示：

(9)

x7=max[x7+1,1],ΔT≤SWL

(10)

其中：循環(huán)滑動窗口的長度設(shè)置為SWL，距離上次請求Web對象的時間間隔設(shè)置為ΔT。

3 實驗結(jié)果與分析

在本文的實驗中，采用了由實驗室代理服務(wù)器收集的不同時段的用戶訪問日志數(shù)據(jù)。數(shù)據(jù)集1包含了該站點從17∶00到24∶00收集的約300 000條訪問數(shù)據(jù)，數(shù)據(jù)集2包含了該站點從6∶00到13∶00收集的約130 000條訪問數(shù)據(jù)。在這兩個真實數(shù)據(jù)集上對本文提出的算法與4種傳統(tǒng)緩存替換算法在對象命中率和字節(jié)命中率上進行了比較，驗證了該算法的性能。在聚類算法的選擇上，比較了幾種聚類算法在對本文數(shù)據(jù)集進行聚類時所耗費的時間，證明了GMM模型在進行聚類分析時具有較好的計算性能。

3.1 實驗設(shè)置

用戶的訪問請求被記錄在代理服務(wù)器的日志文件中。當(dāng)?shù)竭_指定時間后，通過統(tǒng)計用戶訪問在緩存空間中的命中次數(shù)來獲取訪問成功的緩存副本。代理服務(wù)器的日志文件中包含了每條訪問記錄的條目，包括以下8個字段：日志標記、客戶端端口號、請求時間戳、HTTP狀代碼、請求和響應(yīng)報文的大小、URL地址、主機名和內(nèi)容類型。本文通過循環(huán)滑動窗口機制對日志數(shù)據(jù)集進行了預(yù)處理，再去除掉非法訪問、無效訪問后的數(shù)據(jù)集。

為了探究循環(huán)滑動窗口的長度對不同時間段獲取的數(shù)據(jù)特征的影響，使用本文的替換算法在1 M的緩存空間下對兩個數(shù)據(jù)集進行了驗證實驗。實驗將滑動窗口長度設(shè)置為0～1 000 s，0 s表示不設(shè)置滑動窗口，即使用全局時間長度來提取數(shù)據(jù)特征。實驗結(jié)果如圖2所示，可以發(fā)現(xiàn)，循環(huán)滑動窗口的設(shè)置在一定程度上提高了緩存替換的對象命中率。而由于時間段不同，用戶訪問頻率也不同，在兩個數(shù)據(jù)集上的滑動窗口長度分別設(shè)置為50 s和200 s時獲得最高的對象命中率。本文在綜合兩個數(shù)據(jù)集的實驗結(jié)果之后，決定統(tǒng)一選擇100 s作為循環(huán)滑動窗口長度來進行后續(xù)實驗。

圖2 循環(huán)滑動窗口大小對對象命中率的影響

3.2 性能指標

對象請求命中率(HR，hit ratio)和字節(jié)命中率(BHR,byte hit ratio)是兩個最常用的用來評估不同算法的緩存性能的測試指標。對象請求命中率是指緩存命中的請求次數(shù)占總請求次數(shù)的百分比，提高對象請求命中率的目的在于減少用戶的響應(yīng)時間。字節(jié)命中率是指緩存命中的請求對象字節(jié)數(shù)占請求對象總字節(jié)數(shù)的百分比。提高字節(jié)命中率的目的則側(cè)重于降低網(wǎng)絡(luò)通訊量，減少網(wǎng)絡(luò)帶寬開銷。對象請求命中率和字節(jié)命中率的計算公式如下：

(11)

(12)

其中:Si為對象i的大小，Qi為命中對象i的請求數(shù)量，N為被訪問的對象集合。

3.3 性能評估

在聚類算法的選擇上，本文綜合比較了K-Means聚類算法、Mini Batch K-Means算法、DBSCAN算法、GMM和Birch[17]算法的計算性能，實驗結(jié)果如表2所示?？梢园l(fā)現(xiàn)GMM聚類算法在面對較大的數(shù)據(jù)集時，計算性能僅次于K-Means算法和Mini Batch K-Means算法。K-Means算法選擇的初始聚類中心是隨機的，在不同實驗中可能產(chǎn)生不同的結(jié)果，不具備可重復(fù)性，因此并不適用于大型Web日志數(shù)據(jù)。Mini Batch K-means算法是K-Means算法的優(yōu)化變種，訓(xùn)練時從數(shù)據(jù)集中隨機抽取數(shù)據(jù)子集來減少計算時間，但是聚類效果也比K-Means算法稍差。DBSCAN算法是一種基于密度的聚類算法，其優(yōu)點是對噪聲魯棒，能很好地擬合不同形狀的數(shù)據(jù)。但是DBSCAN算法的聚類速度較慢，無法滿足Web緩存替換的高效性需求。Birch算法只需一遍掃描數(shù)據(jù)集就能建立CF Tree，并且對噪聲魯棒，聚類速度也比較快。但是對數(shù)據(jù)集的分布要求較高，不適合具有高維特征的數(shù)據(jù)集。而GMM使用均值和標準差進行計算，使得簇的形狀更加靈活。而且GMM給出的是數(shù)據(jù)集中的項分布在不同簇的概率，因此可以對從Web日志數(shù)據(jù)中得到的概率進行進一步的處理，得到更好的預(yù)測效果。因此，綜合考慮了計算速度和Web日志數(shù)據(jù)的特點，本文決定采用GMM來對已訪問的Web日志數(shù)據(jù)進行聚類劃分。

表2 不同聚類算法的訓(xùn)練時間對比 s

本文在兩個數(shù)據(jù)集上使用了LRU、LFU、FIFO和GDSF作為對比算法，與本文提出的緩存替換算法在不同的緩存大小上進行了對比試驗。實驗結(jié)果如圖3、圖4所示。其中，圖3顯示了在數(shù)據(jù)集1上不同緩存大小下，各種替換策略的HR值和BHR值。圖4顯示了數(shù)據(jù)集2上不同緩存大小下，各種替換策略的HR值和BHR值。

觀察模型在兩個數(shù)據(jù)集上的實驗結(jié)果，不難發(fā)現(xiàn)隨著緩存大小的增加，緩存對象命中率和字節(jié)命中率也呈上升態(tài)勢。當(dāng)緩存較小時，各種替換策略的表現(xiàn)相差不大，緩存命中率都比較低。這是因為在緩存較小時，所能承載的緩存對象較少，在面對大量的用戶訪問時經(jīng)常需要進行緩存替換的操作，因此緩存的命中率較低。當(dāng)緩存大小增大時，由于FIFO、LRU和LFU在進行緩存替換時，使用的數(shù)據(jù)特征較為單一，因此即使使用了更多的緩存，其緩存命中率與使用多種特征進行緩存替換的GDSF相比始終處于劣勢。與傳統(tǒng)方法相比，本文提出的基于GMM的緩存替換算法始終有著較高的HR值和BHR值，這說明使用了基于GMM的聚類分析后得到的預(yù)測結(jié)果對緩存內(nèi)容進行替換，有效地提高了緩存的命中率，顯著地改善了Web代理服務(wù)器的緩存效果。

圖3 數(shù)據(jù)集1上的HR值和BHR值

圖4 數(shù)據(jù)集2上的HR值和BHR值比較

4 結(jié)束語

本文提出了一種基于GMM訪問預(yù)測機制的Web緩存替換策略。在原有數(shù)據(jù)的基礎(chǔ)上，使用循環(huán)滑動窗口機制提取時序特征，根據(jù)用戶之前的訪問日志構(gòu)建包含多項特征的數(shù)據(jù)集，利用GMM對數(shù)據(jù)進行聚類分析，預(yù)測當(dāng)前緩存對象是否會再次被訪問。實驗結(jié)果表明,本文提出的緩存替換策略相比于傳統(tǒng)方法具有較高的命中率, 顯著提高了Web服務(wù)器的緩存效果，緩解了網(wǎng)絡(luò)訪問延遲和網(wǎng)絡(luò)擁塞問題。在接下來的研究中，將在本文的基礎(chǔ)上，根據(jù)用戶的訪問行為構(gòu)建用戶興趣模型, 從而得到更全面、更有效的預(yù)測算法。