前言

作為一臺(tái)服務(wù)器來說，內(nèi)存并不是無限的，所以總會(huì)存在內(nèi)存耗盡的情況，那么當(dāng) Redis 服務(wù)器的內(nèi)存耗盡后，如果繼續(xù)執(zhí)行請(qǐng)求命令，Redis 會(huì)如何處理呢？

內(nèi)存回收

使用Redis 服務(wù)時(shí)，很多情況下某些鍵值對(duì)只會(huì)在特定的時(shí)間內(nèi)有效，為了防止這種類型的數(shù)據(jù)一直占有內(nèi)存，我們可以給鍵值對(duì)設(shè)置有效期。Redis 中可以通過 4 個(gè)獨(dú)立的命令來給一個(gè)鍵設(shè)置過期時(shí)間：

• expire key ttl：將 key 值的過期時(shí)間設(shè)置為 ttl 秒。
•  pexpire key ttl：將 key 值的過期時(shí)間設(shè)置為 ttl 毫秒。
•  expireat key timestamp：將 key 值的過期時(shí)間設(shè)置為指定的 timestamp 秒數(shù)。
•  pexpireat key timestamp：將 key 值的過期時(shí)間設(shè)置為指定的 timestamp 毫秒數(shù)。

PS：不管使用哪一個(gè)命令，最終 Redis 底層都是使用 pexpireat 命令來實(shí)現(xiàn)的。另外，set 等命令也可以設(shè)置 key 的同時(shí)加上過期時(shí)間，這樣可以保證設(shè)值和設(shè)過期時(shí)間的原子性。

設(shè)置了有效期后，可以通過 ttl 和 pttl 兩個(gè)命令來查詢剩余過期時(shí)間（如果未設(shè)置過期時(shí)間則下面兩個(gè)命令返回 -1，如果設(shè)置了一個(gè)非法的過期時(shí)間，則都返回 -2）：

•  ttl key 返回 key 剩余過期秒數(shù)。
•  pttl key 返回 key 剩余過期的毫秒數(shù)。

過期策略

如果將一個(gè)過期的鍵刪除，我們一般都會(huì)有三種策略：

•  定時(shí)刪除：為每個(gè)鍵設(shè)置一個(gè)定時(shí)器，一旦過期時(shí)間到了，則將鍵刪除。這種策略對(duì)內(nèi)存很友好，但是對(duì) CPU 不友好，因?yàn)槊總€(gè)定時(shí)器都會(huì)占用一定的 CPU 資源。
•  惰性刪除：不管鍵有沒有過期都不主動(dòng)刪除，等到每次去獲取鍵時(shí)再判斷是否過期，如果過期就刪除該鍵，否則返回鍵對(duì)應(yīng)的值。這種策略對(duì)內(nèi)存不夠友好，可能會(huì)浪費(fèi)很多內(nèi)存。
•  定期掃描：系統(tǒng)每隔一段時(shí)間就定期掃描一次，發(fā)現(xiàn)過期的鍵就進(jìn)行刪除。這種策略相對(duì)來說是上面兩種策略的折中方案，需要注意的是這個(gè)定期的頻率要結(jié)合實(shí)際情況掌控好，使用這種方案有一個(gè)缺陷就是可能會(huì)出現(xiàn)已經(jīng)過期的鍵也被返回。

在 Redis 當(dāng)中，其選擇的是策略 2 和策略 3 的綜合使用。不過 Redis 的定期掃描只會(huì)掃描設(shè)置了過期時(shí)間的鍵，因?yàn)樵O(shè)置了過期時(shí)間的鍵 Redis 會(huì)單獨(dú)存儲(chǔ)，所以不會(huì)出現(xiàn)掃描所有鍵的情況： 

typedef struct redisDb {  
    dict *dict; //所有的鍵值對(duì)  
    dict *expires; //設(shè)置了過期時(shí)間的鍵值對(duì)  
   dict *blocking_keys; //被阻塞的key,如客戶端執(zhí)行BLPOP等阻塞指令時(shí)  
   dict *watched_keys; //WATCHED keys  
   int id; //Database ID  
   //... 省略了其他屬性  
} redisDb; 

8 種淘汰策略

假如 Redis 當(dāng)中所有的鍵都沒有過期，而且此時(shí)內(nèi)存滿了，那么客戶端繼續(xù)執(zhí)行 set 等命令時(shí) Redis 會(huì)怎么處理呢？Redis 當(dāng)中提供了不同的淘汰策略來處理這種場(chǎng)景。

首先 Redis 提供了一個(gè)參數(shù) maxmemory 來配置 Redis 最大使用內(nèi)存：

maxmemory <bytes>

或者也可以通過命令 config set maxmemory 1GB 來動(dòng)態(tài)修改。

如果沒有設(shè)置該參數(shù)，那么在 32 位的操作系統(tǒng)中 Redis 最多使用 3GB 內(nèi)存，而在 64 位的操作系統(tǒng)中則不作限制。

Redis 中提供了 8 種淘汰策略，可以通過參數(shù) maxmemory-policy 進(jìn)行配置：

