介绍数据淘汰机制

Redis 可使用的内存空间是有限的，最大可使用内存空间由服务器配置 maxmemory 选项来指定。Redis 使用的内存空间达到指定的 maxmemory 选项的值时，如果还想让 Redis 帮我们存储键值对，那么 Redis 就必须淘汰一些键值对，那么淘汰哪些键值对呢？Redis 有一些 数据淘汰策略 供我们选择，我们可以根据自己的业务场景，选择一个合适的数据淘汰策略。

Redis 的数据淘汰策略

Redis 4.0 之前一共实现了 6 种数据淘汰策略，在 4.0 之后，又增加了 2 种数据淘汰策略。

  • Redis 4.0 之前实现的：noeviction、volatile-random、volatile-ttl、volatile-lru、allkeys-random、allkeys-lru
  • Redis 4.0 之后实现的：volatile-lfu、allkeys-lfu

按照是否会进行数据淘汰，把数据淘汰策略分成两类：

  • 不进行数据淘汰的策略：只有 noeviction 这一种，这也是 Redis 的默认淘汰策略。
  • 会进行数据淘汰的其他 7 种策略。

我们可以再进一步根据淘汰候选数据集的范围把 会进行数据淘汰的 7 种策略 分成两类：

  • 淘汰候选数据集是：设置了过期时间的数据（在设置了过期时间的数据中进行淘汰）。包括 volatile-random、volatile-ttl、volatile-lru、volatile-lfu 四种。
  • 淘汰候选数据集是：所有的数据（在所有数据中进行淘汰）。包括 allkeys-lru、allkeys-random、allkeys-lfu 三种。

总结来说，这些数据淘汰策略是 淘汰候选数据集的范围 + 键值对选择算法 的搭配组合，其中范围有 allkeys 和 volatile 两种，算法有 LRU、TTL 和 LFU 三种，另外再加上一个 random。

不进行数据淘汰的策略

Redis 的默认数据淘汰策略是：noeviction。
noeviction 的数据淘汰策略是不进行数据淘汰。也就是说 Redis 使用的内存空间达到指定的 maxmemory 选项的值后，如果再有写请求，那么 Redis 将不再提供写服务，而是直接返回错误。

带 volatile 的数据淘汰策略

名字中带 volatile 的数据淘汰策略有：volatile-random、volatile-ttl、volatile-lru 和 volatile-lfu 这 4 种数据淘汰策略。
这 4 种数据淘汰策略的共同点是：它们的淘汰候选数据集都是设置了过期时间的数据。也就是说 Redis 使用的内存空间达到指定的 maxmemory 选项的值后，如果再有写请求，Redis 会在设置了过期时间的键值对中进行淘汰，而不淘汰那些没有设置过期时间的键值对。

我们下面看一下这 4 种数据淘汰策略的具体规则是怎样的：

  • volatile-ttl 是在设置了过期时间的键值对中，优先删除即将过期的键值对（根据 TTL 的值）
  • volatile-random 是在设置了过期时间的键值对中，随机挑选键值对 进行删除。
  • volatile-lru 是在设置了过期时间的键值对中，使用 LRU 算法，优先选择最近最少使用的键值对 进行删除。
  • volatile-lfu 是在设置了过期时间的键值对中，使用 LFU 算法，优先选择最不经常使用的键值对 进行删除。

    LFU 算法是在 LRU 算法的基础上，同时考虑了键值对的访问时效性和键值对被访问的次数。

带 allkeys 的数据淘汰策略

名字中带 allkeys 的数据淘汰策略有：allkeys-random、allkeys-lru、allkeys-lfu 这 3 种数据淘汰策略。
这 3 种数据淘汰策略的共同点是：它们的淘汰候选数据集是所有的键值对，包括设置了过期时间的键值对和没有设置过期时间的键值对。
我们下面看一下这 3 种数据淘汰策略的具体规则是怎样的：

  • allkeys-random 是在所有键值对中，随机挑选键值对 进行删除。
  • allkeys-lru 是在所有键值对中，使用 LRU 算法，优先选择最近最少使用的键值对 进行删除。
  • allkeys-lfu 是在所有键值对中，使用 LFU 算法，优先选择最不经常使用的键值对 进行删除。

