一、前言

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

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

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

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

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

2.1 LRU算法原理

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

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

以下是一個(gè)LRU算法示意圖：

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

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

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

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

如果你很熟悉Redis的數(shù)據(jù)類型，你會(huì)發(fā)現(xiàn)這個(gè)LRU的數(shù)據(jù)結(jié)構(gòu)與ZSET類型OBJ_ENCODING_SKIPLIST編碼結(jié)構(gòu)相似，只是LRU數(shù)據(jù)排序方式更簡單一些。

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

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

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

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

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

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

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

redisObject是Redis核心的底層數(shù)據(jù)結(jié)構(gòu)，成員變量lru字段用于記錄了此key最近一次被訪問的LRU時(shí)鐘(server.lruclock)，每次Key被訪問或修改都會(huì)引起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;

默認(rèn)的LRU時(shí)鐘單位是秒，可以修改LRU_CLOCK_RESOLUTION宏來改變單位，LRU時(shí)鐘更新的頻率也和server.hz參數(shù)有關(guān)。

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的空間，按秒為單位也只能存儲(chǔ)194天，所以可能會(huì)出現(xiàn)一個(gè)意想不到的結(jié)果，即間隔194天訪問Key后標(biāo)記的時(shí)間戳一樣，Redis LRU淘汰策略局部失效。

2.3 LRU算法缺陷

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

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

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

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

3.1 LFU算法原理

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

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

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

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

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

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

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

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

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

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

LFU熱度值（counter）的算法實(shí)現(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í)候，數(shù)據(jù)一旦被訪問命中， counter接近100%概率遞增1；

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

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

• 當(dāng)counter 數(shù)值達(dá)到255，就不再進(jìn)行數(shù)值遞增的計(jì)算過程。

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

熱度值counter的時(shí)間衰減函數(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)容，是否感覺似曾相似？實(shí)際上LFU counter計(jì)算過程就是對訪問次數(shù)進(jìn)行了數(shù)值歸一化，將數(shù)據(jù)訪問次數(shù)映射成熱度值(counter)，數(shù)值的范圍也從[0,+∞)映射到另一個(gè)維度的[0,255]。

3.3.2 LFU Counter分析

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

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

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

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

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

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

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

四、總結(jié)

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

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

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

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

以上就是深入解析Redis的LRU與LFU算法實(shí)現(xiàn)的詳細(xì)內(nèi)容，更多關(guān)于Redis LRU與LFU算法的資料請關(guān)注腳本之家其它相關(guān)文章！

最新評論