redis 是內(nèi)存數(shù)據(jù)庫(kù)沛豌，可以通過 redis.conf 配置 maxmemory瑰钮，限制 redis 內(nèi)存使用量蓬坡。當(dāng) redis 主庫(kù)內(nèi)存超出限制時(shí)离斩，命令處理將會(huì)觸發(fā)數(shù)據(jù)淘汰機(jī)制，淘汰（key-value）數(shù)據(jù)抽高，直至當(dāng)前內(nèi)存使用量小于限制閾值判耕。

此博客將逐步遷移到作者新的博客，可以點(diǎn)擊此處進(jìn)入翘骂。

數(shù)據(jù)淘汰策略概述

redis.conf

redis 申請(qǐng)和回收內(nèi)存基本上都是通過 zmalloc 接口統(tǒng)一管理的，可以通過接口統(tǒng)計(jì) redis 的內(nèi)存使用量碳竟。當(dāng) redis 超出了內(nèi)存的使用限制 maxmemory草丧，服務(wù)在處理命令時(shí)會(huì)觸發(fā) redis 內(nèi)部的數(shù)據(jù)淘汰機(jī)制。淘汰目標(biāo)數(shù)據(jù)一共有兩種：

1. 數(shù)據(jù)庫(kù)所有(key-value)數(shù)據(jù)莹桅。
2. 數(shù)據(jù)庫(kù)所有被設(shè)置了過期時(shí)間的(key-value)數(shù)據(jù)昌执。

aof 緩存，主從同步的積壓緩沖區(qū)這些數(shù)據(jù)是不會(huì)被淘汰的，也沒有計(jì)算在 maxmemory 里面懂拾。

針對(duì)這兩種目標(biāo)數(shù)據(jù)煤禽，它有幾種淘汰策略：

1. 隨機(jī)淘汰。
2. 先淘汰到期或快到期數(shù)據(jù)岖赋。
3. 近似 LRU 算法（最近最少使用）
4. 近似 LFU 算法 （最近使用頻率最少）

關(guān)于近似的 lru 和 lfu 淘汰策略檬果，英文好的朋友，可以去看看 antirez 的這兩篇文章： Using Redis as an LRU cache唐断， Random notes on improving the Redis LRU algorithm 选脊，redis.conf 也有不少闡述。再結(jié)合源碼栗涂，基本能理解它們的實(shí)現(xiàn)思路知牌。

maxmemory 核心數(shù)據(jù)淘汰策略在函數(shù) freeMemoryIfNeeded 中，可以仔細(xì)閱讀這個(gè)函數(shù)的源碼斤程。

配置

當(dāng) redis.conf 配置了 maxmemory角寸，可以根據(jù)配置采用相應(yīng)的數(shù)據(jù)淘汰策略。volatile-xxx 這種類型配置忿墅，都是只淘汰設(shè)置了過期時(shí)間的數(shù)據(jù)扁藕，allkeys-xxx 淘汰數(shù)據(jù)庫(kù)所有數(shù)據(jù)。如果 redis 在你的應(yīng)用場(chǎng)景中疚脐，只是作為緩存亿柑，任何數(shù)據(jù)都可以淘汰，可以設(shè)置 allkeys-xxx棍弄。

#define MAXMEMORY_FLAG_LRU (1<<0)
#define MAXMEMORY_FLAG_LFU (1<<1)
#define MAXMEMORY_FLAG_ALLKEYS (1<<2)

#define MAXMEMORY_VOLATILE_LRU ((0<<8)|MAXMEMORY_FLAG_LRU)
#define MAXMEMORY_VOLATILE_LFU ((1<<8)|MAXMEMORY_FLAG_LFU)
#define MAXMEMORY_VOLATILE_TTL (2<<8)
#define MAXMEMORY_VOLATILE_RANDOM (3<<8)
#define MAXMEMORY_ALLKEYS_LRU ((4<<8)|MAXMEMORY_FLAG_LRU|MAXMEMORY_FLAG_ALLKEYS)
#define MAXMEMORY_ALLKEYS_LFU ((5<<8)|MAXMEMORY_FLAG_LFU|MAXMEMORY_FLAG_ALLKEYS)
#define MAXMEMORY_ALLKEYS_RANDOM ((6<<8)|MAXMEMORY_FLAG_ALLKEYS)
#define MAXMEMORY_NO_EVICTION (7<<8)

數(shù)據(jù)淘汰時(shí)機(jī)

