關于Redis的內存淘汰策略詳解

更新時間：2023年05月19日 09:33:21 作者：長安明月

當內存空間使用達到限制時，Redis 會根據配置策略來選擇不同處理方式，要么返回 errors，要么按照不同的策略算法來清除一些舊數據，達到回收內存的目的，這就是 Redis 的內存淘汰，有些文章中，內存淘汰也叫緩存回收,需要的朋友可以參考下

一、什么是內存淘汰？

如果在做項目時，不計任何后果地把任何數據都往 Redis 寫入，使用不合理很容易導致數據超過Redis 的最大內存，這種情況就會導致如下問題。

Redis 中有很多無效的緩存，這些緩存數據會降低 IO 性能。
隨著系統(tǒng)的運行，Redis 的數據越來越多，會導致物理內存不足。雖然可以通過使用虛擬內存，將很少訪問的數據交換到磁盤上，騰出內存空間的方法來解決物理內存不足的問題，但是由于這部分數據存儲在磁盤上，如果在高并發(fā)場景中，頻繁訪問虛擬內存空間會嚴重降低系統(tǒng)性能。

所以遇到 Redis 內存不足的問題時，我們一般有幾種方法：

對每個存儲到 Redis 中的 key 設置過期時間，這個根據實際業(yè)務場景來決定。否則，再大的內存都會隨著系統(tǒng)運行被消耗完；
增加內存；
使用內存淘汰策略。

當內存空間使用達到限制時，Redis 會根據配置策略來選擇不同處理方式，要么返回 errors，要么按照不同的策略算法來清除一些舊數據，達到回收內存的目的，這就是 Redis 的內存淘汰，有些文章中，內存淘汰也叫緩存回收。

本文以 Linux 系統(tǒng)安裝的 4.0.8 版本的 Redis 為例，對內存淘汰策略進行總結。Redis 的最大內存上限、淘汰算法的配置都在 redis.conf 文件中有說明，現(xiàn)在把 redis.conf 中對內存管理的部分內容摘錄如下。

############################## MEMORY MANAGEMENT ################################
# Set a memory usage limit to the specified amount of bytes.
# When the memory limit is reached Redis will try to remove keys
# according to the eviction policy selected (see maxmemory-policy).
#
# If Redis can't remove keys according to the policy, or if the policy is
# set to 'noeviction', Redis will start to reply with errors to commands
# that would use more memory, like SET, LPUSH, and so on, and will continue
# to reply to read-only commands like GET.
#
# This option is usually useful when using Redis as an LRU or LFU cache, or to
# set a hard memory limit for an instance (using the 'noeviction' policy).
#
# WARNING: If you have slaves attached to an instance with maxmemory on,
# the size of the output buffers needed to feed the slaves are subtracted
# from the used memory count, so that network problems / resyncs will
# not trigger a loop where keys are evicted, and in turn the output
# buffer of slaves is full with DELs of keys evicted triggering the deletion
# of more keys, and so forth until the database is completely emptied.
#
# In short... if you have slaves attached it is suggested that you set a lower
# limit for maxmemory so that there is some free RAM on the system for slave
# output buffers (but this is not needed if the policy is 'noeviction').
#
# maxmemory <bytes>
# MAXMEMORY POLICY: how Redis will select what to remove when maxmemory
# is reached. You can select among five behaviors:
#
# volatile-lru -> Evict using approximated LRU among the keys with an expire set.
# allkeys-lru -> Evict any key using approximated LRU.
# volatile-lfu -> Evict using approximated LFU among the keys with an expire set.
# allkeys-lfu -> Evict any key using approximated LFU.
# volatile-random -> Remove a random key among the ones with an expire set.
# allkeys-random -> Remove a random key, any key.
# volatile-ttl -> Remove the key with the nearest expire time (minor TTL)
# noeviction -> Don't evict anything, just return an error on write operations.
#
# LRU means Least Recently Used
# LFU means Least Frequently Used
#
# Both LRU, LFU and volatile-ttl are implemented using approximated
# randomized algorithms.
#
# Note: with any of the above policies, Redis will return an error on write
#       operations, when there are no suitable keys for eviction.
#
#       At the date of writing these commands are: set setnx setex append
#       incr decr rpush lpush rpushx lpushx linsert lset rpoplpush sadd
#       sinter sinterstore sunion sunionstore sdiff sdiffstore zadd zincrby
#       zunionstore zinterstore hset hsetnx hmset hincrby incrby decrby
#       getset mset msetnx exec sort
#
# The default is:
#
# maxmemory-policy noeviction
# LRU, LFU and minimal TTL algorithms are not precise algorithms but approximated
# algorithms (in order to save memory), so you can tune it for speed or
# accuracy. For default Redis will check five keys and pick the one that was
# used less recently, you can change the sample size using the following
# configuration directive.
#
# The default of 5 produces good enough results. 10 Approximates very closely
# true LRU but costs more CPU. 3 is faster but not very accurate.
#
# maxmemory-samples 5

