你与解决“缓存污染”只差这篇文章的距离

服务器

浏览数:258

2019-4-4

微信公众号:IT一刻钟。 大型现实非严肃主义现场, 一刻钟与你分享优质技术架构与见闻,做一个有剧情的程序员。 关注可第一时间了解更多精彩内容,定期有福利相送哟。

什么是缓存污染?

由于缓存的读取速度比非缓存要快上很多,所以在高性能场景下,系统在读取数据时,是首先从缓存中查找需要的数据,如果找到了则直接读取结果,如果找不到的话,则从内存或者硬盘中查找,再将查找到的结果存入缓存,以备下次使用。

实际上,对于一个系统来说,缓存的空间是有限且宝贵的,我们不可能将所有的数据都放入缓存中进行操作,即便可以数据安全性也得不到保证,而且,如果缓存的数据量过大大,其速度也会变得越来越慢。 这个时候就需要考虑缓存的淘汰机制,但是淘汰哪些数据,又保留哪些数据,这是一个问题。如果处理不得当,就会造成“缓存污染”问题。

而缓存污染,是指系统将不常用的数据从内存移到缓存,造成常用数据的挤出,降低了缓存效率的现象。

解决缓存污染的算法

LFU算法

LFU,英文名Least Frequently Used,字面意思就是最不经常使用的淘汰掉算法,是通过数据被访问的频率来判断一个数据的热点情况。其核心理念是“历史上这个数据被访问次数越多,那么将来其被访问的次数也多”。

LFU中每个数据块都有一个引用计数器,所有数据块按照引用数从大到小的排序。

步骤:

  1. 新数据插入到尾部,并将计数设置为1;
  2. 当队列中的数据被访问后,引用计数+1,然后重新排序,保持引用次数从大到小排序;
  3. 当空间不足,需要淘汰数据时,将尾部引用计数最小的数据块删除。

分析:由于是根据频数进行热点判断和淘汰,所以先天具备避免偶发性、周期性批量操作导致临时非热点数据大量涌入缓存,挤出热点数据的问题。 虽然具备这种先天优势,但依旧存在另一种缓存污染问题,即历史热点数据污染当前热点数据,如果系统访问模式发生了改变,新的热点数据需要计数累加超过旧热点数据,才能将旧热点数据进行淘汰,造成热点效应滞后的问题。

复杂度与代价:每次操作都需要进行计数和排序,并且需要维护每个数据块计数情况,会占用较高的内存与cpu。

一个小思考,根据LFU算法,如何以O(1)时间复杂度实现get和put操作缓存?

LFU-Aging算法

LFU-Aging是基于LFU的改进算法,目的是解决历史热点数据对当前热点数据的污染问题。有些数据在开始时使用次数很多,但以后就不再使用,这类数据将会长时间留在缓存中,所以“除了访问次数外,还要考虑访问时间”,这也是LFU-Aging的核心理念。

虽然算法将时间纳入了考量范围,但LFU-Aging并不是直接记录数据的访问时间,而是增加了一个最大平均引用计数的阈值,然后通过当前平均引用计数来标识时间,换句话说,就是将当前缓存中的平均引用计数值当作当前的生命年代,当这个生命年代超过了预设的阈值,就会将当前所有计数值减半,形成指数衰变的生命年代。

分析:优点是当访问模式发生改变的时候,生命年代的指数衰变会使LFU-Aging能够更快的适用新的数据访问模式,淘汰旧的热点数据。

复杂度与代价:在LFU的基础上又增加平均引用次数判断和统计处理,对cpu的消耗更高,并且当平均引用次数超过指定阈值(Aging)后,还需要遍历每一个数据块的引用计数,进行指数衰变。

Window-LFU算法

Window-LFU顾名思义叫做窗口期LFU,区别于原义LFU中记录所有数据的访问历史,Window-LFU只记录过去一段时间内(窗口期)的访问历史,相当于给缓存设置了有效期限,过期数据不再缓存。当需要淘汰时,将这个窗口期内的数据按照LFU算法进行淘汰。

