作者：雙子孤狼

原文地址：https://www.cnblogs.com/lonely-wolf/p/14403264.html

---

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

設(shè)置有效期

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

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

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

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

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

過期策略

如果將一個過期的鍵刪除，我們一般都會有三種策略：

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

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

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

8 種淘汰策略

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

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

maxmemory?

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

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

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

淘汰策略	說明
volatile-lru	根據(jù) LRU 算法刪除設(shè)置了過期時間的鍵，直到騰出可用空間。如果沒有可刪除的鍵對象，且內(nèi)存還是不夠用時，則報錯
allkeys-lru	根據(jù) LRU 算法刪除所有的鍵，直到騰出可用空間。如果沒有可刪除的鍵對象，且內(nèi)存還是不夠用時，則報錯
volatile-lfu	根據(jù) LFU 算法刪除設(shè)置了過期時間的鍵，直到騰出可用空間。如果沒有可刪除的鍵對象，且內(nèi)存還是不夠用時，則報錯
allkeys-lfu	根據(jù) LFU 算法刪除所有的鍵，直到騰出可用空間。如果沒有可刪除的鍵對象，且內(nèi)存還是不夠用時，則報錯
volatile-random	隨機刪除設(shè)置了過期時間的鍵，直到騰出可用空間。如果沒有可刪除的鍵對象，且內(nèi)存還是不夠用時，則報錯
allkeys-random	隨機刪除所有鍵，直到騰出可用空間。如果沒有可刪除的鍵對象，且內(nèi)存還是不夠用時，則報錯
volatile-ttl	根據(jù)鍵值對象的 ttl 屬性， 刪除最近將要過期數(shù)據(jù)。如果沒有，則直接報錯
noeviction	默認策略，不作任何處理，直接報錯

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

LRU 算法

LRU?全稱為：Least Recently Used。即：最近最長時間未被使用。這個主要針對的是使用時間。

Redis 改進后的 LRU 算法

在?Redis?當中，并沒有采用傳統(tǒng)的?LRU?算法，因為傳統(tǒng)的?LRU?算法存在?2?個問題：

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

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

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

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

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

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

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

前面我們講述字符串對象時，提到了?redisObject?對象中存在一個?lru?屬性：

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

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

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

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

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

正因為如此，所以計算的時候也需要分為?2?種情況：

• 當全局? lruclock?>? lru，則使用? lruclock?-? lru?得到空閑時間。
• 當全局? lruclock?lru，則使用? lruclock_max（即? 194?天） -? lru?+? lruclock?得到空閑時間。

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

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

LFU 算法

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

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

訪問頻次遞增

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

給定一個舊的訪問頻次，當一個鍵被訪問時，counter?按以下方式遞增：

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

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

lfu_log_factor?10

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

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

訪問頻次遞減

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

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

lfu-decay-time?1

具體算法如下：

1. 獲取當前時間戳，轉(zhuǎn)化為 分鐘后取低? 16?位（為了方便后續(xù)計算，這個值記為? now）。
2. 取出對象內(nèi)的? lru?屬性中的高? 16?位（為了方便后續(xù)計算，這個值記為? ldt）。
3. 當? lru?>? now?時，默認為過了一個周期（ 16?位，最大? 65535)，則取差值? 65535-ldt+now：當? lru?<=? now?時，取差值? now-ldt（為了方便后續(xù)計算，這個差值記為? idle_time）。
4. 取出配置文件中的? lfu_decay_time?值，然后計算： idle_time / lfu_decay_time（為了方便后續(xù)計算，這個值記為 num_periods）。
5. 最后將 counter減少： counter - num_periods。

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

總結(jié)

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