2023-07-01：redis過期策略都有哪些？LRU 算法知道嗎？

答案2023-07-01：

緩存淘汰算法（過期策略）

當Redis的內存超出物理內存限制時，內存中的數(shù)據(jù)就會頻繁地與磁盤進行交換，這個過程叫做交換（swap）。由于交換的高開銷，Redis的性能會急劇下降。對于訪問頻率較高的Redis實例來說，這樣低效的存取效率幾乎等同于不可用。

maxmemory

在生產(chǎn)環(huán)境中，我們嚴禁Redis發(fā)生交換行為。為了限制Redis的最大內存使用量，Redis提供了一個配置參數(shù)maxmemory，用于設置期望的最大內存大小。

當實際內存超出maxmemory限制時，Redis提供了幾種可選策略（maxmemory-policy），供用戶自行選擇如何釋放空間以便繼續(xù)提供讀寫服務。

• ??noeviction: 這種策略不會繼續(xù)為寫請求提供服務（DEL請求可以繼續(xù)提供服務），但讀請求可以繼續(xù)進行。這保證不會丟失數(shù)據(jù)，但會導致在線業(yè)務無法持續(xù)進行。這是默認的淘汰策略。

• ??volatile-lru: 該策略嘗試淘汰設置了過期時間的鍵，優(yōu)先淘汰最近最少使用的鍵。沒有設置過期時間的鍵不會被淘汰，以確保持久化數(shù)據(jù)不會突然丟失。

• ??volatile-ttl: 與前面的策略相似，但淘汰的依據(jù)是鍵的剩余生存時間（TTL）值，TTL越小的鍵優(yōu)先被淘汰。

• ??volatile-random: 與前面的策略類似，但是淘汰過期鍵集合中的鍵時是隨機的。

• ??allkeys-lru: 與volatile-lru不同，該策略淘汰的是整個鍵集合，而不僅限于過期鍵集合。這意味著沒有設置過期時間的鍵也會被淘汰。

• ??allkeys-random: 與前面的策略類似，但淘汰的鍵是整個鍵集合中的隨機鍵。

策略中的"volatile-xxx"僅針對帶有過期時間的鍵進行淘汰，而"allkeys-xxx"策略會對所有鍵進行淘汰。如果您只是將Redis用作緩存，應該使用"allkeys-xxx"策略，客戶端在寫入緩存時不需要提供過期時間。如果您還希望同時使用Redis的持久化功能，則應使用"volatile-xxx"策略，這樣可以保留未設置過期時間的鍵，它們將被視為永久鍵而不會被LRU算法淘汰。

LRU 算法

LRU算法的實現(xiàn)通常涉及兩個數(shù)據(jù)結構：字典和鏈表。字典用于以鍵值對的形式存儲數(shù)據(jù)，而鏈表用于維護鍵的訪問順序。鏈表中的元素按照最近訪問的時間順序排列，最近訪問的元素位于鏈表的頭部，而不常使用的元素位于尾部。當緩存空間已滿時，將會踢掉鏈表尾部的元素。

鏈表尾部的元素是不被頻繁訪問的，因此在空間滿時會被移除。而鏈表頭部的元素是最近被訪問過的，暫時不會被移除。

近似 LRU 算法

Redis使用的是近似LRU算法，與LRU算法有一些不同。由于LRU算法需要消耗大量的額外內存并需要對數(shù)據(jù)結構進行較大改造，所以Redis選擇使用近似LRU算法。

近似LRU算法在現(xiàn)有數(shù)據(jù)結構的基礎上采用了隨機采樣法來淘汰元素，能夠達到非常接近LRU算法的效果。為了實現(xiàn)近似LRU算法，Redis為每個鍵增加了一個額外的小字段，該字段的長度為24個比特，表示最后一次訪問該鍵的時間戳。

當Redis執(zhí)行寫操作時，如果發(fā)現(xiàn)內存超出maxmemory限制，它會執(zhí)行一次LRU淘汰算法。該算法非常簡單：隨機選擇5個鍵（可配置為maxmemory-samples數(shù)），然后淘汰最舊的鍵。如果淘汰后仍然超出maxmemory，Redis將繼續(xù)隨機采樣淘汰，直到內存低于maxmemory為止。

maxmemory-policy的配置決定了采樣的方式。若為"allkeys"，則從所有鍵的字典中進行隨機采樣；若為"volatile"，則從帶有過期時間的鍵字典中隨機采樣。每次采樣的鍵數(shù)量由maxmemory-samples配置確定，默認為5。

采樣數(shù)量越大，近似LRU算法的效果越接近嚴格的LRU算法。

此外，Redis 3.0引入了淘汰池的概念，新的算法會維護一個候選池（大小為16）。池中的數(shù)據(jù)按訪問時間排序，首次隨機選取的鍵將放入池中。隨后的每次隨機選取只有在訪問時間小于池中最小時間時，才會放入池中，直到池滿為止。當池滿時，如果有新的鍵需要放入，將移除最后訪問時間最大（最近被訪問）的鍵。這進一步提升了近似LRU算法的效果。