Fork me on GitHub

Redis淘汰策略

前言

当Ridis被用作缓存时,我们添加新数据后可以很方便的删除旧数据。这种行为在开发过程中十分常见,这种行为是内存型数据库的默认行为。

当然,数据库对旧数据进行处理的前提是我们的数据存储达到了设定的值。

在Redis中,LRU(Less Recently Used)是比较常用的数据淘汰策略,其方式就是当内存达到指定值时,清除一部分当前较少被使用(Less Recently Used)的数据。

从Redis 4.0版本开始,Redis引入了一个新的内存数据淘汰策略LFU(Least Frequently Used),清除最不经常使用的的内存数据。

正文

Maxmemory配置指令

maxmemory 配置指令是用来配置Redis使用指定数量的内存数据集。

我们可以使用redis.conf文件设置配置指令,或者在运行时使用CONFIG set命令设置。

比如,我们想限制Redis使用最大100M的内存,则可以在redis.conf文件中如下配置。

1
maxmemory 100mb

maxmemory设置为0会导致没有内存限制。这是64位系统的默认行为,而32位系统使用隐式内存限制为3GB

当达到指定的内存量时,我们可以设定不同的淘汰策略。Redis可以只返回错误的命令,这可能导致更多的内存被使用,或者它可以淘汰一些旧数据,以便添加新的数据。

淘汰策略

当数据量达到maxmemory限制时,Redis的确切行为是使用maxmemory-policy配置指令配置的。

有以下策略:

  • noeviction:当达到内存限制且客户端试图执行可能导致使用更多内存的命令时返回错误(大多数是write 命令,除了DEL和其他一些异常)。
  • allkeys-lru:通过首先尝试删除最近使用较少的(LRU)键来删除数据,以便为添加的新数据腾出空间。
  • volatile-lru:通过尝试首先删除最近较少使用的(LRU)键,但仅在具有过期时间的键中删除,从而为添加的新数据腾出空间。
  • allkeys-random:随机删除键,以便为添加的新数据腾出空间。
  • volatile-random:随机删除键,以便为添加的新数据腾出空间,但仅删除具有过期时间的键。
  • volatile-ttl:删除具有过期时间的键值,并首先尝试删除具有较短生存时间(TTL)的键值,以便为添加的新数据腾出空间。

如果没有匹配到先决条件的淘汰键,volatile-lruvolatile-randomvolatile-ttl策略的行为类似于noeviction

根据应用程序的访问模式选择正确的回收策略是十分重要的,但是我们也可以在运行时重新配置策略,当应用程序运行时,使用 Redis INFO 命令输出信息来监控缓存丢失和命中的数量,以便调整我们的设置。

一般经验法则:

  • 当我们的请求数据量呈幂律分布时,即访问一部分元素比其它元素更频繁时,可以使用allkeys-lru策略,这是一个不错的选择。
  • 如果我们的访问比较均匀,所有的键都可能平等的被访问(期望分布均匀),那么可以使用allkeys-random策略。
  • 如果我们创建对象的时候,设置了对象的过期时间(TTL),那么可以使用volatile-ttl策略。
  • 当我们使用Redis单例缓存持久数据时,volatile-lruvolatile-random策略就非常有用了。当然,使用两个Redis实例来解决这个问题通常更好。

需要注意的是,为键设置过期时间会消耗内存,因此使用allkeys-lru这样的策略更能有效地利用内存,因为在内存压力下不需要为要淘汰的键设置过期时间。

幂律分布:数学模型,如二八原则:20%的人口拥有80%的财富,20%的上市公司创造80%的价值,80%的收入来自20%的商品等等。

淘汰过程如何进行

我们需要知道淘汰策略是如下进行的:

  1. 客户端运行一个新命令,导致更多数据被添加;
  2. Redis检查内存使用,如果超过maxmemory限制,便会根据策略淘汰数据;
  3. 执行一个新命令,以此类推。

所以实际是不断的跨越maxmemory边界限制,检测到,而后通过淘汰某些数据使内存回到限制下。

如果一个命令导致一段时间内使用了大量内存(如向一个大集合big set里插入一个新的key),那么内存限制可能会短时间内超过很多。

近似LRU算法

需要注意的是RedisLRU算法只是一个近似的实现。这就意味着Redis并不一定能淘汰最佳的需要被淘汰的数据。

Redis通过运行近似LRU算法,对少量数据key进行采样,然后在采样数据中找到最好的(访问时间最旧的key),并将其淘汰。

从Redis 3.0以后,算法得到了改进,采取了一个好的候选淘汰池。这提高了算法的性能,使其更能够更接近真实LRU算法的行为。

