What are the concurrency and design trade-offs of a LinkedHashMap-based LRU cache, and when would you choose a dedicated cache library instead?
answer
- Access-order get mutates → reads contend
- synchronizedMap serializes everything
- Only strict count-LRU; no TTL/weight/stats
- LRU suffers scan pollution
- Caffeine: lock-free reads, W-TinyLFU, TTL, weight, stats
basics
~20 sA LinkedHashMap LRU is simple but not thread-safe, and even reads mutate it in access-order mode, so concurrent use needs full locking. For real systems pick a library like Caffeine that gives concurrent access, expiry, and size weighting.
solid answer
~50 sA LinkedHashMap LRU cache is the textbook implementation, but it has real limits. It is not thread-safe, and in access-order mode every `get` reorders the list, so reads cannot run concurrently without a global lock — `Collections.synchronizedMap` works but serializes all access and kills read throughput. It only supports strict LRU by recency and exact count; no TTL, no size/weight-based bounds, no async loading, no per-entry expiry, no eviction metrics. Strict LRU also has a known weakness: a scan of many one-off keys can flush hot entries (cache pollution). For production I reach for Caffeine: it offers lock-free concurrent reads via a sampling/ring-buffer design, the W-TinyLFU admission policy (much higher hit rates than LRU under scans), TTL/refresh-after-write, weight-based bounds, async cache loaders, and stats. I'd only keep the LinkedHashMap version for small single-threaded caches, tests, or when zero dependencies matter.
go deeper
Knows the LinkedHashMap LRU is not thread-safe and that real apps often use a cache library.
Explains that synchronizedMap is needed and that access-order get mutates, plus that TTL/weight aren't supported.
Articulates the read-contention problem, the policy limitations, and chooses Caffeine for concurrent, feature-rich caching.
Reasons about eviction-policy algorithms (LRU vs LFU vs W-TinyLFU), scan resistance, lock-free read scaling, observability, and the explicit decision criteria for build-vs-library at system scale.
## Recap of the LinkedHashMap LRU You build it by subclassing `LinkedHashMap`, constructing in **access-order** mode (`get`/`put` move the entry to the tail) and overriding `removeEldestEntry` to return `true` once `size() > capacity`, so the head (least-recently-used) entry is evicted. Simple and dependency-free. ## Trade-off 1: thread safety / 'reads are writes' LinkedHashMap is **not synchronized**. Worse, in access-order mode a successful `get` **structurally modifies** the linked list (and bumps `modCount`). That means even concurrent *readers* race with each other, not just readers vs writers. Your options: - `Collections.synchronizedMap(cache)` — a single mutex around every operation. Correct, but it **serializes all access**, so under read-heavy load throughput collapses and the cache becomes a bottleneck. You also must manually synchronize during iteration. - A `ReadWriteLock` doesn't help, because reads take the write lock (they mutate order). This 'reads mutate' property is the core reason LinkedHashMap doesn't scale as a shared cache. ## Trade-off 2: policy expressiveness The LinkedHashMap cache supports exactly **one** policy: strict LRU bounded by **entry count**. It has no: - **TTL / expiry** (expire-after-write or -access), - **weight-based sizing** (e.g., bound by total bytes, not item count), - **async / atomic loading** (`get`-or-compute without dog-piling), - **eviction listeners / statistics** (hit ratio, eviction counts). You'd have to bolt all of these on by hand. ## Trade-off 3: LRU's algorithmic weakness Strict LRU is vulnerable to **scan / one-hit-wonder pollution**: a burst of keys accessed once (e.g., a table scan) walks through the cache and evicts genuinely hot entries, tanking the hit rate. Frequency-aware policies handle this far better. ## When a dedicated library wins (Caffeine / Guava) **Caffeine** (the modern successor to Guava Cache) addresses every point above: - **Concurrency:** near-linear read scalability. It records accesses in lock-free per-thread ring buffers and replays them to update eviction order asynchronously, so reads don't contend on a global lock. - **Admission policy:** **W-TinyLFU**, a frequency+recency policy that resists scan pollution and typically beats LRU on hit rate at the same size. - **Expiry:** expire-after-write, expire-after-access, refresh-after-write, variable per-entry expiry. - **Sizing:** maximumSize *or* maximumWeight with a custom weigher. - **Loading:** `LoadingCache` with atomic compute, async/`CompletableFuture` variants that prevent cache stampedes. - **Observability:** `recordStats()` exposes hit rate, load times, eviction causes. ## When the LinkedHashMap version is still the right call - **Single-threaded** or coarsely-locked, low-traffic contexts. - **Tests / examples / interview answers** where you must show the mechanism. - **Zero-dependency** constraints (no extra jar allowed). - Tiny, fixed caches where simplicity beats features. ## The decision framing Ask: is the cache **shared across threads**, **read-heavy**, or does it need **TTL / weight / metrics / scan resistance**? If yes to any, use Caffeine. If it's a small, single-threaded, count-bounded LRU and you want no dependencies, the LinkedHashMap subclass is perfectly fine — and worth knowing because it's the canonical 'implement an LRU' exercise.
- Why doesn't a ReadWriteLock help an access-order LinkedHashMap cache?Because in access-order mode a get structurally mutates the list, so a read must acquire the write lock, not the read lock. The read/write distinction collapses and you get no concurrency benefit over a plain mutex.
- What is scan/one-hit-wonder pollution and how does W-TinyLFU mitigate it?A burst of keys used only once sweeps through an LRU and evicts hot entries. W-TinyLFU admits a new entry only if its estimated frequency exceeds the victim's, so rarely-used scan keys can't displace frequently-used ones, preserving hit rate.
- When is the plain LinkedHashMap LRU still the right choice?Single-threaded or low-traffic, count-bounded caches, test fixtures, interview demonstrations, or zero-dependency environments where Caffeine's extra features and jar aren't justified.
The LinkedHashMap LRU is a hand-cranked tool: great for a quick job alone in the workshop. Caffeine is the power tool with safety guards and gauges — what you want when a whole crew is using it at once all day.
saying these in an interview costs you the question
- Claiming Collections.synchronizedMap makes it scale for concurrent reads — it serializes everything.
- Saying a ReadWriteLock fixes access-order concurrency (reads mutate, so they need the write lock).
- Believing LRU is always optimal — it degrades badly under scans versus frequency-aware policies.
- Assuming LinkedHashMap supports TTL or weight-based eviction natively.