基于能量模型的交互式環(huán)流緩存置換方法

基于能量模型的交互式環(huán)流緩存置換方法

由于有很多媒體文件，代理服務(wù)器只保存成本最高的媒體內(nèi)容。成本目標(biāo)包括用戶請求的特征、帶寬資源、存儲限制等。作者在互動場景中研究了基于用戶特征的媒體存儲算法，并以存儲熱點媒體段為主要目標(biāo)。一般流媒體點播應(yīng)用假設(shè)用戶總是從媒體內(nèi)容的起始部分請求播放(順序播放),對此,大部分緩存算法采用按時間順序緩存策略.然而順序播放忽略了用戶訪問的交互性,對媒體點播日志的大量觀察表明:大多數(shù)流媒體對象僅被部分訪問;訪問時出現(xiàn)大量的交互式動作(如快進等),即任何部分的媒體內(nèi)容都可能成為用戶訪問的熱點.此時遵循順序緩存策略需要緩存額外片段才能存到熱點片段,既浪費緩存空間也降低緩存命中率.為此,作者提出一種新的緩存算法——基于能量模型(energymodel,EM)的分段緩存算法,此算法以片段作為緩存和置換的基本單元,支持一定程度的用戶交互請求.Exponential算法將媒體對象劃分成大小指數(shù)增加的片段,片斷數(shù)目較少有利于熱點定位.Soccer算法在等分劃分策略的基礎(chǔ)上將相鄰片段聚合成大塊(chunk),在大塊內(nèi)進行前綴緩存.此算法用較少的操作次數(shù)和存儲空間達到對任意熱點片段的緩存,具有一定借鑒作用,選為本文緩存性能評估的參照算法.1im算法EM算法要實現(xiàn)根據(jù)內(nèi)容流行度決定是否緩存片斷,其中涉及到兩個問題:片斷劃分和記錄策略;緩存準(zhǔn)入和置換策略.1.1流媒體文件中重要的碎片流行度交互式場景中,用戶對流媒體的訪問位置和范圍不確定,EM算法采用易于定位的等分劃分策略.片斷記錄策略是算法的設(shè)計關(guān)鍵,難點在于片斷記錄既要準(zhǔn)確反映片斷最近的訪問熱度,又要節(jié)省存儲空間.作者利用片斷流行度在媒體內(nèi)容上的連續(xù)性,給出了一種簡便的片斷記錄策略.定義1存儲塊(Block).定義為流媒體播放1s需要的存儲空間.假設(shè)所有流媒體對象都是以固定速率播放,即所有block大小相等.圖1表示擁有45個block的一個流媒體文件各片斷的受訪問情況,以此衡量各片斷流行度,顯然block20～25是最流行的部分.由于受訪問次數(shù)的連續(xù)性,僅需記錄累計受訪次數(shù)的跳變位置及其對應(yīng)的流行度即可描述整體分布.圖1示例中僅需記錄{(0,1),(5,2),(10,3),(19,4),(25,3),(30,2),(34,1),(45,0)}.通過這種方法,可以顯著減少片斷記錄項的數(shù)量.定義2片斷流行度表(SPT).代理服務(wù)器為任一流媒體文件fj維護一張記錄跳變位置及其對應(yīng)流行度的表SPTj,表中每項記錄為Sji〈bji,Eji〉,其中bji為文件fj的流行度跳變位置,即片斷首個block序號,Eji為此片斷對應(yīng)的流行度.1.2第k次訪問時碎片sj-bjf-k-k1的更新片斷流行度反映了流媒體片斷的活躍程度,通常被定義為一段時間片斷的累計播放次數(shù),但該流行度定義存在緩存污染問題,即過去曾被多次使用的對象即使不再使用,仍有較高流行度;而最近時間訪問頻率的流行度表示存在長環(huán)模式問題,即一個流行度很低的對象實際可能很快被使用.鑒于此,綜合考慮頻率和訪問的最近性,提出一個基于EM的內(nèi)容流行度表示,采用能量這一概念描述片斷的流行度:訪問頻率越高,片斷具有的能量越高;能量隨頻率呈指數(shù)衰減,類似放射性元素的半衰期τ.對文件的每次訪問依次編號,用Eji(k)表示發(fā)生第k次訪問時,片斷Sji具有的能量,α=2-1/τ表示能量衰減基數(shù).片斷能量的表示過程如下:①發(fā)生第k次文件訪問時,片斷Sji從未被訪問過,則Eji(k)=0;②發(fā)生第k次文件訪問時,訪問了片斷Sji,則Eji(k)=Eji(k-)+1,k-表示第k次訪問之前,是個極限概念;③在第k1和k2次訪問之間,沒有對片斷Sji進行訪問,則Eji(k2)=Eji(k1)αk2-k1;④發(fā)生第k2次訪問時,訪問片斷Sji,且最近一次對片斷Sji的訪問發(fā)生在第k1次,則Eji(k2)=Eji(k1)αk2-k1+1.(1)訪問文件的某片斷需要對文件的SPT進行更新操作.設(shè)發(fā)生第k次訪問時,訪問流媒體文件fj的片段Sji.bji,bjk,bjf,bjg均為block,其位置如圖2所示.SPTj依次執(zhí)行如下的更新操作:①如SPTj中存在含bji的記錄,則按式(1)更新此記錄的Eji(k);否則按式(2)計算Eji(k),并將新記錄Sji〈bji,Eji〉插入到SPTj中.式中Eif(k)表示bjf所在片斷的流行度.②如SPTj中存在含bjk記錄,不操作;否則按式(3)計算Ejk(k),并將新記錄Sjk〈bjk,Ejk〉插入到SPTj中.式中Ejg(k)表示bjg所在片斷的流行度.③對SPTj中所有介于(bji,bjk)的block,按式(1)更新各自的片斷流行度.1.3crt添加/合并數(shù)據(jù)的存儲及釋放過程EM算法對緩存片段的接入/釋放操作以block為單位,按照指數(shù)增長方式在已緩存片段的尾部進行,對未緩存片段的第一次訪問將使EM算法為其分配初始緩存空間linit.定義3緩存記錄表(cacherecordtable,CRT).EM算法為每一流媒體文件維護一張CRT,記錄該文件所有片段的第一個block位置、片斷長度、上次被訪問時間、已緩存block數(shù)、當(dāng)前應(yīng)接入/釋放的block數(shù)等信息.對SPT執(zhí)行添加、合并記錄操作也會使CRT添加/合并對應(yīng)項.分別討論緩存接入和釋放的情況:①緩存接入.發(fā)生第t次訪問,訪問片斷Sji,則接入Sji的緩存.設(shè)上次訪問Sji發(fā)生在第t0次,Sji當(dāng)前應(yīng)接入block數(shù)最大值gji:②緩存釋放.發(fā)生第t次訪問空閑緩存不足,選定片斷Sji釋放緩存.設(shè)上次訪問Sji發(fā)生在第t0次,Sji當(dāng)前應(yīng)釋放block數(shù)最大值dji:式中:g′ji,d′ji分別為Sji上次緩存接入值和釋放塊數(shù);設(shè)Gmax,Gmin分別為每次可接入最大、最小塊數(shù);Dmax,Dmin為每次可釋放的最大、最小塊數(shù).從式(4)(5)可看出:當(dāng)t-t0在半衰期內(nèi)時,緩存接入速度成指數(shù)遞增,而釋放速度緩慢;當(dāng)其大于半衰期時,緩存接入增速緩慢,釋放速度很快.1.4dwbdiusjEM算法運用效用函數(shù)為所有緩存片段計算效用,依次讀取效用最小的片段的SPT記錄,根據(jù)式(5)釋放緩存空間,直至可容納下緩存對象為止.片斷Sji的效用函數(shù)U(Sji)表達式為U(Sji)=rwaji(1+1lji/dji?wc)(1+lji/Tji)dwbjiU(Sji)=rjiwa(1+1lji/dji-wc)(1+lji/Τji)djiwb,(6)wa+wb+wc=1.(7)式中:rji表示片段Sji的流行度;lji表示Sji已緩存block數(shù);Tji表示Sji長度;dji表示Sji可釋放的block數(shù)最大值;lji/Tji表示內(nèi)容比率,即已緩內(nèi)容與實際大小的比率;lji/dji表示完全釋放緩存所需的次數(shù).wa,wb,wc為影響因子,分別表示rji,dji,Sji的可釋放次數(shù)lji/dji對效用函數(shù)的影響度.依據(jù)效用函數(shù)進行的緩存置換策略具有如下優(yōu)點.反映訪問熱點U(Sji)與rji成正比,使最受歡迎的片斷緩存時間更長;2平衡內(nèi)容率U(Sji)與內(nèi)容比率lji/Tji成反比,使不同片斷緩存的內(nèi)容比率趨向一致,以減少某片斷長時間占有資源;獲得足夠的空間U(Sji)值與dji成反比,釋放dji值大的片段,迅速獲得較大空間;lj/小鼠U(Sji)與釋放次數(shù)lji/dji成反比,由于lji/dji-wc<1,使得釋放Sji的概率大幅下降,提升Sji頭部的保留時間,實現(xiàn)了前綴緩存.1.5sdisj存片數(shù)ljEM算法步驟如下.步驟1根據(jù)片斷Sji信息更新SPTj記錄,并更新CRTj表的相應(yīng)記錄訪問信息.步驟2讀取CRTj表,獲得Sji最近一次被訪時間t0,根據(jù)t-t0調(diào)用式(4)(5)更新Sji的gji和dji.步驟3根據(jù)Sji的文件未緩存片斷數(shù)lji,獲取實際可接入緩存塊數(shù)Δb=min(gji,lji).步驟4設(shè)空閑緩存空間大小為C,若(Δb≤C)C-=Δb,跳至步驟7.步驟5讀取CRTj,對其它任一緩存片段s′執(zhí)行如下操作:①讀取最近一次被訪問時間,根據(jù)t-t0的值調(diào)用式(4)或(5)更新其最大可釋放block數(shù);②依據(jù)式(6)計算s′的U(s′),并按照效用由小至大升序排列;③依次選取效用最小的片段,根據(jù)其dji,未被播放鎖定的block數(shù)bji,計算該片斷實際可釋放緩存塊數(shù)Δb′=min(dji,bji),并按Δb′進行釋放,直至∑Δb′+C≥Δb.步驟6C=∑Δb′+C-Δb.步驟7為Sji分配緩存空間ΔP.2緩沖區(qū)算法的性能評估2.1媒體性能指標(biāo)評估代理服務(wù)器緩存性能的典型方法是記錄驅(qū)動的仿真.對于流媒體應(yīng)用,往往采用用戶請求生成工具GISMO等評估流媒體的應(yīng)用的性能.作者基于這些用戶請求生成工具,模擬互聯(lián)網(wǎng)媒體點播應(yīng)用中常用的“Play”,“Abort”等動作.表1給出了用戶記錄的主要數(shù)學(xué)特征,其中媒體的受訪次數(shù)、會話的時間相關(guān)性、媒體大小等指標(biāo)和參數(shù)參考GISMO;跳轉(zhuǎn)動作的距離和播放動作的距離等指標(biāo)的模型和參數(shù)分別服從文獻的觀察結(jié)果.設(shè)任意時刻用戶采用播放、跳轉(zhuǎn)和終止動作的概率分別為PPlay,PJump和PAbort,且PPlay+PJump+PAbort=1.按照文獻中的觀察結(jié)果,約定60%的跳轉(zhuǎn)動作是跳進.非播放動作的概率越大,則獲得的用戶記錄的交互強度越大.通過設(shè)置用戶交互式動作的發(fā)生概率參數(shù),獲得了2組不同模式交互強度的用戶記錄,記為A,B.每個用戶記錄都有100個流媒體文件和1萬個用戶會話.表2為不同合成記錄的參數(shù)配置以及數(shù)學(xué)統(tǒng)計特征,流媒體文件的播放速率為384kbit/s.觀察表2統(tǒng)計特性發(fā)現(xiàn),獲得的統(tǒng)計特征基本符合對合成用戶請求記錄的要求:交互強度越大,則會話中交互式動作越多.表3給出本測試中EM算法用到的一些其他參數(shù)的設(shè)置.2.2算法性能分析比較EM與Exponential,Soccer和Entire算法在合成用戶請求記錄上的性能.其中,Entire算法以Web緩存方式將整個媒體作為緩存單元;等分劃分的分段緩存算法Soccer,基本分段大小為300block;Exponential分段大小按{10,20,40,80,160,…}的速度遞增.算法主要性能指標(biāo):①整體命中率(entirehitratio,EHR)指緩存完全命中所需次數(shù)與總請求次數(shù)之比.EHR越大,每個請求的平均時延越小.②字節(jié)命中率(bytehitratio,BHR)指緩存命中的字節(jié)數(shù)與總請求字節(jié)數(shù)之比.BHR越大,帶寬需求就越小.請求記錄A,B代表了不同交互強度的用戶請求,相應(yīng)4種算法的EHR和BHR結(jié)果在圖3,4中給出.實驗結(jié)果表明:①隨著緩存容量的逐漸增大,4種算法的性能趨于一致;②EM算法在不同交互強度下始終擁有最好的性能指標(biāo);③Exponential算法的性能僅