Redis常見面試題之 - 內(nèi)存淘汰算法
現(xiàn)在后端面試中比較喜歡問一些 Redis 的問題，比較常見的就是 內(nèi)存淘汰算法。下面我們通過源碼來分析 Redis 內(nèi)存淘汰算法的實(shí)現(xiàn)，從而不會被面試官問到啞口無言。
Redis 內(nèi)存使用限制設(shè)置
一般來說，要開啟 Redis 的內(nèi)存使用限制才會觸發(fā)內(nèi)存淘汰機(jī)制，Redis 內(nèi)存使用限制通過以下配置來設(shè)置：
# 設(shè)置 Redis 最大使用內(nèi)存大小為100Mmaxmemory 100mb
上面的配置設(shè)置了，當(dāng) Redis 使用的內(nèi)存超過 100Mb 時(shí)就開始對數(shù)據(jù)進(jìn)行淘汰。
Redis 內(nèi)存淘汰算法
而 Redis 的淘汰算法有多種，如下：
隨機(jī)
TTL
LRU（Least Recently Used，最近最少使用）
LFU（Least Frequently Used，最不經(jīng)常使用）
隨機(jī)算法很好理解，就是從數(shù)據(jù)庫中隨機(jī)淘汰一些 Keys。而 TTL 算法就是從設(shè)置了過期時(shí)間的 Keys 中獲取最早過期的 一批 Keys，然后淘汰這些 Keys。而 LRU 和 LFU 這兩種算法在名字上比較容易混淆，所以這里介紹一下這兩種算法的區(qū)別。
LRU算法
LRU 主要是通過 Key 的最后訪問時(shí)間來判定哪些 Key 更適合被淘汰，如下圖所示：
如上圖所示，所有的 Keys 都根據(jù)最后被訪問的時(shí)間來進(jìn)行排序的，所以在淘汰時(shí)只需要按照所有 Keys 的最后被訪問時(shí)間，由小到大來進(jìn)行即可。
LFU算法
LFU算法主要通過 Key 的訪問頻率來統(tǒng)計(jì)哪些 Key 更適合被淘汰，如下圖所示：
如上圖所示，所有 Keys 都根據(jù)被訪問次數(shù)進(jìn)行排序，所以在淘汰時(shí)只需要按照所有 Keys 的被訪問次數(shù)，由小到大來進(jìn)行即可。
Redis 內(nèi)存淘汰算法配置
可以通過 maxmemory-policy 配置項(xiàng)來設(shè)置 Redis 的內(nèi)存淘汰算法，如下：
maxmemory-policy volatile-lru
可以根據(jù)應(yīng)用的使用場景來選擇合適的內(nèi)存淘汰算法。
Redis內(nèi)存淘汰實(shí)現(xiàn)
接下來，我們將通過分析 Redis 源碼來了解其實(shí)現(xiàn)原理。
1. LRU淘汰算法實(shí)現(xiàn)
我們先來分析 Redis 的 LRU 淘汰算法的實(shí)現(xiàn)。
前面說過，LRU 淘汰算法是使用 Key 的最后訪問時(shí)間來進(jìn)行判定的，所以在 Redis 的 Key 對象中有個(gè)字段用于保存其最后被訪問的時(shí)間，如下代碼所示：
typedef struct redisObject {unsigned type:4;unsigned encoding:4;unsigned lru:LRU_BITS; // 記錄 Key 的最后被訪問時(shí)間int refcount;void *ptr;} robj;
在 robj 對象中的 lru 字段就是用來記錄 Key 的最后被訪問時(shí)間。當(dāng) Key 被訪問時(shí)，會調(diào)用 lookupKey 函數(shù)查找 Key 對應(yīng)的值，我們可以從 lookupKey 函數(shù)中找到 lru 字段更新相關(guān)的代碼：
robj *lookupKey(redisDb *db, robj *key, int flags) {dictEntry *de = dictFind(db->dict, key->ptr); // 獲取 Key 對應(yīng)的 Valueif (de) {robj *val = dictGetVal(de);if (!hasActiveChildProcess() && !(flags & LOOKUP_NOTOUCH)){if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {updateLFU(val);} else {val->lru = LRU_CLOCK(); // 更新 Key 最后被訪問時(shí)間}}return val;} else {return NULL;}}
從 lookupKey 函數(shù)的實(shí)現(xiàn)中可以看到，當(dāng) Key 被訪問時(shí)會更新其 lru 字段的值為當(dāng)前時(shí)間戳。
2. LFU淘汰算法實(shí)現(xiàn)
由于 LRU 算法使用 Key 的最后訪問時(shí)間來判定是否應(yīng)該淘汰，那么就會導(dǎo)致以下情況出現(xiàn)：
如上圖的情況，由于 Key2 的最后訪問時(shí)間比 Key1 的要新，所以如果使用 LRU 算法進(jìn)行淘汰的話，那么應(yīng)該先淘汰 Key1。但通過觀察發(fā)現(xiàn)，Key1 的訪問頻率明顯比 Key2 高，所以應(yīng)該淘汰 Key2 更為合理。
由于 LRU 算法有以上的缺點(diǎn)，所以 Redis 4.0 開始支持 LFU 淘汰算法。前面也說過，LFU 算法是通過訪問 Key 的頻率來進(jìn)行淘汰的，下面我們介紹以下 Redis 的 LFU 算法是怎么實(shí)現(xiàn)的。
Redis 的 LFU 算法也是通過 robj 對象的 lru 字段來保存 Key 的訪問頻率的，LFU 算法把 lru 字段分為兩部分，如下圖：
0 ~ 7 位：用于保存 Key 的訪問頻率計(jì)數(shù)器。
8 ~ 23 位：用于保存當(dāng)前時(shí)間（以分鐘計(jì)算）。
由于訪問頻率計(jì)數(shù)器只有8個(gè)位，所以取值范圍為 0 ~ 255，如果每訪問 Key 都增加 1，那么很快就用完。所以 Redis 使用了一種比較復(fù)雜的算法了計(jì)算訪問頻率，算法如下：
獲取一個(gè) 0 ~ 1 的浮點(diǎn)數(shù)隨機(jī)數(shù)
r。根據(jù)計(jì)數(shù)器的舊值與影響因子（通過
lfu-log-factor配置項(xiàng)設(shè)置）計(jì)算出一個(gè) 0 ~ 1 的浮點(diǎn)數(shù)p，計(jì)算公式為：1.0 / (計(jì)算器舊值 * 影響因子 + 1)。如果
p的值大于r，那么就對訪問頻率計(jì)數(shù)器進(jìn)行加一。
Redis 通過 LFULogIncr 函數(shù)來實(shí)現(xiàn)這個(gè)算法：
uint8_t LFULogIncr(uint8_t counter){if (counter == 255)return 255;double r = (double)rand()/RAND_MAX; // 獲取隨機(jī)數(shù)rdouble baseval = counter - LFU_INIT_VAL; // 計(jì)數(shù)器舊值if (baseval < 0) baseval = 0;// 根據(jù)計(jì)數(shù)器舊值與影響因子來計(jì)算出pdouble p = 1.0 / (baseval * server.lfu_log_factor + 1);if (r < p) counter++; // 如果 p 大于 r, 那么對計(jì)數(shù)器進(jìn)行加以操作return counter;}
所以從上面的算法可以看出，影響訪問頻率計(jì)數(shù)器的增加速度有兩個(gè)因素：1. 計(jì)數(shù)器的舊值；2. 影響因子。
下表展示了影響因子的取值對訪問頻率計(jì)數(shù)器增速的影響（從0增長到255需要訪問的次數(shù)）：
| 影響因子 | 100 次 | 1000 次 | 100000 次 | 1000000 次 | 10000000 次 |
|---|---|---|---|---|---|
| 1 | 18 | 49 | 255 | 255 | 255 |
| 10 | 10 | 18 | 142 | 255 | 255 |
| 100 | 8 | 11 | 49 | 143 | 255 |
從上表中可知，在影響因子為100的條件下，經(jīng)過1000萬次命中才能把訪問頻率計(jì)數(shù)器增加到255。
如果訪問頻率計(jì)數(shù)器只增不減的話，那么當(dāng)所有 Key 到增加到 255 后，LFU 算法就不起效果了。所以 Redis 還實(shí)現(xiàn)了訪問頻率計(jì)數(shù)器的衰減算法，衰減算法的原理就是，Key 越久沒被訪問，衰減的程度就越大。
Redis 的訪問頻率計(jì)數(shù)器衰減算法是通過 LFUDecrAndReturn 函數(shù)完成的：
unsigned long LFUDecrAndReturn(robj *o) {unsigned long ldt = o->lru >> 8; // 獲取 Key 最后訪問時(shí)間(單位為分鐘)unsigned long counter = o->lru & 255; // 獲取 Key 訪問頻率計(jì)數(shù)器的值// 下面是計(jì)算要衰減的數(shù)量// LFUTimeElapsed 函數(shù)用于獲取 Key 沒被訪問的時(shí)間(單位為分鐘)// lfu_decay_time 是衰減的力度，通過配置項(xiàng) lfu-decay-time 設(shè)置，值越大，衰減力度約小unsigned long num_periods = server.lfu_decay_time? LFUTimeElapsed(ldt) / server.lfu_decay_time: 0;// 對訪問頻率計(jì)數(shù)器進(jìn)行衰減操作if (num_periods)counter = (num_periods > counter) ? 0 : counter - num_periods;return counter;}
從 LFUDecrAndReturn 函數(shù)可知，lfu-decay-time 設(shè)置越大，衰減的力度就越小。如果 lfu-decay-time 設(shè)置為1，并且 Key 在 10 分鐘內(nèi)沒被訪問的話，按算法可知，訪問頻率計(jì)數(shù)器就會被衰減10。
LFU 算法更新 lru 字段也是在 lookupKey 函數(shù)中完成的：
robj *lookupKey(redisDb *db, robj *key, int flags) {dictEntry *de = dictFind(db->dict, key->ptr); // 獲取 Key 對應(yīng)的 Valueif (de) {robj *val = dictGetVal(de);if (!hasActiveChildProcess() && !(flags & LOOKUP_NOTOUCH)){if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) { // 如果配置的是LFU淘汰算法updateLFU(val); // 更新LFU算法的統(tǒng)計(jì)信息} else {val->lru = LRU_CLOCK();}}return val;} else {return NULL;}}
我們來看看 updateLFU 函數(shù)的實(shí)現(xiàn)：
void updateLFU(robj *val) {unsigned long counter = LFUDecrAndReturn(val); // 對訪問頻率計(jì)數(shù)器進(jìn)行衰減操作counter = LFULogIncr(counter); // 增加訪問頻率計(jì)數(shù)器的值val->lru = (LFUGetTimeInMinutes()<<8) | counter; // 將當(dāng)前時(shí)間與訪問頻率計(jì)數(shù)器組合成LFU統(tǒng)計(jì)信息}
updateLFU 函數(shù)比較簡單，首先對訪問頻率計(jì)數(shù)器進(jìn)行衰減操作，然后增加訪問頻率計(jì)數(shù)器的值，最后將當(dāng)前時(shí)間與訪問頻率計(jì)數(shù)器組合成起來保存到 robj 對象的 lru 字段中。