In-Memory Cache (LRU/LFU)

Requirements & System Scope

Functional Scope (In-Scope)

Strategy-driven Eviction: Support multiple eviction mechanics (LRU and LFU) using the Strategy Pattern.
Dynamic TTL Expired Invalidation: Cleanly check and invalidate cache entries lazily upon query.
Multi-threaded Locks: Shield backing dictionaries with concurrent read-write synchronization locks.
Telemetry Tracking Stats: Aggregate hit, miss, and eviction totals per-cache instance.

Explicit Boundaries (Out-of-Scope)

No Cluster Node Replica Sync: Bypasses state serialization across multiple servers.
No Swap Disk Spillage: Restricts operations memory capacity strictly to RAM storage heaps.

Class Diagram & Entity Relationships

Strategy Pattern layout representing interchangeable eviction algorithms:

Design Patterns & SOLID Principles

Strategy Pattern (Eviction Management): Decoupling eviction rules inside concrete strategy instances makes it easy to plug in LFU, LRU, or FIFO structures at construction time.
Single Responsibility Principle (SRP):CacheStats measures cache hit metadata, CacheEntry monitors lifespans, and InMemoryCache controls coordination.

Core Execution Workflows

Cache Get & Access Sequence

Caller requests key: get(key).
Validate existence in backing dictionary. Return null on miss.
Validate TTL lifespan:
1. If the entry has expired, purge it from the store, signal onRemove to the eviction strategy, and record a cache miss.
Otherwise, signal onAccess to register access timestamps or counts, record a cache hit, and return the item.

Concurrency & Thread Safety Strategy

When multiple threads fetch, write, and evict keys simultaneously:

Concurrent Locks Safeguards: Protect backing collections with thread-safe reader/writer locks (ReentrantReadWriteLock).
Lazy TTL Expirations: Minimises locks holding duration by resolving item validity lazily during read execution.

Complete Clean Code Blueprint

Clean reference designs demonstrating interchangeable eviction caches in Java and Python:

// ─── JAVA BLUEPRINT ──────────────────────────────────────────────────────────
import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.LongAdder;
import java.util.concurrent.locks.*;

interface EvictionStrategy<K> {
    void onAccess(K key);
    void onPut(K key);
    void onRemove(K key);
    K evict();
}

class LRUEvictionStrategy<K> implements EvictionStrategy<K> {
    private final LinkedHashSet<K> order = new LinkedHashSet<>();

    @Override
    public void onAccess(K key) {
        order.remove(key);
        order.add(key);
    }

    @Override
    public void onPut(K key) {
        order.add(key);
    }

    @Override
    public void onRemove(K key) {
        order.remove(key);
    }

    @Override
    public K evict() {
        if (order.isEmpty()) return null;
        K oldest = order.iterator().next();
        order.remove(oldest);
        return oldest;
    }
}

class LFUEvictionStrategy<K> implements EvictionStrategy<K> {
    private final Map<K, Integer> counts = new HashMap<>();
    private final Map<K, Long> timestamps = new HashMap<>();

    @Override
    public void onAccess(K key) {
        counts.put(key, counts.getOrDefault(key, 0) + 1);
        timestamps.put(key, System.nanoTime());
    }

    @Override
    public void onPut(K key) {
        counts.putIfAbsent(key, 1);
        timestamps.put(key, System.nanoTime());
    }

    @Override
    public void onRemove(K key) {
        counts.remove(key);
        timestamps.remove(key);
    }

    @Override
    public K evict() {
        if (counts.isEmpty()) return null;
        K lfuKey = null;
        int minCount = Integer.MAX_VALUE;
        long minTime = Long.MAX_VALUE;

        for (Map.Entry<K, Integer> entry : counts.entrySet()) {
            K key = entry.getKey();
            int count = entry.getValue();
            long time = timestamps.get(key);
            if (count < minCount || (count == minCount && time < minTime)) {
                minCount = count;
                minTime = time;
                lfuKey = key;
            }
        }
        if (lfuKey != null) {
            counts.remove(lfuKey);
            timestamps.remove(lfuKey);
        }
        return lfuKey;
    }
}

