Redis LRU 淘汰策略深度解析：從原理到源碼實現

Redis LRU 淘汰策略深度解析：從原理到源碼實現

在 Redis 作為緩存場景下，內存淘汰策略直接決定內存使用效率。LRU（Least Recently Used，最近最少使用）是最常用策略。本文由淺入深剖析 Redis LRU 具體實現細節與潛在問題。

LRU 算法基礎

核心思想：淘汰最長時間未被訪問的數據。通用實現采用「雙向鏈表 + Hash 表」結構，實現 O(1) 獲取與移動。

簡易 LRUCache 實現（Python）

class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.pre = None
        self.next = None

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.map = {}
        self.head = None
        self.end = None
    
    def get(self, key):
        if key in self.map:
            node = self.map[key]
            self.remove(node)
            self.setHead(node)
            return node.value
        return -1
    
    def set(self, key, value):
        if key in self.map:
            oldNode = self.map[key]
            oldNode.value = value
            self.remove(oldNode)
            self.setHead(oldNode)
        else:
            node = Node(key, value)
            if len(self.map) >= self.capacity:
                self.map.pop(self.end.key)
                self.remove(self.end)
            self.setHead(node)
            self.map[key] = node
    # ... remove, setHead, getAllKeys 等輔助方法

Redis 內部 LRU 實現細節

全局 LRU 時鐘

struct redisServer {
    // ...
    unsigned lruclock:LRU_BITS; /* LRU 淘汰時鐘 */
    // ...
};

#define LRU_CLOCK_RESOLUTION 1000  // 100ms 精度
#define LRU_BITS 24
#define LRU_CLOCK_MAX ((1<
全局時鐘每 100ms 更新一次，最大約 194 天後循環。

對象級 LRU 字段
typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:LRU_BITS;  // 對象最後訪問時間（相對於 server.lruclock）
    int refcount;
    void *ptr;
} robj;

訪問時更新 LRU
robj *lookupKey(redisDb *db, robj *key, int flags) {
    dictEntry *de = dictFind(db->dict, key->ptr);
    if (de) {
        robj *val = dictGetVal(de);
        if (server.rdb_child_pid == -1 && server.aof_child_pid == -1 && !(flags & LOOKUP_NOTOUCH)) {
            if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
                // LFU 邏輯
            } else {
                val->lru = LRU_CLOCK();  // 更新為當前全局時鐘
            }
        }
        return val;
    }
    return NULL;
}

淘汰策略配置與分類
# maxmemory-policy 可選值：
volatile-lru  -> 過期鍵集合中用近似 LRU
allkeys-lru   -> 所有鍵用近似 LRU
volatile-lfu  -> 過期鍵集合中用近似 LFU
allkeys-lfu   -> 所有鍵用近似 LFU
volatile-random -> 過期鍵隨機淘汰
allkeys-random  -> 所有鍵隨機淘汰
volatile-ttl    -> 最近過期鍵優先
noeviction      -> 不淘汰，寫入報錯

兩種淘汰觸發機制

1. 主動淘汰
serverCron 定時任務調用 databasesCron → activeExpireCycle：

每次遍歷最多 16 個 DB
每個 DB 隨機採樣 20 個帶過期時間的鍵
釋放過期鍵內存
單次執行時間限制：timelimit = 1000000 * 25 / hz / 100，默認 hz=10 時為 25ms
若過期鍵比例 ≥ 25%，繼續掃描當前 DB


2. 被動淘汰
寫入時發現內存不足，調用 freeMemoryIfNeeded：

計算實際已用內存
扣除從庫緩衝區、AOF 緩衝區
若仍超限且非 noeviction，按策略淘汰
LRU 策略：隨機採樣 5 個鍵（可配置 maxmemory-samples），淘汰 idle 時間最長者
循環直到內存低於 maxmemory


潛在性能風險與優化建議

大量鍵同時過期：主動掃描耗時可能達 250ms，導致請求超時
內存長期高水位：頻繁觸發被動淘汰，增加寫入延遲
調優建議：

合理設置 hz 參數（1-500），平衡掃描頻率與 CPU 佔用
避免大量鍵設置相同過期時間，增加隨機抖動
監控 expired_keys、evicted_keys 指標
考慮使用 LFU 策略（Redis 4.0+），對頻繁訪問熱數據保護更好




深入理解 LRU 實現機制，能幫助更好地規劃 Redis 內存策略，避免生產環境性能抖動。