作者：雙子孤狼

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

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

設(shè)置有效期

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

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

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

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

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

過(guò)期策略

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

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

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

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

8 種淘汰策略

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

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

maxmemory?

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

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

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

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

LRU 算法

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

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

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

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

為了避免以上?2?個(gè)問(wèn)題，Redis?當(dāng)中對(duì)傳統(tǒng)的?LRU?算法進(jìn)行了改造，通過(guò)抽樣的方式進(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)用程序訪問(wèn)的時(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ì)象被訪問(wèn)到時(shí)也會(huì)進(jìn)行更新。正常人的思路就是最后決定要不要?jiǎng)h除某一個(gè)鍵肯定是用當(dāng)前時(shí)間戳減去?lru，差值最大的就優(yōu)先被刪除。但是?Redis?里面并不是這么做的，Redis?中維護(hù)了一個(gè)全局屬性?lru_clock，這個(gè)屬性是通過(guò)一個(gè)全局函數(shù)?serverCron?每隔?100?毫秒執(zhí)行一次來(lái)更新的，記錄的是當(dāng)前?unix?時(shí)間戳。

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

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

不過(guò)這里還有一個(gè)問(wèn)題，我們看到，redisObject?對(duì)象中的?lru?屬性只有?24?位，24?位只能存儲(chǔ)?194?天的時(shí)間戳大小，一旦超過(guò)?194?天之后就會(huì)重新從?0?開(kāi)始計(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í)間最長(zhǎng)的。這是因?yàn)槭紫瘸^(guò)?194?天還不被使用的情況很少，再次只有?lruclock?第?2?輪繼續(xù)超過(guò)?lru?屬性時(shí)，計(jì)算才會(huì)出問(wèn)題。

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

LFU 算法

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

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

訪問(wèn)頻次遞增

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

給定一個(gè)舊的訪問(wèn)頻次，當(dāng)一個(gè)鍵被訪問(wèn)時(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?，可以通過(guò)參數(shù)來(lái)進(jìn)行控制：

lfu_log_factor?10

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

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

訪問(wèn)頻次遞減

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

counter?的減少速度由參數(shù)?lfu-decay-time?進(jìn)行控制，默認(rèn)是?1，單位是分鐘。默認(rèn)值?1?表示：N?分鐘內(nèi)沒(méi)有訪問(wèn)，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)為過(guò)了一個(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。

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

總結(jié)

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