redis作為緩存的場(chǎng)景下，內(nèi)存淘汰策略決定的redis的內(nèi)存使用效率?？紤]到這個(gè)很多大廠給出的“送分題”，但一般人很少能講清楚，除非你對(duì)真的對(duì)過期策略、懶惰刪除、LRU、LRU有一定的研究。

1. 過期策略

Redis 所有的數(shù)據(jù)結(jié)構(gòu)都可以設(shè)置過期時(shí)間，時(shí)間一到，就會(huì)自動(dòng)刪除。就像死神，時(shí)刻盯著所有設(shè)置了過期時(shí)間的 key，壽命一到就會(huì)立即收割。

站在死神的角度思考：會(huì)不會(huì)在同一時(shí)間太多的 key 過期（Redis 是單線程的，收割的時(shí)間也會(huì)占用線程的處理時(shí)間，如果收割的太過于繁忙），以至于忙不過來？會(huì)不會(huì)導(dǎo)致線上讀寫指令出現(xiàn)卡頓？

1.1 過期的 key 集合

redis 會(huì)將每個(gè)設(shè)置了過期時(shí)間的 key 放入到一個(gè)獨(dú)立的字典中，以后會(huì)定時(shí)遍歷這個(gè)字典來刪除到期的 key。

redis 采用兩種策略：

• 定時(shí)刪除是集中處理
• 惰性刪除是零散處理

1.2 定時(shí)掃描策略

Redis 默認(rèn)會(huì)每秒進(jìn)行十次過期掃描，過期掃描不會(huì)遍歷過期字典中所有的 key，而是采用了一種簡(jiǎn)單的貪心策略。

• 從過期字典中隨機(jī) 20 個(gè) key；
• 刪除這 20 個(gè) key 中已經(jīng)過期的 key；
• 如果過期的 key 比率超過 1/4，那就重復(fù)步驟 1；

同時(shí)，為了保證過期掃描不會(huì)出現(xiàn)循環(huán)過度，導(dǎo)致線程卡死現(xiàn)象，算法還增加了掃描時(shí)間的上限，默認(rèn)不會(huì)超過 25ms。

如果Redis 實(shí)例中所有的 key （幾十萬個(gè)）在同一時(shí)間過期會(huì)怎樣？

Redis 會(huì)持續(xù)掃描過期字典 (循環(huán)多次)，直到過期字典中過期的 key 變得稀疏，才會(huì)停止 (循環(huán)次數(shù)明顯下降)。內(nèi)存管理器需要頻繁回收內(nèi)存頁(yè)，此時(shí)會(huì)產(chǎn)生一定的 CPU 消耗，必然導(dǎo)致線上讀寫請(qǐng)求出現(xiàn)明顯的卡頓現(xiàn)象。

當(dāng)客戶端請(qǐng)求到來時(shí)（服務(wù)器如果正好進(jìn)入過期掃描狀態(tài)），客戶端的請(qǐng)求將會(huì)等待至少 25ms 后才會(huì)進(jìn)行處理，如果客戶端將超時(shí)時(shí)間設(shè)置的比較短，比如 10ms，那么就會(huì)出現(xiàn)大量的鏈接因?yàn)槌瑫r(shí)而關(guān)閉，業(yè)務(wù)端就會(huì)出現(xiàn)很多異常。而且這時(shí)你還無法從 Redis 的 slowlog 中看到慢查詢記錄，因?yàn)槁樵冎傅氖沁壿嬏幚磉^程慢，不包含等待時(shí)間。

其實(shí)這個(gè)故障在社區(qū)中時(shí)常爆出 ，業(yè)務(wù)開發(fā)人員一定要注意不宜全部在同一時(shí)間過期，可以給目標(biāo)過期時(shí)間的基礎(chǔ)上再加一個(gè)隨機(jī)范圍（redis.expire_at(key, random.randint(86400) + expire_ts)），分散過期處理的壓力。

1.3 從庫(kù)的過期策略

從庫(kù)不會(huì)進(jìn)行過期掃描，從庫(kù)對(duì)過期的處理是被動(dòng)的。主庫(kù)在 key 到期時(shí)，會(huì)在 AOF 文件里增加一條 del 指令，同步到所有的從庫(kù)，從庫(kù)通過執(zhí)行這條 del 指令來刪除過期的 key。

