Building a Thread-Safe LRU Cache

Hello! Welcome back to our module on implementing core data structures.

In the last lesson, we built a robust DoublyLinkedList using sentinel nodes, noting its O(1) efficiency for reordering operations. We concluded that this structure, combined with the hash map we previously developed, gives us all the tools needed for a high-performance cache.

Today, we'll put those pieces together to achieve a significant milestone: Implement a thread-safe, production-quality LRU Cache from scratch using a hash map and a doubly linked list.

This is a classic interview problem that tests your ability to combine data structures and reason about concurrency. Given your background building high-throughput services like Rudi at AWS, this lesson will directly translate the concurrency challenges you've solved in Rust—like managing shared state across tasks—to a Python context. We'll focus on not just making it work, but making it robust and discussing the trade-offs involved in a production environment.

1. The Core Architecture: Hash Map + Doubly Linked List

An LRU (Least Recently Used) cache needs to do two things very fast:

1. Look up an item by its key.
2. Track and update the recency of items, evicting the oldest one when capacity is full.

A hash map gives us O(1) average time for lookups, but it doesn't maintain insertion or access order. A linked list maintains order, but lookups are O(N). The solution is to use them together.

• A Hash Map will store the key and a direct reference (pointer) to the node in the linked list. This gives us O(1) access to any node.
• A Doubly Linked List will store the nodes themselves, ordered by recency. We'll use the head of the list for the most recently used item and the tail for the least recently used. The DLL allows us to move any node to the head in O(1) time.

This combination is the key to achieving O(1) performance for both get and put operations.

To see a detailed walkthrough of this logic, the following video explains the mechanics of get, put, and eviction.

2. Single-Threaded Implementation

Let's translate this into Python code. We will use the DoublyLinkedList class we built in the previous lesson.

Here is the implementation of the LRU cache itself:

# Assuming the Node and DoublyLinkedList classes from the previous lesson are available.
# A quick reminder of their structure:
#
# class Node:
#     def __init__(self, key=None, value=None): ...
#
# class DoublyLinkedList:
#     def __init__(self): ...
#     def remove(self, node: Node): ...
#     def prepend(self, node: Node): ...
#     def move_to_head(self, node: Node): ...
#     def pop_tail(self) -> Optional[Node]: ...

class LRUCache:
    """
    A single-threaded LRU Cache implementation using a hash map and a doubly linked list.
    """
    def __init__(self, capacity: int):
        if capacity <= 0:
            raise ValueError("Capacity must be a positive integer.")
        self.capacity = capacity
        self.cache = {}  # The hash map: maps key -> Node
        self.dll = DoublyLinkedList()  # The DLL to track recency

    def get(self, key) -> int:
        """
        Retrieves an item from the cache and marks it as recently used.
        Returns -1 if the key is not found.
        """
        if key not in self.cache:
            return -1

        node = self.cache[key]



        # Move the accessed node to the front (most recently used).
        self.dll.move_to_head(node)
        return node.value

    def put(self, key, value: int) -> None:
        """
        Adds or updates an item in the cache. Evicts the least recently used
        item if the cache is at capacity.
        """
        if key in self.cache:



            # Key already exists, update the value and mark as recently used.
            node = self.cache[key]
            node.value = value
            self.dll.move_to_head(node)
        else:



            # Key does not exist, add a new node.
            if len(self.cache) >= self.capacity:



                # Evict the least recently used item.
                lru_node = self.dll.pop_tail()
                if lru_node:
                    del self.cache[lru_node.key]

            new_node = Node(key, value)
            self.cache[key] = new_node
            self.dll.prepend(new_node) # Add to front (most recently used).

This implementation correctly fulfills the LRU logic. However, in a real system like the ones you build at AWS, services handle concurrent requests. If multiple threads call get and put simultaneously, this code will fail.

3. Making the Cache Thread-Safe

The problem is that both get() and put() can modify the shared state: the self.cache dictionary and, more importantly, the self.dll doubly linked list. A get operation modifies the list by moving a node. A put operation can add, move, or remove nodes. Concurrent modifications can corrupt the list's pointers, leading to an inconsistent state or infinite loops.

This is the same fundamental problem as managing shared resources in any concurrent system. In Rust, you would use a Mutex or RwLock to protect the shared data. In Python, we do the same using the threading module.

