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

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

    // 下面的邏輯都是 Key 過期的邏輯處理

    // 當(dāng)前的節(jié)點(diǎn)是從節(jié)點(diǎn), 返回 1, 然后結(jié)束
    // 為了保持主從數(shù)據(jù)的一致, 從節(jié)點(diǎn)不會(huì)主動(dòng)清除數(shù)據(jù), 都是主節(jié)點(diǎn)同步消息在刪除
    if (server.masterhost != NULL) return 1;

    // 已經(jīng)刪除過期鍵個(gè)數(shù) + 1
    server.stat_expiredkeys++;
    // 向從節(jié)點(diǎn)和 AOF 文件傳播 key 過期信息, 清除過期 key
    propagateExpire(db,key,server.lazyfree_lazy_expire);
    // 發(fā)送事件通知
    notifyKeyspaceEvent(NOTIFY_EXPIRED,"expired",key,db->id);

    // lazyfree-lazy-expire 配置參數(shù) (版本 4.0 以上支持), 默認(rèn)為 0
    // 根據(jù)配置, 同步或異步刪除 key (異步刪除: 先將 key 邏輯刪除, 然后在通過后臺(tái)的線程池進(jìn)行真正的空間釋放)
    return server.lazyfree_lazy_expire ? dbAsyncDelete(db,key) : dbSyncDelete(db,key);
}

int keyIsExpired(redisDb *db, robj *key) {
    // 從過期字典中獲取 key 對(duì)應(yīng)的過期時(shí)間, 實(shí)際就是獲取 dictEntity 的 v 中的 s64 值 (dictEntity.v.s64)
    mstime_t when = getExpire(db,key);
    mstime_t now;

    // 沒有過期時(shí)間
    if (when < 0) return 0;

    // redis 在加載數(shù)據(jù)中
    if (server.loading) return 0;
    
    // 獲取當(dāng)前的事件
    if (server.lua_caller) {
        // 有 lua 腳本在執(zhí)行中, 當(dāng)前時(shí)間等于腳本開始執(zhí)行前的時(shí)間
        now = server.lua_time_start;
    } else if (server.fixed_time_expire > 0) {
        // 有緩存時(shí)間, 線使用緩存時(shí)間
        // server.mstime 這個(gè)時(shí)間會(huì)在調(diào)用執(zhí)行命令函數(shù)的 call() 前進(jìn)行更新
        // 這樣可以避免一些批量操作的命令, 比如 RPOPLPUSH 等命令, 這些命令會(huì)執(zhí)行過程中可能多次訪問這個(gè) key
        // 而在多次的訪問過程中, 可能出現(xiàn)上一次訪問未過期, 下次訪問已經(jīng)過期了, 通過這個(gè)緩沖時(shí)間可以解決這個(gè)問題
        now = server.mstime;
    } else {
        // 其他情況, 直接獲取當(dāng)前時(shí)間
        now = mstime();
    }

    // 當(dāng)前時(shí)間是否大于 key 的過期時(shí)間
    return now > when;
}

/**
 * get 命令對(duì)應(yīng)的執(zhí)行函數(shù)
 * 需要的參數(shù)都封裝在 client 對(duì)象中
 */
void getCommand(client *c) {

    // getGenericCommand -> lookupKeyReadOrReply -> lookupKeyRead -> lookupKeyReadWithFlags
    // getGenericCommand 經(jīng)過幾個(gè)函數(shù)最終調(diào)用到 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;
}

