一種基于緩存對象未來價值的淘汰算法

任 飛， 湯 英， 段翰聰

(1.四川長虹電器股份有限公司， 四川 綿陽 621000；2.電子科技大學(xué) 計算機科學(xué)與工程學(xué)院， 四川 成都 611731)

隨著Internet普及和網(wǎng)絡(luò)應(yīng)用的迅速發(fā)展，從Web Cache到內(nèi)容分發(fā)網(wǎng)絡(luò)(Content Delivery Network，CDN)，再到信息中心網(wǎng)絡(luò)(Information Centric Networking，ICN)和內(nèi)容中心網(wǎng)絡(luò)(Content Centric Network，CCN)，分布式存儲技術(shù)不斷進步，其應(yīng)用也有了顯著的發(fā)展，但也面臨著巨大的挑戰(zhàn)：數(shù)據(jù)分布的地理空間更加廣闊，數(shù)據(jù)存儲容量呈爆炸性增長，數(shù)據(jù)的可靠性要求不斷提高。分布式存儲系統(tǒng)的構(gòu)建必須解決“大規(guī)模、高效率、易擴展、高可靠”等系統(tǒng)性需求問題[1-4]。由于存儲資源的限制，緩存替換策略對于提升文件系統(tǒng)性能尤其重要。一個最優(yōu)化的緩存替換策略是能夠根據(jù)未來價值高低找出最無用的緩存對象，進而淘汰處理，并可降低帶寬開銷和提高用戶體驗。

雖然緩存淘汰算法已經(jīng)有很多研究成果，但都存在一定程度的不足。

(1)研究和應(yīng)用最多的是LRU(Least Recently Used，最近最少使用)算法，將最近最久未被訪問的對象淘汰。由于這種算法只考慮了緩存對象被訪問的時間特性，忽略了對象的大小等其他因素，在塊大小固定的情況下，大多數(shù)計算機系統(tǒng)工作良好，但在某些特殊場合存在很多限制，在訪問大的對象時甚至可能崩潰，因此，不能提供最佳性能[5-7]。

(2)其次，是LFU(Least Frequently Used，最不常用)算法，將訪問頻度最低的緩存對象淘汰。由于這種算法只考慮了對象的被訪問頻次，對那些曾經(jīng)高頻訪問，但近期已經(jīng)過時的對象，也會被長期保留，造成緩存污染[6]。此外，當(dāng)緩存空間總體較小時，LFU算法的性能也會降低[8]。

(3)再次，是SIZE算法，在緩存空間一定時，為確保存儲更多的緩存對象，將占用空間最大的緩存對象淘汰[5-6]。這種算法只考慮了對象的大小，沒有考慮時間和頻率特性，會導(dǎo)致已經(jīng)過時的小的數(shù)據(jù)對象長時間保留在緩存空間，同樣會造成緩存污染。

(4)FIFO(First in First out，先進先出)算法，認為緩存對象中的第一個對象應(yīng)該先被淘汰[7]，于是選擇緩存空間中最早的對象淘汰。這種算法只考慮了對象緩存時長，沒有考慮對象被使用的時間和頻率特性，以及對象的大小，雖然算法簡單，但應(yīng)用價值不大。

(5)兼顧對象被訪問的時間特性和頻率特性的LRFU(Least Recent Frequently Used，最近最不常用)算法[8]，計算每個對象的CRF(Combined Recency and Frequency，最近和頻率組合)值來確定近期被訪問的可能性。CRF值由權(quán)重函數(shù)決定，通過調(diào)整函數(shù)因子尋找最佳性能。雖然LRFU實驗結(jié)果優(yōu)于LRU和LFU策略[8]，但沒考慮對象大小，應(yīng)用領(lǐng)域也存在一定程度的限制。

上述幾種算法都是基于緩存對象被訪問的概率來進行評估的，這也是基于回歸預(yù)測緩存機制的重點。衡量一個緩存對象淘汰算法優(yōu)劣主要有以下3個指標(biāo)[6]：

(1)請求命中率：命中緩存對象的請求數(shù)量與全部請求數(shù)量的比率。

(2)字節(jié)命中率：緩存對象的請求字節(jié)數(shù)與所有請求的字節(jié)數(shù)的比率，這種評價指標(biāo)更適于大對象，因為大尺寸對象被訪問的次數(shù)可能較少，但被訪問后將產(chǎn)生更大的數(shù)據(jù)流量。

