Design and Implement a Thread-Safe LRU Cache

Question

The question asks the candidate to design and implement a thread-safe Least Recently Used (LRU) cache, focusing on handling edge cases and ensuring thread safety.

Codemia · Accepted Answer

To design a thread-safe LRU cache, we need to ensure that it can efficiently store key-value pairs while maintaining the order of usage. It must support operations like inserting, retrieving, and evicting items, all while being safe for concurrent access.

We will use a combination of a hash map and a doubly linked list. The hash map will allow for O(1) access to cache items, while the doubly linked list will maintain the order of usage. The most recently used items will be at the front, and the least recently used will be at the back. To ensure thread safety, we can use a mutex or a read-write lock.

1. **Data Structures**: The hash map will store the key and a pointer to the corresponding node in the doubly linked list. The list will hold the keys in the order of usage. 
2. **Operations**: 
   - **Get(key)**: Check if the key exists in the hash map. If it does, move the corresponding node to the front of the list and return the value. If not, return -1. 
   - **Put(key, value)**: If the key exists, update the value and move the node to the front. If it does not exist, add a new node. If the cache exceeds its size, remove the node from the back of the list.

Using a mutex for every operation can lead to contention, especially with high concurrency. A read-write lock can improve performance by allowing multiple reads while still ensuring exclusive access for writes. Additionally, we should consider the cache size and eviction strategy to ensure that the cache remains efficient under load.

Here is a simple implementation of a thread-safe LRU cache in Python:

```python
import threading

class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}
        self.head = Node(0, 0)
        self.tail = Node(0, 0)
        self.head.next = self.tail
        self.tail.prev = self.head
        self.lock = threading.Lock()

def _remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

def _add(self, node):
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

def get(self, key: int) -> int:
        with self.lock:
            if key in self.cache:
                node = self.cache[key]
                self._remove(node)
                self._add(node)
                return node.value
            return -1

def put(self, key: int, value: int) -> None:
        with self.lock:
            if key in self.cache:
                self._remove(self.cache[key])
            node = Node(key, value)
            self.cache[key] = node
            self._add(node)
            if len(self.cache) > self.capacity:
                lru = self.tail.prev
                self._remove(lru)
                del self.cache[lru.key]
```
This implementation ensures thread safety using a lock around the critical sections.

Design and Implement a Thread-Safe LRU Cache

Snapchat

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Requirements

High-Level Design

Submit Your Answer

Snapchat Software Engineer Interview Guide

Related Questions

Design a scalable Search System

Design a Video Streaming for Rippling

Design a Load Balancing Service

Design a Image Processing Service

Build a high-throughput Image Processing Pipeline