/**
 * 過期循環(huán)清除
 * 為了便于理解, 這里對(duì)函數(shù)的邏輯做了一點(diǎn)小調(diào)整和刪除一些非必要的邏輯, 但是整體的邏輯不變

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

    // 靜態(tài)變量, 當(dāng)前處理的數(shù)據(jù)庫(kù)索引
    // 靜態(tài)的效果, 這個(gè)變量執(zhí)行后的值不會(huì)被清空, 每次調(diào)用這個(gè)方法, 是上一次執(zhí)行的值
    // 這樣就可以保證 16 個(gè)數(shù)據(jù)庫(kù), 每次方法執(zhí)行完, 下次進(jìn)來可以執(zhí)行到下一個(gè)數(shù)據(jù)庫(kù), 循環(huán)起來，而不是每次進(jìn)來都從第 0 個(gè)開始
    static unsigned int current_db = 0;

    // 上一次清理是否是因?yàn)闀r(shí)間超時(shí)結(jié)束循環(huán)的, 同樣是靜態(tài)變量
    static int timelimit_exit = 0;    
    // 上一次快速循環(huán)循環(huán)的時(shí)間, 同樣是靜態(tài)變量
    static long long last_fast_cycle = 0;

    // 當(dāng)前時(shí)間
    long long start = ustime(),

    // 本次循環(huán)清除是快速循環(huán), 上一次是時(shí)間超時(shí)獲取 2 次快速循環(huán)的時(shí)間差在 2 毫秒內(nèi), 不執(zhí)行
    if (type == ACTIVE_EXPIRE_CYCLE_FAST) {
        // 上一次循環(huán)是因?yàn)闀r(shí)間超時(shí)結(jié)束的, 本次快速循環(huán)不進(jìn)行
        if (!timelimit_exit) return;
        // 上次快速循環(huán)距離當(dāng)前時(shí)間在 1000 * 2 = 2 毫秒內(nèi), 也不進(jìn)行快速循環(huán)
        if (start < last_fast_cycle + ACTIVE_EXPIRE_CYCLE_FAST_DURATION*2) return;
        last_fast_cycle = start;
    }

    // 計(jì)算循環(huán)的上限毫秒限制 
    // server.hz 默認(rèn)等于 10, ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC 等于 25
    // 1000000 * 25 / 10 / 100 = 25000 單位: 微秒, 即 25 毫秒
    long long timelimit = 1000000*ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC/server.hz/100;

    // ACTIVE_EXPIRE_CYCLE_FAST_DURATION = 1000
    // 如果是快模式, 修改為 1000 微秒, 即 1 毫秒超時(shí)
    if (type == ACTIVE_EXPIRE_CYCLE_FAST)
        timelimit = ACTIVE_EXPIRE_CYCLE_FAST_DURATION;


    // CRON_DBS_PER_CALL = 16, 每次循環(huán)處理的數(shù)據(jù)庫(kù)數(shù)量
    int dbs_per_call = CRON_DBS_PER_CALL;

    // 遍歷當(dāng)前數(shù)據(jù)庫(kù)的次數(shù)
    int iteration = 0;

    // 遍歷循環(huán) 16 個(gè)數(shù)據(jù)庫(kù)
    for (int j = 0; j < dbs_per_call && timelimit_exit == 0; j++) {

        // 清理過期的 key 個(gè)數(shù)
        int expired;

        // 計(jì)算本次處理的數(shù)據(jù)庫(kù)
        redisDb *db = server.db+(current_db % server.dbnum);
        current_db++;

        do {
            // 開始循環(huán)清除當(dāng)前數(shù)據(jù)庫(kù)中過期的 key

            // 遍歷次數(shù) + 1
            iteration++;

            // dictSize 獲取整個(gè)過期字典的已經(jīng)使用大小
            unsigned long num = dictSize(db->expires);

            // num == 0 表示整個(gè)字典沒有數(shù)據(jù), 跳出循環(huán)，處理下一個(gè)數(shù)據(jù)庫(kù)
            if (num == 0) {
                break;
            }

            // 計(jì)算整個(gè)過期字典的總大小
            unsigned long slots = dictSlots(db->expires);

            // DICT_HT_INITIAL_SIZE = 4, 每個(gè)字典初始化時(shí)的默認(rèn)值
            // num > 0, 字典中有數(shù)據(jù)了, slots 大于 4, 表示當(dāng)前的字典擴(kuò)容過了
            // num && slots > DICT_HT_INITIAL_SIZE, 當(dāng)前的字典擴(kuò)容過同時(shí)里面有數(shù)據(jù)
            // num * 100 / slots < 1 計(jì)算當(dāng)前使用的數(shù)據(jù)占整個(gè)字典的百分比是否小于 1%

            // Redis 認(rèn)為, 如果一個(gè)字典中的使用率小于 1%, 花時(shí)間去進(jìn)行清理是一個(gè)昂貴的操作
            // 應(yīng)該停下來，等待更好的時(shí)間再進(jìn)行調(diào)整
            // 所以簡(jiǎn)單理解: 當(dāng)這個(gè)字典中使用的空間小于 1%, 這里跳過了這個(gè)數(shù)據(jù)的處理
            if (num && slots > DICT_HT_INITIAL_SIZE && (num * 100 / slots < 1)) 
                break;

            expired = 0;

            // ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP = 20 
            // 本次從過期字典中獲取多少個(gè) key, 如果字典中的已經(jīng)使用的 key 大于 20, 則只取 20 個(gè), 否則有多少取多少
            if (num > ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP)
                num = ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP;
            
            // 循環(huán) num 次從字典中獲取 key 
            while (num--) {

                dictEntry *de;
                // 從過期字典中隨機(jī)獲取一個(gè) key, 獲取不到, 就停止本次循環(huán)
                if ((de = dictGetRandomKey(db->expires)) == NULL) break;

                // 嘗試釋放這個(gè) key, 如果 key 釋放成功, 過期次數(shù) + 1
                if (activeExpireCycleTryExpire(db,de,now)) expired++;

            }

            // 0xf = 15, iteration 表示遍歷了 15 次
            if ((iteration & 0xf) == 0) {
                // 計(jì)算消耗時(shí)間
                int elapsed = ustime()-start;
                // 消耗時(shí)間超過了限制時(shí)間, 結(jié)束本次循環(huán)
                if (elapsed > timelimit) {
                    // 超過時(shí)間限制標(biāo)識(shí)設(shè)置為 true, 本次循環(huán)清除超時(shí)了, 結(jié)束本次循環(huán)清除
                    timelimit_exit = 1;
                    break;
                }
            }

            // 本次清理的過期 key 超過了 25%, 繼續(xù), 否則結(jié)束
            // ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP = 20
            // 每次抽取的個(gè)數(shù)最大為 20 個(gè), 控制 25%, 20 * 25% = 5 個(gè)
            // 也就是過期的個(gè)數(shù)大于 5 就是大于 25%, (ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP/4 = 5)
        } while (expired > ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP/4);
    }

    // 省略各種分析數(shù)據(jù)的記錄
}

/**
 * Reids 啟動(dòng)時(shí), 向事件輪詢中注冊(cè)的唯一一個(gè)定時(shí)事件(默認(rèn) 100 毫秒執(zhí)行一次), 執(zhí)行的函數(shù)
 */