因?yàn)橹噶钔绞钱惒竭M(jìn)行的，所以主庫(kù)過期的 key 的 del 指令沒有及時(shí)同步到從庫(kù)的話，會(huì)出現(xiàn)主從數(shù)據(jù)的不一致，主庫(kù)沒有的數(shù)據(jù)在從庫(kù)里還存在，分布式鎖的算法漏洞就是因?yàn)檫@個(gè)同步延遲產(chǎn)生的。

2. 懶惰刪除

懶惰刪除(lazy free)，在客戶端訪問key時(shí)再進(jìn)行檢查如果過期了就立即刪除

為什么要懶惰刪除？

Redis內(nèi)部實(shí)際上并不是只有一個(gè)主線程，它還有幾個(gè)異步線程專門用來處理一些耗時(shí)的操作。刪除指令 del 會(huì)直接釋放對(duì)象的內(nèi)存，大部分情況下，這個(gè)指令非常快，沒有明顯延遲。

不過如果刪除的 key 是一個(gè)非常大的對(duì)象，那么刪除操作就會(huì)導(dǎo)致單線程卡頓，怎么破？

Redis 4.0 版本引入了 unlink 指令（為了解決這個(gè)卡頓問題），它能對(duì)刪除操作進(jìn)行懶處理，丟給后臺(tái)線程來異步回收內(nèi)存。

> unlink key

OK

你肯定會(huì)擔(dān)心這里的線程安全問題，會(huì)不會(huì)出現(xiàn)多個(gè)線程同時(shí)并發(fā)修改數(shù)據(jù)結(jié)構(gòu)的情況存在？

這里我打個(gè)比方：可以將整個(gè) Redis 內(nèi)存里面所有有效的數(shù)據(jù)想象成一棵大樹。當(dāng) unlink 指令發(fā)出時(shí)，它只是把大樹中的一個(gè)樹枝別斷了，然后扔到旁邊的火堆里焚燒 (異步線程池)。樹枝離開大樹的一瞬間，它就再也無法被主線程中的其它指令訪問到了，因?yàn)橹骶€程只會(huì)沿著這顆大樹來訪問。

2.1 異步線程

異步線程在 Redis 內(nèi)部有一個(gè)特別的名稱，它就是BIO，全稱是Background IO，意思是在背后默默干活的 IO 線程。不過內(nèi)存回收本身并不是什么 IO 操作，只是 CPU 的計(jì)算消耗可能會(huì)比較大而已。

異步線程演進(jìn)之路

實(shí)現(xiàn)懶惰刪除時(shí)，它并不是一開始就想到了異步線程。最初的嘗試是在主線程里，使用類似于字典漸進(jìn)式搬遷那樣來實(shí)現(xiàn)漸進(jìn)式刪除回收。懶惰刪除是采用類似于 scan 操作的方法，通過遍歷第一維數(shù)組來逐步刪除回收第二維鏈表的內(nèi)容，等到所有鏈表都回收完了，再一次性回收第一維數(shù)組。這樣也可以達(dá)到刪除大對(duì)象時(shí)不阻塞主線程的效果。

但是說起來容易做起來卻很難。漸進(jìn)式回收需要仔細(xì)控制回收頻率，它不能回收的太猛，這會(huì)導(dǎo)致 CPU 資源占用過多，也不能回收的蝸牛慢，因?yàn)閮?nèi)存回收不及時(shí)可能導(dǎo)致內(nèi)存持續(xù)增長(zhǎng)。

Antirez 需要采用合適的自適應(yīng)算法來控制回收頻率。他首先想到的是檢測(cè)內(nèi)存增長(zhǎng)的趨勢(shì)是增長(zhǎng) (+1) 還是下降 (-1) 來漸進(jìn)式調(diào)整回收頻率系數(shù)，這樣的自適應(yīng)算法實(shí)現(xiàn)也很簡(jiǎn)單。但是測(cè)試后發(fā)現(xiàn)在服務(wù)繁忙的時(shí)候，QPS 會(huì)下降到正常情況下 65% 的水平，這點(diǎn)非常致命。