(3)響應(yīng)時間：用戶發(fā)送請求和用戶接收響應(yīng)之間的時間。

一個理想的緩存替換策略應(yīng)該最大限度地提高緩存命中率或字節(jié)命中率，并最小化響應(yīng)時間[4-10]。為了實現(xiàn)這一目標(biāo)，本文以使用分片的流媒體系統(tǒng)為研究對象，綜合考慮緩存對象最近的訪問時間、訪問頻次、分片優(yōu)先級和對象大小等因素，提出一種基于最小未來價值(Least Future Value，LFV)的緩存淘汰算法，改進現(xiàn)有算法中存在的一些缺點，如抖動現(xiàn)象、緩存污染等，提升緩存性能。

1 設(shè)計思路

關(guān)鍵問題是如何確定一個緩存對象的價值。如果價值預(yù)測錯誤，可能出現(xiàn)抖動現(xiàn)象，即一個緩存對象被淘汰以后馬上被請求，從而再次被緩存。理想情況下，在不久的將來被訪問的價值應(yīng)該比不被訪問的價值大。

對象被訪問的概率和對象的尺寸決定了對象未來的價值，對象未來的價值與被訪問概率正相關(guān)，與對象的大小負相關(guān)，即被訪問的概率越大其未來的價值就越大，對象的尺寸越小其未來價值越大(因為當(dāng)存儲空間一定時，對象尺寸越小，可存儲的對象數(shù)量就越多，請求的命中率就越高，存儲空間的價值越大)。一般情況下，我們是知道緩存對象的尺寸大小的，需要做的是確定對象被訪問的概率。因此，基于LFV的緩存對象淘汰算法主要包括兩部分：預(yù)測被訪問的概率，規(guī)范緩存對象的大小。

(1)利用統(tǒng)計回歸分析方法預(yù)測被訪問的概率。首先，計算當(dāng)前n個時刻的訪問概率；然后，建立指數(shù)回歸模型，并根據(jù)最小二乘原理計算兩個待定參數(shù)；最后，根據(jù)指數(shù)回歸模型預(yù)測對象在第n+1時刻被訪問的概率。

(2)規(guī)范緩存對象的大小。假設(shè)緩存對象的尺寸太大而導(dǎo)致對象數(shù)量較少，對象的命中率將受到一定程度的影響。因此，在預(yù)測訪問概率之前，每個緩存對象的尺寸大小需要規(guī)范化，將所有對象的尺寸大小控制在一定范圍內(nèi)。本文采用歸一化方法對緩存對象進行規(guī)范化處理，采用權(quán)重函數(shù)來計算緩存對象的歸一化尺寸大小。這樣，對于確定的緩存空間，對象的數(shù)量將由對象歸一化尺寸大小決定。

本文基于MATLAB進行算法開發(fā)、數(shù)據(jù)可視化、數(shù)據(jù)分析以及數(shù)值計算，文中所有截圖示例均為MATLAB的輸出結(jié)果。

2 概率預(yù)測

2.1 當(dāng)前概率計算

用戶的訪問請求屬于隨機事件，緩存對象在周期內(nèi)被訪問的次數(shù)也是隨機的，緩存對象的訪問概率也具有很大隨機性。為便于計算和記錄每個緩存對象最近N次被訪問的統(tǒng)計概率值p，我們?yōu)槊總€對象建立和維護了一個N元數(shù)組[p1,p2,p3,…,pN]。

定義1 設(shè)Δt為給定時間t附近的時間區(qū)間長度，某緩存對象α1在(t-Δt,t)被訪問的概率為pt，REHt為對象α1在Δt內(nèi)被訪問的次數(shù)(Request Hits)，TORt為用戶在Δt內(nèi)發(fā)出的總的請求次數(shù)(Total Requests)，則pt表示為

pt=REHt/TORt。

(1)

設(shè)定一個合適的Δt值對于公式(1)的使用尤為重要。因為，數(shù)據(jù)的連續(xù)性決定了回歸分析結(jié)果的可信度。數(shù)據(jù)的連續(xù)性即所有的數(shù)據(jù)都可以繪制在光滑曲線附近，越接近光滑曲線表示數(shù)據(jù)的連續(xù)性越強，預(yù)測結(jié)果越理想。可以通過選取合適的Δt來保證數(shù)據(jù)的連續(xù)性。

圖1 Δt的3種選擇方案