int serverCron(struct aeEventLoop *eventLoop, long long id, void *clientData) {
    ...
    // 數(shù)據(jù)庫(kù)掃描
    databasesCron();
    ...
}

void databasesCron(void) {

    // 過期功能開啟中, 默認(rèn)為開啟
    if (server.active_expire_enabled) {
        // 主節(jié)點(diǎn)
        if (server.masterhost == NULL) {
            // 慢模式循環(huán)清除
            activeExpireCycle(ACTIVE_EXPIRE_CYCLE_SLOW);
        } else {
            // 從節(jié)點(diǎn)處理
            expireSlaveKeys();
        }
    }

    ...
}

void beforeSleep(struct aeEventLoop *eventLoop) {

    ...

    // 過期功能開啟中同時(shí)為主節(jié)點(diǎn)
    if (server.active_expire_enabled && server.masterhost == NULL)
        // 快模式循環(huán)清除
        activeExpireCycle(ACTIVE_EXPIRE_CYCLE_FAST);

    ...
}

typedef struct redisObject {
    
    /** 
     * 標(biāo)識(shí)這個(gè)對(duì)象的數(shù)據(jù)類型, 常說的 String, Hash, List 等
     */
    unsigned type:4;

    /**
     * 可以理解為數(shù)據(jù)類型的具體實(shí)現(xiàn)類型
     * 比如數(shù)據(jù)類型為 List, 在具體的實(shí)現(xiàn)中可以是 ArrayList LinkedList 等
     */
    unsigned encoding:4;

    /** 
     * LRU_BITS = 24,
     * 一個(gè) 24 位的變量, 表示對(duì)象最后一次被程序訪問的時(shí)間或者訪問的次數(shù), 與內(nèi)存回收有關(guān)
     * 暫時(shí)知道有這個(gè)對(duì)象即可, 后面有分析
     */
    unsigned lru:LRU_BITS;

    /**
     * 被引用的次數(shù), 當(dāng) refcount 為 0 的時(shí)候, 表示該對(duì)象已經(jīng)不被任何對(duì)象引用, 則可以進(jìn)行垃圾回收了
     */
    int refcount;

    /**
     * 一個(gè)指針, 指向具體的數(shù)據(jù)
     */
    void *ptr;

} robj;

