回答

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 年提出（论文地址）。其核心思想是结合LRU 和LFU 的优点，同时自适应地调整对这两种算法的依赖度，以优化缓存的性能，来获得可用缓存的最佳使用。

ARC 维护两个链表：

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

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

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

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

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

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

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

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

MRU：最近最常使用算法

MRU（Most Recently Used）：最近最常使用算法。

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

其工作过程如下：

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

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