Implementing a Thread-Safe LRU Cache with High Concurrency

Introduction to Implementing a Thread-Safe LRU Cache with High Concurrency

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.

What You'll Learn

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.

Understanding the LRU Cache with High Concurrency

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.

Building the LRU Cache Class

Let's implement the LRU cache with these structures: Java import java.util.concurrent.ConcurrentHashMap; import java.util.concurrent.ConcurrentLinkedDeque; import java.util.concurrent.locks.ReentrantLock; public class LRUCache<K, V> {private final int capacity; private final ConcurrentHashMap<K, V> cache; private final ConcurrentLinkedDeque<K> accessOrder; private final ReentrantLock lock = new ReentrantLock(); public LRUCache(int capacity) {this.capacity = capacity; this.cache = new ConcurrentHashMap<>(); this.accessOrder = new ConcurrentLinkedDeque<>();}} import java.util.concurrent.ConcurrentHashMap; import java.util.concurrent.ConcurrentLinkedDeque; import java.util.concurrent.locks.ReentrantLock; public class LRUCache<K, V> {private final int capacity; private final ConcurrentHashMap<K, V> cache; private final ConcurrentLinkedDeque<K> accessOrder; private final ReentrantLock lock = new ReentrantLock(); public LRUCache(int capacity) {this.capacity = capacity; this.cache = new ConcurrentHashMap<>(); this.accessOrder = new ConcurrentLinkedDeque<>();}} 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.

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

Implementing the Put Method

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

public void put(K key, V value) {
    lock.lock();
    try {
        if (cache.containsKey(key)) {
            cache.put(key, value); // Update the value
            accessOrder.remove(key);
            accessOrder.addFirst(key); // Update access order
        } else {
            if (cache.size() >= capacity) {
                K lruKey = accessOrder.pollLast(); // Remove least recently used
                if (lruKey != null) {
                    cache.remove(lruKey);
                }
            }
            cache.put(key, value); // Add new key-value pair
            accessOrder.addFirst(key); // Mark as most recently used
        }
    } finally {
        lock.unlock();
    }
}

public void put(K key, V value) {
    lock.lock();
    try {
        if (cache.containsKey(key)) {
            cache.put(key, value); // Update the value
            accessOrder.remove(key);
            accessOrder.addFirst(key); // Update access order
        } else {
            if (cache.size() >= capacity) {
                K lruKey = accessOrder.pollLast(); // Remove least recently used
                if (lruKey != null) {
                    cache.remove(lruKey);
                }
            }
            cache.put(key, value); // Add new key-value pair
            accessOrder.addFirst(key); // Mark as most recently used
        }
    } finally {
        lock.unlock();
    }
}

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.

Concurrent Access with the Main Class

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

Java

import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;

public class Main {

    public static void main(String[] args) throws InterruptedException {
        LRUCache<String, String> cache = new LRUCache<>(3);
        ExecutorService executor = Executors.newFixedThreadPool(5);

        // Simulate concurrent access
        for (int i = 1; i <= 5; i++) {
            int threadId = i;
            executor.submit(() -> {
                String key = "key" + threadId;
                cache.put(key, "value" + threadId);
                System.out.println("Thread-" + threadId + " put " + key);

                // Access cache
                for (int j = 1; j <= 5; j++) {
                    String k = "key" + j;
                    String value = cache.get(k);
                    System.out.println("Thread-" + threadId + " got " + k + ": " + value);
                }
            });
        }

        executor.shutdown();
        executor.awaitTermination(1, TimeUnit.MINUTES);
    }
}

import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;

public class Main {

    public static void main(String[] args) throws InterruptedException {
        LRUCache<String, String> cache = new LRUCache<>(3);
        ExecutorService executor = Executors.newFixedThreadPool(5);

        // Simulate concurrent access
        for (int i = 1; i <= 5; i++) {
            int threadId = i;
            executor.submit(() -> {
                String key = "key" + threadId;
                cache.put(key, "value" + threadId);
                System.out.println("Thread-" + threadId + " put " + key);

                // Access cache
                for (int j = 1; j <= 5; j++) {
                    String k = "key" + j;
                    String value = cache.get(k);
                    System.out.println("Thread-" + threadId + " got " + k + ": " + value);
                }
            });
        }

        executor.shutdown();
        executor.awaitTermination(1, TimeUnit.MINUTES);
    }
}

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.