二、Redis 內存上限

Redis 的最大內存上限可以在配置文件 redis.conf 中配置，redis.conf 配置如下：

# maxmemory <bytes>

設置 maxmemory 為 0 表示沒有內存限制。在 64 位系統(tǒng)中，默認是 0 無限制，但是在 32 位系統(tǒng)中默認是 3GB。

三、Redis 內存淘汰策略

Redis 提供了一種內存淘汰策略，當內存不足時，Redis 會根據相應的淘汰規(guī)則對 key 數據進行淘汰。 Redis 的內存淘汰策略共有 8 種具體的淘汰策略，默認的策略為 noeviction，當內存使用達到閾值的時候，所有引起申請內存的命令會報錯。8 種淘汰策略如下所示。

volatile-lru：當內存不足時，從設置了過期時間的 key 中使用 LRU 算法，選出最近使用最少的數據進行淘汰；
allkeys-lru：當內存不足時，從所有 key 中使用 LRU 算法，選出最近使用最少的數據進行淘汰；
volatile-lfu：當內存不足時，從設置了過期時間的 key 中使用 LFU 算法，選出使用頻率最低的數據進行淘汰；
allkeys-lfu：當內存不足時，從所有 key 中使用 LFU 算法，選出使用頻率最低的數據，進行淘汰；
volatile-random：當內存不足時，從設置了過期時間的 key 中，隨機選出數據進行淘汰；
allkeys-random：當內存不足時，從所有的 key 中，隨機選出數據進行淘汰；
volatile-ttl：當內存不足時，從設置了過期時間的 key 中，選出即將過期的數據（按照過期時間的先后，選出最先過期的數據）進行淘汰；
noeviction：當內存不足時，禁止淘汰數據，寫入操作報錯。這是 Redis 默認的內存淘汰策略。

前綴為 volatile- 和 allkeys- 的區(qū)別在于二者選擇要清除的鍵時的字典不同，volatile- 前綴的策略表示從 redisDb 中的過期字典中選擇鍵進行清除；allkeys- 開頭的策略代表從 dict 字典中選擇鍵進行清除。

策略中用到的兩種算法：

LRU（Least Recently Used）：最近最少使用。優(yōu)先淘汰使用時間最遠的數據。
LFU（Least Frequently Used）：最小頻率使用。優(yōu)先淘汰最不常用的 Key。

四、內存淘汰的具體工作步驟

客戶端執(zhí)行一條新命令，導致數據庫需要增加數據（比如 set key value）；
Redis 會檢查內存使用情況，如果內存使用超過 maxmemory 設置的值，就會按照內存淘汰策略刪除一些 key；
新的命令執(zhí)行成功。

五、LRU 算法及在 Redis 中的改進

5.1 LRU 算法

LRU 是 Least Recently Used 的縮寫，也就是表示最近最少使用，也可以理解成最久沒有使用。也就是說當內存不夠的時候，每次添加一條數據，都需要拋棄一條最久時間沒有使用的舊數據。標準的 LRU 算法為了降低查找和刪除元素的時間復雜度，一般采用 Hash 表和雙向鏈表結合的數據結構，Hash 表可以快速查找到某個 key 是否存在鏈表中，同時可以快速刪除、添加節(jié)點，如下圖所示。

在這里插入圖片描述

雙向鏈表的查找時間復雜度是 O(n)，刪除和插入是 O(1)，借助 HashMap 結構，可以使得查找的時間復雜度變成 O(1)。 Hash 表用來查詢在鏈表中的數據位置，鏈表負責數據的插入，當新數據插入到鏈表頭部時有兩種情況。

鏈表滿了，把鏈表尾部的數據丟棄掉，新加入的緩存直接加入到鏈表頭中。
當鏈表中的某個緩存被命中時，直接把數據移到鏈表頭部，原本在頭節(jié)點的緩存就向鏈表尾部移動。

