Design a thread-safe LFU cache

01The design, in the six-step framework

1. Requirements and use cases

This is the usual follow-up to the LRU cache, and at Google it comes with a second twist: make it safe for many threads, and do not answer "put synchronized on every method". One reported interviewer pushed back on exactly that.

• A caller gets a value by key in O(1) and the key's use count rises by one.
• A caller puts a key and value in O(1); a new key starts with a count of one, an existing key keeps its count plus one.
• When full, the cache evicts the key with the smallest use count; among ties, the least recently used of them.
• Many threads call get and put concurrently and never see a torn entry, a double eviction or a lost update.
• A caller can read size and capacity.

Out of scope: TTL expiry, persistence, and distribution across machines. Non-functional constraints: O(1) for both operations without a heap; memory proportional to capacity; and under contention, readers of different keys should not serialise behind one global lock more than necessary, which is the real content of the thread-safety follow-up.

2. Core entities and relationships

• LFUCache: the public object; owns the key index, the frequency buckets and the minimum frequency; enforces eviction.
• Node: one entry with key, value, frequency and neighbour links.
• FrequencyBucket: a doubly linked list of all nodes with the same frequency, ordered by recency so ties break LRU.
• Lock: a single mutex guarding the whole structure in the first version; a striped set of locks in the scaled version.

The cache composes the buckets (a dictionary from frequency to bucket) and the index (key to node). A node lives in exactly one bucket at a time; moving it is an unlink from one list and a push to the front of another. The invariant that makes O(1) eviction possible is a field min_freq: the smallest frequency with a non-empty bucket. See hash map plus linked list for why each bucket is a list and not a set.

3. Interfaces and key methods

from typing import Generic, Hashable, Optional, TypeVar

K = TypeVar("K", bound=Hashable)
V = TypeVar("V")


class LFUCache(Generic[K, V]):
    def __init__(self, capacity: int) -> None:
        """capacity >= 1. Internally creates the lock, the index and an empty bucket map."""

    def get(self, key: K) -> Optional[V]:
        """Return the value and increment the key's frequency; None on a miss. Thread-safe."""

    def put(self, key: K, value: V) -> None:
        """Insert or replace; new keys start at frequency 1; evicts min-frequency LRU when full."""

    def __len__(self) -> int:
        """Current number of entries."""

Invariants: every node in the index is in exactly the bucket named by its freq; min_freq is the smallest key of a non-empty bucket whenever the cache is non-empty; empty buckets are deleted so min_freq never points at nothing; and all of this is only ever observed by a thread that holds the lock. The last invariant is the whole point of the concurrency design in section 4.

4. Design patterns and the choices behind them

Buckets of lists, not a heap

The force is "smallest frequency, ties by recency" in O(1). A min-heap keyed by (frequency, last use) gives O(log n) and needs a position index to update arbitrary entries. Buckets indexed by frequency give O(1): the frequency only ever moves from f to f + 1, so a node moves to a neighbouring bucket, and the minimum only changes in two predictable ways. When a brand-new key is inserted, min_freq becomes 1. When the only node in the min_freq bucket is promoted, min_freq increases by one. Those two rules keep the field exact without a scan.

One lock first, then stripes, never none

The force is correctness under threads. A get mutates three things (node frequency, two buckets, possibly min_freq), so there is no read-only path and a read-write lock buys nothing. One mutex around each public method is correct, and it is the version to write first. The interviewer's objection to "just synchronise" is about throughput: every thread serialises on one lock even when touching unrelated keys. The scaled answer is striping: shard the cache into S independent LFU caches by key hash, each with its own lock and its own capacity of capacity / S. Eviction becomes approximately LFU across the whole, exactly LFU within a shard, and you must say that trade-off out loud. The rejected alternative, fine-grained locks per bucket inside one cache, invites deadlock because a promotion touches two buckets and min_freq at once; it needs lock ordering and still contends on the index.

Thread-safe collections are not enough

Even if the index were a concurrent map, the operation "look up, then move between buckets, then maybe evict" spans several steps and must be atomic as a whole. Thread-safe collections protect single operations, not sequences; that sentence is the one the interviewer is listening for.

5. Core flow and code

Flow for get("a") when a has frequency 2 and is the only node in bucket 2, with min_freq = 2:

1. Acquire the lock. Look up a in the index; found.
2. Unlink the node from bucket 2. Bucket 2 is now empty, so delete it; since min_freq was 2, set it to 3.
3. Set the node's frequency to 3, push it to the front of bucket 3 (creating the bucket if needed).
4. Release the lock and return the value.

import threading
from dataclasses import dataclass
from typing import Dict, Generic, Hashable, Optional, TypeVar

K = TypeVar("K", bound=Hashable)
V = TypeVar("V")


@dataclass(eq=False)
class Node(Generic[K, V]):
    key: Optional[K]
    value: Optional[V]
    freq: int = 0
    prev: "Optional[Node[K, V]]" = None
    next: "Optional[Node[K, V]]" = None


