Skip to main content

Design an In-Memory Cache (LRU/LFU with TTL)

Problem Statement

Design a fast, thread-safe, in-memory key-value cache (similar to Guava or Caffeine). The cache must enforce a maximum size limit and evict items using a Least Recently Used (LRU) policy when capacity is reached. Additionally, it should support key-level Time-To-Live (TTL) expiration, ensuring expired entries are evicted both passively (on retrieval) and actively (via a background thread).

Asked In Companies
Google Microsoft Directi Oracle

Functional Requirements

  • Implement basic operations: put(key, value, ttl), get(key), and remove(key).
  • Enforce a strict maximum capacity limit. Evict the Least Recently Used (LRU) item when the limit is breached.
  • Support individual Time-To-Live (TTL) configuration for each key.
  • Handle thread-safe operations. Support high-concurrency reads using fine-grained locks.
  • Support passive eviction (removing expired items immediately when trying to access them) and active eviction (cleaning up expired elements using a background service).

Objects Required

  • CacheNode (Doubly Linked List node carrying keys, values, and expiration)
  • Cache (Generic interface for caching contracts)
  • LRUCache (Core cache manager containing eviction and locking controls)
  • CacheBuilder (Helper tool configuring capacity and background intervals)

CacheNode Class

The CacheNode models a single node in our custom doubly linked list. It contains references to adjacent nodes to allow fast $O(1)$ removal and insertions.


public class CacheNode<K, V> {
    K key;
    V value;
    long expiryTime;
    CacheNode<K, V> prev;
    CacheNode<K, V> next;

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

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

The constructor initializes the key, the value, and calculates the absolute millisecond epoch timestamp when this item will expire. The isExpired() helper evaluates whether the current system time has passed the calculated expiration time.

Cache Interface

We define a standard Cache interface to abstract the core operations. This allows us to swap the eviction algorithm later (e.g., LFU, FIFO) without refactoring the client application.


public interface Cache<K, V> {
    V get(K key);
    void put(K key, V value, long ttlMs);
    void remove(K key);
    void clear();
    int size();
}

The interface exposes clean contracts. The put() method accepts a TTL value in milliseconds, whereas a default TTL value of 0 or less signifies that the key will not expire.

LRUCache Class

The LRUCache implementation combines a ConcurrentHashMap for constant-time lookup and a custom doubly linked list to track usage sequences. We use Java's ReentrantReadWriteLock to permit concurrent readers while isolating writes.


import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantReadWriteLock;

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

    private final ReentrantReadWriteLock rwLock = new ReentrantReadWriteLock();
    private final Lock readLock = rwLock.readLock();
    private final Lock writeLock = rwLock.writeLock();

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new ConcurrentHashMap<>();
        
