我是風筝，公衆号「古時的風筝」。 文章會收錄在 JavaNewBee 中，更有 Java 後端知識圖譜，從小白到大牛要走的路都在裡面。
那天我在 LeetCode 上刷到一道 LRU 緩存機制的問題，第 146 題，難度為中等，題目如下。
運用你所掌握的資料結構，設計和實作一個 LRU (最近最少使用) 緩存機制。它應該支援以下操作： 擷取資料 get 和 寫入資料 put 。
擷取資料 get(key) - 如果關鍵字 (key) 存在于緩存中，則擷取關鍵字的值（總是正數），否則傳回 -1。
寫入資料 put(key, value) - 如果關鍵字已經存在，則變更其資料值；如果關鍵字不存在，則插入該組「關鍵字/值」。當緩存容量達到上限時，它應該在寫入新資料之前删除最久未使用的資料值，進而為新的資料值留出空間。
LRU 全名 Least Recently Used，意為最近最少使用，注重最近使用的時間，是常用的緩存淘汰政策。為了加快通路速度，緩存可以說無處不在，無論是計算機内部的緩存，還是 Java 程式中的 JVM 緩存，又或者是網站架構中的 Redis 緩存。緩存雖然好用，但緩存内容可不能無限增加，要受存儲空間的限制，當空間不足的時候，隻能選擇删除一部分内容。那删除哪些内容呢，這就涉及到淘汰政策了，而 LRU 應該是各種緩存架構最常用的淘汰政策了。也就是當記憶體不足，新内容進來時，會将最近最少使用的元素删掉。
我一看這題我熟啊，當初看
LinkedHashMap
源碼的時候，源碼中有注釋提到了它可以用來實作 LRU 緩存。原文是這麼寫的。
A special {@link #LinkedHashMap(int,float,boolean) constructor} is provided to create a linked hash map whose order of iteration is the order in which its entries were last accessed, from least-recently accessed to most-recently (<i>access-order</i>). This kind of map is well-suited to building LRU caches.
翻譯過來大意如下：
通過一個特殊的構造函數，三個參數的這種，最後一個布爾值參數表示是否要維護最近通路順序，如果是 true 的話會維護最近通路的順序，如果是 false 的話，隻會維護插入順序。保證維護最近最少使用的順序。
LinkedHashMap
這種結構非常适合構造 LRU 緩存。
當我看到這段注釋的時候，特意去查了一下用
LinkedHashMap
實作 LRU 的方法。
public class LRUCache {
private int cacheSize;
private LinkedHashMap<Integer,Integer> linkedHashMap;
public LRUCache(int capacity) {
this.cacheSize = capacity;
linkedHashMap = new LinkedHashMap<Integer,Integer>(capacity,0.75F,true){
@Override
protected boolean removeEldestEntry(Map.Entry eldest) {
return size()>cacheSize;
}
};
}
public int get(int key) {
return this.linkedHashMap.getOrDefault(key,-1);
}
public void put(int key, int value) {
this.linkedHashMap.put(key,value);
}
}
這是根據這道題的寫法，如果不限定這個題目的話，可以讓
LRUCache
繼承
LinkedHashMap
，然後再重寫
removeEldestEntry
方法即可。
看到沒，就是這麼簡單，
LinkedHashMap
已經完美實作了 LRU，這個方法是在插入鍵值對的時候調用的，如果傳回 true，就删除最近最少使用的元素，是以隻要判斷
size()
是否大于
cacheSize
即可，
cacheSize
就是緩存的最大容量。
送出，順利通過，完美！
LRU 簡單實作
你以為這麼簡單就完了嗎，并沒有。當我檢視官方題解的時候，發現裡面是這麼說的。
在語言中，同樣有類似的資料結構Java
。這些做法都不會符合面試官的要求。LinkedHashMap
什麼，這麼完美還不符合面試官要求，面試官是什麼要求呢？面試官的要求是考考你 LRU 的原理，讓你自己實作一個。
那咱們就由
LinkedHashMap
介紹一下最基礎的 LRU 實作。簡單概括
LinkedHashMap
的實作原理就是
HashMap
+雙向連結清單的結合。
雙向連結清單用來維護元素通路順序，将最近被通路（也就是調動 get 方法）的元素放到連結清單尾部，一旦超過緩存容量的時候，就從連結清單頭部删除元素，用雙向連結清單能保證元素移動速度最快，假設通路了連結清單中的某個元素，隻要把這個元素移動連結清單尾部，然後修改這個元素的 prev 和 next 節點的指向即可。
雙向連結清單節點的類型的基本屬性如下：
static class Node {
/**
* 緩存 key
*/
private int key;
/**
* 緩存值
*/
private int value;
/**
* 目前節點的前驅節點
*/
private Node prev;
/**
* 目前節點的後驅節點
*/
private Node next;
public Node(int key, int value) {
this.key = key;
this.value = value;
}
}
HashMap
用來存儲 key 值對應的節點，為的是快速定位 key 值在連結清單中的位置，我們都知道，這是因為
HashMap
的 get 方法的時間複雜度為 O(1)。而如果不借助
HashMap
，那這個過程可就慢了。如果要想找一個 key，要從連結清單頭或連結清單尾周遊才行。
按上圖的展示， head 是連結清單頭，也是最長時間未被通路的節點，tail 是最近被通路的元素，假設緩存最大容量是 4 。
插入元素
當有新元素被插入，先判斷緩存容量是否超過最大值了，如果超過，就将頭節點删除，然後将頭結點的 next 節點設定為 head，同時删除
HashMap
中對應的 key。然後将插入的元素放到連結清單尾部，設定此元素為尾節，并在
HashMap
中儲存下來。
如果沒超過最大容量，直接插入到尾部。
通路元素
當通路其中的某個 key 時，先從
HashMap
中快速找到這個節點。如果這個 key 不是尾節點，那麼就将此節的前驅節點的 next 指向此節點的後驅節點，此節點的後驅節點的 prev 指向此節點的前驅節點。 同時，将這個節點移動到尾部，并将它設定為尾結點。
下面這個動圖，示範了 get key2 時的移動情況。
删除元素
如果是删除頭節點，則将此節點的後驅節點的 prev 設定為 null，并将它設定為 head，同時，删除
HashMap
中此節點的 key。
如果是删除尾節點，則将此節點的前驅節點的 next 設定為 null，并将它設定為 tail，同時，删除
HashMap
如果是中間節點，則将此節的前驅節點的 next 指向此節點的後驅節點，此節點的後驅節點的 prev 指向此節點的前驅節點，同時，删除
HashMap
動手實作
思路就是這麼一個思路，有了這個思路我撸起袖子開始寫代碼，由于自身算法比較渣，而且又好長時間不刷算法，是以我的慘痛經曆如下。
先是執行出錯，後來又解答錯誤，頓時開始懷疑人生，懷疑智商。最後發現，确實是智商問題。
總歸就是這麼一個意思，你也去寫一遍試試吧，看看效果如何。原題位址：https://leetcode-cn.com/problems/lru-cache/
除了 LRU 還有 LFU
還有一種常用的淘汰政策叫做 LFU(Least Frequently Used)，最不經常使用。想比于LFU 更加注重通路頻次。在 LRU 的基礎上增加了通路頻次。
看下圖，舉個例子來說，假設現在 put 進來一個鍵值對，并且超過了最大的容量，那就要删除一個鍵值對。假設 key2 是在 5 分鐘之前通路過一次，而 key1 是在 10 分鐘之前通路過，以 LRU 的政策來說，就會删除頭節點，也就是圖中的 key1。但是如果是 LFU 的話，會記錄每個 key 的通路頻次，雖然 key2 是最近一次通路晚于 key1，但是它的頻次比 key1 少，那要淘汰一個 key 的話，還是要淘汰 key2 的。隻是舉個例子，真正的 LFU 資料結構比 LRU 要複雜。
看 LeetCode 上的難度等級就知道了，LFU 也有一道對應的題目，位址：https://leetcode-cn.com/problems/lfu-cache/，它的難度是困難，而 LRU 的難度是中等。
還有一種 FIFO ，先進先出政策，先進入緩存的會先被淘汰，比起上面兩種，它的命中率比較低。
優缺點分析
LRU的優點：LRU相比于 LFU 而言性能更好一些，因為它算法相對比較簡單，不需要記錄通路頻次，可以更好的應對突發流量。
LRU的缺點：雖然性能好一些，但是它通過曆史資料來預測未來是局限的，它會認為最後到來的資料是最可能被再次通路的，進而給與它最高的優先級。有些非熱點資料被通路過後，占據了高優先級，它會在緩存中占據相當長的時間，進而造成空間浪費。
LFU的優點：LFU根據通路頻次通路，在大部分情況下，熱點資料的頻次肯定高于非熱點資料，是以它的命中率非常高。
LFU的缺點：LFU 算法相對比較複雜，性能比 LRU 差。有問題的是下面這種情況，比如前一段時間微網誌有個熱點話題熱度非常高，就比如那種可以讓微網誌短時間停止服務的，于是趕緊緩存起來，LFU 算法記錄了其中熱點詞的通路頻率，可能高達十幾億，而過後很長一段時間，這個話題已經不是熱點了，新的熱點也來了，但是，新熱點話題的熱度沒辦法到達十幾億，也就是說通路頻次沒有之前的話題高，那之前的熱點就會一直占據着緩存空間，長時間無法被剔除。
針對以上這些問題，現有的緩存架構都會做一系列改進。比如 JVM 本地緩存 Caffeine，或者分布式緩存 Redis。
Caffeine 中的緩存淘汰政策
Caffeine 是一款高性能的 JVM 緩存架構，是目前 Spring 5.x 中的預設緩存架構，之前版本是用的 Guava Cache。
為了改進上述 LRU 和 LFU 存在的問題，前Google工程師在 TinyLfu的基礎上發明了 W-TinyLFU 緩存算法。Caffine 就是基于此算法開發的。
Caffeine 因使用 Window TinyLfu 回收政策，提供了一個近乎最佳的命中率。
TinyLFU維護了近期通路記錄的頻率資訊，作為一個過濾器，當新記錄來時，隻有滿足TinyLFU要求的記錄才可以被插入緩存。
TinyLFU借助了資料流Sketching技術，它可以用小得多的空間存放頻次資訊。TinyLFU采用了一種基于滑動視窗的時間衰減設計機制，借助于一種簡易的 reset 操作：每次添加一條記錄到Sketch的時候，都會給一個計數器上加 1，當計數器達到一個尺寸 W 的時候，把所有記錄的 Sketch 數值都除以 2，該 reset 操作可以起到衰減的作用 。
W-TinyLFU主要用來解決一些稀疏的突發通路元素。在一些數目很少但突發通路量很大的場景下，TinyLFU将無法儲存這類元素，因為它們無法在給定時間内積累到足夠高的頻率。是以 W-TinyLFU 就是結合 LFU 和LRU，前者用來應對大多數場景，而 LRU 用來處理突發流量。
在處理頻次記錄方面，采用 Bloom Filter，對于每個key，用 n 個 byte 每個存儲一個标志用來判斷 key 是否在集合中。原理就是使用 k 個 hash 函數來将 key 散列成一個整數。
在 W-TinyLFU 中使用 Count-Min Sketch 記錄 key 的通路頻次，而它就是布隆過濾器的一個變種。
Redis 中的緩存淘汰政策
Redis 支援如下 8 中淘汰政策，其中最後兩種 LFU 的是 4.0 版本之後新加的。
noeviction：當記憶體使用超過配置的時候會傳回錯誤，不會驅逐任何鍵
allkeys-lru：加入鍵的時候，如果過限，首先通過LRU算法驅逐最久沒有使用的鍵
volatile-lru：加入鍵的時候如果過限，首先從設定了過期時間的鍵集合中驅逐最久沒有使用的鍵
allkeys-random：加入鍵的時候如果過限，從所有key随機删除
volatile-random：加入鍵的時候如果過限，從過期鍵的集合中随機驅逐
volatile-ttl：從配置了過期時間的鍵中驅逐馬上就要過期的鍵
volatile-lfu：從所有配置了過期時間的鍵中驅逐使用頻率最少的鍵
allkeys-lfu：從所有鍵中驅逐使用頻率最少的鍵
最常用的就是兩種 LRU 和 兩種 LFU 的。
通過在 redis.conf 配置檔案中配置如下配置項，來設定最大容量和采用的緩存淘汰政策。
maxmemory 1024M
maxmemory-policy volatile-lru
Redis 中的 LRU
Redis使用的是近似LRU算法，它跟正常的LRU算法還不太一樣，它并不維護隊列，而是随機采樣法淘汰資料，每次随機選出5（預設）個key，從裡面淘汰掉最近最少使用的key。
通過配置
maxmemory-samples
設定随機采樣大小。
maxmemory-samples 5
LRU 算法會維護一個淘汰候選池（大小為16），池中的資料根據通路時間進行排序，第一次随機選取的key都會放入池中，随後每次随機選取的key隻有在通路時間小于池中最小的時間才會放入池中，直到候選池被放滿。當放滿後，如果有新的key需要放入，則将池中最後通路時間最大（最近被通路）的移除。當需要淘汰 key 的時候，則直接從池中選取最近通路時間最小（最久沒被通路）的 key 淘汰掉即可。
Redis 中的 LFU
LFU 算法是 4.0 之後才加入進來的。
上面 LRU 算法中會按照通路時間進行淘汰，這個通路時間是 Redis 中維護的一個 24 位時鐘，也就是目前時間戳，每個 key 所在的對象也維護着一個時鐘字段，當通路一個 key 的時候，會拿到目前的全局時鐘，然後将這個時鐘值賦給這個 key 所在對象維護的時鐘字段，之後的按時間比較就是根據這個時鐘字段。
而 LFU 算法就是利用的這個字段，24位分成兩部分，前16位還代表時鐘，後8位代表一個計數器。16位的情況下如果還按照秒為機關就會導緻不夠用，是以一般這裡以時鐘為機關。而後8位表示目前key對象的通路頻率，8位隻能代表255，但是redis并沒有采用線性上升的方式，而是通過一個複雜的公式，通過配置兩個參數來調整資料的遞增速度。
lfu-log-factor 10
lfu-decay-time 1
在影響因子 lfu-log-factor 為10的情況下，經過1百萬次命中才能達到 255。
本文完。
送給你
種一棵樹最好的時間是十年前，其次是現在。送給各位，也送給自己。
公衆号「古時的風筝」，Java 開發者，全棧工程師，人稱遲到小王子，bug 殺手，擅長解決問題。
一個兼具深度與廣度的程式員鼓勵師，本打算寫詩卻寫起了代碼的田園碼農！堅持原創幹貨輸出，你可選擇現在就關注我，或者看看曆史文章再關注也不遲。長按二維碼關注，跟我一起變優秀！
人生沒有回頭路，珍惜當下。