從零開始手寫 redis（十）緩存淘汰LFU算法詳解

前言

java從零手寫實現redis（一）如何實現固定大小的緩存？

java從零手寫實現redis（三）redis expire 過期原理

java從零手寫實現redis（三）內存數據如何重啟不丟失？

java從零手寫實現redis（四）添加監聽器

java從零手寫實現redis（五）過期策略的另一種實現思路

java從零手寫實現redis（六）AOF 持久化原理詳解及實現

java從零手寫實現redis（七）LRU 緩存淘汰策略詳解

java從零開始手寫 redis（八）樸素 LRU 淘汰算法性能優化

本節一起來學習下另一個常用的緩存淘汰算法，LFU 最少使用頻次算法。

LFU 基礎知識

概念

LFU(Least Frequently Used)即最近最不常用.看名字就知道是個基於訪問頻次的一種算法。

LRU是基於時間的,會將時間上最不常訪問的數據給淘汰，在算法表現上是放到列表的頂部;LFU為將頻率上最不常訪問的數據淘汰.

既然是基於頻率的,就需要有存儲每個數據訪問的次數.

從存儲空間上,較LRU會多出一些持有計數的空間.

核心思想

如果一個數據在最近一段時間內使用次數很少，那麼在將來一段時間內被使用的可能性也很小。

實現思路

O(N) 的刪除

為了能夠淘汰最少使用的數據，個人第一直覺就是直接一個 HashMap<String, Interger>, String 對應 key 信息，Integer 對應次數。

每次訪問到就去+1，設置和讀取的時間複雜度都是 O(1)；不過刪除就比較麻煩了，需要全部遍歷對比，時間複雜度為 O(n);

O(logn) 的刪除

另外還有一種實現思路就是利用小頂堆+hashmap，小頂堆插入、刪除操作都能達到O(logn)時間複雜度，因此效率相比第一種實現方法更加高效。比如 TreeMap。

O(1) 的刪除

是否能夠更進一步優化呢？

其實 O(1) 的算法是有的，參見這篇 paper:

An O(1) algorithm for implementing the LFU cache eviction scheme

簡單說下個人的想法：

我們要想實現 O(1) 的操作，肯定離不開 Hash 的操作，我們 O(N) 的刪除中就實現了 O(1) 的 put/get。

但是刪除性能比較差，因為需要尋找次數最少的比較耗時。

private Map<K, Node> map; // key和數據的映射private Map<Integer, LinkedHashSet<Node>> freqMap; // 數據頻率和對應數據組成的鍊表class Node {    K key;    V value;    int frequency = 1;}

我們使用雙 Hash 基本上就可以解決這個問題了。

map 中存放 key 和節點之間的映射關係。put/get 肯定都是 O(1) 的。

key 映射的 node 中，有對應的頻率 frequency 信息；相同的頻率都會通過 freqMap 進行關聯，可以快速通過頻率獲取對應的鍊表。

刪除也變得非常簡單了，基本可以確定需要刪除的最低頻次是1，如果不是最多從 1...n 開始循環，最小 freq 選擇鍊表的第一個元素開始刪除即可。

至於鍊表本身的優先級，那麼可以根據 FIFO，或者其他你喜歡的方式。

paper 的核心內容介紹

他山之石，可以攻玉。

我們在實現代碼之前，先來讀一讀這篇 O(1) 的 paper。

介紹

本文的結構如下。

對LFU用例的描述，它可以證明優於其他緩存逐出算法

LFU緩存實現應支持的字典操作。 這些是確定策略運行時複雜度的操作

當前最著名的LFU算法及其運行時複雜度的描述

提出的LFU算法的說明； 每個操作的運行時複雜度為O（1）

LFU的用途

考慮用於HTTP協議的緩存網絡代理應用程式。

該代理通常位於Internet與用戶或一組用戶之間。

它確保所有用戶都能夠訪問Internet，並實現所有可共享資源的共享，以實現最佳的網絡利用率和響應速度。

這樣的緩存代理應該嘗試在可支配的有限數量的存儲或內存中最大化其可以緩存的數據量。

通常，在將靜態資源（例如圖像，CSS樣式表和javascript代碼）替換為較新版本之前，可以很容易地將它們緩存很長時間。

