浅谈Redis 中的过期删除策略和内存淘汰机制

// https://GitHub.com/redis/redis/blob/6.2/src/db.C#L1541
// 当访问到 key 的时候，会调用这个函数，因为有的 key 虽然已经过期了，但是还可能存在于内存中

// key 仍然有效，函数返回值为0，否则，如果 key 过期，函数返回1。
int expireIfNeeded(redisDb *db, robj *key) {
    // 没有过期
    if (!keyIsExpired(db,key)) return 0;

    // 从库的过期是主库控制的，是不会进行删除操作的
    // 上面已经判断过是否到期了，所以这里的 key 肯定是过期的 key ,不过如果是主节点创建的 key 从节点就不删除，只会返回已经过期了
    if (server.masterhost != NULL) return 1;
    ...
    
    // 删除 key 
    deleteExpiredKeyAndPropagate(db,key);
    return 1;
}

// Https://github.com/redis/redis/blob/6.2/src/server.c#L1853
// 这个函数处理我们需要在Redis数据库中增量执行的“后台”操作，例如活动键过期，调整大小，重哈希。
void databasesCron(void) {
    // 通过随机抽样来过期
    // 这里区分了主节点和从节点的处理
    if (server.active_expire_enabled) {
        if (iAmMaster()) {
            activeExpireCycle(ACTIVE_EXPIRE_CYCLE_SLOW);
        } else {
            expireSlaveKeys();
        }
    }
    ...
}

// https://github.com/redis/redis/blob/6.2/src/expire.c#L113
void activeExpireCycle(int type) {
    // 根据配置的超时工作调整运行参数。默认工作量为1，最大可配置工作量为10
    unsigned long
    effort = server.active_expire_effort-1, 
    // 采样的 key 的数量
    config_keys_per_loop = ACTIVE_EXPIRE_CYCLE_KEYS_PER_LOOP +
                           ACTIVE_EXPIRE_CYCLE_KEYS_PER_LOOP/4*effort,
    // 占比CPU时间，默认是25%，最大43%，如果是100%，那除了定时删除其他的工作都做不了了，所以要做限制
    config_cycle_slow_time_perc = ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC +
                                  2*effort,
    // 可接受的过期 key 的百分比
    config_cycle_acceptable_stale = ACTIVE_EXPIRE_CYCLE_ACCEPTABLE_STALE-
                                    effort;
    ...
    //慢速定期删除的执行时长
    timelimit = config_cycle_slow_time_perc*1000000/server.hz/100;
    timelimit_exit = 0;
    ...
    // 在 key 过期时积累一些全局统计信息，以便了解逻辑上已经过期但仍存在于数据库中的 key 的数量
    long total_sampled = 0;
    long total_expired = 0;

    for (j = 0; j < dbs_per_call && timelimit_exit == 0; j++) {
        ...
        // 如果超过 config_cycle_acceptable_stale 的key过期了，则重复删除的过程，直到过期key的比例降至 config_cycle_acceptable_stale 以下。  
        // 存储在 config_cycle_acceptable_stale 中的百分比不是固定的，而是取决于Redis配置的“expire efforce”  
        do {
            
            if ((num = dictSize(db->expires)) == 0) {
                db->avg_ttl = 0;
                break;
            }
            ...
            // 采样的 key 的数量 
            if (num > config_keys_per_loop)
                num = config_keys_per_loop;
            ...
            while (sampled < num && checked_buckets < max_buckets) {
                for (int table = 0; table < 2; table++) {
                    ...
                    while(de) {
                        
                        dictEntry *e = de;
                        de = de->next;

                        ttl = dictGetSignedIntegerVal(e)-now;
                        // 过期检查，并对过期键进行删除
                        if (activeExpireCycleTryExpire(db,e,now)) expired++;
                        ...
                    }
                }
                db->expires_cursor++;
            }
         ...
        // 判断过期 key 的占比是否大于 config_cycle_acceptable_stale，如果大于持续进行过期 key 的删除
        } while (sampled == 0 ||
                 (expired*100/sampled) > config_cycle_acceptable_stale);
    }
    ...
}

// 检查删除由从节点创建的有过期的时间的 key 
void expireSlaveKeys(void) {
    // 从主库同步的 key，过期时间由主库维护，主库同步 DEL 操作到从库。
    // 从库如果是 READ-WRITE 模式，就可以继续写入数据。从库自己写入的数据就需要自己来维护其过期操作。
    if (slaveKeysWithExpire == NULL ||
        dictSize(slaveKeysWithExpire) == 0) return;
     ...
}

