本地应用缓存算法和缓存策略的介绍

特别声明：该文章是 本人在网上搜索到的一些资料，稍作整理而成的，还望大家不要误会，具体出自于那本人也已经忘记。还请大家不要误会！！！

通过设计良好的数据分块、预取、替换、更新等算法来提高对缓存内容的命中率和一致性。

1）数据分块

Memcached默认情况下采用了名为Slab Allocator的机制分配、管理内存。在该机制出现以前，内存的分配是通过对所有记录简单地进行malloc和free来进行的。但是，这种方式会导致内存碎片，加重操作系统内存管理器的负担，最坏的情况下，会导致操作系统比memcached进程本身还慢。Slab Allocator就是为解决该问题而诞生的。

2）预取策略

大部分缓存算法使用预取策略来提前将部分磁盘数据放入缓存,以进一步减少磁盘I/O,加大缓存命中率。通过记录、分析以往的数据请求模式来预测将来可能被请求到的数据段,将访问可能性大的数据段放入缓存。VoD视频点播存在很强的顺序数据访问模式:即在用户不进行VCR操作的情况下,对整个影片文件的各部分依次顺序访问,访问过的数据很少再次进行访问。此种数据访问模式是在设计VoD缓存算法时必须要考虑的。所以顺序预取方式适用于VoD系统。

3）替换策略

由于不同系统的数据访问模式不尽相同,同一种缓存策难以在各种数据访问模式下均取得满意性能,

研究人员提出不同缓存策略以适应不同需求。缓存策略可分为以下几类:

基于访问时间:此类算法按各缓存项的被访问时间来组织缓存队列,决定替换对象。如LRU。

基于访问频率:此类算法用缓存项的被访问频率来组织缓存。如LFU、LRU-2、2Q、LIRS。

访问时间与频率兼顾:通过兼顾访问时间与频率,使得在数据访问模式变化时缓存策略仍有较好性能。如FBR、LRFU、ALRFU。多数此类算法具有一个可调或自适应参数,通过该参数的调节使缓存策略在基于访问时间与频率间取得一定平衡。

基于访问模式:某些应用有较明确的的数据访问特点,进而产生与其相适应的缓存策略。如专为VoD系统设计的A&L缓存策略,同时适应随机、顺序两种访问模式的SARC策略。

基于访问时间的缓存策略：LRU (LeastRecentlyUsed)是一种应用广泛的缓存算法。该算法维护一个缓存项队列,队列中的缓存项按每项的最后被访问时间排序。当缓存空间已满时,将处于队尾,即删除最后一次被访问时间距现在最久的项,将新的区段放入队列首部。

但LRU算法仅维护了缓存块的访问时间信息,没有考虑被访问频率等因素,在某些访问模式下无法获得理想命中率。例如对于VoD系统,在没有VCR操作的情况下,数据被由前至后顺序访问,已访问过的数据不会被再次访问。所以LRU算法将最新被访问的数据最后被替换不适用于VoD系统。

基于访问频率的缓存策略：

LFU (LeastFrequentlyUsed)按每个缓存块的被访问频率将缓存中的各块排序,当缓存空间已满时,替换掉缓存队列中访问频率最低的一项。与LRU的缺点类似, LFU仅维护各项的被访问频率信息,对于某缓存项,如果该项在过去有着极高的访问频率而最近访问频率较低,当缓存空间已满时该项很难被从缓存中替换出来,进而导致命中率下降。

LRU-2[2, 3]算法记录下每个缓存页面最后两次被访问的时间。替换页面时替换掉倒数第二次访问时间距现在最久的一项。

在IRM (IndependentReferenceModel)访问模式下,LRU-2有着最好的预期命中率,由于LRU-2算法要维护一个优先级队列,所以该算法复杂度为logN(N为缓存队列中缓存项的数量)。

2Q[4](2 Queues)使用LRU队列替换了LRU-2中的优先级队列,将算法时间复杂度由logN降为常数,且维护缓存项的各信息所需空间比LRU-2小。