/**
 * redisServer 可以看做整個(gè) Redis 運(yùn)行時(shí)的上下文, 保存的數(shù)據(jù), 配置等都在這個(gè)結(jié)構(gòu)體中
 */
struct redisServer {
    unsigned int lruclock = getLRUClock();
}

unsigned int getLRUClock(void) {
    // LRU_CLOCK_RESOLUTION = 1000
    // mstime() 當(dāng)前時(shí)間毫秒, 當(dāng)前時(shí)間的毫秒/LRU_CLOCK_RESOLUTION = 當(dāng)前時(shí)間的毫秒/1000 = 變?yōu)閱挝幻?
    // LRU_CLOCK_MAX = ((1<<LRU_BITS)-1) = 1<<24-1 = redisObject lru 字段的最大值
    // (當(dāng)前的時(shí)間 / 1000) & (1<<24-1) 確保時(shí)間的精度是秒, 同時(shí)不會(huì)超過 24 位的整數(shù)的最多值
    // 整個(gè)全局時(shí)間的進(jìn)度為秒, 2 個(gè)對(duì)象的訪問時(shí)間差如果在秒內(nèi), 得到的是他們的訪問時(shí)間是一樣的
    
    // 得到一個(gè)當(dāng)前時(shí)間的相對(duì)值
    return (mstime()/LRU_CLOCK_RESOLUTION) & LRU_CLOCK_MAX;
}

int serverCron(struct aeEventLoop *eventLoop, long long id, void *clientData) {
    // serverCron 默認(rèn)是 100 毫秒執(zhí)行一次
    unsigned int lruclock = getLRUClock();
    atomicSet(server.lruclock,lruclock);
}