PS：淘汰策略也可以直接使用命令 config set maxmemory-policy <策略> 來進(jìn)行動(dòng)態(tài)配置。

LRU 算法

LRU 全稱為：Least Recently Used。即：最近最長時(shí)間未被使用。這個(gè)主要針對(duì)的是使用時(shí)間。

Redis 改進(jìn)后的 LRU 算法

在 Redis 當(dāng)中，并沒有采用傳統(tǒng)的 LRU 算法，因?yàn)閭鹘y(tǒng)的 LRU 算法存在 2 個(gè)問題：

•  需要額外的空間進(jìn)行存儲(chǔ)。
•  可能存在某些 key 值使用很頻繁，但是最近沒被使用，從而被 LRU 算法刪除。

為了避免以上 2 個(gè)問題，Redis 當(dāng)中對(duì)傳統(tǒng)的 LRU 算法進(jìn)行了改造，通過抽樣的方式進(jìn)行刪除。

配置文件中提供了一個(gè)屬性 maxmemory_samples 5，默認(rèn)值就是 5，表示隨機(jī)抽取 5 個(gè) key 值，然后對(duì)這 5 個(gè) key 值按照 LRU 算法進(jìn)行刪除，所以很明顯，key 值越大，刪除的準(zhǔn)確度越高。

對(duì)抽樣 LRU 算法和傳統(tǒng)的 LRU 算法，Redis 官網(wǎng)當(dāng)中有一個(gè)對(duì)比圖：

•  淺灰色帶是被刪除的對(duì)象。
•  灰色帶是未被刪除的對(duì)象。
•  綠色是添加的對(duì)象。

左上角第一幅圖代表的是傳統(tǒng) LRU 算法，可以看到，當(dāng)抽樣數(shù)達(dá)到 10 個(gè)（右上角），已經(jīng)和傳統(tǒng)的 LRU 算法非常接近了。

Redis 如何管理熱度數(shù)據(jù)

前面我們講述字符串對(duì)象時(shí)，提到了 redisObject 對(duì)象中存在一個(gè) lru 屬性： 

typedef struct redisObject {  
    unsigned type:4;//對(duì)象類型（4位=0.5字節(jié)）  
    unsigned encoding:4;//編碼（4位=0.5字節(jié)）  
    unsigned lru:LRU_BITS;//記錄對(duì)象最后一次被應(yīng)用程序訪問的時(shí)間（24位=3字節(jié)）  
    int refcount;//引用計(jì)數(shù)。等于0時(shí)表示可以被垃圾回收（32位=4字節(jié)）  
    void *ptr;//指向底層實(shí)際的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)，如：SDS等(8字節(jié))  
} robj; 

lru 屬性是創(chuàng)建對(duì)象的時(shí)候?qū)懭?，?duì)象被訪問到時(shí)也會(huì)進(jìn)行更新。正常人的思路就是最后決定要不要?jiǎng)h除某一個(gè)鍵肯定是用當(dāng)前時(shí)間戳減去 lru，差值最大的就優(yōu)先被刪除。但是 Redis 里面并不是這么做的，Redis 中維護(hù)了一個(gè)全局屬性 lru_clock，這個(gè)屬性是通過一個(gè)全局函數(shù) serverCron 每隔 100 毫秒執(zhí)行一次來更新的，記錄的是當(dāng)前 unix 時(shí)間戳。

最后決定刪除的數(shù)據(jù)是通過 lru_clock 減去對(duì)象的 lru 屬性而得出的。那么為什么 Redis 要這么做呢？直接取全局時(shí)間不是更準(zhǔn)確嗎？

這是因?yàn)檫@么做可以避免每次更新對(duì)象的 lru 屬性的時(shí)候可以直接取全局屬性，而不需要去調(diào)用系統(tǒng)函數(shù)來獲取系統(tǒng)時(shí)間，從而提升效率（Redis 當(dāng)中有很多這種細(xì)節(jié)考慮來提升性能，可以說是對(duì)性能盡可能的優(yōu)化到極致）。

不過這里還有一個(gè)問題，我們看到，redisObject 對(duì)象中的 lru 屬性只有 24 位，24 位只能存儲(chǔ) 194 天的時(shí)間戳大小，一旦超過 194 天之后就會(huì)重新從 0 開始計(jì)算，所以這時(shí)候就可能會(huì)出現(xiàn) redisObject 對(duì)象中的 lru 屬性大于全局的 lru_clock 屬性的情況。

正因?yàn)槿绱耍杂?jì)算的時(shí)候也需要分為 2 種情況：

•  當(dāng)全局 lruclock > lru，則使用 lruclock - lru 得到空閑時(shí)間。
•  當(dāng)全局 lruclock < lru，則使用 lruclock_max（即 194 天） - lru + lruclock 得到空閑時(shí)間。

需要注意的是，這種計(jì)算方式并不能保證抽樣的數(shù)據(jù)中一定能刪除空閑時(shí)間最長的。這是因?yàn)槭紫瘸^ 194 天還不被使用的情況很少，再次只有 lruclock 第 2 輪繼續(xù)超過 lru 屬性時(shí)，計(jì)算才會(huì)出問題。

