基于能量模型的交互式环流缓存置换方法

基于能量模型的交互式环流缓存置换方法

由于有很多媒体文件，代理服务器只保存成本最高的媒体内容。成本目标包括用户请求的特征、带宽资源、存储限制等。作者在互动场景中研究了基于用户特征的媒体存储算法，并以存储热点媒体段为主要目标。一般流媒体点播应用假设用户总是从媒体内容的起始部分请求播放(顺序播放),对此,大部分缓存算法采用按时间顺序缓存策略.然而顺序播放忽略了用户访问的交互性,对媒体点播日志的大量观察表明:大多数流媒体对象仅被部分访问;访问时出现大量的交互式动作(如快进等),即任何部分的媒体内容都可能成为用户访问的热点.此时遵循顺序缓存策略需要缓存额外片段才能存到热点片段,既浪费缓存空间也降低缓存命中率.为此,作者提出一种新的缓存算法——基于能量模型(energymodel,EM)的分段缓存算法,此算法以片段作为缓存和置换的基本单元,支持一定程度的用户交互请求.Exponential算法将媒体对象划分成大小指数增加的片段,片断数目较少有利于热点定位.Soccer算法在等分划分策略的基础上将相邻片段聚合成大块(chunk),在大块内进行前缀缓存.此算法用较少的操作次数和存储空间达到对任意热点片段的缓存,具有一定借鉴作用,选为本文缓存性能评估的参照算法.1im算法EM算法要实现根据内容流行度决定是否缓存片断,其中涉及到两个问题:片断划分和记录策略;缓存准入和置换策略.1.1流媒体文件中重要的碎片流行度交互式场景中,用户对流媒体的访问位置和范围不确定,EM算法采用易于定位的等分划分策略.片断记录策略是算法的设计关键,难点在于片断记录既要准确反映片断最近的访问热度,又要节省存储空间.作者利用片断流行度在媒体内容上的连续性,给出了一种简便的片断记录策略.定义1存储块(Block).定义为流媒体播放1s需要的存储空间.假设所有流媒体对象都是以固定速率播放,即所有block大小相等.图1表示拥有45个block的一个流媒体文件各片断的受访问情况,以此衡量各片断流行度,显然block20～25是最流行的部分.由于受访问次数的连续性,仅需记录累计受访次数的跳变位置及其对应的流行度即可描述整体分布.图1示例中仅需记录{(0,1),(5,2),(10,3),(19,4),(25,3),(30,2),(34,1),(45,0)}.通过这种方法,可以显著减少片断记录项的数量.定义2片断流行度表(SPT).代理服务器为任一流媒体文件fj维护一张记录跳变位置及其对应流行度的表SPTj,表中每项记录为Sji〈bji,Eji〉,其中bji为文件fj的流行度跳变位置,即片断首个block序号,Eji为此片断对应的流行度.1.2第k次访问时碎片sj-bjf-k-k1的更新片断流行度反映了流媒体片断的活跃程度,通常被定义为一段时间片断的累计播放次数,但该流行度定义存在缓存污染问题,即过去曾被多次使用的对象即使不再使用,仍有较高流行度;而最近时间访问频率的流行度表示存在长环模式问题,即一个流行度很低的对象实际可能很快被使用.鉴于此,综合考虑频率和访问的最近性,提出一个基于EM的内容流行度表示,采用能量这一概念描述片断的流行度:访问频率越高,片断具有的能量越高;能量随频率呈指数衰减,类似放射性元素的半衰期τ.对文件的每次访问依次编号,用Eji(k)表示发生第k次访问时,片断Sji具有的能量,α=2-1/τ表示能量衰减基数.片断能量的表示过程如下:①发生第k次文件访问时,片断Sji从未被访问过,则Eji(k)=0;②发生第k次文件访问时,访问了片断Sji,则Eji(k)=Eji(k-)+1,k-表示第k次访问之前,是个极限概念;③在第k1和k2次访问之间,没有对片断Sji进行访问,则Eji(k2)=Eji(k1)αk2-k1;④发生第k2次访问时,访问片断Sji,且最近一次对片断Sji的访问发生在第k1次,则Eji(k2)=Eji(k1)αk2-k1+1.(1)访问文件的某片断需要对文件的SPT进行更新操作.设发生第k次访问时,访问流媒体文件fj的片段Sji.bji,bjk,bjf,bjg均为block,其位置如图2所示.SPTj依次执行如下的更新操作:①如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添加/合并数据的存储及释放过程EM算法对缓存片段的接入/释放操作以block为单位,按照指数增长方式在已缓存片段的尾部进行,对未缓存片段的第一次访问将使EM算法为其分配初始缓存空间linit.定义3缓存记录表(cacherecordtable,CRT).EM算法为每一流媒体文件维护一张CRT,记录该文件所有片段的第一个block位置、片断长度、上次被访问时间、已缓存block数、当前应接入/释放的block数等信息.对SPT执行添加、合并记录操作也会使CRT添加/合并对应项.分别讨论缓存接入和释放的情况:①缓存接入.发生第t次访问,访问片断Sji,则接入Sji的缓存.设上次访问Sji发生在第t0次,Sji当前应接入block数最大值gji:②缓存释放.发生第t次访问空闲缓存不足,选定片断Sji释放缓存.设上次访问Sji发生在第t0次,Sji当前应释放block数最大值dji:式中:g′ji,d′ji分别为Sji上次缓存接入值和释放块数;设Gmax,Gmin分别为每次可接入最大、最小块数;Dmax,Dmin为每次可释放的最大、最小块数.从式(4)(5)可看出:当t-t0在半衰期内时,缓存接入速度成指数递增,而释放速度缓慢;当其大于半衰期时,缓存接入增速缓慢,释放速度很快.1.4dwbdiusjEM算法运用效用函数为所有缓存片段计算效用,依次读取效用最小的片段的SPT记录,根据式(5)释放缓存空间,直至可容纳下缓存对象为止.片断Sji的效用函数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数;Tji表示Sji长度;dji表示Sji可释放的block数最大值;lji/Tji表示内容比率,即已缓内容与实际大小的比率;lji/dji表示完全释放缓存所需的次数.wa,wb,wc为影响因子,分别表示rji,dji,Sji的可释放次数lji/dji对效用函数的影响度.依据效用函数进行的缓存置换策略具有如下优点.反映访问热点U(Sji)与rji成正比,使最受欢迎的片断缓存时间更长;2平衡内容率U(Sji)与内容比率lji/Tji成反比,使不同片断缓存的内容比率趋向一致,以减少某片断长时间占有资源;获得足够的空间U(Sji)值与dji成反比,释放dji值大的片段,迅速获得较大空间;lj/小鼠U(Sji)与释放次数lji/dji成反比,由于lji/dji-wc<1,使得释放Sji的概率大幅下降,提升Sji头部的保留时间,实现了前缀缓存.1.5sdisj存片数ljEM算法步骤如下.步骤1根据片断Sji信息更新SPTj记录,并更新CRTj表的相应记录访问信息.步骤2读取CRTj表,获得Sji最近一次被访时间t0,根据t-t0调用式(4)(5)更新Sji的gji和dji.步骤3根据Sji的文件未缓存片断数lji,获取实际可接入缓存块数Δb=min(gji,lji).步骤4设空闲缓存空间大小为C,若(Δb≤C)C-=Δb,跳至步骤7.步骤5读取CRTj,对其它任一缓存片段s′执行如下操作:①读取最近一次被访问时间,根据t-t0的值调用式(4)或(5)更新其最大可释放block数;②依据式(6)计算s′的U(s′),并按照效用由小至大升序排列;③依次选取效用最小的片段,根据其dji,未被播放锁定的block数bji,计算该片断实际可释放缓存块数Δb′=min(dji,bji),并按Δb′进行释放,直至∑Δb′+C≥Δb.步骤6C=∑Δb′+C-Δb.步骤7为Sji分配缓存空间ΔP.2缓冲区算法的性能评估2.1媒体性能指标评估代理服务器缓存性能的典型方法是记录驱动的仿真.对于流媒体应用,往往采用用户请求生成工具GISMO等评估流媒体的应用的性能.作者基于这些用户请求生成工具,模拟互联网媒体点播应用中常用的“Play”,“Abort”等动作.表1给出了用户记录的主要数学特征,其中媒体的受访次数、会话的时间相关性、媒体大小等指标和参数参考GISMO;跳转动作的距离和播放动作的距离等指标的模型和参数分别服从文献的观察结果.设任意时刻用户采用播放、跳转和终止动作的概率分别为PPlay,PJump和PAbort,且PPlay+PJump+PAbort=1.按照文献中的观察结果,约定60%的跳转动作是跳进.非播放动作的概率越大,则获得的用户记录的交互强度越大.通过设置用户交互式动作的发生概率参数,获得了2组不同模式交互强度的用户记录,记为A,B.每个用户记录都有100个流媒体文件和1万个用户会话.表2为不同合成记录的参数配置以及数学统计特征,流媒体文件的播放速率为384kbit/s.观察表2统计特性发现,获得的统计特征基本符合对合成用户请求记录的要求:交互强度越大,则会话中交互式动作越多.表3给出本测试中EM算法用到的一些其他参数的设置.2.2算法性能分析比较EM与Exponential,Soccer和Entire算法在合成用户请求记录上的性能.其中,Entire算法以Web缓存方式将整个媒体作为缓存单元;等分划分的分段缓存算法Soccer,基本分段大小为300block;Exponential分段大小按{10,20,40,80,160,…}的速度递增.算法主要性能指标:①整体命中率(entirehitratio,EHR)指缓存完全命中所需次数与总请求次数之比.EHR越大,每个请求的平均时延越小.②字节命中率(bytehitratio,BHR)指缓存命中的字节数与总请求字节数之比.BHR越大,带宽需求就越小.请求记录A,B代表了不同交互强度的用户请求,相应4种算法的EHR和BHR结果在图3,4中给出.实验结果表明:①随着缓存容量的逐渐增大,4种算法的性能趋于一致;②EM算法在不同交互强度下始终拥有最好的性能指标;③Exponential算法的性能仅