快捷導(dǎo)航

淺談Redis中LFU算法源碼解析

更新時(shí)間：2025年04月10日 09:53:30 作者：百里自來卷

Redis的LFU淘汰算法主要用于?maxmemory-policy?設(shè)置為allkeys-lfu或volatile-lfu時(shí),以最少使用頻率的鍵進(jìn)行淘汰,本文主要介紹了淺談Redis中LFU算法源碼解析,文中通過示例代碼介紹的非常詳細(xì),需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧

Redis 的 LFU（Least Frequently Used，最不經(jīng)常使用）淘汰算法主要用于 maxmemory-policy 設(shè)置為 allkeys-lfu 或 volatile-lfu 時(shí)，以最少使用頻率的鍵進(jìn)行淘汰。其核心實(shí)現(xiàn)涉及到訪問頻率計(jì)數(shù) 和時(shí)間衰減機(jī)制，源碼主要集中在 src/server.c 和 src/evict.c 文件中。

1. LFU 計(jì)數(shù)存儲

Redis 采用 8-bit 的 LRU 字段來存儲訪問頻率計(jì)數(shù)，存儲在 robj 結(jié)構(gòu)體的 lru 字段中：

struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:LRU_BITS; // 用于 LRU/LFU 計(jì)算
    int refcount;
    void *ptr;
};

其中 lru 變量的 8-bit 空間被拆分：

前 6-bit（counter）：用于存儲訪問計(jì)數(shù)，最大值 63。
后 2-bit（clock）：用于時(shí)間衰減計(jì)算。

2. 訪問計(jì)數(shù)的計(jì)算

LFU 計(jì)數(shù)在每次訪問鍵時(shí)都會遞增，但遞增方式不是簡單 +1，而是使用對數(shù)增長方式，避免某些鍵因高訪問量而壟斷：

unsigned long LFUDecrAndReturn(robj *o) {
    unsigned long counter = LFUGetCounter(o);
    if (counter == 0) return 0;
    if (rand() % (counter + 1) == 0) counter--;
    LFUSetCounter(o, counter);
    return counter;
}

計(jì)數(shù)增長時(shí)：

int LFUIncrAndReturn(robj *o) {
    unsigned long counter = LFUGetCounter(o);
    if (counter < 63) {
        if (rand() % (counter + 1) == 0) counter++;
    }
    LFUSetCounter(o, counter);
    return counter;
}

這意味著：

初始時(shí)計(jì)數(shù)增長較快 (1 → 2 → 3…)
計(jì)數(shù)越高，增長概率越低（符合對數(shù)曲線）
這樣可以防止某些高訪問量鍵長期存活。

3. LFU 訪問頻率的衰減

由于有些數(shù)據(jù)可能短期內(nèi)訪問頻繁，但長期不再被訪問，因此 Redis 采用了時(shí)間衰減機(jī)制：

每 1 分鐘遞減一次訪問計(jì)數(shù)。

使用 2-bit 記錄最近訪問的時(shí)間 lfu_clock，每隔 60s 觸發(fā) 衰減：

#define LFU_INIT_VAL 5 // 初始訪問計(jì)數(shù)
unsigned long LFUDecrAndReturn(robj *o) {
    unsigned long counter = LFUGetCounter(o);
    if (counter == 0) return 0;
    if (rand() % (counter + 1) == 0) counter--;
    LFUSetCounter(o, counter);
    return counter;
}

該方法會按照一定概率減少計(jì)數(shù)，確保近期訪問過的鍵不會輕易被淘汰，而長時(shí)間未訪問的鍵會逐步淘汰。

4. 淘汰策略

當(dāng) maxmemory 超出時(shí)，Redis 需要淘汰一部分?jǐn)?shù)據(jù)，LFU 主要執(zhí)行：

遍歷數(shù)據(jù)，找到訪問計(jì)數(shù)最小的鍵。

采用 volatile-lfu 或 allkeys-lfu 進(jìn)行數(shù)據(jù)刪除：

evictionPoolPopulate(dict *sample_dict) {
    // 從字典中隨機(jī)采樣 N 個(gè)鍵
    for (i = 0; i < EVPOOL_SIZE; i++) {
        lfu = LFUGetCounter(entry);
        if (lfu < min_lfu) {
            min_lfu = lfu;
            min_entry = entry;
        }
    }
    // 淘汰訪問次數(shù)最少的
    dictDelete(sample_dict, min_entry);
}

采用近似隨機(jī)采樣，而不是遍歷所有鍵，提高效率。