淺談Redis 中的過期刪除策略和記憶體淘汰機制

2022-04-03 13:01:28

前言

Redis 中的 key 設定一個過期時間，在過期時間到的時候，Redis 是如何清除這個 key 的呢？

這來分析下 Redis 中的過期刪除策略和記憶體淘汰機制

Redis 中 key 的過期刪除策略

Redis 中提供了三種過期刪除的策略

1、定時刪除

在設定某個 key 的過期時間同時，我們建立一個定時器，讓定時器在該過期時間到來時，立即執行對其進行刪除的操作。

優點：

通過使用定時器，可以保證過期 key 可以被儘快的刪除，並且釋放過期 key 所佔用的記憶體

缺點：

對 CPU 是不友好的，當過期鍵比較多的時候，刪除過期 key 會佔用相當一部分的 CPU 資源，對伺服器的響應時間和吞吐量造成影響。

2、惰性刪除

惰性刪除，當一個鍵值對過期的時候，只有再次用到這個鍵值對的時候才去檢查刪除這個鍵值對，也就是如果用不著，這個鍵值對就會一直存在。

優點：

對 CPU 是友好的，只有在取出鍵值對的時候才會進行過期檢查，這樣就不會把 CPU 資源花費在其他無關緊要的鍵值對的過期刪除上。

缺點：

如果一些鍵值對永遠不會被再次用到，那麼將不會被刪除，最終會造成記憶體漏失，無用的垃圾資料佔用了大量的資源，但是伺服器卻不能去刪除。

看下原始碼

// 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;
    ...
    /* Delete the key */
    // 刪除 key 
    deleteExpiredKeyAndPropagate(db,key);
    return 1;
}

可以看到每次操作對應的 key 是會檢查 key 是否過期，如果過期則會刪除對應的 key 。

如果過期鍵是主庫建立的，那麼從庫進行檢查是不會進行刪除操作的,只是會根據 key 的過期時間返回過期或者未過期的狀態。

3、定期刪除

定期刪除是對上面兩種刪除策略的一種整合和折中

每個一段時間就對一些 key 進行取樣檢查，檢查是否過期，如果過期就進行刪除

1、取樣一定個數的key，取樣的個數可以進行設定，並將其中過期的 key 全部刪除；

2、如果過期 key 的佔比超過可接受的過期 key 的百分比，則重複刪除的過程，直到過期key的比例降至可接受的過期 key 的百分比以下。

優點：

定期刪除，通過控制定期刪除執行的時長和頻率，可以減少刪除操作對 CPU 的影響，同時也能較少因過期鍵帶來的記憶體的浪費。

缺點：

執行的頻率不太好控制

頻率過快對 CPU 不友好，如果過慢了就會對記憶體不太友好，過期的鍵值對不能及時的被刪除掉

同時如果一個鍵值對過期了，但是沒有被刪除，這時候業務再次獲取到這個鍵值對，那麼就會獲取到被刪除的資料了，這肯定是不合理的。

看下原始碼實現

