Katkat
Back

Implement a thread-safe high-concurrency LRU cache

MongoDBSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to design a thread-safe LRU cache using a combination of a hash map and a doubly linked list, requiring efficient synchronization to handle concurrent access.

Problem Statement

Design and implement a thread-safe Least Recently Used (LRU) cache. The cache should support the following operations:

  • get(key): Returns the value of the key if it exists, otherwise returns -1. Accessing a key makes it the most recently used.
  • put(key, value): Inserts or updates the value if the key is not already present. When the cache reaches its capacity, it should invalidate the least recently used item before inserting a new item.

Your implementation must be thread-safe, supporting multiple concurrent readers and writers. Strive for high concurrency by minimizing lock contention.

Interface

class LRUCache:
    def __init__(self, capacity: int):
        pass

    def get(self, key: int) -> int:
        pass

    def put(self, key: int, value: int) -> None:
        pass

Examples

lru = LRUCache(2)
lru.put(1, 1)    # Cache: {1=1}
lru.put(2, 2)    # Cache: {1=1, 2=2}
lru.get(1)       # Returns 1, Cache: {2=2, 1=1}
lru.put(3, 3)    # Evicts 2, Cache: {1=1, 3=3}
lru.get(2)       # Returns -1

Constraints

  • capacity will be between 1 and 100,000.
  • Operations must run in O(1) average time complexity.
  • You must handle high levels of concurrency effectively.

Hints

Hint 1

A standard LRU cache uses a hash map for O(1) lookups and a doubly linked list to track access order.

Hint 2

Using a single global lock for all operations will create a bottleneck; consider using fine-grained locking or a concurrent map structure.

Hint 3

While complete lock-free implementation of a doubly linked list is complex, consider if there are ways to minimize the critical section duration or use `ReadWriteLocks` if the read-to-write ratio is high.

Follow-up questions

  • How would your implementation change if the cache needed to support expiration (TTL) for keys?
  • If the cache size were too large for a single machine, how would you distribute this cache across multiple nodes?
  • Explain the performance trade-offs between using a global mutex versus fine-grained locking in this specific data structure.