第6集Redis工作原理之删除淘汰策略

引言

Redis作为内存数据库，内存管理是其核心功能之一。当内存不足时，Redis需要通过删除过期键和淘汰策略来释放空间，保证服务的正常运行。本文将深入探讨Redis的删除策略和内存淘汰机制。

Redis删除策略概述

Redis的删除策略主要涉及两个方面：

过期键的删除：如何处理设置了过期时间的键
内存淘汰策略：当内存不足时如何选择要删除的键

过期键的删除策略

1. 定时删除（Timed Deletion）

定时删除策略在设置键的过期时间时，同时创建一个定时器，在键过期时立即执行删除操作。

实现原理

// 定时删除的伪代码
void expireKeyTimer(redisDb *db, robj *key, long long when) {
    // 创建定时器
    aeCreateTimeEvent(server.el, when, expireKeyCallback, key);
}

void expireKeyCallback(aeEventLoop *eventLoop, long long id, void *clientData) {
    robj *key = clientData;
    // 检查键是否仍然过期
    if (isExpired(key)) {
        dbDelete(db, key);
    }
}

优缺点分析

优点：

及时释放内存，避免过期键占用空间
删除操作精确，不会延迟

缺点：

占用大量CPU资源
如果过期键很多，会创建大量定时器
影响Redis的整体性能

2. 惰性删除（Lazy Deletion）

惰性删除策略在访问键时检查其是否过期，如果过期则删除。

实现原理

// 惰性删除的实现
int expireIfNeeded(redisDb *db, robj *key) {
    if (!keyIsExpired(db, key)) return 0;
    
    // 如果是主服务器，删除过期键
    if (server.masterhost == NULL) {
        server.stat_expiredkeys++;
        propagateExpire(db, key, server.lazyfree_lazy_expire);
        notifyKeyspaceEvent(NOTIFY_EXPIRED, "expired", key, db->id);
        return dbDelete(db, key);
    }
    
    return 1;
}

// 在访问键时调用
robj *lookupKeyRead(redisDb *db, robj *key) {
    robj *val;
    
    expireIfNeeded(db, key);
    val = lookupKey(db, key, LOOKUP_NONE);
    
    if (val == NULL)
        server.stat_keyspace_misses++;
    else
        server.stat_keyspace_hits++;
    
    return val;
}

优缺点分析

优点：

CPU资源消耗少
只在需要时进行删除操作
不影响Redis的整体性能

缺点：

可能导致大量过期键占用内存
如果过期键不被访问，会一直占用空间
内存利用率可能较低

3. 定期删除（Periodic Deletion）

定期删除策略每隔一段时间，随机抽取部分键进行过期检查和删除。

实现原理

// 定期删除的实现
void activeExpireCycle(int type) {
    unsigned long
        effort = server.active_expire_effort-1, // 努力程度
        config_keys_per_loop = ACTIVE_EXPIRE_CYCLE_KEYS_PER_LOOP +
                               ACTIVE_EXPIRE_CYCLE_KEYS_PER_LOOP/4*effort,
        config_cycle_fast_duration = ACTIVE_EXPIRE_CYCLE_FAST_DURATION +
                                     ACTIVE_EXPIRE_CYCLE_FAST_DURATION/4*effort,
        config_cycle_slow_time_perc = ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC +
                                      2*effort,
        config_cycle_acceptable_stale = ACTIVE_EXPIRE_CYCLE_ACCEPTABLE_STALE-
                                        effort;
    
    // 快速模式：在短时间内处理更多键
    if (type == ACTIVE_EXPIRE_CYCLE_FAST) {
        if (!server.active_expire_enabled) return;
        
        start = server.cronloops;
        timelimit = config_cycle_fast_duration;
        timelimit_exit = 0;
        if (timelimit <= 0) timelimit = 1;
    } else {
        // 慢速模式：更仔细地处理键
        timelimit = config_cycle_slow_time_perc;
        timelimit = timelimit*1000000/server.hz/100;
        timelimit_exit = 0;
        if (timelimit <= 0) timelimit = 1;
    }
    
    // 随机抽取键进行检查
    for (j = 0; j < dbs_per_call && timelimit_exit == 0; j++) {
        int expired = 0;
        redisDb *db = server.db+(current_db % server.dbnum);
        
        current_db++;
        
        do {
            unsigned long num, slots;
            long long now, ttl_sum;
            int ttl_samples;
            
            if ((num = dictSize(db->expires)) == 0) {
                db->avg_ttl = 0;
                break;
            }
            slots = dictSlots(db->expires);
            now = mstime();
            
            // 随机选择键
            if (num && slots > DICT_HT_INITIAL_SIZE &&
                (num*100/slots < 1)) break;
            
            expired = 0;
            ttl_sum = 0;
            ttl_samples = 0;
            
            if (num > config_keys_per_loop)
                num = config_keys_per_loop;
            
            while (num--) {
                dictEntry *de;
                long long ttl;
                
                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++;
                }
            }
            
            if (ttl_samples) {
                long long avg_ttl = ttl_sum/ttl_samples;
                
                if (db->avg_ttl == 0) db->avg_ttl = avg_ttl;
                db->avg_ttl = (db->avg_ttl/50)*49 + (avg_ttl/50);
            }
            
        } while (expired > ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP/4);
    }
}