// https://github.com/redis/redis/blob/6.2/src/db.c#L1541
// 当访问到 key 的时候，会调用这个函数，因为有的 key 虽然已经过期了，但是还可能存在于内存中

// key 仍然有效，函数返回值为0，否则，如果 key 过期，函数返回1。
int expireIfNeeded(redisDb *db, robj *key) {
    // 检查 key 是否过期
    if (!keyIsExpired(db,key)) return 0;

    // 从库的过期是主库控制的，是不会进行删除操作的
    // 上面已经判断过是否到期了，所以这里的 key 肯定设计过期的 key ,不过如果是主节点创建的 key 从节点就不删除，只会返回已经过期了
    if (server.masterhost != NULL) return 1;
    ...
    
    // 删除 key 
    deleteExpiredKeyAndPropagate(db,key);
    return 1;
}

// https://github.com/redis/redis/blob/6.2/src/db.c#L1485

int keyIsExpired(redisDb *db, robj *key) {
    // 过期时间
    mstime_t when = getExpire(db,key);
    mstime_t now;

    // 没有过期
    if (when < 0) return 0; 

    
    if (server.loading) return 0;

    // lua 脚本执行的过程中不过期
    if (server.lua_caller) {
        now = server.lua_time_snapshot;
    }
    // 如果我们正在执行一个命令，我们仍然希望使用一个不会改变的引用时间:在这种情况下，我们只使用缓存的时间，我们在每次调用call()函数之前更新。
    // 这样我们就避免了RPOPLPUSH之类的命令，这些命令可能会重新打开相同的键多次，如果下次调用会看到键过期，则会使已经打开的对象在下次调用中失效，而第一次调用没有。
    else if (server.fixed_time_expire > 0) {
        now = server.mstime;
    }
    // 其他情况下，获取最新的时间
    else {
        now = mstime();
    }
    // 判断是否过期了
    return now > when;
}

// 返回指定 key 的过期时间，如果没有过期则返回-1
long long getExpire(redisDb *db, robj *key) {
    dictEntry *de;

    
    if (dictSize(db->expires) == 0 ||
       (de = dictFind(db->expires,key->ptr)) == NULL) return -1;

    
    serverAssertWithInfo(NULL,key,dictFind(db->dict,key->ptr) != NULL);
    return dictGetSignedIntegerVal(de);
}

127.0.0.1:6379> config get maxmemory
1) "maxmemory"
2) "0"

// https://github.com/redis/redis/blob/6.2/src/server.h#L673
typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    // 这里保存 
    // LRU时间(相对于全局LRU时钟)
    // LFU数据 (低 8 bits 作为计数器,用 24 bits 中的高 16 bits，记录访问的时间戳)
    unsigned lru:LRU_BITS; 
    int refcount;
    void *ptr;
} robj;

// https://github.com/redis/redis/blob/6.2/src/object.c#L41  
robj *createObject(int type, void *ptr) {
    robj *o = zmalloc(sizeof(*o));
    o->type = type;
    o->encoding = OBJ_ENCODING_RAW;
    o->ptr = ptr;
    o->refcount = 1;

    // 如果缓存替换策略是LFU，那么将lru变量设置为LFU的计数值
    if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
        o->lru = (LFUGetTimeInMinutes()<<8) | LFU_INIT_VAL;
    } else {
    // 如果是 lru 
    // 调用LRU_CLOCK函数获取LRU时钟值
        o->lru = LRU_CLOCK();
    }
    return o;
}

// https://github.com/redis/redis/blob/6.2/src/db.c#L63
robj *lookupKey(redisDb *db, robj *key, int flags) {
    dictEntry *de = dictFind(db->dict,key->ptr);
    if (de) {
        robj *val = dictGetVal(de);

        
        if (!hasActiveChildProcess() && !(flags & LOOKUP_NOTOUCH)){
            if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
                updateLFU(val);
            } else {
                // 使用 LRU 更新 lru 的时间
                val->lru = LRU_CLOCK();
            }
        }
        return val;
    } else {
        return NULL;
    }
}

// https://github.com/redis/redis/blob/6.2/src/evict.c#L512
int performEvictions(void) {
    ...
    while (mem_freed < (long long)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;

                
                // 根据淘汰策略，决定使用全局哈希表还是设置了过期时间的key的哈希表
                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) {
                        // 将选择的哈希表dict传入evictionPoolPopulate函数，同时将全局哈希表也传给evictionPoolPopulate函数
                        evictionPoolPopulate(i, dict, db->dict, pool);
                        total_keys += keys;
                    }
                }
                ...
            }
        }
    ...
}