在事件循環(huán)處理命令時(shí)觸發(fā)檢查

int processCommand(client *c) {
    ...
    if (server.maxmemory && !server.lua_timedout) {
        int out_of_memory = freeMemoryIfNeededAndSafe() == C_ERR;
        if (server.current_client == NULL) return C_ERR;

        if (out_of_memory &&
            (c->cmd->flags & CMD_DENYOOM ||
             (c->flags & CLIENT_MULTI &&
              c->cmd->proc != execCommand &&
              c->cmd->proc != discardCommand)))
        {
            flagTransaction(c);
            addReply(c, shared.oomerr);
            return C_OK;
        }
    }
    ...
}

int freeMemoryIfNeededAndSafe(void) {
    if (server.lua_timedout || server.loading) return C_OK;
    return freeMemoryIfNeeded();
}

數(shù)據(jù)淘汰策略

下面從簡(jiǎn)單到復(fù)雜椭员，說說這幾種策略。

不淘汰數(shù)據(jù)（noeviction）

超出內(nèi)存限制笛园，可以淘汰數(shù)據(jù)拆撼，當(dāng)然也可以不使用淘汰策略淘汰數(shù)據(jù)容劳，noeviction 配置允許我們這樣做。服務(wù)允許讀闸度，但禁止大部分寫命令，返回 oomerr 錯(cuò)誤蚜印。只有少數(shù)寫命令可以執(zhí)行莺禁，例如刪除命令 del，hdel窄赋，unlink 這些能降低內(nèi)存使用的寫命令哟冬。

• 32 位系統(tǒng)，如果沒有設(shè)置 maxmemory忆绰，系統(tǒng)默認(rèn)最大值是 3G浩峡，過期淘汰策略是：MAXMEMORY_NO_EVICTION

64 位系統(tǒng)不設(shè)置 maxmemory，是沒有限制的错敢，Linux 以及其它很多系統(tǒng)通過虛擬內(nèi)存管理物理內(nèi)存翰灾，進(jìn)程可以使用超出物理內(nèi)存大小的內(nèi)存，只是那個(gè)時(shí)候稚茅，物理內(nèi)存和磁盤間頻繁地 swap纸淮，導(dǎo)致系統(tǒng)性能下降，對(duì)于 redis 這種高性能內(nèi)存數(shù)據(jù)庫(kù)亚享，這不是一個(gè)友好的體驗(yàn)咽块。

void initServer(void) {
    ...
    if (server.arch_bits == 32 && server.maxmemory == 0) {
        serverLog(LL_WARNING,"Warning: 32 bit instance detected but no memory limit set. Setting 3 GB maxmemory limit with 'noeviction' policy now.");
        server.maxmemory = 3072LL*(1024*1024); /* 3 GB */
        server.maxmemory_policy = MAXMEMORY_NO_EVICTION;
    }
    ...
}

• 服務(wù)禁止大部分寫命令

int processCommand(client *c) {
    ...
    if (server.maxmemory && !server.lua_timedout) {
        // 當(dāng)內(nèi)存超出限制，進(jìn)行回收處理欺税。
        int out_of_memory = freeMemoryIfNeededAndSafe() == C_ERR;
        /* freeMemoryIfNeeded may flush slave output buffers. This may result
         * into a slave, that may be the active client, to be freed. */
        if (server.current_client == NULL) return C_ERR;

        /* It was impossible to free enough memory, and the command the client
         * is trying to execute is denied during OOM conditions or the client
         * is in MULTI/EXEC context? Error. */
        // 內(nèi)存回收后侈沪，還是辦法將內(nèi)存減少到限制以下，那么大部分寫命令將會(huì)被禁止執(zhí)行晚凿。
        if (out_of_memory &&
            (c->cmd->flags & CMD_DENYOOM ||
             (c->flags & CLIENT_MULTI &&
              c->cmd->proc != execCommand &&
              c->cmd->proc != discardCommand)))
        {
            flagTransaction(c);
            addReply(c, shared.oomerr);
            return C_OK;
        }
    }
    ...
}

int freeMemoryIfNeededAndSafe(void) {
    if (server.lua_timedout || server.loading) return C_OK;
    return freeMemoryIfNeeded();
}

int freeMemoryIfNeeded(void) {
    ...
    if (server.maxmemory_policy == MAXMEMORY_NO_EVICTION)
        goto cant_free; /* We need to free memory, but policy forbids. */
    ...
cant_free:
    ...
    return C_ERR;
}

• CMD_DENYOOM 命令屬性（use-memory）