优缺点分析

优点：

在CPU和内存之间取得平衡
可以控制删除操作的频率
避免大量过期键占用内存

缺点：

可能无法及时删除所有过期键
需要调整参数来优化性能
删除操作不够精确

Redis的混合策略

Redis实际采用的是定期删除和惰性删除相结合的策略：

定期删除：通过activeExpireCycle函数定期清理过期键
惰性删除：在访问键时检查并删除过期键

这种混合策略在CPU使用和内存释放之间取得了良好的平衡。

内存淘汰策略

当Redis内存达到最大限制时，需要通过淘汰策略来释放空间。Redis提供了多种淘汰策略：

1. LRU（Least Recently Used）策略

volatile-lru

从设置了过期时间的键中，淘汰最近最少使用的键。

allkeys-lru

从所有键中，淘汰最近最少使用的键。

LRU实现原理

// LRU淘汰策略的实现
int freeMemoryIfNeeded(void) {
    size_t mem_used, mem_tofree, mem_freed;
    int slaves = listLength(server.slaves);
    mstime_t latency, eviction_latency;
    long long delta;
    
    // 计算当前内存使用量
    mem_used = zmalloc_used_memory();
    if (mem_used <= server.maxmemory) return C_OK;
    
    if (server.maxmemory_policy == MAXMEMORY_NO_EVICTION)
        return C_ERR;
    
    mem_tofree = mem_used - server.maxmemory;
    mem_freed = 0;
    latencyStartMonitor(latency);
    
    while (mem_freed < mem_tofree) {
        int j, k, i;
        static unsigned int next_db = 0;
        sds bestkey = NULL;
        int bestdbid;
        redisDb *db;
        dict *dict;
        dictEntry *de;
        
        if (server.maxmemory_policy & (MAXMEMORY_FLAG_LRU|MAXMEMORY_FLAG_LFU) ||
            server.maxmemory_policy == MAXMEMORY_VOLATILE_TTL)
        {
            struct evictionPoolEntry *pool = EvictionPoolLRU;
            
            while(bestkey == NULL) {
                unsigned long total_keys = 0, keys;
                
                for (i = 0; i < server.dbnum; i++) {
                    db = server.db+i;
                    dict = (server.maxmemory_policy & MAXMEMORY_FLAG_ALLKEYS) ?
                            db->dict : db->expires;
                    if ((keys = dictSize(dict)) != 0) {
                        evictionPoolPopulate(i, dict, db->dict, pool);
                        total_keys += keys;
                    }
                }
                if (!total_keys) break;
                
                for (k = EVPOOL_SIZE-1; k >= 0; k--) {
                    if (pool[k].key == NULL) continue;
                    bestdbid = pool[k].dbid;
                    
                    if (server.maxmemory_policy & MAXMEMORY_FLAG_ALLKEYS) {
                        de = dictFind(server.db[bestdbid].dict, pool[k].key);
                    } else {
                        de = dictFind(server.db[bestdbid].expires, pool[k].key);
                    }
                    
                    if (pool[k].idle < current_idle || pool[k].key == NULL) {
                        if (pool[k].key != NULL) {
                            sdsfree(pool[k].key);
                        }
                        pool[k].key = NULL;
                        pool[k].idle = 0;
                    }
                    
                    if (pool[k].key != NULL) {
                        bestkey = pool[k].key;
                        break;
                    }
                }
            }
        }
        
        // 执行删除操作
        if (bestkey) {
            db = server.db+bestdbid;
            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++;
            signalModifiedKey(NULL,db,bestkey);
            notifyKeyspaceEvent(NOTIFY_EVICTED, "evicted", keyobj, db->id);
            decrRefCount(keyobj);
            keys_freed++;
            
            if (slaves) flushSlavesOutputBuffers();
        }
    }
    
    latencyEndMonitor(latency);
    latencyAddSampleIfNeeded("eviction-cycle",latency);
    
    return C_OK;
}

2. LFU（Least Frequently Used）策略

Redis 4.0版本引入了LFU算法，更好地适应不同的访问模式。

volatile-lfu

从设置了过期时间的键中，淘汰使用频率最低的键。

allkeys-lfu

从所有键中，淘汰使用频率最低的键。

LFU实现原理