robj *lookupKey(redisDb *db, robj *key, int flags) {
    // 從字典中獲取 key 對(duì)應(yīng)的 dictEntry (字典的設(shè)計(jì)可以看一下后面的附錄)
    dictEntry *de = dictFind(db->dict,key->ptr);
    if (de) {
        // 獲取 key 對(duì)應(yīng)的 dictEntry 的存在
        // 獲取 dictEntry 的 value 也就是 redisObject 對(duì)象
        robj *val = dictGetVal(de);

        if (server.rdb_child_pid == -1 && server.aof_child_pid == -1 && !(flags & LOOKUP_NOTOUCH)) {
            // 沒有在進(jìn)行 RDB 或 AOF 操作, 并且 flags 沒有設(shè)置 LOOKUP_NOTOUCH

            // 淘汰策略設(shè)置的的 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 就是上面定時(shí)任務(wù) serverCron 的執(zhí)行時(shí)間
    // <= 1000 說明 serverCron 的執(zhí)行時(shí)間小于 1 秒, 直接獲取 server.lruclock 的值
    // 如果大于 1000, 就調(diào)用 getLRUClock() 實(shí)時(shí)獲取當(dāng)前的時(shí)間, 因?yàn)轭l率太低了, 會(huì)造成更多的對(duì)象的訪問時(shí)間一樣
    if (1000/server.hz <= LRU_CLOCK_RESOLUTION) {
        atomicGet(server.lruclock,lruclock);
    } else {
        lruclock = getLRUClock();
    }
    return lruclock;
}

unsigned long LFUGetTimeInMinutes(void) {
  // & 65535 保證時(shí)間的范圍在 0 ~ 65535 之間, 不會(huì)超過 16 數(shù)值的大小   
  return (server.unixtime/60) & 65535;
}

uint8_t LFULogIncr(uint8_t counter) {
    // 當(dāng)前的訪問次數(shù)已經(jīng)達(dá)到了最大值了
    if (counter == 255) 
        return 255;

    // 產(chǎn)生一個(gè)隨機(jī)數(shù)
    double r = (double)rand()/RAND_MAX;
    // 獲取一個(gè)基礎(chǔ)值, 當(dāng)前的次數(shù) - 對(duì)象初始化的默認(rèn)次數(shù) (LFU_INIT_VAL = 5)
    double baseval = counter - LFU_INIT_VAL;
    if (baseval < 0) baseval = 0;
    // 1.0 / 基礎(chǔ)值 * server.lfu_log_factor (默認(rèn)值, 10, 可配置) + 1, 得到一個(gè)數(shù)
    double p = 1.0/(baseval*server.lfu_log_factor+1);
    // 得到的數(shù)大于隨機(jī)出來的數(shù), 訪問次數(shù) + 1
    if (r < p) counter++;
    return counter;
}

unsigned long LFUDecrAndReturn(robj *o) {

    // 右移 8 為, 也就是得的了高位的 16 位, 即 ldt, 得到上次記錄的時(shí)間
    unsigned long ldt = o->lru >> 8;
    // 得到當(dāng)前保存的次數(shù)
    unsigned long counter = o->lru & 255;

    // lfu_decay_time 衰減時(shí)間, 默認(rèn) 1, 單位分鐘
    // 如果沒有配置 lfu_decay_time, 則默認(rèn)不進(jìn)行衰減, counter 當(dāng)前是多少就是多少
    // 獲取 2 次訪問的時(shí)間差 / lfu_decay_time, 得到經(jīng)過了多少個(gè)時(shí)間段   
    unsigned long num_periods = server.lfu_decay_time ? LFUTimeElapsed(ldt) / server.lfu_decay_time : 0;
    if (num_periods)
        // 最新的次數(shù) = 當(dāng)前的次數(shù) - 經(jīng)過了多少個(gè)時(shí)間段, 小于 0 時(shí), 設(shè)置為 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)) {
            // 淘汰策略設(shè)置的的 LFU 策略
            if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
                updateLFU(val);
            } else {
                val->lru = LRU_CLOCK();
            }
        }
    } else {
        return NULL;
    }
}

void updateLFU(robj *val) {
    // 通過衰減機(jī)制, 得到最新的 counter
    unsigned long counter = LFUDecrAndReturn(val);
    // 通過隨機(jī)公式, 得到最新的 counter
    counter = LFULogIncr(counter);
    // 將最新的 counter 和 當(dāng)前時(shí)間保存到 lru 字段中
    val->lru = (LFUGetTimeInMinutes()<<8) | counter;
}

int processCommand(client *c) {
    ...

    // 有設(shè)置最大內(nèi)存 同時(shí)當(dāng)前沒有 lua 腳本超時(shí)的情況
    if (server.maxmemory && !server.lua_timedout) {
        // 有必要時(shí), 嘗試釋放內(nèi)存
        int out_of_memory = freeMemoryIfNeededAndSafe() == C_ERR;

        // 內(nèi)存不夠 同時(shí)執(zhí)行的命令是變更命令 或者 當(dāng)前的客戶端開啟了事務(wù), 同時(shí)執(zhí)行的命令不是 exec 
        if (out_of_memory && (c->cmd->flags & CMD_DENYOOM || (c->flags & CLIENT_MULTI && c->cmd->proc != execCommand))) {
            flagTransaction(c);
            // 響應(yīng) -OOM command not allowed when used memory > 'maxmemory'
            addReply(c, shared.oomerr);
            return C_OK;
        }
    }

    ...
}

