淘汰策略概述

redis作为缓存使用时,在添加新数据的同时自动清理旧的数据。这种行为在开发者社区众所周知,也是流行的memcached系统的默认行为。

redis中使用的LRU淘汰算法是一种近似LRU的算法。

淘汰策略

针对淘汰策略,redis有一下几种配置方案:

1、noeviction:当触发内存阈值时,redis只读不写;

2、allkeys-lru:针对所有的key,执行LRU(最近最少使用)策略;

3、allkeys-lfu:针对所有的key,执行LFU(最低频使用)策略;

4、volatile-lru:针对设置了过期时间的key,执行LRU(最近最少使用)策略;

5、volatile-lfu:针对设置了过期时间的key,执行LFU(最低频使用)策略;

6、allkeys-random:针对所有key,进行随机淘汰;

7、volatile-random:针对设置了过期时间的key,进行随机淘汰;

8、volatile-ttl:针对设置了过期时间的key,淘汰剩余过期时间最短的;

根据应用场景选择合适的淘汰策略是非常重要的,我们可以在程序运行时实时重置淘汰策略,并使用Redis INFO输出来监控缓存未命中和命中的数量,以优化设置。

根据以往使用惯例:

  • 当你希望某些元素的子集被访问的频率高于其他元素,或者当你不知道怎么选择淘汰策略时,allkeys-lru策略是一个很好的选择;
  • 当你在循环访问redis,且所有的key是被连续扫描时,或者你希望key过期时间均匀分布时,allkeys-random策略是一个很好的选择;
  • 如果你希望基于key不同的TTL时间筛选出哪些key可被淘汰,volatile-ttl策略是一个很好的选择;

还有一点是为key设置过期时间会占用内存,因此使用allkeys-lru这样的策略会更节省内存,因为在内存压力下不需要对key进行过期设置。

淘汰策略如何工作

淘汰过程如下:

  • 客户端执行一条指令,需要添加一批数据;
  • redis检测缓存阈值限制,如果超过阈值则执行淘汰策略;
  • 执行指令等等;

因此在redis的使用过程中,我们可能不断的超过内存阈值限制,然后执行淘汰策略再将内存恢复到阈值之下。

近似LRU算法

redis lru算法是一个近似lru算法,这意味着针对整个key集合,redis在执行lru策略时可能不会很精准的淘汰掉最应该被淘汰的key,相反的是,redis会通过抽样一小部分key,并淘汰采样key中最该被淘汰的。
自redis3.0以来,该算法得到了改善,能够抽样大批量的key进行淘汰,使其能够更接近真实LRU算法的行为。
redis lru算法的重要之处在于可以通过更改样本数量来调整算法的精度,此参数由以下配置指令控制:
maxmemory-samples 5

redis不使用真正的LRU实现的原因是它需要更多的内存。然而,对于使用Redis的应用程序,近似lru算法实际上是与精确lru算法差不多的。此图将redis使用的LRU近似值与真实LRU进行了比较。

用给定数量的key填充了Redis服务器(达到内存阈值)进行测试并生成了上面的图。从第一个到最后一个访问key。第一个key是使用LRU算法淘汰的最佳候选key。之后再添加50%以上的key,以强制淘汰一半的旧key。

你可以在图中看到三种点,形成了三个不同的区域:

  • 浅灰色区域是被淘汰的对象
  • 灰色区域是未被淘汰的对象
  • 绿色区域是新加的对象

在理论LRU实现中(theoretical LRU),我们预计旧key集合中的前一半将会被淘汰,与之相反,redis lru算法实现中,旧key集合中也只是会离散性的淘汰其中某些key。

正如您所看到的那样,与Redis 2.8相比,Redis 3.0在同样抽样数为5个时做得更好,但是大多数最新增加的key仍然被Redis 2.8保留。在Redis 3.0中使用10的样本大小,近似值非常接近Redis 3.0的理论性能。

在模拟中,我们发现使用幂律访问模式(类似20%的key承担了80%的访问),真实LRU和Redis近似LRU之间的差异极小或根本不存在。

使用CONFIG SET maxmemory samples<count>命令在生产中使用不同的样本大小值进行实验非常简单。

新的LFU模式

从redis4.0开始,可以在某些特定场景下使用低频淘汰策略。在选用LFU策略后,redis会跟踪key的访问频率,所以低频的key将被淘汰。这意味着经常访问的key有很大的机会一直留在内存中。

要配置LFU模式,可以使用以下策略:

  • volatile-lfu:针对设置了过期时间的key,使用近似lfu淘汰;
  • allkeys-lfu:针对所有key,使用近似lfu淘汰;

LFU近似于LRU:它使用一个称为Morris的概率计数器来估计key访问频率,计数器中每个key只占用几个bit,并且计数器功能附加衰减周期,这样计数器统计的key访问频率就会随着时间的推移而降低(如果一段时间内一个key访问频率低于计数器衰减速度,最终这个key会被淘汰)。直至某一刻,我们不再将一些key视为频繁访问的key,即使它们在过去是被频繁访问的,以便算法能够适应访问模式的变化。

该信息的采样方式与LRU(如本文档前一节所述)选择淘汰key的情况类似。

然而,与LRU不同的是,LFU具有某些可调参数:例如,如果一个频繁key不再被访问,那么它的访问频率级别应该降低多少?还可以调整Morris计数器范围,以更好地使算法适应特定的场景。

默认情况下,Redis配置为:

  • 在大约100万次请求时让计数器饱和;
  • 每一分钟使计数器衰减一次;

这些配置应该是合理的,并且经过了实验测试,但用户可能希望使用这些配置设置来选择最佳值。

有关如何调整这些参数的说明,可以在源发行版的示例redis.conf文件中找到。简而言之,它们是:

lfu-log-factor 10
lfu-decay-time 1

衰减时间是最明显的一个,它是计数器在采样时应该衰减的分钟数。特殊值0表示:永远不会衰减计数器。

计数器对数因子决定了使频率计数器达到饱和需要的key命中次数,频率计数器刚好在0-255范围内。系数越高,需要更多的访问才能达到最大值;系数越低,低频访问计数器的分辨率越好,如下表所示: