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

前言

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

內(nèi)存回收

使用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)過期的鍵就進(jìn)行刪除。這種策略相對來說是上面兩種策略的折中方案，需要注意的是這個定期的頻率要結(jié)合實際情況掌控好，使用這種方案有一個缺陷就是可能會出現(xiàn)已經(jīng)過期的鍵也被返回。

在 Redis 當(dāng)中，其選擇的是策略 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 當(dāng)中所有的鍵都沒有過期，而且此時內(nèi)存滿了，那么客戶端繼續(xù)執(zhí)行 set 等命令時 Redis 會怎么處理呢？Redis 當(dāng)中提供了不同的淘汰策略來處理這種場景。

首先 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 進(jìn)行配置：

LRU 算法

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

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

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

需要額外的空間進(jìn)行存儲。

可能存在某些 key 值使用很頻繁，但是最近沒被使用，從而被 LRU 算法刪除。

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

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

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

淺灰色帶是被刪除的對象。

灰色帶是未被刪除的對象。

綠色是添加的對象。

左上角第一幅圖代表的是傳統(tǒng) LRU 算法，可以看到，當(dāng)抽樣數(shù)達(dá)到 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ū)懭?，對象被訪問到時也會進(jìn)行更新。正常人的思路就是最后決定要不要刪除某一個鍵肯定是用當(dāng)前時間戳減去 lru，差值最大的就優(yōu)先被刪除。但是 Redis 里面并不是這么做的，Redis 中維護(hù)了一個全局屬性 lru_clock，這個屬性是通過一個全局函數(shù) serverCron 每隔 100 毫秒執(zhí)行一次來更新的，記錄的是當(dāng)前 unix 時間戳。

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

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

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

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

當(dāng)全局 lruclock > lru，則使用 lruclock - lru 得到空閑時間。

當(dāng)全局 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ā)生，所以說這種處理方式是可能存在刪除不準(zhǔn)確的情況，但是本身這種算法就是一種近似的算法，所以并不會有太大影響。

LFU 算法

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

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

訪問頻次遞增

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

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

提取 0 和 1 之間的隨機數(shù) R。

counter - 初始值（默認(rèn)為 5），得到一個基礎(chǔ)差值，如果這個差值小于 0，則直接取 0，為了方便計算，把這個差值記為 baseval。

概率 P 計算公式為：1/(baseval * lfu_log_factor + 1)。

如果 R < P 時，頻次進(jìn)行遞增（counter++）。

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

lfu_log_factor 10

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

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

訪問頻次遞減

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

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

lfu-decay-time 1

具體算法如下：

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

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

當(dāng) lru > now 時，默認(rèn)為過了一個周期（16 位，最大 65535)，則取差值 65535-ldt+now：當(dāng) lru <= now 時，取差值 now-ldt（為了方便后續(xù)計算，這個差值記為 idle_time）。

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

最后將counter減少：counter - num_periods。

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

總結(jié)

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

編輯：黃飛

?