int expireIfNeeded(redisDb *db, robj *key) {

    // key 未过期返回 0
    if (!keyIsExpired(db,key)) return 0;

    // 下面的逻辑都是 Key 过期的逻辑处理

    // 当前的节点是从节点, 返回 1, 然后结束
    // 为了保持主从数据的一致, 从节点不会主动清除数据, 都是主节点同步消息在删除
    if (server.masterhost != NULL) return 1;

    // 已经删除过期键个数 + 1
    server.stat_expiredkeys++;
    // 向从节点和 AOF 文件传播 key 过期信息, 清除过期 key
    propagateExpire(db,key,server.lazyfree_lazy_expire);
    // 发送事件通知
    notifyKeyspaceEvent(NOTIFY_EXPIRED,"expired",key,db->id);

    // lazyfree-lazy-expire 配置参数 (版本 4.0 以上支持), 默认为 0
    // 根据配置, 同步或异步删除 key (异步删除: 先将 key 逻辑删除, 然后在通过后台的线程池进行真正的空间释放)
    return server.lazyfree_lazy_expire ? dbAsyncDelete(db,key) : dbSyncDelete(db,key);
}

int keyIsExpired(redisDb *db, robj *key) {
    // 从过期字典中获取 key 对应的过期时间, 实际就是获取 dictEntity 的 v 中的 s64 值 (dictEntity.v.s64)
    mstime_t when = getExpire(db,key);
    mstime_t now;

    // 没有过期时间
    if (when  0) {
        // 有缓存时间, 线使用缓存时间
        // server.mstime 这个时间会在调用执行命令函数的 call() 前进行更新
        // 这样可以避免一些批量操作的命令, 比如 RPOPLPUSH 等命令, 这些命令会执行过程中可能多次访问这个 key
        // 而在多次的访问过程中, 可能出现上一次访问未过期, 下次访问已经过期了, 通过这个缓冲时间可以解决这个问题
        now = server.mstime;
    } else {
        // 其他情况, 直接获取当前时间
        now = mstime();
    }

    // 当前时间是否大于 key 的过期时间
    return now > when;
}

/**
 * get 命令对应的执行函数
 * 需要的参数都封装在 client 对象中
 */
void getCommand(client *c) {

    // getGenericCommand -> lookupKeyReadOrReply -> lookupKeyRead -> lookupKeyReadWithFlags
    // getGenericCommand 经过几个函数最终调用到 lookupKeyReadWithFlags
    getGenericCommand(c);
}

robj *lookupKeyReadWithFlags(redisDb *db, robj *key, int flags) {

    robj *val;
    // expireIfNeeded 返回 > 0, 过期了
    if (expireIfNeeded(db,key) == 1) {
        // 省略过期处理
        // 过期的处理, 然后 return null
    }

    // 非过期处理, 查找然后返回
    val = lookupKey(db,key,flags);
    if (val == NULL)
        server.stat_keyspace_misses++;
    else
        server.stat_keyspace_hits++;
    return val;
}

/**
 * 过期循环清除
 * 为了便于理解, 这里对函数的逻辑做了一点小调整和删除一些非必要的逻辑, 但是整体的逻辑不变

 * @type 模式, 取值有 2 个 ACTIVE_EXPIRE_CYCLE_SLOW (0, 慢模式), ACTIVE_EXPIRE_CYCLE_FAST (1, 快模式)
 */