class FrequencyBucket(Generic[K, V]):
    def __init__(self, freq: int) -> None:
        self.freq = freq
        self.head: Node[K, V] = Node(None, None)
        self.tail: Node[K, V] = Node(None, None)
        self.head.next, self.tail.prev = self.tail, self.head

    def push_front(self, node: Node[K, V]) -> None:
        first = self.head.next
        node.prev, node.next = self.head, first
        self.head.next = node
        first.prev = node  # type: ignore[union-attr]

    def unlink(self, node: Node[K, V]) -> None:
        node.prev.next, node.next.prev = node.next, node.prev  # type: ignore[union-attr]
        node.prev = node.next = None

    def pop_back(self) -> Node[K, V]:
        last = self.tail.prev
        self.unlink(last)  # type: ignore[arg-type]
        return last  # type: ignore[return-value]

    def empty(self) -> bool:
        return self.head.next is self.tail


class LFUCache(Generic[K, V]):
    def __init__(self, capacity: int) -> None:
        if capacity < 1:
            raise ValueError("capacity must be at least 1")
        self.capacity = capacity
        self.index: Dict[K, Node[K, V]] = {}
        self.buckets: Dict[int, FrequencyBucket[K, V]] = {}
        self.min_freq = 0
        self.lock = threading.RLock()

    def get(self, key: K) -> Optional[V]:
        with self.lock:
            node = self.index.get(key)
            if node is None:
                return None
            self._promote(node)
            return node.value

    def put(self, key: K, value: V) -> None:
        with self.lock:
            node = self.index.get(key)
            if node is not None:
                node.value = value
                self._promote(node)
                return
            if len(self.index) >= self.capacity:
                victim = self.buckets[self.min_freq].pop_back()
                self._drop_if_empty(self.min_freq)
                del self.index[victim.key]  # type: ignore[arg-type]
            node = Node(key, value, freq=1)
            self.index[key] = node
            self._bucket(1).push_front(node)
            self.min_freq = 1

    def _promote(self, node: Node[K, V]) -> None:
        old = node.freq
        self.buckets[old].unlink(node)
        if self._drop_if_empty(old) and self.min_freq == old:
            self.min_freq = old + 1
        node.freq = old + 1
        self._bucket(node.freq).push_front(node)

    def _bucket(self, freq: int) -> FrequencyBucket[K, V]:
        if freq not in self.buckets:
            self.buckets[freq] = FrequencyBucket(freq)
        return self.buckets[freq]

    def _drop_if_empty(self, freq: int) -> bool:
        if self.buckets[freq].empty():
            del self.buckets[freq]
            return True
        return False

    def __len__(self) -> int:
        with self.lock:
            return len(self.index)


class StripedLFUCache(Generic[K, V]):
    """Throughput version: S independent LFU caches, one lock each; LFU is exact per stripe."""

    def __init__(self, capacity: int, stripes: int = 16) -> None:
        per = max(1, capacity // stripes)
        self.stripes = [LFUCache[K, V](per) for _ in range(stripes)]

    def _pick(self, key: K) -> LFUCache[K, V]:
        return self.stripes[hash(key) % len(self.stripes)]

    def get(self, key: K) -> Optional[V]:
        return self._pick(key).get(key)

    def put(self, key: K, value: V) -> None:
        self._pick(key).put(key, value)

6. Extensions, concurrency and what interviewers probe

• Evict before insert, not after. With LFU, inserting first would make the new node (frequency 1) the eviction victim. The code evicts first, then inserts; this is the opposite order from the LRU solution and a classic slip.
• Why an RLock. A re-entrant lock lets __len__ or a future stats() be called from inside another locked method without deadlocking on itself. Say that a plain Lock would also be correct for the two public methods as written.
• Striping changes the semantics. With 16 stripes a globally rare key can survive while a globally common key in a crowded stripe is evicted. If the interviewer wants exact LFU under high concurrency, the honest answer is that you pay with one lock or move to a lock-free design that is out of scope for an hour.
• TTL on top. Add an expiry timestamp per node and treat an expired node as a miss on read, cleaning it lazily; the cache manager problem shows the injected clock that keeps this testable.
• What to test first. Tie-breaking: two keys at frequency 1, touch one, insert a third, the untouched one must go. Then the min_freq reset to 1 after any insert.
• Common mistake. Leaving empty buckets in the map so min_freq points at an empty list, then pop_back returns a sentinel. The _drop_if_empty helper exists for that reason alone.

02Where this question was reported

• DesignGurus · DesignGurus case study 'In-Memory Cache'
• LLD Mastery · Google-tagged (Hard); LRU/LFU eviction, TTL expiry
• LLD Mastery · Google-tagged with Amazon/Microsoft/Meta/Salesforce
• DesignGurus · DesignGurus blog common LLD question
• PracHub · PracHub OOD practice prompt 'Cache'
• LeetCode Discuss · LeetCode 460 (Hard), Google-tagged, freq 36.5; typical follow-up to LRU per Prepfully
• LeetCode Discuss · Thread-safe LFU; follow-up on concurrency; interviewer pushed back on relying only on `synchronized`
• LeetCode Discuss · Round 'felt like implementing an LRU/LFU-style system'; edge cases were the hard part
• Taro · Taro tags Google; edge case: get immediately followed by put must evict the now-least-recent key
• Prepfully · Listed among recently reported Google coding questions: O(1) insert/delete/retrieve LRU
• ReturnZero · Phased: get/put -> eviction -> O(1) -> recency queries + TTL expiry (Google tag hidden behind '+7')
• PracHub · Data-structure design problem 'similar to an LRU variant' in coding round