基于高斯混合模型的Web代理服務器緩存替換策略

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

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

0 引言

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

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

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

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

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

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

1 模型概述

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

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

(1)

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

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

(2)

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

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

(3)

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

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

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

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

k=1,2,...,K

(4)

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

(5)

(6)

(7)

4)計算對數似然函數：

(8)

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

2 基于GMM的緩存替換策略

2.1 Web緩存框架

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

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

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

圖1 基于GMM的緩存替換模塊架構圖

算法1：緩存替換算法

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

1. If (Size > Capacity)

2.緩存未命中

3. Get Object // 從代理服務器獲取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尾部節點

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

14.更新CachedSeq

15. End While

16.通過GMM預測得到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 特征提取

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

表1 預處理后的參數列表

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

(9)

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

(10)

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

3 實驗結果與分析

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

3.1 實驗設置

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

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

圖2 循環滑動窗口大小對對象命中率的影響

3.2 性能指標

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

(11)

(12)

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

3.3 性能評估

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

表2 不同聚類算法的訓練時間對比 s

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

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

圖3 數據集1上的HR值和BHR值

圖4 數據集2上的HR值和BHR值比較

4 結束語

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