Redis++：Redis 内存爆满 之 淘汰策略
前言：
我们的redis使用的是内存空间来存储数据的，但是内存空间毕竟有限，随着我们存储数据的不断增长，当超过了我们的内存大小时，即在redis中设置的缓存大小（maxmeory 4GB），redis会怎么处理呢？
Redis内存淘汰策略，是被很多小伙伴忽略的知识盲区，注意，是盲区。
注意，Redis如果内存淘汰策略配置不合理，可能会导致Redis无法服务。
今天就来聊聊redis的缓存淘汰策略：↓ ↓ ↓
首先，介绍一下Redis过期删除策略，然后，再介绍Redis淘汰策略.
1）：Redis过期删除策略
Redis对于过期的key，有三种删除策略：
- 定期删除（主动删除：由于惰性删除策略无法保证冷数据被及时删掉，所以Redis会定期主动淘汰一批已过期的key）
- 惰性删除（被动删除：当读/写一个已经过期的key时，会触发惰性删除策略，直接删除掉这个过期key）
- 当前已用内存超过maxmemory限定时，触发主动清理策略
定期删除：
redis 会将每个设置了过期时间的 key 放入到一个独立的字典中，以后会定期遍历这个字典来删除到期的 key。
Redis 默认会每秒进行十次过期扫描（100ms一次），过期扫描不会遍历过期字典中所有的 key，而是采用了一种简单的贪心策略。
1、从过期字典中随机 20 个 key；
2、删除这 20 个 key 中已经过期的 key；
3、如果过期的 key 比率超过 1/4，那就重复步骤 1；
redis默认是每隔 100ms就随机抽取一些设置了过期时间的key，检查其是否过期，如果过期就删除。
注意这里是随机抽取的。为什么要随机呢？
你想一想假如 redis 存了几十万个 key ，每隔100ms就遍历所有的设置过期时间的 key 的话，就会给 CPU 带来很大的负载。
惰性删除：
所谓惰性策略就是在客户端访问这个key的时候，redis对key的过期时间进行检查，如果过期了就立即删除，不会给你返回任何东西。
为啥需要两种删除策略呢？
定期删除可能会导致很多过期key到了时间并没有被删除掉。
所以就有了惰性删除。假如你的过期 key，靠定期删除没有被删除掉，还停留在内存里，除非你的系统去查一下那个 key，才会被redis给删除掉。
这就是所谓的惰性删除，即当你主动去查过期的key时,如果发现key过期了,就立即进行删除,不返回任何东西.
总结：定期删除是集中处理，惰性删除是零散处理
2）：Redis 内存爆满 淘汰置换策略
当 Redis 内存使用达到 maxmemory 时，需要选择设置好的 maxmemory-policy 进行对老数据的置换。
下面是可以选择的置换策略：
不同于之前的版本，redis5.0为我们提供了八个不同的内存置换策略；很早之前提供了6种。
- volatile-lru：从已设置过期时间的数据集中挑选最近最少使用的数据淘汰。
- volatile-ttl：从已设置过期时间的数据集中挑选将要过期的数据淘汰。
- volatile-random：从已设置过期时间的数据集中任意选择数据淘汰。
- volatile-lfu：从已设置过期时间的数据集挑选使用频率最低的数据淘汰。
- allkeys-lru：从数据集中挑选最近最少使用的数据淘汰
- allkeys-lfu：从数据集中挑选使用频率最低的数据淘汰。
- allkeys-random：从数据集（server.db[i].dict）中任意选择数据淘汰
- no-enviction（驱逐）：禁止驱逐数据，这也是默认策略。
意思是当内存不足以容纳新入数据时，新写入操作就会报错，请求可以继续进行，线上任务也不能持续进行，采用no-enviction策略可以保证数据不被丢失。
这八种大体上可以分为4中：
- lru（Least Recently Used，最近最少使用）
- lfu（Least Frequently Used，最不经常使用）、
- random（随机）
- ttl
设置 maxmemory-policy 的方法 和 设置 maxmemory 方法类似，通过 redis.conf 或是通过 CONFIG SET 动态修改。
选择合适的置换策略是很重要的，这主要取决于你的应用的访问模式，当然你也可以动态的修改置换策略；
并通过用 Redis 命令——INFO 去输出 cache 的命中率情况，进而可以对置换策略进行调优。
置换策略是如何工作的？
- 客户端执行一条新命令，导致数据库需要增加数据（比如set key value）
- Redis会检查内存使用，如果内存使用超过 maxmemory，就会按照置换策略删除一些 key
- 新的命令执行成功
我们持续的写数据会导致内存达到或超出上限 maxmemory，但是置换策略会将内存使用降低到上限以下。
如果一次需要使用很多的内存（比如一次写入一个很大的set），那么，Redis 的内存使用可能超出最大内存限制一段时间。
LRU 算法机制：
LRU算法的全称叫做Least Recently Used,也就是最近最少使用原则来进行数据的淘汰算法。
其原理就是，会将数据放入到一个链表中，当链表中的某个元素被访问时，这个元素就被会提到链表的前面，其他元素，默认向后移动；
当这个时候我们想缓存中新增一个元素时，也会被增加到链表的头部，那么尾部的最后一个元素就被淘汰了。
lru的实现思想就是：就是刚被访问的数据，在接下来的时间里，更容易被再次访问，而一段时间没有被访问的数据，之后也不会再次访问。
但是要将redis的全部数据都放入这样一个链表中的话，redis的数据被频繁访问时，需要不停的移动链表的位置，降低redis的性能。
所以redis对LRU算法进行了优化 ↓
在redis中，会给每个数据记录一个最近访问的时间戳（记录在RedisObject的lru字段中），
当需要进行数据淘汰时，redis就随机筛选出N个数据放入到候选集合中去，然后比较这N个数据中的lru的值，最小的就会被淘汰。
当再次需要淘汰数据时，这个时候筛选数据放入到第一次创建的淘汰集合中，那么这次筛选就不在是随机筛选，而是能进入候选集合的数据的 lru 字段值必须小于候选集合中最小的 lru 值，
然后再次将最小的lru的值的数据进行淘汰。
其中N的配置项为：
maxmemory-samples 100 # 表示N为100
LFU 算法机制：
LFU（Least frequently used）称为最近使用最少的数据将被淘汰，redis在就是在LRU的基础上增加一个次数统计。
其步骤就是根据数据的访问次数进行筛选，淘汰访问次数少的数据，如果访问次数相同，在根据访问时间进行比较，淘汰访问时间久远的数据。
redis中的实现方式：就是在RedisObject的字段lru上，拆分为两个部分：
- ldt值：lru字段的前16bit位，还是用来表示时间戳。
- counter值：lru字段的后8bit位，用来表示数据的访问次数。
当 LFU 策略筛选数据时，Redis 会在候选集合中，根据数据 lru 字段的后 8bit 选择访问次数最少的数据进行淘汰。
当访问次数相同时，再根据 lru 字段的前 16bit 值大小，选择访问时间最久远的数据进行淘汰。
但是8个bit位，最大只能记录255的值，但是redis中的数据，有时候会被访问成千上万次，那么这个问题如何进行解决呢？
redis对计数进行了优化，并不是数据被访问一次，counter就会被加1，而是遵循如下规则：↓
当数据被访问一次时，首先用计数器当前的值乘以配置项lfu_log_factor再加1，再取倒数得到一个p值然后把这个p值和一个取值范围在（0,1）的一个随机数r，进行比大小，只有p值大于r时，counter的值才会被加一
lfu-log-factor可以调整计数器counter的增长速度，lfu-log-factor越大，counter增长的越慢。
lfu-decay-time是一个以分钟为单位的数值，可以调整counter的减少速度
#redis部分源码展示
double r = (double)rand()/RAND_MAX;
double p = 1.0/(baseval*server.lfu_log_factor+1);
if (r < p) counter++;
其中 baseval是计数器的当前值。计数器的默认初始值为5（由代码中的 LFU_INIT_VAL 常量设置），并不是为0，这样可以避免数据刚进入缓存，就因为访问次数少而被立即淘汰。
当lfu_log_factor取不同的值时，实际访问次数下，counter的值的变化情况：
在实际的使用场景中，还会有这样一种情况，某些数据可能一开始会被大量的访问，但是过了时间段后，就不会再被访问。
如果这个时候counter的值很大，就算后续不会被访问，也就不会被redis进行数据淘汰。
针对这种情况，在redis中，设计了counter的衰减策略。其实现就是根据lfu_decay_time的配置值，来控制访问次数的衰减。
其流程如下：
- lfu会计算当前时间和数据最近一次访问的时间差值，并将这个差值换算为分钟单位。
- 然后在将这个差值除以lfu_decay_time值，得到的就是我们需要减去的值
- 然后再讲counter的值减去这个值
这样就可以保证在一段时间后，可以淘汰这部分数据。
Redis 的淘汰策略怎么选：
一般来说，有这样一些常用的经验：
- 在所有的 key 都是最近最经常使用，那么就需要选择 allkeys-lru 进行置换最近最不经常使用的 key，如果你不确定使用哪种策略，那么推荐使用 allkeys-lru
- 如果所有的 key 的访问概率都是差不多的，那么可以选用 allkeys-random 策略去置换数据
- 如果对数据有足够的了解，能够为 key 指定 hint（通过expire/ttl指定），那么可以选择 volatile-ttl 进行置换
volatile-lru 和 volatile-random 经常在一个Redis实例既做cache又做持久化的情况下用到，然而，更好的选择使用两个Redis实例来解决这个问题。
设置是失效时间 expire 会占用一些内存，而采用 allkeys-lru 就没有必要设置失效时间，进而更有效的利用内存。