LIRS[5](Low Inter-ReferenceRecency Set)维护一个变长的LRU队列,该队列的LRU端为最近至少被访问过2次的第Llirs项(Llirs为算法参数)。LIRS算法在IRM访问模式下可以获得很高的命中率,但对于SDD访问模式效率明显下降。

对于VoD系统,基于访问频率的策略可以捕捉到热点影片片段,使得对热点片段的大量请求免于进行缓慢的磁盘I/O。但影片热点会随时间不断变化,且此类策略无法利用VoD的顺序访问模式,所以纯粹以访问频率为度量来进行替换操作不适合VoD系统。

兼顾访问时间与频率：

FBR[6](Frequency Based Replacement)维护一个LRU队列,并将该队列分为New、Middle、Old三段。对队列中的每一缓存项均维护一个计数值。当缓存中的一项被命中时,被命中的缓存项被移至New段的MRU端,如果该项原本位于Old或Middle段,则其计数值加1,原位于New段则计数值不变。当进行替换操作时,删除Old段计数值最小的一项(LRU端)。

LRFU[7](LeastRecently FrequentlyUsed)为每一个缓存项维护一个权值C(x),其初始值为0, C(x)按以下公式变化。

在t时刻, C(x) =1+2-λC(x): x被访问到2-λC(x): x未被访问进行替换操作时,C(x)值最小的一项被删除。当时, LRFU算法行为类似于LFU;而当时,该算法行为逼近LRU算法。该算法通过选用合适的λ值来获得时间与频率因素的平衡。

LRFU虽然通过一个值来兼顾访问时间与频率因素,但由于值固定,当访问模式变化时,该算法无法做出相应的调整而造成性能下降。ALRFU[8](Adaptive LRFU)在此方面对LRFU进行了改进。通过对数据访问模式的历史进行监控,ALRFU动态调整值来适应数据访问模式的改变,表现出比LRFU更好的适应性。

基于访问模式的缓存策略：

文献[9]针对VoD系统的特点提出A&L算法。该算法通过记录每个缓存项的历史访问时间与访问数量来估计该项的未来被访问频率。以该频率值为度量,在进行缓存替换时替换掉该值最小的一项。由于该算法考虑了VoD系统的数据访问特点,所以广泛应用于VoD系统。

但A&L算法通过直接计算缓存区段生成以来的总的访问数量、频率来生成缓存权值,没有考虑VoD影片的访问热点会随时间不断变化。当某些缓存区段历史访问频率较高但最近访问频率下降时,仍保持较大权值,影响新的热点片段的缓存,无法适应影片热点的动态变化。

IBM提出的SARC[10]是针对于大型服务器的缓存算法,可在随机访问与顺序访问的数据访问模式下做出动态适应。SARC通过将随机访问与顺序访问分为两个队列分别管理来实现对两种不同访问模式的适应。并通过分析缓存大小-命中率的仿真试验数据曲线,得出对随机队列与顺序队列项分别进行替换的代价函数。当进行缓存替换时,通过两队列的代价函数来对代价小的队列进行替换。

4）更新策略

更新策略分为主动更新和被动更新：

被动更新

设置key过期的时间，让其自动失效。

是我们通常做的缓存数据过期时间设置，例如redis和memcache都提供了expire这样的API，来设置K-V的过期时间。

一般来说业务可以容忍一段时间内（例如一个小时），缓存数据和真实数据（例如：mysql, hbase等等）数据不一致（一般来说，缓存可以提高访问速度降低后端负载），那么我们可以对一个数据设置一定时间的过期时间，在数据过期后，再从真实数据源获取数据，重新放到缓存中，继续设置过期时间。

主动更新

更新DB的时候，同时更新缓存。一般业务都是主动更新和被动更新结合使用。

业务对于数据的一致性要求很高，需要在真实数据更新后，立即更新缓存数据。

具体做法：例如可以利用消息系统或者其他方式（比如数据库触发器，或者其他数据源的listener机制来完成）通知缓存更新。