int populateCommandTableParseFlags(struct redisCommand *c, char *strflags) {
    ...
    for (int j = 0; j < argc; j++) {
        ...
        } else if (!strcasecmp(flag,"use-memory")) {
            c->flags |= CMD_DENYOOM;
        }
        ...
    }
    ...
}

struct redisCommand redisCommandTable[] = {
    ...

    {"get",getCommand,2,
     "read-only fast @string",
     0,NULL,1,1,1,0,0,0},

    /* Note that we can't flag set as fast, since it may perform an
     * implicit DEL of a large key. */
    {"set",setCommand,-3,
     "write use-memory @string",
     0,NULL,1,1,1,0,0,0},

    {"setnx",setnxCommand,3,
     "write use-memory fast @string",
     0,NULL,1,1,1,0,0,0},
     ...
    {"del",delCommand,-2,
     "write @keyspace",
     0,NULL,1,-1,1,0,0,0},

    {"unlink",unlinkCommand,-2,
     "write fast @keyspace",
     0,NULL,1,-1,1,0,0,0},
     ...
};

隨機(jī)淘汰

volatile-random亭罪，allkeys-random 這兩個(gè)隨機(jī)淘汰機(jī)制相對(duì)比較簡(jiǎn)單，也比較暴力晃虫，隨機(jī)從庫(kù)中挑選數(shù)據(jù)進(jìn)行淘汰皆撩。

int freeMemoryIfNeeded(void) {
    ...
        /* volatile-random and allkeys-random policy */
        else if (server.maxmemory_policy == MAXMEMORY_ALLKEYS_RANDOM ||
                 server.maxmemory_policy == MAXMEMORY_VOLATILE_RANDOM)
        {
            /* When evicting a random key, we try to evict a key for
             * each DB, so we use the static 'next_db' variable to
             * incrementally visit all DBs. */
            for (i = 0; i < server.dbnum; i++) {
                j = (++next_db) % server.dbnum;
                db = server.db+j;
                dict = (server.maxmemory_policy == MAXMEMORY_ALLKEYS_RANDOM) ?
                        db->dict : db->expires;
                if (dictSize(dict) != 0) {
                    de = dictGetRandomKey(dict);
                    bestkey = dictGetKey(de);
                    bestdbid = j;
                    break;
                }
            }
        }
    ...
}

采樣淘汰

redis 作為一個(gè)數(shù)據(jù)庫(kù)，里面保存了大量數(shù)據(jù)哲银，可以根據(jù)到期時(shí)間（ttl）扛吞，lru 或 lfu 進(jìn)行數(shù)據(jù)淘汰，嚴(yán)格來說荆责，需要維護(hù)一些數(shù)據(jù)結(jié)構(gòu)才能準(zhǔn)確篩選出目標(biāo)數(shù)據(jù)滥比，但是 maxmemory 觸發(fā)的概率比較低，小系統(tǒng)有可能永遠(yuǎn)不會(huì)觸發(fā)做院。為了一個(gè)概率低的場(chǎng)景去維護(hù)一些數(shù)據(jù)結(jié)構(gòu)盲泛，這顯然不是一個(gè)聰明的做法濒持。所以 redis 通過采樣的方法，近似的數(shù)據(jù)淘汰策略寺滚。

采樣方法：遍歷數(shù)據(jù)庫(kù)柑营，每個(gè)數(shù)據(jù)庫(kù)隨機(jī)采集maxmemory_samples個(gè)樣本，放進(jìn)一個(gè)樣本池中（數(shù)組）村视。樣本池中的樣本 idle 值從低到高排序（數(shù)組從左到右存儲(chǔ)）官套，數(shù)據(jù)淘汰策略將會(huì)每次淘汰 idle 最高的那個(gè)數(shù)據(jù)。因?yàn)闃颖境卮笮∈怯邢拗频模?code>EVPOOL_SIZE）蚁孔，所以采集的樣本要根據(jù)自己的 idle 值大小或池中是否有空位來確定是否能成功插入到樣本池中奶赔。如果池中沒有空位或被插入樣本的idle 值都小于池子中的數(shù)據(jù)，那插入將會(huì)失敗杠氢。所以池子中一直存儲(chǔ)著idle最大站刑，最大幾率被淘汰的那些數(shù)據(jù)樣本。

redis 近似算法采樣流程

