點(diǎn)擊關(guān)注公眾號(hào)，Java干貨及時(shí)送達(dá)

牛逼！又發(fā)現(xiàn)了一款面試題庫(kù)，太全了??！
（點(diǎn)擊查看）

來(lái)源：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ì)如何處理呢？

# 內(nèi)存回收

使用Redis 服務(wù)時(shí)，很多情況下某些鍵值對(duì)只會(huì)在特定的時(shí)間內(nèi)有效，為了防止這種類(lè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 <bytes>

或者也可以通過(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ì)象類(lèi)型（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 按以下方式遞增：

提取?0?和 1 之間的隨機(jī)數(shù) R。
counter - 初始值（默認(rèn)為 5），得到一個(gè)基礎(chǔ)差值，如果這個(gè)差值小于?0，則直接取?0，為了方便計(jì)算，把這個(gè)差值記為 baseval。
概率 P 計(jì)算公式為：1/(baseval * lfu_log_factor + 1)。
如果 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

具體算法如下：

獲取當(dāng)前時(shí)間戳，轉(zhuǎn)化為分鐘后取低 16 位（為了方便后續(xù)計(jì)算，這個(gè)值記為 now）。
取出對(duì)象內(nèi)的 lru 屬性中的高 16 位（為了方便后續(xù)計(jì)算，這個(gè)值記為 ldt）。
當(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）。
取出配置文件中的 lfu_decay_time 值，然后計(jì)算：idle_time / lfu_decay_time（為了方便后續(xù)計(jì)算，這個(gè)值記為num_periods）。
最后將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。


如有文章對(duì)你有幫助，
歡迎關(guān)注??、點(diǎn)贊??、轉(zhuǎn)發(fā)??！

推薦，?Java面試題庫(kù)，詳情點(diǎn)擊：

牛逼！又發(fā)現(xiàn)了一款牛逼的Java面試題庫(kù)，史上最強(qiáng)！

京東二面：內(nèi)存耗盡后Redis會(huì)發(fā)生什么？

牛逼！又發(fā)現(xiàn)了一款面試題庫(kù)，太全了??！

（點(diǎn)擊查看）