过期删除与内存淘汰：8种策略深解

第25章 过期删除与内存淘汰：8种策略深解

Redis 的内存管理涉及两个独立但互补的机制：过期删除（管理有 TTL 的 key 的生命周期）和内存淘汰（maxmemory 达到上限时的驱逐策略）。本章从源码层面深度分析这两个机制的实现原理、算法细节和工程权衡。

25.1 过期删除的三张存储结构

expires 字典

每个 redisDb 包含两个并行字典：

// server.h
typedef struct redisDb {
    dict *dict;       // 主数据字典：key → redisObject
    dict *expires;    // 过期字典：key → 过期时间戳（毫秒，long long）
    dict *blocking_keys;
    dict *watched_keys;
    int id;
    long long avg_ttl;        // 平均 TTL（用于统计）
    unsigned long expires_cursor; // activeExpireCycle 的扫描游标
    list *ready_keys;
} redisDb;

关键设计：

• expires 字典中的 key 是指针，指向 dict 中同一个 SDS 对象（共享，不重复分配）
• expires 字典中的 value 是 long long（毫秒时间戳），不是 redisObject，节省空间
• 设置过期：EXPIRE key seconds → dbAdd(expires, key, timestamp)
• 查询过期：O(1)，直接 dictFind(db->expires, key)

时间戳的存储方式

// expire.c
void expireGenericCommand(client *c, long long basetime, int unit) {
    // 将相对时间转换为绝对时间戳（毫秒）
    long long when = unit == UNIT_SECONDS
                     ? basetime + (long long)c->argv[2]->ptr * 1000
                     : basetime + (long long)c->argv[2]->ptr;

    // 写入 expires 字典
    setExpire(c, c->db, c->argv[1], when);
}

void setExpire(client *c, redisDb *db, robj *key, long long when) {
    dictEntry *kde, *de;

    // 必须先确认 key 存在于主字典
    kde = dictFind(db->dict, key->ptr);
    serverAssertWithInfo(NULL, key, kde != NULL);

    de = dictAddOrFind(db->expires, dictGetKey(kde));
    // value 直接存时间戳，不封装成 robj
    dictSetSignedIntegerVal(de, when);

    // 通知 key space（如果开启了 notify-keyspace-events）
    int writable_slave = server.masterhost && server.repl_slave_lazy_flush;
    if (c && !writable_slave && server.notify_keyspace_events) {
        notifyKeyspaceEvent(NOTIFY_GENERIC, "expire", key, db->id);
    }
}

25.2 惰性删除：expireIfNeeded

每次读或写 key 时，Redis 都会先调用 expireIfNeeded 检查是否过期：

// db.c
int expireIfNeeded(redisDb *db, robj *key, int flags) {
    if (!keyIsExpired(db, key)) return 0;

    // 从库不主动删除（等主库的 DEL 命令），除非设置了 slave-read-only no
    if (server.masterhost != NULL) {
        if (server.current_client &&
            server.current_client->flags & CLIENT_MASTER) return 0;
        // 从库只在自己的读请求中跳过过期 key（返回空），不删除
        if (!(flags & EXPIRE_FORCE_DELETE_EXPIRED)) return 1;
    }

    // 更新统计
    server.stat_expiredkeys++;

    // 传播到从库和 AOF（主库执行删除时）
    propagateExpire(db, key, server.lazyfree_lazy_expire);

    notifyKeyspaceEvent(NOTIFY_GENERIC, "expired", key, db->id);

    int deleted;
    if (server.lazyfree_lazy_expire) {
        // 惰性过期：异步删除（UNLINK 语义）
        deleted = dbAsyncDelete(db, key);
    } else {
        // 同步删除
        deleted = dbSyncDelete(db, key);
    }

    if (deleted) notifyKeyspaceEvent(NOTIFY_GENERIC, "del", key, db->id);
    return deleted;
}