對(duì)于樣本鼻百，顯然是采樣越多绞旅，篩選目標(biāo)數(shù)據(jù)就越精確。redis 作者根據(jù)實(shí)踐經(jīng)驗(yàn)愕宋，maxmemory_samples 默認(rèn)每次采樣 5 個(gè)已經(jīng)比較高效了玻靡，10 個(gè)就非常接近 LRU 算法效果。例如下圖近似 lru 算法：

圖 1 是正常的 LRU 算法中贝。

1. 淺灰色表示已經(jīng)刪除的鍵囤捻。
2. 深灰色表示沒有被刪除的鍵。
3. 綠色表示新加入的鍵邻寿。

近似采樣算法與原算法比較

• 樣本數(shù)據(jù)池

#define EVPOOL_SIZE 16
#define EVPOOL_CACHED_SDS_SIZE 255
struct evictionPoolEntry {
    unsigned long long idle;    /* Object idle time (inverse frequency for LFU) */
    sds key;                    /* Key name. */
    sds cached;                 /* Cached SDS object for key name. */
    int dbid;                   /* Key DB number. */
};

static struct evictionPoolEntry *EvictionPoolLRU;

void evictionPoolAlloc(void) {
    struct evictionPoolEntry *ep;
    int j;

    ep = zmalloc(sizeof(*ep)*EVPOOL_SIZE);
    for (j = 0; j < EVPOOL_SIZE; j++) {
        ep[j].idle = 0;
        ep[j].key = NULL;
        ep[j].cached = sdsnewlen(NULL,EVPOOL_CACHED_SDS_SIZE);
        ep[j].dbid = 0;
    }
    EvictionPoolLRU = ep;
}

• 采樣淘汰機(jī)制實(shí)現(xiàn)蝎土，掃描數(shù)據(jù)庫(kù)，從樣本池中取出淘汰鍵 bestkey 進(jìn)行淘汰绣否。

int freeMemoryIfNeeded(void) {
    ...
    while (mem_freed < mem_tofree) {
        ...
        // 采樣誊涯，從樣本中選出一個(gè)合適的鍵，進(jìn)行數(shù)據(jù)淘汰蒜撮。
        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;

                // 將采集的鍵放進(jìn) pool 中暴构。
                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) {
                        // 采樣到樣本池中
                        evictionPoolPopulate(i, dict, db->dict, pool);
                        total_keys += keys;
                    }
                }
                if (!total_keys) break; /* No keys to evict. */

                // 從數(shù)組高到低取逾，查找鍵進(jìn)行數(shù)據(jù)淘汰
                for (k = EVPOOL_SIZE-1; k >= 0; k--) {
                    if (pool[k].key == NULL) continue;
                    bestdbid = pool[k].dbid;

                    if (server.maxmemory_policy & MAXMEMORY_FLAG_ALLKEYS) {
                        de = dictFind(server.db[pool[k].dbid].dict,
                            pool[k].key);
                    } else {
                        de = dictFind(server.db[pool[k].dbid].expires,
                            pool[k].key);
                    }

                    /* Remove the entry from the pool. */
                    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. */
                    if (de) {
                        bestkey = dictGetKey(de);
                        break;
                    } else {
                        /* Ghost... Iterate again. */
                    }
                }
            }
        }
        ...
    }
}

• 采樣到樣本池中