這樣，經過多次 Cache 操作之后，最近被命中的緩存，都會存在鏈表頭部的方向，沒有命中的，都會在鏈表尾部方向，當需要替換內容時，由于鏈表尾部是最少被命中的，我們只需要淘汰鏈表尾部的數據即可。

5.2 Redis 中的 LRU 算法

實際上，Redis 使用的 LRU 算法是一種不可靠的 LRU 算法，它實際淘汰的鍵并不一定是真正最少使用的數據。它的工作機制是：

隨機采集淘汰的 key，每次隨機選出 5 個key；
然后淘汰這 5 個 key 中最少使用的 key。

這 5 個 key 是默認的個數，具體的數值可以在 redis.conf 中配置。

maxmemory-samples 5

當近似 LRU 算法的抽樣值越大時就越接近真實的 LRU 算法，因為取值越大獲取的數據越完整，淘汰的數據就更加接近最少使用的數據，但是消耗的 CPU 更多。抽樣值越小，算法運行更快，但是準確度越低。這里涉及一個權衡問題，如果需要在所有的數據中搜索最符合條件的數據，那么一定會增加系統(tǒng)的開銷。Redis 是單線程的，所有耗時的操作都要謹慎一些。為了在一定成本內實現(xiàn)相對的 LRU，早期的 Redis 版本是基于采樣的 LRU，也就是放棄了從所有數據中搜索解，改為在采樣空間搜索最優(yōu)解。Redis 3.0 版本之后，Redis 作者對基于采樣的 LRU 進行了一些優(yōu)化：

Redis 中維護一個大小為 16 的候選池，當第一次隨機選取采樣數據時，會把數據放入到候選池中，并且候選池中的數據會根據 key 的空閑時間進行排序。
當第二次以后選取數據時，只有大于候選池內最小空閑時間的 key 才會被放進候選池（空閑時間越大，代表越久沒有被使用，準備淘汰)）。
當候選池的數據滿了之后，那么空閑時間最大的 key 就會被擠出候選池。當執(zhí)行淘汰時，直接從候選池中選取空閑時間最大的 key 進行淘汰。

如下圖所示，首先從目標字典中采集出 maxmemory-samples 個鍵，緩存在一個 samples 數組中，然后從 samples 數組中一個個取出來，和回收池中的鍵進行鍵的空閑時間比較，從而更新回收池。在更新過程中，首先遍歷找到每個鍵的實際插入位置 x，然后根據不同情況進行處理。

在這里插入圖片描述

回收池滿了，并且當前插入的 key 的空閑時間最小（也就是回收池中的所有 key 都比當前插入的 key 的空閑時間大），則不作任何操作。
回收池未滿，并且插入的位置 x 沒有鍵，則直接插入即可。
回收池未滿，且插入的位置 x 原本已經存在要淘汰的鍵，則把第 x 個以后的元素都往后挪一個位置，然后再執(zhí)行插入操作。
回收池滿了，將當前第 x 個以前的元素往前挪一個位置（實際就是淘汰了），然后執(zhí)行插入操作。

這樣做的目的是能夠選出最真實的最少被訪問的 key，能夠正確選擇不常使用的 key。因為在Redis 3.0 之前是隨機選取樣本，這樣的方式很有可能不是真正意義上的最少訪問的 key。LRU 算法有一個弊端，假如一個 key 值訪問頻率很低，但是最近一次被訪問到了，那 LRU 會認為它是熱點數據，不會被淘汰。同樣，經常被訪問的數據，最近一段時間沒有被訪問，這樣會導致這些數據被淘汰掉，導致誤判而淘汰掉熱點數據，于是在 Redis 4.0 中，新加了一種 LFU 算法。

六、LFU

LFU（Least Frequently Used），表示最小頻率使用，它和 key 的使用次數有關。其思想是：根據 key 最近被訪問的頻率進行淘汰，比較少訪問的 key 優(yōu)先淘汰，反之則保留。LFU 的原理是使用計數器來對 key 進行排序，每次 key 被訪問時，計數器會增大，當計數器越大，意味著當前 key 的訪問越頻繁，也就是意味著它是熱點數據。它很好的解決了 LRU 算法的缺陷：一個很久沒有被訪問的 key，偶爾被訪問一次，導致被誤認為是熱點數據的問題。LFU 的實現(xiàn)原理如下圖所示，LFU 維護了兩個鏈表，橫向組成的鏈表用來存儲訪問頻率，每個訪問頻率的節(jié)點下存儲另外一個具有相同訪問頻率的緩存數據。具體的工作原理是：