深入解析 Redis 的 LRU 與 LFU 算法實現

作者：vivo 互聯網服務器團隊 - Luo Jianxin

重點介紹了 Redis 的 LRU 與 LFU 算法實現，並分析總結了兩種算法的實現效果以及存在的問題。

一、前言

Redis 是一款基於內存的高性能 NoSQL 數據庫，數據都緩存在內存裏，這使得 Redis 可以每秒輕鬆地處理數萬的讀寫請求。

相對於磁盤的容量，內存的空間一般都是有限的，爲了避免 Redis 耗盡宿主機的內存空間，Redis 內部實現了一套複雜的緩存淘汰策略來管控內存使用量。

Redis 4.0 版本開始就提供了 8 種內存淘汰策略，其中 4 種都是基於 LRU 或 LFU 算法實現的，本文就這兩種算法的 Redis 實現進行了詳細的介紹，並闡述其優劣特性。

二、Redis 的 LRU 實現

在介紹 Redis LRU 算法實現之前，我們先簡單介紹一下原生的 LRU 算法。

2.1 LRU 算法原理

LRU（The Least Recently Used）是最經典的一款緩存淘汰算法，其原理是：如果一個數據在最近一段時間沒有被訪問到，那麼在將來它被訪問的可能性也很低，當數據所佔據的空間達到一定閾值時，這個最少被訪問的數據將被淘汰掉。

如今，LRU 算法廣泛應用在諸多系統內，例如 Linux 內核頁表交換，MySQL Buffer Pool 緩存頁替換，以及 Redis 數據淘汰策略。

以下是一個 LRU 算法示意圖：

圖片

向一個緩存空間依次插入三個數據 A/B/C，填滿了緩存空間；
讀取數據 A 一次，按照訪問時間排序，數據 A 被移動到緩存頭部；
插入數據 D 的時候，由於緩存空間已滿，觸發了 LRU 的淘汰策略，數據 B 被移出，緩存空間只保留了 D/A/C。

一般而言，LRU 算法的數據結構不會如示意圖那樣，僅使用簡單的隊列或鏈表去緩存數據，而是會採用 Hash 表 + 雙向鏈表的結構，利用 Hash 表確保數據查找的時間複雜度是 O(1)，雙向鏈表又可以使數據插入 / 刪除等操作也是 O(1)。

如果你很熟悉 Redis 的數據類型，你會發現這個 LRU 的數據結構與 ZSET 類型 OBJ_ENCODING

_SKIPLIST 編碼結構相似，只是 LRU 數據排序方式更簡單一些。

2.2 Redis LRU 算法實現

按照官方文檔的介紹，Redis 所實現的是一種近似的 LRU 算法，每次隨機選取一批數據進行 LRU 淘汰，而不是針對所有的數據，通過犧牲部分準確率來提高 LRU 算法的執行效率。

Redis 內部只使用 Hash 表緩存了數據，並沒有創建一個專門針對 LRU 算法的雙向鏈表，之所以這樣處理也是因爲以下幾個原因：

篩選規則，Redis 是隨機抽取一批數據去按照淘汰策略排序，不再需要對所有數據排序；
性能問題，每次數據訪問都可能涉及數據移位，性能會有少許損失；
內存問題，Redis 對內存的使用一向很 “摳門”，數據結構都很精簡，儘量不使用複雜的數據結構管理數據；
策略配置，如果線上 Redis 實例動態修改淘汰策略會觸發全部數據的結構性改變，這個 Redis 系統無法承受的。

redisObject 是 Redis 核心的底層數據結構，成員變量 lru 字段用於記錄了此 key 最近一次被訪問的 LRU 時鐘 (server.lruclock)，每次 Key 被訪問或修改都會引起 lru 字段的更新。

#define LRU_BITS 24
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;

默認的 LRU 時鐘單位是秒，可以修改 LRU_CLOCK_RESOLUTION 宏來改變單位，LRU 時鐘更新的頻率也和 server.hz 參數有關。

unsigned int LRU_CLOCK(void) {
    unsigned int lruclock;
    if (1000/server.hz <= LRU_CLOCK_RESOLUTION) {
        atomicGet(server.lruclock,lruclock);
    } else {
        lruclock = getLRUClock();
    }
    return lruclock;
}

由於 lru 字段僅佔用了 24bit 的空間，按秒爲單位也只能存儲 194 天，所以可能會出現一個意想不到的結果，即間隔 194 天訪問 Key 後標記的時間戳一樣，Redis LRU 淘汰策略局部失效。

2.3 LRU 算法缺陷

LRU 算法僅關注數據的訪問時間或訪問順序，忽略了訪問次數的價值，在淘汰數據過程中可能會淘汰掉熱點數據。

如上圖所示，時間軸自左向右，數據 A/B/C 在同一段時間內被分別訪問的數次。數據 C 是最近一次訪問的數據，按照 LRU 算法排列數據的熱度是 C>B>A，而數據的真實熱度是 B>A>C。

這個是 LRU 算法的原理性問題，自然也會在 Redis 近似 LRU 算法中呈現，爲了解決這個問題衍生出來 LFU 算法。

三、Redis 的 LFU 實現

3.1 LFU 算法原理

LFU（Least frequently used）即最不頻繁訪問，其原理是：如果一個數據在近期被高頻率地訪問，那麼在將來它被再訪問的概率也會很高，而訪問頻率較低的數據將來很大概率不會再使用。