void evictionPoolPopulate(int dbid, dict *sampledict, dict *keydict, struct evictionPoolEntry *pool) {
    int j, k, count;
    dictEntry *samples[server.maxmemory_samples];

    // 隨機(jī)采樣多個(gè)數(shù)據(jù)。
    count = dictGetSomeKeys(sampledict,samples,server.maxmemory_samples);
    for (j = 0; j < count; j++) {
        ...
        if (server.maxmemory_policy & MAXMEMORY_FLAG_LRU) {
            // lru 近似算法苹支，淘汰長(zhǎng)時(shí)間沒有使用的數(shù)據(jù)砾隅。
            idle = estimateObjectIdleTime(o);
        } else if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
            // 淘汰使用頻率比較小的數(shù)據(jù)。
            idle = 255-LFUDecrAndReturn(o);
        } else if (server.maxmemory_policy == MAXMEMORY_VOLATILE_TTL) {
            // 淘汰最快過期數(shù)據(jù)债蜜。
            idle = ULLONG_MAX - (long)dictGetVal(de);
        } else {
            serverPanic("Unknown eviction policy in evictionPoolPopulate()");
        }

        // 將采集的 key晴埂，填充到 pool 數(shù)組中去究反。
        // 在 pool 數(shù)組中，尋找合適到位置儒洛。pool[k].key == NULL 或者 idle < pool[k].idle
        k = 0;
        while (k < EVPOOL_SIZE &&
               pool[k].key &&
               pool[k].idle < idle) k++;

        if (k == 0 && pool[EVPOOL_SIZE-1].key != NULL) {
            // pool 已滿精耐，當(dāng)前采樣沒能找到合適位置插入。
            continue;
        } else if (k < EVPOOL_SIZE && pool[k].key == NULL) {
            // 找到合適位置插入晶丘，不需要移動(dòng)數(shù)組其它元素黍氮。
        } else {
            // 找到數(shù)組中間位置，需要移動(dòng)數(shù)據(jù)浅浮。
            if (pool[EVPOOL_SIZE-1].key == NULL) {
                // 數(shù)組還有空間，數(shù)據(jù)從插入位置向右移動(dòng)捷枯。
                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 {
                // 數(shù)組右邊已經(jīng)沒有空間滚秩，那么刪除 idle 最小的元素。
                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;
            }
        }

        // 內(nèi)存的分配和銷毀開銷大淮捆，pool 緩存空間比較小的 key郁油，方便內(nèi)存重復(fù)使用。
        int klen = sdslen(key);
        if (klen > EVPOOL_CACHED_SDS_SIZE) {
            pool[k].key = sdsdup(key);
        } else {
            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;
    }
}

淘汰快到期數(shù)據(jù)（volatile-ttl）

• 數(shù)據(jù)庫(kù) redisDb 用 expires 字典保存了 key 對(duì)應(yīng)的過期時(shí)間攀痊。

typedef struct redisDb {
    dict *dict;                 /* The keyspace for this DB */
    dict *expires;              /* Timeout of keys with a timeout set */
    ...
} redisDb;

• volatile-ttl 淘汰那些設(shè)置了過期時(shí)間且最快到期的數(shù)據(jù)桐腌。隨機(jī)采樣放進(jìn)樣本池，從樣本池中先淘汰idle值最大數(shù)據(jù)苟径。

void evictionPoolPopulate(int dbid, dict *sampledict, dict *keydict, struct evictionPoolEntry *pool) {
    ...
    else if (server.maxmemory_policy == MAXMEMORY_VOLATILE_TTL) {
        // (long)dictGetVal(de) 時(shí)間越小案站，越快到期；idle 越大棘街，越容易從樣本池中淘汰蟆盐。
        idle = ULLONG_MAX - (long)dictGetVal(de);
    }
    ...
}

lru

緩存目的是緩存活躍數(shù)據(jù)，volatile-ttl 淘汰最快到期的數(shù)據(jù)遭殉，存在缺陷：有可能把活躍的數(shù)據(jù)先淘汰了石挂，可以采用 allkeys-lru 和 volatile-lru 策略，根據(jù)當(dāng)前時(shí)間與上一次訪問的時(shí)間間隔险污，間隔越小說明越活躍痹愚。通過采樣，用近似 lru 算法淘汰那些很久沒有使用的數(shù)據(jù)蛔糯。

簡(jiǎn)單的 lru 實(shí)現(xiàn)可以看看我這個(gè)帖子 lru c++ 實(shí)現(xiàn)

• redisObject 成員 lru 保存了一個(gè) 24 bit 的系統(tǒng)訪問數(shù)據(jù)時(shí)間戳拯腮。保存 lru 時(shí)間精度是秒，LRU_CLOCK_MAX 時(shí)間范圍大概 194 天渤闷。

#define LRU_BITS 24
#define LRU_CLOCK_MAX ((1<<LRU_BITS)-1) /* Max value of obj->lru */
#define LRU_CLOCK_RESOLUTION 1000 /* LRU clock resolution in ms */

typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    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;

• 訪問對(duì)應(yīng)數(shù)據(jù)時(shí)疾瓮，更新 lru 時(shí)間。

/* Low level key lookup API, not actually called directly from commands
 * implementations that should instead rely on lookupKeyRead(),
 * lookupKeyWrite() and lookupKeyReadWithFlags(). */
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. */
        // 當(dāng)主進(jìn)程 fork 子進(jìn)程處理數(shù)據(jù)時(shí)飒箭，不要更新狼电。
        // 否則父子進(jìn)程 `copy-on-write` 模式將被破壞蜒灰，產(chǎn)生大量新增內(nèi)存。
        if (!hasActiveChildProcess() && !(flags & LOOKUP_NOTOUCH)){
            if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
                updateLFU(val);
            } else {
                // 更新 lru 時(shí)間
                val->lru = LRU_CLOCK();
            }
        }
        return val;
    } else {
        return NULL;
    }
}

