Welcome back! In our previous lesson, we explored concurrent image processing pipelines, focusing on how to utilize multiple threads for efficient task coordination. Today, we will expand on that concurrency knowledge by learning how to implement a thread-safe Least Recently Used (LRU) cache with high concurrency. This lesson will deepen your understanding of concurrent data structures and synchronization techniques.

In this session, you'll gain insights into:

• Designing a thread-safe LRU cache suitable for concurrent environments.
• Using ConcurrentHashMap and ConcurrentLinkedDeque for shared data structures.
• Applying advanced synchronization techniques using ReentrantLock to ensure thread safety and optimal performance.

By the end of this lesson, you will be equipped to implement an LRU cache that handles high concurrency efficiently, an essential skill for building scalable applications.

The LRU cache is a widely used caching strategy that removes the least recently used items first when the cache reaches its maximum capacity. Designing a thread-safe LRU cache for a multi-threaded environment is critical to preventing data corruption and ensuring efficient performance.

To achieve this, we can use a ConcurrentHashMap to store the cache entries, which provides thread safety and non-blocking read operations. Additionally, a ConcurrentLinkedDeque tracks the access order of keys, ensuring the least recently used key is removed when necessary. To prevent race conditions when updating the cache or access order, we use a ReentrantLock to ensure safe and consistent changes.

Let's implement the LRU cache with these structures:

Java
Copy to clipboard
1import java.util.concurrent.ConcurrentHashMap;
2import java.util.concurrent.ConcurrentLinkedDeque;
3import java.util.concurrent.locks.ReentrantLock;
4
5public class LRUCache<K, V> {
6    private final int capacity;
7    private final ConcurrentHashMap<K, V> cache;
8    private final ConcurrentLinkedDeque<K> accessOrder;
9    private final ReentrantLock lock = new ReentrantLock();
10
11    public LRUCache(int capacity) {
12        this.capacity = capacity;
13        this.cache = new ConcurrentHashMap<>();
14        this.accessOrder = new ConcurrentLinkedDeque<>();
15    }
16}

In the above code, we initialize the cache with a specific capacity using the ConcurrentHashMap to store the cache entries and the ConcurrentLinkedDeque to keep track of the access order of the keys. The ConcurrentHashMap allows safe, non-blocking read operations from multiple threads, while the ConcurrentLinkedDeque is a double-ended queue that efficiently allows additions and removals from both ends. We also use a ReentrantLock to ensure that only one thread at a time can modify the accessOrder or the cache content.

Now, we’ll implement the get method to retrieve a value from the cache and update its access order.

Java
Copy to clipboard
1public V get(K key) {
2    lock.lock();
3    try {
4        V value = cache.get(key);
5        if (value != null) {
6            // Move key to the front (most recently used)
7            accessOrder.remove(key);
8            accessOrder.addFirst(key);
9        }
10        return value;
11    } finally {
12        lock.unlock();
13    }
14}

In the get method, the lock.lock() method is called at the beginning to ensure the operation is thread-safe before any modifications to the cache's internal structure are made. After acquiring the lock, the cache.get(key) retrieves the value from the cache. If the key exists in the cache (i.e., the value is not null), the key is removed from its current position in the accessOrder deque and added to the front using addFirst(key) to mark it as the most recently used item.

The lock.unlock() method is placed in a finally block to ensure the lock is always released after the operation is complete, even if an exception occurs. This guarantees that other threads can access the cache without being blocked. This structure ensures that multiple threads can safely modify the cache and access order without causing data corruption or race conditions.

Next, we’ll implement the put method to add or update a value in the cache. If the cache exceeds its capacity, the least recently used item will be removed.

Java
Copy to clipboard
1public void put(K key, V value) {
2    lock.lock();
3    try {
4        if (cache.containsKey(key)) {
5            cache.put(key, value); // Update the value
6            accessOrder.remove(key);
7            accessOrder.addFirst(key); // Update access order
8        } else {
9            if (cache.size() >= capacity) {
10                K lruKey = accessOrder.pollLast(); // Remove least recently used
11                if (lruKey != null) {
12                    cache.remove(lruKey);
13                }
14            }
15            cache.put(key, value); // Add new key-value pair
16            accessOrder.addFirst(key); // Mark as most recently used
17        }
18    } finally {
19        lock.unlock();
20    }
21}

In the above put method, we use lock.lock() to ensure that the entire cache update process is thread-safe. If the key already exists in the cache, we update its value and refresh its position in the accessOrder deque by removing and then adding it to the front using addFirst(key).

If the key is new, we check whether the cache has exceeded its capacity using cache.size() >= capacity. If it has, we evict the least recently used item by calling accessOrder.pollLast(), which removes the last entry from the deque, and then remove this key from the cache using cache.remove(lruKey). Finally, the new key-value pair is added to the cache, and the key is marked as most recently used by adding it to the front of the accessOrder. This structure ensures that the cache maintains its size limit and operates efficiently under concurrent access.

Finally, let’s see how this LRU cache handles concurrent access by simulating multiple threads.

Java
Copy to clipboard
1import java.util.concurrent.ExecutorService;
2import java.util.concurrent.Executors;
3import java.util.concurrent.TimeUnit;
4
5public class Main {
6
7    public static void main(String[] args) throws InterruptedException {
8        LRUCache<String, String> cache = new LRUCache<>(3);
9        ExecutorService executor = Executors.newFixedThreadPool(5);
10
11        // Simulate concurrent access
12        for (int i = 1; i <= 5; i++) {
13            int threadId = i;
14            executor.submit(() -> {
15                String key = "key" + threadId;
16                cache.put(key, "value" + threadId);
17                System.out.println("Thread-" + threadId + " put " + key);
18
19                // Access cache
20                for (int j = 1; j <= 5; j++) {
21                    String k = "key" + j;
22                    String value = cache.get(k);
23                    System.out.println("Thread-" + threadId + " got " + k + ": " + value);
24                }
25            });
26        }
27
28        executor.shutdown();
29        executor.awaitTermination(1, TimeUnit.MINUTES);
30    }
31}

In the main class above, we simulate concurrent access by creating five threads using ExecutorService. Each thread interacts with the cache, adding keys with cache.put() and retrieving them with cache.get(). As each thread operates, the console will print the cache interactions, showing how the cache handles multiple concurrent requests.

The fixed thread pool (newFixedThreadPool(5)) creates exactly five threads, which simultaneously access and modify the cache. The thread-safe design of the LRU cache ensures that even with concurrent access, the cache operates correctly, maintaining both its size and access order.

A thread-safe LRU cache is critical for scenarios where fast, reliable data retrieval is needed, such as in web applications or database caching. This design ensures:

• Scalability: By managing cache size and access with minimal locking overhead, it can scale to handle concurrent requests in high-demand environments.
• Performance: Non-blocking read operations from the ConcurrentHashMap combined with synchronized updates ensure efficient access and modification, even under heavy concurrency.
• Robustness: The use of locks prevents race conditions, ensuring data consistency and preventing stale data from being accessed under high concurrency.

Now that you’ve learned how to design and implement a thread-safe LRU cache, it’s time to practice applying these concepts. Let's move on to the practice section, where you’ll test and further solidify your understanding of this lesson!