void activeExpireCycle(int type) {

    // 静态变量, 当前处理的数据库索引
    // 静态的效果, 这个变量执行后的值不会被清空, 每次调用这个方法, 是上一次执行的值
    // 这样就可以保证 16 个数据库, 每次方法执行完, 下次进来可以执行到下一个数据库, 循环起来，而不是每次进来都从第 0 个开始
    static unsigned int current_db = 0;

    // 上一次清理是否是因为时间超时结束循环的, 同样是静态变量
    static int timelimit_exit = 0;    
    // 上一次快速循环循环的时间, 同样是静态变量
    static long long last_fast_cycle = 0;

    // 当前时间
    long long start = ustime(),

    // 本次循环清除是快速循环, 上一次是时间超时获取 2 次快速循环的时间差在 2 毫秒内, 不执行
    if (type == ACTIVE_EXPIRE_CYCLE_FAST) {
        // 上一次循环是因为时间超时结束的, 本次快速循环不进行
        if (!timelimit_exit) return;
        // 上次快速循环距离当前时间在 1000 * 2 = 2 毫秒内, 也不进行快速循环
        if (start expires);

            // num == 0 表示整个字典没有数据, 跳出循环，处理下一个数据库
            if (num == 0) {
                break;
            }

            // 计算整个过期字典的总大小
            unsigned long slots = dictSlots(db->expires);

            // DICT_HT_INITIAL_SIZE = 4, 每个字典初始化时的默认值
            // num > 0, 字典中有数据了, slots 大于 4, 表示当前的字典扩容过了
            // num && slots > DICT_HT_INITIAL_SIZE, 当前的字典扩容过同时里面有数据
            // num * 100 / slots  DICT_HT_INITIAL_SIZE && (num * 100 / slots  ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP)
                num = ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP;
            
            // 循环 num 次从字典中获取 key 
            while (num--) {

                dictEntry *de;
                // 从过期字典中随机获取一个 key, 获取不到, 就停止本次循环
                if ((de = dictGetRandomKey(db->expires)) == NULL) break;

                // 尝试释放这个 key, 如果 key 释放成功, 过期次数 + 1
                if (activeExpireCycleTryExpire(db,de,now)) expired++;

            }

            // 0xf = 15, iteration 表示遍历了 15 次
            if ((iteration & 0xf) == 0) {
                // 计算消耗时间
                int elapsed = ustime()-start;
                // 消耗时间超过了限制时间, 结束本次循环
                if (elapsed > timelimit) {
                    // 超过时间限制标识设置为 true, 本次循环清除超时了, 结束本次循环清除
                    timelimit_exit = 1;
                    break;
                }
            }

            // 本次清理的过期 key 超过了 25%, 继续, 否则结束
            // ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP = 20
            // 每次抽取的个数最大为 20 个, 控制 25%, 20 * 25% = 5 个
            // 也就是过期的个数大于 5 就是大于 25%, (ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP/4 = 5)
        } while (expired > ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP/4);
    }

    // 省略各种分析数据的记录
}

/**
 * Reids 启动时, 向事件轮询中注册的唯一一个定时事件(默认 100 毫秒执行一次), 执行的函数
 */
int serverCron(struct aeEventLoop *eventLoop, long long id, void *clientData) {
    ...
    // 数据库扫描
    databasesCron();
    ...
}

void databasesCron(void) {

    // 过期功能开启中, 默认为开启
    if (server.active_expire_enabled) {
        // 主节点
        if (server.masterhost == NULL) {
            // 慢模式循环清除
            activeExpireCycle(ACTIVE_EXPIRE_CYCLE_SLOW);
        } else {
            // 从节点处理
            expireSlaveKeys();
        }
    }

    ...
}

void beforeSleep(struct aeEventLoop *eventLoop) {

    ...

    // 过期功能开启中同时为主节点
    if (server.active_expire_enabled && server.masterhost == NULL)
        // 快模式循环清除
        activeExpireCycle(ACTIVE_EXPIRE_CYCLE_FAST);

    ...
}

typedef struct redisObject {
    
    /** 
     * 标识这个对象的数据类型, 常说的 String, Hash, List 等
     */
    unsigned type:4;

    /**
     * 可以理解为数据类型的具体实现类型
     * 比如数据类型为 List, 在具体的实现中可以是 ArrayList LinkedList 等
     */
    unsigned encoding:4;

    /** 
     * LRU_BITS = 24,
     * 一个 24 位的变量, 表示对象最后一次被程序访问的时间或者访问的次数, 与内存回收有关
     * 暂时知道有这个对象即可, 后面有分析
     */
    unsigned lru:LRU_BITS;

    /**
     * 被引用的次数, 当 refcount 为 0 的时候, 表示该对象已经不被任何对象引用, 则可以进行垃圾回收了
     */
    int refcount;

    /**
     * 一个指针, 指向具体的数据
     */
    void *ptr;

} robj;

/**
 * redisServer 可以看做整个 Redis 运行时的上下文, 保存的数据, 配置等都在这个结构体中
 */
struct redisServer {
    unsigned int lruclock = getLRUClock();
}

