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

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

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

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

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

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

本文以 Linux 系統(tǒng)安裝的 4.0.8 版本的 Redis 為例，對(duì)內(nèi)存淘汰策略進(jìn)行總結(jié)。Redis 的最大內(nèi)存上限、淘汰算法的配置都在 redis.conf 文件中有說(shuō)明，現(xiàn)在把 redis.conf 中對(duì)內(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 表示沒(méi)有內(nèi)存限制。在 64 位系統(tǒng)中，默認(rèn)是 0 無(wú)限制，但是在 32 位系統(tǒng)中默認(rèn)是 3GB。

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

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

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

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

策略中用到的兩種算法：

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

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

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

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

5.1 LRU 算法

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

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

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

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

5.2 Redis 中的 LRU 算法

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

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

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

maxmemory-samples 5

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

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

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

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

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

六、LFU

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

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

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

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

最新評(píng)論