2024-05-02  阅读(37)
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 本文链接:https://www.skjava.com/mianshi/baodian/detail/2832026939

回答

Redis 的缓存淘汰策略是 Redis 管理内存的一种机制。当 Redis 使用的内存达到 maxmemory 参数配置的阈值的时候,Redis 会根据特定的缓存淘汰策略来决定哪些数据应该被删除,以便为新的写入操作释放内存空间。

Redis 提供了 8 种缓存淘汰策略:

  • noeviction:默认淘汰策略。不删除任何数据,当内存使用达到阈值时,所有尝试写入的操作都会报错。
  • allkeys-random:从所有 key 中随机选择并淘汰。
  • allkeys-lru:对所有 key 使用 LRU 算法进行删除。淘汰最近最少使用的键。
  • allkeys-lfu:对所有 key 使用 LFU 算法进行删除。淘汰访问频率最低的键。
  • volatile-random:对已设置过期时间的 key 随机删除。
  • volatile-lru:对已设置过期时间的 key 使用 LRU 算法进行删除。
  • volatile-lfu:对已设置过期时间的 key 使用 LFU 算法进行删除。
  • volatile-ttl:从已设置过期时间的键中选择将要最先过期的键进行淘汰。

常见缓存淘汰算法

FIFO:先进先出算法

FIFO(First-In, First-Out),先进先出算法。它的核心思路是最先进入缓存的数据最先被淘汰,该算法是基于一种比较简单的假设:最早被存储的数据最可能是不再需要的。

其工作原理是:

  • 内部维护了一个队列,数据按照它们进入缓存的顺序排列。
  • 当新数据被加载到缓存中时,它被放置在队列的尾部。
  • 当缓存达到其容量上限时,位于队列头部的数据(即最早进入缓存的数据)将被移除以腾出空间给新数据。

FIFO 算法的逻辑比较简单,容易实现,而且保证了绝对的公平性。但是 FIFO 算法不考虑数据的访问频率,最早进入缓存的数据也有可能是热点数据,但是 FIFO 依然会将该数据淘汰掉,这样就降低了缓存的命中率了。

所以,FIFO 算法一般都比较适用于数据访问比较均匀的场景,但是这种场景在实际业务中都会比较少。

LRU:最近最少使用算法

LRU(Least Recently used),最近最少使用算法。

LRU 根据数据的历史访问记录来进行淘汰数据,其核心思想是:“如果数据最近被访问过,那么将来被访问的几率也更高”。所以,当内存容量满了后,优先淘汰最近很少使用的数据。

其过程如下:

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

如下图

从上面图中我们可以看,LRU 算法是需要添加头节点和删除尾节点,这种特性比较适合使用链表来实现,因为链表添加节点、删除节点时间复杂度 O(1),但是我们不能单纯地使用单向链表,因为单向链表有几个缺陷:

  1. 随机访问某个节点时,需要从头节点开始遍历,时间复杂度为 O(N)
  2. 移动中间节点到头节点时,需要知道它的前节点,而这个时候又需要从头节点开始遍历。

目前一种比较常见的实现方法是使用哈希表与双向链表结合。哈希表用于快速定位数据项在链表中的位置,而双向链表则按照每个元素的访问顺序排列。如下:

在双向链表中,头节点和尾节点是不用存储任何数据的,他们是两个『哨兵』节点,增加这两个哨兵节点,在增加和删除节点的时候是不需要考虑边界情况的,简化了变成难度。

当存在热点数据时,LRU 的效率很好,因为频繁访问的热点数据会保持在缓存中,但是,在面对偶发性的大量数据访问或周期性的批量操作时,会导致LRU命中率急剧下降。

  • 大量的一次性访问:如果有大量的一次性访问数据(比如批处理作业),这些数据可能会替换掉当前缓存中的热点数据。这种情况被称为“缓存污染”,因为这些只被访问一次的数据占据了缓存空间,导致频繁访问的数据被移出缓存。
  • 周期性访问:如果数据的访问具有周期性,比如,某个数据每小时访问一次。在这种情况下,LRU可能在每个周期结束时都会将这些数据移出缓存,导致每次都需要重新加载。

基于这个缺陷,MySQL InnoDB 改进 LRU 算法,将链表拆分成两部分,分为热数据区,与冷数据区:

LFU:最近最不常用算法

LFU(Least Frequently Used)**: **最近最不常用算法。

LFU 根据数据的历史访问频率来淘汰数据。其核心思想是:如果数据过去被访问多次,那么将来被访问的频率也更高。它与 LRU 算法的区别是,LRU 是基于访问时间,而 LFU 是基于访问次数。