圖2 選擇不同Δt時的數(shù)據(jù)分布

設(shè)采樣周期的大小為T，δ表示Δt和T的重疊情況，即δ=Δt-T。Δt的3種可能的選擇方案如圖1所示。

當(dāng)δ<0時，即在相鄰Δt間存在一定時間間隔，如前所述，對象的訪問是一種隨機事件，相鄰Δt間的數(shù)據(jù)可能存在巨大差異，數(shù)據(jù)的連續(xù)性無法保證。

當(dāng)δ=0時，相鄰Δt首尾相接，同樣存在相鄰間隔內(nèi)數(shù)據(jù)差異性大的問題，數(shù)據(jù)連續(xù)性仍無法保證。

當(dāng)δ>0時，相鄰Δt部分重疊，數(shù)據(jù)的連續(xù)性可以在一定程度上得到保證，數(shù)據(jù)連續(xù)性的強弱可能通過調(diào)整重疊部分的大小δ來實現(xiàn)，δ越大，數(shù)據(jù)越連續(xù)。

選擇不同的Δt值時，如圖2所示，用戶請求數(shù)據(jù)的分布變化不大，但是，Δt越大曲線越平滑，回歸分析效果越好。

為了定量分析光滑特征，消除單位和(或)平均數(shù)不同對兩個或多個曲線變異程度比較的影響，比較其變異程度就不能采用標(biāo)準(zhǔn)差，而需采用標(biāo)準(zhǔn)差σ與平均數(shù)μ的比值來比較。標(biāo)準(zhǔn)差與平均數(shù)的比值稱為變異系數(shù)，記為CV(公式表示為CV=σ/μ)，反映單位均值上的離散程度。通過計算3條曲線的變異系數(shù)CV，結(jié)果如表1所示，當(dāng)δ>0，即Δt>T時，CV最小，曲線最平滑。因此，選擇Δt>T。

表1 3條曲線的CV值

考慮實施的復(fù)雜性，在每個采樣周期T中記錄用戶請求次數(shù)是容易的，如果Δt等于采樣周期T的整倍數(shù)，例如2T、3T等，則公式(1)的計算將更容易。假設(shè)Δt=2T，即相鄰Δt重疊長度δ=T(重疊率50%)，數(shù)據(jù)的連續(xù)性得到保證的同時，實現(xiàn)也較為簡單。

2.2 回歸預(yù)測

訪問概率隨時間而變化，很難預(yù)測在未來某一時刻訪問的準(zhǔn)確概率，未來某一時刻的概率只能根據(jù)過去的數(shù)據(jù)和行為來近似估計，本文使用回歸分析方法來預(yù)測?；貧w分析的關(guān)鍵是選擇一個近似回歸模型，近似的標(biāo)準(zhǔn)是最大化相關(guān)系數(shù)。

2.2.1 相關(guān)分析

相關(guān)分析即研究自變量與因變量之間的關(guān)聯(lián)度，是回歸分析的前提。本文以時間t為自變量，訪問概率p為因變量。關(guān)系包括線性關(guān)系和曲線關(guān)系(也稱非線性關(guān)系)，時間與訪問概率之間的關(guān)系是一種曲線關(guān)系，關(guān)系的判斷標(biāo)準(zhǔn)是相關(guān)系數(shù)R。

(2)

對于曲線關(guān)系模型，相關(guān)系數(shù)的計算，第一步是確定回歸方程，然后根據(jù)公式(2)計算相關(guān)系數(shù)R。R反映了因變量p和自變量t之間的密切程度，R越大，回歸預(yù)測越有意義。

2.2.2 選擇合適的回歸模型

圖3 泊松分布和實時數(shù)據(jù)

一個好的回歸模型應(yīng)該具有更大的相關(guān)系數(shù)。曲線的相關(guān)系數(shù)越大，曲線越接近真實數(shù)據(jù)。常見的曲線回歸模型包括指數(shù)曲線、對數(shù)曲線、雙曲線、冪函數(shù)曲線、S曲線、高階方程等。較可靠的方法是計算所有曲線回歸模型的相關(guān)系數(shù)，然后選擇具有最大相關(guān)系數(shù)的模型，但是，這種方法的計算成本太高。一種合理的假設(shè)就是單位時間內(nèi)的請求數(shù)服從泊松分布[9]。圖3顯示的用戶請求數(shù)據(jù)分布類似于標(biāo)準(zhǔn)泊松分布。