// 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, /* Rescale from 0 to 9. */
    // 取樣的 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 there is nothing to expire try next DB ASAP. */
            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) {
                        /* 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，如果大於持續進行過期 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;
     ...
}

惰性刪除過程

1、固定的時間執行一次定期刪除；

2、取樣一定個數的key，取樣個數可以進行設定，並將其中過期的key全部刪除；

3、如果過期 key 的佔比超過可接受的過期 key 的百分比，則重複刪除的過程，直到過期key的比例降至可接受的過期 key 的百分比以下；

4、對於從庫建立的過期 key 同樣從庫是不能進行刪除的。

Redis 中過期刪除策略

上面討論的三種策略，都有或多或少的問題。Redis 中實際採用的策略是惰性刪除加定期刪除的組合方式。

組合方式的使用

定期刪除，獲取 CPU 和記憶體的使用平衡，針對過期的 KEY 可能得不到及時的刪除，當 KEY 被再次獲取的時候，通過惰性刪除再做一次過期檢查，來避免業務獲取到過期內容。

從庫是否會髒讀主庫建立的過期鍵

從上面惰性刪除和定期刪除的原始碼閱讀中，我們可以發現，從庫對於主庫的過期鍵是不能主動進行刪除的。如果一個主庫建立的過期鍵值對，已經過期了，主庫在進行定期刪除的時候，沒有及時的刪除掉，這時候從庫請求了這個鍵值對，當執行惰性刪除的時候，因為是主庫建立的鍵值對，這時候是不能在從庫中刪除的，那麼是不是就意味著從庫會讀取到已經過期的資料呢？

答案肯定不是的

how-redis-replication-deals-with-expires-on-keys

How Redis replication deals with expires on keys
Redis expires allow keys to have a limited time to live. Such a feature depends on the ability of an instance to count the time, however Redis slaves correctly replicate keys with expires, even when such keys are altered using Lua scripts.
To implement such a feature Redis cannot rely on the ability of the master and slave to have synchronized clocks, since this is a problem that cannot be solved and would result into race conditions and diverging data sets, so Redis uses three main techniques in order to make the replication of expired keys able to work:
1.Slaves don’t expire keys, instead they wait for masters to expire the keys. When a master expires a key (or evict it because of LRU), it synthesizes a DEL command which is transmitted to all the slaves.
2.However because of master-driven expire, sometimes slaves may still have in memory keys that are already logically expired, since the master was not able to provide the DEL command in time. In order to deal with that the slave uses its logical clock in order to report that a key does not exist only for read operations that don’t violate the consistency of the data set (as new commands from the master will arrive). In this way slaves avoid to report logically expired keys are still existing. In practical terms, an HTML fragments cache that uses slaves to scale will avoid returning items that are already older than the desired time to live.
3.During Lua scripts executions no keys expires are performed. As a Lua script runs, conceptually the time in the master is frozen, so that a given key will either exist or not for all the time the script runs. This prevents keys to expire in the middle of a script, and is needed in order to send the same script to the slave in a way that is guaranteed to have the same effects in the data set.
Once a slave is promoted to a master it will start to expire keys independently, and will not require any help from its old master.

上面是官方檔案中針對這一問題的描述

大概意思就是從節點不會主動刪除過期鍵，從節點會等待主節點觸發鍵過期。當主節點觸發鍵過期時，主節點會同步一個del命令給所有的從節點。

因為是主節點驅動刪除的，所以從節點會獲取到已經過期的鍵值對。從節點需要根據自己原生的邏輯時鐘來判斷減值是否過期，從而實現資料集合的一致性讀操作。

我們知道 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) {
    // 檢查 key 是否過期
    if (!keyIsExpired(db,key)) return 0;

    // 從庫的過期是主庫控制的，是不會進行刪除操作的
    // 上面已經判斷過是否到期了，所以這裡的 key 肯定設計過期的 key ,不過如果是主節點建立的 key 從節點就不刪除，只會返回已經過期了
    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 指令碼執行的過程中不過期
    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;

    /* 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);
}

上面的惰性刪除，對於主節點建立的過期 key ，雖然不能進行刪除的操作，但是可以進行過期時間的判斷，所以如果主庫建立的過期鍵，如果主庫沒有及時進行刪除，這時候從庫可以通過惰性刪除來判斷鍵值對的是否過期，避免讀取到過期的內容。

記憶體淘汰機制

上面我們討論的 Redis 過期策略指的是 Redis 使用那種策略，來刪除已經過期的鍵值對。但是有一些 key以後永遠用不到了，那麼就可能一直不能被刪除掉，還有就是 Redis 中的使用過程中，隨著寫資料的增加，Redis 中的記憶體不夠用了，這時候就需要 Redis 的記憶體淘汰策略了。

Redis 過期策略指的是 Redis 使用那種策略，來刪除已經過期的鍵值對；

Redis 記憶體淘汰機制指的是，當 Redis 執行記憶體已經超過 Redis 設定的最大記憶體之後，將採用什麼策略來刪除符合條件的鍵值對，以此來保障 Redis 高效的執行。

記憶體淘汰觸發的最大記憶體

Redis 中的記憶體只有達到了閥值，才會觸發記憶體淘汰演演算法,這個閥值就是我們設定的最大執行記憶體，在組態檔redis.conf中，通過引數 maxmemory <bytes> 來設定

查詢最大執行記憶體

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

在 64 位元運算系統中，當 maxmemory 為 0 時，表示沒有記憶體大小限制，32位元的系統。

有哪些記憶體淘汰策略

當現有記憶體大於 maxmemory 時，便會觸發redis主動淘汰記憶體方式，通過設定 maxmemory-policy ，有如下幾種淘汰方式：

1、volatile-lru:淘汰所有設定了過期時間的鍵值中最久未使用的鍵值；

2、allkeys-lru:淘汰整個鍵值中最久未使用的鍵值；

3、volatile-random:隨機淘汰設定了過期時間的任意鍵值；

4、allkeys-random:隨機淘汰任意鍵值;

5、volatile-ttl:優先淘汰更早過期的鍵值;

6、noeviction:不淘汰任何資料，當記憶體不足時，新增操作會報錯，Redis 預設記憶體淘汰策略；

其中 allkeys-xxx 表示從所有的鍵值中淘汰資料，而 volatile-xxx 表示從設定了過期鍵的鍵值中淘汰資料。

記憶體淘汰演演算法

除了隨機刪除和不刪除之外，主要有兩種淘汰演演算法：LRU 演演算法和 LFU 演演算法。

LRU

LRU 全稱是Least Recently Used譯為最近最少使用，是一種常用的頁面置換演演算法，選擇最近最久未使用的頁面予以淘汰。

一般 LRU 演演算法的實現基於連結串列結構，連結串列中的元素按照操作順序從前往後排列，最新操作的鍵會被移動到表頭，當需要記憶體淘汰時，只需要刪除連結串列尾部的元素即可。

Redis 使用的是一種近似 LRU 演演算法，目的是為了更好的節約記憶體，它的實現方式是給現有的資料結構新增一個額外的欄位，用於記錄此鍵值的最後一次存取時間，Redis 記憶體淘汰時，會使用隨機取樣的方式來淘汰資料，它是隨機取 5 個值（此值可設定），然後淘汰最久沒有使用的那個。

這裡看下是如何實現的呢

Redis 在原始碼中對於每個鍵值對中的值，會使用一個 redisObject 結構體來儲存指向值的指標，這裡先來看下 redisObject 的結構

// 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; /* 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變數設定為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;
}

同時一個鍵值對被存取的時候記錄的時間也會被更新，當一個鍵值對被存取時，存取操作最終都會呼叫 lookupKey 函數。

// 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;
    }
}

上面我們分別看了，建立和存取一個鍵值對的程式碼，每次操作，redisObject 中記錄的 lru 時間就會被同步的更新

Redis 會判斷當前記憶體的使用情況，如果超過了 maxmemory 設定的值，就會觸發新的記憶體淘汰了

如果記憶體超過了 maxmemory 的值，這時候還需要去計算需要釋放的記憶體量，這個釋放的記憶體大小等於已使用的記憶體量減去 maxmemory。不過，已使用的記憶體量並不包括用於主從複製的複製緩衝區大小。

// 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. */
                // 根據淘汰策略，決定使用全域性雜湊表還是設定了過期時間的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) {
            /* 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;
            }
        }
    ...
    }
}

處理淘汰的資料，Redis 中提供了一個陣列 EvictionPoolLRU，用來儲存待淘汰的候選鍵值對。這個陣列的元素型別是 evictionPoolEntry 結構體，該結構體儲存了待淘汰鍵值對的空閒時間 idle、對應的 key 等資訊。

可以看到上面的上面會選取一定的過期鍵，然後插入到 EvictionPoolLRU 中

dictGetSomeKeys 函數取樣的 key 的數量，是由 redis.conf 中的設定項 maxmemory-samples 決定的，該設定項的預設值是 5

// 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所在的資料庫ID
    int dbid;                   /* Key DB number. */
};