// 判断 key 是否已过期
int keyIsExpired(redisDb *db, robj *key) {
    mstime_t when = getExpire(db, key);
    mstime_t now;

    if (when < 0) return 0;  // key 无过期时间

    // 如果正在加载 RDB/AOF，使用加载时的时间（避免误删历史数据）
    if (server.loading) return 0;

    // 如果正在执行 Lua 脚本，使用脚本开始时的时间（保证脚本内一致性）
    if (server.script_caller)
        now = server.lua_time_start;
    else if (server.fixed_time_expire > 0)
        now = server.mstime;  // 事务中使用固定时间
    else
        now = mstime();

    return now > when;
}

惰性删除的缺点：

• 长期不被访问的 key 永远不会被删除
• 内存泄漏风险（Redis 会报告 used_memory 高但 keys 少）
• 因此必须配合定期删除使用

25.3 定期删除：activeExpireCycle

activeExpireCycle 是 Redis 主动扫描并删除过期 key 的核心函数，由 serverCron 驱动：

// expire.c
#define ACTIVE_EXPIRE_CYCLE_SLOW    0  // 慢速模式（serverCron 每次执行，25% CPU 上限）
#define ACTIVE_EXPIRE_CYCLE_FAST    1  // 快速模式（beforeSleep 执行，1ms 时间上限）

void activeExpireCycle(int type) {
    // 时间限制（防止过期扫描占用过多 CPU）
    unsigned long
        effort = server.active_expire_effort - 1, /* 0-9, 默认0 */
        config_keys_per_loop = ACTIVE_EXPIRE_CYCLE_KEYS_PER_LOOP + /* 20 */
                               ACTIVE_EXPIRE_CYCLE_KEYS_PER_LOOP/4 * effort,
        config_cycle_fast_duration = ACTIVE_EXPIRE_CYCLE_FAST_DURATION +    /* 1000µs */
                                     ACTIVE_EXPIRE_CYCLE_FAST_DURATION/4 * effort,
        config_cycle_slow_duration = ACTIVE_EXPIRE_CYCLE_SLOW_DURATION,     /* 25% CPU */
        config_cycle_acceptable_stale = ACTIVE_EXPIRE_CYCLE_ACCEPTABLE_STALE; /* 10% */

    long long start = ustime(), timelimit, elapsed;

    // 计算本次允许的时间上限
    if (type == ACTIVE_EXPIRE_CYCLE_FAST) {
        timelimit = config_cycle_fast_duration;
    } else {
        // 慢速模式：占用不超过 ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC% CPU
        // 默认 25%，即每次最多 250ms（如果 serverCron 每秒10次的话）
        timelimit = 1000000 * ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC / server.hz / 100;
    }

    // 遍历所有 DB
    for (j = 0; j < dbs_per_call && timelimit_exit == 0; j++) {
        redisDb *db = server.db + (current_db % server.dbnum);
        current_db++;

        do {
            // 快速路径：如果 expires 字典为空，跳过
            if (dictSize(db->expires) == 0) break;

            unsigned long num = dictSize(db->expires);
            unsigned long slots = dictSlots(db->expires);

            // 如果 expires 字典填充率很低，跳过（避免空扫描）
            if (num && slots > DICT_HT_INITIAL_SIZE &&
                (num * 100 / slots < 1)) break;

            expired = 0;
            sampled = 0;
            long long ttl_sum = 0;
            int ttl_samples = 0;

            // 随机采样 config_keys_per_loop（默认20）个 key
            if (num > config_keys_per_loop)
                num = config_keys_per_loop;

            while (sampled < num) {
                dictEntry *de;
                long long ttl;

                // 随机获取一个 expires 字典中的 entry
                if ((de = dictGetRandomKey(db->expires)) == NULL) break;
                ttl = dictGetSignedIntegerVal(de) - now;

                // 检查是否过期并删除
                if (activeExpireCycleTryExpire(db, de, now)) expired++;

                if (ttl > 0) {
                    ttl_sum += ttl;
                    ttl_samples++;
                }
                sampled++;
            }

            // 更新平均 TTL 统计
            if (ttl_samples) db->avg_ttl = ttl_sum / ttl_samples;

            // 如果过期比例 > config_cycle_acceptable_stale（默认10%）
            // 继续采样（更激进地清理）
        } while (sampled == 0 ||
                 (expired * 100 / sampled) > config_cycle_acceptable_stale);

        // 超时检查
        elapsed = ustime() - start;
        if (elapsed > timelimit) {
            timelimit_exit = 1;
            server.stat_expire_cycle_time_used += elapsed;
            break;
        }
    }
}