unsigned int getLRUClock(void) {
    // LRU_CLOCK_RESOLUTION = 1000
    // mstime() 当前时间毫秒, 当前时间的毫秒/LRU_CLOCK_RESOLUTION = 当前时间的毫秒/1000 = 变为单位秒
    // LRU_CLOCK_MAX = ((1

int serverCron(struct aeEventLoop *eventLoop, long long id, void *clientData) {
    // serverCron 默认是 100 毫秒执行一次
    unsigned int lruclock = getLRUClock();
    atomicSet(server.lruclock,lruclock);
}

robj *lookupKey(redisDb *db, robj *key, int flags) {
    // 从字典中获取 key 对应的 dictEntry (字典的设计可以看一下后面的附录)
    dictEntry *de = dictFind(db->dict,key->ptr);
    if (de) {
        // 获取 key 对应的 dictEntry 的存在
        // 获取 dictEntry 的 value 也就是 redisObject 对象
        robj *val = dictGetVal(de);

        if (server.rdb_child_pid == -1 && server.aof_child_pid == -1 && !(flags & LOOKUP_NOTOUCH)) {
            // 没有在进行 RDB 或 AOF 操作, 并且 flags 没有设置 LOOKUP_NOTOUCH

            // 淘汰策略设置的的 LFU 策略
            if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
                updateLFU(val);
            } else {
                // 其他策略, 更新 lru 为全局的 lruclock
                val->lru = LRU_CLOCK();
            }
        }
    } else {
        // key 不存在, 返回 null
        return NULL;
    }
}

