Mastering Cache Algorithms: From LRU to LFU with Java Implementations

Introduction

Cache is a temporary storage for frequently accessed data to avoid the high cost of retrieving original data. Historically, without caching, repeated database requests slowed applications and overloaded databases, leading to user frustration and potential system failures.

Why We Need Caches

Without caches, users experience long response times, and databases become a bottleneck. Caching reduces latency, improves scalability, and protects backend resources.

What Is a Cache?

A cache stores copies of data from the primary data store, indexed by a key, allowing fast retrieval. Cache entries can become stale, requiring invalidation.

Cache Operations

Hit : When a requested key is found in the cache, the entry is used, increasing the hit rate.

Miss : If the key is absent, the data is fetched from the database and stored in the cache. When the cache is full, a replacement policy decides which entry to evict.

Storage and Index Cost

Storing a new entry consumes memory and time; indexing incurs similar overhead.

Invalidation

When underlying data changes, the corresponding cache entry must be invalidated.

Replacement Policies

When the cache is full, policies such as LRU, LFU, FIFO, Second Chance, Clock, Random, and various time‑based strategies determine which entry to evict.

Common Algorithms

Least Frequently Used (LFU)

Evicts the entry with the lowest access count.

Least Recently Used (LRU)

Moves recently accessed entries to the front; evicts the least recently used entry.

LRU2

Requires two accesses before an entry is considered for eviction, reducing premature removal.

Two‑Queue (2Q)

Uses a small LRU queue for recent items and a larger LRU queue for items accessed more than once.

Adaptive Replacement Cache (ARC)

Combines LRU and LFU by maintaining two LRU lists: one for recent single accesses and one for frequent accesses.

Most Recently Used (MRU)

Evicts the most recently used entry; useful in specific scenarios.

First‑In‑First‑Out (FIFO)

Evicts entries in insertion order.

Second Chance

Enhances FIFO by giving entries a second chance if they have been accessed recently.

Clock

Implements Second Chance with a circular buffer for faster eviction decisions.

Random

Randomly selects an entry to evict; simple but less predictable.

Time‑Based Policies

Simple, extended, and sliding expiration remove entries based on absolute or relative time intervals.

Implementation Example (Java)

Below is a simplified cache element class used by all algorithms:

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

Common add‑element logic (used by many algorithms):

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;
    }
    // insertion or eviction logic follows
}

LFU Example

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) {
    // ... check for space ...
    // if full, remove least‑hit element
    CacheElement element = removeLfuElement();
    int index = element.getIndex();
    table.remove(element.getObjectKey());
    // store new element at index
}

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

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

LRU Example

private void moveToFront(int index) {
    // adjust linked‑list pointers to move entry to head
}

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;
    }
    // insertion or eviction logic follows
}

FIFO Example

public final synchronized void addElement(Object key, Object value) {
    // if cache not full, append at end
    // else replace entry at current pointer and advance pointer cyclically
}

Conclusion

We have examined LFU and LRU cache implementations and discussed when to use arrays versus LinkedHashMap. Choose the data structure based on cache size and performance requirements.