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 算法淘汰。