activeExpireCycleTryExpire：实际删除

static int activeExpireCycleTryExpire(redisDb *db, dictEntry *de, long long now) {
    long long t = dictGetSignedIntegerVal(de);
    if (now > t) {
        sds key = dictGetKey(de);
        robj *keyobj = createStringObject(key, sdslen(key));

        propagateExpire(db, keyobj, server.lazyfree_lazy_expire);
        if (server.lazyfree_lazy_expire) {
            dbAsyncDelete(db, keyobj);
        } else {
            dbSyncDelete(db, keyobj);
        }
        notifyKeyspaceEvent(NOTIFY_GENERIC, "expired", keyobj, db->id);
        decrRefCount(keyobj);
        server.stat_expiredkeys++;
        return 1;
    }
    return 0;
}

hz 配置对过期精度的影响

# redis.conf
hz 10          # 默认：每秒10次 serverCron = 过期扫描最低精度 100ms
hz 100         # 高精度：每秒100次，过期延迟最低 10ms，但 CPU 占用上升
dynamic-hz yes # 动态 hz：有大量客户端时自动提升（最高 500Hz）

实测数据：

• hz 10（默认）：过期 key 的实际删除时间可能比 TTL 晚 0–100ms
• hz 100：过期延迟降至 0–10ms，CPU 额外占用约 1–3%
• 过期 key 数量极多时：可能出现扫描超过时间上限，部分 key 延迟删除

25.4 从库的过期处理

从库的过期处理有一个重要的特殊性：

// 从库不主动删除过期 key
// 只有当主库发送 DEL/UNLINK 命令时，从库才删除

// 从库读取过期 key 时：
// - 返回空值（对客户端表现为 key 不存在）
// - 但 key 实际还在内存中，等待主库的 DEL 命令
// 这种设计保证了主从的最终一致性

// expireIfNeeded 中的从库逻辑
if (server.masterhost != NULL) {
    // 从库：不删除，但告诉调用者这个 key 已过期
    if (!(flags & EXPIRE_FORCE_DELETE_EXPIRED)) return 1;
}

从库过期问题的实际影响：

• 从库上读取刚过期但主库还未同步 DEL 的 key → 返回空（正确）
• 主库负载高时，过期 key 的 DEL 命令可能延迟传到从库
• 从库上的 dbsize 可能比主库大（包含了已过期但未清除的 key）

25.5 内存淘汰机制：触发条件

当 Redis 的 used_memory 达到 maxmemory 时，每次新的写命令执行前触发内存淘汰：

// server.c — processCommand
int processCommand(client *c) {
    // ...
    if (server.maxmemory && !server.loading) {
        int out_of_memory = (performEvictions() == EVICT_FAIL);
        // 如果淘汰失败（noeviction 或无法淘汰）→ 返回错误
        if (out_of_memory && isCommandDeniedInOOM(c)) {
            addReply(c, shared.oomerr);
            return C_OK;
        }
    }
    // 继续执行命令...
}

25.6 8种内存淘汰策略

策略总览

performEvictions 核心流程

