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

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

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