// https://github.com/redis/redis/blob/6.2/src/db.c#L1541
// 當(dāng)訪問到 key 的時候，會調(diào)用這個函數(shù)，因為有的 key 雖然已經(jīng)過期了，但是還可能存在于內(nèi)存中

// key 仍然有效，函數(shù)返回值為0，否則，如果 key 過期，函數(shù)返回1。
int expireIfNeeded(redisDb *db, robj *key) {
    // 沒有過期
    if (!keyIsExpired(db,key)) return 0;

    // 從庫的過期是主庫控制的，是不會進行刪除操作的
    // 上面已經(jīng)判斷過是否到期了，所以這里的 key 肯定是過期的 key ,不過如果是主節(jié)點創(chuàng)建的 key 從節(jié)點就不刪除，只會返回已經(jīng)過期了
    if (server.masterhost != NULL) return 1;
    ...
    /* Delete the key */
    // 刪除 key 
    deleteExpiredKeyAndPropagate(db,key);
    return 1;
}

// https://github.com/redis/redis/blob/6.2/src/server.c#L1853
// 這個函數(shù)處理我們需要在Redis數(shù)據(jù)庫中增量執(zhí)行的“后臺”操作，例如活動鍵過期，調(diào)整大小，重哈希。
void databasesCron(void) {
    // 通過隨機抽樣來過期
    // 這里區(qū)分了主節(jié)點和從節(jié)點的處理
    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) {
    // 根據(jù)配置的超時工作調(diào)整運行參數(shù)。默認(rèn)工作量為1，最大可配置工作量為10
    unsigned long
    effort = server.active_expire_effort-1, /* Rescale from 0 to 9. */
    // 采樣的 key 的數(shù)量
    config_keys_per_loop = ACTIVE_EXPIRE_CYCLE_KEYS_PER_LOOP +
                           ACTIVE_EXPIRE_CYCLE_KEYS_PER_LOOP/4*effort,
    // 占比CPU時間，默認(rèn)是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;
    ...
    //慢速定期刪除的執(zhí)行時長
    timelimit = config_cycle_slow_time_perc*1000000/server.hz/100;
    timelimit_exit = 0;
    ...
    // 在 key 過期時積累一些全局統(tǒng)計信息，以便了解邏輯上已經(jīng)過期但仍存在于數(shù)據(jù)庫中的 key 的數(shù)量
    long total_sampled = 0;
    long total_expired = 0;

    for (j = 0; j < dbs_per_call && timelimit_exit == 0; j++) {
        ...
        // 如果超過 config_cycle_acceptable_stale 的key過期了，則重復(fù)刪除的過程，直到過期key的比例降至 config_cycle_acceptable_stale 以下。  
        // 存儲在 config_cycle_acceptable_stale 中的百分比不是固定的，而是取決于Redis配置的“expire efforce”  
        do {
            /* If there is nothing to expire try next DB ASAP. */
            if ((num = dictSize(db->expires)) == 0) {
                db->avg_ttl = 0;
                break;
            }
            ...
            // 采樣的 key 的數(shù)量 
            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) {
                        /* Get the next entry now since this entry may get
                         * deleted. */
                        dictEntry *e = de;
                        de = de->next;

                        ttl = dictGetSignedIntegerVal(e)-now;
                        // 過期檢查，并對過期鍵進行刪除
                        if (activeExpireCycleTryExpire(db,e,now)) expired++;
                        ...
                    }
                }
                db->expires_cursor++;
            }
         ...
        // 判斷過期 key 的占比是否大于 config_cycle_acceptable_stale，如果大于持續(xù)進行過期 key 的刪除
        } while (sampled == 0 ||
                 (expired*100/sampled) > config_cycle_acceptable_stale);
    }
    ...
}

// 檢查刪除由從節(jié)點創(chuàng)建的有過期的時間的 key 
void expireSlaveKeys(void) {
    // 從主庫同步的 key，過期時間由主庫維護，主庫同步 DEL 操作到從庫。
    // 從庫如果是 READ-WRITE 模式，就可以繼續(xù)寫入數(shù)據(jù)。從庫自己寫入的數(shù)據(jù)就需要自己來維護其過期操作。
    if (slaveKeysWithExpire == NULL ||
        dictSize(slaveKeysWithExpire) == 0) return;
     ...
}