// evict.c
int performEvictions(void) {
    if (!isSafeToPerformEvictions()) return EVICT_OK;

    // 检查是否需要淘汰
    size_t mem_reported, mem_tofree;
    if (getMaxmemoryState(&mem_reported, NULL, &mem_tofree, NULL) == C_OK)
        return EVICT_OK;  // 内存充足，不需要淘汰

    int keys_freed = 0;
    while (mem_tofree > 0) {
        // 寻找候选 key（依据策略）
        bestkey = NULL;
        server.eviction_pool_size = 0;

        for (int j = 0; j < server.dbnum; j++) {
            redisDb *db = server.db + j;
            dict *dict;

            // 根据策略选择字典范围
            if (server.maxmemory_policy & MAXMEMORY_FLAG_ALLKEYS) {
                dict = db->dict;          // 所有 key
            } else {
                dict = db->expires;       // 仅有 TTL 的 key
            }
            if (dictSize(dict) == 0) continue;

            // 根据具体策略填充候选池
            if (server.maxmemory_policy & MAXMEMORY_FLAG_LRU) {
                evictionPoolPopulate(j, dict, db->dict, pool);
            } else if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
                evictionPoolPopulate(j, dict, db->dict, pool);
            } else if (server.maxmemory_policy == MAXMEMORY_ALLKEYS_RANDOM) {
                dictEntry *de = dictGetRandomKey(dict);
                bestkey = dictGetKey(de);
                bestdbid = j;
            } else if (server.maxmemory_policy == MAXMEMORY_VOLATILE_RANDOM) {
                dictEntry *de = dictGetRandomKey(dict);
                bestkey = dictGetKey(de);
                bestdbid = j;
            } else if (server.maxmemory_policy == MAXMEMORY_VOLATILE_TTL) {
                // 找 TTL 最小的 key
                // 随机采样 maxmemory_samples 个，选 TTL 最小的
            }
        }

        // 从候选池中选出最佳 key
        if (bestkey == NULL && pool[0].key != NULL) {
            // 从 eviction pool 中取分数最低的（最适合被淘汰的）
            bestkey = pool[EVPOOL_SIZE-1].key;
        }

        if (bestkey) {
            // 执行淘汰
            robj *keyobj = createStringObject(bestkey, sdslen(bestkey));
            propagateExpire(db, keyobj, server.lazyfree_lazy_eviction);
            if (server.lazyfree_lazy_eviction) {
                dbAsyncDelete(db, keyobj);
            } else {
                dbSyncDelete(db, keyobj);
            }
            server.stat_evictedkeys++;
            mem_tofree -= estimatedSize;
            keys_freed++;
        }

        if (mem_tofree <= 0 || bestkey == NULL) break;
    }

    return keys_freed > 0 ? EVICT_OK : EVICT_FAIL;
}

25.7 LRU 近似算法：Redis 的独特设计

为什么不用精确 LRU

精确 LRU 需要一个按访问时间有序的双向链表，每次访问都要调整链表，开销是 O(1) 但内存开销大：

每个 key 的精确 LRU 链表节点：2个指针（16字节）
100万个 key：额外 16MB 内存
更严重：指针修改的 cache miss 开销

Redis 的近似 LRU

// 每个 redisObject 的 lru 字段（24bit）存储 LRU 时钟值
typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:24;   // LRU 时钟（秒，24bit，低位截断，约194天循环）
    int refcount;
    void *ptr;
} robj;

// LRU 时钟更新（server.lruclock，每次 serverCron 更新）
#define LRU_CLOCK_MAX ((1<<24)-1)  // 16777215 秒
#define LRU_CLOCK_RESOLUTION 1000  // 1秒精度

unsigned int getLRUClock(void) {
    return (mstime()/LRU_CLOCK_RESOLUTION) & LRU_CLOCK_MAX;
}

// 计算 key 的空闲时间（毫秒）
unsigned long long estimateObjectIdleTime(robj *o) {
    unsigned long long lruclock = LRU_CLOCK();
    if (lruclock >= o->lru) {
        return (lruclock - o->lru) * LRU_CLOCK_RESOLUTION;
    } else {
        // 时钟回绕（24bit 溢出，194天后）
        return (lruclock + (LRU_CLOCK_MAX - o->lru)) * LRU_CLOCK_RESOLUTION;
    }
}

evictionPoolPopulate：近似 LRU 采样