        // Dummy head and tail nodes to avoid null checks during list manipulations
        this.head = new CacheNode<>(null, null, 0);
        this.tail = new CacheNode<>(null, null, 0);
        head.next = tail;
        tail.prev = head;
    }

    @Override
    public V get(K key) {
        readLock.lock();
        try {
            CacheNode<K, V> node = map.get(key);
            if (node == null) return null;

            if (node.isExpired()) {
                // Passive Eviction: Hand over to write lock to delete the expired entry safely
                readLock.unlock();
                writeLock.lock();
                try {
                    if (map.containsKey(key)) { // Double-check pattern
                        removeNode(node);
                        map.remove(key);
                    }
                } finally {
                    writeLock.unlock();
                    readLock.lock();
                }
                return null;
            }

            // Move the node to head to signal it was recently accessed
            readLock.unlock();
            writeLock.lock();
            try {
                moveToHead(node);
            } finally {
                writeLock.unlock();
                readLock.lock();
            }
            return node.value;
        } finally {
            readLock.unlock();
        }
    }

    @Override
    public void put(K key, V value, long ttlMs) {
        writeLock.lock();
        try {
            CacheNode<K, V> existingNode = map.get(key);
            if (existingNode != null) {
                existingNode.value = value;
                existingNode.expiryTime = (ttlMs > 0) ? (System.currentTimeMillis() + ttlMs) : Long.MAX_VALUE;
                moveToHead(existingNode);
                return;
            }

            if (map.size() >= capacity) {
                CacheNode<K, V> lruNode = removeTail();
                if (lruNode != null) {
                    map.remove(lruNode.key);
                }
            }

            CacheNode<K, V> newNode = new CacheNode<>(key, value, ttlMs);
            addToHead(newNode);
            map.put(key, newNode);
        } finally {
            writeLock.unlock();
        }
    }

    @Override
    public void remove(K key) {
        writeLock.lock();
        try {
            CacheNode<K, V> node = map.remove(key);
            if (node != null) {
                removeNode(node);
            }
        } finally {
            writeLock.unlock();
        }
    }

    @Override
    public void clear() {
        writeLock.lock();
        try {
            map.clear();
            head.next = tail;
            tail.prev = head;
        } finally {
            writeLock.unlock();
        }
    }

    @Override
    public int size() {
        readLock.lock();
        try {
            return map.size();
        } finally {
            readLock.unlock();
        }
    }

    public void cleanExpired() {
        writeLock.lock();
        try {
            map.values().removeIf(node -> {
                if (node.isExpired()) {
                    removeNode(node);
                    return true;
                }
                return false;
            });
        } finally {
            writeLock.unlock();
        }
    }

    // --- Helper Doubly Linked List Operations ---
    
    private void addToHead(CacheNode<K, V> node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }

    private void removeNode(CacheNode<K, V> node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void moveToHead(CacheNode<K, V> node) {
        removeNode(node);
        addToHead(node);
    }

    private CacheNode<K, V> removeTail() {
        if (tail.prev == head) return null;
        CacheNode<K, V> lru = tail.prev;
        removeNode(lru);
        return lru;
    }
}

Here is an explanation of the core operations inside the LRUCache class:

  • The constructor configures maximum size and links the sentinel head and tail nodes to simplify pointer operations.
  • get() retrieves the node. It checks for expiry (passive eviction). If expired, it acquires a write lock, strips references, and returns null. If active, it moves the node to the head of the list.
  • put() inserts a new node or updates an existing one. If capacity overflows, the tail node is removed from the linked list and hash map. The write lock ensures exclusive update control.
  • remove() deletes a specific key from map and linked list under a write lock.
  • cleanExpired() checks all values, removes nodes that fail validation checks, and prunes the hash map. This is utilized by background workers to perform active cleanups.
  • The list manipulation helpers (addToHead, removeNode, moveToHead, removeTail) safely rearrange memory pointers around sentinel bounds.

CacheBuilder Class

The CacheBuilder class uses a builder pattern to configure capacity and kick off active background cleaner threads.


import java.util.concurrent.Executors;
import java.util.concurrent.ScheduledExecutorService;
import java.util.concurrent.TimeUnit;

public class CacheBuilder<K, V> {
    private int capacity = 1000;
    private long cleanupIntervalMs = 10000; // 10 seconds default

    public CacheBuilder<K, V> withCapacity(int capacity) {
        this.capacity = capacity;
        return this;
    }

    public CacheBuilder<K, V> withCleanupInterval(long ms) {
        this.cleanupIntervalMs = ms;
        return this;
    }

    public Cache<K, V> build() {
        LRUCache<K, V> cache = new LRUCache<>(capacity);
        
        // Spawn active cleanup scheduler daemon thread
        ScheduledExecutorService scheduler = Executors.newSingleThreadScheduledExecutor(runnable -> {
            Thread t = new Thread(runnable);
            t.setDaemon(true);
            t.setName("Cache-Cleanup-Worker");
            return t;
        });
        
        scheduler.scheduleAtFixedRate(cache::cleanExpired, cleanupIntervalMs, cleanupIntervalMs, TimeUnit.MILLISECONDS);
        return cache;
    }
}