定義2 設(shè)p為訪問概率，q、m為待定參數(shù)，則指數(shù)模型可定義為

p=qemt。

(3)

2.2.3 模型轉(zhuǎn)換

通過變量代換將公式(3)表示的指數(shù)回歸模型轉(zhuǎn)化為線性回歸模型。對公式(3)的兩邊取對數(shù)，并設(shè)y=lnp和b=lnq，而進行變量代換后得到一元線性回歸模型：

(4)

由b=lnq得q=eb，式(3)可變換為

(5)

當(dāng)確定了m和b的參數(shù)值，就可以根據(jù)公式(5)進行概率預(yù)測。接下來的工作就是確定參數(shù)m和b的值。

2.2.4 回歸分析

待定參數(shù)m和b可以通過最小二乘法估計確定，即找到合適的m和b使殘差平方和最小。計算殘差項平方和的公式為

(6)

根據(jù)最小二乘法原理，當(dāng)m和b的偏導(dǎo)數(shù)分別為0時，φ達到極小值：

(7)

解方程組(7)得到：

(8)

2.2.5 概率預(yù)測

確定了參數(shù)m和b的值后，可以根據(jù)公式(5)預(yù)測下一時刻tn+1的對象被訪問的概率：

pn+1=eb+mtn+1。

(9)

2.2.6 回歸規(guī)模

在上述回歸分析中，對于每個對象基于前n個時刻(t1,t2,…,tn)的已知數(shù)據(jù)(p1,p2,…,pn)預(yù)測下一時刻tn+1的訪問概率pn+1，n代表回歸規(guī)模，回歸結(jié)果的精度與n的大小緊密相關(guān)。n如果取得太小，回歸精度將下降，如果取得太大，雖然回歸精度較高，但內(nèi)存和CPU等計算資源消耗太大，會影響到系統(tǒng)效率。

2.3 緩存淘汰

當(dāng)緩存空間不足或者系統(tǒng)定時器觸發(fā)的緩存淘汰時，預(yù)測每個緩存對象的未來價值，并選擇一定比例的未來價值最小的緩存對象進行淘汰。

2.3.1 未來價值估算

(10)

2.3.2 優(yōu)先因子設(shè)定

在使用分片的流媒體系統(tǒng)中，文件被分成若干個分片(chunk)[11-15]，針對流媒體分片的優(yōu)化在公式(10)中設(shè)置了優(yōu)先級因子α，針對不同的分片可以設(shè)置不同的優(yōu)先級。對流媒體的請求總是從第一個分片開始的，第一個分片的訪問概率最大，因此，如果對第一分片給以最高優(yōu)先級因子α值，用戶請求的響應(yīng)時間可以大幅降低，系統(tǒng)的響應(yīng)效率也可以得到改善。比如，將首分片的α值設(shè)為1，其他分片的α值設(shè)定在0.6～0.8之間。

另外，訪問概率p對未來價值fv估算起主導(dǎo)作用，優(yōu)先級因子α的作用不應(yīng)超過訪問概率p。

2.3.3 對象大小規(guī)范化處理

(11)

2.3.4 緩存淘汰過程

緩存淘汰的具體過程如下：

步驟1：按公式(11)對所有對象大小進行預(yù)處理，在整個過程中只有一次；

步驟2：按公式(1)計算當(dāng)前各個時刻t所有對象的訪問概率pt(如前所述，計算時選擇Δt等于采樣周期T的整倍數(shù))；

步驟3：按公式(4)的變量代換關(guān)系計算所有對象訪問概率對應(yīng)的y值；

步驟4：按公式(8)計算參數(shù)m、b的值；

步驟5：按公式(9)預(yù)測所有對象下一時刻的訪問概率；

步驟7：在fv最小的緩存對象中，選擇一定比例(比如20%)來執(zhí)行淘汰操作。

3 仿真實驗

3.1 復(fù)雜性分析

執(zhí)行緩存淘汰操作，需要針對每個緩存對象計算其fv。fv的主要計算量是公式(8)，當(dāng)確定了回歸規(guī)模后，則n為一常數(shù)，因而，該算法的時間復(fù)雜度為O(x)，x為緩存空間內(nèi)的緩存對象的數(shù)量，表明本算法的時間復(fù)雜度與緩存空間中的對象數(shù)量是線性階的。

3.2 仿真結(jié)果