// https://github.com/redis/redis/blob/6.2/src/db.c#L1541
// 當(dāng)訪問到 key 的時候，會調(diào)用這個函數(shù)，因為有的 key 雖然已經(jīng)過期了，但是還可能存在于內(nèi)存中

// key 仍然有效，函數(shù)返回值為0，否則，如果 key 過期，函數(shù)返回1。
int expireIfNeeded(redisDb *db, robj *key) {
    // 檢查 key 是否過期
    if (!keyIsExpired(db,key)) return 0;

    // 從庫的過期是主庫控制的，是不會進行刪除操作的
    // 上面已經(jīng)判斷過是否到期了，所以這里的 key 肯定設(shè)計過期的 key ,不過如果是主節(jié)點創(chuàng)建的 key 從節(jié)點就不刪除，只會返回已經(jīng)過期了
    if (server.masterhost != NULL) return 1;
    ...
    /* Delete the key */
    // 刪除 key 
    deleteExpiredKeyAndPropagate(db,key);
    return 1;
}

// https://github.com/redis/redis/blob/6.2/src/db.c#L1485
/* Check if the key is expired. */
int keyIsExpired(redisDb *db, robj *key) {
    // 過期時間
    mstime_t when = getExpire(db,key);
    mstime_t now;

    // 沒有過期
    if (when < 0) return 0; /* No expire for this key */

    /* Don't expire anything while loading. It will be done later. */
    if (server.loading) return 0;

    // lua 腳本執(zhí)行的過程中不過期
    if (server.lua_caller) {
        now = server.lua_time_snapshot;
    }
    // 如果我們正在執(zhí)行一個命令，我們?nèi)匀幌Ｍ褂靡粋€不會改變的引用時間:在這種情況下，我們只使用緩存的時間，我們在每次調(diào)用call()函數(shù)之前更新。
    // 這樣我們就避免了RPOPLPUSH之類的命令，這些命令可能會重新打開相同的鍵多次，如果下次調(diào)用會看到鍵過期，則會使已經(jīng)打開的對象在下次調(diào)用中失效，而第一次調(diào)用沒有。
    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;

    /* No expire? return ASAP */
    if (dictSize(db->expires) == 0 ||
       (de = dictFind(db->expires,key->ptr)) == NULL) return -1;

    /* The entry was found in the expire dict, this means it should also
     * be present in the main dict (safety check). */
    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數(shù)據(jù) (低 8 bits 作為計數(shù)器,用 24 bits 中的高 16 bits，記錄訪問的時間戳)
    unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
                            * LFU data (least significant 8 bits frequency
                            * and most significant 16 bits access time). */
    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變量設(shè)置為LFU的計數(shù)值
    if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
        o->lru = (LFUGetTimeInMinutes()<<8) | LFU_INIT_VAL;
    } else {
    // 如果是 lru 
    // 調(diào)用LRU_CLOCK函數(shù)獲取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);

        /* Update the access time for the ageing algorithm.
         * Don't do it if we have a saving child, as this will trigger
         * a copy on write madness. */
        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;

                /* We don't want to make local-db choices when expiring keys,
                 * so to start populate the eviction pool sampling keys from
                 * every DB. */
                // 根據(jù)淘汰策略，決定使用全局哈希表還是設(shè)置了過期時間的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函數(shù)，同時將全局哈希表也傳給evictionPoolPopulate函數(shù)
                        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) {
            /* Can't insert if the element is < the worst element we have
             * and there are no empty buckets. */
            continue;
        } else if (k < EVPOOL_SIZE && pool[k].key == NULL) {
            /* Inserting into empty position. No setup needed before insert. */
        } else {
            /* Inserting in the middle. Now k points to the first element
             * greater than the element to insert.  */
            if (pool[EVPOOL_SIZE-1].key == NULL) {
                /* Free space on the right? Insert at k shifting
                 * all the elements from k to end to the right. */

                /* Save SDS before overwriting. */
                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 {
                /* No free space on right? Insert at k-1 */
                k--;
                /* Shift all elements on the left of k (included) to the
                 * left, so we discard the element with smaller idle time. */
                sds cached = pool[0].cached; /* Save SDS before overwriting. */
                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;    /* Object idle time (inverse frequency for LFU) */
    // 待淘汰的鍵值對的key
    sds key;                    /* Key name. */
    // 緩存的SDS對象
    sds cached;                 /* Cached SDS object for key name. */
    // 待淘汰鍵值對的key所在的數(shù)據(jù)庫ID
    int dbid;                   /* Key DB number. */
};

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; /* May be negative */
    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;
                ...
                /* Go backward from best to worst element to evict. */
                // 從數(shù)組最后一個key開始查找
                for (k = EVPOOL_SIZE-1; k >= 0; k--) {
                    // 當(dāng)前key為空值，則查找下一個key
                    if (pool[k].key == NULL) continue;
                    bestdbid = pool[k].dbid;

                    // 從全局哈希表或是expire哈希表中，獲取當(dāng)前key對應(yīng)的鍵值對；
                    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);
                    }

                    /* Remove the entry from the pool. */
                    // 將當(dāng)前key從EvictionPoolLRU數(shù)組刪除
                    if (pool[k].key != pool[k].cached)
                        sdsfree(pool[k].key);
                    pool[k].key = NULL;
                    pool[k].idle = 0;

                    /* If the key exists, is our pick. Otherwise it is
                     * a ghost and we need to try the next element. */
                    // 如果當(dāng)前key對應(yīng)的鍵值對不為空，選擇當(dāng)前key為被淘汰的key
                    if (de) {
                        bestkey = dictGetKey(de);
                        break;
                    } else {
                        /* Ghost... Iterate again. */
                    }
                }
            }
        }
        ...
        /* Finally remove the selected key. */
        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數(shù)據(jù) (低 8 bits 作為計數(shù)器,用 24 bits 中的高 16 bits，記錄訪問的時間戳)
    unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
                            * LFU data (least significant 8 bits frequency
                            * and most significant 16 bits access time). */
    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時間戳和訪問次數(shù)5
    if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
        o->lru = (LFUGetTimeInMinutes()<<8) | LFU_INIT_VAL;
    } else {
    // 如果是 lru 
    // 調(diào)用LRU_CLOCK函數(shù)獲取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算法時，調(diào)用updateLFU函數(shù)更新訪問頻率
        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
/* 訪問對象時更新 LFU。
 * 首先，如果達到遞減時間，則遞減計數(shù)器。
 * 然后對計數(shù)器進行對數(shù)遞增，并更新訪問時間。 */
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) {
    // 獲取當(dāng)前鍵值對的上一次訪問時間
    unsigned long ldt = o->lru >> 8;
    // 獲取當(dāng)前的訪問次數(shù)
    unsigned long counter = o->lru & 255;
    unsigned long num_periods = server.lfu_decay_time ? LFUTimeElapsed(ldt) / server.lfu_decay_time : 0;
    if (num_periods)
        // 如果衰減大小小于當(dāng)前訪問次數(shù)，那么，衰減后的訪問次數(shù)是當(dāng)前訪問次數(shù)減去衰減大??；否則，衰減后的訪問次數(shù)等于0
        counter = (num_periods > counter) ? 0 : counter - num_periods;
    // 如果衰減大小為0，則返回原來的訪問次數(shù)
    return counter;
}

// https://github.com/redis/redis/blob/6.2/src/evict.c#L298
uint8_t LFULogIncr(uint8_t counter) {
    // 等于255，不在進行次數(shù)的更新
    if (counter == 255) return 255;
    // 計算一個隨機數(shù)
    double r = (double)rand()/RAND_MAX;
    // 計算當(dāng)前訪問次數(shù)和初始值的差值
    double baseval = counter - LFU_INIT_VAL;
    if (baseval < 0) baseval = 0;
    // 根據(jù)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