• 近似 lru 淘汰長(zhǎng)時(shí)間沒使用數(shù)據(jù)肩碟。

void evictionPoolPopulate(int dbid, dict *sampledict, dict *keydict, struct evictionPoolEntry *pool) {
    ...
    if (server.maxmemory_policy & MAXMEMORY_FLAG_LRU) {
        // lru 近似算法强窖，淘汰長(zhǎng)時(shí)間沒有使用的數(shù)據(jù)。
        idle = estimateObjectIdleTime(o);
    }
    ...
}

• 返回當(dāng)前時(shí)間與上一次訪問時(shí)間間距削祈。間隔越小翅溺，說明越活躍。（時(shí)間精度毫秒）

時(shí)間間隔

unsigned long long estimateObjectIdleTime(robj *o) {
    unsigned long long lruclock = LRU_CLOCK();
    if (lruclock >= o->lru) {
        return (lruclock - o->lru) * LRU_CLOCK_RESOLUTION;
    } else {
        return (lruclock + (LRU_CLOCK_MAX - o->lru)) *
                    LRU_CLOCK_RESOLUTION;
    }
}

lfu

近似 lru 淘汰策略髓抑，似乎要比前面講的策略都要先進(jìn)咙崎，但是它也是有缺陷的。因?yàn)楦鶕?jù)當(dāng)前時(shí)間與上一次訪問時(shí)間兩個(gè)時(shí)間點(diǎn)間隔來判斷數(shù)據(jù)是否活躍吨拍。也只能反映兩個(gè)時(shí)間點(diǎn)的活躍度褪猛。對(duì)于一段時(shí)間內(nèi)的活躍度是很難反映出來的。

在同一個(gè)時(shí)間段內(nèi)羹饰，B 的訪問頻率明顯要比 A 高伊滋，顯然 B 要比 A 熱度更高。然而 lru 算法會(huì)把 B 數(shù)據(jù)淘汰掉队秩。

~~~~~A~~~~~A~~~~~A~~~~A~~~~~A~~~~A~A~|
~~B~~B~~B~~B~~B~~B~~B~~B~~B~~B~~B~~B~|

所以 redis 作者又引入了一種新的算法笑旺，近似 lfu 算法，反映數(shù)值訪問頻率馍资，也就是數(shù)據(jù)訪問熱度筒主。它重復(fù)利用了 redisObject 結(jié)構(gòu) lru 成員。

typedef struct redisObject {
    ...
    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). */
    ...
} robj;

#           16 bits      8 bits
#      +----------------+--------+
#      + Last decr time | LOG_C  |
#      +----------------+--------+

前 16 bits 用來存儲(chǔ)上一個(gè)訪問衰減時(shí)間（ldt）迷帜，后 8 bits 用來存儲(chǔ)衰減計(jì)數(shù)頻率(counter)物舒。那衰減時(shí)間和計(jì)數(shù)到底有什么用呢？其實(shí)是在一個(gè)時(shí)間段內(nèi)戏锹，訪問頻率越高冠胯，計(jì)數(shù)就越大（計(jì)數(shù)最大值為 255）。我們通過計(jì)數(shù)的大小判斷數(shù)據(jù)的熱度锦针。

• 近似 lfu 淘汰使用頻率比較低的數(shù)據(jù)荠察。

void evictionPoolPopulate(int dbid, dict *sampledict, dict *keydict, struct evictionPoolEntry *pool) {
    ...
    if (server.maxmemory_policy & MAXMEMORY_FLAG_LRU) {
        // 淘汰使用頻率比較小的數(shù)據(jù)。
        idle = 255-LFUDecrAndReturn(o);
    }
    ...
}

• 當(dāng)前時(shí)間與上次訪問的時(shí)間間隔奈搜，時(shí)間精度是分鐘悉盆。

unsigned long LFUTimeElapsed(unsigned long ldt) {
    unsigned long now = LFUGetTimeInMinutes();
    if (now >= ldt) return now-ldt;
    return 65535-ldt+now;
}

unsigned long LFUGetTimeInMinutes(void) {
    return (server.unixtime/60) & 65535;
}

