Redis-原理-内存淘汰策略.md

转自：https://zhuanlan.zhihu.com/p/105587132

过期策略

定期删除

redis 会将每个设置了过期时间的 key 放入到一个独立的字典中，以后会定期遍历这个字典来删除到期的 key。

Redis 默认会每秒进行十次过期扫描（100ms 一次），过期扫描不会遍历过期字典中所有的 key，而是采用了一种简单的贪心策略。

从过期字典中随机 20 个 key；
删除这 20 个 key 中已经过期的 key；
如果过期的 key 比率超过 1/4，那就重复步骤 1；

redis 默认是每隔 100ms 就随机抽取一些设置了过期时间的 key，检查其是否过期，如果过期就删除。注意这里是随机抽取的。为什么要随机呢？你想一想假如 redis 存了几十万个 key ，每隔 100ms 就遍历所有的设置过期时间的 key 的话，就会给 CPU 带来很大的负载。

惰性删除

所谓惰性策略就是在客户端访问这个 key 的时候，redis 对 key 的过期时间进行检查，如果过期了就立即删除，不会给你返回任何东西。

定期删除可能会导致很多过期 key 到了时间并没有被删除掉。所以就有了惰性删除。假如你的过期 key，靠定期删除没有被删除掉，还停留在内存里，除非你的系统去查一下那个 key，才会被 redis 给删除掉。这就是所谓的惰性删除，即当你主动去查过期的 key 时，如果发现 key 过期了，就立即进行删除，不返回任何东西。

总结：定期删除是集中处理，惰性删除是零散处理。

为什么需要淘汰策略

有了以上过期策略的说明后，就很容易理解为什么需要淘汰策略了，因为不管是定期采样删除还是惰性删除都不是一种完全精准的删除，就还是会存在 key 没有被删除掉的场景，所以就需要内存淘汰策略进行补充。

内存淘汰策略

noeviction：当内存使用超过配置的时候会返回错误，不会驱逐任何键
allkeys-lru：加入键的时候，如果过限，首先通过 LRU 算法驱逐最久没有使用的键
volatile-lru：加入键的时候如果过限，首先从设置了过期时间的键集合中驱逐最久没有使用的键
allkeys-random：加入键的时候如果过限，从所有 key 随机删除
volatile-random：加入键的时候如果过限，从过期键的集合中随机驱逐
volatile-ttl：从配置了过期时间的键中驱逐马上就要过期的键
volatile-lfu：从所有配置了过期时间的键中驱逐使用频率最少的键
allkeys-lfu：从所有键中驱逐使用频率最少的键

LRU

标准 LRU 实现方式

新增 key value 的时候首先在链表结尾添加 Node 节点，如果超过 LRU 设置的阈值就淘汰队头的节点并删除掉 HashMap 中对应的节点。
修改 key 对应的值的时候先修改对应的 Node 中的值，然后把 Node 节点移动队尾。
访问 key 对应的值的时候把访问的 Node 节点移动到队尾即可。

Redis 的 LRU 实现

Redis 维护了一个 24 位时钟，可以简单理解为当前系统的时间戳，每隔一定时间会更新这个时钟。每个 key 对象内部同样维护了一个 24 位的时钟，当新增 key 对象的时候会把系统的时钟赋值到这个内部对象时钟。比如我现在要进行 LRU，那么首先拿到当前的全局时钟，然后再找到内部时钟与全局时钟距离时间最久的（差最大）进行淘汰，这里值得注意的是全局时钟只有 24 位，按秒为单位来表示才能存储 194 天，所以可能会出现 key 的时钟大于全局时钟的情况，如果这种情况出现那么就两个相加而不是相减来求最久的 key。

struct redisServer {
       pid_t pid; 
       char *configfile; 
       //全局时钟
       unsigned lruclock:LRU_BITS; 
       ...
};
typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    /* key对象内部时钟 */
    unsigned lru:LRU_BITS;
    int refcount;
    void *ptr;
} robj;

