快捷導(dǎo)航

淺談Redis中LFU算法源碼解析

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

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

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

1. LFU 計數(shù)存儲

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

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

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

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

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

LFU 計數(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;
}

計數(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ù)增長較快 (1 → 2 → 3…)
計數(shù)越高，增長概率越低（符合對數(shù)曲線）
這樣可以防止某些高訪問量鍵長期存活。

3. LFU 訪問頻率的衰減

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

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

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

#define LFU_INIT_VAL 5 // 初始訪問計數(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;
}

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

4. 淘汰策略

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

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

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

evictionPoolPopulate(dict *sample_dict) {
    // 從字典中隨機采樣 N 個鍵
    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);
}

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