// 用来填充evictionPool
// 按升序插入键，所以空闲时间小的键在左边，空闲时间高的键在右边。
// https://github.com/redis/redis/blob/6.2/src/evict.c#L145
void evictionPoolPopulate(int dbid, dict *sampledict, dict *keydict, struct evictionPoolEntry *pool) {
    int j, k, count;
    dictEntry *samples[server.maxmemory_samples];

    count = dictGetSomeKeys(sampledict,samples,server.maxmemory_samples);
    for (j = 0; j < count; j++) {
        ...
        // 将元素插入池中。 首先，找到第一个空闲时间小于我们空闲时间的空桶或第一个填充的桶。
        k = 0;
        while (k < EVPOOL_SIZE &&
               pool[k].key &&
               pool[k].idle < idle) k++;
        if (k == 0 && pool[EVPOOL_SIZE-1].key != NULL) {
            
            continue;
        } else if (k < EVPOOL_SIZE && pool[k].key == NULL) {
            
        } else {
            
            if (pool[EVPOOL_SIZE-1].key == NULL) {
                

                
                sds cached = pool[EVPOOL_SIZE-1].cached;
                memmove(pool+k+1,pool+k,
                    sizeof(pool[0])*(EVPOOL_SIZE-k-1));
                pool[k].cached = cached;
            } else {
                
                k--;
                
                sds cached = pool[0].cached; 
                if (pool[0].key != pool[0].cached) sdsfree(pool[0].key);
                memmove(pool,pool+1,sizeof(pool[0])*k);
                pool[k].cached = cached;
            }
        }
    ...
    }
}

// https://github.com/redis/redis/blob/6.2/src/evict.c#L55
struct evictionPoolEntry {
    // 待淘汰的键值对的空闲时间
    unsigned long long idle;    
    // 待淘汰的键值对的key
    sds key;                    
    // 缓存的SDS对象
    sds cached;                 
    // 待淘汰键值对的key所在的数据库ID
    int dbid;                   
};

static struct evictionPoolEntry *EvictionPoolLRU;

// https://github.com/redis/redis/blob/6.2/src/evict.c#L512
int performEvictions(void) {
    if (!isSafeToPerformEvictions()) return EVICT_OK;

    int keys_freed = 0;
    size_t mem_reported, mem_tofree;
    long long mem_freed; 
    mstime_t latency, eviction_latency;
    long long delta;
    int slaves = listLength(server.slaves);
    int result = EVICT_FAIL;

    if (getMaxmemoryState(&mem_reported,NULL,&mem_tofree,NULL) == C_OK)
        return EVICT_OK;
    ...
    while (mem_freed < (long long)mem_tofree) {

        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;
                ...
                
                // 从数组最后一个key开始查找
                for (k = EVPOOL_SIZE-1; k >= 0; k--) {
                    // 当前key为空值，则查找下一个key
                    if (pool[k].key == NULL) continue;
                    bestdbid = pool[k].dbid;

                    // 从全局哈希表或是expire哈希表中，获取当前key对应的键值对；
                    if (server.maxmemory_policy & MAXMEMORY_FLAG_ALLKEYS) {
                        de = dictFind(server.db[pool[k].dbid].dict,
                            pool[k].key);
                    } else {
                        de = dictFind(server.db[pool[k].dbid].expires,
                            pool[k].key);
                    }

                    
                    // 将当前key从EvictionPoolLRU数组删除
                    if (pool[k].key != pool[k].cached)
                        sdsfree(pool[k].key);
                    pool[k].key = NULL;
                    pool[k].idle = 0;

                    
                    // 如果当前key对应的键值对不为空，选择当前key为被淘汰的key
                    if (de) {
                        bestkey = dictGetKey(de);
                        break;
                    } else {
                        
                    }
                }
            }
        }
        ...
        
        if (bestkey) {
            db = server.db+bestdbid;
            robj *keyobj = createStrinGobject(bestkey,sdslen(bestkey));
            propagateExpire(db,keyobj,server.lazyfree_lazy_eviction);
            delta = (long long) zmalloc_used_memory();
            latencyStartMonitor(eviction_latency);
            // 惰性删除
            if (server.lazyfree_lazy_eviction)
                dbAsyncDelete(db,keyobj);
            else
                // 同步删除
                dbSyncDelete(db,keyobj);
            ...
        }
    }
    ...
}

