Design an in-memory cache (LRU, LFU, TTL)¶
TL;DR¶
- You build a bounded
Cachewhose reads and writes are O(1): a dict holds the values, a pluggableEvictionPolicyholds the order. - Three decisions carry the interview: the dict and the ordering structure must move under one lock, LFU needs frequency buckets plus a minimum pointer or eviction degrades to a scan, and TTL is checked lazily on read with a sweeper only for memory.
- Patterns that earn their place: Strategy (the policy), Template Method (LRU and FIFO differ by one method), Decorator (
LoadingCache), Dependency Injection (Clock).
Problem statement¶
"Design an in-memory cache with a fixed capacity. get and put must both be O(1). When the cache is full, an eviction policy decides which key leaves — support least-recently-used and least-frequently-used, and make the policy swappable. Keys may carry a time-to-live. The cache is shared by many threads, and it should report hit and miss statistics. Show me the data structures, then show me what happens when two threads write at the same time."
Requirements¶
Functional
- O(1)
getandput, including the eviction that aputmay trigger. - A fixed capacity; a
putpast the capacity evicts exactly one key. - LRU built from a dict plus a doubly linked list; LFU built from frequency buckets, also O(1); FIFO for contrast.
- The policy is pluggable: the cache never asks which one it holds.
- Per-key TTL with lazy expiry on read, plus an optional background sweeper.
- Thread-safe: concurrent readers and writers cannot corrupt either structure.
- Hit, miss, eviction and expiry counters, and the hit ratio derived from them.
- An optional read-through loader (cache-aside behind one call) with a stampede guard.
Non-functional and constraints
- In-process and in-memory. Distribution is a different problem, and the page hands it off to the HLD case study.
- Deterministic and testable: time is injected, so a TTL test never sleeps.
- No unbounded growth: every structure a key touches must release it on eviction or expiry.
Out of scope: persistence, serialisation, size-aware eviction by bytes, and cross-process invalidation.
Clarifying questions and assumptions¶
| Question to ask | Assumption taken here |
|---|---|
| Is capacity counted in entries or in bytes? | Entries. Byte-aware eviction is an extensibility item, and it changes _evict_one into a loop. |
Does a put on an existing key count as a use? |
Yes — a rewrite is a use, so it moves to the front under LRU and bumps the frequency under LFU. |
What does get return for a missing key? |
A default (None). try_get returns the Entry, so a caller can tell "absent" from "stored None". |
| Is TTL absolute or a sliding window? | Absolute: the deadline is fixed at write time. Sliding TTL is one line in try_get, and you should say which one. |
| Must expired keys disappear immediately? | No. Lazy expiry is correct on its own; the sweeper exists to release memory nobody reads again. |
| One lock or many? | One reentrant lock per cache, plus an optional ShardedCache when profiling says the lock is the bottleneck. |
| Do we need the values to be strongly typed? | Cache[K, V] is generic, keys are Hashable. Policies work in terms of keys only. |
Core entities and relationships¶
Cache[K, V]— the aggregate: the entry dict, the policy, the injectedClock, the lock and the counters. Everything public goes through it.Entry[V]— a frozen value object: the value plusexpires_at, an absolute instant rather than a remaining duration, so nothing has to be decremented as time passes.EvictionPolicy— aProtocolwith five verbs:on_insert,on_access,on_remove,evict,keys. It owns order and never sees a value.NodeandDoublyLinkedList— the intrusive list both list-based policies share. The list stores no wrappers: the policy already holds the node for a key, so "move this key to the front" is four pointer writes.RecencyPolicy(abstract) withLRUPolicyandFIFOPolicy— one index, one list, one hook.LFUPolicy—dict[int, DoublyLinkedList]keyed by use count, plus_min_freq.LoadingCache[K, V]— wraps aCacheand adds read-through loading with a single-flight guard.ShardedCache[K, V]— many independent caches chosen byhash(key), for when one lock is measurably hot.TtlSweeper— a daemon thread that callspurge_expiredon an interval and stops on anEvent.CacheStats— an immutable snapshot; the cache never hands out live counters.
Multiplicities: cache 1 → 1 policy, cache 1 → * entries, RecencyPolicy 1 → 1 list, LFUPolicy 1 → * lists, ShardedCache 1 → * caches.
Class diagram¶
Structure: a dict for the values, a policy for the order, and three ways to be that policy.
classDiagram
class Cache {
+capacity: int
-_entries: Dict~K,Entry~
-_lock: RLock
-_clock: Clock
+try_get(key) Entry
+get(key, default) V
+put(key, value, ttl)
+delete(key) bool
+purge_expired() int
+stats() CacheStats
}
class Entry {
+value: V
+expires_at: float
+is_expired(now) bool
}
class CacheStats {
+hits: int
+misses: int
+evictions: int
+hit_ratio: float
}
class EvictionPolicy {
<<interface>>
+on_insert(key)
+on_access(key)
+on_remove(key)
+evict() Hashable
+keys() List~Hashable~
}
class RecencyPolicy {
<<abstract>>
-_nodes: Dict~Hashable,Node~
-_order: DoublyLinkedList
}
class LRUPolicy {
+on_access(key)
}
class FIFOPolicy {
+on_access(key)
}
class LFUPolicy {
-_buckets: Dict~int,DoublyLinkedList~
-_min_freq: int
+on_access(key)
+evict() Hashable
}
class DoublyLinkedList {
+push_front(node)
+unlink(node)
+move_to_front(node)
+pop_back() Node
}
class Node {
+key: Hashable
+freq: int
+prev: Node
+next: Node
}
class LoadingCache {
-_stripes: List~Lock~
+get(key) V
+invalidate(key) bool
}
class ShardedCache {
+shard_for(key) Cache
}
class TtlSweeper {
+start()
+stop(timeout)
}
Cache --> EvictionPolicy
Cache "1" *-- "many" Entry
Cache ..> CacheStats : snapshots
EvictionPolicy <|.. RecencyPolicy
EvictionPolicy <|.. LFUPolicy
RecencyPolicy <|-- LRUPolicy
RecencyPolicy <|-- FIFOPolicy
RecencyPolicy *-- DoublyLinkedList
LFUPolicy *-- "many" DoublyLinkedList
DoublyLinkedList o-- "many" Node
LoadingCache o-- Cache
ShardedCache o-- "many" Cache
TtlSweeper --> CacheDesign patterns applied¶
| Pattern | Where | Why it earns its place |
|---|---|---|
| Strategy | EvictionPolicy with LRUPolicy, LFUPolicy, FIFOPolicy |
Eviction is the rule the interviewer changes ("now make it LFU", "now add ARC"). Each is a new class and a registry entry; Cache is untouched. |
| Template Method | RecencyPolicy → LRUPolicy / FIFOPolicy |
Insert, remove, evict and listing are identical; the algorithms differ only in what a read does. One abstract method makes that difference literally one line long. |
| Decorator | LoadingCache wrapping Cache |
Read-through and stampede protection are a separate concern layered on top. A caller that does not want a loader pays nothing for it. |
| Dependency Injection | Clock |
TTL is testable without sleeping: FakeClock.advance(301) expires a five-minute key instantly. |
| Factory | make_policy("lfu") |
Configuration arrives as a string; the registry dict maps it to a class. |
| Composite-by-hash | ShardedCache holding many Cache objects |
Same public surface, many locks. You add it when profiling says so, not before. |
What was deliberately not used: a BaseCache template with abstract hooks. The temptation is to make Cache abstract and have LruCache and LfuCache subclass it. That puts the varying part (the order) in the inheritance axis and the fixed part (dict, lock, TTL, stats) in the subclasses' way — composition through a policy object is strictly better, and you can say why in one sentence. Observer for eviction notifications is also skipped: nothing in this problem listens, and a listener called under the cache lock is a deadlock waiting to happen.
Key flows¶
Write then read: the policy is told about every change, and expiry is settled on the read path.
sequenceDiagram
autonumber
actor App as Caller
participant C as Cache
participant P as EvictionPolicy
participant K as Clock
App->>C: put(k, v, ttl)
C->>K: now()
K-->>C: now, so expires_at = now + ttl
alt key already stored
C->>C: replace the Entry
C->>P: on_access(k)
else new key
opt cache is full
C->>P: evict()
P-->>C: victim key
C->>C: delete the victim entry
end
C->>P: on_insert(k)
end
App->>C: get(k)
C->>K: now()
alt entry is past its deadline
C->>P: on_remove(k)
C-->>App: default value, miss counted
else entry is live
C->>P: on_access(k)
C-->>App: value, hit counted
endThe stampede: sixteen threads miss the same key, one query leaves the process.
sequenceDiagram
autonumber
participant T1 as Thread1
participant T2 as Thread2
participant L as LoadingCache
participant C as Cache
participant DB as Database
T1->>L: get(k)
L->>C: try_get(k)
C-->>L: miss
T2->>L: get(k)
L->>C: try_get(k)
C-->>L: miss
L->>L: thread 1 takes the stripe for hash(k)
Note over T2,L: thread 2 blocks on that same stripe
L->>DB: loader(k)
DB-->>L: row
L->>C: put(k, row)
L-->>T1: row
L->>C: try_get(k), thread 2 re-checks
C-->>L: hit
L-->>T2: row, counted as coalescedImplementation¶
Write it in the order you would at the whiteboard: the vocabulary, then the list everything else stands on, then the policies, then the cache and its lock.
The errors subclass the shared hierarchy, so a caller catches ValidationError without importing anything cache-specific, and the policy names are an enum because they arrive from configuration as strings:
class CapacityError(ValidationError):
"""Capacity is not a positive integer, so the cache could never hold anything."""
class KeyMissingError(NotFoundError):
"""Strict lookup (``cache[key]``) for a key that is absent or already expired."""
class EmptyCacheError(InvalidStateError):
"""A policy was asked for a victim while it was tracking no keys at all."""
class EvictionPolicyName(StrEnum):
LRU = "lru"
LFU = "lfu"
FIFO = "fifo"
Entry stores an absolute deadline rather than a duration — the difference between a TTL you can check in one comparison and one you would have to sweep to maintain. CacheStats is frozen because handing out live counters is how a "read-only" accessor becomes a data race.
@dataclass(frozen=True, slots=True)
class Entry[V]:
"""One stored value plus its deadline. Frozen: a rewrite replaces the entry.
``expires_at`` is an absolute instant read from the injected ``Clock``, not a
remaining duration, so nothing has to be decremented as time passes.
"""
value: V
expires_at: float | None = None
def is_expired(self, now: float) -> bool:
return self.expires_at is not None and now >= self.expires_at
def ttl_remaining(self, now: float) -> float | None:
return None if self.expires_at is None else max(0.0, self.expires_at - now)
@dataclass(frozen=True, slots=True)
class CacheStats:
"""An immutable snapshot of the counters; the cache never hands out live state."""
hits: int = 0
misses: int = 0
evictions: int = 0
expirations: int = 0
loads: int = 0
coalesced: int = 0
size: int = 0
capacity: int = 0
@property
def lookups(self) -> int:
return self.hits + self.misses
@property
def hit_ratio(self) -> float:
return self.hits / self.lookups if self.lookups else 0.0
def __str__(self) -> str:
return (
f"size={self.size}/{self.capacity} hits={self.hits} misses={self.misses} "
f"evictions={self.evictions} expirations={self.expirations} "
f"hit_ratio={self.hit_ratio:.2f}"
)
Now the structure the whole problem rests on. Write the sentinels first and the rest follows: with a permanent head and tail there is no "is this the only node?" case to get wrong under pressure.
@dataclass(slots=True)
class Node:
"""A key inside an intrusive doubly linked list.
Intrusive means the list stores no wrapper objects: the policy keeps
``dict[key, Node]`` and every operation is pointer surgery on the node it
already has, which is what turns "move this key to the front" into O(1).
``freq`` is used by ``LFUPolicy`` only; one node type serves both policies.
"""
key: Hashable
freq: int = 1
prev: Node | None = None
next: Node | None = None
class DoublyLinkedList:
"""Insertion order with O(1) push, unlink and pop. Front is newest, back is the victim.
The two sentinel nodes are the detail interviewers watch for: with a permanent
head and tail, ``push_front`` and ``unlink`` never test for ``None``, so there
is no special case for the first or the last element to get wrong.
"""
def __init__(self) -> None:
self._head = Node(key=None) # sentinel before the newest node
self._tail = Node(key=None) # sentinel after the oldest node
self._head.next = self._tail
self._tail.prev = self._head
self._size = 0
def __len__(self) -> int:
return self._size
def is_empty(self) -> bool:
return self._size == 0
def push_front(self, node: Node) -> None:
first = self._head.next
node.prev, node.next = self._head, first
self._head.next = node
first.prev = node # type: ignore[union-attr]
self._size += 1
def unlink(self, node: Node) -> None:
before, after = node.prev, node.next
before.next = after # type: ignore[union-attr]
after.prev = before # type: ignore[union-attr]
node.prev = node.next = None
self._size -= 1
def move_to_front(self, node: Node) -> None:
self.unlink(node)
self.push_front(node)
def pop_back(self) -> Node:
"""Remove and return the oldest node - the eviction victim."""
if self.is_empty():
raise EmptyCacheError("the list is empty; there is nothing to evict")
victim = self._tail.prev
self.unlink(victim) # type: ignore[arg-type]
return victim # type: ignore[return-value]
def keys_back_to_front(self) -> list[Hashable]:
"""Keys in eviction order, victim first. O(n); used by tests and the demo."""
out: list[Hashable] = []
node = self._tail.prev
while node is not None and node is not self._head:
out.append(node.key)
node = node.prev
return out
The policy interface is five verbs and one rule: the cache owns values, the policy owns order. Because every method runs with the cache's lock already held, no policy needs a lock of its own — say that out loud, it is the reason the design stays simple.
class EvictionPolicy(Protocol):
"""Owns *order*, never values. The cache owns the values, never the order.
That split is the whole design: a policy can be swapped, unit-tested on its
own and reasoned about without touching TTL, stats or locking. Every method
is called with the cache's lock already held, so policies need no lock.
"""
def on_insert(self, key: Hashable) -> None:
"""A key that was not present has just been stored."""
def on_access(self, key: Hashable) -> None:
"""A stored key was read or rewritten."""
def on_remove(self, key: Hashable) -> None:
"""A key left by explicit delete or by expiry (not by eviction)."""
def evict(self) -> Hashable:
"""Drop and return the victim. Raises ``EmptyCacheError`` when empty."""
def clear(self) -> None: ...
def keys(self) -> list[Hashable]:
"""Tracked keys in eviction order, victim first."""
def __len__(self) -> int: ...
LRU and FIFO share everything except what a read means, so the shared machinery lives in an abstract base with exactly one abstract method:
class RecencyPolicy(ABC):
"""Shared machinery for the two order-of-arrival policies: an index and one list.
Template Method: insert, remove, evict and the key listing are written once
here; subclasses override exactly one hook, ``on_access``. LRU moves the node
to the front on every read, FIFO ignores reads - which is the entire
difference between the two algorithms, and now it is one method long.
"""
def __init__(self) -> None:
self._nodes: dict[Hashable, Node] = {}
self._order = DoublyLinkedList()
def on_insert(self, key: Hashable) -> None:
node = Node(key=key)
self._nodes[key] = node
self._order.push_front(node)
@abstractmethod
def on_access(self, key: Hashable) -> None:
"""The one hook that separates LRU from FIFO."""
def on_remove(self, key: Hashable) -> None:
self._order.unlink(self._nodes.pop(key))
def evict(self) -> Hashable:
if not self._nodes:
raise EmptyCacheError("no key to evict")
victim = self._order.pop_back()
del self._nodes[victim.key]
return victim.key
def clear(self) -> None:
self._nodes.clear()
self._order = DoublyLinkedList()
def keys(self) -> list[Hashable]:
return self._order.keys_back_to_front()
def __len__(self) -> int:
return len(self._nodes)
class LRUPolicy(RecencyPolicy):
"""Least recently used leaves first: every read moves its node to the front."""
def on_access(self, key: Hashable) -> None:
self._order.move_to_front(self._nodes[key])
class FIFOPolicy(RecencyPolicy):
"""Oldest insertion leaves first; reads change nothing.
Cheaper than LRU (no pointer moves on the read path) and worse on any
workload with re-reads, because a hot key ages out on schedule anyway.
"""
def on_access(self, key: Hashable) -> None:
return None
LFU is the one people get wrong. The trick is that you never search for the minimum count: _min_freq is maintained, a new key resets it to 1, and promoting the last key out of the minimum bucket moves it up by exactly one.
class LFUPolicy:
"""Least frequently used leaves first, ties broken by least recently used.
``_buckets[f]`` holds every key seen exactly ``f`` times, newest at the front,
and ``_min_freq`` is the lowest non-empty bucket. That pair is what makes
eviction O(1): there is never a scan for the minimum count, and the tie inside
the bucket is settled by taking its back - the LRU key of that frequency.
"""
def __init__(self) -> None:
self._nodes: dict[Hashable, Node] = {}
self._buckets: dict[int, DoublyLinkedList] = {}
self._min_freq = 0
def on_insert(self, key: Hashable) -> None:
node = Node(key=key, freq=1)
self._nodes[key] = node
self._bucket(1).push_front(node)
self._min_freq = 1 # a brand new key is always the least used one
def on_access(self, key: Hashable) -> None:
node = self._nodes[key]
bucket = self._buckets[node.freq]
bucket.unlink(node)
if bucket.is_empty():
del self._buckets[node.freq]
if self._min_freq == node.freq:
# The node itself lands in freq + 1 and every surviving bucket is
# higher, so the new minimum is exactly one more. No scan: this is
# the step that makes the read path O(1).
self._min_freq = node.freq + 1
node.freq += 1
self._bucket(node.freq).push_front(node)
def on_remove(self, key: Hashable) -> None:
self._detach(self._nodes.pop(key))
def evict(self) -> Hashable:
if not self._nodes:
raise EmptyCacheError("no key to evict")
victim = self._buckets[self._min_freq].pop_back()
self._drop_empty_bucket(self._min_freq)
del self._nodes[victim.key]
return victim.key
def clear(self) -> None:
self._nodes.clear()
self._buckets.clear()
self._min_freq = 0
def keys(self) -> list[Hashable]:
out: list[Hashable] = []
for freq in sorted(self._buckets):
out.extend(self._buckets[freq].keys_back_to_front())
return out
def __len__(self) -> int:
return len(self._nodes)
def _bucket(self, freq: int) -> DoublyLinkedList:
bucket = self._buckets.get(freq)
if bucket is None:
bucket = self._buckets[freq] = DoublyLinkedList()
return bucket
def _detach(self, node: Node) -> None:
self._buckets[node.freq].unlink(node)
self._drop_empty_bucket(node.freq)
def _drop_empty_bucket(self, freq: int) -> None:
"""Keep ``_min_freq`` pointing at a bucket that still exists."""
if not self._buckets[freq].is_empty():
return
del self._buckets[freq]
if self._min_freq == freq:
# O(distinct frequencies), and never on the read path: only an explicit
# delete, an expiry, or an eviction that drains the minimum bucket - and
# after an eviction the next insert resets ``_min_freq`` to 1 anyway.
self._min_freq = min(self._buckets, default=0)
The cache is then short, which is the point: it validates, reads the clock once per call, and keeps the dict and the policy in step under one lock.
class Cache[K: Hashable, V]:
"""Bounded, thread-safe, O(1) cache: a dict for the values, a policy for the order.
One ``threading.RLock`` guards three pieces of state that must always agree:
``_entries``, the policy's ordering structure and the counters. Splitting them
would let a reader see a key the policy has already evicted. The lock is
*reentrant* so a public method may call another one (``purge_expired`` walks
keys and calls the same removal helper as ``delete``) without a second lock
protocol; an uncontended acquire costs about 17 ns, so the reentrancy is not
what your latency budget will notice.
"""
def __init__(
self,
capacity: int,
policy: EvictionPolicy | None = None,
clock: Clock | None = None,
default_ttl: float | None = None,
) -> None:
if capacity < 1:
raise CapacityError(f"capacity must be at least 1, got {capacity}")
if default_ttl is not None and default_ttl <= 0:
raise ValidationError("default_ttl must be positive")
self.capacity = capacity
# `policy or LRUPolicy()` would be a bug: an empty policy is falsy because
# it defines __len__, so every caller would silently get an LRU cache.
self._policy = LRUPolicy() if policy is None else policy
self._clock = clock or SystemClock()
self._default_ttl = default_ttl
self._entries: dict[K, Entry[V]] = {}
self._lock = threading.RLock()
self._hits = self._misses = self._evictions = self._expirations = 0
def try_get(self, key: K) -> Entry[V] | None:
"""The full read path: expiry check, recency update, hit or miss counted.
It returns the *entry*, not the value, so a caller can tell "no such key"
from "a key whose value is ``None``" - which is what makes caching a
negative lookup possible.
"""
with self._lock:
entry = self._entries.get(key)
if entry is None:
self._misses += 1
return None
if entry.is_expired(self._clock.now()):
self._discard(key) # lazy expiry: the reader pays for the cleanup
self._expirations += 1
self._misses += 1
return None
self._policy.on_access(key)
self._hits += 1
return entry
def get(self, key: K, default: V | None = None) -> V | None:
entry = self.try_get(key)
return default if entry is None else entry.value
def __getitem__(self, key: K) -> V:
entry = self.try_get(key)
if entry is None:
raise KeyMissingError(f"{key!r} is not in the cache")
return entry.value
def put(self, key: K, value: V, ttl: float | None = None) -> None:
"""Insert or overwrite. Eviction happens only on the insert path."""
if ttl is not None and ttl <= 0:
raise ValidationError("ttl must be positive; use delete() to remove a key")
deadline = self._deadline(self._default_ttl if ttl is None else ttl)
with self._lock:
if key in self._entries:
self._entries[key] = Entry(value, deadline)
self._policy.on_access(key) # a rewrite counts as a use
return
if len(self._entries) >= self.capacity:
self._evict_one()
self._entries[key] = Entry(value, deadline)
self._policy.on_insert(key)
def delete(self, key: K) -> bool:
with self._lock:
if key not in self._entries:
return False
self._discard(key)
return True
def __contains__(self, key: K) -> bool:
"""Membership without touching recency or the counters; expired keys are absent."""
with self._lock:
entry = self._entries.get(key)
return entry is not None and not entry.is_expired(self._clock.now())
def __len__(self) -> int:
with self._lock:
return len(self._entries)
def purge_expired(self) -> int:
"""Active expiry: drop every entry past its deadline. O(n), so call it on a timer."""
with self._lock:
now = self._clock.now()
dead = [k for k, entry in self._entries.items() if entry.is_expired(now)]
for key in dead:
self._discard(key)
self._expirations += len(dead)
return len(dead)
def keys(self) -> list[K]:
"""A snapshot of the live keys; expired entries are left out."""
with self._lock:
now = self._clock.now()
return [key for key, entry in self._entries.items() if not entry.is_expired(now)]
def eviction_order(self) -> list[Hashable]:
"""Tracked keys, victim first - the cheapest way to assert a policy in a test."""
with self._lock:
return self._policy.keys()
def clear(self) -> None:
with self._lock:
self._entries.clear()
self._policy.clear()
def stats(self) -> CacheStats:
with self._lock:
return CacheStats(
hits=self._hits,
misses=self._misses,
evictions=self._evictions,
expirations=self._expirations,
size=len(self._entries),
capacity=self.capacity,
)
def _deadline(self, ttl: float | None) -> float | None:
return None if ttl is None else self._clock.now() + ttl
def _evict_one(self) -> None:
"""Caller holds the lock. The policy picks; the cache forgets the value."""
victim = self._policy.evict()
del self._entries[victim]
self._evictions += 1
def _discard(self, key: K) -> None:
"""Caller holds the lock. Remove a key from both structures at once."""
del self._entries[key]
self._policy.on_remove(key)
The loader is a decorator, not a feature of the cache. Its single-flight guard is a fixed array of stripe locks rather than a lock per key, so there is no per-key bookkeeping to leak:
class LoadingCache[K: Hashable, V]:
"""Cache-aside behind one call, with a single-flight guard against stampedes.
Decorator: it wraps *a* ``Cache`` and adds exactly one behaviour. On a miss,
one thread runs the loader while every other thread asking for the same key
waits on the same stripe lock and then finds the value already stored. Without
the guard, a hot key expiring under 500 requests/s sends 500 identical queries
to the database in the time it takes to answer one.
The guard is a fixed array of locks chosen by ``hash(key)``, not a dict of
locks per key: no bookkeeping, no leak, and the only cost is that two keys
that share a stripe load one after the other instead of together.
"""
def __init__(
self,
inner: Cache[K, V],
loader: Callable[[K], V],
ttl: float | None = None,
stripes: int = DEFAULT_LOAD_STRIPES,
) -> None:
if stripes < 1:
raise ValidationError("stripes must be at least 1")
self._inner = inner
self._loader = loader
self._ttl = ttl
self._stripes = [threading.Lock() for _ in range(stripes)]
self._counter_lock = threading.Lock()
self._loads = self._coalesced = 0
def get(self, key: K) -> V:
entry = self._inner.try_get(key)
if entry is not None:
return entry.value
with self._stripes[hash(key) % len(self._stripes)]:
entry = self._inner.try_get(key) # a waiter re-checks: the winner may have filled it
if entry is not None:
self._bump(coalesced=1)
return entry.value
value = self._loader(key) # a loader failure propagates and is not cached
self._inner.put(key, value, ttl=self._ttl)
self._bump(loads=1)
return value
def invalidate(self, key: K) -> bool:
return self._inner.delete(key)
def stats(self) -> CacheStats:
with self._counter_lock:
return replace(self._inner.stats(), loads=self._loads, coalesced=self._coalesced)
def _bump(self, loads: int = 0, coalesced: int = 0) -> None:
with self._counter_lock:
self._loads += loads
self._coalesced += coalesced
Sharding and the sweeper are the two answers you keep in your pocket for "what if this is too slow?" and "what about memory?":
class ShardedCache[K: Hashable, V]:
"""N independent caches picked by ``hash(key)`` - the answer to "one lock is a bottleneck".
You cannot stripe a single strict LRU, because the recency list is global
state that every read mutates. What production caches do instead is exactly
this: shard the key space, give each shard its own lock and its own order, and
accept an eviction order that is per shard rather than global. Contention
falls roughly with the shard count; the hit ratio moves by a fraction of a
percent because the shards get statistically similar load.
"""
def __init__(
self,
capacity: int,
shards: int = DEFAULT_SHARDS,
policy: EvictionPolicyName | str = EvictionPolicyName.LRU,
clock: Clock | None = None,
default_ttl: float | None = None,
) -> None:
if shards < 1:
raise ValidationError("shards must be at least 1")
if capacity < shards:
raise CapacityError(f"capacity {capacity} cannot be split across {shards} shards")
per_shard = capacity // shards
self._shards: list[Cache[K, V]] = [
Cache(per_shard, make_policy(policy), clock=clock, default_ttl=default_ttl)
for _ in range(shards)
]
def shard_for(self, key: K) -> Cache[K, V]:
return self._shards[hash(key) % len(self._shards)]
def get(self, key: K, default: V | None = None) -> V | None:
return self.shard_for(key).get(key, default)
def put(self, key: K, value: V, ttl: float | None = None) -> None:
self.shard_for(key).put(key, value, ttl=ttl)
def delete(self, key: K) -> bool:
return self.shard_for(key).delete(key)
def __contains__(self, key: K) -> bool:
return key in self.shard_for(key)
def __len__(self) -> int:
return sum(len(shard) for shard in self._shards)
def stats(self) -> CacheStats:
parts = [shard.stats() for shard in self._shards]
return CacheStats(
hits=sum(p.hits for p in parts),
misses=sum(p.misses for p in parts),
evictions=sum(p.evictions for p in parts),
expirations=sum(p.expirations for p in parts),
size=sum(p.size for p in parts),
capacity=sum(p.capacity for p in parts),
)
class TtlSweeper[K: Hashable, V]:
"""Optional background thread that calls ``purge_expired`` every ``interval`` seconds.
Lazy expiry alone is already correct - an expired entry can never be read.
The sweeper is about *memory*: a key written once, expired and never read
again would otherwise hold its value until eviction pressure removed it.
Shutdown is the part interviewers probe. The loop waits on an ``Event``
instead of sleeping, so ``stop()`` returns as soon as the flag is set rather
than after the rest of an interval, and the thread is a daemon so a forgotten
``stop()`` cannot keep the process alive.
"""
def __init__(self, cache: Cache[K, V], interval: float, name: str = "ttl-sweeper") -> None:
if interval <= 0:
raise ValidationError("interval must be positive")
self._cache = cache
self._interval = interval
self._stopping = threading.Event()
self._thread = threading.Thread(target=self._run, name=name, daemon=True)
self._purged = 0
@property
def purged(self) -> int:
"""Entries reclaimed so far. Written by the sweeper thread only."""
return self._purged
def start(self) -> None:
self._thread.start()
def stop(self, timeout: float = 1.0) -> None:
self._stopping.set()
if self._thread.is_alive():
self._thread.join(timeout)
def _run(self) -> None:
while not self._stopping.wait(self._interval):
self._purged += self._cache.purge_expired()
Running python -m lld.in_memory_cache.demo walks the whole surface — the same access trace under LRU and under LFU, lazy expiry, the sweeper, the stampede and the sharded variant:
--- LRU, capacity 3: put a,b,c then read a, then put d ---
eviction order, victim first: ['c', 'a', 'd']
b was evicted: get('b') -> None, stats: size=3/3 hits=1 misses=1 evictions=1 expirations=0 hit_ratio=0.50
--- LFU, capacity 3: a read 3 times, b once, c never, then put d ---
eviction order, victim first: ['d', 'b', 'a']
c was evicted (least used): get('c') -> None
--- TTL with lazy expiry ---
after 4 min: user-7
after 6 min: None, size=0/100 hits=1 misses=1 evictions=0 expirations=1 hit_ratio=0.50
--- background sweeper reclaims what nobody reads again ---
reclaimed both keys without a read: True, cache size now 0
--- loading cache: 8 threads, one cold key, one database query ---
values agree: {'row(product:1)'}, loader ran 1 time(s), coalesced=7
--- sharded cache: 8 locks instead of 1 ---
400 keys written by 8 threads, capacity 64 -> size 64
size=64/64 hits=0 misses=0 evictions=336 expirations=0 hit_ratio=0.00
Concurrency and edge cases¶
Which lock protects what. Cache._lock is one threading.RLock guarding three things that must always agree: _entries, the policy's ordering structure, and the counters. The race it prevents is the one every candidate half-sees: put reads len(_entries) >= capacity, decides not to evict, and inserts. Two threads can both read 49 against a capacity of 50, both skip the eviction and both insert — and now the dict holds 51 entries while the policy's list holds 51 nodes that no longer match the dict after the next eviction. Reading the size and acting on it is one critical section, not two.
Why reentrant. purge_expired walks the keys and calls the same private removal helper as delete; a plain Lock would force a second no-lock variant of every internal method, which is exactly how a codebase grows a deadlock. An uncontended acquire costs about 17 ns against a 100 ns main-memory reference, so reentrancy is not what your latency budget will notice — contention is.
Why you cannot simply stripe an LRU. The recency list is global state that every read mutates, so per-key locks buy nothing: they all end up serialising on the list anyway. The real answer is ShardedCache — partition the key space, give each shard its own lock and its own order, and accept that eviction is now per shard. That is what production caches do, and the hit-ratio cost is small because the shards see statistically similar load.
Lazy expiry and its cost. An expired entry occupies memory until something reads it or the sweeper runs. Lazy expiry alone is correct — the read path checks the deadline before every hit — but a write-once key that expires and is never read again would sit there until eviction pressure removed it. The sweeper is Event.wait(interval) rather than sleep, so stop() returns as soon as the flag is set instead of after the rest of an interval, and the thread is a daemon so a forgotten stop() cannot keep the process alive.
Edge cases handled: capacity below 1 is rejected at construction rather than producing a cache that evicts what it just inserted; a non-positive TTL is rejected because "expire immediately" is a delete; a rewrite updates in place instead of inserting a second node; key in cache never resurrects an expired key and never disturbs recency; the LFU tie is broken by taking the back of the minimum bucket, which is the least recently used key at that frequency; deleting a key repairs _min_freq instead of leaving it pointing at a bucket that no longer exists; and a loader that raises propagates and stores nothing, so a database outage does not fill the cache with failures.
Common mistake
Writing self._policy = policy or LRUPolicy(). It reads fine and it is a real bug: a policy defines __len__, an empty policy is therefore falsy, and every caller who passes a fresh LFUPolicy() silently gets an LRU cache. Use if policy is None. The general rule is worth saying in the room — or for defaults is only safe for arguments that can never be falsy.
Extensibility and follow-ups¶
- LRU-K and ARC: LRU-K evicts on the K-th most recent access rather than the last one, which stops a single scan from flushing the whole cache. Both are new
EvictionPolicyimplementations; ARC additionally keeps ghost lists of recently evicted keys, so it needs a policy that is told about evictions — one more hook, not a redesign. - Size-based eviction: give
puta weight and keep a running total;_evict_onebecomeswhile total > limit: evict. The policy interface does not change at all. - Sliding TTL: refresh
expires_atinsidetry_geton a hit. One line, and a genuinely different product decision — say which you chose. - Probabilistic early expiration: have
try_gettreat an entry as expired slightly before its deadline with a probability that grows as the deadline approaches, so one request refreshes a hot key while the rest still get the cached value. It composes with the single-flight guard rather than replacing it. - Monotonic time:
SystemClock.now()is wall-clock, and a clock step from an NTP correction can expire or resurrect entries. In production theClockyou inject should read a monotonic source; the injection point is already there, which is the whole benefit of not callingtime.time()inside the cache. - Async loader: the same
LoadingCacheshape with anasyncio.Lockper stripe and an awaited loader — the algorithm is unchanged. - Distribution: once the cache must survive a process restart or be shared by many machines, the conversation becomes sharding, replication and cross-node invalidation, and it moves to the distributed-cache case study.
Sizing is the other follow-up worth rehearsing. The 80/20 rule from the estimation sheet gives you the capacity in one line: 100M reads/day at 1 KB per object, caching the hottest 20%, is 100M x 1 KB x 0.2 = 20 GB — one large machine, or a small cluster once you want redundancy. And the reason to bother: a hit costs a ~100 ns memory reference against ~16 µs for the 4 KB SSD read it replaces, roughly 160 times cheaper before the query itself is counted.
Interview tip
When you are asked for LFU, do not start typing. Say the shape first: "a dict from key to node, a dict from frequency to a list of nodes, and a _min_freq integer — the integer is what makes eviction O(1) instead of a scan." Then write it. Interviewers grade whether you knew the invariant before you wrote the code, and _min_freq is the invariant.
Tests¶
tests/test_in_memory_cache.py has 18 cases. The two worth walking an interviewer through are the capacity invariant under load and the stampede.
def test_concurrent_writers_never_break_the_capacity_invariant(clock: FakeClock) -> None:
"""8 threads, 800 distinct keys, capacity 50: the two structures must not drift.
Without the lock, `len(entries) >= capacity` and the eviction that follows are
two steps: two threads can both read 49, both skip the eviction and both
insert - leaving 51 entries and, worse, a policy that no longer lists the same
keys the dict holds.
"""
cache: Cache[str, int] = Cache(capacity=50, policy=LRUPolicy(), clock=clock)
def write(i: int) -> None:
cache.put(f"key-{i}", i)
cache.get(f"key-{i // 2}")
with ThreadPoolExecutor(max_workers=8) as pool:
list(pool.map(write, range(800)))
assert len(cache) == 50
assert set(cache.keys()) == set(cache.eviction_order())
stats = cache.stats()
assert stats.lookups == 800 # no counter update was lost
assert stats.evictions == 750
The assertion that matters is not len(cache) == 50, which a lucky race would still satisfy; it is that the dict's key set equals the policy's key set. Structural drift between the two is the bug an unlocked cache actually produces, and it survives long after the count looks right.
def test_single_flight_loads_a_hot_key_once(clock: FakeClock) -> None:
"""The stampede test: 16 threads miss the same key, the loader runs once."""
calls: list[str] = []
gate = threading.Barrier(16)
def loader(key: str) -> str:
calls.append(key)
time.sleep(0.01) # a slow query is what makes a stampede expensive
return f"row({key})"
cache = LoadingCache(Cache[str, str](capacity=8, clock=clock), loader=loader)
def read(_: int) -> str:
gate.wait()
return cache.get("product:1")
with ThreadPoolExecutor(max_workers=16) as pool:
values = set(pool.map(read, range(16)))
assert values == {"row(product:1)"}
assert calls == ["product:1"] # exactly one database round trip
stats = cache.stats()
# one winner ran the loader; the other 15 re-checked under the stripe and found it
assert stats.loads == 1 and stats.coalesced == 15 and stats.misses == 17
A threading.Barrier makes the stampede deterministic: all sixteen threads arrive at the miss together instead of trickling in after the first one has already filled the cache.
The rest cover: LRU eviction order and its stats; LFU eviction with the frequency tie broken by recency; reading the only key in the minimum bucket, which is the one promotion that has to move _min_freq by hand; a parametrized case where LRU, LFU and FIFO disagree about a key that was written first and then read; lazy expiry with KeyMissingError from the strict accessor; active purge; rejected capacities and TTLs; delete-and-overwrite keeping both structures in step; a loader failure that is retried rather than cached; the sweeper reclaiming in the background and stopping within its timeout; and the sharded cache splitting its capacity. Run them with uv run pytest code/lld/in_memory_cache -q.
45-minute pacing¶
| Minutes | What to do | What to say or write |
|---|---|---|
| 0–5 | Clarify | Capacity in entries or bytes? Which policies? TTL absolute or sliding? Threads? Out of scope: persistence, distribution. |
| 5–10 | Entities and API | get, put, delete, stats on the board. Name the split immediately: dict owns values, policy owns order. |
| 10–16 | LRU | Draw the dict beside the list, mark head as newest and tail as victim, then write Node, the sentinels and move_to_front. |
| 16–24 | Policy seam and LFU | Extract the five-verb EvictionPolicy, then write LFU with buckets and _min_freq. State the tie-break rule before coding it. |
| 24–32 | Cache, TTL and the lock | put with the eviction branch, try_get with lazy expiry, and the one lock around both structures. |
| 32–40 | Concurrency | The 49-plus-49 race, why an RLock, why LRU cannot be striped, and what the concurrency test asserts. |
| 40–45 | Extensions | Stampede and single flight, LRU-K and ARC as new policies, size-based eviction, and the hand-off to a distributed cache. |
Related¶
- Caching and CDNs — where caches sit, cache-aside versus write-through, and stampede protection at system scale
- Strategy — the pattern behind the pluggable eviction policy
- Template Method — the one-hook base class that separates LRU from FIFO
- Decorator — how
LoadingCacheadds read-through without touchingCache - Concurrency for LLD in Python — lock granularity, reentrancy and the read-modify-write race
- Design a distributed cache — the same problem once it no longer fits in one process
- Primary sources: Megiddo and Modha, "ARC: A Self-Tuning, Low Overhead Replacement Cache" (FAST 2003); Nishtala et al., "Scaling Memcache at Facebook" (NSDI 2013)