结合源码分析Redis的内存回收和内存淘汰机制，LRU和LFU是如何进行计算的？

Redis 内存回收

1. 过期 key 处理

Redis 之所以性能强，最主要的原因就是基于内存存储。然而单节点的 Redis 其内存大小不宜过大，会影响持久化或主从同步性能。我们可以通过修改配置文件来设置Redis的最大内存：

当内存使用达到上限时，就无法存储更多数据了。为了解决这个问题，Redis 提供了一些策略实现内存回收，在学习 Redis 缓存的时候我们说过，可以通过 expire 命令给 Redis 的 key 设置 TTL（存活时间），key 的 TTL 到期以后，再次访问 name 返回的是 nil，说明这个 key 已经不存在了，对应的内存也得到释放。从而起到内存回收的目的

Redis 本身是一个典型的 key-value 内存存储数据库，因此所有的 key、value 都保存在之前学习过的 Dict 结构中。不过在其 database 结构体中，有两个 Dict：一个用来记录 key-value；另一个用来记录 key-TTL

Redis 的 DB 结构

Redis是如何知道一个key是否过期呢？

利用两个 Dict 分别记录 key-value 对及 key-ttl

是不是 TTL 到期就立即删除了呢？

1. 惰性删除：顾明思议并不是在 TTL 到期后就立刻删除，而是在访问一个 key 的时候，检查该 key 的存活时间，如果已经过期才执行删除

• • 

1. 周期删除：顾明思议是通过一个定时任务，周期性的抽样部分过期的 key，然后执行删除，执行周期有两种

• • 初始化时设置定时任务serverCron()，按照 server.hz 的频率来执行过期 key 清理，模式为 SLOW
  • Redis 每个事件循环前都会调用beforeSlepp()函数，执行过期 Key 清理，模式为 Fast

  • 

SLOW 模式规则：

• 执行频率受 server.hz 影响，默认为 10，即每秒执行 10 次，每个执行周期 100ms
• 执行清理耗时不超过一次执行周期的 25%，默认 slow 模式耗时不超过 25ms
• 逐个遍历 db，逐个遍历 db 中的 bucket（hash 表的角标），抽取 20 个 key 判断是否过期
• 如果没达到时间上限（25ms）并且过期 key 比例大于 10%，再进行一次抽样，否则结束

FAST 模式规则（过期 key 比例小于 10% 不执行 ）：

• 执行频率受beforeSleep()调用频率影响，但两次 FAST 模式间隔不低于 2ms
• 执行清理耗时不超过 1ms
• 只会采样存在明显过期积压的 DB/Bucket，抽取 20 个 key 判断是否过期如果没达到时间上限（1ms）并且过期 key 比例大于 10%，再进行一次抽样，否则结束

Redis 的 SLOW 和 FAST 两种定期过期删除本质上都是由主线程串行执行的，不会并发执行。即使是不同扫描模式，也只是调度频率不同，删除操作永远是串行的，因此不会出现多个线程同时对同一个 bucket 释放内存，也就自然防止了冲突和数据错误

模式	触发时机	调度点	典型频率	目标
SLOW	serverCron100ms/次	主线程定时	10Hz	全局定期均匀采样
FAST	beforeSleep/压力感知	主线程调度插入	ms 级别	过期压力下快速补刀

RedisKey 的 TTL 记录方式：

• 在 RedisDB 中通过一个 Dict 记录每个 Key 的 TTL 时间

过期 key 的删除策略：

• 惰性清理：每次查找 key 时判断是否过期，如果过期则删除
• 定期清理：定期抽样部分 key，判断是否过期，如果过期则删除

定期清理的两种模式：

• SLOW 模式执行频率默认为 10，每次不超过 25ms
• FAST 模式执行频率不固定，但两次间隔不低于 2ms，每次耗时不超过 1ms

2. 内存淘汰策略