Redis 中的 LRU 与常规的 LRU 实现并不相同，常规 LRU 会准确的淘汰掉队头的元素，但是 Redis 的 LRU 并不维护队列，只是根据配置的策略要么从所有的 key 中随机选择 N 个（N 可以配置）要么从所有的设置了过期时间的 key 中选出 N 个键，然后再从这 N 个键中选出最久没有使用的一个 key 进行淘汰。

下图是常规 LRU 淘汰策略与 Redis 随机样本取一键淘汰策略的对比，浅灰色表示已经删除的键，深灰色表示没有被删除的键，绿色表示新加入的键，越往上表示键加入的时间越久。从图中可以看出，在 redis 3 中，设置样本数为 10 的时候能够很准确的淘汰掉最久没有使用的键，与常规 LRU 基本持平。

为什么要使用近似 LRU？

性能问题，由于近似 LRU 算法只是最多随机采样 N 个 key 并对其进行排序，如果精准需要对所有 key 进行排序，这样近似 LRU 性能更高
内存占用问题，redis 对内存要求很高，会尽量降低内存使用率，如果是抽样排序可以有效降低内存的占用
实际效果基本相等，如果请求符合长尾法则，那么真实 LRU 与 Redis LRU 之间表现基本无差异
在近似情况下提供可自配置的取样率来提升精准度，例如通过 CONFIG SET maxmemory-samples <count> 指令可以设置取样数，取样数越高越精准，如果你的 CPU 和内存有足够，可以提高取样数看命中率来探测最佳的采样比例。

LFU

LFU 是在 Redis4.0 后出现的，LRU 的最近最少使用实际上并不精确，考虑下面的情况，如果在|处删除，那么 A 距离的时间最久，但实际上 A 的使用频率要比 B 频繁，所以合理的淘汰策略应该是淘汰 B。LFU 就是为应对这种情况而生的。

1
2
3

A~~A~~A~~A~~A~~A~~A~~A~~A~~A~~~|

B~~~~~B~~~~~B~~~~~B~~~~~~~~~~~~B|

LFU 把原来的 key 对象的内部时钟的 24 位分成两部分，前 16 位还代表时钟，后 8 位代表一个计数器。16 位的情况下如果还按照秒为单位就会导致不够用，所以一般这里以时钟为单位。而后 8 位表示当前 key 对象的访问频率，8 位只能代表 255，但是 redis 并没有采用线性上升的方式，而是通过一个复杂的公式，通过配置如下两个参数来调整数据的递增速度。

lfu-log-factor 可以调整计数器 counter 的增长速度，lfu-log-factor 越大，counter 增长的越慢。
lfu-decay-time 是一个以分钟为单位的数值，可以调整 counter 的减少速度。

所以这两个因素就对应到了 LFU 的 Counter 减少策略和增长策略，它们实现逻辑分别如下。

降低 LFUDecrAndReturn

先从高 16 位获取最近的降低时间 ldt 以及低 8 位的计数器 counter 值
计算当前时间 now 与 ldt 的差值（now-ldt），当 ldt 大于 now 时，那说明是过了一个周期，按照 65535-ldt+now 计算（16 位一个周期最大 65535）
使用第 2 步计算的差值除以 lfu_decay_time，即 LFUTimeElapsed(ldt) / server.lfu_decay_time，已过去 n 个 lfu_decay_time，则将 counter 减少 n。

增长 LFULogIncr

获取 0-1 的随机数 r

计算 0-1 之间的控制因子 p，它的计算逻辑如下

//LFU_INIT_VAL默认为5
baseval = counter - LFU_INIT_VAL;
//计算控制因子
p = 1.0/(baseval*lfu_log_factor+1);

如果 r 小于 p，counter 增长 1

p 取决于当前 counter 值与 lfu_log_factor 因子，counter 值与 lfu_log_factor 因子越大，p 越小，r 小于 p 的概率也越小，counter 增长的概率也就越小。增长情况如下图：

从左到右表示 key 的命中次数，从上到下表示影响因子，在影响因子为 100 的条件下，经过 10M 次命中才能把后 8 位值加满到 255.

新生 KEY 策略

另外一个问题是，当创建新对象的时候，对象的 counter 如果为 0，很容易就会被淘汰掉，还需要为新生 key 设置一个初始 counter。counter 会被初始化为 LFU_INIT_VAL，默认 5。