unsigned int LRU_CLOCK(void) {
    unsigned int lruclock;
    // LRU_CLOCK_RESOLUTION = 1000
    // 1000/server.hz 就是上面定时任务 serverCron 的执行时间
    // 

unsigned long LFUGetTimeInMinutes(void) {
  // & 65535 保证时间的范围在 0 ~ 65535 之间, 不会超过 16 数值的大小   
  return (server.unixtime/60) & 65535;
}

uint8_t LFULogIncr(uint8_t counter) {
    // 当前的访问次数已经达到了最大值了
    if (counter == 255) 
        return 255;

    // 产生一个随机数
    double r = (double)rand()/RAND_MAX;
    // 获取一个基础值, 当前的次数 - 对象初始化的默认次数 (LFU_INIT_VAL = 5)
    double baseval = counter - LFU_INIT_VAL;
    if (baseval 

unsigned long LFUDecrAndReturn(robj *o) {

    // 右移 8 为, 也就是得的了高位的 16 位, 即 ldt, 得到上次记录的时间
    unsigned long ldt = o->lru >> 8;
    // 得到当前保存的次数
    unsigned long counter = o->lru & 255;

    // lfu_decay_time 衰减时间, 默认 1, 单位分钟
    // 如果没有配置 lfu_decay_time, 则默认不进行衰减, counter 当前是多少就是多少
    // 获取 2 次访问的时间差 / lfu_decay_time, 得到经过了多少个时间段   
    unsigned long num_periods = server.lfu_decay_time ? LFUTimeElapsed(ldt) / server.lfu_decay_time : 0;
    if (num_periods)
        // 最新的次数 = 当前的次数 - 经过了多少个时间段, 小于 0 时, 设置为 0 
        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;
}

robj *lookupKey(redisDb *db, robj *key, int flags) {
    
    dictEntry *de = dictFind(db->dict,key->ptr);
    if (de) {
        robj *val = dictGetVal(de);

        if (server.rdb_child_pid == -1 && server.aof_child_pid == -1 && !(flags & LOOKUP_NOTOUCH)) {
            // 淘汰策略设置的的 LFU 策略
            if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
                updateLFU(val);
            } else {
                val->lru = LRU_CLOCK();
            }
        }
    } else {
        return NULL;
    }
}

void updateLFU(robj *val) {
    // 通过衰减机制, 得到最新的 counter
    unsigned long counter = LFUDecrAndReturn(val);
    // 通过随机公式, 得到最新的 counter
    counter = LFULogIncr(counter);
    // 将最新的 counter 和 当前时间保存到 lru 字段中
    val->lru = (LFUGetTimeInMinutes()

int processCommand(client *c) {
    ...

    // 有设置最大内存 同时当前没有 lua 脚本超时的情况
    if (server.maxmemory && !server.lua_timedout) {
        // 有必要时, 尝试释放内存
        int out_of_memory = freeMemoryIfNeededAndSafe() == C_ERR;

        // 内存不够 同时执行的命令是变更命令 或者 当前的客户端开启了事务, 同时执行的命令不是 exec 
        if (out_of_memory && (c->cmd->flags & CMD_DENYOOM || (c->flags & CLIENT_MULTI && c->cmd->proc != execCommand))) {
            flagTransaction(c);
            // 响应 -OOM command not allowed when used memory > 'maxmemory'
            addReply(c, shared.oomerr);
            return C_OK;
        }
    }

    ...
}

int freeMemoryIfNeededAndSafe(void) {
    // 当前有 lua 脚本执行超时或者真正加载数据, 返回成功
    if (server.lua_timedout || server.loading) return C_OK;
    // 是否内存如果有必要的话
    return freeMemoryIfNeeded();
}

int freeMemoryIfNeeded(void) {

    // 如果是从节点同时配置了从节点忽略内存配置, 直接返回
    if (server.masterhost && server.repl_slave_ignore_maxmemory) return C_OK;

    // mem_reported 保存了整个 Redis 已经使用的内存
    // mem_tofree 经过计算本次应该释放的内存, 等于当前已经使用的内存 - 用于主从复制的复制缓冲区大小 - 配置的 maxmemory
    // mem_freed 已经释放了多少内存
    size_t mem_reported, mem_tofree, mem_freed;

    long long delta;

    // 从节点个数
    int slaves = listLength(server.slaves);

    // 判断当前的内存状态, 如果足够, 直接返回
    if (getMaxmemoryState(&mem_reported,NULL,&mem_tofree,NULL) == C_OK)
        return C_OK;

    // 如果配置的策略为  noeviction
    if (server.maxmemory_policy == MAXMEMORY_NO_EVICTION)
        goto cant_free;

    mem_freed = 0;

    // 没有达到需要的内存大小, 继续循环
    while (mem_freed dict : db->expires;
                    // 获取字典的数据大小, keys 为当前数据库的 key 的数量
                    if ((keys = dictSize(dict)) != 0) {
                        evictionPoolPopulate(i, dict, db->dict, pool);
                        total_keys += keys;
                    }
                }

                // 没有可以处理的 keys
                if (!total_keys) break;

                // EVPOOL_SIZE =  16
                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[pool[k].dbid].dict, pool[k].key);
                    } else {
                        de = dictFind(server.db[pool[k].dbid].expires, pool[k].key);
                    }

                    // 释放缓存
                    if (pool[k].key != pool[k].cached)
                        sdsfree(pool[k].key);
                    pool[k].key = NULL;
                    pool[k].idle = 0;

                    // 找到的释放对象存在, 先跳出这次循环
                    if (de) {
                        bestkey = dictGetKey(de);
                        break;
                    } else {
                        // 不存在, 进行循环查找
                    }
                }
            }

        } else if (server.maxmemory_policy == MAXMEMORY_ALLKEYS_RANDOM || server.maxmemory_policy == MAXMEMORY_VOLATILE_RANDOM) {
            // random 策略
        }

        // 删除找到的 key
        if (bestkey) {
            
            db = server.db+bestdbid;

            // 将 key 封装为 redisObject 对象
            robj *keyobj = createStringObject(bestkey,sdslen(bestkey));

            // 传播 key 过期信息到主从复制和 AOF 文件
            propagateExpire(db,keyobj,server.lazyfree_lazy_eviction);

            // 获取当前的内存大小
            delta = (long long) zmalloc_used_memory();
            // 同步删除或异步删除 key
            if (server.lazyfree_lazy_eviction) {
                dbAsyncDelete(db,keyobj);
            else
                dbSyncDelete(db,keyobj);
            }

            // 计算本次释放的内存
            delta -= (long long) zmalloc_used_memory();
            mem_freed += delta;
            // 释放创建的 key redisObject 对象
            decrRefCount(keyobj);
            keys_freed++;

            // 如果有从节点, 推送缓冲区的数据
            if (slaves) flushSlavesOutputBuffers();

            // 支持异步清除 同时 清除了 16 个 key
            if (server.lazyfree_lazy_eviction && !(keys_freed % 16)) {
                // 再次判断内存情况, 如果内存足够了
                if (getMaxmemoryState(NULL,NULL,NULL,NULL) == C_OK) {
                    // 更新已经释放的缓存大小 = 需要释放的缓存大小
                    mem_freed = mem_tofree;
                }
            }

        }

        // 本次释放没有处理成功任何一个 key
        if (!keys_freed) {
            goto cant_free; 
        }
    }

    return C_OK;


