Mastering Cache Algorithms: From LRU to LFU and Beyond

Introduction

Cache is a temporary storage for frequently accessed data that reduces the cost of retrieving data from slower sources such as databases. The article explores cache fundamentals, common algorithms, and practical Java implementations.

Why Cache Is Needed

Without caching, each request may trigger a costly database read, leading to longer response times, higher load on the database, and a poor user experience. Caching mitigates these problems by keeping hot data in memory.

Core Concepts

Cache Hit : The requested key is found in the cache and the value is returned.

Cache Miss : The key is absent; the system must fetch the data from the backing store and decide how to store it.

Storage Cost : Time and space required to insert a new entry after a miss.

Index Cost : Overhead of locating an entry, similar to storage cost.

Invalidation : Removing or updating entries when the underlying data changes.

Replacement Policies

When the cache is full, a policy determines which entry to evict.

Least Frequently Used (LFU) : Evicts the entry with the lowest access frequency.

Least Recently Used (LRU) : Evicts the entry that has not been accessed for the longest time.

LRU‑2 : Keeps entries that have been accessed at least twice before eviction.

Two‑Queue (2Q) : Uses a small LRU queue for recent accesses and a larger LRU queue for entries accessed more than once.

Adaptive Replacement Cache (ARC) : Combines two LRU lists (one for recent, one for frequent) to adapt dynamically.

Most Recently Used (MRU) : Evicts the most recently accessed entry (useful in specific workloads).

First‑In‑First‑Out (FIFO) : Evicts entries in insertion order.

Second Chance : Extends FIFO by giving entries a second chance if they have been accessed.

Clock : A circular FIFO variant that uses a reference bit.

Time‑Based Policies : Expire entries after a fixed absolute or sliding interval.

Common Code Used by All Algorithms

public class CacheElement {
    private Object objectValue;
    private Object objectKey;
    private int index;
    private int hitCount; // getters and setters
}

public final synchronized void addElement(Object key, Object value) {
    int index;
    Object obj = table.get(key);
    if (obj != null) {
        CacheElement element = (CacheElement) obj;
        element.setObjectValue(value);
        element.setObjectKey(key);
        return;
    }
    // insertion logic handled by specific algorithms
}

LFU Implementation

public synchronized Object getElement(Object key) {
    Object obj = table.get(key);
    if (obj != null) {
        CacheElement element = (CacheElement) obj;
        element.setHitCount(element.getHitCount() + 1);
        return element.getObjectValue();
    }
    return null;
}

public final synchronized void addElement(Object key, Object value) {
    Object obj = table.get(key);
    if (obj != null) {
        CacheElement element = (CacheElement) obj;
        element.setObjectValue(value);
        element.setObjectKey(key);
        return;
    }
    if (!isFull()) {
        index = numEntries;
        ++numEntries;
    } else {
        CacheElement element = removeLfuElement();
        index = element.getIndex();
        table.remove(element.getObjectKey());
    }
    cache[index].setObjectValue(value);
    cache[index].setObjectKey(key);
    cache[index].setIndex(index);
    table.put(key, cache[index]);
}

public CacheElement removeLfuElement() {
    CacheElement[] elements = getElementsFromTable();
    return leastHit(elements);
}

public static CacheElement leastHit(CacheElement[] elements) {
    CacheElement lowest = null;
    for (CacheElement e : elements) {
        if (lowest == null || e.getHitCount() < lowest.getHitCount()) {
            lowest = e;
        }
    }
    return lowest;
}

LRU Implementation

private void moveToFront(int index) {
    int nextIndex = next[index];
    int prevIndex = prev[index];
    next[prevIndex] = nextIndex;
    if (nextIndex >= 0) {
        prev[nextIndex] = prevIndex;
    } else {
        tail = prevIndex;
    }
    prev[index] = -1;
    next[index] = head;
    prev[head] = index;
    head = index;
}

public final synchronized void addElement(Object key, Object value) {
    Object obj = table.get(key);
    if (obj != null) {
        CacheElement entry = (CacheElement) obj;
        entry.setObjectValue(value);
        entry.setObjectKey(key);
        moveToFront(entry.getIndex());
        return;
    }
    if (!isFull()) {
        if (_numEntries > 0) {
            prev[_numEntries] = tail;
            next[_numEntries] = -1;
            moveToFront(numEntries);
        }
        ++numEntries;
    } else {
        table.remove(cache[tail].getObjectKey());
        moveToFront(tail);
    }
    cache[head].setObjectValue(value);
    cache[head].setObjectKey(key);
    table.put(key, cache[head]);
}

FIFO Implementation

public final synchronized void addElement(Object key, Object value) {
    Object obj = table.get(key);
    if (obj != null) {
        CacheElement element = (CacheElement) obj;
        element.setObjectValue(value);
        element.setObjectKey(key);
        return;
    }
    if (!isFull()) {
        index = numEntries;
        ++numEntries;
    } else {
        index = current;
        if (++current >= cache.length) current = 0; // circular FIFO
        table.remove(cache[index].getObjectKey());
    }
    cache[index].setObjectValue(value);
    cache[index].setObjectKey(key);
    table.put(key, cache[index]);
}

Conclusion

The article demonstrates how LFU and LRU (as well as other policies) can be implemented in Java, either with simple arrays for small caches or with more sophisticated structures such as LinkedHashMap for larger ones. Choosing the right replacement strategy depends on workload characteristics, cost considerations, and cache size.