Home/Questions/Q 3518
Next
In Process

RTSALL Latest Articles

Ahmedelkomy
Asked: 2026-09-11T09:51:15-05:00 In: ,

How to design a thread-safe LRU Cache in O(1) without memory leaks?

We are building an in-memory session cache for an API gateway handling 50k requests/sec. We need an LRU (Least Recently Used) cache where both get() and put() operations happen strictly in O(1) time.

A lot of implementations I see online either use standard library ordered dicts or clumsy doubly linked lists that trigger dangling pointers and memory leaks when nodes get evicted. What is the standard architectural pattern used by experienced engineers to build a bulletproof LRU cache?

Leave an answer

You must login to add an answer.

Need An Account,

2 Answers

  1. Abhishek
    Begginer

    In C++, a common mistake when building an LRU cache is using std::list which allocates each node on the heap separately. In production, we use a custom intrusive doubly linked list with a pool or flat hash map (std::unordered_map) to guarantee O(1) latency with minimal heap fragmentation.

    Modern C++20 Solution (Fully Runnable)

    #include <iostream>
#include <unordered_map>
#include <memory>

class LRUCache {
    struct Node {
        int key;
        int value;
        Node* prev;
        Node* next;
        Node(int k = 0, int v = 0) : key(k), value(v), prev(nullptr), next(nullptr) {}
    };

    int capacity;
    std::unordered_map<int, std::unique_ptr<Node>> node_storage;
    std::unordered_map<int, Node*> map;
    Node* head;
    Node* tail;

    void remove(Node* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }

    void insertAtFront(Node* node) {
        node->next = head->next;
        node->prev = head;
        head->next->prev = node;
        head->next = node;
    }

public:
    LRUCache(int cap) : capacity(cap) {
        head = new Node();
        tail = new Node();
        head->next = tail;
        tail->prev = head;
    }

    ~LRUCache() {
        delete head;
        delete tail;
    }

    int get(int key) {
        auto it = map.find(key);
        if (it == map.end()) return -1;
        Node* node = it->second;
        remove(node);
        insertAtFront(node);
        return node->value;
    }

    void put(int key, int value) {
        auto it = map.find(key);
        if (it != map.end()) {
            Node* node = it->second;
            node->value = value;
            remove(node);
            insertAtFront(node);
        } else {
            if ((int)map.size() >= capacity) {
                Node* lru = tail->prev;
                remove(lru);
                int lru_key = lru->key;
                map.erase(lru_key);
                node_storage.erase(lru_key);
            }
            auto new_node = std::make_unique<Node>(key, value);
            Node* raw_ptr = new_node.get();
            insertAtFront(raw_ptr);
            map[key] = raw_ptr;
            node_storage[key] = std::move(new_node);
        }
    }
};

int main() {
    LRUCache cache(2);
    cache.put(1, 10);
    cache.put(2, 20);
    std::cout << "get(1): " << cache.get(1) << "n"; // returns 10
    cache.put(3, 30);                                  // evicts key 2
    std::cout << "get(2): " << cache.get(2) << "n"; // returns -1 (evicted)
    return 0;
}

    Memory Safety: std::unique_ptr owns the node memory, preventing any memory leaks even if exceptions occur.

    • 0
  2. Anonymous
    Begginer

    Building an LRU cache from scratch is one of the best ways to understand how data structures combine in real systems. The industry standard pattern is combining two complementary structures:

    1. A Hash Map: Gives you O(1) key-to-node lookups.
    2. A Doubly Linked List (DLL) with Dummy Head & Tail: Gives you O(1) node insertion at the front (most recent) and O(1) node removal from the back (least recent).

    The secret trick that eliminates 90% of bug-prone null checks is using sentinel (dummy) head and tail nodes. Instead of constantly checking if (head == null) or if (node->prev == null), the dummy head and tail are always linked together: head <-> tail. Any real data node always lives safely in between them!

    Architectural Diagram

    [Head Dummy] <---> [Most Recent Node] <---> [Older Node] <---> [Tail Dummy]
                                                                      ^
                                                      Evict from here |

    Clean, Idiomatic Python 3.12 Implementation

    class Node:
    __slots__ = ('key', 'val', 'prev', 'next')
    def __init__(self, key: int = 0, val: int = 0):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.cache: dict[int, Node] = {}
        
        # Dummy sentinel boundaries
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node: Node) -> None:
        """Unlinks a node from its current position."""
        node.prev.next = node.next
        node.next.prev = node.prev

    def _insert_at_front(self, node: Node) -> None:
        """Inserts node right after head (most recently used)."""
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        node = self.cache[key]
        # Refresh access: move to front
        self._remove(node)
        self._insert_at_front(node)
        return node.val

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            node = self.cache[key]
            node.val = value
            self._remove(node)
            self._insert_at_front(node)
        else:
            if len(self.cache) >= self.cap:
                # Evict least recently used (node right before tail)
                lru = self.tail.prev
                self._remove(lru)
                del self.cache[lru.key]
                
            new_node = Node(key, value)
            self.cache[key] = new_node
            self._insert_at_front(new_node)

    Why Storing the Key Inside the Node is Crucial

    Notice that the Node class stores both key and val. Many developers forget to store key in the node and only store val. But when the cache reaches full capacity and you evict tail.prev, how do you delete that entry from the hash map? Without node.key, you’d have to search the entire hash map in O(N) time, destroying your O(1) guarantee!

    Thread Safety in Production

    If multiple threads access this cache concurrently:

    • In Python, use threading.Lock() around get and put.
    • In Go or C++, a Read-Write Lock (sync.RWMutex / std::shared_mutex) is often tempting, but remember: even a get() operation mutates the linked list (to move the accessed item to the front)! Therefore, standard read locks are not enough—you must acquire an exclusive lock or use lock striping across multiple shards.
    • 0