static struct evictionPoolEntry *EvictionPoolLRU;

然後通過 evictionPoolPopulate 函數，進行取樣，然後將取樣資料寫入到 EvictionPoolLRU 中，插入到 EvictionPoolLRU 中的資料是按照空閒時間從小到大進行排好序的

freeMemoryIfNeeded 函數會遍歷一次 EvictionPoolLRU 陣列，從陣列的最後一個 key 開始選擇，如果選到的 key 不是空值，那麼就把它作為最終淘汰的 key。

// 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. */
                // 從陣列最後一個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);
                    }

                    /* Remove the entry from the pool. */
                    // 將當前key從EvictionPoolLRU陣列刪除
                    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. */
                    // 如果當前key對應的鍵值對不為空，選擇當前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);
            ...
        }
    }
    ...
}

每次選中一部分過期的鍵值對，每次淘汰最久沒有使用的那個，如果釋放的記憶體空間還不夠，就會重複的進行取樣，刪除的過程。

LFU

除了 LRU 演演算法，Redis 在 4.0 版本引入了 LFU 演演算法，就是最不頻繁使用（Least Frequently Used，LFU）演演算法。

LRU 演演算法：淘汰最近最少使用的資料，它是根據時間維度來選擇將要淘汰的元素，即刪除掉最長時間沒被存取的元素。

LFU 演演算法：淘汰最不頻繁存取的資料，它是根據頻率維度來選擇將要淘汰的元素，即刪除存取頻率最低的元素。如果兩個元素的存取頻率相同，則淘汰最久沒被存取的元素。

LFU 的基本原理

LFU（Least Frequently Used）演演算法，即最少存取演演算法，根據存取快取的歷史頻率來淘汰資料，核心思想是“如果資料在過去一段時間被存取的次數很少，那麼將來被存取的概率也會很低”。