本文設(shè)計了一個模擬器來測試和驗證該算法，并與其他兩個淘汰算法：LRU和LP(Least Popularity，最小流行度)進行比較[10-11]，LP是最小流行度的緩存對象的淘汰。由于本文把流媒體文件分成大小相同的對象，除了最后一個對象可能要小一些，大部分對象具有相同的大小，字節(jié)命中率和緩存命中率是非常相似的。因此，本文主要對緩存命中率、訪問時延，以及磁盤空間、內(nèi)存和帶寬等重要資源使用情況進行了計算和分析。

模擬器的輸入數(shù)據(jù)是運營商網(wǎng)絡(luò)中的業(yè)務(wù)數(shù)據(jù)，包括何時、哪些流媒體文件被請求、開始時間和結(jié)束時間。為了方便描述，將本文的緩存淘汰算法稱為最小未來價值算法。圖4展示了以1 min為周期3種算法的緩存命中率的比較，緩存命中率即將命中緩存對象(即分片)的請求數(shù)量除以所有請求數(shù)量。

根據(jù)圖4，LFV在大多數(shù)時間比其他兩種算法具有更高的命中率，這意味著保存的文件比在LFV淘汰的文件更有價值，可能的原因是LFV不僅考慮歷史數(shù)據(jù)，還考慮了變化趨勢，因此，它可以更準(zhǔn)確地預(yù)測訪問概率。

圖5展示了3種算法的用戶訪問時延的比較。計算實際用戶訪問時延比較困難，本文以使用服務(wù)器之間的hop數(shù)來近似計算。例如，0跳意味著用戶請求的文件在緩存服務(wù)器中，并且可以立即發(fā)送給用戶，2跳意味著請求的文件將要從一個文件服務(wù)器傳輸?shù)骄彺娣?wù)器。

圖4 3種淘汰算法的緩存命中率結(jié)果 圖5 3種算法用戶訪問時延比較

圖6 3種算法磁盤空間使用結(jié)果

根據(jù)圖5，在開始時，3種算法對于沒有足夠的緩存文件具有相似的訪問時延，但是隨著時間的推移，LFV的接入時延變得比其他兩個小。

圖6顯示了3種算法對磁盤空間使用情況的比較，從圖中可以看出，因為算法的差異導(dǎo)致LFV與其他兩條曲線存在一定的差異，但3條曲線表現(xiàn)出的走勢相似，即他們對磁盤空間使用情況是相似的，表明3種算法的平均空間使用率無顯著性差異。

圖7顯示了3種算法對內(nèi)存資源使用情況的比較，從圖中可以看出，LFV比其他兩種算法消耗了更多的內(nèi)存資源，因為LFV為每個緩存對象記錄了n個概率(n為某個整數(shù))，而其他兩種算法只為每個緩存對象記錄一個參數(shù)。

從圖8看出，3種緩存淘汰算法的帶寬使用情況非常接近，表明LFV對于減少帶寬消耗是有限的。

圖7 3種算法的內(nèi)存使用情況比較 圖8 3種算法的帶寬使用情況比較

4 結(jié) 論

與現(xiàn)有LRU、LFU、SIZE等算法相比，本文提出基于回歸預(yù)測模型的LFV緩存替換策略具有3個顯著的優(yōu)點：第一，避免緩存污染問題，只有最近n個時間間隔內(nèi)的請求才會影響下一個緩存對象的淘汰；第二，不僅表達了緩存對象的流行度，而且表達了流行度的變化趨勢，這是更有用的，例如，一些對象在最近n個時間間隔內(nèi)有很大的訪問概率，但是數(shù)據(jù)出現(xiàn)了一個意外的下行曲線，那么預(yù)測的概率將遵循下行曲線；第三，可以通過提高第一個分片的優(yōu)先級，使用戶請求的響應(yīng)時間大幅降低，系統(tǒng)響應(yīng)效率得以大幅提升。

實驗數(shù)據(jù)表明，基于回歸預(yù)測模型的LFV緩存替換策略比其他的緩存替換算法具有更高的命中率，但是犧牲了更多的系統(tǒng)資源，如內(nèi)存。換句話說，這個算法用內(nèi)存資源換來了預(yù)測精度。

對這一領(lǐng)域的研究，未來將嘗試建立比泊松分布更多的其他回歸模型，去尋找最優(yōu)模型。此外，必須在實際工作負載中進行廣泛的實驗，以充分利用多種模式之間的實際性能。