一、前言
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/ target=_blank class=infotextkey>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算法無法展現出較大的優勢，也可能會淘汰掉比較熱的數據。
