LRU vs. LFU Eviction Policies

Least Recently Used (LRU) and Least Frequently Used (LFU) are common cache eviction strategies. LRU tracks the time since last access, evicting the oldest entry when capacity is reached. LFU prioritizes access frequency, evicting entries with the lowest hit count. When multiple entries share the same minimum frequency, LFU falls back to LRU, evicting the least recently accessed item among them.

Consider a cache with a capacity of 3 and the following access sequence: A, B, C, A, A, A, B, C, C, D. Under LRU, the final cache state would be D, C, B, having evicted A despite it being the most frequently accessed item. LFU correctly retains A, leaving the cache with A, C, D.

Naive Doubly Linked List Approach

A basic LFU implementation can use a single doubly linked list sorted primarily by frequency, and by access time as a secondary criterion. When an entry is accessed, its frequency increases, requiring a traversal to reposition it correctly within the list. This repositioning results in O(N) time complexity for both read and write operations, making it inefficient for large caches.

Achieving O(1) Time Complexity

An optimal O(1) solution requires combining multiple hash maps and tracking the minimum frequency.

• Key-to-Record Mapping: A hash map (recordMap) maps keys to CacheRecord objects for O(1) value retrieval. The CacheRecord stores the key, value, and current hitCount.
• Frequency-to-Records Mapping: A second hash map (frequencyMap) maps frequencies to a collection of CacheRecord objects. To satisfy the LRU fallback for identical frequencies, this collection must maintain insertion order and allow O(1) removal. A LinkedHashSet is ideal.
• Minimum Frequency Tracking: A global minFrequency variable tracks the lowest hit count currently in the cache, enabling O(1) identification of eviction candidates.

When an entry is accessed, it is removed from the set at its current hitCount, its hitCount is incremented, and it is added to the set at the new hitCount. If the set at minFrequency becomes empty, minFrequency is incremented. When inserting a new entry, minFrequency is reset to 1.

class CacheRecord {
    int identifier;
    int data;
    int hitCount = 1;

    CacheRecord(int identifier, int data) {
        this.identifier = identifier;
        this.data = data;
    }
}

class FrequencyCache {
    private int maxCapacity;
    private int minFrequency;
    private Map<Integer, CacheRecord> recordMap;
    private Map<Integer, LinkedHashSet<CacheRecord>> frequencyMap;

    public FrequencyCache(int capacity) {
        this.maxCapacity = capacity;
        this.minFrequency = 0;
        this.recordMap = new HashMap<>();
        this.frequencyMap = new HashMap<>();
    }

    public int get(int key) {
        // O(1) retrieval and frequency update logic
    }

    public void put(int key, int value) {
        // O(1) insertion, eviction, and frequency update logic
    }
}

SPI Configuration Omission in Dubbo

Apache Dubbo introduced an LFU cache implementation in version 2.7.7 within the org.apache.dubbo.common.utils.LFUCache class. However, users configuring cache="lfu" encountered a No such extension org.apache.dubbo.cache.CacheFactory by name lfu exception. The root cause was a missing Service Provider Interface (SPI) registration. While the class existed, the Dubbo ExtensionLoader could not discover it because the lfu alias was omitted from the corresponding SPI configuration file. Adding the missing entry resolves the runtime error.