Building a Least Recently Used (LRU) cache is a rite of passage. It seems simple—just a map and a doubly linked list—but the moment you introduce multi-threading, the complexity spikes. I've seen many developers try to optimize their cache using RwLock to allow multiple concurrent readers, only to find their application freezing in production. Let's look at a classic example of how this happens.

use std::sync::{Arc, RwLock};
use std::collections::HashMap;

struct Node {
    key: String,
    value: String,
    prev: Option<Arc<RwLock<Node>>>,
    next: Option<Arc<RwLock<Node>>>,
}

struct LruCache {
    map: HashMap<String, Arc<RwLock<Node>>>,
    head: Option<Arc<RwLock<Node>>>,
    tail: Option<Arc<RwLock<Node>>>,
    capacity: usize,
}

impl LruCache {
    pub fn get(&mut self, key: &str) -> Option<String> {
        // Acquire a read lock to find the node
        let node_arc = self.map.get(key)?.clone();
        let node_read = node_arc.read().unwrap();
        let val = node_read.value.clone();

        // Now we need to move this node to the front (the "Most Recently Used" position)
        // This requires updating the pointers, so we need a write lock.
        let mut node_write = node_arc.write().unwrap(); 
        self.move_to_front(node_write); 

        Some(val)
    }
}

The RwLock Promotion Deadlock

At first glance, the code above looks efficient. You're using a read lock to get the value, which should allow other threads to read simultaneously. But there is a fatal flaw: lock promotion. In Rust (and most systems languages), you cannot "upgrade" a read lock to a write lock while still holding the read lock.

In the get method, the thread acquires node_read. While that lock is still held, it attempts to acquire node_write. The thread is now waiting for itself to release the read lock before it can acquire the write lock. It's a deadlock. Even if you wrap the entire LruCache in an RwLock, the logic remains the same: if you hold a read lock on the container and then try to acquire a write lock on the container to update the LRU order, you've just locked your program into a standstill.

Using a Mutex for Atomic State Updates

The hard truth about LRU caches is that every "read" is actually a "write." Because get modifies the internal order of the elements to track recency, the entire operation is a mutation. Trying to use RwLock to optimize reads is a premature optimization that leads to fragility.

The fix is to use a Mutex for the cache state. While it sounds slower, it's correct. By locking the cache for the duration of the get and put operations, we ensure that the map and the linked list stay in sync without risking deadlocks. If you truly need high concurrency, you'd look into "sharded caches" (splitting the cache into 16 smaller caches based on a hash of the key), but for a single cache instance, a Mutex is the right tool.

Here is the corrected approach for the synchronization logic:

use std::sync::{Arc, Mutex};
use std::collections::HashMap;

// We use a Mutex around the internal state to ensure 
// the map and the list are updated atomically.
pub struct ThreadSafeLruCache {
    inner: Arc<Mutex<LruInner>>,
}

struct LruInner {
    map: HashMap<String, Arc<Mutex<Node>>>,
    head: Option<Arc<Mutex<Node>>>,
    tail: Option<Arc<Mutex<Node>>>,
    capacity: usize,
}

impl ThreadSafeLruCache {
    pub fn get(&self, key: &str) -> Option<String> {
        let mut guard = self.inner.lock().unwrap();
        
        if let Some(node_arc) = guard.map.get(key).cloned() {
            // Now we can safely move it to the front because we hold the
            // lock on the entire inner state.
            guard.move_to_front(node_arc.clone());
            
            let node = node_arc.lock().unwrap();
            return Some(node.value.clone());
        }
        None
    }
}

Note how I separated ThreadSafeLruCache from LruInner. This is a common pattern I use to keep the locking logic separate from the data structure logic. The ThreadSafeLruCache handles the synchronization, while LruInner handles the pointer manipulation. It makes the code much easier to test and reason about.

📋 Practical Task

Exercise: Implementing a Thread-Safe LRU Cache with Eviction Logic

Your task is to complete the implementation of a thread-safe LRU cache. You are provided with the basic structure, but the core logic for eviction and pointer updates is missing.

Requirements:

• Implement the put method: If the key exists, update the value and move it to the front. If it doesn't exist, add it. If the cache exceeds capacity, remove the least recently used (tail) item from both the map and the linked list.
• Implement the move_to_front helper method: This should correctly rewire the prev and next pointers of the affected nodes to move the target node to the head of the list.
• Ensure the implementation is thread-safe using Arc and Mutex.
• The cache should handle a capacity of 0 or 1 without crashing.

use std::sync::{Arc, Mutex};
use std::collections::HashMap;

struct Node {
    key: String,
    value: String,
    prev: Option<Arc<Mutex<Node>>>,
    next: Option<Arc<Mutex<Node>>>,
}

struct LruInner {
    map: HashMap<String, Arc<Mutex<Node>>>,
    head: Option<Arc<Mutex<Node>>>,
    tail: Option<Arc<Mutex<Node>>>,
    capacity: usize,
}

impl LruInner {
    fn move_to_front(&mut self, node: Arc<Mutex<Node>>) {
        // TODO: Implement pointer logic to move node to head
    }

    fn evict(&mut self) {
        // TODO: Implement logic to remove tail node
    }
}

pub struct ThreadSafeLruCache {
    inner: Arc<Mutex<LruInner>>,
}

impl ThreadSafeLruCache {
    pub fn new(capacity: usize) -> Self {
        Self {
            inner: Arc::new(Mutex::new(LruInner {
                map: HashMap::new(),
                head: None,
                tail: None,
                capacity,
            })),
        }
    }

    pub fn put(&self, key: String, value: String) {
        let mut inner = self.inner.lock().unwrap();
        // TODO: Implement put logic with eviction
    }

    pub fn get(&self, key: &str) -> Option<String> {
        let mut inner = self.inner.lock().unwrap();
        if let Some(node_arc) = inner.map.get(key).cloned() {
            inner.move_to_front(node_arc.clone());
            return Some(node_arc.lock().unwrap().value.clone());
        }
        None
    }
}