它是根據頻率維度來選擇將要淘汰的元素，即刪除存取頻率最低的元素。如果兩個元素的存取頻率相同，則淘汰最久沒被存取的元素。也就是說 LFU 淘汰的時候會選擇兩個維度，先比較頻率，選擇存取頻率最小的元素；如果頻率相同，則按時間維度淘汰掉最久遠的那個元素。

LUF 的實現可參見LFU實現詳解

這看下 Redis 中對 LFU 演演算法的實現

1、鍵值對的存取頻率記錄和更新

上面分析 LRU 的時候，聊到了 redisObject，Redis 在原始碼中對於每個鍵值對中的值，會使用一個 redisObject 結構體來儲存指向值的指標。裡面 lru:LRU_BITS 欄位記錄了 LRU 演演算法和 LFU 演演算法需要的時間和計數器。

// 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; /* 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;

當一個鍵值對被建立的時候，如果使用 LFU 演演算法，就會更新 lru 欄位記錄的鍵值對的存取時間戳和存取次數。

// 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;
}

當一個鍵值對被存取時，Redis 會呼叫 lookupKey 函數進行查詢。當 maxmemory-policy 設定使用 LFU 演演算法時，lookupKey 函數會呼叫 updateLFU 函數來更新鍵值對的存取頻率，也就是 lru 變數值，如下所示：

// 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
/* 存取物件時更新 LFU。
 * 首先，如果達到遞減時間，則遞減計數器。
 * 然後對計數器進行對數遞增，並更新存取時間。 */
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;
}

上面的程式碼可以看到，當存取一個鍵值對的時候，首先進行了存取次數的衰減？

LFU 演演算法是根據存取頻率來淘汰資料的，而不只是存取次數。如果存取間隔時間越長，那麼存取頻率就越低。

因為 Redis 是使用 lru 變數中的存取次數來表示存取頻率，所以在每次更新鍵值對的存取頻率時，就會通過 LFUDecrAndReturn 函數對存取次數進行衰減。

LFUDecrAndReturn 函數會呼叫 LFUTimeElapsed 函數（在 evict.c 檔案中），計算距離鍵值對的上一次存取已經過去的時長。這個時長也是以 1 分鐘為精度來計算的。有了距離上次存取的時長後，LFUDecrAndReturn 函數會把這個時長除以 lfu_decay_time 的值，並把結果作為存取次數的衰減大小。

lfu_decay_time 變數值，是由 redis.conf 檔案中的設定項 lfu-decay-time 來決定的。Redis 在初始化時，會通過 initServerConfig 函數來設定 lfu_decay_time 變數的值，預設值為 1。所以，在預設情況下，存取次數的衰減大小就是等於上一次存取距離當前的分鐘數。

衰減之後，再來看下如何進行存取次數的更新

// 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;
}

如果當前存取次數小於255的時候，每次 LFULogIncr 函數會計算一個閾值 p，以及一個取值為 0 到 1 之間的隨機概率值 r。如果概率 r 小於閾值 p，那麼 LFULogIncr 函數才會將存取次數加 1。否則的話，LFULogIncr 函數會返回當前的存取次數，不做更新。

這樣按照一定的概率增加存取頻率，避免了存取次數過大，8 bits 計數器對存取次數的影響。

2、使用 LFU 演演算法淘汰資料

LFU 處理資料淘汰和 LRU 方式差不多，這裡回顧下 LRU 處理資料淘汰的過程

1、呼叫 getMaxmemoryState 函數計算待釋放的記憶體空間；
2、呼叫 evictionPoolPopulate 函數隨機取樣鍵值對，並插入到待淘汰集合 EvictionPoolLRU 中；
3、遍歷待淘汰集合 EvictionPoolLRU，選擇實際被淘汰資料，並刪除。

不同的是，LFU 演演算法在淘汰資料時，在第二步的 evictionPoolPopulate 函數中，使用了不同的方法來計算每個待淘汰鍵值對的空閒時間。

LRU 中 idle 記錄的是它距離上次存取的空閒時間。

LFU 中 idle 記錄的是用 255 減去鍵值對的存取次數。也就是鍵值對存取次數越大，它的 idle 值就越小，反之 idle 值越大。

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

freeMemoryIfNeeded 函數按照 idle 值從大到小，遍歷 EvictionPoolLRU 陣列，選擇實際被淘汰的鍵值對時，它就能選出存取次數小的鍵值對了，也就是把存取頻率低的鍵值對淘汰出去。

具體的原始碼上面 LRU 已經展示了，這裡不在囉嗦了。

