【redis】 LRU 和 LFU 算法_redislru和lfu算法的区别

1、简介

• Redis 中的 LRU（Least Recently Used）和 LFU（Least Frequently Used）算法是用于决定在内存空间不足时，哪些键（key）应该被删除以释放空间的策略。
• 这两种算法都试图通过跟踪键的使用情况来优化缓存的性能。

2、LRU  算法

• LRU 是一种常用的页面置换算法，它选择最久未使用的页面予以淘汰。
• 在 Redis 中，LRU 策略用于当内存达到 maxmemory 限制时，选择哪些键进行删除。然而，Redis 的 LRU 实现并不是严格意义上的 LRU，因为它采用了近似 LRU 算法，以节省内存和提高性能。
• Redis 的近似 LRU 算法通过随机采样一部分键，并基于这些键的访问时间来决定哪些键最久未使用。具体来说，Redis 会为每个键维护一个访问时间戳，当需要淘汰键时，它会随机选择一部分键，并比较这些键的访问时间戳，淘汰最久未使用的键。

3、 LFU 算法

• LFU 是一种基于访问频率的页面置换算法，它选择访问频率最低的页面予以淘汰。在 Redis 4.0 及更高版本中，引入了 LFU 淘汰策略。
• LFU 策略跟踪每个键的访问频率，并据此决定哪些键应该被删除。与 LRU 不同，LFU 不依赖于时间戳，而是根据键的访问次数来判断其“新鲜度”。
• 在 Redis 中，LFU 使用一个 8 位的计数器来记录每个键的访问频率，每当键被访问时，计数器就会增加。当需要淘汰键时，Redis 会选择访问频率最低的键进行删除。
• 为了更精确地跟踪访问频率，Redis 的 LFU 计数器采用了衰减机制。如果一个键在一段时间内没有被访问，它的计数器值会逐渐减小，从而反映出该键的“过时”程度。
• 这种机制有助于 Redis 在淘汰键时更好地平衡新数据和旧数据。

4、LRU与LFU算法的区别

• LRU（Least Recently Used）：最近最少使用算法，认为长时间不使用的数据在未来被使用的可能性也很小。Redis中LRU算法的实现采用了随机抽样的方式，提升了性能。
• LFU（Least Frequently Used）：最不常用算法，根据数据的访问频率来决定哪些数据应当被淘汰。LFU算法更加重视元素的访问频率，而非最近一次访问时间。

5、配置和使用

在 Redis 配置文件中（通常是 redis.conf），你可以通过 maxmemory-policy 选项来设置淘汰策略。对于 LRU 和 LFU 策略，你可以分别使用以下值：

• volatile-lru：对设置了过期时间的数据使用 LRU 算法淘汰。
• allkeys-lru：对所有数据使用 LRU 算法淘汰。
• volatile-lfu：对设置了过期时间的数据使用 LFU 算法淘汰。
• allkeys-lfu：对所有数据使用 LFU 算法淘汰。