Design a Cache with Pluggable Eviction Policy

Thread-Safe LRU Cache built one specific eviction policy directly into the cache. This lesson generalizes: the eviction algorithm becomes swappable, distinct from the cache's own get/put mechanics.

Core classes

interface EvictionPolicy<K> {
    void onAccess(K key);   // called on every get/put — policy tracks whatever it needs internally
    K evictionCandidate();  // returns which key SHOULD be evicted next, per this policy's rules
}

class LRUPolicy<K> implements EvictionPolicy<K> {
    private final LinkedHashMap<K, Boolean> accessOrder = new LinkedHashMap<>(16, 0.75f, true);
    public void onAccess(K key) { accessOrder.put(key, true); }
    public K evictionCandidate() { return accessOrder.keySet().iterator().next(); } // oldest access = first in iteration order
}

class LFUPolicy<K> implements EvictionPolicy<K> {
    private final Map<K, Integer> frequencies = new HashMap<>();
    public void onAccess(K key) { frequencies.merge(key, 1, Integer::sum); }
    public K evictionCandidate() { return frequencies.entrySet().stream().min(Map.Entry.comparingByValue()).map(Map.Entry::getKey).orElseThrow(); }
}

Cache delegates entirely to the policy

class Cache<K, V> {
    private final Map<K, V> store = new HashMap<>();
    private final EvictionPolicy<K> evictionPolicy; // injected — Cache never knows WHICH policy is active
    private final int capacity;

    Cache(int capacity, EvictionPolicy<K> evictionPolicy) {
        this.capacity = capacity;
        this.evictionPolicy = evictionPolicy;
    }

    V get(K key) {
        evictionPolicy.onAccess(key);
        return store.get(key);
    }

    void put(K key, V value) {
        if (store.size() >= capacity && !store.containsKey(key)) {
            K evict = evictionPolicy.evictionCandidate();
            store.remove(evict);
        }
        store.put(key, value);
        evictionPolicy.onAccess(key);
    }
}

Cache has zero knowledge of whether it's running LRU, LFU, or any future policy — swapping new Cache<>(100, new LRUPolicy<>()) for new Cache<>(100, new LFUPolicy<>()) requires no change to Cache itself, matching the Strategy pattern's core benefit as it's been applied throughout this course. This is a meaningfully different design from Thread-Safe LRU Cache's LinkedHashMap-based approach — that one is optimal specifically because it commits to LRU semantics and exploits LinkedHashMap's built-in access-order support directly; this design trades that specific optimization for the ability to swap eviction algorithms at construction time.

Adding metrics without violating SRP

class MetricsCollectingCache<K, V> {
    private final Cache<K, V> delegate; // Decorator, not inheritance
    private long hits = 0, misses = 0, evictions = 0;

    V get(K key) {
        V value = delegate.get(key);
        if (value != null) hits++; else misses++;
        return value;
    }
    double hitRate() { return (double) hits / (hits + misses); }
}

Adding metrics inside Cache itself would give it a second reason to change (cache logic changes, OR metrics requirements change) — a direct Single Responsibility violation. Wrapping it in a MetricsCollectingCache via Decorator (see Decorator Pattern) keeps metrics as a separate, addable/removable concern layered on top, without Cache's own code ever needing to know metrics exist.

Follow-up questions this topic invites — and their answers

Q: What's the time complexity cost of this generalized design vs Thread-Safe LRU Cache's specialized one? A: LFUPolicy.evictionCandidate() here is O(n) (scanning all frequencies for the minimum) — noticeably worse than LRU's O(1) via LinkedHashMap's ordered iteration. A production LFU implementation would use a frequency-bucketed structure to get back to O(1), which is worth naming as the natural next optimization rather than presenting this simple version as production-ready.

Q: How would you make EvictionPolicy thread-safe, given Cache itself isn't shown with any locking here? A: The same lock-the-whole-operation approach from Thread-Safe LRU Cache applies — wrap get()/put() in a lock, and note that onAccess() must be covered by the SAME lock as the store mutation, since eviction-candidate selection and store modification need to stay atomic together, exactly the same 'get() is not read-only' subtlety from that earlier lesson.

Q: Could FIFO (from the Distributed Cache case's eviction policy comparison) be added as a third policy here? A: Yes — a FIFOPolicy tracking insertion order (via a plain Queue, not needing access-order tracking at all, since FIFO ignores access pattern entirely) would plug in identically, which is exactly the point of the pluggable design: a new policy is a new class, zero changes elsewhere.

Q: Is a separate onAccess() call from get() AND put() ever a source of bugs? A: Yes — forgetting to call onAccess() in one code path (e.g. a bulk-load method that populates the cache without going through put()) would leave the eviction policy's internal state silently out of sync with the cache's actual contents, a real risk worth calling out: every mutation path needs to consistently notify the policy, which is easy to miss if the Cache class grows additional entry points over time.