這些靜態資源或程式設計師所謂的「資產」幾乎包含在每個頁面中，因此緩存它們是最有益的，因為幾乎每個請求都將需要它們。

此外，由於要求網絡代理每秒處理數千個請求，因此應將這樣做所需的開銷保持在最低水平。

為此，它應該僅驅逐那些不經常使用的資源。

因此，應該將經常使用的資源保持在不那麼頻繁使用的資源上，因為前者已經證明自己在一段時間內是有用的。

當然，有一個說法與之相反，它說將來可能不需要大量使用的資源，但是我們發現在大多數情況下情況並非如此。

例如，頻繁使用頁面的靜態資源始終由該頁面的每個用戶請求。

因此，當內存不足時，這些緩存代理可以使用LFU緩存替換策略來驅逐其緩存中使用最少的項目。

LRU在這裡也可能是適用的策略，但是當請求模式使得所有請求的項目都沒有進入緩存並且以循環方式請求這些項目時，LRU將會失敗。

ps: 數據的循環請求，會導致 LRU 剛好不適應這個場景。

在使用LRU的情況下，項目將不斷進入和離開緩存，而沒有用戶請求訪問緩存。

但是，在相同條件下，LFU算法的性能會更好，大多數緩存項會導致緩存命中。

LFU算法的病理行為並非沒有可能。

我們不是在這裡提出LFU的案例，而是試圖證明如果LFU是適用的策略，那麼比以前發布的方法有更好的實現方法。

LFU緩存支持的字典操作

當我們談到緩存逐出算法時，我們主要需要對緩存數據進行3種不同的操作。

1. 在緩存中設置（或插入）項目
2. 檢索（或查找）緩存中的項目； 同時增加其使用計數（對於LFU）
3. 從緩存中逐出（或刪除）最少使用（或作為逐出算法的策略）

LFU算法的當前最著名的複雜性

在撰寫本文時，針對LFU緩存逐出策略的上述每個操作的最著名的運行時如下：

插入：O（log n）

查找：O（log n）

刪除：O（log n）

這些複雜度值直接從二項式堆實現和標準無衝突哈希表中獲得。

使用最小堆數據結構和哈希圖可以輕鬆有效地實施LFU緩存策略。

最小堆是基於（項目的）使用計數創建的，並且通過元素的鍵為哈希表建立索引。

無衝突哈希表上的所有操作的順序均為O（1），因此LFU緩存的運行時間由最小堆上的操作的運行時間控制。

將元素插入高速緩存時，它將以1的使用計數進入，由於插入最小堆的開銷為O（log n），因此將其插入LFU高速緩存需要O（log n）時間。

在查找元素時，可以通過哈希函數找到該元素，該哈希函數將鍵哈希到實際元素。同時，使用計數（最大堆中的計數）加1，這導致最小堆的重組，並且元素從根移開。

由於元素在任何階段都可以向下移動至log(n)電平，因此此操作也需要時間O（log n）。

當選擇一個元素將其逐出並最終從堆中刪除時，它可能導致堆數據結構的重大重組。

使用計數最少的元素位於最小堆的根。

刪除最小堆的根包括將根節點替換為堆中的最後一個葉節點，並將該節點起泡到正確的位置。

此操作的運行時複雜度也為O（log n）。

提出的LFU算法

對於可以在LFU緩存上執行的每個字典操作（插入，查找和刪除），提出的LFU算法的運行時複雜度為O（1）。

這是通過維護2個連結列表來實現的。一個用於訪問頻率，另一個用於具有相同訪問頻率的所有元素。

哈希表用於按鍵訪問元素（為清楚起見，下圖中未顯示）。

雙鍊表用於將代表一組具有相同訪問頻率的節點的節點連結在一起（在下圖中顯示為矩形塊）。

我們將此雙重連結列表稱為頻率列表。具有相同訪問頻率的這組節點實際上是此類節點的雙向連結列表（在下圖中顯示為圓形節點）。

我們將此雙向連結列表（在特定頻率本地）稱為節點列表。

節點列表中的每個節點都有一個指向其父節點的指針。

頻率列表（為清楚起見，未在圖中顯示）。因此，節點x和您將有一個指向節點1的指針，節點z和a將有一個指向節點2的指針，依此類推...

輸入圖片說明

下面的偽代碼顯示了如何初始化LFU緩存。