The withCapacity() and withCleanupInterval() methods assign execution properties fluently. The build() method initializes the cache and runs a scheduled background executor service that regularly calls cleanExpired(). Using daemon threads ensures the worker doesn't block the JVM shutdown process.

Class Diagram

CacheK, Vget(key: K): Vput(key: K, value: V, ttlMs: long): voidremove(key: K): voidclear(): voidsize(): intCacheNodeK, Vkey: Kvalue: VexpiryTime: longprev: CacheNode<K, V>next: CacheNode<K, V>isExpired(): booleanLRUCacheK, Vcapacity: intmap: Map<K, CacheNode<K, V>>head: CacheNode<K, V>tail: CacheNode<K, V>rwLock: ReentrantReadWriteLockreadLock: LockwriteLock: Lockget(key: K): Vput(key: K, value: V, ttlMs: long): voidremove(key: K): voidclear(): voidsize(): intcleanExpired(): voidaddToHead(node: CacheNode<K, V>): voidremoveNode(node: CacheNode<K, V>): voidmoveToHead(node: CacheNode<K, V>): voidremoveTail(): CacheNode<K, V>CacheBuilderK, Vcapacity: intcleanupIntervalMs: longwithCapacity(capacity: int): CacheBuilder<K, V>withCleanupInterval(ms: long): CacheBuilder<K, V>build(): Cache<K, V>1manyconfigures & instantiates

Also See

Comments

Post a Comment

Popular posts from this blog

Designing a Parking Lot - Low Level Design

Problem Statement Design a parking lot that can handle vehicles entering and leaving while managing parking across multiple floors. Each vehicle should be assigned a suitable parking spot based on its type, and the spot should be freed once the vehicle exits. The design should also support generating a ticket at entry and optionally calculating the parking fee based on the duration of stay. Asked In Companies Amazon Google Microsoft Uber Walmart Flipkart Meta PayPal Oracle Salesforce Adobe Apple Intuit LinkedIn Atlassian Functional Requirements The design should support multiple vehicle types such as bikes, cars, and trucks A vehicle must be assigned a parking spot compatible with its type A parking spot cannot be assigned to more than one vehicle at a time The parking lot should support multiple levels (floors) The design should search and allocate an availa...
Post a Comment
Read more

Most Frequently Asked Low Level Design(LLD) Interview Questions

Below are the curated list of most commonly asked Low Level Design (LLD) interview problems. Each problem includes a short description and a link to the complete solution with code and class diagrams. Design Parking Lot System The system should handle parking for different vehicle types such as bikes, cars, and trucks. It should manage slot allocation, availability tracking, and entry/exit flow. The design also ensures efficient usage of parking space under varying load conditions. View Solution Design Elevator / Lift System The system should support multiple elevators operating across floors with request handling logic. It focuses on scheduling algorithms to minimize wait time and optimize movement. It also manages direction control and concurrent floor requests. View Solution Design Movie Ticket Booking System The system should allow users to browse movies, select shows, and book seats. It handles seat ...
Post a Comment
Read more

Software Design Patterns for LLD Interviews: A Complete Guide

Software Design Patterns for LLD Interviews: A Complete Guide In Software Development Engineer (SDE) interviews—especially for mid-level and senior roles—low-level design (LLD) rounds assess your ability to write clean, reusable, maintainable, and extensible code. The foundation of resolving these architectural challenges lies in the standard Gang of Four (GoF) Design Patterns. Rather than memorizing theoretical definitions, interviewers expect you to apply these patterns to real-world scenarios, identifying the trade-offs of each. Below is a comprehensive guide to the 12 most frequently asked design patterns in LLD interviews, categorized by their classification (Creational, Structural, and Behavioral). Each pattern contains a concrete, real-world Java implementation and a detailed breakdown of design decisions. Creational Design Patterns Creational design patterns deal with object creation mechanisms. They abstract the instantiation process, making a system independent of how...
Post a Comment
Read more