所以 Antirez 才使用了如今使用的方案——異步線程。異步線程這套方案就簡(jiǎn)單多了，釋放內(nèi)存不用為每種數(shù)據(jù)結(jié)構(gòu)適配一套漸進(jìn)式釋放策略，也不用搞個(gè)自適應(yīng)算法來仔細(xì)控制回收頻率。

不過使用異步線程也是有代價(jià)的，主線程和異步線程之間在內(nèi)存回收器 (jemalloc) 的使用上存在競(jìng)爭(zhēng)。這點(diǎn)競(jìng)爭(zhēng)消耗是可以忽略不計(jì)的，因?yàn)?Redis 的主線程在內(nèi)存的分配與回收上花的時(shí)間相對(duì)整體運(yùn)算時(shí)間而言是極少的。

異步線程方案相當(dāng)復(fù)雜，具體可參閱引用資料。

2.2 flush

Redis 提供了 flushdb 和 flushall 指令，用來清空數(shù)據(jù)庫(kù)，這也是極其緩慢的操作。

Redis 4.0 同樣給這兩個(gè)指令也帶來了異步化，在指令后面增加 async 參數(shù)就可以將整棵大樹拔起，扔給后臺(tái)線程慢慢焚燒。

> flushall async

OK

2.3 異步隊(duì)列

Redis4.0，主線程將對(duì)象的引用從「大樹」中摘除后，會(huì)將這個(gè) key 的內(nèi)存回收操作包裝成一個(gè)任務(wù)，塞進(jìn)異步任務(wù)隊(duì)列，后臺(tái)線程會(huì)從這個(gè)異步隊(duì)列中取任務(wù)。任務(wù)隊(duì)列被主線程和異步線程同時(shí)操作，所以必須是一個(gè)線程安全的隊(duì)列。

不是所有的 unlink 操作都會(huì)延后處理，如果對(duì)應(yīng) key 所占用的內(nèi)存很小，延后處理就沒有必要了，這時(shí)候 Redis 會(huì)將對(duì)應(yīng)的 key 內(nèi)存立即回收，跟 del 指令一樣。

2.4 AOF Sync很慢的問題

Redis需要每秒一次（可配置）同步AOF日志到磁盤，確保消息盡量不丟失，需要調(diào)用sync函數(shù)，這個(gè)操作會(huì)比較耗時(shí)，會(huì)導(dǎo)致主線程的效率下降，所以Redis也將這個(gè)操作移到異步線程來完成。

執(zhí)行AOF Sync操作的線程是一個(gè)獨(dú)立的異步線程，和前面的懶惰刪除線程不是一個(gè)線程，同樣它也有一個(gè)屬于自己的任務(wù)隊(duì)列，隊(duì)列里只用來存放AOF Sync任務(wù)。

2.5 更多異步刪除點(diǎn)

Redis 回收內(nèi)存除了 del 指令和 flush 之外，還會(huì)存在于在 key 的過期、LRU 淘汰、rename 指令以及從庫(kù)全量同步時(shí)接受完 rdb 文件后會(huì)立即進(jìn)行的 flush 操作。

Redis4.0 為這些刪除點(diǎn)也帶來了異步刪除機(jī)制，打開這些點(diǎn)需要額外的配置選項(xiàng)。

• slave-lazy-flush 從庫(kù)接受完 rdb 文件后的 flush 操作
• lazyfree-lazy-eviction 內(nèi)存達(dá)到 maxmemory 時(shí)進(jìn)行淘汰
• lazyfree-lazy-expire key 過期刪除
• lazyfree-lazy-server-del rename 指令刪除 destKey

3. 過期淘汰配置

當(dāng) Redis 已使用內(nèi)存超出物理內(nèi)存限制時(shí)，內(nèi)存中的數(shù)據(jù)會(huì)開始和磁盤產(chǎn)生頻繁的交換 (swap)，交換會(huì)讓 Redis 的性能急劇下降，而此時(shí)Redis的存取效率簡(jiǎn)直是龜速（基本上等于不可用）。在生產(chǎn)環(huán)境中這是不允許的，為了限制最大使用內(nèi)存，Redis 提供了配置參數(shù) maxmemory 來限制內(nèi)存超出期望大小。

