LLD for LRU Cache: Designing a High-Performance Cache

Scenario context

A cache is a small, fast store that holds a hot subset of a larger, slower dataset. When your application repeatedly reads the same data from a database, remote API, or disk, caching the results in memory slashes latency from milliseconds to microseconds.

Because caches have limited capacity, they need an eviction policy — a rule for deciding which item to drop when the cache is full and a new item arrives.…

This walkthrough focuses on Eviction Policies: Why LRU Makes Sense.

Before making a design choice, clarify:

• A cache is a small, fast store that holds a hot subset of a larger, slower dataset.
• When your application repeatedly reads the same data from a database, remote API, or disk, caching the results in memory slashes latency from milliseconds to microseconds.
• Because caches have limited capacity, they need an eviction policy — a rule for deciding which item to drop when the cache is full and a new item arrives.

Concepts in play: caching, low-level-design-systems, hash-tables-and-bloom-filters, database-indexing

Stage 1 — The Browser History Analogy

• Your browser "Back" button stores the pages you visited most recently.
• If you visit 100 pages and your browser only keeps 10 in memory, it drops the oldest one.
• LRU says: the item you haven't needed in the longest time is the least valuable — evict it first.
• The classic challenge is implementing this in O(1) for both get and put .

Observable outcome: The classic challenge is implementing this in O(1) for both get and put .

Stage 2 — The HashMap + Doubly Linked List Architecture

• architecture { "version": 1, "title": "The HashMap + Doubly Linked List Architecture - Subsystem Overview", "description": "Decoupled system architecture isolating ingress, stateless logic, and persistent datastores.",…
• Together, both get() and put() complete in O(1) — something neither data structure can achieve alone.
• The arrow represents the dependency: every cache operation starts at the HashMap to retrieve the node reference, then hands off to the DLL for order-preserving position updates.
• • HashMap: Maps each key to its Node in the list— O(1) access.

flowchart LR
    HashMap["HashMap (key  node pointer)"] --> DLL["Doubly Linked List Head (MRU)  ...  Tail (LRU)"]

Observable outcome: - HashMap: Maps each key to its Node in the list— O(1) access.

Stage 3 — Step-by-Step Trace: Capacity = 3

• Key: get(1) bumped 1 to head, so 3 became the new tail.
• When 4 arrives, 2 gets evicted — not 3.
• 📊 Cache Entry Lifecycle States The state machine captures the complete lifecycle of a single cache entry from insertion to eviction.
• A node enters as HOT (placed at the head/MRU position) and returns to HOT whenever get() is called on it, resetting its eviction clock with each access.

stateDiagram-v2
    [*] --> HOT : put(key, val)  inserted at head (MRU)
    HOT --> HOT : get(key)  moved back to head
    HOT --> COLD : newer entries push it toward tail
    COLD --> HOT : get(key)  moved back to head (MRU)
    COLD --> EVICTED : cache full  tail node removed on next put()
    EVICTED --> [*]

Observable outcome: A node enters as HOT (placed at the head/MRU position) and returns to HOT whenever get() is called on it, resetting its eviction clock with each access.

Stage 4 — LRU Cache Operation Flow

• Every get and put follows a deterministic decision path.
• Tracking which branch executes is the key to understanding unexpected evictions.
• This decision tree captures every execution path through get() and put() in a single view.
• The left branch ( get ) is two steps: a HashMap lookup, then either a miss (return -1) or a move-to-head followed by returning the value.

flowchart TD
    A[Request arrives] --> B{get or put?}
    B -->|"get(key)"| C{Key in HashMap?}
    C -->|No| D["Return -1 (cache miss)"]
    C -->|Yes| E["Move node to head (mark as MRU)"]
    E --> F["Return value (cache hit)"]
    B -->|"put(key, val)"| G{Key exists?}
    G -->|Yes| H[Update value Move node to head]
    G -->|No| I[Create new node Insert at head]
    I --> J{Size > capacity?}
    J -->|Yes| K[Remove tail node Delete from HashMap]
    J -->|No| L[Done ]
    K --> L

Observable outcome: The left branch ( get ) is two steps: a HashMap lookup, then either a miss (return -1) or a move-to-head followed by returning the value.

Stage 5 — How the Four OOP Pillars Shape the LRU Cache Design

• Object-oriented design is not just syntax — it is a discipline for assigning clear, bounded responsibilities to each class.
• The LRU cache is a compact example of all four OOP pillars working together in a single design.
• Encapsulation: The Node<K,V inner class — with its prev and next pointers — is declared private static .
• A dedicated DoublyLinkedList helper manages all pointer manipulation.

classDiagram
    direction LR
    class Cache~K,V~ {
        <>
        +get(key K) Optional~V~
        +put(key K, value V) void
        +size() int
        +capacity() int
    }
    class LruCache~K,V~ {
        -capacity int
        -map HashMap
        -head Node
        -tail Node
        +get(key K) Optional~V~
        +put(key K, value V) void
    }
    class LfuCache~K,V~ {
        -capacity int
        -freqMap HashMap
        +get(key K) Optional~V~
        +put(key K, value V) void
    }
    class Node~K,V~ {
        -key K
        -value V
        -prev Node
        -next Node
    }
    Cache <|.. LruCache : implements
    Cache <|.. LfuCache : implements
    LruCache *-- Node : has-a (private)

Observable outcome: A dedicated DoublyLinkedList helper manages all pointer manipulation.

Stage 6 — SOLID Principles in the LRU Cache Design

• Getting the algorithm right is only half the job in LLD.
• The other half is designing classes that are easy to extend, test, and replace independently.
• Every SOLID principle has a concrete mapping in the LRU cache design.
• SRP in practice: When a pointer-corruption bug surfaces, you look inside DoublyLinkedList .

Observable outcome: SRP in practice: When a pointer-corruption bug surfaces, you look inside DoublyLinkedList .

End-to-end outcome

A cache is a small, fast store that holds a hot subset of a larger, slower dataset.

Alternatives considered

Decision Guide: Choosing the Right Cache Implementation

Start with synchronized methods for correctness.

Failure and degraded modes

Trade-offs & Failure Modes: Thread Safety and Cache Invalidation

• Detection: The basic implementation above is not thread-safe.
• User or operator impact: The basic implementation above is not thread-safe.