分析:由于是维护一段窗口期的记录,数据量会比较少,所以内存占用和cpu消耗都比LFU要低。并且这段窗口期相当于给缓存设置了有效期,能够更快的适应新的访问模式的变化,缓存污染问题基本不严重。

复杂度与代价:维护一段时期内的数据访问记录,并对其排序。

LRU算法

LRU算法,英文名Least Recently Used,意思是最近最少使用的淘汰算法,根据数据的历史访问记录来进行淘汰数据,核心思想是“如果数据最近被访问过1次,那么将来被访问的概率会更高”,类似于就近优先原则。

步骤:

  1. 新数据插入到链表头部;
  2. 每当命中缓存,便将命中的缓存数据移到链表头部;
  3. 当链表满的时候,将链表尾部的数据丢弃。

分析:偶发性的、周期性的批量操作会使临时数据涌入缓存,挤出热点数据,导致LRU热点命中率急剧下降,缓存污染情况比较严重。

复杂度与代价:数据结构复杂度较低;每次需要遍历链表,找到命中的数据块,然后将数据移到头部。

LRU-K算法

LRU-K是基于LRU算法的优化版,其中K代表最近访问的次数,从某种意义上,LRU可以看作是LRU-1算法,引入K的意义是为了解决上面所提到的缓存污染问题。其核心理念是从“数据最近被访问过1次”蜕变成“数据最近被访问过K次,那么将来被访问的概率会更高”。

LRU-K与LRU区别是,LRU-K多了一个数据访问历史记录队列(需要注意的是,访问历史记录队列并不是缓存队列,所以是不保存数据本身的,只是保存对数据的访问记录,数据此时依旧在原始存储中),队列中维护着数据被访问的次数以及时间戳,只有当这个数据被访问的次数大于等于K值时,才会从历史记录队列中删除,然后把数据加入到缓存队列中去。

步骤:

  1. 数据第一次被访问时,加入到历史访问记录队列中,访问次数为1,初始化访问时间戳;
  2. 如果数据访问次数没有达到K次,则访问次数+1,更新时间戳。当队列满了时,按照某种规则(LRU或者FIFO)将历史记录淘汰。为了避免历史数据污染未来数据的问题,还需要加上一个有效期限,对超过有效期的访问记录,进行重新计数。(可以使用懒处理,即每次对访问记录做处理时,先将记录中的访问时间与当前时间进行对比,如果时间间隔超过预设的值,则访问次数重置为1并更新时间戳,表示重新开始计数)
  3. 当数据访问计数大于等于K次后,将数据从历史访问队列中删除,更新数据时间戳,保存到缓存队列头部中(缓存队列时间戳递减排序,越到尾部距离当前时间越长);
  4. 缓存队列中数据被再次访问后,将其移到头部,并更新时间戳;
  5. 缓存队列需要淘汰数据时,淘汰缓存队列中排在末尾的数据,即:淘汰“倒数第K次访问离现在最久”的数据。

分析:LRU-K降低了“缓存污染”带来的问题,命中率比LRU要高。实际应用中LRU-2是综合各种因素后最优的选择,LRU-3或者更大的K值命中率会高,但适应性差,一旦访问模式发生变化,需要大量的新数据访问才能将历史热点访问记录清除掉。

复杂度与代价:LRU-K队列是一个优先级队列。由于LRU-K需要记录那些被访问过,但还没有放入缓存的对象,导致内存消耗会很多。

URL-Two queues算法

URL-Two queues算法类似于LRU-2,不同点在于URL-Two queues将LRU-2算法中的访问历史队列(注意这不是缓存数据的)改为一个FIFO缓存队列,即:URL-Two queues算法有两个缓存队列,一个是FIFO队列(First in First out,先进先出),一个是LRU队列

