Caching Strategies: LRU, LFU, Write Policies, Coherence

Caching is a cornerstone of distributed systems for reducing latency, increasing throughput, and alleviating backend load, typically converting database query times from milliseconds to microsecond access. Building on the CAP theorem trade-offs introduced in the previous section—where consistency and availability are balanced—this section delves into eviction policies and write strategies that dictate cache behavior. We define and implement LRU and LFU eviction using Java 21+ data structures, compare write-through and write-back policies based on consistency needs, explain the cache coherence problem in distributed setups, and provide a verification exercise for interview readiness. Every implementation includes explicit time and space complexity analysis, failure modes, and trade-offs articulated as ‘X provides Y at the cost of Z’.

LRU (Least Recently Used) Eviction Policy

LRU (Least Recently Used) is a cache eviction policy that removes the least recently accessed items first, implemented with a hash map and doubly linked list for O(1) time complexity in access and eviction operations. This policy is ideal for general-purpose, time-sensitive access patterns but may evict frequently used items if not recently accessed, trading simplicity for potential inefficiency in hotspot scenarios.

Java 21+ implementation uses a HashMap for O(1) key lookup and a doubly linked list for O(1) move-to-front and eviction, with a CacheEntry Record for immutable data carriers. The following code is whiteboard-reproducible and includes capacity management:

import java.util.HashMap;
import java.util.Map;

public record CacheEntry<K, V>(K key, V value) {}

public class LRUCache<K, V> {
    private final int capacity;
    private final Map<K, Node> map;
    private Node head, tail;

    private class Node {
        K key;
        V value;
        Node prev, next;
        Node(K key, V value) { this.key = key; this.value = value; }
    }

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<>();
        head = new Node(null, null);
        tail = new Node(null, null);
        head.next = tail;
        tail.prev = head;
    }

    public V get(K key) {
        if (!map.containsKey(key)) return null;
        Node node = map.get(key);
        remove(node);
        addToFront(node);
        return node.value; // Time Complexity: O(1) average, Space Complexity: O(1) extra
    }

    public void put(K key, V value) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            node.value = value;
            remove(node);
            addToFront(node);
        } else {
            if (map.size() >= capacity) {
                map.remove(tail.prev.key);
                remove(tail.prev);
            }
            Node newNode = new Node(key, value);
            map.put(key, newNode);
            addToFront(newNode);
        } // Time Complexity: O(1) average, Space Complexity: O(n) for n entries
    }

    private void remove(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void addToFront(Node node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }
}

Time and space complexities are summarized in the following table, which compares LRU and LFU operations:

Cache Operation	LRU Time Complexity	LRU Space Complexity	LFU Time Complexity	LFU Space Complexity
Get (access)	O(1) average	O(1) auxiliary	O(log n) with heap	O(1) auxiliary
Put (insert/update)	O(1) average	O(n) for n entries	O(log n) with heap	O(n) for n entries
Eviction	O(1)	O(1)	O(log n)	O(1)
Write-through	O(1) cache + O(1) DB sync	O(n)	Similar to LRU/LFU	Similar to LRU/LFU
Write-back	O(1) cache + async	O(n)	Similar to LRU/LFU	Similar to LRU/LFU

Failure modes for LRU include not handling null keys or values, incorrect eviction logic by not updating access order on get operations, and ignoring thread-safety, which can cause race conditions in concurrent access. The memory layout for LRU cache uses a HashMap (array of buckets) storing references to Node objects, each containing key, value, prev, and next pointers. In Java 21+, Records reduce overhead by storing components in the object header, and virtual threads allocate approximately 2KB per thread versus 1MB for platform threads, making them suitable for high-concurrency caching.

LFU (Least Frequently Used) Eviction Policy

LFU (Least Frequently Used) is a cache eviction policy that removes the least frequently accessed items first, implemented using data structures like min-heaps or frequency maps with linked lists for efficient frequency tracking and eviction. It optimizes for frequency-based patterns, such as hotspots, but adds complexity in implementation.