class CacheEntry<V> {
    private final V value;
    private final long expiryTime;

    public CacheEntry(V value, long ttlMs) {
        this.value = value;
        this.expiryTime = ttlMs > 0 ? System.currentTimeMillis() + ttlMs : Long.MAX_VALUE;
    }

    public V getValue() { return value; }
    public boolean isExpired() { return System.currentTimeMillis() > expiryTime; }
}

class CacheStats {
    private final LongAdder hits = new LongAdder();
    private final LongAdder misses = new LongAdder();
    private final LongAdder evictions = new LongAdder();

    public void recordHit() { hits.increment(); }
    public void recordMiss() { misses.increment(); }
    public void recordEviction() { evictions.increment(); }

    public long getHits() { return hits.sum(); }
    public long getMisses() { return misses.sum(); }
    public long getEvictions() { return evictions.sum(); }
}

class InMemoryCache<K, V> {
    private final int capacity;
    private final Map<K, CacheEntry<V>> store = new HashMap<>();
    private final EvictionStrategy<K> evictionStrategy;
    private final CacheStats stats = new CacheStats();
    private final ReentrantReadWriteLock rwLock = new ReentrantReadWriteLock();

    public InMemoryCache(int capacity, EvictionStrategy<K> strategy) {
        this.capacity = capacity;
        this.evictionStrategy = strategy;
    }

    public V get(K key) {
        rwLock.writeLock().lock();
        try {
            CacheEntry<V> entry = store.get(key);
            if (entry == null) {
                stats.recordMiss();
                return null;
            }
            if (entry.isExpired()) {
                store.remove(key);
                evictionStrategy.onRemove(key);
                stats.recordMiss();
                return null;
            }
            evictionStrategy.onAccess(key);
            stats.recordHit();
            return entry.getValue();
        } finally {
            rwLock.writeLock().unlock();
        }
    }

    public void put(K key, V value, long ttlMs) {
        rwLock.writeLock().lock();
        try {
            if (store.containsKey(key)) {
                store.put(key, new CacheEntry<>(value, ttlMs));
                evictionStrategy.onAccess(key);
            } else {
                if (store.size() >= capacity) {
                    K evictedKey = evictionStrategy.evict();
                    if (evictedKey != null) {
                        store.remove(evictedKey);
                        stats.recordEviction();
                    }
                }
                store.put(key, new CacheEntry<>(value, ttlMs));
                evictionStrategy.onPut(key);
            }
        } finally {
            rwLock.writeLock().unlock();
        }
    }

    public CacheStats getStats() { return stats; }
}

public class Main {
    public static void main(String[] args) {
        System.out.println("=== In-Memory Cache (LRU Strategy) ===");
        InMemoryCache<String, String> lruCache = new InMemoryCache<>(2, new LRUEvictionStrategy<>());
        lruCache.put("A", "Apple", 0);
        lruCache.put("B", "Banana", 0);
        lruCache.get("A");
        lruCache.put("C", "Cherry", 0); // Evicts B

        System.out.println("Hits: " + lruCache.getStats().getHits());
        System.out.println("Misses: " + lruCache.getStats().getMisses());
        System.out.println("Evictions: " + lruCache.getStats().getEvictions());
    }
}

Help Us Improve

How helpful was this walkthrough?

Click a star to rate. We actively use this feedback to refine and update our system design content.

Placeholder

Discussion

Share your thoughts, ask questions, or help others.

Loading comments...

✦Requirements & System Scope

Functional Scope (In-Scope)

Explicit Boundaries (Out-of-Scope)

◫Class Diagram & Entity Relationships

⬡Design Patterns & SOLID Principles

{ }Core Execution Workflows