為什麼資料刪除後記憶體佔用還是很高

Redis 中的記憶體可能會遇到這樣一種情況，雖然進行了資料的刪除，據量已經不大了，但是使用 top 命令，發現 Redis 還是會佔用大量的記憶體

因為，當資料刪除後，Redis 釋放的記憶體空間會由記憶體分配器管理，並不會立即返回給作業系統。所以，作業系統仍然會記錄著給 Redis 分配了大量記憶體。

但是這些記憶體可能是不連續的，對於不連續的小記憶體塊，雖然是空閒記憶體，但是 Redis 缺不能拿來用，會造成資源的浪費。

為什麼會產生記憶體碎片呢？

記憶體碎片如何產生

1、記憶體分配器的分配策略

記憶體分配器對於記憶體的分配，一般是按固定大小來分配記憶體，而不是完全按照應用程式申請的記憶體空間大小給程式分配。

Redis 可以使用 libc、jemalloc、tcmalloc 多種記憶體分配器來分配記憶體，預設使用 jemalloc。

jemalloc 的分配策略之一，是按照一系列固定的大小劃分記憶體空間，例如8位元組、16位元組、32位元組、48位元組，…, 2KB、4KB、8KB等。當程式申請的記憶體最接近某個固定值時，jemalloc會給它分配相應大小的空間。

這樣的分配方式本身是為了減少分配次數。例如，Redis申請一個20位元組的空間儲存資料，jemalloc 就會分配 32 位元組，此時，如果應用還要寫入 10 位元組的資料，Redis 就不用再向作業系統申請空間了，因為剛才分配的32位元組已經夠用了，這就避免了一次分配操作。

減少了記憶體分配的次數，缺點就是增加了產生記憶體碎片的可能。

2、鍵值對的刪除更改操作

Redis 中鍵值對會被修改和刪除，這會導致空間的擴容和釋放，一方面，如果修改後的鍵值對變大或變小了，就需要佔用額外的空間或者釋放不用的空間。另一方面，刪除的鍵值對就不再需要記憶體空間了，此時，就會把空間釋放出來，形成空閒空間。

Redis中的值刪除的時候，並沒有把記憶體直接釋放，交還給作業系統，而是交給了Redis內部有記憶體管理器。

Redis 中申請記憶體的時候，也是先看自己的記憶體管理器中是否有足夠的記憶體可用。Redis的這種機制，提高了記憶體的使用率，但是會使 Redis 中有部分自己沒在用，卻不釋放的記憶體，導致了記憶體碎片的發生。

碎片率的意義

mem_fragmentation_ratio的不同值，說明不同的情況。

大於1：說明記憶體有碎片，一般在1到1.5之間是正常的；
大於1.5：說明記憶體碎片率比較大，需要考慮是否要進行記憶體碎片清理，要引起重視；
小於1：說明已經開始使用交換記憶體，也就是使用硬碟了，正常的記憶體不夠用了，需要考慮是否要進行記憶體的擴容。

可以使用 INFO memory 命令檢視記憶體碎片率

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 表示的就是記憶體碎片率

mem_fragmentation_ratio = used_memory_rss/ used_memory

used_memory_rss 是作業系統實際分配給 Redis 的實體記憶體空間，裡面就包含了碎片；而 used_memory 是 Redis 為了儲存資料實際申請使用的空間。

如何清理記憶體碎片

Redis伺服器重啟後，Redis會將沒用的記憶體歸還給作業系統，碎片率會降下來；

4.0 版本的 Redis 引入了自動記憶體碎片清理的功能。

自動碎片清理，只要設定了如下的設定，記憶體就會自動清理了。

config set activedefrag yes

不過對於具體什麼時候開始，受下面兩個引數的控制，只要一個不滿足就停止自動清理

active-defrag-ignore-bytes 100mb：表示記憶體碎片的位元組數達到100MB時，開始清理；
active-defrag-threshold-lower 10：表示記憶體碎片空間佔作業系統分配給Redis的總空間比例達到10%時，開始清理。

為了保證清理過程中對 CPU 的影響，還設定了兩個引數，分別用於控制清理操作佔用的CPU時間比例的上、下限，既保證清理工作能正常進行，又避免了降低Redis效能。

active-defrag-cycle-min 25：表示自動清理過程所用CPU時間的比例不低於25%，保證清理能正常開展；
active-defrag-cycle-max 75：表示自動清理過程所用CPU時間的比例不高於75%，一旦超過，就停止清理，從而避免在清理時，大量的記憶體拷貝阻塞Redis，導致響應延遲升高。、

如果你對自動清理的效果不滿意，可以使用如下命令，直接試下手動碎片清理：