// evict.c
void evictionPoolPopulate(int dbid, dict *sampledict, dict *keydict,
                          struct evictionPoolEntry *pool) {
    int j, k, count;
    dictEntry *samples[server.maxmemory_samples];  // 默认5个

    // 随机采样 maxmemory_samples 个 key
    count = dictGetSomeKeys(sampledict, samples, server.maxmemory_samples);

    for (j = 0; j < count; j++) {
        unsigned long long idle;
        sds key;
        robj *o;
        dictEntry *de;

        de = samples[j];
        key = dictGetKey(de);

        // 在 keydict（主字典）中找到 value（eviction pool 可能来自 expires dict）
        if (sampledict != keydict) de = dictFind(keydict, key);
        o = dictGetVal(de);

        // 计算"空闲时间"分数（LRU 或 LFU 都用此接口，但含义不同）
        if (server.maxmemory_policy & MAXMEMORY_FLAG_LRU) {
            idle = estimateObjectIdleTime(o);
        } else if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
            // LFU 模式：空闲时间分数 = 255 - lfu_freq
            // 频率越低 → idle 分数越高 → 越先被淘汰
            idle = 255 - LFUDecrAndReturn(o);
        } else if (server.maxmemory_policy == MAXMEMORY_VOLATILE_TTL) {
            // TTL 越小 → idle 分数越高
            idle = ULLONG_MAX - (long)dictGetVal(de);
        }

        // 插入 eviction pool（按 idle 升序，末尾 idle 最大即最应淘汰）
        // pool 大小 EVPOOL_SIZE = 16
        k = 0;
        while (k < EVPOOL_SIZE && pool[k].key &&
               pool[k].idle < idle) k++;

        if (k == 0 && pool[EVPOOL_SIZE-1].key != NULL) continue; // pool已满且新entry idle最小

        // 将新entry插入合适位置，移动其他entry
        // ...
    }
}

近似 LRU 的精度：

• maxmemory-samples 5（默认）：精度约 80%（vs 精确 LRU）
• maxmemory-samples 10：精度约 95%
• maxmemory-samples 20：精度约 99%，接近精确 LRU
• 性能开销：samples=5 时每次淘汰约需 5 次随机字典查找

25.8 LFU Morris 计数器：Redis 4.0 的创新

传统计数的问题

纯计数器的 LFU 会导致：

• 旧热点永不被淘汰（历史高计数会保持很久）
• 新出现的热点无法替换旧热点
• 计数无限增长，内存占用增大

Redis 的 LFU 实现

Redis 复用 redisObject.lru 字段（24bit）作为 LFU 计数器：

// lfu 字段布局（24bit）：
// 高16bit = 最后访问时间（分钟，低16位截断，约45天循环）
// 低8bit  = Morris 计数器（0–255）

#define LFU_INIT_VAL 5  // 新 key 的初始计数值

// 获取 LFU 频率（同时执行时间衰减）
uint8_t LFUDecrAndReturn(robj *o) {
    unsigned long ldt = o->lru >> 8;      // 高16bit：最后访问分钟
    unsigned long counter = o->lru & 255; // 低8bit：Morris 计数

    // 计算需要衰减的量
    // lfu-decay-time（默认1分钟）：每经过 lfu-decay-time 分钟，计数减1
    unsigned long num_periods = LFUTimeElapsed(ldt) / server.lfu_decay_time;
    if (num_periods) {
        counter = (num_periods > counter) ? 0 : counter - num_periods;
    }
    return counter;
}

// LFUTimeElapsed：计算距上次访问经过了多少分钟
unsigned long LFUTimeElapsed(unsigned long ldt) {
    unsigned long now = LFUGetTimeInMinutes();
    if (now >= ldt) return now - ldt;
    return 65535 - ldt + now;  // 处理16bit回绕（45天）
}

// Morris 计数器递增（概率性增加）
uint8_t LFULogIncr(uint8_t counter) {
    if (counter == 255) return 255;  // 已到最大值
    double r = (double)rand() / RAND_MAX;
    // 递增概率 = 1 / (counter * lfu-log-factor + 1)
    // 计数越大，递增概率越低 → 防止计数无限增长
    double p = 1.0 / (counter * server.lfu_log_factor + 1);
    if (r < p) counter++;
    return counter;
}

访问时更新 LFU

// object.c — lookupKey 调用后执行
void updateLFU(robj *val) {
    unsigned long counter = LFUDecrAndReturn(val);
    counter = LFULogIncr(counter);
    val->lru = (LFUGetTimeInMinutes() << 8) | counter;
}

LFU 配置

# redis.conf

# LFU 计数器衰减速度：每 lfu-decay-time 分钟衰减1（默认1）
lfu-decay-time 1