int freeMemoryIfNeededAndSafe(void) {
    // 當(dāng)前有 lua 腳本執(zhí)行超時(shí)或者真正加載數(shù)據(jù), 返回成功
    if (server.lua_timedout || server.loading) return C_OK;
    // 是否內(nèi)存如果有必要的話
    return freeMemoryIfNeeded();
}

int freeMemoryIfNeeded(void) {

    // 如果是從節(jié)點(diǎn)同時(shí)配置了從節(jié)點(diǎn)忽略內(nèi)存配置, 直接返回
    if (server.masterhost && server.repl_slave_ignore_maxmemory) return C_OK;

    // mem_reported 保存了整個(gè) Redis 已經(jīng)使用的內(nèi)存
    // mem_tofree 經(jīng)過計(jì)算本次應(yīng)該釋放的內(nèi)存, 等于當(dāng)前已經(jīng)使用的內(nèi)存 - 用于主從復(fù)制的復(fù)制緩沖區(qū)大小 - 配置的 maxmemory
    // mem_freed 已經(jīng)釋放了多少內(nèi)存
    size_t mem_reported, mem_tofree, mem_freed;

    long long delta;

    // 從節(jié)點(diǎn)個(gè)數(shù)
    int slaves = listLength(server.slaves);

    // 判斷當(dāng)前的內(nèi)存狀態(tài), 如果足夠, 直接返回
    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;

    // 沒有達(dá)到需要的內(nèi)存大小, 繼續(xù)循環(huán)
    while (mem_freed < mem_tofree) {

        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) {
            // LRU + LFU + TTL 策略

            // 淘汰池
            struct evictionPoolEntry *pool = EvictionPoolLRU;

            while(bestkey == NULL) {
                
                // 遍歷 16 個(gè)數(shù)據(jù)庫(kù)
                for (i = 0; i < server.dbnum; i++) {
                    db = server.db+i;
                    // 根據(jù) volatile 或 all 選擇對(duì)應(yīng)的數(shù)據(jù)字典
                    dict = (server.maxmemory_policy & MAXMEMORY_FLAG_ALLKEYS) ? db->dict : db->expires;
                    // 獲取字典的數(shù)據(jù)大小, keys 為當(dāng)前數(shù)據(jù)庫(kù)的 key 的數(shù)量
                    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;

                    // 從數(shù)據(jù)庫(kù)中獲取對(duì)應(yīng)的節(jié)點(diǎn)
                    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;

                    // 找到的釋放對(duì)象存在, 先跳出這次循環(huán)
                    if (de) {
                        bestkey = dictGetKey(de);
                        break;
                    } else {
                        // 不存在, 進(jìn)行循環(huán)查找
                    }
                }
            }

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

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

            // 將 key 封裝為 redisObject 對(duì)象
            robj *keyobj = createStringObject(bestkey,sdslen(bestkey));

            // 傳播 key 過期信息到主從復(fù)制和 AOF 文件
            propagateExpire(db,keyobj,server.lazyfree_lazy_eviction);

            // 獲取當(dāng)前的內(nèi)存大小
            delta = (long long) zmalloc_used_memory();
            // 同步刪除或異步刪除 key
            if (server.lazyfree_lazy_eviction) {
                dbAsyncDelete(db,keyobj);
            else
                dbSyncDelete(db,keyobj);
            }

            // 計(jì)算本次釋放的內(nèi)存
            delta -= (long long) zmalloc_used_memory();
            mem_freed += delta;
            // 釋放創(chuàng)建的 key redisObject 對(duì)象
            decrRefCount(keyobj);
            keys_freed++;

            // 如果有從節(jié)點(diǎn), 推送緩沖區(qū)的數(shù)據(jù)
            if (slaves) flushSlavesOutputBuffers();

            // 支持異步清除 同時(shí) 清除了 16 個(gè) key
            if (server.lazyfree_lazy_eviction && !(keys_freed % 16)) {
                // 再次判斷內(nèi)存情況, 如果內(nèi)存足夠了
                if (getMaxmemoryState(NULL,NULL,NULL,NULL) == C_OK) {
                    // 更新已經(jīng)釋放的緩存大小 = 需要釋放的緩存大小
                    mem_freed = mem_tofree;
                }
            }

        }

        // 本次釋放沒有處理成功任何一個(gè) key
        if (!keys_freed) {
            goto cant_free; 
        }
    }

    return C_OK;


