Redis 过期删除和内存淘汰

发表于 2025-05-12 分类于中间件， Redis 本文字数： 1.5k

Redis 内存淘汰策略（史上最全）_redis内存淘汰策略-CSDN博客

过期删除

每当我们对一个 key 设置了过期时间时，Redis 会把该 key 带上过期时间存储到一个过期字典（expires dict）中。当我们查询一个 key 时，Redis 首先检查该 key 是否存在于过期字典中：

如果不在，则正常读取键值；
如果存在，则会获取该 key 的过期时间与当前系统时间比对

Redis 使用的过期删除策略是「惰性删除+定期删除」这两种策略配和使用：

惰性删除：在访问某个 key 时，再去判断是否过期，如果过期则删除。
定期删除：每隔一段时间随机检查过期字典中的一些 key 并删除其中过期的 key。如果这些随机抽取的 key 中的比例超过了上限，则继续抽查和删除，直到抽到的过期 key 比例低于上限或者超过了规定的过期删除时间。

持久化中的过期删除

RDB：

在创建 RDB 时就已经过期数的据不会存储在 RDB 中；
主节点加载 RDB 会删除过期数据，从节点不会，但是后续同步时节点数据会被清空（全量复制），所以也没有影响。

AOF：

会保留没被删除的过期键，在删除后再追加 DEL 命令
AOF 重写时，已过期的键不会被保存到重写后的 AOF 文件中

主从复制时的过期删除

主从复制时从节点不进行过期扫描，只能将其当做正常键值返回。直接主节点删除时才会添加进去。

内存淘汰策略

淘汰策略

内存淘汰策略仅在内存使用量超过最大内存 (maxmemory) 限制时触发。Redis 计算当前内存使用量与最大内存限制之间的差值，逐步淘汰，直到满足内存限制。Redis 会在 写操作 发生时触发淘汰。

no-envicition：默认配置，不淘汰，内存满了后增加数据的写请求直接返回错误；
allkeys-random：从所有键中随机选择一个键进行删除；
allkeys-lru：使用LRU（Least Recently Used，最近最少使用）算法，从redis中选取使用最少的key进行淘汰；
allkeys-lfu：使用LFU（Least Frequently Used，最不经常使用），从所有的键中选择某段时间之内使用频次最少的键值对清除；
volatile-random：设置了过期时间的键中随机淘汰；
volatile-ttl：设置了过期时间的键中基于 TTL 淘汰，优先选择即将过期的键进行删除；
volatile-lru：使用LRU（Least Recently Used，最近最少使用）算法，从redis中设置过过期时间的key中选取淘汰；
volatile-lfu：使用LFU（Least Frequently Used，最不经常使用），从设置了过期时间的键中选择淘汰；

LRU的实现

Redis 采用 “近似 LRU”（Approximate LRU）算法，采用 24 位时间戳（LRU_CLOCK）记录键的最后访问时间，在需要淘汰时从所有键中随机选择一批作为候选集，在这些键中选择最近最少使用的键进行淘汰。采样数量可控制，越大的采样数量越接近 LRU 精确时的效果，一般随着缓存规模的增加而增加：

1	config set maxmemory-samples 16

为什么不用精确的 LRU：

精确 LRU 通常需要使用双向链表（Doubly Linked List），每次键被访问或更新时，需要将其从链表中移到队尾，保持链表按访问顺序排序，每次访问都需要修改链表结构，双向链表还会占用额外的内存（指针开销）。

无法解决缓存污染问题，应用一次读取了大量的数据，而这些数据只会被读取这一次，那么这些数据会留存在 Redis 缓存中很长一段时间，造成缓存污染。

LFU 的实现

在 LFU 中 Redis 对象头的 24 bits 的 lru 字段被分成两段来存储：

高 16bit 存储 ldt(Last Decrement Time)，用来记录 key 的访问时间戳；

低 8bit 存储 logc(Logistic Counter)，用来记录 key 的访问频次，logc 会随时间推移而衰减的。

在每次 key 被访问时，会先对 logc 做一个衰减操作，衰减的值跟前后访问时间间隔有关，间隔越长衰减的值就越大。

redis/src/evict.c at unstable · redis/redis

/* If the object's ldt (last access time) is reached, decrement the LFU counter but
 * do not update LFU fields of the object, we update the access time
 * and counter in an explicit way when the object is really accessed.
 * And we will decrement the counter according to the times of
 * elapsed time than server.lfu_decay_time.
 * Return the object frequency counter.
 *
 * This function is used in order to scan the dataset for the best object
 * to fit: as we check for the candidate, we incrementally decrement the
 * counter of the scanned objects if needed. */
unsigned long LFUDecrAndReturn(robj *o) {
    unsigned long ldt = o->lru >> 8; // 取高 12 位的时间戳
    unsigned long counter = o->lru & 255; // 取低八位的count
    // 计算时间差的衰减周期数，就是 （时间差/周期长度）
    unsigned long num_periods = server.lfu_decay_time ? LFUTimeElapsed(ldt) / server.lfu_decay_time : 0;
    if (num_periods)
        // counter 会衰减和周期数一样的次数
        counter = (num_periods > counter) ? 0 : counter - num_periods;
    return counter;
}

unsigned long LFUTimeElapsed(unsigned long ldt) {
    unsigned long now = LFUGetTimeInMinutes();
    if (now >= ldt) return now-ldt;
    return 65535-ldt+now; // 发生了时间溢出，超过了 12 位的时间戳的上限
}

衰减之后进行增加操作，根据概率增加，如果 logc 越大的 key，它的 logc 就越难再增加。

/* Logarithmically increment a counter. The greater is the current counter value
 * the less likely is that it gets really incremented. Saturate it at 255. */
uint8_t LFULogIncr(uint8_t counter) {
    if (counter == 255) return 255;
    double r = (double)rand()/RAND_MAX;
    double baseval = counter - LFU_INIT_VAL;
    if (baseval < 0) baseval = 0;
    // counter 越大 baseval 越大，进而分母越大该数越小，最终的概率越小
    double p = 1.0/(baseval*server.lfu_log_factor+1); 
    if (r < p) counter++;
    return counter;
}