这也就是说，如果一个键值对被数据淘汰策略选中了，即使键值对的过期时间还没到，也需要被删除。

LRU 数据淘汰策略

Redis 不是使用链表来实现 LRU 数据淘汰策略的。如果用链表来管理所有的键值对，那么会带来额外的空间开销。而且，每次数据访问时都需要移动链表项，如果有大量数据被访问，就会有很多链表移动操作，会很耗时，进而会降低 Redis 的性能。
所以，在 Redis 中，LRU 算法被做了简化，以减轻数据淘汰对系统性能的影响。
具体来说，Redis 会记录每个数据的最后一次被访问的时间戳（由键值对数据结构 redisObject 中的 lru 字段记录）。在决定淘汰数据时：

  • 第一次会随机选出 N 个数据，把它们作为一个候选集合。接下来，Redis 会比较这 N 个数据的 lru 字段，把 lru 字段值最小的数据从缓存中淘汰出去。
  • 当需要再次淘汰数据时，Redis 需要挑选数据进入第一次淘汰时创建的候选数据集。挑选标准是：能进入候选集合的数据的 lru 字段值必须小于候选集合中最小的 lru 值。当有新数据进入候选数据集后，如果候选数据集中的数据个数达到了 maxmemory-samples，Redis 就把候选数据集中 lru 字段值最小的数据淘汰出去。

这样一来，Redis 缓存不用为所有的键值对维护一个大链表，也不用在每次数据访问时都移动链表项，提升了缓存的性能。

Redis 提供了一个配置参数 maxmemory-samples，这个参数就是 Redis 选出的数据个数 N。

LFU 数据淘汰策略

LFU 数据淘汰策略

LFU 数据淘汰策略是在 LRU 数据淘汰策略上做的优化。
LRU 数据淘汰策略只是从一个维度来筛选并淘汰数据的（数据最后一次被访问的时间），而 LFU 数据淘汰策略会从两个维度来筛选并淘汰数据：

  • 一是，数据最后一次被访问的时间（访问的时效性，最后一次访问的时间离当前时间的远近）；
  • 二是，数据被访问的次数。

使用 LRU 数据淘汰策略时，Redis 会在键值对数据结构 redisObject 中的 lru 字段记录每个数据的最后一次被访问的时间戳，而使用 LFU 数据淘汰策略时，Redus 会将 24bit 大小的 lru 字段拆分成两部分：

  • lru 字段的前 16bit 是 ldt 值，表示数据最后一次被访问的时间戳；
  • lru 字段的后 8bit 是 counter 值，表示数据被访问的次数。

使用 LFU 数据淘汰策略，在决定淘汰的数据时，第一次会随机选出 N 个数据，把它们作为一个候选集合。接下来，首先 Redis 会比较这 N 个数据的 lru 字段的后 8bit，选择被访问次数最少的数据进行淘汰。如果两个数据的被访问次数相同，再比较这两个数据的 lru 字段的前 16bit，把被访问时间距离当前更久的数据淘汰出缓存。

counter 计数规则优化

Redis 只使用了 8bit 记录数据被访问的次数，而 8bit 记录的最大值是 255。如果数据每被访问一次，counter 的值就加 1 的话，那数据的可表示的范围显然是不够的。如果是这样的话，只要数据被访问的次数超过了 255，数据的 counter 值就一样了。在进行数据淘汰时，LFU 数据淘汰策略就无法很好地区分并筛选这些数据，反而还可能会把不怎么访问的数据留在缓存。

在实现 LFU 数据淘汰策略时，Redis 并没有采用数据每被访问一次，就给对应的 counter 值加 1 的计数规则，而是采用了一个更优化的非线性递增的计数规则。
简单来说，LFU 数据淘汰策略实现的计数规则是：每当数据被访问一次时：

  • 首先，用 counter 的值 乘以 配置项 lfu_log_factor 再加 1，再取其倒数，得到一个 p 值；
  • 然后，把这个 p 值和一个取值范围在（0，1）的随机数 r 值比较大小，只有 p 值大于 r 值时，counter 才加 1。

