一、前言

Redis是一款基于內(nèi)存的高性能NoSQL數(shù)據(jù)庫，數(shù)據(jù)都緩存在內(nèi)存里， 這使得Redis可以每秒輕松地處理數(shù)萬的讀寫請求。

相對于磁盤的容量，內(nèi)存的空間一般都是有限的，為了避免Redis耗盡宿主機的內(nèi)存空間，Redis內(nèi)部實現(xiàn)了一套復雜的緩存淘汰策略來管控內(nèi)存使用量。

Redis 4.0版本開始就提供了8種內(nèi)存淘汰策略，其中4種都是基于LRU或LFU算法實現(xiàn)的，本文就這兩種算法的Redis實現(xiàn)進行了詳細的介紹，并闡述其優(yōu)劣特性。

二、Redis的LRU實現(xiàn)

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

2.1 LRU算法原理

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

如今，LRU算法廣泛應用在諸多系統(tǒng)內(nèi)，例如Linux內(nèi)核頁表交換，MySQL Buffer Pool緩存頁替換，以及Redis數(shù)據(jù)淘汰策略。

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

向一個緩存空間依次插入三個數(shù)據(jù)A/B/C，填滿了緩存空間；

讀取數(shù)據(jù)A一次，按照訪問時間排序，數(shù)據(jù)A被移動到緩存頭部；

插入數(shù)據(jù)D的時候，由于緩存空間已滿，觸發(fā)了LRU的淘汰策略，數(shù)據(jù)B被移出，緩存空間只保留了D/A/C。

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

如果你很熟悉Redis的數(shù)據(jù)類型，你會發(fā)現(xiàn)這個LRU的數(shù)據(jù)結構與ZSET類型OBJ_ENCODING

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

2.2 Redis LRU算法實現(xiàn)

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

Redis內(nèi)部只使用Hash表緩存了數(shù)據(jù)，并沒有創(chuàng)建一個專門針對LRU算法的雙向鏈表，之所以這樣處理也是因為以下幾個原因：

篩選規(guī)則，Redis是隨機抽取一批數(shù)據(jù)去按照淘汰策略排序，不再需要對所有數(shù)據(jù)排序；

性能問題，每次數(shù)據(jù)訪問都可能涉及數(shù)據(jù)移位，性能會有少許損失；

內(nèi)存問題，Redis對內(nèi)存的使用一向很“摳門”，數(shù)據(jù)結構都很精簡，盡量不使用復雜的數(shù)據(jù)結構管理數(shù)據(jù)；

策略配置，如果線上Redis實例動態(tài)修改淘汰策略會觸發(fā)全部數(shù)據(jù)的結構性改變，這個Redis系統(tǒng)無法承受的。

redisObject是Redis核心的底層數(shù)據(jù)結構，成員變量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參數(shù)有關。

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天，所以可能會出現(xiàn)一個意想不到的結果，即間隔194天訪問Key后標記的時間戳一樣，Redis LRU淘汰策略局部失效。

2.3 LRU算法缺陷

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

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

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

三、Redis的LFU實現(xiàn)

3.1 LFU算法原理

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

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

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

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

3.2 Redis LFU算法實現(xiàn)

Redis 4.0版本開始增加了LFU緩存淘汰策略，也采用數(shù)據(jù)隨機篩選規(guī)則，然后依據(jù)數(shù)據(jù)的熱度值排序，淘汰掉熱度值較低的數(shù)據(jù)。

3.2.1 LFU算法代碼實現(xiàn)

LFU算法的實現(xiàn)沒有使用額外的數(shù)據(jù)結構，復用了redisObject數(shù)據(jù)結構的lru字段，把這24bit空間拆分成兩部分去使用。

由于記錄時間戳在空間被壓縮到16bit，所以LFU改成以分鐘為單位，大概45.5天會出現(xiàn)數(shù)值折返，比LRU時鐘周期還短。

低位的8bit用來記錄熱度值（counter），8bit空間最大值為255，無法記錄數(shù)據(jù)在訪問總次數(shù)。

LFU熱度值（counter）的算法實現(xiàn)：

#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 時候，數(shù)據(jù)一旦被訪問命中， counter接近100%概率遞增1；

counter 大于 LFU_INIT_VAL 時候，需要先計算兩者差值，然后作為分母的一部分參與遞增概率的計算；

隨著counter 數(shù)值的增大，遞增的概率逐步衰減，可能數(shù)次的訪問都不能使其數(shù)值加1；

當counter 數(shù)值達到255，就不再進行數(shù)值遞增的計算過程。

LFU counter的計算也并非“一塵不變”，為了適配各種業(yè)務數(shù)據(jù)的特性，Redis在LFU算法實現(xiàn)過程中引入了兩個可調(diào)參數(shù)：

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

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

3.3.2 LFU Counter分析

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

在lfu_log_factor為默認值10的場景下，利用Python實現(xiàn)Redis LFU算法流程，繪制出LFU counter遞增概率曲線圖：

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

保持Redis系統(tǒng)配置默認值的情況下，對同一個數(shù)據(jù)持續(xù)的訪問，并采集此數(shù)據(jù)的LFU counter數(shù)值，繪制出LFU counter數(shù)值曲線圖：

隨著訪問次數(shù)的不斷增加，LFU counter數(shù)值曲線呈現(xiàn)出爬坡式的遞增，形態(tài)趨近于根號曲線，由此推測出以下觀點：

在訪問次數(shù)相同的情況下，counter數(shù)值不是固定的，大概率在一個范圍內(nèi)波動；

在同一個時間段內(nèi)，數(shù)據(jù)之間訪問次數(shù)相差上千次，才可以通過counter數(shù)值區(qū)分出哪些數(shù)據(jù)更熱，而“溫”數(shù)據(jù)之間可能很難區(qū)分熱度。

四、總結

通過對Redis LRU與LFU算法實現(xiàn)的介紹，我們可以大體了解兩種算法策略的優(yōu)缺點，在Redis運維過程中，可以依據(jù)業(yè)務數(shù)據(jù)的特性去選擇相應的算法。

如果業(yè)務數(shù)據(jù)的訪問較為均勻，OPS或CPU利用率一般不會出現(xiàn)周期性的陡升或陡降，數(shù)據(jù)沒有體現(xiàn)出相對的“冷熱”特性，即建議采用LRU算法，可以滿足一般的運維需求。

相反，業(yè)務具備很強時效性，在活動推廣或大促期間，業(yè)務某些數(shù)據(jù)會突然成為熱點數(shù)據(jù)，監(jiān)控上呈現(xiàn)出OPS或CPU利用率的大幅波動，為了能抓取熱點數(shù)據(jù)便于后期的分析或優(yōu)化，建議一定要配置成LFU算法。

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

審核編輯：劉清