• 衰減計(jì)數(shù)

  LFUTimeElapsed 值越大，counter 就越小馋吗。也就是說焕盟，兩次訪問的時(shí)間間隔越大，計(jì)數(shù)的遞減就越厲害宏粤。這個(gè)遞減速度會(huì)受到衰減時(shí)間因子（lfu_decay_time）影響脚翘∽坡可以在配置文件中調(diào)節(jié)，一般默認(rèn)為 1来农。

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)
        counter = (num_periods > counter) ? 0 : counter - num_periods;
    return counter;
}

• 訪問觸發(fā)頻率更新鞋真，更新 lfu 數(shù)據(jù)

robj *lookupKey(redisDb *db, robj *key, int flags) {
    dictEntry *de = dictFind(db->dict,key->ptr);
    if (de) {
        robj *val = dictGetVal(de);
        if (!hasActiveChildProcess() && !(flags & LOOKUP_NOTOUCH)){
            if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
                // 更新頻率
                updateLFU(val);
            } else {
                val->lru = LRU_CLOCK();
            }
        }
        return val;
    } else {
        return NULL;
    }
}

// 更新 lfu 數(shù)據(jù)
void updateLFU(robj *val) {
    // LFUDecrAndReturn 的時(shí)間精度是分鐘，所以只會(huì)每分鐘更新一次 counter.
    unsigned long counter = LFUDecrAndReturn(val);
    // 實(shí)時(shí)更新當(dāng)前 counter
    counter = LFULogIncr(counter);
    // 保存 lfu 數(shù)據(jù)沃于。
    val->lru = (LFUGetTimeInMinutes()<<8) | counter;
}

• 計(jì)數(shù)器統(tǒng)計(jì)訪問頻率

  這其實(shí)是一個(gè)概率計(jì)算涩咖，當(dāng)數(shù)據(jù)被訪問次數(shù)越多，那么隨機(jī)數(shù)落在某個(gè)數(shù)據(jù)段的概率就越大繁莹。計(jì)數(shù)增加的可能性就越高檩互。 redis 作者添加了控制因子 lfu_log_factor，當(dāng)因子越大咨演，那計(jì)數(shù)增長(zhǎng)速度就越緩慢盾似。

uint8_t LFULogIncr(uint8_t counter) {
    if (counter == 255) return 255;
    double r = (double)rand()/RAND_MAX;
    double baseval = counter - LFU_INIT_VAL;
    if (baseval < 0) baseval = 0;
    double p = 1.0/(baseval*server.lfu_log_factor+1);
    if (r < p) counter++;
    return counter;
}

• 數(shù)據(jù)庫(kù)新增數(shù)據(jù)默認(rèn)計(jì)數(shù)為 LFU_INIT_VAL，這樣不至于剛添加進(jìn)來就被淘汰了雪标。

robj *createEmbeddedStringObject(const char *ptr, size_t len) {
    ...
    if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
        o->lru = (LFUGetTimeInMinutes()<<8) | LFU_INIT_VAL;
    }
    ...
}

下面是 redis 作者壓力測(cè)試得出的 factor 和 counter 測(cè)試數(shù)據(jù)。因子越大溉跃，counter 增長(zhǎng)越緩慢村刨。

測(cè)試數(shù)據(jù)來自 redis.conf

# +--------+------------+------------+------------+------------+------------+
# | factor | 100 hits   | 1000 hits  | 100K hits  | 1M hits    | 10M hits   |
# +--------+------------+------------+------------+------------+------------+
# | 0      | 104        | 255        | 255        | 255        | 255        |
# +--------+------------+------------+------------+------------+------------+
# | 1      | 18         | 49         | 255        | 255        | 255        |
# +--------+------------+------------+------------+------------+------------+
# | 10     | 10         | 18         | 142        | 255        | 255        |
# +--------+------------+------------+------------+------------+------------+
# | 100    | 8          | 11         | 49         | 143        | 255        |
# +--------+------------+------------+------------+------------+------------+
#
# NOTE: The above table was obtained by running the following commands:
#
#   redis-benchmark -n 1000000 incr foo
#   redis-cli object freq foo

總結(jié)

• maxmemory 淘汰數(shù)據(jù)機(jī)制，主要淘汰兩種目標(biāo)數(shù)據(jù)：整個(gè)數(shù)據(jù)庫(kù)數(shù)據(jù)和設(shè)置了過期時(shí)間的數(shù)據(jù)撰茎。

• maxmemory 淘汰策略嵌牺，有：不使用淘汰策略淘汰數(shù)據(jù)，隨機(jī)淘汰數(shù)據(jù)龄糊，采樣的近似算法 ttl逆粹，lru，lfu炫惩。