那如果實(shí)際內(nèi)存超出 maxmemory 時(shí)該怎么辦？

Redis提供了幾種可選策略 (maxmemory-policy) 來讓用戶自己決定該如何騰出新的空間以繼續(xù)提供讀寫服務(wù)。

redis.conf中配置

maxmemory <bytes> #最大內(nèi)存（單位字節(jié)）

maxmemory-policy noeviction #默認(rèn)

小結(jié)

• volatile-xxx 策略只會(huì)針對(duì)帶過期時(shí)間的 key 進(jìn)行淘汰
• allkeys-xxx 策略會(huì)對(duì)所有的 key 進(jìn)行淘汰

那該如何抉擇呢？

如果你只是拿 Redis 做緩存，那最好使用 allkeys-xxx，客戶端寫緩存時(shí)不必?cái)y帶過期時(shí)間。

如果你還想同時(shí)具備持久化功能，那就使用 volatile-xxx 策略，好處就是，沒有設(shè)置過期時(shí)間的 key 不會(huì)被 LRU 算法淘汰

4. LRU 算法

實(shí)現(xiàn) LRU（最近最少） 算法除了需要 key/value 字典外，還需要附加一個(gè)鏈表，鏈表中的元素按照一定的順序進(jìn)行排列。

當(dāng)空間滿的時(shí)候，會(huì)踢掉鏈表尾部的元素。當(dāng)字典的某個(gè)元素被訪問時(shí)，它在鏈表中的位置會(huì)被移動(dòng)到表頭。所以鏈表的元素排列順序就是元素最近被訪問的時(shí)間順序。

4.1 近似 LRU 算法

Redis 使用的是一種近似 LRU 算法，它跟 LRU 算法還不太一樣。之所以不使用 LRU 算法，是因?yàn)樾枰拇罅康念~外的內(nèi)存，需要對(duì)現(xiàn)有的數(shù)據(jù)結(jié)構(gòu)進(jìn)行較大的改造。近似 LRU 算法則很簡(jiǎn)單，在現(xiàn)有數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上使用隨機(jī)采樣法來淘汰元素，能達(dá)到和 LRU 算法非常近似的效果。

Redis 為實(shí)現(xiàn)近似 LRU 算法，它給每個(gè) key 增加了一個(gè)額外的小字段，這個(gè)字段的長(zhǎng)度是 24 個(gè) bit，也就是最后一次被訪問的時(shí)間戳。

前面講過key 過期方式分為集中處理和懶惰處理，LRU 淘汰不一樣，它的處理方式只有懶惰處理。當(dāng) Redis 執(zhí)行寫操作時(shí)，發(fā)現(xiàn)內(nèi)存超出 maxmemory，就會(huì)執(zhí)行一次 LRU 淘汰算法。這個(gè)算法也很簡(jiǎn)單，就是隨機(jī)采樣（可以通過maxmemory-policy配置）出 5個(gè) key，然后淘汰掉最舊的 key，如果淘汰后內(nèi)存還是超出 maxmemory，那就繼續(xù)隨機(jī)采樣淘汰，直到內(nèi)存低于 maxmemory為止。

下面是隨機(jī) LRU 算法和嚴(yán)格 LRU 算法的效果對(duì)比圖：綠色部分是新加入的 key，深灰色部分是老舊的 key，淺灰色部分是通過 LRU 算法淘汰掉的 key。可以看出采樣數(shù)量越大，近似 LRU 算法的效果越接近嚴(yán)格 LRU 算法。同時(shí) Redis3.0 在算法中增加了淘汰池，進(jìn)一步提升了近似 LRU 算法的效果。

淘汰池是一個(gè)數(shù)組，它的大小是 maxmemory_samples，在每一次淘汰循環(huán)中，新隨機(jī)出來的 key 列表會(huì)和淘汰池中的 key 列表進(jìn)行融合，淘汰掉最舊的一個(gè) key 之后，保留剩余較舊的 key 列表放入淘汰池中留待下一個(gè)循環(huán)。

5. LRU

