流媒体文件缓存替代算法研究

流媒体文件缓存替代算法研究

1代理服务器存储及服务模型由于格式转换的适应性、连续性和高传输带宽的要求，基于网络代理技术的开发需要到附近用户提供服务，这可以减少网络过载的影响，降低用户服务的延迟，导致大规模研究。此外，基于缓冲矩阵数据的粒度，这些工作可分为两类：部分缓冲区和全部复制。部分缓冲区是指基于堤岸噪声传播的流媒体文件的一部分数据，例如，段、访问间隔、文件序列、层等。它不包含整个流媒体文件。整体复制是指代理服务器以某种方式处理传播的流媒体文件的一部分数据，例如，不连续噪声组、连续噪声组（块）、段、访问间隔、文件目录之前、层和其他粒度的流媒体文件，而不包含整个流媒体文件。整体复制是指代理服务器在继承热点流媒体文件的基础上实现的复制。图1清晰地给出了基于代理技术的互联网流媒体服务模型,其中,Si(i=1,2,3)是流媒体文件服务器,Proxy是代理服务器,用户(User)通过代理服务器享受流媒体服务.若用户需要的流媒体数据在代理服务器中没有被缓存的话,需要从远端服务器中获取,这个数据可以直接或是经过代理服务器送达用户.可以想象代理服务器的缓存问题对于这个服务模型的性能影响的重要程度.缓存什么以及当缓存满时替换出什么是缓存问题的研究内容,通常称前者为缓存准入问题,后者为缓存替代问题.代理服务器可以采用部分缓存、整体复制或是两者的组合以改善基于流媒体文件的互联网流媒体服务系统的性能,本文考虑代理服务器整体复制缓存的替代策略问题.1.1自适应的循环访问模式设计缓存替代策略实际上就是给当前缓存中的对象一个使用价值排名,然后依次替换出使用价值最小者直至可用空间能容纳下要缓存的对象.其中,价值函数的设计是问题的关键,它对缓存命中率(hitrate)、缓存字节命中率(bytehitrate)等性能指标有很大的影响.对价值函数的设计最有影响的当数资源访问的局部性原理.所谓资源访问的局部性原理是指最近被访问的资源在不久的将来可能再次被访问,该原理对缓存技术、复制技术以及预抓取技术有深远影响.比如,LRU(LeastRecentlyUsed)策略总是替换最久没有被使用的资源,认为最近被使用者有很高的(未来)使用价值,其价值函数可以用式(1)表达.其中,ϕi(t)表示资源i在缓存替代请求时刻t被估计的未来使用价值,t1是最近一次访问资源i的时刻.ϕi(t)=1/(t-t1)(1)另一个对价值函数设计较有影响的因素是资源的访问频率.比如LFU(LeastFrequentlyUsed)总是替换出使用频率最小的资源,认为资源的使用频率越高,未来的使用价值越大.不幸地是LFU存在缓存污染(cachingpollution)问题(过去曾被多次使用的对象即便不再被使用仍占据着缓存空间)、LRU存在长环模式问题(由于缓存大小小于资源的重用模式长度,存在资源刚被替换出缓存又被请求使用的情况).鉴于此,EELRU试图侦测循环访问模式的长度,以自适应选择替换出的对象,而最近较有影响的工作应该是LRU-K.它将访问频率和访问的最近性综合到价值函数的设计之中,具有较好的性能.随着计算机应用的广泛深入,缓存问题也从缓存对象具有相同大小、在高速缓存和内存中进行缓存的问题,演变到缓存对象具有不同大小、在内存或外存中进行缓存的问题.被缓存的对象也从同一系统中的单一部件,演变到来自于网络中的不同计算机.比如:网页的代理服务器缓存问题,需要考虑缓存对象的大小、来源于不同网站的缓存对象(页面)的费用等问题.类似地,在数据网格系统中的文件缓存问题也要考虑这些因素.通常,这类价值函数有如式(2)的形式,其中,Ci(t)是从网络中获得资源i的估计费用,Sizei是资源i的大小,Pi(t)是资源i的未来使用概率的估计.Ci(t)可以使用上一次获得资源i的费用或是累计平均等进行估计,而Pi(t)的估计仍是采用类似LRU,LFU和LRU-K等的价值函数设计方法.比如,LCB-K对Pi(t)的估计就是综合了LFU和LRU-K的估值思想.ϕi(t)=Pi(t)×Ci(t)/Sizei(2)这些相关工作的问题共性在于:假定了缓存对象的整体有用性,即缓存对象被使用时是一个不可分割的整体.然而,本文探讨的流媒体整体复制缓存替代问题存在其特殊性,即我们注意到了一个流媒体文件对用户来说并非总是全部有用,用户的播放器可能仅使用了部分的媒体文件数据作为输入(比如,用户没有从头看到尾,而是看了自己喜欢的片断等).1.2各变量在文件文本文本用量性下的性能差异我们注意到请求进入复制缓存的对象是一个文件整体,而这个文件服务用户时又是以流的方式,让用户“边下载边播放”并且用户可能在任意媒体位置上停止使用.这就是说,媒体文件并不是整体有用,而是部分有用,应该对文件i占据的缓存字节数所带来的价值进行评估,定义为文件i的字节有用性并记为ξi(t).举例来说,设对流媒体文件i访问了3次,第1次访问停止在Sizei/3处,第2次访问停止在Sizei/2处,第3次访问停止在Sizei/4处,则文件i的字节有用性可估计为ξi(t)=1/3+1/2+1/4=13/12.基于文件字节有用性,本文提出了BB,BBLRU-K和BBLCB-K三个流媒体复制缓存替代算法,仿真实验表明:BBLRU-K和BBLCB-K算法随着K值的增加,性能指标值均趋于更好,尤其是当K=2时,性能指标值的增长幅度最大;在BB算法与LFU和LRU算法的比较中,发现BB算法的性能最优;在LRU-2,LCB-2,BBLRU-2,BBLCB-2和BB算法的性能比较中,BBLCB-2算法的平均性能最优,但当缓存容量较小时,BB算法性能最优.然而由于BBLCB-2算法需要考虑访问的局部性、访问频率和字节有用性,使得平均性能非常接近BBLCB-2算法的BB算法显得更为简单有效,因为BB算法只使用了字节有用性.可见,字节有用性概念对流媒体复制缓存替代策略设计的有效性.本文后续如下组织:首先对复制缓存的替代问题建立模型并通过分析得到了相应的缓存替代算法模型,然后探讨价值函数参数的估算问题并给出了几个缓存替代算法,进一步地又通过仿真试验分析比较研究了这些算法的性能,最后总结全文及指出下一步的工作.2流遗产保存算法2.1缓冲替代策略假定正在使用的流媒体文件不允许被替换出缓存,设缓存替代请求时刻为t,此时流媒体文件集合为DataSet(t)={1,2,…,n},Sizei是文件i(i∈DataSet(t))的大小;估计文件i以后会被使用的概率为Pi(t),估计以后将文件i从最近的服务器中检索出来、传输并完全进入缓存中的费用为Ci(t);缓存容量上限为B;流媒体文件i时刻t后占据的缓存容量为δi(t)×Sizei,δi(t)∈{0,1},δi(t)=0表示文件i不在缓存中,δi(t)=1表示文件i在缓存中.为了最小化t时刻后,用户请求的平均响应延迟,则应确保:当缓存不命中时,平均需要付出的费用最小.因此,在时刻t,一个理想的缓存替代策略执行后应为最小化:∑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,则可以忽略缓存最大数量的文件后剩余的空间,于是理想的缓存替代策略变为最大化:∑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)求解该问题的最优化算法就是:按照Pk(t)×Ck(t)/Sizek非递增排序DataSet(t)集中的元素,然后从头依次选择要缓存的流媒体文件直到式(4)刚好满足.这意味着在当前δ值为1的流媒体文件集合中找出淘汰者就是按照式(7)进行非递增排名,然后从最小值者逆序开始释放缓存,直到可用缓存满足要求.ϕi(t)=Pi(t)×Ci(t)/Sizei(7)可见,缓存替代策略实际上就是给当前缓存中的对象一个使用价值排名,然后依次替换出使用价值最小者直至可用空间能容纳下要缓存的对象.ϕi(t)被称为(使用)价值函数.如何设计有效的价值函数成为解决问题的关键,它对缓存命中率(hitrate)、缓存字节命中率(bytehitrate)等性能指标有很大的影响.所谓缓存命中率是指在缓存中发现所需对象的次数与总的请求次数之比,字节命中率指通过缓存命中的字节数与总的请求字节数之比.2.2关于相对时间的估计上节模型化流媒体文件“整进整出”缓存的替代问题(即流媒体文件以一个不可分割的整体进入缓存或是被替换出缓存,且若正在被使用的话,不允许被替换出缓存)之后,得到了复制缓存替代策略,但它只是一个算法模型.公式(7)中参数的不同估计得到不同的替代算法实例.在Pi(t),Ci(t)和Sizei这3个参数中,Sizei的确定没有什么难度,Ci(t)可以使用上一次缓存流媒体文件i的费用或是累计缓存文件i的平均费用等进行估计,最难的就是Pi(t)的估计.由于对未来访问序列的不可先知性,估计Pi(t)显然只能根据过去的访问序列预测.图2给出了文件i的历史访问序列例.可以看到自t3时刻访问过文件i以来,在t2和t1时刻又有两次访问,现在是缓存替代请求时刻t,需要估计Pi(t).由于对任意文件i的访问假定独立且服从参数为λ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的估计方法表现出良好的性能特点,但是它们估计λi(t)的方法是基于格林威治时间尺度,而基于相对时间(timescalerelativity)的方法,在Jiang和Smaragdakis的研究中表现出更好的合理性.其原因在于,绝对时间尺度可能与资源的重用概率毫不相关,而相对时间可以确保这种相关性.我们认为这种不相关性在以硬盘作为缓存空间并且缓存从不归零的应用背景中是非常大的,所以选择相对时间刻度估计λi(t).所谓相对时间研究方法是指一个研究中使用的时间粒度(刻度)仅应反映出研究对象之间至关重要的事件特征.对于文件访问序列来说,则可用资源i自从本次被访问之后又有多少个其它不同的资源被访问来作为此次访问发生的时刻.举例来说,记最近对资源i的逆数第m次访问时刻为ti(m),设有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就是使用这种相对时间技术.类似LRU-K和LCB-K估计λi(t)的思想,使用这种相对时间技术,可以得到如式(9)所示的λi(t)估值公式,其中,K是常数.显然,当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)让流媒体文件“整进整出”缓存,那么该缓存替代问题区别于诸如网页缓存替代问题的地方在哪呢?我们注意到:用户在享受某个媒体流服务时,可能在任意媒体位置上停止使用.这就是说,媒体文件并不是整体有用,而是部分地有用,应该对文件i占据的缓存字节数所带来的使用价值进行评估,定义为文件i的字节有用性并记为ξi(t).举例来说,设对流媒体文件i访问了3次,第1次访问停止在Sizei/3处,第2次访问停止在Sizei/2处,第3次访问停止在Sizei/4处,则文件i的字节有用性可估计为ξi(t)=1/3+1/2+1/4=13/12.可形式描述该概念如下:设对流媒体文件i共访问了g次,在第h次播放过程中(不管流媒体服务是否支持VCR操作),我们用xi(h,j)表示文件i第j字节是否曾是解码器的输入,即xi(h,j)={1,第j字节进入过解码器0‚否则,则文件i的字节有用性ξi(t)=[g∑h=1Sizei∑j=1xi(h,j)]/Sizei.在实际系统中,可以采用rp·Lh来估算Sizei∑j=1xi(h,j),其中,rp是流媒体文件i的(平均)播放速率,Lh是第h次播放持续的时间.2.3基于性能分析的判断函数如前文所述,不同的λi(t)估计得到不同的替代算法.比如,将式(8)和(9)代入价值函数(7)中,得到如式(10)所示的价值函数实例,我们仍称其对应的替代算法为LRU-K.ϕi(t)=1Κ∑m=1ti(m)×Ci(t)Sizei(10)表1给出了本文要考察的几个替代算法所用的估值函数.当K=1时,LRU-1算法就是传统的LRU算法.LFU和LRU的简单性、LRU-K和LCB-K在相关工作问题模型中表现的良好性能使得它们成为我们下一节性能研究比较的合适对象.类似LFU只考虑访问频率、LRU只考虑最近性,我们把只考虑字节有用性的算法定义为BB替代算法,同时鉴于LRU-K和LCB-K在相关工作的性能表现,提出了BBLRU-K和BBLCB-K算法.3仿真实验性能引入字节有用性到价值函数中,对缓存命中率和缓存字节命中率的影响如何是该节要考虑的问题.我们将通过与LRU,LFU和LRU-K等算法的仿真实验性能比较来考察这种影响力.3.1流媒体文件的总体特征我们设计了一个离散事件仿真器,用以模拟代理服务器对复制缓存的操作行为,由用户的请求驱动运行.当有新的请求到达仿真器时,检查缓存是否命中,如果命中,仿真器开始为该请求安排流媒体服务事件,否则开始为该请求需要的流媒体文件安排缓存事件,若无可用缓存空间还需要运行缓存替代算法替换出缓存中的一些文件.存在这样5种离散事件:请求到达、用户开始播放、用户结束播放、开始缓存和结束缓存.为生成用户请求负载,假定用户请求平均到达间隔服从参数为120s的指数分布;流媒体文件的流行度服从参数θ=0.271的Zipf分布(即将流媒体文件按照流行度非递增排序,第i个文件的被访概率为fi=C/i(1-θ),θ称为偏爱因子,C是规一化常数);流媒体文件大小在50～100MBytes之间均匀分布且播放时长为60min;播放结束位置均匀分布且不考虑VCR操作的影响;CBR流媒体文件数W=500;用户始播延迟在0～120s之间均匀分布(流媒体播放一般要求用户先缓存一段数据之后,才开始播放,始播延迟指的是客户缓存这段数据的时间);将流媒体文件从其源服务器中提取过来的代价用WebCaching日志1中的会话持续时间经缩放后模拟,并且也假定源服务器的响应延迟在0～120s之间均匀分布.3.2算法性能对比引入字节有用性到价值函数中是否有意义,是要考虑的首要问题.BB算法同LFU和LRU算法的性能比较,可以说明这一概念较访问局部性和访问频率的有效性.正如图3实验结果所示,随着缓存容量的逐渐增大,3个算法的性能逐渐趋于一致,并且BB算法始终拥有最好的性能指标值.其中,横轴是缓存的大小(CacheSize)与500个文件大小和之百分比,纵轴是LFU算法和BB算法与LRU算法对应的性能指标值的差值.比如,当缓存大小占10%时,BB算法的命中率(hitrate)高出LRU算法约13个百分点,而LFU仅高出约2个百分点.BB算法良好的性能源于其价值函数设计的“细粒度”,即不是把文件看作一个整体,而是把文件看作字节的集合,关注的是文件字节带来的“使用价值”而不是“笼统”地考虑整个文件的“使用价值”.此外,我们也注意到LFU算法的性能好于LRU算法,这与Williams等的工作是一致的(即在如本文第2节所述的问题模型中,LRU策略是低效的).进一步将BB算法与其他较复杂的替代算法进行比较前,先考虑这些算法自身的一些特性.表2,表3和表4分别给出了LRU-K,LCB-K和BBLRU-K算法在上述仿真试验设置情况下的运行性能结果.表中的第1列是缓存的大小(CacheSize),两个大栏分别给出不同K值情况下的命中率(hitrate)和字节命中率(bytehitrate).可以看到:随着K值的增加