• redis 版本從 2.x 到 6.x僻弹，一直不停地改進(jìn)迭代，redis 作者精益求精的精神值得我們學(xué)習(xí)他嚷。

• 采樣近似淘汰策略蹋绽，巧妙避免了維護(hù)額外的數(shù)據(jù)結(jié)構(gòu)，達(dá)到差不多的效果筋蓖，這個(gè)思路獨(dú)具匠心卸耘。

• 采樣算法，根據(jù)樣本的 idle 值進(jìn)行數(shù)據(jù)淘汰粘咖，所以當(dāng)我們采用一種采樣算法時(shí)蚣抗，不要密集地設(shè)置大量相似的 idle 數(shù)據(jù)，否則效率也是很低的瓮下。

• maxmemory 設(shè)置其實(shí)是一個(gè)學(xué)問翰铡，到底應(yīng)該設(shè)置多少钝域，才比較合理。很多人建議是物理內(nèi)存大小的一半两蟀，原因如下：

  1. 數(shù)據(jù)持久化過程中网梢，redis 會(huì) fork 子進(jìn)程，在 linux 系統(tǒng)中雖然父子進(jìn)程有 'copy-on-write' 模式赂毯，redis 也盡量避免子進(jìn)程工作過程中修改數(shù)據(jù)战虏，子進(jìn)程部分操作會(huì)使用內(nèi)存，例如寫 rdb 文件党涕。
  2. maxmemory 限制的內(nèi)存并不包括 aof 緩存和主從同步積壓緩沖區(qū)部分內(nèi)存烦感。
  3. redis 集群數(shù)據(jù)同步機(jī)制，全量同步數(shù)據(jù)膛堤，某些場(chǎng)景也要也要占用不少內(nèi)存手趣。
  4. 我們的機(jī)器很多時(shí)候不是只跑 redis 進(jìn)程的，系統(tǒng)其它進(jìn)程也要使用內(nèi)存肥荔。

• maxmemory 雖然有眾多的處理策略绿渣，然而超過閾值運(yùn)行，這是不健康的燕耿，生產(chǎn)環(huán)境應(yīng)該實(shí)時(shí)監(jiān)控程序運(yùn)行的健康狀況中符。

• redis 經(jīng)常作為緩存使用，其實(shí)它也有持久化誉帅，可以存儲(chǔ)數(shù)據(jù)淀散。redis 作為緩存和數(shù)據(jù)庫(kù)一般都是交叉使用，沒有明確的界限蚜锨，所以不建議設(shè)置 allkeys-xxx 全局淘汰數(shù)據(jù)的策略档插。

• 當(dāng)redis 內(nèi)存到達(dá) maxmemory，觸發(fā)了數(shù)據(jù)淘汰亚再，但是一頓操作后郭膛，內(nèi)存始終無法成功降到閾值以下，那么 redis 主進(jìn)程將會(huì)進(jìn)入睡眠等待针余。這種問題是隱性的饲鄙，很難查出來。新手很容易犯錯(cuò)誤圆雁，經(jīng)常把 redis 當(dāng)做數(shù)據(jù)庫(kù)使用忍级，并發(fā)量高的系統(tǒng)，一段時(shí)間就跑滿內(nèi)存了伪朽，沒經(jīng)驗(yàn)的運(yùn)維肯定第一時(shí)間想到切換到好點(diǎn)的機(jī)器解決問題轴咱。

  int freeMemoryIfNeeded(void) {
      ...
  cant_free:
      // 如果已經(jīng)沒有合適的鍵進(jìn)行回收了，而且內(nèi)存還沒降到 maxmemory 以下，
      // 那么需要看看回收線程中是否還有數(shù)據(jù)需要進(jìn)行回收朴肺，通過 sleep 主線程等待回收線程處理窖剑。
      while(bioPendingJobsOfType(BIO_LAZY_FREE)) {
          if (((mem_reported - zmalloc_used_memory()) + mem_freed) >= mem_tofree)
              break;
          usleep(1000);
      }
      return C_ERR;
  }
  

參考

• [redis 源碼走讀] 字典(dict)
• Using Redis as an LRU cache
• Random notes on improving the Redis LRU algorithm
• Redis的緩存淘汰策略LRU與LFU
• redis 過期策略及內(nèi)存回收機(jī)制

• 更精彩內(nèi)容，可以關(guān)注我的博客：wenfh2020.com