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

1. 過期策略

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

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

1.1 過期的 key 集合

redis 會將每個設置了過期時間的 key 放入到一個獨立的字典中，以后會定時遍歷這個字典來刪除到期的 key。

redis 采用兩種策略：

• 定時刪除是集中處理
• 惰性刪除是零散處理

1.2 定時掃描策略

Redis 默認會每秒進行十次過期掃描，過期掃描不會遍歷過期字典中所有的 key，而是采用了一種簡單的貪心策略。

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

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

如果Redis 實例中所有的 key （幾十萬個）在同一時間過期會怎樣？

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

當客戶端請求到來時（服務器如果正好進入過期掃描狀態(tài)），客戶端的請求將會等待至少 25ms 后才會進行處理，如果客戶端將超時時間設置的比較短，比如 10ms，那么就會出現(xiàn)大量的鏈接因為超時而關(guān)閉，業(yè)務端就會出現(xiàn)很多異常。而且這時你還無法從 Redis 的 slowlog 中看到慢查詢記錄，因為慢查詢指的是邏輯處理過程慢，不包含等待時間。

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

1.3 從庫的過期策略

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

因為指令同步是異步進行的，所以主庫過期的 key 的 del 指令沒有及時同步到從庫的話，會出現(xiàn)主從數(shù)據(jù)的不一致，主庫沒有的數(shù)據(jù)在從庫里還存在，分布式鎖的算法漏洞就是因為這個同步延遲產(chǎn)生的。

2. 懶惰刪除

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

為什么要懶惰刪除？

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

不過如果刪除的 key 是一個非常大的對象，那么刪除操作就會導致單線程卡頓，怎么破？

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

> unlink key

OK

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

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

2.1 異步線程

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

異步線程演進之路

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

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

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

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

不過使用異步線程也是有代價的，主線程和異步線程之間在內(nèi)存回收器 (jemalloc) 的使用上存在競爭。這點競爭消耗是可以忽略不計的，因為 Redis 的主線程在內(nèi)存的分配與回收上花的時間相對整體運算時間而言是極少的。

異步線程方案相當復雜，具體可參閱引用資料。

2.2 flush

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

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

> flushall async

OK

2.3 異步隊列

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

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

2.4 AOF Sync很慢的問題

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

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

2.5 更多異步刪除點

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

Redis4.0 為這些刪除點也帶來了異步刪除機制，打開這些點需要額外的配置選項。

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

3. 過期淘汰配置

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

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

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

redis.conf中配置

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

maxmemory-policy noeviction #默認

小結(jié)

• volatile-xxx 策略只會針對帶過期時間的 key 進行淘汰
• allkeys-xxx 策略會對所有的 key 進行淘汰

那該如何抉擇呢？

如果你只是拿 Redis 做緩存，那最好使用 allkeys-xxx，客戶端寫緩存時不必攜帶過期時間。

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

4. LRU 算法

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

當空間滿的時候，會踢掉鏈表尾部的元素。當字典的某個元素被訪問時，它在鏈表中的位置會被移動到表頭。所以鏈表的元素排列順序就是元素最近被訪問的時間順序。

4.1 近似 LRU 算法

Redis 使用的是一種近似 LRU 算法，它跟 LRU 算法還不太一樣。之所以不使用 LRU 算法，是因為需要消耗大量的額外的內(nèi)存，需要對現(xiàn)有的數(shù)據(jù)結(jié)構(gòu)進行較大的改造。近似 LRU 算法則很簡單，在現(xiàn)有數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上使用隨機采樣法來淘汰元素，能達到和 LRU 算法非常近似的效果。

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

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

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

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

5. LRU

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

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

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

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

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

5.1 LRU 模式

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

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

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

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

在java中我們使用System.currentTimeInMillis()，而Redis 不能這樣，因為每一次獲取系統(tǒng)時間戳都是一次系統(tǒng)調(diào)用，系統(tǒng)調(diào)用相對來說是比較費時間的，這樣的消耗對redis而言是傷不起的，所以獲取時間都直接從緩存中直接拿。

5.2 LFU 模式

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

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

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

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

// nowInMinutes
// server.unixtime 為 redis 緩存的系統(tǒng)時間戳
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 的值不是在對象被訪問時更新的，它在 Redis 的淘汰邏輯進行時進行更新，淘汰邏輯只會在內(nèi)存達到 maxmemory 的設置時才會觸發(fā)，在每一個指令的執(zhí)行之前都會觸發(fā)。每次淘汰都是采用隨機策略，隨機挑選若干個 key，更新這個 key 的「熱度」，淘汰掉「熱度」最低的。因為 Redis 采用的是隨機算法，如果 key 比較多的話，那么 ldt 更新的可能會比較慢。不過既然它是分鐘級別的精度，也沒有必要更新的過于頻繁。

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

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

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

以上為個人經(jīng)驗，希望能給大家一個參考，也希望大家多多支持腳本之家。