Skip to content

LRU and LFU Cache#

Problem statement (interviewer prompt)

Design a thread-safe in-memory cache with get(key) and put(key, value) both in O(1). Implement both LRU (least-recently-used) and LFU (least-frequently-used) eviction. Discuss thread-safety, TTL, and stats counters.

classDiagram
  class Cache {
    <<interface>>
    +get(key) value
    +put(key, value)
  }
  class LRUCache {
    -capacity : int
    -map : HashMap
    -head, tail : Node
    +get(key)
    +put(key, value)
    -moveToFront(n)
    -evictLRU()
  }
  class LFUCache {
    -capacity : int
    -keyToNode : HashMap
    -freqToList : HashMap~int, DLL~
    -minFreq : int
    +get(key)
    +put(key, value)
    -incrementFreq(n)
    -evictLFU()
  }
  class Node {
    +key, value, freq : int
    +prev, next : Node
  }
  Cache <|.. LRUCache
  Cache <|.. LFUCache
  LRUCache *-- Node
  LFUCache *-- Node

Both rely on the same trick: a hashmap to find the entry in O(1), a doubly-linked list to remove it in O(1).

The cache interview classic. The standard interview answer is the O(1) hashmap + doubly-linked-list. Production caches go further: tinyLFU, sharded locks, TTL, and stats.

LRU - O(1) hashmap + doubly-linked list#

classDiagram
  class LRUCache {
    -capacity : int
    -map : HashMap~K, Node~
    -head : Node
    -tail : Node
    +get(k) V
    +put(k, v)
    -addToFront(n)
    -remove(n)
    -moveToFront(n)
  }
  class Node {
    +key : K
    +value : V
    +prev : Node
    +next : Node
  }
  LRUCache *-- "many" Node
  LRUCache --> Node : head, tail
class Node:
    __slots__ = ("k", "v", "prev", "next")

class LRUCache:
    def __init__(self, cap):
        self.cap = cap
        self.map = {}
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, n):
        n.prev.next = n.next
        n.next.prev = n.prev

    def _add_front(self, n):
        n.next = self.head.next
        n.prev = self.head
        self.head.next.prev = n
        self.head.next = n

    def get(self, k):
        if k not in self.map: return -1
        n = self.map[k]
        self._remove(n)
        self._add_front(n)
        return n.v

    def put(self, k, v):
        if k in self.map:
            n = self.map[k]
            n.v = v
            self._remove(n)
            self._add_front(n)
        else:
            if len(self.map) == self.cap:
                lru = self.tail.prev
                self._remove(lru)
                del self.map[lru.k]
            n = Node(); n.k = k; n.v = v
            self._add_front(n)
            self.map[k] = n

LFU - frequency buckets#

classDiagram
  class LFUCache {
    -capacity : int
    -minFreq : int
    -keyToNode : HashMap~K, Node~
    -freqToList : HashMap~int, DLinkedList~
    +get(k) V
    +put(k, v)
    -increment(n)
  }
  class Node {
    +k, v, freq
    +prev, next
  }
  class DLinkedList {
    +head, tail
    +addFront(n)
    +remove(n)
    +removeLast() Node
  }
  LFUCache *-- Node
  LFUCache *-- DLinkedList

Maintain a map freq -> doubly-linked list of nodes at that frequency. On access, remove the node from its current list, increment frequency, add to the new list. Track minFreq to know which list to evict from.

Thread-safety options#

Strategy Trade-off
synchronized whole map Simplest; lock contention at scale
ReadWriteLock Better for read-heavy
Striped locks: shard map by hash(key) % N Good throughput
Lock-free CAS Hard; rarely worth it
Concurrent linked-hash-map (Java LinkedHashMap) Use Collections.synchronizedMap or library

TTL eviction#

Two approaches:

  • Lazy: check expiresAt on read; treat expired as miss.
  • Active: background thread sweeps expired entries.

Caffeine combines both with hierarchical timer wheels for O(1) expiration scheduling.

Production caches#

Library Strategy
Guava Cache Old; LRU + TTL
Caffeine W-TinyLFU; near-optimal hit rate, sharded locks
Redis LRU / LFU configurable; sampled (approximate) eviction
Memcached Slab allocator + LRU within slab
moka (Rust) Caffeine port

W-TinyLFU uses a small admission filter (TinyLFU sketch) in front of LRU; entries must be hot enough to be admitted.

Stats and metrics#

class CacheStats:
    hits: int
    misses: int
    evictions: int
    @property
    def hit_rate(self): return self.hits / (self.hits + self.misses)

Expose via JMX / Prometheus; alert on hit-rate drops.

Edge cases#

  • cap = 0: every get is a miss.
  • put updating existing key: update value and move to front; doesn't grow size.
  • Concurrent put of same key: last writer wins; protect with lock.
  • LFU tie-breaker on equal frequency: LRU within the bucket.

Where LRU/LFU cache fits#

flowchart TB
  LRU((LRU / LFU<br/>cache))
  CACHE[Caching strategies<br/>system context]
  DSC["Data structures complexity<br/>O(1) analysis"]
  CON[Concurrency primitives<br/>thread-safe variants]
  DC[Distributed cache<br/>system-design sibling]
  CACHE --> LRU
  DSC --> LRU
  CON --> LRU
  LRU -. scaled .-> DC

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class LRU service;
    class CACHE,DSC,CON,DC datastore;

Glossary & fundamentals#

Tag Concept What it is Page
HLD Caching strategies the broader system context caching-strategies
LLD Data structures complexity the analysis behind O(1) data-structures-complexity
LLD Concurrency primitives the thread-safe variants concurrency-primitives
HLD Distributed cache the system-design sibling distributed-cache

Quick reference#

API#

get(k) -> v | -1
put(k, v)

LRU recipe (O(1))#

  • HashMap
  • Doubly-linked list (head=MRU, tail=LRU)
  • On get/put: move to head; evict tail when full

LFU recipe (O(1))#

  • HashMap
  • HashMap of nodes at that frequency
  • Track minFreq for eviction
  • On access: bump freq; move node between lists

Thread-safety#

Strategy Use
synchronized Tiny caches
ReadWriteLock Read-heavy
Striped locks Production default
Caffeine Just use it

TTL#

  • Lazy: check expiresAt on read
  • Active: timer-wheel sweeper

Production libraries#

  • Caffeine (Java) - W-TinyLFU, best hit rate
  • moka (Rust)
  • Redis - sampled approximate LRU/LFU
  • Memcached - slab + LRU

Metrics#

  • hits, misses, hit_rate, evictions, p99 get

Refs#

  • Caffeine GitHub
  • TinyLFU paper (arXiv 1512.00727)
  • Redis eviction docs

FAQ#

How do you implement an LRU cache in O(1)?#

Combine a HashMap from key to node with a doubly-linked list ordered by recency; get and put move the node to the head and evict from the tail in O(1).

How does an LFU cache work?#

Maintain a HashMap key to node and a HashMap frequency to doubly-linked list of nodes with that count. On access, bump the node into the next-higher frequency list.

When should you choose LFU over LRU?#

Choose LFU when access patterns have a stable hot set that benefits from long-term retention; LRU adapts faster but evicts hot items during scans.

How do you make an LRU cache thread-safe?#

Wrap mutations in a single mutex or use a striped lock per shard. Concurrent variants like Caffeine use read buffers and async maintenance to avoid serialisation.

How is TTL added to an LRU cache?#

Store an expires_at per entry, check it on get, and run a background sweeper or check on access to evict stale items independent of recency order.

Further reading#

Video walkthrough

LRU Cache Implementation: LeetCode System Design Pattern : via LLD Walkthrough