Redis 之所以性能强，最主要的原因就是基于内存存储。然而单节点的 Redis 其内存大小不宜过大，会影响持久化或主从同步性能。

当内存使用达到上限时，就无法存储更多数据了。为了解决这个问题，Redis提供了一些策略实现内存回收：

• 内存过期策略
• 内存淘汰策略

内存过期策略

在学习 Redis 缓存的时候我们说过，是可以通过 expire 命令给 Redis 的 key 设置 TTL（存活时间）。根据 TTL 时间来判断过期策略。

在这里我们就有了疑问：

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

源码方法体代码：

typedef struct redisDb {
    dict *dict;                 /* 存放所有key及value的地方，也被称为keyspace*/
    dict *expires;              /* 存放每一个key及其对应的TTL存活时间，只包含设置了TTL的key*/
    dict *blocking_keys;        /* Keys with clients waiting for data (BLPOP)*/
    dict *ready_keys;           /* Blocked keys that received a PUSH */
    dict *watched_keys;         /* WATCHED keys for MULTI/EXEC CAS */
    int id;                     /* Database ID，0~15 */
    long long avg_ttl;          /* 记录平均TTL时长 */
    unsigned long expires_cursor; /* expire检查时在dict中抽样的索引位置. */
    list *defrag_later;         /* 等待碎片整理的key列表. */
} redisDb;
1
2
3
4
5
6
7
8
9
10
11

所以它的内存结构图：

所以在 Redis 中是利用两个 Dict 分别记录 key-value 对及 key-ttl 对‘，对过期数据的一个处理。

而数据时间到期后，就要考虑什么时候去删除，是立即去删除吗？肯定的回答是不是，因为 Redis 是单线程的，到期后立即去删除，会造成写不必要的性能浪费。

所以在 Redis 中的过期策略是分为惰性删除和周期删除的。

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

源码部分：

// 查找一个key执行写操作
robj *lookupKeyWriteWithFlags(redisDb *db, robj *key, int flags) {
    // 检查key是否过期
    expireIfNeeded(db,key);
    return lookupKey(db,key,flags);
}
// 查找一个key执行读操作
robj *lookupKeyReadWithFlags(redisDb *db, robj *key, int flags) {
    robj *val;
    // 检查key是否过期    if (expireIfNeeded(db,key) == 1) {
        // ...略
    }
    return NULL;
}

int expireIfNeeded(redisDb *db, robj *key) {
    // 判断是否过期，如果未过期直接结束并返回0
    if (!keyIsExpired(db,key)) return 0;
    // ... 略
    // 删除过期key
    deleteExpiredKeyAndPropagate(db,key);
    return 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

周期删除：
顾明思议是通过一个定时任务，周期性的抽样部分的key，然后执行删除过期的key，在抽样的时候时会经过轮询将每一个 key 最终都会遍历到的。

而它的执行周期是分为两种的：

Redis 服务初始化函数 initServer() 中设置定时任务，按照 server.hz 的频率来执行过期 key 清理，模式为 SLOW。
Redis 的每个事件循环前会调用 beforeSleep() 函数，执行过期 key 清理，模式为 FAST。

SLOW 模式的规则：

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

SLOW模式执行频率默认为10，每次不超过25ms

FAST 模式的规则：

1. 两次FAST执行频率模式间隔不低于2ms；
2. 执行清理耗时不超过1ms；
3. 逐个遍历 db，抽取20个key判断是否过期；
4. 如果没达到时间上限（1ms）并且过期 key 比例大于10%，再进行一次抽样，否则结束。

FAST模式执行频率不固定，但两次间隔不低于2ms，每次耗时不超过1ms

总结：内存过期：是设置一个key的过期时间，到过期时间的时候，我们就可以向办法将其删除。删除的策略是由两种的，一种是惰性删除，就是在访问的那一刻，检查一下是否过期，若是过期，就删除，若没有过期，就正常访问。另外一种是周期性删除，就是一个定期的任务，没隔一段时间，就尝试去清理一些过期的 key。这就是过期策略。

淘汰策略

• 内存淘汰：就是当 Redis 内存使用达到设置的上限时，主动挑选部分 key 删除以释放更多内存的流程。

在 Redis 中是支持8种不同策略来选择要删除的key：
● noeviction： 不淘汰任何 key，但是内存满时不允许写入新数据，默认就是这种策略；
● volatile-ttl： 对设置了 TTL 的 key，比较 key 的剩余 TTL 值，TTL 越小越先被淘汰；
● allkeys-random：对全体 key ，随机进行淘汰。也就是直接从 db->dict 中随机挑选；
● volatile-random：对设置了 TTL 的key ，随机进行淘汰。也就是从 db->expires 中随机挑选；
● allkeys-lru： 对全体 key，基于 LRU 算法进行淘汰；
● volatile-lru： 对设置了 TTL 的 key，基于 LRU 算法进行淘汰；
● allkeys-lfu： 对全体 key，基于 LFU 算法进行淘汰；
● volatile-lfu： 对设置了 TTL 的 key，基于 LFI 算法进行淘汰；

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

在 Redis 当中的数据都会被封装为 RedisObject 结构。

typedef struct redisObject {
    unsigned type:4;        // 对象类型
    unsigned encoding:4;    // 编码方式
    unsigned lru:LRU_BITS;  // LRU：以秒为单位记录最近一次访问时间，长度24bit
			  // LFU：高16位以分钟为单位记录最近一次访问时间，低8位记录逻辑访问次数
    int refcount;           // 引用计数，计数为0则可以回收
    void *ptr;              // 数据指针，指向真实数据
} robj;
1
2
3
4
5
6
7
8

因为在记录访问次数的时候，它只有 4 个bit位进行存储，最大是255 显然是很不合理的。所以记录 LFU 的访问次数是为逻辑访问次数。
LFU 记录逻辑访问次数，并不是每次 key 被访问都计数，而是通过运算：

1. 生成0~1之间的随机数R
2. 计算 (旧次数 * lfu_log_factor + 1)，记录为P
3. 如果 R < P ，则计数器 + 1，且最大不超过255
4. 访问次数会随时间衰减，距离上一次访问时间每隔 lfu_decay_time 分钟，计数器 -1

淘汰策略的运行逻辑图：

在 eviction_pool 池子当中，虽然最开始是随机存储的key 值，但是在后面的判断是否存入 eviction_pool 当中，每次存取进去的都是计算得到结果的小值，大值将不会给里面存储，这样一直循环下去，也就会降级最初的不稳定性。