Build an LRU Cache in Java: O(1), TTL and Thread Safety

What you'll learn: By the end of this lesson you will be able to explain why an LRU cache needs a hash map and a doubly linked list, write one in Java with O(1) get, put and remove, add a time to live read from an injectable clock, say why even a read must take the lock, compare a single lock, a lock with a timeout and lock striping, and name the failure of holding the cache lock while loading from the database.

A desk is covered in books. Each time you use one you put it on top of the pile, and when the desk is full the book at the bottom goes back to the shelf. The pile is the record of use. An LRU cache is that pile; the hard parts are doing it in constant time and letting several people reach for it at once.

Eviction Policies: LRU, LFU and TTL explains what LRU bets on and where it fails. This lesson builds one. It assumes you have read Caching Basics.

Verified with Java 25.0.3 and Gradle 9.8.2 on 2026-11-08. The code is in the repository under examples/backend/labs/lru-cache (single-threaded) and examples/backend/labs/concurrent-lru-ttl-cache (thread-safe, with a TTL).

The core idea

An LRU cache keeps a hash map for finding entries and a doubly linked list for ordering them. The map answers "is this key here?" in O(1). The list answers "which entry is least recently used?" in O(1), because that entry is always at one end and moving any entry to the other end is two pointer changes. Neither structure alone does both jobs.

Three kinds of example run through the lesson, each labelled:

• Minimal example: the single-threaded LruCache and its walk-through.
• Realistic example: a ShopStream app server keeping a short-lived local copy of hot product data, in "In practice".
• Failure example: two threads corrupting the list, and a cache that holds its lock while it loads.

Why two structures

A hash map alone has no order, so finding the least recently used entry means scanning. A list alone keeps the order, but finding a key means walking it. Together, the map's values point straight at the list's nodes, so a lookup lands on the node and the node can unlink itself.

Figure 1. The two structures and how they connect. How to read this: the top row is the recency list, most recent next to the head. Arrows show the next pointers; each node also points back to its predecessor. Every map entry points at its node, so a lookup finds the node directly. The sentinels are fixed nodes that remove every "is this the first or last node?" special case.

The operations are then short:

1. get(key): look the key up in the map. If absent, return null. If present, unlink its node and relink it right after the head, and return the value.
2. put(key, value): if the key exists, replace the value and move the node to the front. Otherwise, if the cache is full, unlink the node before the tail and remove its key from the map; then add a new node at the front and in the map.
3. remove(key): remove from the map and unlink the node.

Figure 2. The put operation. How to read this: the only branch that can remove data is the full-cache branch, and it removes exactly one entry, the one next to the tail.

The shortcut, and why the lesson still builds one

The JDK has the structure already. The LinkedHashMap documentation describes a constructor that makes the encounter order "the order in which its entries were last accessed, from least-recently accessed to most-recently (access-order)" and calls it well suited to building LRU caches. You override removeEldestEntry, which put calls after inserting an entry, and return true when the size passes your limit.

Two warnings from the same page matter. The class is not synchronized, and in an access-ordered map "merely querying the map with get is a structural modification", so wrapping it for threads means wrapping every get too. Building the list by hand is still worth doing once: it shows where the cost sits and makes TTL, callbacks and per-stripe capacity easy to add.

Build it: the single-threaded core

Goal. An LRU cache with O(1) get, put and remove, and an eviction callback, that you can read in one sitting.

Setup. From examples/backend: ./gradlew :labs:lru-cache:test runs its 13 tests and ./gradlew -q :labs:lru-cache:run prints a walk-through. The code is LruCache.java in labs/lru-cache. This is the heart of put:

public void put(K key, V value) {
    Objects.requireNonNull(key, "key");
    Node<K, V> existing = index.get(key);
    if (existing != null) {
        existing.value = value;
        unlink(existing);
        linkFirst(existing);
        return;
    }
    if (index.size() == capacity) {
        Node<K, V> eldest = tail.prev;
        unlink(eldest);
        index.remove(eldest.key);
        onEvict.accept(eldest.key, eldest.value);
    }
    Node<K, V> node = new Node<>(key, value);
    index.put(key, node);
    linkFirst(node);
}

unlink and linkFirst are four pointer assignments each. containsKey does not change recency: a membership test is not a use.

Break it. Delete the two lines unlink(node); linkFirst(node); from get. The cache becomes FIFO and the test that checks a touched key survives fails.

Add a TTL

A time to live bounds how stale an entry can be, which an eviction policy does not. The lab wraps LruCache in TtlLruStore, which stores each value with expiresAt = now + ttl, reading now from an injected clock so that tests control time. Three decisions are baked in, and each could go the other way:

The lazy choice has a visible effect: after the TTL passes, size() still counts the entry until someone touches it. Redis makes the same split, expiring a key when it is accessed and also by periodically testing a few keys at random.

Make it thread-safe

An LRU get is a write: it rewrites four pointers. So two readers are two writers, and a read-write lock does not help, because the reads need the exclusive side anyway. The simplest correct answer is one lock around everything.

Figure 3. One possible interleaving of two unsynchronized reads. How to read this: both threads run the same unlink code. If thread B starts after thread A has cleared the pointers, B dereferences null. Other interleavings corrupt the list silently, with a node linked twice or lost. This shows that a failure is possible, not that it happens on every run.

The lab has three protections for one TtlLruStore:

The Java Language Specification says a synchronized method locks an object "as if by use of a synchronized statement". SynchronizedCache is only delegation:

@Override
public synchronized V get(K key) {
    return store.get(key);
}

ReentrantLock follows the documented idiom: lock(), then a try block, with unlock() as the first statement of finally. Its fairness option favours the longest-waiting thread, and the Javadoc warns that fair locks may display lower overall throughput, "often much slower". Its timed tryLock is what tryGet uses: a caller that cannot get the lock within the timeout learns that, and can go to the source of truth instead of queueing.

Striping splits the key space. The lab hashes a key with the bit-spreading step java.util.HashMap uses, then takes a modulo:

public int stripeOf(K key) {
    int h = key.hashCode();
    return Math.floorMod(h ^ (h >>> 16), stores.length);
}

The capacity is divided between the stripes. That is the price of striping, and it has a concrete failure.

Figure 4. A cache of capacity 4 striped in two. How to read this: threads 1 and 2 queue on stripe 0's lock while thread 3 uses stripe 1 freely. Each stripe can hold only two entries, whatever the other holds.

Edge case: eviction while there is room

The Demo puts a, c and e into a capacity-4 cache. Their hash codes are 97, 99 and 101, all odd, so all three go to stripe 1, which holds two. An exact LRU keeps all three. The striped cache evicts a while half its slots are empty. Skewed keys produce exactly this, so size stripes for the key distribution you have, and measure hit ratios, not only throughput.

Run it

Run the tests and the Demo from examples/backend:

./gradlew :labs:concurrent-lru-ttl-cache:check
./gradlew -q :labs:concurrent-lru-ttl-cache:run

The 30 tests include a concurrent test that runs 8 threads, each doing 20,000 mixed get, put and remove calls, against every variant. It checks that no exception occurs, the size never passes the capacity, no key is held twice, no value comes back under the wrong key, and every get is counted once. The Demo prints only facts that do not depend on thread scheduling, so its hit counts and timings are not shown. Expected output, captured from a real run (Java 25.0.3, 2026-11-08):

Thread-safe LRU cache with a TTL: one single-threaded LruCache, three ways to protect it

== 1. Time to live: an entry expires ttl after it was WRITTEN; reads do not extend it ==
t=0     put a=1
t=999   get a -> 1
t=1000  get a -> null   (expired: found, removed, counted as a miss)
size=0 Stats[hits=1, misses=1, evictions=0, expirations=1]
b written at t=1000, read at t=1500 (does not extend); t=1999 get b -> 2
t=2000  get b -> null

== 2. What striping gives up: the exact LRU order ==
Capacity 4. Keys a, c, e land in the same stripe of a 2-stripe cache (hash codes 97, 99, 101 are odd).
synchronized   put a, c, e; get a -> 1     keys held=[a, c, e] size=3 of capacity 4
striped-2      put a, c, e; get a -> null  keys held=[c, e] size=2 of capacity 4
The striped cache dropped 'a' while holding only 2 of its 4 slots: each stripe has its own capacity of 2.

== 3. Eight threads hammer each variant: 8 x 20000 operations (70% get, 30% put) over 64 keys, capacity 32 ==
Only scheduling-independent facts are printed. Hit counts differ from run to run, so they are not.
synchronized   gets issued=111731  hits+misses=111731  size<=capacity=true  keys distinct=true  wrong values or errors=0
reentrant-lock gets issued=111731  hits+misses=111731  size<=capacity=true  keys distinct=true  wrong values or errors=0
striped-4      gets issued=111731  hits+misses=111731  size<=capacity=true  keys distinct=true  wrong values or errors=0

== 4. A lock you can give up on: tryGet with a timeout ==
while the lock is held:     timedOut=true
after the lock is released: timedOut=false value=1
A caller that times out can go to the source of truth instead of queueing behind the lock.

Break it. Remove synchronized from get and put in SynchronizedCache. On the run made while writing this lesson, the concurrent test failed for that variant. A data race does not fail on every run, so a passing run never proves thread safety.

Stretch. Measure the variants with JMH: the lab prints no throughput because a hand-made timing loop would be machine dependent.