下面这段 Redis 的部分源码，显示了 LFU 数据淘汰策略增加 counter 值的计算逻辑。

  1. double r = (double)rand()/RAND_MAX;
  2. ...
  3. // baseval 是 counter 当前的值
  4. double p = 1.0/(baseval*server.lfu_log_factor+1);
  5. if (r < p) {
  6.     counter++;
  7. }

counter 的初始值默认是 5（由代码中的 LFU_INIT_VAL 常量设置），而不是 0，这样可以避免数据刚被写入缓存就因为被访问次数太少而被立即淘汰。

使用了这种计算规则后，我们就可以通过设置不同的 lfu_log_factor 配置项，来控制 counter 的值增加的速度，避免 counter 的值很快就到达 255。
正是因为使用了非线性递增的计数器方法，即使数据被访问的次数成千上万，LFU 数据淘汰策略也可以有效地区分不同的访问次数，从而进行合理的数据筛选。

counter 值的衰减机制

在一些场景下，有些数据在短时间内被大量访问后就不会再被访问了。那么再按照数据被访问的次数来筛选的话，这些数据就会被留存在缓存中，但不会提升缓存命中率。为此，Redis 在实现 LFU 数据淘汰策略时，还设计了一个 counter 值的衰减机制。
简单来说，LFU 数据淘汰策略使用衰减因子配置项 lfu_decay_time 来控制被访问次数的衰减。LFU 数据淘汰策略会计算当前时间和数据最后一次被访问时间的差值，并把这个差值换算成以分钟为单位，然后，LFU 数据淘汰策略再把这个差值除以 lfu_decay_time 值，所得的结果就是 counter 要衰减的值。
举个例子，假设 lfu_decay_time 取值为 1，如果数据在 N 分钟内没有被访问，那么它的被访问次数就要减 N。如果 lfu_decay_time 取值更大，那么相应的衰减值会变小，衰减效果也会减弱。所以，如果业务应用中有短时高频被访问的数据的话，建议把 lfu_decay_time 值设置为 1，这样一来，在短时高频被访问的数据不再被访问后，会较快地衰减它们的被访问次数，尽早把它们从缓存中淘汰出去，避免缓存污染。

数据淘汰机制的配置参数

maxmemory-samples：使用 LFU 数据淘汰策略时，Redis 选出的数据个数 N 的值
lfu_log_factor：用以 counter 值的计算，控制 counter 值的增速
lfu_decay_time：衰减因子的值，用以控制被访问次数的衰减
从刚才的表中，我们可以看到，当 lfu_log_factor 取值为 10 时，百、千、十万级别的访问次数对应的 counter 值已经有明显的区分了，所以，我们在应用 LFU 策略时，一般可以将 lfu_log_factor 取值为 10。

不同数据淘汰策略的优劣局限

优先使用 allkeys-lru 策略。这样，可以充分利用 LRU 这一经典缓存算法的优势，把最近最常访问的数据留在缓存中，提升应用的访问性能。如果你的业务数据中有明显的冷热数据区分，我建议你使用 allkeys-lru 策略。
如果业务应用中的数据访问频率相差不大，没有明显的冷热数据区分，建议使用 allkeys-random 策略，随机选择淘汰的数据就行。
如果你的业务中有置顶的需求，比如置顶新闻、置顶视频，那么，可以使用 volatile-lru 策略，同时不给这些置顶数据设置过期时间。这样一来，这些需要置顶的数据一直不会被删除，而其他数据会在过期时根据 LRU 规则进行筛选。
先根据是否有始终会被频繁访问的数据（例如置顶消息），来选择淘汰数据的候选集，也就是决定是针对所有数据进行淘汰，还是针对设置了过期时间的数据进行淘汰。候选数据集范围选定后，建议优先使用 LRU 算法，也就是，allkeys-lru 或 volatile-lru 策略。

参考资料

24 | 替换策略：缓存满了怎么办？
27 | 缓存被污染了，该怎么办？