Redis 键淘汰策略

概述

在内存紧张时，Redis 能够在添加数据时选择性的删除一些老数据。本文将会详述 maxmemory 指令，该指令可用来限制 redis 使用内存大小。另外会重点讲述 redis 的 LRU 键驱逐算法，redis 使用的 LRU 算法不是“精确”的，这一点会在后文指出。

注：以下会混用 key 和 ‘键’，他们表达相同的含义。

Maxmemory 指令

maxmemory 指令用来配置 redis 存储数据最大可用的内存空间。我们可以修改 redis.conf 中的配置项，也可以在运行时通过 config set 命令动态修改。举个例子，我们想限制 redis 至多使用 100m 空间来存储数据，可配置如下：

maxmemory 100mb

如果设置 maxmemory 为 0，表示无限制。64 位机上，默认就是无限制，32 位机上则隐式限制为 3GB。当达到指定的内存限制时，键驱逐策略决定了 redis 默认行为，例如：写操作可能会超出内存限制时，根据驱逐策略，redis 可以返回错误，也可以驱逐一些老数据再添加新数据。

驱逐策略

当达到内存限制时，redis 的行为取决于 maxmemory-policy 指令配置的内存驱逐策略，redis 提供了以下几种内存驱逐策略：

• noeviction：当到达内存限制时，新的值不会被保存。当数据库开启了复制（也就是有副本），该策略适用于主实例。
• allkeys-lru：当到达内存限制时，保留最近使用的键，驱逐最长时间未使用的键。
• allkeys-lfu：当到达内存限制时，保留最常使用的键， 驱逐最少使用的键。
• volatile-lru：当到达内存限制时，驱逐最长时间未使用且设置了过期时间的键。
• volatile-lfu：当到达内存限制时，驱逐最少使用的且设置了过期时间的键。
• allkeys-random：当到达内存限制时，随机驱逐一些键以便添加新数据。
• volatile-random：当到达内存限制时，随机驱逐一些设置了过期时间的键。
• volatile-ttl：当到达内存限制时，驱逐设置了过期时间且 ttl 剩余时间最短的键。

注：lru 一般用于内存换页算法，每个页面如果被访问就会被赋予一个访问时间，当内存不足时，选择那些上次访问时间距离当前时间最长的页面换出。

如果没有键满足驱逐条件时，volatile-lru、volatile-lfu、volatile-random、和 volatile-ttl 这几个驱逐策略和 noeviction 是相同的。根据应用的特性，选择合适的驱逐策略是很重要的。可以利用 INFO 命令监控缓命中与否并在运行时动态调整驱逐策略。

以下是选择驱逐策略的一些经验法则：

• 当一些 key 的访问远比另外一些频繁时，就是用 allkeys-lru 策略。另外当你不确定选择什么策略的时候，选择该策略通常是一个好选择。这比你考试时选择题不知道选啥都选 C 靠谱多了。
• 当所有的 key 访问比较均衡时，就可以考虑 allkeys-random。
• 当你想通过给 key 设置不同的 ttl 给 redis 提供键驱逐暗示时，可以考虑 volatile-ttl。

volatile-lru 和 volatile-random 一个使用场景是你想把一个 redis 实例既当做缓存使用又当做一些 key 的持久化存储使用。

注：volatile-* 系列的驱逐策略都要求键设置了过期时间才能驱逐，而其他的驱逐策略任意 key 都有潜在被驱逐的风险。

key 驱逐是如何工作的

• 客户端请求执行一个新的写入命令；
• Redis 检查内存使用，如果超过了 maxmemory 配置的值，redis 会根据驱逐策略驱逐一部分 key。
• 重复以上两步。

Redis 文档中提到内存超限后，redis 可能经常游走在内存限制的边缘（可能会在短时间内超出 maxmemory 限制的值），并最终通过驱逐策略回到内存限制的值下方。以下是原文：

So we continuously cross the boundaries of the memory limit, by going over it, and then by evicting keys to return back under the limits.

If a command results in a lot of memory being used (like a big set intersection stored into a new key) for some time, the memory limit can be surpassed by a noticeable amount.

近似 LRU 算法

Redis 并不采用精确的 LRU 算法，换句话说 redis 不能精确移除那些最长时间未使用的键。redis 使用的近似的 lru 算法，这是一种采用算法，采集一部分 key，并在样本中移除最长时间未使用的键。可以通过 maxmemory-samples 指令配置采样数量。

maxmemory-samples 5

这种近似 lru 算法很接近于真实的 lru 算法，特别是在访问符合幂次分布的情况下。之所以采用近似 LRU，是为了减少内存的使用。当我们将 maxmemory-samples 配置到 10 的时候，将会非常接近于真实的 lru 算法，代价是消耗更多的 cpu。

以下是一个真实 lru 算法和 近似 lru 算法的对比图：

先将 redis 填满 key，然后再添加 maxmemory 一半的 key。图中绿色部分是新加的 key，淡灰色的是被驱逐的键，深灰色是被保留的 key。可以看出在 maxmemory-samples 为 10 的时候，近似 lru 的表现很接近真实 lru。另外可以看出 redis 3.0 之后近似 lru 算法精确度有了很大提升。

新的 Lfu 策略

Redis 4.0 开始支持 lfu 策略，redis 会追踪 key 的访问频次，低频次的会被驱逐。lfu 也是使用近似算法，采用的是 Morris counter。这种算法能够使用几个位（a few bits）近似记录一个对象被访问的次数，显然也是为了节省内存。考虑到对象的访问次数可能很频繁，正常情况下记录对象访问次数，可以用一个长整形。在 java 中 Long 类型需要占用 8 字节（64 位）之多，如果 redis 使用 Long 类型显然会消耗很多内存，但问题是如何使用 ‘a few bits’ 记录次数呢？要做到只用几位便可存储访问次数，我们需要对次数的统计方式做一个折算，比如 1000 次访问算作 1 次（注：这里只是打个比方，真实的算法并非这样，但是最终达到的效果类似于折算。），这样便可计算出一个访问次数的相对值，相对值越大，访问次数越多。

Redis 中提供了以下两个配置参数调整 morris counter：

# 该值影响 counter 的累加，值越大，counter 累加的越慢
lfu-log-factor 10
# 单位是分钟，这里配置的值为1，表示 1 分钟后，counter 折半，但是如果 counter 的值小于等于 10，则只减少 1。
lfu-decay-time 1

Redis 中 counter 的真实计算方法：

• ① A random number R between 0 and 1 is extracted.
• ② A probability P is calculated as 1/(old_value*lfu_log_factor+1).
• ③ The counter is incremented only if R < P.

Redis 默认的 lfu-log-factor 是 10，下面这张表格给出了 lfu-log-factor 配置为不同值时，在不同访问次数情况下，counter 的累加情况。

factor	100 hits	1000 hits	100K hits	1M hits	10M hits
0	104	255	255	255	255
1	18	49	255	255	255
10	10	18	142	255	255
100	8	11	49	143	255