Java 21+ implementation uses a HashMap and a PriorityQueue (min-heap) for O(log n) eviction and access operations:

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public record LFUCache<K, V>(int capacity) {
    private final Map<K, Node> map = new HashMap<>();
    private final PriorityQueue<Node> minHeap = new PriorityQueue<>((a, b) -> a.freq - b.freq);
    private int minFreq = 0;

    private class Node {
        K key;
        V value;
        int freq;
        Node(K key, V value) { this.key = key; this.value = value; this.freq = 1; }
    }

    public V get(K key) {
        if (!map.containsKey(key)) return null;
        Node node = map.get(key);
        minHeap.remove(node);
        node.freq++;
        minHeap.offer(node);
        updateMinFreq();
        return node.value; // Time Complexity: O(log n) for heap operations, Space Complexity: O(1) extra
    }

    public void put(K key, V value) {
        if (capacity <= 0) return;
        if (map.containsKey(key)) {
            Node node = map.get(key);
            node.value = value;
            get(key); // Reuse get to update frequency
        } else {
            if (map.size() >= capacity) {
                Node evicted = minHeap.poll();
                map.remove(evicted.key);
            }
            Node newNode = new Node(key, value);
            map.put(key, newNode);
            minHeap.offer(newNode);
            minFreq = 1;
        } // Time Complexity: O(log n) for heap operations, Space Complexity: O(n) for n entries
    }

    private void updateMinFreq() {
        if (!minHeap.isEmpty()) {
            minFreq = minHeap.peek().freq;
        }
    }
}

Complexities are detailed in the table above. Failure modes include not properly updating frequency counts or the heap on access, causing stale evictions, and using mutable keys in HashMap, violating the hashCode/equals contract. Trade-offs between LRU and LFU are captured in the following matrix:

Aspect	LRU	LFU	Write-through	Write-back
Time Complexity	O(1) for access/eviction	O(log n) for eviction with heap	Higher latency due to sync writes	Lower latency, async writes
Consistency	Eventual based on access order	Based on frequency	Strong consistency	Eventual consistency, risk of data loss
Implementation Simplicity	Simple with linked list	More complex with heap or frequency maps	Straightforward sync logic	Requires async persistence logic
Best Use Case	General-purpose, time-sensitive access	Hotspot optimization, frequency-based patterns	Financial transactions, strong consistency needs	High-write throughput, tolerant to stale reads
Trade-off	Fast access but may evict frequent items if recently unused	Optimizes for frequency but adds complexity	Provides safety at the cost of speed	Provides speed at the cost of safety

Write Policies: Write-through vs Write-back

Write-through cache is a write policy where data is synchronously written to both the cache and the underlying database or storage, ensuring strong consistency but with higher write latency. In contrast, write-back cache writes data to the cache first and asynchronously persists to storage, reducing write latency but risking data loss if the cache fails before persistence. These policies align with consistency models from the CAP theorem: write-through supports CP (Consistency-Partition tolerance) systems like financial transactions, while write-back fits AP (Availability-Partition tolerance) systems such as social media feeds where speed is prioritized over immediate consistency.

Trade-offs are explicit: write-through provides safety at the cost of speed, whereas write-back provides speed at the cost of safety. For example, in a high-write scenario, write-back reduces backend load but requires robust failure handling to prevent data loss.

Cache Coherence

Cache coherence is the problem in distributed caching systems where multiple cache instances may hold stale data; solutions include broadcast invalidation and versioning to maintain consistency across caches. This issue arises when updates in one cache are not propagated to others, leading to inconsistent reads. Methods to address coherence include time-based invalidation with TTL (Time To Live), where cached items expire after a predetermined duration, and event-based notifications via message queues. However, implementing distributed protocols is beyond basic scope; focus remains on single-instance eviction and write policies.

Implementation and Verification

Following an interview pattern template ensures systematic design: understand requirements for cache size and access patterns, choose eviction policy based on constraints (LRU for time-based, LFU for frequency-based), design data structures with HashMap and appropriate lists or heaps, implement in Java 21+ using Records and virtual threads, analyze complexities, test edge cases, and state trade-offs explicitly. A verification exercise involves coding an LRU cache with O(1) get/put using HashMap and doubly linked list within 15 minutes, mirroring common interview problems.

Failure mode checklists summarize common pitfalls:

Not handling null keys or values in cache operations, leading to NullPointerException.
Incorrect eviction logic in LRU, e.g., not updating access order on get operations.
For LFU, not properly updating frequency counts or heap on access, causing stale evictions.
Ignoring thread-safety: concurrent access without synchronization can cause race conditions.
Not validating capacity limits, leading to memory leaks or overflow.
In write-back caches, failing to implement proper async persistence, risking data loss.
Overlooking cache coherence in distributed setups, resulting in stale data reads.
Using mutable keys in HashMap, violating hashCode/equals contract and causing lookup failures.
Not including complexity analysis in implementations, missing interview requirements.
Assuming O(1) performance in all cases without considering worst-case scenarios like hash collisions.

By integrating these elements, readers can implement robust caching strategies, leveraging Java 21+ features for efficiency and clarity in system design interviews.