CDN算法2Q(2 Queues)使用LRU队列替换了LRU-2中的优先级队列,将算法时间复杂度由logN降为常数,且维护缓存项的各信息所需空间比LRU-2小。LIRS(Low Inter-ReferenceRecency Set)维护一个变长的LRU队列,该队列的LRU端为最近至少被访问过两次的第Llirs项(Llirs为算法参数)。
CDN算法在IRM访问模式下可以获得很高的命中率,但对于SDD访问模式效率明显下降。
对于VoD系统,基于访问频率的策略可以捕捉到热点影片片段,使得对热点片段的大量请求免于进行缓慢的磁盘I/O。但影片热点会随时间不断变化,且此类策略无法利用VoD的顺序访问模式,所以纯粹以访问频率为度量来进行替换操作不适合VoD系统,更多相关知识:
http://www.zhengdaole.com。
访问时间与频率兼顾:通过兼顾访问时间与频率,使得在数据访问模式变化时缓存策略仍有较好性能。如 FBR、LRFU、ALRFU。多数此类CDN算法具有一个可调或自适应参数,通过该参数的调节使缓存策略在基于访问时间与频率间取得一定平衡。FBR(Frequency Based Replacement)维护一个LRU队列,并将该队列分为New、Middle、Old三段。
对队列中的每一缓存项均维护一个计数值。当缓存中的一项被命中时,被命中的缓存项被移至New段的MRU端,如果该项原本位于Old或Middle段,则其计数值加1,原位于New段则计数值不变。当进行替换操作时,删除Old段计数值最小的一项(LRU端),如果开展IDC业务,需要了解数据中心机房系统。
LRFU(Least Recently Frequently Used)为每一个缓存项维护一个权值C(x),其初始值为0。该CDN算法通过选用合适的λ值来获得时间与频率因素的平衡。 LRFU 虽然通过一个值来兼顾访问时间与频率因素,但由于值固定,当访问模式变化时,该算法无法做出相应的调整而造成性能下降。ALRFU对LRFU进行了改进。通过对数据访问模式的历史进行监控,ALRFU动态调整值来适应数据访问模式的改变,表现出比LRFU更好的适应性。
基于访问模式:某些应用有较明确的数据访问特点,进而产生与其相适应的缓存策略。如专为VoD系统设计的A&L缓存策略,同时适应随机、顺序两种访问模式的SARC策略。
针对VoD系统的特点提出A&L算法。该CDN算法通过记录每个缓存项的历史访问时间与访问数量来估计该项的未来被访问频率。以该频率值为度量,在进行缓存替换时替换掉该值最小的一项。由于该算法考虑了VoD系统的数据访问特点,因此广泛应用于VoD系统。