From Interview Blunders to Cache Algorithms: A Deep Dive into Caching

Introduction

We have all heard of cache, but many cannot explain how it is built or which standards to use when choosing a caching framework. This article discusses caches, cache algorithms, cache frameworks, and which framework might be better.

Interview

"Cache is a temporary place for storing frequently used data because fetching the original data is too costly, so we can get it faster," said a candidate (programmer one) during a Java developer interview focused on caching experience.

The interviewer asked what criteria the candidate used to select a cache solution. The candidate stammered, "Based on… based on data…" and could not answer further.

Talk to Action

After the interview, programmer one searched online for information about caching. He found an article that explained why caches are needed, what they are, and various cache concepts.

Why Do We Need Cache?

Before caches existed, users repeatedly requested large objects directly from the database, causing long response times and heavy database load. This led to user frustration and, in extreme cases, database failure.

God Sent Cache

In the 1960s, IBM researchers introduced the concept of caching.

What Is Cache?

Cache is a temporary storage for frequently accessed data, allowing faster retrieval because accessing the original data is expensive.

Cache can be seen as a pool of data copied from the database and indexed by a key.

Hit

When a request is made, if the data is found in the cache, it is a cache hit, contributing to the hit rate.

Cache Miss

If there is space, a missed object is stored in the cache; otherwise, an eviction strategy (cache algorithm) decides which old object to replace.

Storage Cost

When a miss occurs, the time and space required to fetch data from the database and store it in the cache constitute the storage cost.

Index Cost

Similar to storage cost, indexing incurs comparable overhead.

Invalidation

When cached data needs updating, the old entry becomes invalid.

Eviction Strategies

When the cache is full and a miss occurs, an eviction strategy determines which entry to evict. No single algorithm is universally superior.

Least Frequently Used (LFU)

LFU tracks usage frequency and evicts the least frequently used entries.

Least Recently Used (LRU)

LRU evicts the least recently used entries, moving recently accessed items to the front of the cache.

LRU2

LRU2 requires an entry to be accessed twice before being kept, aiming to improve over LRU for large caches.

Two Queues (2Q)

2Q uses a two‑level LRU system: an entry moves to the second queue after a second access, balancing recency and frequency.

Adaptive Replacement Cache (ARC)

ARC combines two LRU lists (one for recent single accesses, one for recent double accesses) to achieve a balance between LRU and LFU.

Most Recently Used (MRU)

MRU evicts the most recently used entries, useful in specific scenarios where recent items are less likely to be needed again.

First In First Out (FIFO)

FIFO evicts entries in insertion order using a simple queue.

Second Chance

Second Chance improves FIFO by giving entries a second chance if they have been accessed recently, using a reference bit.

Clock

Clock is an efficient variant of Second Chance that uses a circular list and a pointer to decide evictions.

Simple Time‑Based

Simple time‑based eviction removes entries after a fixed absolute time interval.

Extended Time‑Based Expiration

Extended time‑based eviction removes entries based on relative intervals (e.g., every 5 minutes).

Sliding Time‑Based Expiration

Sliding expiration resets the timer each time an entry is accessed.

Additional Considerations

Cost: Prefer keeping hard‑to‑obtain objects.

Size: Evict larger objects to make room for smaller ones.

Time: Respect explicit expiration times.

Code Samples

Below are simplified Java snippets used by many cache algorithms.

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

Common method to add or replace an element:

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;
    }
    // handle insertion or eviction when cache is full
}

Random Cache 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()) {
        int index = numEntries++;
        // insert at end
    } else {
        int index = (int) (cache.length * random.nextFloat());
        table.remove(cache[index].getObjectKey());
    }
    cache[index].setObjectValue(value);
    cache[index].setObjectKey(key);
    table.put(key, cache[index]);
}

FIFO Cache 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()) {
        int index = numEntries++;
        // insert at end
    } else {
        int 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]);
}

LFU Cache 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()) {
        int index = numEntries++;
        // insert
    } else {
        CacheElement element = removeLfuElement();
        int index = element.getIndex();
        table.remove(element.getObjectKey());
    }
    cache[index].setObjectValue(value);
    cache[index].setObjectKey(key);
    cache[index].setIndex(index);
    table.put(key, cache[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 Cache Implementation

private void moveToFront(int index) {
    if (head != 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()) {
        // add new entry at next free slot and move to front
    } else {
        table.remove(cache[tail].getObjectKey());
        moveToFront(tail);
    }
    cache[head].setObjectValue(value);
    cache[head].setObjectKey(key);
    table.put(key, cache[head]);
}

These snippets illustrate how each algorithm manages insertion, eviction, and access tracking.

Conclusion

We have examined LFU and LRU implementations and discussed when to use arrays versus LinkedHashMap for cache storage. The choice depends on cache size and performance requirements.