用於按鍵定位元素的哈希表由按鍵變量表示。

為了簡化實現，我們使用SET代替鍊表來存儲具有相同訪問頻率的元素。

變量項是標準的SET數據結構，其中包含具有相同訪問頻率的此類元素的鍵。

它的插入，查找和刪除運行時複雜度為O（1）。

輸入圖片說明

偽代碼

後面的都是一些偽代碼了，我們條國內。

理解其最核心的思想就行了，下面我們上真代碼。

感受

這個 O(1) 的算法最核心的地方實際上不多，放在 leetcode 應該算是一個中等難度的題目。

不過很奇怪，這篇論文是在 2010 年提出的，估計以前都以為 O(logn) 是極限了？

java 代碼實現

基本屬性

public class CacheEvictLfu<K,V> extends AbstractCacheEvict<K,V> {    private static final Log log = LogFactory.getLog(CacheEvictLfu.class);    /**     * key 映射信息     * @since 0.0.14     */    private final Map<K, FreqNode<K,V>> keyMap;    /**     * 頻率 map     * @since 0.0.14     */    private final Map<Integer, LinkedHashSet<FreqNode<K,V>>> freqMap;    /**     *     * 最小頻率     * @since 0.0.14     */    private int minFreq;    public CacheEvictLfu() {        this.keyMap = new HashMap<>();        this.freqMap = new HashMap<>();        this.minFreq = 1;    }}

節點定義

• FreqNode.java

