Redis 内存淘汰算法有哪些?

千锋教育

Redis共支持八种淘汰策略,分别是noeviction、volatile-random、volatile-ttl、volatile-lru、volatile-lfu、allkeys-lru、allkeys-random 和 allkeys-lfu 策略。


怎么理解呢?主要看分三类看:


不淘汰


noeviction (v4.0后默认的) 


对设置了过期时间的数据中进行淘汰


随机:volatile-random 


ttl:volatile-ttl 


lru:volatile-lru 


lfu:volatile-lfu 


全部数据进行淘汰


随机:allkeys-random 


lru:allkeys-lru 


lfu:allkeys-lfu


LRU算法:LRU 算法的全称是 Least Recently Used,按照最近最少使用的原则来筛选数据。这种模式下会使用 LRU 算法筛选设置了过期时间的键值对。


Redis优化的LRU算法实现:


Redis会记录每个数据的最近一次被访问的时间戳。在Redis在决定淘汰的数据时,第一次会随机选出 N 个数据,把它们作为一个候选集合。接下来,Redis 会比较这 N 个数据的 lru 字段,把 lru 字段值最小的数据从缓存中淘汰出去。通过随机读取待删除集合,可以让Redis不用维护一个巨大的链表,也不用操作链表,进而提升性能。


LFU 算法:LFU 缓存策略是在 LRU 策略基础上,为每个数据增加了一个计数器,来统计这个数据的访问次数。当使用 LFU 策略筛选淘汰数据时,首先会根据数据的访问次数进行筛选,把访问次数最低的数据淘汰出缓存。如果两个数据的访问次数相同,LFU 策略再比较这两个数据的访问时效性,把距离上一次访问时间更久的数据淘汰出缓存。Redis的LFU算法实现:


当 LFU 策略筛选数据时,Redis 会在候选集合中,根据数据 lru 字段的后 8bit 选择访问次数最少的数据进行淘汰。当访问次数相同时,再根据 lru 字段的前 16bit 值大小,选择访问时间最久远的数据进行淘汰。


Redis 只使用了 8bit 记录数据的访问次数,而 8bit 记录的最大值是 255,这样在访问快速的情况下,如果每次被访问就将访问次数加一,很快某条数据就达到最大值255,可能很多数据都是255,那么退化成LRU算法了。所以Redis为了解决这个问题,实现了一个更优的计数规则,并可以通过配置项,来控制计数器增加的速度。