// LFU淘汰策略的实现
unsigned long LFUDecrAndReturn(robj *o) {
    unsigned long ldt = o->lru >> 8;
    unsigned long counter = o->lru & 255;
    unsigned long num_periods = server.lfu_decay_time ? 
        LFUTimeElapsed(ldt) / server.lfu_decay_time : 0;
    
    if (num_periods)
        counter = (num_periods > counter) ? 0 : counter - num_periods;
    
    return counter;
}

unsigned long LFULogIncr(unsigned long counter) {
    if (counter == 255) return 255;
    double r = (double)rand()/RAND_MAX;
    double baseval = counter - LFU_INIT_VAL;
    if (baseval < 0) baseval = 0;
    double p = 1.0/(baseval*server.lfu_log_factor+1);
    if (r < p) counter++;
    return counter;
}

3. 其他淘汰策略

volatile-random

从设置了过期时间的键中，随机淘汰键。

allkeys-random

从所有键中，随机淘汰键。

volatile-ttl

从设置了过期时间的键中，淘汰剩余生存时间最短的键。

noeviction

当内存不足以容纳新数据时，不淘汰任何键，而是返回错误。

内存管理配置

配置文件参数

# Redis配置文件中的内存管理参数
maxmemory 2gb                    # 设置最大内存限制
maxmemory-policy allkeys-lru     # 设置淘汰策略
maxmemory-samples 5              # LRU/LFU采样数量

动态配置

# 通过CONFIG命令动态配置
CONFIG SET maxmemory 2gb
CONFIG SET maxmemory-policy allkeys-lru
CONFIG SET maxmemory-samples 10

淘汰策略选择指南

业务场景分析

缓存场景
- 推荐：allkeys-lru
- 原因：缓存数据通常有访问热点，LRU能很好地保留热点数据
会话存储
- 推荐：volatile-lru
- 原因：会话数据有明确的过期时间，优先淘汰过期键
计数器场景
- 推荐：allkeys-lfu
- 原因：计数器访问频率相对稳定，LFU更适合
随机访问
- 推荐：allkeys-random
- 原因：访问模式随机，随机淘汰策略更公平

性能优化建议

调整采样数量

1 2	# 增加采样数量提高精确度，但会增加CPU开销 CONFIG SET maxmemory-samples 10

监控内存使用
1
2
# 查看内存使用情况
INFO memory

设置合理的内存限制

1 2	# 根据实际需求设置内存限制 CONFIG SET maxmemory 4gb

实际应用案例

案例1：电商缓存系统

# 电商商品缓存配置
import redis

# 连接Redis
r = redis.Redis(host='localhost', port=6379, db=0)

# 配置淘汰策略
r.config_set('maxmemory-policy', 'allkeys-lru')
r.config_set('maxmemory', '2gb')

# 设置商品缓存
def cache_product(product_id, product_info):
    key = f"product:{product_id}"
    r.setex(key, 3600, product_info)  # 1小时过期

# 获取商品信息
def get_product(product_id):
    key = f"product:{product_id}"
    return r.get(key)

案例2：用户会话管理

# 用户会话管理
def create_session(user_id, session_data):
    key = f"session:{user_id}"
    r.hset(key, mapping=session_data)
    r.expire(key, 1800)  # 30分钟过期

def get_session(user_id):
    key = f"session:{user_id}"
    return r.hgetall(key)

def extend_session(user_id):
    key = f"session:{user_id}"
    r.expire(key, 1800)  # 延长30分钟

案例3：排行榜系统

# 排行榜系统
def update_leaderboard(user_id, score):
    r.zadd('leaderboard', {user_id: score})
    
    # 只保留前1000名
    r.zremrangebyrank('leaderboard', 0, -1001)

def get_top_users(limit=10):
    return r.zrevrange('leaderboard', 0, limit-1, withscores=True)

监控和调优

关键指标监控

# 查看内存使用情况
INFO memory

# 查看键空间信息
INFO keyspace

# 查看过期键统计
INFO stats

性能调优

调整淘汰策略
- 根据业务特点选择合适的淘汰策略
- 定期评估和调整策略效果
优化内存使用
- 合理设置过期时间
- 使用压缩列表等节省内存的数据结构
监控关键指标
- 内存使用率
- 淘汰键数量
- 命中率

总结

Redis的删除淘汰策略是保证其高性能和稳定性的重要机制：

核心要点

过期键删除：采用定期删除和惰性删除的混合策略
内存淘汰：提供多种淘汰策略适应不同业务场景
性能平衡：在CPU使用和内存释放之间取得平衡
灵活配置：支持动态调整策略参数

最佳实践

根据业务特点选择合适的淘汰策略
合理设置内存限制和过期时间
定期监控内存使用情况
根据实际效果调整配置参数

理解Redis的删除淘汰策略，有助于我们更好地使用Redis，优化应用性能，避免内存问题。