# LFU 计数增长速度因子（默认10）
# 因子越大 → 计数增长越慢 → 需要更多访问才能达到高计数
# 因子越小 → 计数增长越快 → 更容易达到最大值255
lfu-log-factor 10

lfu-log-factor 对应的访问次数与计数关系：

• lfu-log-factor 10（默认）：约需 10 万次访问才能接近 255，适合真实热点区分

25.9 淘汰策略选择指南

不同业务场景的建议

# 场景1：纯缓存（所有 key 可淘汰）
maxmemory-policy allkeys-lru
# 优点：自动淘汰最久未访问的 key，无需设置 TTL

# 场景2：热点不均匀的缓存（少量 key 被频繁访问）
maxmemory-policy allkeys-lfu
# 优点：LFU 比 LRU 更准确地识别真正的热点

# 场景3：缓存与持久数据混存
maxmemory-policy volatile-lru  # 或 volatile-lfu
# 缓存 key 设 TTL，持久数据不设 TTL
# 淘汰时只淘汰有 TTL 的缓存 key，保留持久数据

# 场景4：数据库类应用（不允许丢失数据）
maxmemory-policy noeviction
# 写满后新写入命令返回 OOM 错误，由应用层处理

# 场景5：临时数据（优先淘汰即将过期的）
maxmemory-policy volatile-ttl
# 适合 session、验证码等短 TTL 数据

maxmemory 设置建议

# 建议设置为物理内存的 70–80%（预留给 OS、fork 等）
maxmemory 6gb          # 8GB 内存的机器

# 集群模式：每个节点单独设置 maxmemory
# 建议 = 总内存 / 主节点数（不含从节点内存）

# 主从模式：主库设 maxmemory，从库不设（或设更大值）
# 从库的 output buffer 不计入 maxmemory

# 查看当前内存使用
redis-cli INFO memory | grep "used_memory:"
redis-cli INFO memory | grep "maxmemory:"

25.10 监控与调优

过期删除监控

# 查看过期 key 统计
redis-cli INFO stats | grep expired
# expired_keys:12345678  # 累计删除的过期 key 数量

# 查看每秒过期速率（结合 INFO stats + 时间差计算）
redis-cli --stat | grep expired

# 主动触发过期扫描（调试用）
redis-cli DEBUG SLEEP 0  # 触发一次 serverCron 而不等待

淘汰统计

redis-cli INFO stats | grep evicted
# evicted_keys:0  # 累计淘汰的 key 数量

# 实时监控淘汰速率
redis-cli MONITOR  # 观察 DEL 命令频率

# keyspace 统计
redis-cli INFO keyspace
# db0:keys=1000000,expires=500000,avg_ttl=3600000

调优参数

# 提高过期扫描精度（默认10，可调至100）
hz 100
dynamic-hz yes

# 提高过期扫描力度（0-9，默认0）
active-expire-effort 5

# 提高 LRU 采样数（默认5，调至10可显著提升精度）
maxmemory-samples 10

# 开启 lazyfree 加速过期删除
lazyfree-lazy-expire yes
lazyfree-lazy-eviction yes

本章小结

• expires 字典与 dict 字典 key 共享 SDS 指针，value 直接存 long long 时间戳（毫秒），设计极为紧凑
• 惰性删除（expireIfNeeded）在每次读写时触发，必须配合定期删除使用
• 定期删除（activeExpireCycle）随机采样20个 key，过期比例 > 10% 则继续，整体 CPU 占用不超过 25%
• 从库不主动删除过期 key，等待主库的 DEL/EXPIRE 命令，保证主从一致性
• 8种淘汰策略中：allkeys-lru 适合通用缓存，allkeys-lfu 适合热点不均匀场景，volatile-* 适合混存
• Redis 的近似 LRU（随机采样5个，取空闲时间最长的）以极低内存开销达到接近精确 LRU 的效果
• LFU Morris 计数器（低8bit）+ 时间戳（高16bit）复用 lru 字段，概率性递增防止计数溢出，按分钟衰减保证老热点被替换
• maxmemory-samples 从5调至10，LRU/LFU 精度从约80%提升至约95%，CPU 开销翻倍但仍极低