RedisLRU算法有一个比较重要的点,我们可以改变样本数量来调整算法的精度,参数控制如下:

1
maxmemory-samples 5

Redis不使用真正LRU算法的根本原因是其需要很多内存。其实对于使用Redis的应用来说,这个近似LRU算法和真正的LRU算法是等价的。

下面是Redis使用的LRU近似值与真实LRU之间的图形比较。

upload successful

上述图形生成过程:使用给定数量的key填充Redis,然后从第一个键访问到最后一个键,因此第一个键是使用LRU算法淘汰的最佳候选键。然后增加50%的键,迫使Redis淘汰一半的键。

可以看到上图的数据点,形成了3个不同的带。

  • 浅灰色带是被淘汰的对象。
  • 灰色带是未被淘汰的对象。
  • 绿带是新添加的对象。

在理论上的LRU实现中,我们期望在旧的键中,将前一半淘汰。而Redis LRU算法只会概率地使旧键被淘汰。

正如我们所看到的,与Redis 2.8相比,Redis 3.0在5个样本上做得更好,但是大多数最新访问的对象仍然保留在Redis 2.8中。在Redis 3.0中使用10个样本大小,这个近似非常接近于理论性能的Redis 3.0

需要注意的是,LRU只是一个模型,用于预测给定key在未来被访问的可能性。此外,如果我们数据访问模式与幂律分布非常相似,那么大多数访问将位于LRU近似算法能够很好处理的键集中。

在模拟中,我们发现使用幂律访问模式,真实LRU近似和Redis LRU近似之间的差异极小或不存在。

但是,我们可以以额外的CPU使用为代价将样本大小增加到10,以接近真实的LRU,并检查这是否会对缓存漏报率产生影响。

通过使用配置集maxmemory-samples \命令,在生产环境中使用不同的样本大小值进行试验,这非常简单。

新的LFU策略模式

Redis 4.0中,我们可以使用一种新的淘汰策略模式,LFU(Least Frequently Used)。在某些情况下,这种策略模式可能更好(提供更好的命中/丢失比率),因为使用LFURedis会尝试跟踪访问条目的频率,所以使用很少的会被清除,而经常使用的会被留在内存中。

而我们想下LRU,最近访问过但实际上几乎从未请求过的项将不会淘汰,因此风险是淘汰一个将来有更高机会被请求的键。LFU不存在这个问题,一般来说能更好地适应不同的访问模式。

LFU有以下策略模式可以使用:

  • volatile-lfu:在设置过期时间的键里使用近似LFU模式淘汰键。
  • allkeys-lfu:使用近似LFU模式淘汰任何键。

LFULRU有些类似:它使用概率计算器,一种叫Morris counter的计数器。根据一些对象的访问频率,结合衰减期来进行估算。

信息采样类似于LRU,选择一个合适的候选数据以便淘汰掉。

LRU不同的是,LFU有某些参数可调,如果一个频繁的条目不再被访问,它的排名应该降低多快? 还可以调优Morris计数器范围,以便更好地使算法适应特定的用例。

Redis 4.0默认配置如下:

  • 大约一百万个请求使计数器饱和。
  • 每隔一分钟衰减一下计数器。

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

关于如何调优这些参数的说明可以在源代码分发版的示例redis.conf文件中找到,但简单地说,它们是:

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

lfu-decay-time :衰减时间,计数器应衰减的分钟数,当采样并发现比该值更早的值时。一个特殊的值0表示:每次扫描时总是衰减计数器,很少有用。

lfu-log-factor :计数器对数因子,使计数器达到饱和所需的命中次数,该次数刚好在0-255范围内。系数越高,为了达到最大值,需要的访问次数就越多。系数越低,计数器对于低访问频率的表现越好,由下表可知:

factor100 hits1000 hits100K hits1M hits10M hits
0104255255255255
11849255255255
101018142255255
10081149143255

所以基本上这个因子就是在低访问和高访问之间进行权衡。更多的信息可以在示例redis.conf文件中获得。

由于LFU是一个新特性,如果我们在实际使用中可以与LRU进行比较,得到的信息及疑问可以反馈给Redis官方。

总结

本文通过对Redis淘汰策略的介绍,了解了Redis淘汰模式的一些特点和用法,这对我们是比较有帮助的。

参考/翻译

  1. Using Redis as an LRU cache



-------------文章结束啦 ~\(≧▽≦)/~ 感谢您的阅读-------------

SakuraTears wechat
扫一扫关注我的公众号
您的支持就是我创作的动力!
0%