public class FreqNode<K,V> {    /**     * 鍵     * @since 0.0.14     */    private K key;    /**     * 值     * @since 0.0.14     */    private V value = null;    /**     * 頻率     * @since 0.0.14     */    private int frequency = 1;    public FreqNode(K key) {        this.key = key;    }    //fluent getter & setter    // toString() equals() hashCode()}

移除元素

/** * 移除元素 * * 1. 從 freqMap 中移除 * 2. 從 keyMap 中移除 * 3. 更新 minFreq 信息 * * @param key 元素 * @since 0.0.14 */@Overridepublic void removeKey(final K key) {    FreqNode<K,V> freqNode = this.keyMap.remove(key);    //1. 根據 key 獲取頻率    int freq = freqNode.frequency();    LinkedHashSet<FreqNode<K,V>> set = this.freqMap.get(freq);    //2. 移除頻率中對應的節點    set.remove(freqNode);    log.debug("freq={} 移除元素節點：{}", freq, freqNode);    //3. 更新 minFreq    if(CollectionUtil.isEmpty(set) && minFreq == freq) {        minFreq--;        log.debug("minFreq 降低為：{}", minFreq);    }}

更新元素

/** * 更新元素，更新 minFreq 信息 * @param key 元素 * @since 0.0.14 */@Overridepublic void updateKey(final K key) {    FreqNode<K,V> freqNode = keyMap.get(key);    //1. 已經存在    if(ObjectUtil.isNotNull(freqNode)) {        //1.1 移除原始的節點信息        int frequency = freqNode.frequency();        LinkedHashSet<FreqNode<K,V>> oldSet = freqMap.get(frequency);        oldSet.remove(freqNode);        //1.2 更新最小數據頻率        if (minFreq == frequency && oldSet.isEmpty()) {            minFreq++;            log.debug("minFreq 增加為：{}", minFreq);        }        //1.3 更新頻率信息        frequency++;        freqNode.frequency(frequency);        //1.4 放入新的集合        this.addToFreqMap(frequency, freqNode);    } else {        //2. 不存在        //2.1 構建新的元素        FreqNode<K,V> newNode = new FreqNode<>(key);        //2.2 固定放入到頻率為1的列表中        this.addToFreqMap(1, newNode);        //2.3 更新 minFreq 信息        this.minFreq = 1;        //2.4 添加到 keyMap        this.keyMap.put(key, newNode);    }}/** * 加入到頻率 MAP * @param frequency 頻率 * @param freqNode 節點 */private void addToFreqMap(final int frequency, FreqNode<K,V> freqNode) {    LinkedHashSet<FreqNode<K,V>> set = freqMap.get(frequency);    if (set == null) {        set = new LinkedHashSet<>();    }    set.add(freqNode);    freqMap.put(frequency, set);    log.debug("freq={} 添加元素節點：{}", frequency, freqNode);}

數據淘汰

@Overrideprotected ICacheEntry<K, V> doEvict(ICacheEvictContext<K, V> context) {    ICacheEntry<K, V> result = null;    final ICache<K,V> cache = context.cache();    // 超過限制，移除頻次最低的元素    if(cache.size() >= context.size()) {        FreqNode<K,V> evictNode = this.getMinFreqNode();        K evictKey = evictNode.key();        V evictValue = cache.remove(evictKey);        log.debug("淘汰最小頻率信息, key: {}, value: {}, freq: {}",                evictKey, evictValue, evictNode.frequency());        result = new CacheEntry<>(evictKey, evictValue);    }    return result;}/** * 獲取最小頻率的節點 * * @return 結果 * @since 0.0.14 */private FreqNode<K, V> getMinFreqNode() {    LinkedHashSet<FreqNode<K,V>> set = freqMap.get(minFreq);    if(CollectionUtil.isNotEmpty(set)) {        return set.iterator().next();    }    throw new CacheRuntimeException("未發現最小頻率的 Key");}

測試

代碼

ICache<String, String> cache = CacheBs.<String,String>newInstance()        .size(3)        .evict(CacheEvicts.<String, String>lfu())        .build();cache.put("A", "hello");cache.put("B", "world");cache.put("C", "FIFO");// 訪問一次Acache.get("A");cache.put("D", "LRU");Assert.assertEquals(3, cache.size());System.out.println(cache.keySet());

日誌

[DEBUG] [2020-10-03 21:23:43.722] [main] [c.g.h.c.c.s.e.CacheEvictLfu.addToFreqMap] - freq=1 添加元素節點：FreqNode{key=A, value=null, frequency=1}[DEBUG] [2020-10-03 21:23:43.723] [main] [c.g.h.c.c.s.e.CacheEvictLfu.addToFreqMap] - freq=1 添加元素節點：FreqNode{key=B, value=null, frequency=1}[DEBUG] [2020-10-03 21:23:43.725] [main] [c.g.h.c.c.s.e.CacheEvictLfu.addToFreqMap] - freq=1 添加元素節點：FreqNode{key=C, value=null, frequency=1}[DEBUG] [2020-10-03 21:23:43.727] [main] [c.g.h.c.c.s.e.CacheEvictLfu.addToFreqMap] - freq=2 添加元素節點：FreqNode{key=A, value=null, frequency=2}[DEBUG] [2020-10-03 21:23:43.728] [main] [c.g.h.c.c.s.e.CacheEvictLfu.doEvict] - 淘汰最小頻率信息, key: B, value: world, freq: 1[DEBUG] [2020-10-03 21:23:43.731] [main] [c.g.h.c.c.s.l.r.CacheRemoveListener.listen] - Remove key: B, value: world, type: evict[DEBUG] [2020-10-03 21:23:43.732] [main] [c.g.h.c.c.s.e.CacheEvictLfu.addToFreqMap] - freq=1 添加元素節點：FreqNode{key=D, value=null, frequency=1}[D, A, C]

LFU vs LRU

區別

LFU是基於訪問頻次的模式，而LRU是基於訪問時間的模式。

優勢

在數據訪問符合正態分布時，相比於LRU算法，LFU算法的緩存命中率會高一些。

劣勢

• LFU的複雜度要比LRU更高一些。
• 需要維護數據的訪問頻次，每次訪問都需要更新。
• 早期的數據相比於後期的數據更容易被緩存下來，導致後期的數據很難被緩存。
• 新加入緩存的數據很容易被剔除，像是緩存的末端發生「抖動」。

小結

不過實際實踐中，LFU 的應用場景實際並沒有那麼廣泛。

因為真實的數據都是有傾斜的，熱點數據才是常態，所以 LRU 的性能一般情況下優於 LFU。

開源地址：https://github.com/houbb/cache

覺得本文對你有幫助的話，歡迎點讚評論收藏關注一波，你的鼓勵，是我最大的動力~

目前我們實現了性能比較優異的 LRU 和 LFU 算法，但是作業系統實際採用的卻不是這兩種算法，我們下一節將一起學習下作業系統青睞的 clock 淘汰算法。

不知道你有哪些收穫呢？或者有其他更多的想法，歡迎留言區和我一起討論，期待與你的思考相遇。

深入學習