Redis之過期删除側率

Redis 中 key 的過期删除政策

記憶體碎片如何産生
碎片率的意義
如何清理記憶體碎片
記憶體淘汰觸發的最大記憶體
有哪些記憶體淘汰政策
記憶體淘汰算法
LRU
LFU
1、定時删除
2、惰性删除
3、定期删除
Redis 中過期删除政策
從庫是否會髒讀主庫建立的過期鍵
前言
Redis 中 key 的過期删除政策
記憶體淘汰機制
為什麼資料删除後記憶體占用還是很高
總結
參考

Redis 中 key 的過期删除政策

◆ 前言

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 預設記憶體淘汰政策；

在 Redis 4.0 版本中又新增了 2 種淘汰政策：

volatile-lfu：淘汰所有設定了過期時間的鍵值中，最少使用的鍵值；

allkeys-lfu：淘汰整個鍵值中最少使用的鍵值。

其中 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，導緻響應延遲升高。、

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

memory purge

◆ 總結

1、Redis 中實際采用的政策是惰性删除加定期删除的組合方式；

2、組合的删除政策，其中定期删除，擷取 CPU 和記憶體的使用平衡，針對過期的 KEY 可能得不到及時的删除，當 KEY 被再次擷取的時候，通過惰性删除再做一次過期檢查，來避免業務擷取到過期内容；

3、删除的時候，如果主庫建立的過期鍵，并且過期了沒有被删除，這時候從庫是會讀取到内容，并且是不能進行删除操作，隻能由主庫操作删除，不過從庫會根據自己的邏輯時間判斷這個過期鍵是否過期，進而避免讀取到過期的資料；

4、當 Redis 運作記憶體已經超過 Redis 設定的最大記憶體之後，這時候就會觸發記憶體淘汰機制來清理記憶體，保證 Redis 的正常運作；

5、記憶體淘汰機制一共 6 種淘汰方式；

6、記憶體淘汰機制裡面用到了 LRU 和 LFU；

7、具體的淘汰過程；

1、調用 getMaxmemoryState 函數計算待釋放的記憶體空間；
2、調用 evictionPoolPopulate 函數随機采樣鍵值對，并插入到待淘汰集合 EvictionPoolLRU 中；
3、周遊待淘汰集合 EvictionPoolLRU，選擇實際被淘汰資料，并删除。

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

LRU 中 idle 記錄的是它距離上次通路的空閑時間。

Redis之過期删除側率

Redis 中 key 的過期删除政策

◆ 前言

Redis 中 key 的過期删除政策

◆ 1、定時删除

◆ 2、惰性删除

◆ 3、定期删除

◆ Redis 中過期删除政策

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

◆ 記憶體淘汰機制

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

◆ 有哪些記憶體淘汰政策

◆ 記憶體淘汰算法

◆ LRU

◆ LFU

◆ 1、鍵值對的通路頻率記錄和更新

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

◆ 為什麼資料删除後記憶體占用還是很高

◆ 記憶體碎片如何産生

◆ 碎片率的意義

◆ 如何清理記憶體碎片

◆ 總結

繼續閱讀

django短信驗證碼的後端實作

PHP輔導代做程式設計：CS353 Database System

自學Zabbix3.10.2-事件通知Notifications upon events-Actions報警配置點選傳回：自學zabbix集錦

HDU 5678 ztr loves trees

Redis訂閱了一段時間後訂閱失效了（ redisTemplate.convertAndSend）

2022秋招面試總結（cpp+java+測開）百度測開一面位元組後端一面蝦皮後端一面蝦皮後端二面

拓端tecdat|R語言彈性網絡Elastic Net正則化懲罰回歸模型交叉驗證可視化

二叉樹及其應用--二叉樹建立

資料遷移方法資料遷移原則資料遷移之雙寫方案資料遷移之級聯同步方案

微服務-性能壓測\緩存redis和分布式鎖redisson和SpringCache

Nacos 2.0 更新前後性能對比壓測

Spring資料和Redis

redis叢集資料一緻性_RedisRaft為Redis叢集帶來強大的資料一緻性

supervisor 管理redis 和httpd 環境centos7

Redis簡介一(單機版)發展曆程Redis

詳解STM32單片機的堆棧