作者：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算法無法展現出較大的優勢，也可能會淘汰掉比較熱的資料。
參考文獻：
- Key eviction。
- Redis的LRU緩存淘汰算法實作（上）
- Redis 緩存淘汰政策以及 LRU、LFU 算法
作者:Luo Jianxin
來源:微信公衆号:vivo網際網路技術
出處:https://mp.weixin.qq.com/s/LsxzvpegWk6XVqhuqHKS4g