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

maxmemory bytes>

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

LRU 算法

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

Redis 改進后的 LRU 算法

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

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

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

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

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

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

左上角第一幅圖代表的是傳統(tǒng) LRU 算法，可以看到，當(dāng)抽樣數(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ū)懭?，對象被訪問到時也會進行更新。正常人的思路就是最后決定要不要刪除某一個鍵肯定是用當(dāng)前時間戳減去 lru，差值最大的就優(yōu)先被刪除。但是 Redis 里面并不是這么做的，Redis 中維護了一個全局屬性 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)中有很多這種細節(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 - 初始值（默認為 5），得到一個基礎(chǔ)差值，如果這個差值小于 0，則直接取 0，為了方便計算，把這個差值記為 baseval。
• 概率 P 計算公式為：1/(baseval * lfu_log_factor + 1)。
• 如果 R P 時，頻次進行遞增（counter++）。

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

lfu_log_factor 10

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

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

訪問頻次遞減

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

counter 的減少速度由參數(shù) lfu-decay-time 進行控制，默認是 1，單位是分鐘。默認值 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 時，默認為過了一個周期（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 屬性進行對比，計算出當(dāng)前多久沒有被訪問到，比如計算得到的結(jié)果是 100 分鐘沒有被訪問，然后再去除配置參數(shù) lfu_decay_time，如果這個配置默認為 1也即是 100/1=100，代表 100 分鐘沒訪問，所以 counter 就減少 100。

總結(jié)

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

到此這篇關(guān)于淺談內(nèi)存耗盡后Redis會發(fā)生什么的文章就介紹到這了,更多相關(guān)Redis內(nèi)存耗盡內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！