緩存使用的是內存資源，而內存資源是非常寶貴的，要用有限的服務器資源支撐更多的業(yè)務，就必須讓那些訪問頻率不高的緩存刪除掉，為新的緩存騰出內存空間。這一課時，我們一起來看一下，緩存失效有哪些策略。

頁面置換算法

我們從一開始就提到，緩存技術在計算機系統設計中有著非常廣泛的應用，對應到操作系統中，就是緩存頁面的調度算法。

在操作系統中，文件的讀取會先分配一定的頁面空間，也就是我們說的 Page，使用頁面的時候首先去查詢空間是否有該頁面的緩存，如果有的話，則直接拿出來；否則就先查詢，頁面空間沒有滿，就把新頁面緩存起來，如果頁面空間滿了，就刪除部分頁面，方便新的頁面插入。

在操作系統的頁面空間中，對應淘汰舊頁面的機制不同，所以會有不同頁面調度方法，常見的有 FIFO、LRU、LFU 過期策略：

• FIFO（First In First Out，先進先出），根據緩存被存儲的時間，離當前最遠的數據優(yōu)先被淘汰；

• LRU（Least Recently Used，最近最少使用），根據最近被使用的時間，離當前最遠的數據優(yōu)先被淘汰；

• LFU（Least Frequently Used，最不經常使用），在一段時間內，緩存數據被使用次數最少的會被淘汰。

這三種策略也是經典的緩存淘汰策略，大部分緩存應用模型，都是基于這幾種策略實現的。

內存淘汰策略

操作系統的頁面置換算法，對應到分布式緩存中，就是緩存的內存淘汰策略，這里以 Redis 為例，進行分析。

當 Redis 節(jié)點分配的內存使用到達最大值以后，為了繼續(xù)提供服務，Redis 會啟動內存淘汰策略，以下的幾種策略參考官方文檔：

• noeviction，這是默認的策略，對于寫請求會拒絕服務，直接返回錯誤，這種策略下可以保證數據不丟失；

• allkeys-lru，這種策略操作的范圍是所有 key，使用 LRU 算法進行緩存淘汰；

• volatile-lru，這種策略操作的范圍是設置了過期時間的 key，使用 LRU 算法進行淘汰；

• allkeys-random，這種策略下操作的范圍是所有 key，會進行隨機淘汰數據；

• volatile-random，這種策略操作的范圍是設置了過期時間的 key，會進行隨機淘汰；

• volatile-ttl，這種策略操作的范圍是設置了過期時間的 key，根據 key 的過期時間進行淘汰，越早過期的越優(yōu)先被淘汰。

緩存過期策略

分布式緩存中的過期策略和內存淘汰策略又有一些不同，希望大家不要混淆，內存淘汰是緩存服務層面的操作，而過期策略定義的是具體緩存數據何時失效，下面一起來看一下。

我們都知道，Redis 是 key-value 數據庫，可以設置緩存 key 的過期時間，過期策略就是指當 Redis 中緩存的 key 過期了，Redis 如何處理。

Redis 中過期策略通常有以下三種。

• 定時過期

這是最常見也是應用最多的策略，為每個設置過期時間的 key 都需要創(chuàng)建一個定時器，到過期時間就會立即清除。這種方式可以立即刪除過期數據，避免浪費內存，但是需要耗費大量的 CPU 資源去處理過期的數據，可能影響緩存服務的性能。

• 惰性過期

可以類比懶加載的策略，這個就是懶過期，只有當訪問一個 key 時，才會判斷該 key 是否已過期，并且進行刪除操作。這種方式可以節(jié)省 CPU 資源，但是可能會出現很多無效數據占用內存，極端情況下，緩存中出現大量的過期 key 無法被刪除。

• 定期過期

這種方式是上面方案的整合，添加一個即將過期的緩存字典，每隔一定的時間，會掃描一定數量的 key，并清除其中已過期的 key。

合理的緩存配置，需要協調內存淘汰策略和過期策略，避免內存浪費，同時最大化緩存集群的吞吐量。另外，Redis 的緩存失效有一點特別關鍵，那就是如何避免大量主鍵在同一時間同時失效造成數據庫壓力過大的情況，對于這個問題在第 33 課時緩存穿透中有過描述，大家可以去擴展了解下。

實現一個 LRU 緩存

下面介紹一個高頻的面試問題：如何實現一個 LRU 算法，該算法的實現很多同學都聽過，但是不知道你還記不記得那句經典的格言，Talk is cheap，show me the code。很多人在寫代碼時一說就懂，一寫就錯，特別在面試時，常常要求你白板編程，脫離了 IDE 的幫助，更容易出現錯誤，所以我建議大家動手去實現一下。

在 Java 語言中實現 LUR 緩存，可以直接應用內置的 LinkedHashMap，重寫對應的 removeEldestEntry() 方法，代碼如下：

為什么重寫 LinkedHashMap 可以實現 LRU 緩存呢？

對于這個問題，我建議你可以查看一下 LinkedHashMap 的源碼實現，在原生的 removeEldestEntry 實現中，默認返回了 false，也就是永遠不會移除最“早”的緩存數據，只要擴展這個條件，緩存滿了移除最早的數據，是不是就實現了一個 LRU 策略？

在面試中，單純使用 LinkedHashMap 實現是不夠的，還會要求你使用原生的 Map 和雙向鏈表來實現。下面我簡單實現了一個參考代碼，這道題目在 Leetcode 上的編號是 146，也是劍指 offer 里的一道經典題，大家可以去力扣網站提交代碼試一下。

總結

這一課時的內容主要介紹了緩存的幾種失效策略，并且分享了一個面試中的高頻問題：LRU 緩存實現。

緩存過期的策略來自操作系統，在我們的專欄中，對很多知識的展開都來自計算機原理、網絡原理等底層技術，也從一個側面反映了計算機基礎知識的重要性。