skip to content

What are the concurrency and design trade-offs of a LinkedHashMap-based LRU cache, and when would you choose a dedicated cache library instead?

level: principalimportance: nice to knowfreq 35%

answer

  1. Access-order get mutates → reads contend
  2. synchronizedMap serializes everything
  3. Out of the box: count-LRU; no TTL/weight/stats
  4. LRU suffers scan pollution
  5. Caffeine: concurrent reads, expiry, weights, stats

basics

~20 s

A LinkedHashMap LRU is simple but not thread-safe, and even reads mutate it in access-order mode, so concurrent use needs exclusive locking. For a busy shared cache pick a library like Caffeine, with concurrent access, expiry and weighted size bounds.

solid answer

~50 s

A LinkedHashMap LRU cache is the textbook implementation, but it has real limits. It is not thread-safe, and in access-order mode `get` is a structural modification, so reads cannot run concurrently without an exclusive lock — `Collections.synchronizedMap` works but serializes all access. Out of the box it evicts only the list's head when a new entry goes in, bounded by whatever `removeEldestEntry` tests: no TTL, no async loading, no eviction metrics. Strict LRU also has a known weakness: a scan of one-off keys can flush hot entries (cache pollution), and a 100-entry cache loses all 100 hot keys to 100 one-off puts. I reach for Caffeine when the cache is shared across threads, read-heavy, or needs those features: it batches read reordering instead of locking per read, and its Window TinyLfu policy weighs frequency and recency. I'd only keep the LinkedHashMap version for small single-threaded caches, tests, or when zero dependencies matter.

go deeper

for a junior

Knows the LinkedHashMap LRU is not thread-safe and that real apps often use a cache library.

for a middle

Explains that synchronizedMap is needed and that access-order get mutates, plus that TTL/weight aren't supported.

for a senior

Articulates the read-contention problem, the policy limitations, and chooses a dedicated library such as Caffeine for concurrent, feature-rich caching.

for a principal

Reasons about eviction-policy algorithms (LRU vs LFU vs frequency-aware admission), scan resistance, 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 the documentation says "merely querying the map with `get` is a structural modification": a `get` that moves an entry rewrites links 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 reads do not scale and under read-heavy load the cache can become 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 Out of the box, the recipe gives **one** policy: strict LRU bounded by **entry count**. `removeEldestEntry` can test other conditions, such as the eldest entry's age, but it runs only when a new entry goes in, and its return value removes only the head. The class 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, so their next reads miss. The worst case: a 100-entry cache with 100 hot keys, each read ten times, keeps none of them after 100 one-off `put`s. A policy that weighs how often an entry was used, not only how recently, can keep the hot set through such a scan. ## When a dedicated library wins A dedicated cache library exists to cover the gaps above. Reach for **Caffeine**: Guava's `CacheBuilder` documentation says to prefer it over Guava's own caching API and names it that API's successor. It offers: - **Concurrency:** reads do not all queue on one global lock. They record reorders in a striped ring buffer, which is allowed to lose some, and the changes reach the eviction order later, in batches. - **Eviction or admission policy:** Window TinyLfu, which weighs how often an entry was used as well as how recently, so it can keep the hot set through a burst of one-off keys. - **Expiry:** expire-after-write, expire-after-access, and refresh. - **Sizing:** a bound by entry count or by a custom weight. - **Loading:** an atomic get-or-load, so one miss does not start a stampede of duplicate loads, with asynchronous variants. - **Observability:** hit rate, load times, eviction counts. ## 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 a dedicated library. 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 or one-hit-wonder pollution, and how does a frequency-aware policy mitigate it?
    A burst of keys used only once sweeps through an LRU and evicts hot entries. A frequency-aware policy weighs how often entries were used, so it can refuse to let a rarely-used key displace a frequently-used one.
  • 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 a library'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. A dedicated cache library is the power tool with safety guards and gauges — what you want when a whole crew is using it at once all day.

  • 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 — a scan of one-off keys can evict its whole hot set.
  • Assuming LinkedHashMap supports TTL or weight-based eviction natively.

LinkedHashMap access order and removeEldestEntry
Java 1.4

Assumes JDK 27; LinkedHashMap.java is byte-identical at JDK 25, and the recipe dates from the class's arrival in 1.4.

context