当数据第一次访问时,URL-Two queues算法将数据缓存在FIFO队列里面,当数据第二次被访问时,则将数据从FIFO队列移到LRU队列里面,两个队列各自按照自己的方法淘汰数据。

步骤:

  1. 新访问的数据先插入到FIFO队列中;
  2. 如果数据在FIFO队列中一直没有被再次访问,则最终按照FIFO规则淘汰;
  3. 如果数据在FIFO队列中被再次访问,则将数据从FIFO删除,加入到LRU队列头部;
  4. 如果数据在LRU队列再次被访问,则将数据移到LRU队列头部;
  5. LRU队列淘汰末尾的数据。

分析:URL-Two queues算法和LRU-2算法命中率类似,但是URL-Two queues会减少一次从原始存储读取或计算数据的操作。命中率要高于LRU。

复杂度与代价:需要维护两个队列,代价是FIFO和LRU代价之和。

五三LRU算法

emmmm…

这个名字其实是我取的,大概是这种算法还没有被命名?当然,这是一个玩笑话。

我是在mysql底层实现里发现这个算法的,mysql在处理缓存淘汰时是用的这个方法,有点像URL-Two queues的变体,只是我们只需要维护一个队列,然后将队列按照5:3的比例进行分割,5的那部分叫做young区,3的那部分叫做old区。具体是怎么样的请先看我把图画出来:

步骤:

  1. 第一次访问的数据从队列的3/8处位置插入;
  2. 如果数据再次被访问,则移动到队列头部;
  3. 如果数据没有被再访问,会逐步被热点数据驱逐向下移;
  4. 淘汰尾部数据。

分析:五三LRU算法算作是URL-Two queues算法的变种,原理其实是一样的,只是把两个队列合二为一个队列进行数据的处理,所以命中率和URL-Two queues算法一样。

复杂度与代价:维护一个队列,代价较低,但是内存占用率和URL-Two queues一样。

Multi Queue算法

Multi Queue算法根据访问频率将数据划分为多个队列,不同的队列具有不同的访问优先级,其核心思想是“优先缓存访问次数多的数据”。

Multi Queue算法将缓存划分为多个LRU队列,每个队列对应不同的访问优先级。访问优先级是根据访问次数计算出来的,例如: Q0,Q1….Qn代表不同的优先级队列,Q-history代表从缓存中淘汰数据,但记录了数据的索引和引用次数。

步骤:

  1. 新插入的数据放入Q0;
  2. 每个队列按照LRU管理数据,再次访问的数据移动到头部;
  3. 当数据的访问次数达到一定次数,需要提升优先级时,将数据从当前队列删除,加入到高一级队列的头部;
  4. 为了防止高优先级数据永远不被淘汰,当数据在指定的时间里访问没有被访问时,需要降低优先级,将数据从当前队列删除,加入到低一级的队列头部;
  5. 需要淘汰数据时,从最低一级队列开始按照LRU淘汰;每个队列淘汰数据时,将数据从缓存中删除,将数据索引加入Q-history头部;
  6. 如果数据在Q-history中被重新访问,则重新计算其优先级,移到目标队列的头部;
  7. Q-history按照LRU淘汰数据的索引。

分析:Multi Queue降低了“缓存污染”带来的问题,命中率比LRU要高。

复杂度与代价:Multi Queue需要维护多个队列,且需要维护每个数据的访问时间,复杂度比LRU高。Multi Queue需要记录每个数据的访问时间,需要定时扫描所有队列,代价比LRU要高。虽然Multi Queue的队列看起来数量比较多,但由于所有队列之和受限于缓存容量的大小,因此这里多个队列长度之和和一个LRU队列是一样的,因此队列扫描性能也相近。

说在后面话

还有哪些优秀的缓存淘汰算法,或者你有更好的想法或问题,欢迎留言给我!

 

 

                                    喜欢就点一下「小心心」呗~