Introduction

An LRU cache needs two things at once: fast key lookup and fast recency updates. In a concurrent setting that becomes harder, because reads also mutate recency state, so a "thread-safe map plus thread-safe list" is not enough unless the operations across both structures stay consistent.

The Core Data Structure

The standard LRU design combines:

• a hash map from key to node
• a doubly linked list ordered by recency

The map gives O(1) lookup. The list lets you move a recently used node to the front and evict the least recently used node from the back.

In single-threaded code, the algorithm is straightforward:

1. get(key) looks up the node and moves it to the front
2. put(key, value) inserts or updates, then moves the node to the front
3. if capacity is exceeded, evict the tail node

Concurrency complicates this because map and list must be updated together.

Why ConcurrentHashMap Alone Is Not Enough

A common mistake is to think:

• use ConcurrentHashMap for the keys
• use some concurrent deque for recency
• done

That is not enough for a real LRU policy. The problem is that recency and value updates must be atomic with respect to each other. If two threads both read and move the same key at the same time, or one thread evicts while another updates, the cache can become inconsistent.

For correctness, treat the map-plus-list pair as one shared structure.

A Practical Thread-Safe Design

The simplest correct design is:

• a normal hash map
• a normal doubly linked list
• one lock protecting the entire cache

This is not the most scalable design under very high contention, but it is easy to reason about and usually the right first implementation.

1import java.util.HashMap;
2import java.util.Map;
3import java.util.concurrent.locks.ReentrantLock;
4
5public class ConcurrentLruCache<K, V> {
6    private final int capacity;
7    private final Map<K, Node<K, V>> map = new HashMap<>();
8    private final ReentrantLock lock = new ReentrantLock();
9
10    private Node<K, V> head;
11    private Node<K, V> tail;
12
13    public ConcurrentLruCache(int capacity) {
14        this.capacity = capacity;
15    }
16
17    public V get(K key) {
18        lock.lock();
19        try {
20            Node<K, V> node = map.get(key);
21            if (node == null) {
22                return null;
23            }
24            moveToFront(node);
25            return node.value;
26        } finally {
27            lock.unlock();
28        }
29    }
30
31    public void put(K key, V value) {
32        lock.lock();
33        try {
34            Node<K, V> node = map.get(key);
35            if (node != null) {
36                node.value = value;
37                moveToFront(node);
38                return;
39            }
40
41            Node<K, V> newNode = new Node<>(key, value);
42            addToFront(newNode);
43            map.put(key, newNode);
44
45            if (map.size() > capacity) {
46                Node<K, V> victim = removeTail();
47                map.remove(victim.key);
48            }
49        } finally {
50            lock.unlock();
51        }
52    }
53
54    private void moveToFront(Node<K, V> node) {
55        if (node == head) return;
56        removeNode(node);
57        addToFront(node);
58    }
59
60    private void addToFront(Node<K, V> node) {
61        node.prev = null;
62        node.next = head;
63        if (head != null) head.prev = node;
64        head = node;
65        if (tail == null) tail = node;
66    }
67
68    private void removeNode(Node<K, V> node) {
69        if (node.prev != null) node.prev.next = node.next;
70        if (node.next != null) node.next.prev = node.prev;
71        if (node == head) head = node.next;
72        if (node == tail) tail = node.prev;
73    }
74
75    private Node<K, V> removeTail() {
76        Node<K, V> oldTail = tail;
77        removeNode(oldTail);
78        return oldTail;
79    }
80
81    private static class Node<K, V> {
82        K key;
83        V value;
84        Node<K, V> prev;
85        Node<K, V> next;
86
87        Node(K key, V value) {
88            this.key = key;
89            this.value = value;
90        }
91    }
92}

This keeps the map and list in sync because all state transitions happen under one lock.

Read Performance Tradeoff

The downside is that get is also a write to recency order, so it needs the same lock. That can limit throughput when the cache is read-heavy.

There are a few common strategies:

• accept the single lock because it is simple and correct
• relax exact LRU semantics and batch recency updates
• shard the cache into multiple smaller LRU segments
• use a production-grade library that already solved the concurrency tradeoffs

Exact concurrent LRU is harder than it looks. Many high-performance caches use approximations of LRU because strict recency under concurrency is expensive.

Eviction Race Conditions

Eviction is where broken implementations usually show up. If one thread decides to evict while another thread is still promoting or updating the same node, you can get:

• stale map entries
• list corruption
• lost updates

That is why any eviction path must hold the same synchronization that protects list movement and map mutation.

When to Use a Library

If you are building infrastructure code for production rather than learning the algorithm, prefer a mature cache library. A good library will handle:

• concurrency
• eviction correctness
• memory visibility
• performance tuning

Writing your own concurrent LRU cache is a valuable exercise, but it is rarely the first operational choice when a production library is available.

Common Pitfalls

• Combining a concurrent map with an independent queue or list and assuming the result is automatically a correct LRU cache.
• Treating get as a read-only operation even though it changes recency state and therefore needs synchronization.
• Implementing eviction without the same lock that protects map and list updates.
• Over-engineering a lock-free design before proving a simple locked design is insufficient.
• Reimplementing production cache infrastructure when a maintained library would provide better correctness and performance characteristics.

Summary

• A correct LRU cache needs both fast lookup and consistent recency ordering.
• In concurrent code, the map and linked-list updates must stay synchronized as one unit.
• A single-lock implementation is the simplest correct design.
• Exact LRU under high concurrency is expensive, so production systems often use approximations or mature libraries.
• If you implement your own, focus on correctness first, especially around get and eviction races.