What the model leaves out. Byte-size weights, a background sweeper, stampede protection (a planned lesson, Cache Stampede and Hot Keys, covers it), and any claim about which variant is fastest on your hardware.

Figure 5. A choice of variant. How to read this: start at the top. The first question is not about code at all, because a maintained library has done the work you are about to do.

Trade-offs

In practice: a local copy of hot product data on every app server

This is the realistic example. It is an educational scenario on the course's running example, ShopStream, and nothing in it describes a real company. Figures are illustrative or the shared project numbers.

This is a realistic scenario, not a case history.

The situation

ShopStream's catalogue has 100,000 products per region and browsing peaks near 2,300 requests per second across the fleet (shared project numbers). Redis already absorbs most reads (ShopStream Stage 2), but every product page still pays a network round trip to Redis, and a few hundred products receive most of the traffic. The team wants a small in-process copy on each app server for those products, with a short TTL so price edits show quickly.

Starting architecture

Figure 6. Two cache levels. How to read this: a request stops at the first level that has the entry. Each app server has its own local copy, so two servers can briefly show different prices.

Options considered

The decision

Option D for production, with the lab's cache kept as the team's reference for what the library's settings mean. A library such as Caffeine documents an atomic get(key, mappingFunction) on its cache that computes and inserts a missing value, which the hand-written cache above lacks. The capacity of 10,000 entries and a 2-second TTL are illustrative starting values to tune from the hit ratio, not recommendations.

Rollout and verification

A rollout would run the local cache in shadow mode first, comparing what it would have served with Redis's value. The checks: local hit ratio per key family, served values never older than the TTL, thread-pool utilisation unchanged, and price disagreements between servers.

The 2 a.m. failure

The page reads: request latency climbing on every app server and the thread pool full. A developer had added a "load on miss" method that calls the database from inside the cache's locked section. One slow query held the cache lock; every other thread, including those that only wanted a cached value, waited behind it; the pool filled. The checks: a thread dump shows most threads blocked on the cache's lock and one inside the loader. The mitigation is to restart the stuck servers or disable the local cache with a flag. The lasting fix is never to call slow code while holding the lock: look up under the lock, load outside it, then take the lock again to store, and use per-key coordination so a hot miss does not turn into a stampede.

Architect's notes

• Decide the TTL semantics early. From write or from last access changes how stale data can get and how a hot entry behaves.
• Never load under the lock. Anything slow or that can block belongs outside the critical section.
• Measure before striping. Contention is a measurement, not an assumption.
• Expose counters for hits, misses, evictions and expirations: they separate "too small" from "TTL too short".

Common mistakes

• Treating get as read-only. In an LRU it reorders the list.
• Holding the lock while calling the loader. It serialises every thread behind the slowest query.
• Mutable keys. A key whose hashCode changes after insertion cannot be found again.
• Assuming a passing concurrent test proves safety. It can only fail to find a bug.

Key takeaways

• An LRU cache is a hash map plus a doubly linked list: the map finds, the list orders, and both operations are O(1).
• LinkedHashMap in access order is the JDK's version, and in that mode even get is a structural modification.
• A TTL bounds staleness; decide whether it starts at write or at access, and whether removal is lazy.
• Reads of an LRU are writes, so a single exclusive lock is the simple correct design.
• Striping trades exact eviction for parallel access, and skewed keys expose the cost.
• Never call slow code while holding the cache lock.

Practice exercises

Exercise 1 (30 min). Run the single-threaded Demo and predict the eviction order of the cache before each step, then check against the output.

Exercise 2 (45 min). Add a method getOrLoad(key, loader) to SynchronizedCache that loads outside the lock. List the two interleavings in which two threads load the same key, and say why that is acceptable here and what the next lesson adds.

Exercise 3 (2 hours). Run the lab's tests with synchronized removed from get ten times and count the failures. Explain why the count is not zero or ten.

Related reading

• Eviction Policies: LRU, LFU and TTL: what LRU bets on, where it fails and what real caches do.
• Caching Basics: why caches work.
• Advanced Caching: write policies, invalidation, stampedes and hot keys.
• Cache Layers: Client, CDN, Application, Database: where an in-process cache sits.
• ShopStream Stage 2: Scaling Reads: the read path this lesson's example belongs to.

Official documentation

• Oracle, LinkedHashMap (Java 25): access order, removeEldestEntry and synchronization.
• Oracle, ReentrantLock: fairness, timed tryLock and the try/finally idiom.
• Oracle, ConcurrentHashMap: non-blocking retrievals and atomic updates.
• Oracle, Java Language Specification, chapter 8: synchronized methods.
• Caffeine, Population: manual and automatic loading.
• Redis, EXPIRE: passive and active expiry.