面试题：Redis缓存淘汰策略有哪些？简述LRU和LFU策略的原理

Question

请列举出Redis常见的缓存淘汰策略，并详细说明LRU（最近最少使用）和LFU（最不经常使用）这两种策略的工作原理，以及它们在实际应用场景中的优缺点。

Answer 1

Redis常见缓存淘汰策略

1. noeviction：当内存不足以容纳新写入数据时，新写入操作会报错。
2. allkeys-lru：从所有key中，使用LRU算法淘汰最近最少使用的key。
3. volatile-lru：从设置了过期时间的key中，使用LRU算法淘汰最近最少使用的key。
4. allkeys-random：从所有key中随机淘汰某个key。
5. volatile-random：从设置了过期时间的key中随机淘汰某个key。
6. volatile-ttl：从设置了过期时间的key中，优先淘汰剩余时间TTL（Time To Live）短的key。
7. allkeys-lfu：从所有key中，使用LFU算法淘汰最不经常使用的key。
8. volatile-lfu：从设置了过期时间的key中，使用LFU算法淘汰最不经常使用的key。

LRU（最近最少使用）策略工作原理

LRU算法维护一个链表，链表头是最近使用的元素，链表尾是最久未使用的元素。当有新元素被访问时，如果它已经在链表中，将其移动到链表头；如果不在链表中，将其添加到链表头。当需要淘汰元素时，淘汰链表尾的元素。在实际实现中，Redis并没有使用完整的链表来实现LRU，而是采用了一种近似LRU算法，通过为每个key记录一个访问时间戳，在进行淘汰时随机采样一部分key，根据它们的访问时间戳来选择淘汰最近最少使用的key。

LRU策略优缺点

• 优点：
  • 比较符合大多数应用场景下数据的访问模式，近期使用过的数据在未来被使用的概率相对较高，因此能有效减少缓存穿透，提高缓存命中率。
  • 实现相对简单，不需要额外记录数据的访问频率等复杂信息。
• 缺点：
  • 无法区分偶尔访问一次但近期访问过的数据和经常访问的数据。例如，一个很少使用的大key在近期被访问了一次，按照LRU算法它不会被淘汰，可能会导致缓存空间浪费，影响其他经常使用的小key进入缓存。
  • 严格的LRU算法需要完整的链表结构，内存开销较大，Redis采用的近似LRU算法虽然降低了内存开销，但可能导致淘汰的key并非是真正最久未使用的，从而影响缓存命中率。

LFU（最不经常使用）策略工作原理

LFU算法为每个key维护一个访问频率计数器。当key被首次访问时，计数器初始化为1。此后，每访问一次该key，计数器就增加1。当需要淘汰key时，优先淘汰计数器值最小的key，即最不经常使用的key。在Redis中，LFU实现并非简单的直接记录访问次数，而是采用了一种基于概率的方式，通过两个8位字段来近似表示访问频率，一个记录最近的访问时间衰减，另一个记录访问频率，这样既减少了内存开销，又能较好地反映数据的访问频率情况。

LFU策略优缺点

• 优点：
  • 能更好地区分访问频率不同的数据，优先淘汰访问频率低的key，相比LRU更能有效利用缓存空间，提高缓存命中率。
  • 对于访问模式变化较大的场景，LFU能更快适应，因为它基于访问频率而非仅基于访问时间，能更准确地判断数据的重要性。
• 缺点：
  • 实现相对复杂，需要额外记录和更新每个key的访问频率信息，内存开销比LRU略高。
  • 初始阶段可能会出现问题，因为新加入的key访问频率初始值较低，可能在短时间内就被淘汰，即使它们未来可能会被频繁访问。为了解决这个问题，Redis的LFU实现会对新key有一定的保护机制，使其在初始阶段不容易被淘汰。