流媒體文件緩存替代算法研究

流媒體文件緩存替代算法研究

1代理服務器存儲及服務模型由于格式轉(zhuǎn)換的適應性、連續(xù)性和高傳輸帶寬的要求，基于網(wǎng)絡代理技術(shù)的開發(fā)需要到附近用戶提供服務，這可以減少網(wǎng)絡過載的影響，降低用戶服務的延遲，導致大規(guī)模研究。此外，基于緩沖矩陣數(shù)據(jù)的粒度，這些工作可分為兩類：部分緩沖區(qū)和全部復制。部分緩沖區(qū)是指基于堤岸噪聲傳播的流媒體文件的一部分數(shù)據(jù)，例如，段、訪問間隔、文件序列、層等。它不包含整個流媒體文件。整體復制是指代理服務器以某種方式處理傳播的流媒體文件的一部分數(shù)據(jù)，例如，不連續(xù)噪聲組、連續(xù)噪聲組（塊）、段、訪問間隔、文件目錄之前、層和其他粒度的流媒體文件，而不包含整個流媒體文件。整體復制是指代理服務器在繼承熱點流媒體文件的基礎(chǔ)上實現(xiàn)的復制。圖1清晰地給出了基于代理技術(shù)的互聯(lián)網(wǎng)流媒體服務模型,其中,Si(i=1,2,3)是流媒體文件服務器,Proxy是代理服務器,用戶(User)通過代理服務器享受流媒體服務.若用戶需要的流媒體數(shù)據(jù)在代理服務器中沒有被緩存的話,需要從遠端服務器中獲取,這個數(shù)據(jù)可以直接或是經(jīng)過代理服務器送達用戶.可以想象代理服務器的緩存問題對于這個服務模型的性能影響的重要程度.緩存什么以及當緩存滿時替換出什么是緩存問題的研究內(nèi)容,通常稱前者為緩存準入問題,后者為緩存替代問題.代理服務器可以采用部分緩存、整體復制或是兩者的組合以改善基于流媒體文件的互聯(lián)網(wǎng)流媒體服務系統(tǒng)的性能,本文考慮代理服務器整體復制緩存的替代策略問題.1.1自適應的循環(huán)訪問模式設(shè)計緩存替代策略實際上就是給當前緩存中的對象一個使用價值排名,然后依次替換出使用價值最小者直至可用空間能容納下要緩存的對象.其中,價值函數(shù)的設(shè)計是問題的關(guān)鍵,它對緩存命中率(hitrate)、緩存字節(jié)命中率(bytehitrate)等性能指標有很大的影響.對價值函數(shù)的設(shè)計最有影響的當數(shù)資源訪問的局部性原理.所謂資源訪問的局部性原理是指最近被訪問的資源在不久的將來可能再次被訪問,該原理對緩存技術(shù)、復制技術(shù)以及預抓取技術(shù)有深遠影響.比如,LRU(LeastRecentlyUsed)策略總是替換最久沒有被使用的資源,認為最近被使用者有很高的(未來)使用價值,其價值函數(shù)可以用式(1)表達.其中,?i(t)表示資源i在緩存替代請求時刻t被估計的未來使用價值,t1是最近一次訪問資源i的時刻.?i(t)=1/(t-t1)(1)另一個對價值函數(shù)設(shè)計較有影響的因素是資源的訪問頻率.比如LFU(LeastFrequentlyUsed)總是替換出使用頻率最小的資源,認為資源的使用頻率越高,未來的使用價值越大.不幸地是LFU存在緩存污染(cachingpollution)問題(過去曾被多次使用的對象即便不再被使用仍占據(jù)著緩存空間)、LRU存在長環(huán)模式問題(由于緩存大小小于資源的重用模式長度,存在資源剛被替換出緩存又被請求使用的情況).鑒于此,EELRU試圖偵測循環(huán)訪問模式的長度,以自適應選擇替換出的對象,而最近較有影響的工作應該是LRU-K.它將訪問頻率和訪問的最近性綜合到價值函數(shù)的設(shè)計之中,具有較好的性能.隨著計算機應用的廣泛深入,緩存問題也從緩存對象具有相同大小、在高速緩存和內(nèi)存中進行緩存的問題,演變到緩存對象具有不同大小、在內(nèi)存或外存中進行緩存的問題.被緩存的對象也從同一系統(tǒng)中的單一部件,演變到來自于網(wǎng)絡中的不同計算機.比如:網(wǎng)頁的代理服務器緩存問題,需要考慮緩存對象的大小、來源于不同網(wǎng)站的緩存對象(頁面)的費用等問題.類似地,在數(shù)據(jù)網(wǎng)格系統(tǒng)中的文件緩存問題也要考慮這些因素.通常,這類價值函數(shù)有如式(2)的形式,其中,Ci(t)是從網(wǎng)絡中獲得資源i的估計費用,Sizei是資源i的大小,Pi(t)是資源i的未來使用概率的估計.Ci(t)可以使用上一次獲得資源i的費用或是累計平均等進行估計,而Pi(t)的估計仍是采用類似LRU,LFU和LRU-K等的價值函數(shù)設(shè)計方法.比如,LCB-K對Pi(t)的估計就是綜合了LFU和LRU-K的估值思想.?i(t)=Pi(t)×Ci(t)/Sizei(2)這些相關(guān)工作的問題共性在于:假定了緩存對象的整體有用性,即緩存對象被使用時是一個不可分割的整體.然而,本文探討的流媒體整體復制緩存替代問題存在其特殊性,即我們注意到了一個流媒體文件對用戶來說并非總是全部有用,用戶的播放器可能僅使用了部分的媒體文件數(shù)據(jù)作為輸入(比如,用戶沒有從頭看到尾,而是看了自己喜歡的片斷等).1.2各變量在文件文本文本用量性下的性能差異我們注意到請求進入復制緩存的對象是一個文件整體,而這個文件服務用戶時又是以流的方式,讓用戶“邊下載邊播放”并且用戶可能在任意媒體位置上停止使用.這就是說,媒體文件并不是整體有用,而是部分有用,應該對文件i占據(jù)的緩存字節(jié)數(shù)所帶來的價值進行評估,定義為文件i的字節(jié)有用性并記為ξi(t).舉例來說,設(shè)對流媒體文件i訪問了3次,第1次訪問停止在Sizei/3處,第2次訪問停止在Sizei/2處,第3次訪問停止在Sizei/4處,則文件i的字節(jié)有用性可估計為ξi(t)=1/3+1/2+1/4=13/12.基于文件字節(jié)有用性,本文提出了BB,BBLRU-K和BBLCB-K三個流媒體復制緩存替代算法,仿真實驗表明:BBLRU-K和BBLCB-K算法隨著K值的增加,性能指標值均趨于更好,尤其是當K=2時,性能指標值的增長幅度最大;在BB算法與LFU和LRU算法的比較中,發(fā)現(xiàn)BB算法的性能最優(yōu);在LRU-2,LCB-2,BBLRU-2,BBLCB-2和BB算法的性能比較中,BBLCB-2算法的平均性能最優(yōu),但當緩存容量較小時,BB算法性能最優(yōu).然而由于BBLCB-2算法需要考慮訪問的局部性、訪問頻率和字節(jié)有用性,使得平均性能非常接近BBLCB-2算法的BB算法顯得更為簡單有效,因為BB算法只使用了字節(jié)有用性.可見,字節(jié)有用性概念對流媒體復制緩存替代策略設(shè)計的有效性.本文后續(xù)如下組織:首先對復制緩存的替代問題建立模型并通過分析得到了相應的緩存替代算法模型,然后探討價值函數(shù)參數(shù)的估算問題并給出了幾個緩存替代算法,進一步地又通過仿真試驗分析比較研究了這些算法的性能,最后總結(jié)全文及指出下一步的工作.2流遺產(chǎn)保存算法2.1緩沖替代策略假定正在使用的流媒體文件不允許被替換出緩存,設(shè)緩存替代請求時刻為t,此時流媒體文件集合為DataSet(t)={1,2,…,n},Sizei是文件i(i∈DataSet(t))的大小;估計文件i以后會被使用的概率為Pi(t),估計以后將文件i從最近的服務器中檢索出來、傳輸并完全進入緩存中的費用為Ci(t);緩存容量上限為B;流媒體文件i時刻t后占據(jù)的緩存容量為δi(t)×Sizei,δi(t)∈{0,1},δi(t)=0表示文件i不在緩存中,δi(t)=1表示文件i在緩存中.為了最小化t時刻后,用戶請求的平均響應延遲,則應確保:當緩存不命中時,平均需要付出的費用最小.因此,在時刻t,一個理想的緩存替代策略執(zhí)行后應為最小化:∑k∈DataSet(t)&δk(t)=0Ρk(t)×Ck(t)(3)∑k∈DataSet(t)&δk(t)=0Pk(t)×Ck(t)(3)約束條件:n∑i=1δi(t)×Sizei≤B(4)∑i=1nδi(t)×Sizei≤B(4)然而,求解該NP完全問題并不存在有效的算法.若進一步假定流媒體文件的大小遠小于緩存容量B,則可以忽略緩存最大數(shù)量的文件后剩余的空間,于是理想的緩存替代策略變?yōu)樽畲蠡?∑k∈DataSet(t)&δk(t)=1Ρk(t)×Ck(t)(5)∑k∈DataSet(t)&δk(t)=1Pk(t)×Ck(t)(5)約束條件:n∑i=1δi(t)×Sizei≈B(6)∑i=1nδi(t)×Sizei≈B(6)求解該問題的最優(yōu)化算法就是:按照Pk(t)×Ck(t)/Sizek非遞增排序DataSet(t)集中的元素,然后從頭依次選擇要緩存的流媒體文件直到式(4)剛好滿足.這意味著在當前δ值為1的流媒體文件集合中找出淘汰者就是按照式(7)進行非遞增排名,然后從最小值者逆序開始釋放緩存,直到可用緩存滿足要求.?i(t)=Pi(t)×Ci(t)/Sizei(7)可見,緩存替代策略實際上就是給當前緩存中的對象一個使用價值排名,然后依次替換出使用價值最小者直至可用空間能容納下要緩存的對象.?i(t)被稱為(使用)價值函數(shù).如何設(shè)計有效的價值函數(shù)成為解決問題的關(guān)鍵,它對緩存命中率(hitrate)、緩存字節(jié)命中率(bytehitrate)等性能指標有很大的影響.所謂緩存命中率是指在緩存中發(fā)現(xiàn)所需對象的次數(shù)與總的請求次數(shù)之比,字節(jié)命中率指通過緩存命中的字節(jié)數(shù)與總的請求字節(jié)數(shù)之比.2.2關(guān)于相對時間的估計上節(jié)模型化流媒體文件“整進整出”緩存的替代問題(即流媒體文件以一個不可分割的整體進入緩存或是被替換出緩存,且若正在被使用的話,不允許被替換出緩存)之后,得到了復制緩存替代策略,但它只是一個算法模型.公式(7)中參數(shù)的不同估計得到不同的替代算法實例.在Pi(t),Ci(t)和Sizei這3個參數(shù)中,Sizei的確定沒有什么難度,Ci(t)可以使用上一次緩存流媒體文件i的費用或是累計緩存文件i的平均費用等進行估計,最難的就是Pi(t)的估計.由于對未來訪問序列的不可先知性,估計Pi(t)顯然只能根據(jù)過去的訪問序列預測.圖2給出了文件i的歷史訪問序列例.可以看到自t3時刻訪問過文件i以來,在t2和t1時刻又有兩次訪問,現(xiàn)在是緩存替代請求時刻t,需要估計Pi(t).由于對任意文件i的訪問假定獨立且服從參數(shù)為λi(t)的泊松過程通常是有效的,所以可用式(8)估計Pi(t):Ρi(t)=λi(t)/n∑j=1λj(t)(8)Pi(t)=λi(t)/∑j=1nλj(t)(8)問題是又如何估計λi(t)呢?盡管LRU-K,LCB-K的估計方法表現(xiàn)出良好的性能特點,但是它們估計λi(t)的方法是基于格林威治時間尺度,而基于相對時間(timescalerelativity)的方法,在Jiang和Smaragdakis的研究中表現(xiàn)出更好的合理性.其原因在于,絕對時間尺度可能與資源的重用概率毫不相關(guān),而相對時間可以確保這種相關(guān)性.我們認為這種不相關(guān)性在以硬盤作為緩存空間并且緩存從不歸零的應用背景中是非常大的,所以選擇相對時間刻度估計λi(t).所謂相對時間研究方法是指一個研究中使用的時間粒度(刻度)僅應反映出研究對象之間至關(guān)重要的事件特征.對于文件訪問序列來說,則可用資源i自從本次被訪問之后又有多少個其它不同的資源被訪問來作為此次訪問發(fā)生的時刻.舉例來說,記最近對資源i的逆數(shù)第m次訪問時刻為ti(m),設(shè)有DataSet(t)={1,2,3,4,5},最近的訪問歷史序列為:{…,1,4,2,3,2,1,4,1,5},則有t5(1)=0,t5(2)=∞,t1(1)=1,t1(2)=1,t1(3)=3,t4(1)=2,t4(2)=3等等.LIRS,EELRU就是使用這種相對時間技術(shù).類似LRU-K和LCB-K估計λi(t)的思想,使用這種相對時間技術(shù),可以得到如式(9)所示的λi(t)估值公式,其中,K是常數(shù).顯然,當K=1時,式(9)表達的就是LRU策略在上述相對時間意義下的λi(t)估值方式.通常這類估計λi(t)的方法被稱為基于訪問的局部性原理,λi(t)也常被稱為資源i訪問的最近性(recency)估值.另一類估計λi(t)的方法以LFU為代表,認為訪問頻率高的資源將來被訪問的概率也高,把資源的訪問頻率gi(t)用于估計λi(t).LCB-K等則是把資源i訪問的最近性和訪問頻率同時用于估計λi(t).λi(t)=Κ/Κ∑m=1ti(m)(9)λi(t)=K/∑m=1Kti(m)(9)讓流媒體文件“整進整出”緩存,那么該緩存替代問題區(qū)別于諸如網(wǎng)頁緩存替代問題的地方在哪呢?我們注意到:用戶在享受某個媒體流服務時,可能在任意媒體位置上停止使用.這就是說,媒體文件并不是整體有用,而是部分地有用,應該對文件i占據(jù)的緩存字節(jié)數(shù)所帶來的使用價值進行評估,定義為文件i的字節(jié)有用性并記為ξi(t).舉例來說,設(shè)對流媒體文件i訪問了3次,第1次訪問停止在Sizei/3處,第2次訪問停止在Sizei/2處,第3次訪問停止在Sizei/4處,則文件i的字節(jié)有用性可估計為ξi(t)=1/3+1/2+1/4=13/12.可形式描述該概念如下:設(shè)對流媒體文件i共訪問了g次,在第h次播放過程中(不管流媒體服務是否支持VCR操作),我們用xi(h,j)表示文件i第j字節(jié)是否曾是解碼器的輸入,即xi(h,j)={1,第j字節(jié)進入過解碼器0?否則,則文件i的字節(jié)有用性ξi(t)=[g∑h=1Sizei∑j=1xi(h,j)]/Sizei.在實際系統(tǒng)中,可以采用rp·Lh來估算Sizei∑j=1xi(h,j),其中,rp是流媒體文件i的(平均)播放速率,Lh是第h次播放持續(xù)的時間.2.3基于性能分析的判斷函數(shù)如前文所述,不同的λi(t)估計得到不同的替代算法.比如,將式(8)和(9)代入價值函數(shù)(7)中,得到如式(10)所示的價值函數(shù)實例,我們?nèi)苑Q其對應的替代算法為LRU-K.?i(t)=1Κ∑m=1ti(m)×Ci(t)Sizei(10)表1給出了本文要考察的幾個替代算法所用的估值函數(shù).當K=1時,LRU-1算法就是傳統(tǒng)的LRU算法.LFU和LRU的簡單性、LRU-K和LCB-K在相關(guān)工作問題模型中表現(xiàn)的良好性能使得它們成為我們下一節(jié)性能研究比較的合適對象.類似LFU只考慮訪問頻率、LRU只考慮最近性,我們把只考慮字節(jié)有用性的算法定義為BB替代算法,同時鑒于LRU-K和LCB-K在相關(guān)工作的性能表現(xiàn),提出了BBLRU-K和BBLCB-K算法.3仿真實驗性能引入字節(jié)有用性到價值函數(shù)中,對緩存命中率和緩存字節(jié)命中率的影響如何是該節(jié)要考慮的問題.我們將通過與LRU,LFU和LRU-K等算法的仿真實驗性能比較來考察這種影響力.3.1流媒體文件的總體特征我們設(shè)計了一個離散事件仿真器,用以模擬代理服務器對復制緩存的操作行為,由用戶的請求驅(qū)動運行.當有新的請求到達仿真器時,檢查緩存是否命中,如果命中,仿真器開始為該請求安排流媒體服務事件,否則開始為該請求需要的流媒體文件安排緩存事件,若無可用緩存空間還需要運行緩存替代算法替換出緩存中的一些文件.存在這樣5種離散事件:請求到達、用戶開始播放、用戶結(jié)束播放、開始緩存和結(jié)束緩存.為生成用戶請求負載,假定用戶請求平均到達間隔服從參數(shù)為120s的指數(shù)分布;流媒體文件的流行度服從參數(shù)θ=0.271的Zipf分布(即將流媒體文件按照流行度非遞增排序,第i個文件的被訪概率為fi=C/i(1-θ),θ稱為偏愛因子,C是規(guī)一化常數(shù));流媒體文件大小在50～100MBytes之間均勻分布且播放時長為60min;播放結(jié)束位置均勻分布且不考慮VCR操作的影響;CBR流媒體文件數(shù)W=500;用戶始播延遲在0～120s之間均勻分布(流媒體播放一般要求用戶先緩存一段數(shù)據(jù)之后,才開始播放,始播延遲指的是客戶緩存這段數(shù)據(jù)的時間);將流媒體文件從其源服務器中提取過來的代價用WebCaching日志1中的會話持續(xù)時間經(jīng)縮放后模擬,并且也假定源服務器的響應延遲在0～120s之間均勻分布.3.2算法性能對比引入字節(jié)有用性到價值函數(shù)中是否有意義,是要考慮的首要問題.BB算法同LFU和LRU算法的性能比較,可以說明這一概念較訪問局部性和訪問頻率的有效性.正如圖3實驗結(jié)果所示,隨著緩存容量的逐漸增大,3個算法的性能逐漸趨于一致,并且BB算法始終擁有最好的性能指標值.其中,橫軸是緩存的大小(CacheSize)與500個文件大小和之百分比,縱軸是LFU算法和BB算法與LRU算法對應的性能指標值的差值.比如,當緩存大小占10%時,BB算法的命中率(hitrate)高出LRU算法約13個百分點,而LFU僅高出約2個百分點.BB算法良好的性能源于其價值函數(shù)設(shè)計的“細粒度”,即不是把文件看作一個整體,而是把文件看作字節(jié)的集合,關(guān)注的是文件字節(jié)帶來的“使用價值”而不是“籠統(tǒng)”地考慮整個文件的“使用價值”.此外,我們也注意到LFU算法的性能好于LRU算法,這與Williams等的工作是一致的(即在如本文第2節(jié)所述的問題模型中,LRU策略是低效的).進一步將BB算法與其他較復雜的替代算法進行比較前,先考慮這些算法自身的一些特性.表2,表3和表4分別給出了LRU-K,LCB-K和BBLRU-K算法在上述仿真試驗設(shè)置情況下的運行性能結(jié)果.表中的第1列是緩存的大小(CacheSize),兩個大欄分別給出不同K值情況下的命中率(hitrate)和字節(jié)命中率(bytehitrate).可以看到:隨著K值的增加