cant_free:
    // 没有内存可以分配了, 做唯一可以做的一件事: 检查是否有 lazyfree 线程在执行释放内存任务, 有进行等待
    // 知道没有任务或者已有的内存达到了需要释放的内存
    while(bioPendingJobsOfType(BIO_LAZY_FREE)) {
        // 当前的内存达到了现在需要的释放的内存, 结束检查
        if (((mem_reported - zmalloc_used_memory()) + mem_freed) >= mem_tofree)
            break;
        usleep(1000);
    }
    return C_ERR;  

void evictionPoolPopulate(int dbid, dict *sampledict, dict *keydict, struct evictionPoolEntry *pool) {

    int j, k, count;
    // 采样结果数组, 最大容量为 mamemory_samples 的大小
    dictEntry *samples[server.maxmemory_samples];

    // 从 sampledict 字典中采样 server.maxmemory_samples 个 key 存放到 samples, 同时返回总共采样的多少个
    count = dictGetSomeKeys(sampledict,samples,server.maxmemory_samples);

    for (j = 0; j  EVPOOL_CACHED_SDS_SIZE) {
            // 创建一个新的 key 赋值给 pool[k].key
            pool[k].key = sdsdup(key);
        } else {
            // 从 key 中拷贝 klen + 1 的长度到 pool[k].cached
            memcpy(pool[k].cached,key,klen+1);

            sdssetlen(pool[k].cached,klen);
            pool[k].key = pool[k].cached;
        }
        pool[k].idle = idle;
        pool[k].dbid = dbid;
    }
}

unsigned int dictGetSomeKeys(dict *d, dictEntry **des, unsigned int count) {
    unsigned long j; 
    unsigned long tables;
    unsigned long stored = 0, maxsizemask;
    unsigned long maxsteps;

    // 字典中的数据量小于需要的个数, 取的个数变为字典的数据大小
    if (dictSize(d) ht[0].sizemask;
    if (tables > 1 && maxsizemask ht[1].sizemask)
        maxsizemask = d->ht[1].sizemask;

    // 随机获取一个位置
    unsigned long i = random() & maxsizemask;
    unsigned long emptylen = 0;

    // 获取到的个数没达到需要的个数 或者尝试的次数还没达到 0 
    while(stored rehashidx) {
                // 防止获取数据的位置 i 超过第二个字典的大小
                if (i >= d->ht[1].size)
                    i = d->rehashidx;
                else
                    continue;
            }

            // 超过了数组的长度
            if (i >= d->ht[j].size) continue;
            // 获取对应位置的数据
            dictEntry *he = d->ht[j].table[i];

            // 对应的位置为 null
            if (he == NULL) {
                emptylen++;
                // 获取 null 数据的次数大于 5 次 同时 大于需要的过期 key 的个数
                if (emptylen >= 5 && emptylen > count) {
                    // 重新计算获取的位置 i, 重新获取
                    i = random() & maxsizemask;
                    emptylen = 0;
                }
            } else {
                emptylen = 0;
                while (he) {
                    // he 本身是链表, 计算从链表中获取到的个数, 够了结束, 不够就 i+1, 从字典的下一个位置继续获取
                    *des = he;
                    des++;
                    he = he->next;
                    stored++;
                    if (stored == count) return stored;
                }
            }
        }
        i = (i+1) & maxsizemask;
    }
    return stored;
}

typedef struct dictht {
    // 存放节点的数组
    dictEntry **table;
    // HashTable 的大小, 2 的幂次方
    unsigned long size;
    // HashTable 的大小掩码, 用于计算索引值
    unsigned long sizemask;
    // HashTable 中已经使用的节点个数
    unsigned long used;
} dictht;

typedef struct dictEntry {
    // 存储的键值对的 key
    void *key;
    // 存储的键值对的 value
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    // 指向下一个节点
    struct dictEntry *next;
} dictEntry;

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];   // 2 个 HashTable
    long rehashidx; // rehash 的索引
    unsigned long iterators;
} dict;

typedef struct redisDb {
    dict *dict; 
    dict *expires;
    ....
} redisDb;

struct evictionPoolEntry {
    unsigned long long idle;    // 对象空闲时间 (使用的算法是 LFU 则是逆频率)
    sds key;                    // 待淘汰的键值对的 key
    sds cached;                 // 缓存的 key 名称 SDS 对象
    int dbid;                   // 待淘汰键值对的 key 所在的数据库 ID
};