Design a Thread-Safe LRU Cache in Java
Fast recall
Quick revision
Core answer
ReentrantLock and demonstrates get/put with eviction.Data structure choice (HashMap + DLL), thread-safety strategy, eviction algorithm correctness, and awareness of concurrency optimizations beyond the naive lock.
Using `LinkedHashMap` with `synchronized` blocks (works but doesn't scale), or moving DLL nodes inside `get` without holding the lock (race-prone).
Walk through stripe-locking, batched ring-buffer recency updates (Caffeine's trick), and W-TinyLFU's hit-rate advantage over plain LRU.
Interview-ready guide
Interview answer
The data structure
HashMap for O(1) lookup, doubly linked list for O(1) recency moves. Map points to list nodes; list orders by recency with sentinel head and tail. On get, look up the node, unlink, move to head, return value. On put, insert at head, evict tail if over capacity.
Doubly linked specifically because we need O(1) removal of an arbitrary node — the one found via the map. Singly linked would require an O(N) scan.
Naive thread-safe version
Wrap everything in a single ReentrantLock. get and put both acquire/release. Correct and simple. Throughput caps at maybe 100K ops/sec because everything serialises — even reads, because get mutates the recency list.
Scaling — striped locks
Partition into N segments by hashCode % N. Each segment is a self-contained LRU with its own lock. Threads on different segments don't contend. Trade-off: LRU is now per-segment, not strictly global — the approximation is fine for hit rate.
This is conceptually what Java 7's ConcurrentHashMap did. Modern ConcurrentHashMap uses lock-free reads with synchronized bin updates.
Caffeine — the production answer
Caffeine decouples the read path from recency updates:
- get is lock-free — just a ConcurrentHashMap lookup
- The 'key X was accessed' event is appended to a per-thread ring buffer (lock-free)
- A background drain batches and applies these to the eviction policy
Result: read throughput near raw ConcurrentHashMap; eviction slightly behind real-time but accurate.
W-TinyLFU is Caffeine's eviction policy — a hybrid using a TinyLFU frequency sketch + an LRU window. Gives 5-10% better hit rate than plain LRU on most workloads, especially under bursty access.
For production: I'd use Caffeine, set maximumSize and expireAfterWrite, done.
Edge cases
- Updating existing key: update value AND move to head, both under lock
- Capacity = 0: reject in constructor
- Null keys/values: reject by contract (mirrors ConcurrentHashMap)
- Iteration: snapshot under lock or document weak-consistency
- Combining TTL with LRU: store expiry per node, lazy-expire on access, periodic sweep
Failure modes
- Single lock: contention bottleneck above ~100K ops/sec
- Striped: per-segment LRU approximation; slightly worse hit rate but scales to ~1M ops/sec
- Caffeine: ~10M ops/sec, better hit rate, adds dependency
- Memory pressure: configure by weight (bytes), not just count
Recommendation
Hand-rolled HashMap+DLL with a single ReentrantLock for the interview answer to demonstrate the data structure understanding. For production, Caffeine — lock-free reads, batched recency updates via ring buffer, W-TinyLFU eviction with better hit rate than LRU. Reserve striped LRU for the educational middle step or for environments where adding a dependency isn't allowed.
Design a Thread-Safe LRU Cache in Java
Direct Answer
Use a HashMap for O(1) lookup + a doubly linked list for O(1) recency moves, guarded by a single lock for the simple version. For high concurrency, prefer ConcurrentHashMap + striped locks (per-segment) or, in production, use Caffeine's W-TinyLFU — lock-free reads, batched recency updates via a ring buffer, and far better hit rate than pure LRU. The interview-favorite version implements the HashMap-plus-DLL approach with a ReentrantLock and demonstrates get/put with eviction.
Common Mistakes & Pitfalls
Using LinkedHashMap with synchronized blocks (works but doesn't scale), or moving DLL nodes inside get without holding the lock (race-prone).
Check your understanding
Answer these without looking back at the article.
- Extend the LRU to support per-key TTL in addition to size-based eviction.
- How would you implement a write-back LRU where modifications are flushed to disk asynchronously?
- Explain Caffeine's W-TinyLFU policy and why it outperforms plain LRU on real workloads.
- Walk through an LFU cache implementation — what data structures change?
Related interview prep categories
2Want a guided curriculum order?
These modules are also sequenced in our flagship backend interview track — open it when you prefer an ordered path instead of browsing by topic.