System Design: Distributed Cache (Redis)

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:

1. LRUCache(int capacity): Initialize the LRU cache with positive size capacity.

2. int get(int key): Return the value of the key if the key exists, otherwise return -1.

3. void put(int key, int value): Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.

Functional Requirements

• The LRUCache should store (key, value) pairs. Every new (key, value) pair should be inserted at the front of the cache, marking it as the most recently used. If the provided key already exists, its value should be updated and the corresponding entry should be moved to the front instead of creating a duplicate.

• The LRUCache should maintain elements ordered by recency of access. Whenever a key is accessed or updated, its corresponding (key, value) pair should be moved to the front of the cache, marking it as the most recently used.

• When the LRUCache reaches its maximum capacity and a new (key, value) pair needs to be inserted, the cache should evict the least recently used entry. This corresponds to removing the (key, value) pair at the end of the cache, which represents the item that has not been accessed for the longest time.

Non-Functional Requirements

• The get and put operations must execute in O(1) average time complexity, ensuring constant-time performance regardless of the number of elements in the cache. This requirement is critical to support high-performance use cases where frequent reads and writes are expected.

Key Observations

• A HashMap can be used to store (key, value) mappings, allowing both put and get operations to run in O(1) time. However, a HashMap cannot maintain the order of usage, making it difficult to identify the least recently used element.

• A SinglyLinkedList can help maintain ordering. By inserting every new (key, value) pair at the head and removing the tail node when the cache exceeds its capacity, we can evict the least recently used element in O(1) time. However, when a key is accessed or updated, we still need to search for the corresponding node in the list, update its value, and move it to the front. This search operation takes O(n) time, which becomes the primary bottleneck.

• Along with a SinglyLinkedList, we can use a HashMap to store (key, node) mappings, enabling O(1) lookup when accessing or updating a (key, value) pair. This eliminates the need to search through the list. However, once we locate a node, we still need to remove from its current position and move it to the front of the cache. A SinglyLinkedList cannot efficiently support this operation, as it does not provide access to the previous node, making removal from the middle costly.

• Instead of a SinglyLinkedList, we can use a DoublyLinkedList, which maintains both prev and next pointers. This allows us to remove and reposition nodes in O(1) time by directly reconnecting the previous and the next nodes.

Low-Level Design

The most efficient way to implement an LRUCache is by using a HashMap for O(1) lookup and a DoublyLinkedList to maintain the access order.

class LRUCache {

    // Inner class to represent (key, value) pair 
    class Node {
        int key, value;
        Node prev, next;

        Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    private Map<Integer, Node> map;
    private int capacity;
    private Node head, tail;

    public LRUCache(int capacity) {...}
    public int get(int key) {...}
    public void put(int key, int value) {...}

}   

Let’s implement each of the core public functionalities step by step.

LRUCache(int capacity)

public LRUCache(int capacity) {
    this.capacity = capacity;
    this.map = new HashMap<>();

    head = new Node(0, 0);
    tail = new Node(0, 0);

    head.next = tail;
    tail.next = head;
}

Instead of letting head and tail point to actual cache entries, we can use dummy nodes to act as fixed boundary markers. This removes the need for null checks when inserting or deleting nodes, since every real node will always have a valid previous and next node.

get(int key)

public int get(int key) {
    Node node = map.get(key);

    if(node == null) return -1;
    
    moveToHead(node);
    return node.value;
}

Operations that modify the list are internal implementation details and can be abstracted into private helper methods to keep the public API clean.

put(int key, int value)

public void put(int key, int value) {
    Node node = map.get(key);

    if(node != null) {
        node.value = value;
        moveToHead(node);
    } else {
        Node newNode = new Node(key, value);

        map.put(key, newNode);
        addNode(newNode);

        // if adding new node exceeds the capacity, remove the least recently used node
        if(map.size() > capacity) {
            Node tailNode = removeTail();
            map.remove(tailNode.key);
        }
    }
}

moveToHead(Node node)

private void moveToHead(Node node) {
    removeNode(node);
    addNode(node);
}

removeNode(Node node)

private void removeNode(Node node) {
    Node prev = node.prev;
    Node next = node.next;

    // Connect previous node to the next node
    prev.next = next;
    next.prev = prev;
}

addNode(Node node)

private void addNode(Node node) {
    // Step 1: Link new node with the current first node
    node.next = head.next;
    head.next.prev = node;

    // Step 2: Link new node with the head
    node.prev = head;
    head.next = node;

    // Final structure: head <-> node <-> previousFirstNode
}

removeTail()

private Node removeTail() {
    Node node = tail.prev;
    removeNode(node);
    return node;
}