比如對(duì)象 A 記錄的 lru 是 1 天，而 lruclock 第二輪都到 10 天了，這時(shí)候就會(huì)導(dǎo)致計(jì)算結(jié)果只有 10-1=9 天，實(shí)際上應(yīng)該是 194+10-1=203 天。但是這種情況可以說又是更少發(fā)生，所以說這種處理方式是可能存在刪除不準(zhǔn)確的情況，但是本身這種算法就是一種近似的算法，所以并不會(huì)有太大影響。

LFU 算法

LFU 全稱為：Least Frequently Used。即：最近最少頻率使用，這個(gè)主要針對(duì)的是使用頻率。這個(gè)屬性也是記錄在redisObject 中的 lru 屬性內(nèi)。

當(dāng)我們采用 LFU 回收策略時(shí)，lru 屬性的高 16 位用來記錄訪問時(shí)間（last decrement time：ldt，單位為分鐘），低 8 位用來記錄訪問頻率（logistic counter：logc），簡稱 counter。

訪問頻次遞增

LFU 計(jì)數(shù)器每個(gè)鍵只有 8 位，它能表示的最大值是 255，所以 Redis 使用的是一種基于概率的對(duì)數(shù)器來實(shí)現(xiàn) counter 的遞增。r

給定一個(gè)舊的訪問頻次，當(dāng)一個(gè)鍵被訪問時(shí)，counter 按以下方式遞增：

1.  提取 0 和 1 之間的隨機(jī)數(shù) R。
2.  counter - 初始值（默認(rèn)為 5），得到一個(gè)基礎(chǔ)差值，如果這個(gè)差值小于 0，則直接取 0，為了方便計(jì)算，把這個(gè)差值記為 baseval。
3.  概率 P 計(jì)算公式為：1/(baseval * lfu_log_factor + 1)。
4.  如果 R < P 時(shí)，頻次進(jìn)行遞增（counter++）。

公式中的 lfu_log_factor 稱之為對(duì)數(shù)因子，默認(rèn)是 10 ，可以通過參數(shù)來進(jìn)行控制：

lfu_log_factor 10 

下圖就是對(duì)數(shù)因子 lfu_log_factor 和頻次 counter 增長的關(guān)系圖：

可以看到，當(dāng)對(duì)數(shù)因子 lfu_log_factor 為 100 時(shí)，大概是 10M（1000萬） 次訪問才會(huì)將訪問 counter 增長到 255，而默認(rèn)的 10 也能支持到 1M（100萬） 次訪問 counter 才能達(dá)到 255 上限，這在大部分場(chǎng)景都是足夠滿足需求的。

訪問頻次遞減

如果訪問頻次 counter 只是一直在遞增，那么遲早會(huì)全部都到 255，也就是說 counter 一直遞增不能完全反應(yīng)一個(gè) key 的熱度的，所以當(dāng)某一個(gè) key 一段時(shí)間不被訪問之后，counter 也需要對(duì)應(yīng)減少。

counter 的減少速度由參數(shù) lfu-decay-time 進(jìn)行控制，默認(rèn)是 1，單位是分鐘。默認(rèn)值 1 表示：N 分鐘內(nèi)沒有訪問，counter 就要減 N。 

lfu-decay-time 1 

具體算法如下：

    1.  獲取當(dāng)前時(shí)間戳，轉(zhuǎn)化為分鐘后取低 16 位（為了方便后續(xù)計(jì)算，這個(gè)值記為 now）。

    2.  取出對(duì)象內(nèi)的 lru 屬性中的高 16 位（為了方便后續(xù)計(jì)算，這個(gè)值記為 ldt）。

    3.  當(dāng) lru > now 時(shí)，默認(rèn)為過了一個(gè)周期（16 位，最大 65535)，則取差值 65535-ldt+now：當(dāng) lru <= now 時(shí)，取差值 now-ldt（為了方便后

        續(xù)計(jì)算，這個(gè)差值記為 idle_time）。

    4.  取出配置文件中的 lfu_decay_time 值，然后計(jì)算：idle_time / lfu_decay_time（為了方便后續(xù)計(jì)算，這個(gè)值記為num_periods）。

    5.  最后將counter減少：counter - num_periods。

看起來這么復(fù)雜，其實(shí)計(jì)算公式就是一句話：取出當(dāng)前的時(shí)間戳和對(duì)象中的 lru 屬性進(jìn)行對(duì)比，計(jì)算出當(dāng)前多久沒有被訪問到，比如計(jì)算得到的結(jié)果是 100 分鐘沒有被訪問，然后再去除配置參數(shù) lfu_decay_time，如果這個(gè)配置默認(rèn)為 1也即是 100/1=100，代表 100 分鐘沒訪問，所以 counter 就減少 100。

總結(jié)

本文主要介紹了 Redis 過期鍵的處理策略，以及當(dāng)服務(wù)器內(nèi)存不夠時(shí) Redis 的 8 種淘汰策略，最后介紹了 Redis 中的兩種主要的淘汰算法 LRU 和 LFU。