Redis 4.0 里引入了一個(gè)新的淘汰策略 —— LFU （Least Frequently Used）模式，作者認(rèn)為它比 LRU 更加優(yōu)秀。它表示按最近的訪問頻率進(jìn)行淘汰，它比 LRU 更加精準(zhǔn)地表示了一個(gè) key 被訪問的熱度。

它淘汰策略配置參數(shù)maxmemory-policy增加了 2 個(gè)選項(xiàng)，分別是 volatile-lfu 和 allkeys-lfu，分別是對(duì)帶過期時(shí)間的 key 進(jìn)行 lfu 淘汰以及對(duì)所有的 key 執(zhí)行 lfu 淘汰算法。

如果一個(gè) key 長(zhǎng)時(shí)間不被訪問，只是剛剛偶然被用戶訪問了一下，那么在使用 LRU 算法下它是不容易被淘汰的，因?yàn)?LRU 算法認(rèn)為當(dāng)前這個(gè) key 是很熱的。而 LFU 是需要追蹤最近一段時(shí)間的訪問頻率，如果某個(gè) key 只是偶然被訪問一次是不足以變得很熱的，它需要在近期一段時(shí)間內(nèi)被訪問很多次才有機(jī)會(huì)被認(rèn)為很熱。

Redis 的所有對(duì)象結(jié)構(gòu)頭中都有一個(gè) 24bit 的字段，這個(gè)字段用來記錄對(duì)象的「熱度」。

// redis 的對(duì)象頭
typedef struct redisObject {
    unsigned type:4; // 對(duì)象類型如 zset/set/hash 等等
    unsigned encoding:4; // 對(duì)象編碼如 ziplist/intset/skiplist 等等
    unsigned lru:24; // 對(duì)象的「熱度」
    int refcount; // 引用計(jì)數(shù)
    void *ptr; // 對(duì)象的 body
}robj;

5.1 LRU 模式

lru 字段存儲(chǔ)的是 Redis 時(shí)鐘server.lruclock，Redis 時(shí)鐘是一個(gè) 24bit 的整數(shù)，默認(rèn)是 Unix 時(shí)間戳對(duì) 2^24 取模的結(jié)果，大約 97 天清零一次。當(dāng)某個(gè) key 被訪問一次，它的對(duì)象頭的 lru 字段值就會(huì)被更新為server.lruclock，該值一直是遞增的，通過這個(gè)邏輯就可以精準(zhǔn)計(jì)算出對(duì)象多長(zhǎng)時(shí)間沒有被訪問——對(duì)象的空閑時(shí)間。如果超過server.lruclock折返了。

有了對(duì)象的空閑時(shí)間，就可以相互之間進(jìn)行比較誰新誰舊，隨機(jī) LRU 算法靠的就是比較對(duì)象的空閑時(shí)間來決定誰該被淘汰了。

默認(rèn) Redis 時(shí)鐘值每毫秒更新一次，在定時(shí)任務(wù)serverCron里主動(dòng)設(shè)置，在serverCron里面其實(shí)有很多很多定時(shí)任務(wù)，比如大型 hash 表的漸進(jìn)式遷移、過期 key 的主動(dòng)淘汰、觸發(fā) bgsave、bgaofrewrite 等等。

為什么 Redis 要緩存系統(tǒng)時(shí)間戳？

在java中我們使用System.currentTimeInMillis()，而Redis 不能這樣，因?yàn)槊恳淮潍@取系統(tǒng)時(shí)間戳都是一次系統(tǒng)調(diào)用，系統(tǒng)調(diào)用相對(duì)來說是比較費(fèi)時(shí)間的，這樣的消耗對(duì)redis而言是傷不起的，所以獲取時(shí)間都直接從緩存中直接拿。

5.2 LFU 模式

lru 字段 24 個(gè) bit 用來存儲(chǔ)兩個(gè)值，分別是ldt(last decrement time)和logc(logistic counter)。

logc是 8 個(gè) bit，用來存儲(chǔ)訪問頻次（最大整數(shù)值為 255）。存儲(chǔ)頻次遠(yuǎn)遠(yuǎn)不夠（太?。?，所以這 8 個(gè) bit 存儲(chǔ)的是頻次的對(duì)數(shù)值，并且這個(gè)值還會(huì)隨時(shí)間衰減。如果它的值比較小，就很容易被回收，為了確保新創(chuàng)建的對(duì)象不被回收，新對(duì)象的初始化默認(rèn)是LFU_INIT_VAL=5。