很多人看到上面的描述，會認爲 LFU 算法主要是比較數據的訪問次數，畢竟訪問次數多了自然訪問頻率就高啊。實際上，訪問頻率不能等同於訪問次數，拋開訪問時間談訪問次數就是在 “耍流氓”。

圖片

在這段時間片內數據 A 被訪問了 5 次，數據 B 與 C 各被訪問了 4 次，如果按照訪問次數判斷數據熱度值，必然是 A>B=C；如果考慮到時效性，距離當前時間越近的訪問越有價值，那麼數據熱度值就應該是 C>B>A。因此，LFU 算法一般都會有一個時間衰減函數參與熱度值的計算，兼顧了訪問時間的影響。

LFU 算法實現的數據結構與 LRU 一樣，也採用 Hash 表 + 雙向鏈表的結構，數據在雙向鏈表內按照熱度值排序。如果某個數據被訪問，更新熱度值之重新插入到鏈表合適的位置，這個比 LRU 算法處理的流程複雜一些。

3.2 Redis LFU 算法實現

Redis 4.0 版本開始增加了 LFU 緩存淘汰策略，也採用數據隨機篩選規則，然後依據數據的熱度值排序，淘汰掉熱度值較低的數據。

3.2.1 LFU 算法代碼實現

LFU 算法的實現沒有使用額外的數據結構，複用了 redisObject 數據結構的 lru 字段，把這 24bit 空間拆分成兩部分去使用。

由於記錄時間戳在空間被壓縮到 16bit，所以 LFU 改成以分鐘爲單位，大概 45.5 天會出現數值折返，比 LRU 時鐘週期還短。
低位的 8bit 用來記錄熱度值（counter），8bit 空間最大值爲 255，無法記錄數據在訪問總次數。

LFU 熱度值（counter）的算法實現：

#define LFU_INIT_VAL 5
/* Logarithmically increment a counter. The greater is the current counter value
 * the less likely is that it gets really implemented. Saturate it at 255. */
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;
}

counter 小於或等於 LFU_INIT_VAL 時候，數據一旦被訪問命中， counter 接近 100% 概率遞增 1；
counter 大於 LFU_INIT_VAL 時候，需要先計算兩者差值，然後作爲分母的一部分參與遞增概率的計算；
隨着 counter 數值的增大，遞增的概率逐步衰減，可能數次的訪問都不能使其數值加 1；
當 counter 數值達到 255，就不再進行數值遞增的計算過程。

LFU counter 的計算也並非 “一塵不變”，爲了適配各種業務數據的特性，Redis 在 LFU 算法實現過程中引入了兩個可調參數：

熱度值counter的時間衰減函數：
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;
}

閱讀完以上的內容，是否感覺似曾相似？實際上 LFU counter 計算過程就是對訪問次數進行了數值歸一化，將數據訪問次數映射成熱度值 (counter)，數值的範圍也從[0,+∞) 映射到另一個維度的[0,255]。

3.3.2 LFU Counter 分析

僅從代碼層面分析研究 Redis LFU 算法實現會比較抽象且枯燥，無法直觀的呈現 counter 遞增概率的算法效果，以及 counter 數值與訪問次數的關係。

在 lfu_log_factor 爲默認值 10 的場景下，利用 Python 實現 Redis LFU 算法流程，繪製出 LFU counter 遞增概率曲線圖：

圖片

可以清晰的觀察到，當 LFU counter 數值超過 LFU_INIT_VAL 之後，曲線出現了垂直下降，遞增概率陡降到 0.2% 左右，隨後在底部形成一個較爲緩慢的衰減曲線，直至 counter 數值達到 255 則遞增概率歸於 0，貼合 3.3.1 章節分析的理論。

保持 Redis 系統配置默認值的情況下，對同一個數據持續的訪問，並採集此數據的 LFU counter 數值，繪製出 LFU counter 數值曲線圖：

隨着訪問次數的不斷增加，LFU counter 數值曲線呈現出爬坡式的遞增，形態趨近於根號曲線，由此推測出以下觀點：

在訪問次數相同的情況下，counter 數值不是固定的，大概率在一個範圍內波動；
在同一個時間段內，數據之間訪問次數相差上千次，纔可以通過 counter 數值區分出哪些數據更熱，而 “溫” 數據之間可能很難區分熱度。

四、總結

通過對 Redis LRU 與 LFU 算法實現的介紹，我們可以大體瞭解兩種算法策略的優缺點，在 Redis 運維過程中，可以依據業務數據的特性去選擇相應的算法。

如果業務數據的訪問較爲均勻，OPS 或 CPU 利用率一般不會出現週期性的陡升或陡降，數據沒有體現出相對的 “冷熱” 特性，即建議採用 LRU 算法，可以滿足一般的運維需求。

相反，業務具備很強時效性，在活動推廣或大促期間，業務某些數據會突然成爲熱點數據，監控上呈現出 OPS 或 CPU 利用率的大幅波動，爲了能抓取熱點數據便於後期的分析或優化，建議一定要配置成 LFU 算法。

在 Used_memory 接近 Maxmemory 的情況下，Redis 一直都採用隨機的方式篩選數據，且篩選的個數極其有限，所以，LFU 算法無法展現出較大的優勢，也可能會淘汰掉比較熱的數據。

參考文獻：

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/LsxzvpegWk6XVqhuqHKS4g

猜你喜歡