内存淘汰：就是当 Redis 内存使用达到设置的上限时，主动挑选部分 key 删除以释放更多内存的流程，Redis 会在处理客户端命令的方法 processCommand() 中尝试做内存淘汰：

淘汰策略

Redis支持 8 种不同策略来选择要删除的 key

1. noeviction： 不淘汰任何 key，但是内存满时不允许写入新数据，默认就是这种策略
2. volatile-ttl： 对设置了 TTL 的 key，比较 key 的剩余 TTL 值，TTL 越小越先被淘汰
3. allkeys-random：对全体 key ，随机进行淘汰，也就是直接从db->dict中随机挑选
4. volatile-random：对设置了 TTL 的 key ，随机进行淘汰，也就是从db->expires中随机挑选
5. allkeys-lru： 对全体 key，基于LRU算法进行淘汰
6. volatile-lru： 对设置了 TTL 的 key，基于LRU算法进行淘汰
7. allkeys-lfu： 对全体 key，基于LFU算法进行淘汰
8. volatile-lfu： 对设置了 TTL 的 key，基于LFU算法进行淘汰比较容易混淆的有两个：

• • LRU（Least Recently Used），最少最近使用（最近使用的时间越小越容易被淘汰）。用当前时间减去最后一次访问时间，这个值越大则淘汰优先级越高。
  • LFU（Least Frequently Used），最少频率使用。会统计每个 key 的访问频率，值越小淘汰优先级越高

Redis的数据都会被封装为 RedisObject 结构：

LFU的访问次数之所以叫做逻辑访问次数，是因为并不是每次 key 被访问都计数，而是通过运算：

• 生成 0~1 之间的随机数 R
• 计算 (旧次数 * lfu_log_factor + 1)，记录为 P,lfu-log-factor默认为 10
• 如果 R < P ，则计数器 + 1，且最大不超过 255
• 访问次数会随时间衰减，距离上一次访问时间每隔lfu_decay_time分钟（默认 1），计数器减 1

LFU的逻辑访问次数中，如果一个 key 访问的频率越高，那么他的逻辑访问次数递增的概率将会越低，最多递增到 255；其次LFU的逻辑访问次数，会在距离上一次访问间隔lfu_decay_time分组，进行递减

内存淘汰策略：从源码角度分析内存的淘汰策略流程，首先插入 key 时，发现内存已满，Redis 首先判断是否设置了noeviction策略；如果没有设置，那么将判断淘汰策略中是否从Allkeys中进行淘汰，当策略为Allkeys时将从dict中进行选取，反之从expires中选取。然后进一步判断采用内存策略是Random还是LRU/LFU/TTL？如果是RANDOM那么遍历 DB 之后进行随机淘汰；如果是LRU/LFU/TTL，首先 key 的淘汰将会在eviction_pool中完成。在选取 DB 之后，还是会先随机选取maxmemory-sample个 key，然后才会根据不同的策略去进行判断。eviction-pool中是根据一个值进行升序排序之后，将最大的值进行淘汰。LRU/LFU/TTL这三种淘汰策略，我们不可能给每一种都设置一个排序机制，所以 Redis 巧妙的采用了idleTime进行统一标准的判断。对于TTL而言，idleTime等于maxTTL-TTL减去 TTL 剩余有效期，maxTTL-TTL就是 long 的最大值，如果 key 的有效期越短那么idleTime的值也会越大，也就符合idleTime升序排序并淘汰最大的 key；对于LRU而言，idleTime等于当前时间戳减去 key 的时间戳，key 的最少最近访问时间戳越小，代表 key 很久没有被查询，idleTime的值也会越大；最后LFU的idleTime计算是 255-LFU 的计数，如果计数越小，说明这个值就越大

Redis 的内存淘汰机制基于一定的概率进行选择，虽然在一开始的时候，可能会出现不合理的清除，但是随着时间的增加，这个淘汰机制的正确率还是很乐观的