cant_free:
    // 沒有內(nèi)存可以分配了, 做唯一可以做的一件事: 檢查是否有 lazyfree 線程在執(zhí)行釋放內(nèi)存任務(wù), 有進(jìn)行等待
    // 知道沒有任務(wù)或者已有的內(nèi)存達(dá)到了需要釋放的內(nèi)存
    while(bioPendingJobsOfType(BIO_LAZY_FREE)) {
        // 當(dāng)前的內(nèi)存達(dá)到了現(xiàn)在需要的釋放的內(nèi)存, 結(jié)束檢查
        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;
    // 采樣結(jié)果數(shù)組, 最大容量為 mamemory_samples 的大小
    dictEntry *samples[server.maxmemory_samples];

    // 從 sampledict 字典中采樣 server.maxmemory_samples 個(gè) key 存放到 samples, 同時(shí)返回總共采樣的多少個(gè)
    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);       

        if (server.maxmemory_policy != MAXMEMORY_VOLATILE_TTL) {
            if (sampledict != keydict) de = dictFind(keydict, key);
            o = dictGetVal(de);
        }

        if (server.maxmemory_policy & MAXMEMORY_FLAG_LRU) {
            // LRU 算法
            idle = estimateObjectIdleTime(o);
        } else if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
            // LRU 算法
            idle = 255 - LFUDecrAndReturn(o);
        } else if (server.maxmemory_policy == MAXMEMORY_VOLATILE_TTL) {
            // TTL 算法
            idle = ULLONG_MAX - (long)dictGetVal(de);
        } else {
            serverPanic("Unknown eviction policy in evictionPoolPopulate()");
        }

        k = 0;
        // 從 evictionPoolEntry 淘汰池中找到第一個(gè)閑置時(shí)間比當(dāng)前淘汰 key 大的
        while (k < EVPOOL_SIZE && pool[k].key && pool[k].idle < idle) 
            k++;
        
        if (k == 0 && pool[EVPOOL_SIZE-1].key != NULL) {
            // 如果找到的 key 比淘汰池中閑置時(shí)間最小的 key 還小, 同時(shí)淘汰池沒有空間了, 則跳過這個(gè) key
            continue;
        } else if (k < EVPOOL_SIZE && pool[k].key == NULL) {
            // 插入的位置為空, 直接進(jìn)入到下面的賦值節(jié)點(diǎn)
        } else {
            // 核心就是將找到的位置 k 空出來

            // 最后的位置為空
            if (pool[EVPOOL_SIZE-1].key == NULL) {
                // 將原本 k 位置和后面的數(shù)據(jù)向后移動(dòng) 1 位 
                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 位置前面的數(shù)據(jù)往前移動(dòng) 1 位, 原本的第一位丟棄
                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;
            }
        }

        // 把找到的 key 放到 k 的位置
        int klen = sdslen(key);
        // EVPOOL_CACHED_SDS_SIZE = 255
        if (klen > EVPOOL_CACHED_SDS_SIZE) {
            // 創(chuàng)建一個(gè)新的 key 賦值給 pool[k].key
            pool[k].key = sdsdup(key);
        } else {
            // 從 key 中拷貝 klen + 1 的長(zhǎng)度到 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;

    // 字典中的數(shù)據(jù)量小于需要的個(gè)數(shù), 取的個(gè)數(shù)變?yōu)樽值涞臄?shù)據(jù)大小
    if (dictSize(d) < count) count = dictSize(d);

    // 最大次數(shù) = 次數(shù) * 10
    maxsteps = count*10;

    /* 如果字典在 rehash 中, 嘗試 count 一樣次數(shù)的 rehash */
    for (j = 0; j < count; j++) {
        if (dictIsRehashing(d))
            _dictRehashStep(d);
        else
            break;
    }

    // 獲取總的 HashTable 個(gè)數(shù), 如果在 rehash 中就是 2 個(gè), 否則 1 個(gè)
    tables = dictIsRehashing(d) ? 2 : 1;
    // 獲取數(shù)組大小的掩碼, 用于計(jì)算索引值
    maxsizemask = d->ht[0].sizemask;
    if (tables > 1 && maxsizemask < d->ht[1].sizemask)
        maxsizemask = d->ht[1].sizemask;

    // 隨機(jī)獲取一個(gè)位置
    unsigned long i = random() & maxsizemask;
    unsigned long emptylen = 0;

    // 獲取到的個(gè)數(shù)沒達(dá)到需要的個(gè)數(shù) 或者嘗試的次數(shù)還沒達(dá)到 0 
    while(stored < count && maxsteps--) {
        for (j = 0; j < tables; j++) {
    
            // 如果字典在 rehash 中, 同時(shí)當(dāng)前處理的是第一個(gè)字典, 處理的位置小于 rehash 下次處理的位置, 
            // 則跳過這個(gè)位置, 直接到 rehash 下次處理的位置
            // 因?yàn)榈谝粋€(gè)字典 rehash 下次處理的位置前的數(shù)據(jù)都遷移到第二個(gè)字典中了
            if (tables == 2 && j == 0 && i < (unsigned long) d->rehashidx) {
                // 防止獲取數(shù)據(jù)的位置 i 超過第二個(gè)字典的大小
                if (i >= d->ht[1].size)
                    i = d->rehashidx;
                else
                    continue;
            }

            // 超過了數(shù)組的長(zhǎng)度
            if (i >= d->ht[j].size) continue;
            // 獲取對(duì)應(yīng)位置的數(shù)據(jù)
            dictEntry *he = d->ht[j].table[i];

            // 對(duì)應(yīng)的位置為 null
            if (he == NULL) {
                emptylen++;
                // 獲取 null 數(shù)據(jù)的次數(shù)大于 5 次 同時(shí) 大于需要的過期 key 的個(gè)數(shù)
                if (emptylen >= 5 && emptylen > count) {
                    // 重新計(jì)算獲取的位置 i, 重新獲取
                    i = random() & maxsizemask;
                    emptylen = 0;
                }
            } else {
                emptylen = 0;
                while (he) {
                    // he 本身是鏈表, 計(jì)算從鏈表中獲取到的個(gè)數(shù), 夠了結(jié)束, 不夠就 i+1, 從字典的下一個(gè)位置繼續(xù)獲取
                    *des = he;
                    des++;
                    he = he->next;
                    stored++;
                    if (stored == count) return stored;
                }
            }
        }
        i = (i+1) & maxsizemask;
    }
    return stored;
}

typedef struct dictht {
    // 存放節(jié)點(diǎn)的數(shù)組
    dictEntry **table;
    // HashTable 的大小, 2 的冪次方
    unsigned long size;
    // HashTable 的大小掩碼, 用于計(jì)算索引值
    unsigned long sizemask;
    // HashTable 中已經(jīng)使用的節(jié)點(diǎn)個(gè)數(shù)
    unsigned long used;
} dictht;

typedef struct dictEntry {
    // 存儲(chǔ)的鍵值對(duì)的 key
    void *key;
    // 存儲(chǔ)的鍵值對(duì)的 value
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    // 指向下一個(gè)節(jié)點(diǎn)
    struct dictEntry *next;
} dictEntry;

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

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

struct evictionPoolEntry {
    unsigned long long idle;    // 對(duì)象空閑時(shí)間 (使用的算法是 LFU 則是逆頻率)
    sds key;                    // 待淘汰的鍵值對(duì)的 key
    sds cached;                 // 緩存的 key 名稱 SDS 對(duì)象
    int dbid;                   // 待淘汰鍵值對(duì)的 key 所在的數(shù)據(jù)庫(kù) ID
};