LFU为每个数据维护一个计数器,记录该数据从加入缓存以来被访问的次数。当缓存空间满时,访问次数最少的数据将被淘汰。过程如下:

  1. 在缓存中找到了需要访问的数据,则将访问的数据从队列中取出,并将数据对应的计数器 +1,然后将其放到计数相同的数据队列头部。
  2. 如果没有找到,则先获取数据,然后将其加入到缓存队列的尾部,计数为 1,需要注意的是,也是加入到计数为 1 的最前面。
  3. 如果此时缓存已满,则淘汰队列尾部频率最小的数据,然后再在队列尾部加入新数据。

LFU 算法对长期热点数据很友好,因为它会长期存在缓存当中,而且比 LRU 更能抵抗短期的访问波峰。但是它有两个缺点:

  1. 如果某些数据短期内被频繁访问,之后就很少访问了,由于它的计数比较大,导致它会存在缓存中相当长一段时间,这会产生一个“陈旧的热点数据”问题。
  2. 对于刚刚加入的缓存的新数据不友好,因为刚刚加入,它的计数值很低,很容就会被删除了,及时它后面可能会被频繁使用。

对于,这种新数据因为计数低而被删除的情况,我们可以使用“二次机会LFU”,即,不是立刻淘汰访问次数最少的数据,而是给它们一次“再被访问”的机会,这样就可以避免刚被加入但访问次数较少的数据被过早淘汰。

ARC:自适应缓存替换算法

ARC(Adaptive Replacement Cache),自适应缓存替换算法。

ARC 是一种智能的缓存淘汰算法,由 Nimrod Megiddo 和 Dharmendra S. Modha 于 2003 年提出(论文地址)。其核心思想是结合LRULFU 的优点,同时自适应地调整对这两种算法的依赖度,以优化缓存的性能,来获得可用缓存的最佳使用。

ARC 维护两个链表:

  • 最近最多使用的缓存链表,LRU链表
  • 最近最频繁使用的缓存链表,LFU链表

同时还使用了两个链表来跟踪最近被淘汰的数据:

  • 最近从 LRU 表中淘汰的缓存链表,ghost LRU链表
  • 最近从 LFU 表中淘汰的缓存链表,ghost LFU链表

所有数据首次进入缓存都会被放在LRU链表中,当被访问第二次时会进入LFU链表,且越是最近访问的数据越靠近头部。其自适应过程如下:

  • 当一个数据项被访问时,如果它在LRULFU中,则将其移到相应队列的顶部。
  • 如果访问的数据在 ghost LRU 中,则说明 LRU 缓存太小了,则需要增加 LRU 的大小,相应地增加 LFU 的大小。LFU 同理

当有一个新的数据请求发生时,ARC 根据以下规则来处理:

  1. 如果请求的数据在LRULFU中,这表明缓存命中了,将该数据移动到 LFU 中去,表示它不仅被最近访问,而且可能被频繁访问。
  2. 如果请求的数据不在 LRULFU 中,但在 ghost LRU 中,这表示最近被淘汰的数据又被访问了。则需要增加 LRU 的空间,同时将数据移动到 LFU 中去。
  3. 如果请求的数据不在 LRULFU 中,但在 ghost LFU 中,这表示该数据虽然不是最近访问的,但在之前是频繁访问的。则需要增加 LFU 的空间,同时将数据移动到 LFU 中去。
  4. 如果请求的数据不在四个列表里面,则按照如下情况来
    1. 如果 LRUghost LRU 列表的总大小超过了缓存大小,则从ghost LRU列表中移除数据,并可能从 LRU 列表中淘汰数据以腾出空间。
    2. 如果 LRULFU 列表的总大小加上两个 ghost 列表的大小超过了缓存的两倍大小,从 ghost LFU 列表中移除数据。
    3. 新数据添加到LRU列表中。

ARC 算法比 LRULFU 有更好的缓存命中率,尤其是在访问模式频繁变化的情况下。但是它实现比较复杂,而且需要维护四个队列,需要消耗更多的内存资源。

MRU:最近最常使用算法

MRU(Most Recently Used):最近最常使用算法。

MRULRU 是相反的,它的核心思想是:“淘汰那些最近被使用过的数据项”。MRU 是基于这样一个假设:最近被访问过的数据项在不久的将来可能不会再次被访问。

其工作过程如下:

  • 每当有数据被访问时,无论是读取还是写入,该数据项都会被标记为“最近使用过”。
  • 当缓存达到其容量上限并且需要空间来存储新的数据项时,MRU会选择最近被访问过的数据项进行淘汰。

MRU 是一个比较有意思的缓存淘汰算法,它一般不适用于一些常规场景,反而适用一些特殊场景,比如非重复访问。

阅读全文
  • 点赞