ldt 是 16 個(gè)位，用來存儲(chǔ)上一次 logc 的更新時(shí)間（精度不可能很高），它取的是分鐘時(shí)間戳對(duì) 2^16 進(jìn)行取模，大約每隔 45 天就會(huì)折返。同 LRU 模式一樣，我們也可以使用這個(gè)邏輯計(jì)算出對(duì)象的空閑時(shí)間，只不過精度是分鐘級(jí)別的。

server.unixtime 是當(dāng)前 redis 記錄的系統(tǒng)時(shí)間戳，和 server.lruclock 一樣，它也是每毫秒更新一次。

// nowInMinutes
// server.unixtime 為 redis 緩存的系統(tǒng)時(shí)間戳
unsigned long LFUGetTimeInMinutes(void) {
    return (server.unixtime/60) & 65535;
}
// idle_in_minutes
unsigned long LFUTimeElapsed(unsigned long ldt) {
    unsigned long now = LFUGetTimeInMinutes();
    if (now >= ldt) return now-ldt; // 正常比較
    return 65535-ldt+now; // 折返比較
}

ldt 的值不是在對(duì)象被訪問時(shí)更新的，它在 Redis 的淘汰邏輯進(jìn)行時(shí)進(jìn)行更新，淘汰邏輯只會(huì)在內(nèi)存達(dá)到 maxmemory 的設(shè)置時(shí)才會(huì)觸發(fā)，在每一個(gè)指令的執(zhí)行之前都會(huì)觸發(fā)。每次淘汰都是采用隨機(jī)策略，隨機(jī)挑選若干個(gè) key，更新這個(gè) key 的「熱度」，淘汰掉「熱度」最低的。因?yàn)?Redis 采用的是隨機(jī)算法，如果 key 比較多的話，那么 ldt 更新的可能會(huì)比較慢。不過既然它是分鐘級(jí)別的精度，也沒有必要更新的過于頻繁。

ldt 更新的同時(shí)也會(huì)一同衰減 logc 的值，衰減也有特定的算法。它將現(xiàn)有的 logc 值減去對(duì)象的空閑時(shí)間 (分鐘數(shù)) 除以一個(gè)衰減系數(shù)，默認(rèn)這個(gè)衰減系數(shù)lfu_decay_time是 1。如果這個(gè)值大于 1，那么就會(huì)衰減的比較慢。如果它等于零，那就表示不衰減，它是可以通過配置參數(shù)lfu_decay_time進(jìn)行配置。

logc 的更新和 LRU 模式的 lru 字段一樣，都會(huì)在 key 每次被訪問的時(shí)候更新，只不過它的更新不是簡(jiǎn)單的+1，而是采用概率法進(jìn)行遞增，因?yàn)?logc 存儲(chǔ)的是訪問計(jì)數(shù)的對(duì)數(shù)值，不能直接+1。

總結(jié)，通過LFU 和LRU的介紹，我們知道redis的設(shè)計(jì)有多優(yōu)秀，不浪費(fèi)一丁點(diǎn)內(nèi)存！

以上為個(gè)人經(jīng)驗(yàn)，希望能給大家一個(gè)參考，也希望大家多多支持本站。

美國(guó)穩(wěn)定服務(wù)器

版權(quán)聲明：本站文章來源標(biāo)注為YINGSOO的內(nèi)容版權(quán)均為本站所有，歡迎引用、轉(zhuǎn)載，請(qǐng)保持原文完整并注明來源及原文鏈接。禁止復(fù)制或仿造本網(wǎng)站，禁止在非www.sddonglingsh.com所屬的服務(wù)器上建立鏡像，否則將依法追究法律責(zé)任。本站部分內(nèi)容來源于網(wǎng)友推薦、互聯(lián)網(wǎng)收集整理而來，僅供學(xué)習(xí)參考，不代表本站立場(chǎng)，如有內(nèi)容涉嫌侵權(quán)，請(qǐng)聯(lián)系alex-e#qq.com處理。