一、什么是內(nèi)存淘汰？

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

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

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

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

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

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

############################## 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 內(nèi)存上限

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

# maxmemory <bytes>

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

三、Redis 內(nèi)存淘汰策略

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

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

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

策略中用到的兩種算法：

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

四、內(nèi)存淘汰的具體工作步驟

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

五、LRU 算法及在 Redis 中的改進(jìn)

5.1 LRU 算法

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

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

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

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

5.2 Redis 中的 LRU 算法

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

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

這 5 個 key 是默認(rèn)的個數(shù)，具體的數(shù)值可以在 redis.conf 中配置。

maxmemory-samples 5

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

• Redis 中維護(hù)一個大小為 16 的候選池，當(dāng)?shù)谝淮坞S機(jī)選取采樣數(shù)據(jù)時，會把數(shù)據(jù)放入到候選池中，并且候選池中的數(shù)據(jù)會根據(jù) key 的空閑時間進(jìn)行排序。
• 當(dāng)?shù)诙我院筮x取數(shù)據(jù)時，只有大于候選池內(nèi)最小空閑時間的 key 才會被放進(jìn)候選池（空閑時間越大，代表越久沒有被使用，準(zhǔn)備淘汰)）。
• 當(dāng)候選池的數(shù)據(jù)滿了之后，那么空閑時間最大的 key 就會被擠出候選池。當(dāng)執(zhí)行淘汰時，直接從候選池中選取空閑時間最大的 key 進(jìn)行淘汰。

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

• 回收池滿了，并且當(dāng)前插入的 key 的空閑時間最?。ㄒ簿褪腔厥粘刂械乃?key 都比當(dāng)前插入的 key 的空閑時間大），則不作任何操作。
• 回收池未滿，并且插入的位置 x 沒有鍵，則直接插入即可。
• 回收池未滿，且插入的位置 x 原本已經(jīng)存在要淘汰的鍵，則把第 x 個以后的元素都往后挪一個位置，然后再執(zhí)行插入操作。
• 回收池滿了，將當(dāng)前第 x 個以前的元素往前挪一個位置（實際就是淘汰了），然后執(zhí)行插入操作。

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

六、LFU

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

• 當(dāng)添加元素時，找到相同訪問頻次的節(jié)點，然后添加到該節(jié)點的數(shù)據(jù)鏈表的頭部。如果該數(shù)據(jù)鏈表滿了，則移除鏈表尾部的節(jié)點；
• 當(dāng)獲取元素或者修改元素時，都會增加對應(yīng) key 的訪問頻次，并把當(dāng)前節(jié)點移動到下一個頻次節(jié)點。

添加元素時，訪問頻率默認(rèn)為 1，隨著訪問次數(shù)的增加，頻率不斷遞增。而當(dāng)前被訪問的元素也會隨著頻率增加進(jìn)行移動。

到此這篇關(guān)于關(guān)于Redis的內(nèi)存淘汰策略詳解的文章就介紹到這了,更多相關(guān)Redis內(nèi)存淘汰策略內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論