The most straightforward approach is to use a single, coarse-grained lock that protects all access to the cache.

To understand this approach, please read the following section from an article on implementing LRU caches.

As the article explains, we can add a lock to our LRUCache class and ensure every method acquires it before modifying the shared state.

Here is the thread-safe version of our LRUCache:

import threading




# Assume Node and DoublyLinkedList classes are defined as before

class ThreadSafeLRUCache:
    """
    A production-quality, thread-safe LRU Cache.
    """
    def __init__(self, capacity: int):
        if capacity <= 0:
            raise ValueError("Capacity must be a positive integer.")
        self.capacity = capacity
        self.cache = {}
        self.dll = DoublyLinkedList()



        # A single lock to protect all shared state (cache and dll).
        self.lock = threading.Lock()

    def get(self, key) -> int:
        """
        Thread-safe retrieval of an item.
        """
        with self.lock:
            if key not in self.cache:
                return -1

            node = self.cache[key]
            self.dll.move_to_head(node)
            return node.value

    def put(self, key, value: int) -> None:
        """
        Thread-safe addition or update of an item.
        """
        with self.lock:
            if key in self.cache:
                node = self.cache[key]
                node.value = value
                self.dll.move_to_head(node)
            else:
                if len(self.cache) >= self.capacity:
                    lru_node = self.dll.pop_tail()
                    if lru_node:
                        del self.cache[lru_node.key]

                new_node = Node(key, value)
                self.cache[key] = new_node
                self.dll.prepend(new_node)

The with self.lock: statement ensures that the lock is acquired before the block is entered and released when it's exited, even if errors occur. This makes our cache safe for use in a multi-threaded environment.

4. Trade-offs and Production Considerations

For an interview at a company like Anthropic, simply providing the thread-safe code is good, but discussing the trade-offs is what demonstrates senior engineering thinking.

Coarse-Grained Locking (Our current approach)

• Pros: It's simple to implement and reason about. It completely prevents race conditions.
• Cons: It introduces a performance bottleneck. Only one thread can be in any part of the cache (get or put) at a time. If you have many threads trying to read from the cache, they will be serialized, waiting on each other, even though reads could theoretically happen in parallel.

Finer-Grained Locking
A more advanced solution would be to use a read-write lock. In Python, there is no standard library implementation, but the concept is crucial and directly maps to Rust's RwLock.

• How it works: It allows multiple "reader" threads to acquire the lock simultaneously, but a "writer" thread must wait for all readers to finish and then acquires an exclusive lock.
• Application to our cache:
  • The get method is mostly a "read" operation, though it does modify the DLL. So, a simple read-write lock isn't a perfect fit unless the read and write portions of the operation are separated.
  • A more complex get could first acquire a read lock to check for the key, and if found, "upgrade" to a write lock to perform the move_to_head operation. Lock upgrading can be tricky and lead to deadlocks if not handled carefully.
• The Interview Takeaway: You should mention the performance limitations of a single global lock and propose a read-write lock as a more performant alternative for read-heavy workloads, while acknowledging the added complexity. This shows you're thinking about performance under load, a key concern in systems like Bedrock. For most interviews, the threading.Lock implementation is a sufficient and correct "production-quality" answer.

Conclusion

In this lesson, we successfully built a thread-safe, production-quality LRU cache from scratch. We combined a hash map for fast lookups with the doubly linked list from our previous lesson for efficient recency tracking.

Key Takeaways:

• An LRU Cache's O(1) performance comes from the synergy between a hash map (for O(1) lookups) and a doubly linked list (for O(1) reordering).
• In a concurrent environment, shared data structures like this must be protected by locks to prevent race conditions and data corruption.
• A single, coarse-grained lock is the simplest way to ensure thread safety, but it's important to discuss its performance trade-offs and mention more advanced patterns like read-write locks for read-heavy workloads.

Next Lesson Preview

We have now built the complete data structure and made it robust. The foundation of this design rests on its O(1) time complexity. In our next lesson, we will formalize this by focusing on the following learning outcome: Justify the O(1) time complexity of the get and put operations in the from-scratch LRU Cache. We will break down each step of our methods to prove why this design is so efficient.