// https://github.com/redis/redis/blob/6.2/src/server.h#L673
typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    // 这里保存 
    // LRU时间(相对于全局LRU时钟)
    // LFU数据 (低 8 bits 作为计数器,用 24 bits 中的高 16 bits，记录访问的时间戳)
    unsigned lru:LRU_BITS; 
    int refcount;
    void *ptr;
} robj;

// https://github.com/redis/redis/blob/6.2/src/object.c#L41  
robj *createObject(int type, void *ptr) {
    robj *o = zmalloc(sizeof(*o));
    o->type = type;
    o->encoding = OBJ_ENCODING_RAW;
    o->ptr = ptr;
    o->refcount = 1;

    // 如果缓存替换策略是LFU，lru变量包括以分钟为精度的UNIX时间戳和访问次数5
    if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
        o->lru = (LFUGetTimeInMinutes()<<8) | LFU_INIT_VAL;
    } else {
    // 如果是 lru 
    // 调用LRU_CLOCK函数获取LRU时钟值
        o->lru = LRU_CLOCK();
    }
    return o;
}

// https://github.com/redis/redis/blob/6.2/src/db.c#L63
robj *lookupKey(redisDb *db, robj *key, int flags) {
    dictEntry *de = dictFind(db->dict,key->ptr);
    if (de) {
        robj *val = dictGetVal(de);

        // 使用LFU算法时，调用updateLFU函数更新访问频率
        if (!hasActiveChildProcess() && !(flags & LOOKUP_NOTOUCH)){
            if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
                updateLFU(val);
            } else {
                // 使用 LRU 更新 lru 的时间
                val->lru = LRU_CLOCK();
            }
        }
        return val;
    } else {
        return NULL;
    }
}

// https://github.com/redis/redis/blob/6.2/src/db.c#L54

void updateLFU(robj *val) {
    unsigned long counter = LFUDecrAndReturn(val);
    counter = LFULogIncr(counter);
    val->lru = (LFUGetTimeInMinutes()<<8) | counter;
}

// https://github.com/redis/redis/blob/6.2/src/evict.c#L318
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)
        // 如果衰减大小小于当前访问次数，那么，衰减后的访问次数是当前访问次数减去衰减大小；否则，衰减后的访问次数等于0
        counter = (num_periods > counter) ? 0 : counter - num_periods;
    // 如果衰减大小为0，则返回原来的访问次数
    return counter;
}

// https://github.com/redis/redis/blob/6.2/src/evict.c#L298
uint8_t LFULogIncr(uint8_t counter) {
    // 等于255，不在进行次数的更新
    if (counter == 255) return 255;
    // 计算一个随机数
    double r = (double)rand()/RAND_MAX;
    // 计算当前访问次数和初始值的差值
    double baseval = counter - LFU_INIT_VAL;
    if (baseval < 0) baseval = 0;
    // 根据baseval和lfu_log_factor计算阈值p
    double p = 1.0/(baseval*server.lfu_log_factor+1);
    // 概率值小于阀值
    if (r < p) counter++;
    return counter;
}

        if (server.maxmemory_policy & MAXMEMORY_FLAG_LRU) {
            idle = estimateObjectIdleTime(o);
        } else if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
            idle = 255-LFUDecrAndReturn(o);
        }

127.0.0.1:6379> INFO memory
# Memory
used_memory:865672
used_memory_human:845.38K
used_memory_rss:8085504
used_memory_rss_human:7.71M
used_memory_peak:865672
used_memory_peak_human:845.38K
used_memory_peak_perc:100.01%
used_memory_overhead:819226
used_memory_startup:802056
used_memory_dataset:46446
used_memory_dataset_perc:73.01%
allocator_allocated:995552
allocator_active:1282048
allocator_resident:3690496
total_system_memory:1929736192
total_system_memory_human:1.80G
used_memory_lua:37888
used_memory_lua_human:37.00K
used_memory_scripts:0
used_memory_scripts_human:0B
number_of_cached_scripts:0
maxmemory:0
maxmemory_human:0B
maxmemory_policy:noeviction
allocator_frag_ratio:1.29
allocator_frag_bytes:286496
allocator_rss_ratio:2.88
allocator_rss_bytes:2408448
rss_overhead_ratio:2.19
rss_overhead_bytes:4395008
mem_fragmentation_ratio:9.80
mem_fragmentation_bytes:7260856
mem_not_counted_for_evict:0
mem_replication_backlog:0
mem_clients_slaves:0
mem_clients_normal:16986
mem_aof_buffer:0
mem_allocator:jemalloc-5.1.0
active_defrag_running:0
lazyfree_pending_objects:0

mem_fragmentation_ratio = used_memory_rss/ used_memory

config set activedefrag yes

memory purge