Multi-Level Cache
L1/L2/L3 cache layers composed as decorators, each checking its own storage before delegating down. Eviction strategies (LRU, LFU) are swappable per level, so you can tune each tier independently without modifying the chain.
Key Abstractions
Interface defining get/put operations. Every cache level and decorator implements this contract.
Wraps an inner CacheLayer, checks its own local storage first, and delegates to the wrapped layer on a miss.
Interface for swappable eviction policies. Implementations include LRU (recency-based) and LFU (frequency-based).
Coordinates invalidation and write-propagation across all cache levels, preventing direct coupling between layers.
Entry point for clients. Intercepts reads and writes, routing them through the cache hierarchy transparently.
Observer that receives cache events (hit, miss, eviction) for monitoring, logging, and metrics collection.
Class Diagram
How It Works
A multi-level cache mirrors the memory hierarchy in CPUs: small and fast at the top, large and slower at the bottom. L1 is typically an in-process hash map with minimal capacity (hundreds of entries). L2 might be a shared in-memory store like Redis with thousands of entries. L3 could be a distributed cache or even a CDN edge layer.
When a client requests a key, the system checks L1 first. On a hit, it returns immediately. On a miss, it falls through to L2, then L3. When a lower level produces a hit, the value gets promoted back up to higher levels so subsequent reads are fast. Each layer wraps the next, checking its own storage before delegating: that's the Decorator pattern in action.
Writes follow a write-through policy by default: the value is written to every level immediately. Every level stays consistent, but you pay for it in write latency. The alternative, write-back, writes only to L1 and asynchronously flushes to lower levels. You trade consistency for speed.
Invalidation is the hard part. When a key must be removed (data changed at the source), every level needs to know. Rather than having L1 call L2 call L3 directly (tight coupling), a Mediator holds references to all levels and broadcasts the invalidation in one pass.
Requirements
Functional
get(key)returns the cached value or null, checking levels top-downput(key, value)writes through all cache levelsinvalidate(key)removes the key from every level via the mediator- Each level supports a configurable eviction policy (LRU, LFU)
- Cache hits at lower levels promote the value to upper levels
Non-Functional
- O(1) get/put per level for LRU (LinkedHashMap). O(n) worst case for LFU eviction scan (can be optimized to O(1) with a frequency list)
- Thread-safe per-level operations via locking
- Observable: external listeners can track hit rates, miss rates, and eviction counts per level
- Configurable capacity and eviction strategy per level independently
Design Decisions
Couldn't you just use an if/else chain for lookups?
A naive approach puts all levels in one method: if l1.has(key) return l1.get(key); else if l2.has(key).... Two levels? Fine. But adding L3 means editing the lookup method. With Decorator, each layer wraps the next. Adding a level means wrapping one more object. The lookup method in each decorator is identical: check locally, delegate on miss. No existing code changes.
Does direct coupling work for invalidation?
If L1 directly calls L2.invalidate() and L2 calls L3.invalidate(), every layer must know about the layers below it. Remove L2 and L1 breaks. The Mediator holds a flat list of all levels. Invalidation is a single broadcast. Adding or removing a level means registering or unregistering with the mediator. No layer knows about any other layer.
Write-through vs write-back: when to use which?
Write-through is simpler and guarantees that all levels are consistent after every write. The cost is latency: every put blocks until all levels confirm. Write-back writes only to L1 and queues async flushes. Faster, but there's a window where lower levels serve stale data. Use write-through when correctness matters (financial data). Use write-back when read latency matters and eventual consistency is acceptable (social media feeds).
What if we just used the same eviction policy everywhere?
L1 is tiny and serves the hottest data. LRU works well here because recently accessed keys are most likely to be accessed again soon (temporal locality). L2 is larger and should retain keys that are popular over longer periods, even if they weren't accessed in the last few seconds. LFU captures this frequency-based popularity. One size does not fit all.
Interview Follow-ups
- Distributed multi-level cache: In a microservices architecture, L1 is per-instance (in-process), L2 is a shared Redis cluster. Invalidation must use pub/sub (Redis Pub/Sub, Kafka) so all instances evict stale keys. The mediator becomes a message publisher instead of a direct method caller.
- Cache stampede prevention: When a popular key expires, hundreds of threads simultaneously miss and hit the database. Solutions include mutex locking (only one thread fetches, others wait), probabilistic early expiration (randomly refresh before TTL), or request coalescing (group concurrent misses into one fetch).
- Consistency models: Strong consistency (invalidate-on-write) prevents stale reads but costs write latency. Eventual consistency (TTL-based expiration) is simpler but serves stale data within the TTL window. Hybrid approaches use short TTLs plus active invalidation for critical keys.
- Monitoring and tuning: Track hit/miss ratio per level. If L1 hit rate drops below 80%, increase its capacity or review the eviction policy. If L2 rarely gets hits, the data access pattern may not benefit from multi-level caching and a single level suffices.
45-Minute LLD Playbook
Each phase is what the interviewer expects you to do and say. Concrete steps, not topic hints. Diagrams are what you would sketch on the board.
- 15 min
Clarify scope and lock the process
GoalPin down the cache topology, the consistency model for writes, and what eviction means at each level. End by asking the interviewer whether they want a diagram first or code first so you can budget the remaining time.
Do & Say- ASK·1Open with: How many levels do we want, two or three? L1 in-process small and fast, L2 shared like Redis, L3 optionally a distributed tier? I will design for two with the third trivially added as another decorator.
- SAY·2Pin write policy: Write-through to every level by default, so reads at any tier are consistent. Write-back is a knob we add later as an alternate decorator behavior. Park it for v1.
- SAY·3Pin per-level eviction: L1 small with LRU because recency wins on a tiny working set. L2 larger with LFU because frequency matters more over a longer window. Per-level strategy, not one global policy.
- SAY·4Pin invalidation: When a source-of-truth write happens externally, we need a single call that wipes the key from every level. That is the mediator, not a chain of layer-to-layer calls.
- ASK·5ASK: Sketch the L1/L2 decorator stack first, or start with the CacheLayer interface in code? Budgeting the next 40 minutes. Diagram = 8 min sketch, otherwise 4 min of signatures then code.
Interviewer is grading: You explicitly park write-back, async invalidation, and stampede prevention as v2 rather than letting them creep into the core design. You ask the diagram-vs-code question unprompted.
- 25-10 min
Sketch the interfaces and (optionally) the decorator stack
GoalLock the CacheLayer interface and name where each pattern lives before any code. Draw the layered stack only if requested. Either way, call out the decorator-mediator split out loud.
Do & Say- WRITE·1Write the CacheLayer interface: get(key) -> Optional[str], put(key, value), invalidate(key). Every level, every decorator, and the proxy implement this same three-method contract.
- SAY·2Name the four roles: ConcreteCache is one level with its own storage and EvictionStrategy. CacheDecorator wraps a local ConcreteCache plus an inner CacheLayer. CacheProxy is the client entry point. CacheMediator holds flat references to every level for cross-level invalidation.
- WRITE·3Write the decorator behavior explicitly: On get, check local. On miss, delegate inward, and if the inner returns a hit, promote it back into local. On put, write-through to both. On invalidate, propagate down.
- SAY·4Name the EvictionStrategy contract: record_access(key), evict() returns the victim key, remove(key). LRU and LFU plug in here. The level holds the strategy as a constructor parameter, never as a hardcoded if/else.
- SAY·5Call out the mediator role: External invalidations from the source of truth do not walk the decorator chain because that would only hit the path you wrapped. The mediator has flat references to L1 and L2 and broadcasts in one pass.
- SAY·6If a diagram was requested, draw the stack: CacheProxy on top, then CacheDecorator wrapping ConcreteCache(L1) and ConcreteCache(L2), with CacheMediator hanging off the side holding both levels. Point at each cluster and name the pattern.
- SAY·7If no diagram, verbalize: Proxy is the entry point. Decorator does the inline read/write path. Mediator handles the cross-cutting invalidate. Strategy is the per-level eviction policy. Observer is the metrics pipe.
Interviewer is grading: You call out that the decorator chain and the mediator do different jobs (inline read path versus broadcast invalidation) without prompting. You commit to per-level eviction strategies, not a single global policy.
- 325 min
Code in this sequence (bottom-up)
GoalType the foundation first so each layer compiles against an already-defined interface. Talk while you type. End with a mental walk-through of one promote-on-hit and one mediator broadcast.
Do & Say- SAY·1Start with CacheListener (Observer interface) and a LoggingListener that prints on_hit, on_miss, on_eviction. Say: Observer first because every level needs the listener reference in its constructor. Decoupling metrics from cache code is what keeps the core layers from growing print statements. (~2 min)
- SAY·2Next, EvictionStrategy with LRUEviction (OrderedDict, move_to_end on access, popitem(last=False) on evict) and LFUEviction (defaultdict counting frequency, min by value on evict). Say: Two strategies for v1. New policies are new classes, never new branches inside ConcreteCache. (~5 min)
- SAY·3Then the CacheLayer interface with the three methods. Trivial but it has to exist before ConcreteCache implements it. (~1 min)
- SAY·4ConcreteCache: name, capacity, strategy, listeners, internal dict, lock. get fires on_hit/on_miss. put evicts via strategy at capacity, writes, fires on_eviction. invalidate removes from dict and strategy. Lowest level; doesn't know it's in a decorator chain. (~6 min)
- SAY·5CacheDecorator: local ConcreteCache plus inner CacheLayer. get checks local, delegates on miss, promotes inner-hit back to local. put writes through to both. invalidate propagates. Promote-on-hit raises the hot working set into L1. (~5 min)
- SAY·6Code CacheMediator: list of ConcreteCache references, register adds to it, invalidate_all iterates and calls invalidate on each. Say: Mediator does not walk the decorator chain. It has flat references because invalidation is a broadcast, not a read-path operation. (~3 min)
- SAY·7CacheProxy: chain plus mediator. get/put delegate to chain. invalidate delegates to mediator. Two-target dispatch: reads/writes go through the chain for promotion, invalidations skip it so every level gets hit. (~2 min)
- SAY·8Mental walk: Put user:1 (L1+L2), put user:2, put user:3 (L1 evicts user:1 via LRU). Get user:1: L1 miss, L2 hit, promote to L1 (evicts user:2). Invalidate user:3, mediator hits L1 and L2 directly. (~1 min)
Interviewer is grading: Code compiles as you type. You name promote-on-hit as the reason CacheDecorator does work on the return path of get. You call out why mediator and decorator dispatch differently for invalidate versus get/put. You run a mental walk-through unprompted.
- 45 min
Trade-offs, extensions, and wrap-up
GoalName two specific trade-offs you defend, volunteer one extension, close with a one-sentence summary that names every pattern and the role it plays.
Do & Say- SAY·1Trade-off one, write-through vs write-back: Write-through is consistent but slower. Write-back returns after L1 and queues async flush; faster with a stale-read window. Financial data: write-through. Social feeds: write-back. Wrong choice = double-counted likes or wrong balances.
- SAY·2Trade-off two, mediator over decorator-chain invalidation: Pushing invalidate down the chain works in-process but breaks when L2 is remote Redis (chain call blocks on network). Mediator with flat references swaps for Redis pub-sub broadcaster without layer changes.
- SAY·3Volunteer stampede prevention: When a popular key expires across all levels, every concurrent request misses to the backing store. Single-flight at L1: one thread fetches, others wait on a future. Or probabilistic early refresh on hot keys.
- WATCH·4Be ready for the distributed question: L1 stays per-instance in-process. L2 becomes a shared Redis. Invalidation moves from in-process method call to Redis pub-sub. Every instance subscribes and wipes its L1 on the event. Mediator interface stays, implementation swaps.
- SAY·5Close with one sentence: Proxy as the entry point. Decorator for the layered read path with promote-on-hit. Mediator for cross-level invalidation. Strategy for per-level eviction. Observer for metrics. Adding L3 is one more decorator and one more register call.
Interviewer is grading: You defend write-through versus write-back with a concrete failure mode, not just a textbook reason. You volunteer stampede prevention or the distributed L2 design unprompted.
Code Implementation
from abc import ABC, abstractmethod
from collections import OrderedDict, defaultdict
from dataclasses import dataclass, field
from typing import Optional
from threading import Lock
# ── Observer: Cache Event Listener ──────────────────────────────
class CacheListener(ABC):
@abstractmethod
def on_hit(self, level: str, key: str) -> None: ...
@abstractmethod
def on_miss(self, level: str, key: str) -> None: ...
@abstractmethod
def on_eviction(self, level: str, key: str) -> None: ...
class LoggingListener(CacheListener):
def on_hit(self, level: str, key: str) -> None:
print(f" [HIT] {level} -> key='{key}'")
def on_miss(self, level: str, key: str) -> None:
print(f" [MISS] {level} -> key='{key}'")
def on_eviction(self, level: str, key: str) -> None:
print(f" [EVICTION] {level} -> key='{key}'")
# ── Strategy: Eviction Policies ─────────────────────────────────
class EvictionStrategy(ABC):
@abstractmethod
def record_access(self, key: str) -> None: ...
@abstractmethod
def evict(self) -> Optional[str]: ...
@abstractmethod
def remove(self, key: str) -> None: ...
class LRUEviction(EvictionStrategy):
def __init__(self) -> None:
self._order: OrderedDict[str, None] = OrderedDict()
def record_access(self, key: str) -> None:
if key in self._order:
self._order.move_to_end(key)
else:
self._order[key] = None
def evict(self) -> Optional[str]:
if self._order:
return self._order.popitem(last=False)[0]
return None
def remove(self, key: str) -> None:
self._order.pop(key, None)
class LFUEviction(EvictionStrategy):
def __init__(self) -> None:
self._freq: dict[str, int] = defaultdict(int)
def record_access(self, key: str) -> None:
self._freq[key] += 1
def evict(self) -> Optional[str]:
if not self._freq:
return None
victim = min(self._freq, key=self._freq.get) # type: ignore
del self._freq[victim]
return victim
def remove(self, key: str) -> None:
self._freq.pop(key, None)
# ── Core: CacheLayer Interface ──────────────────────────────────
class CacheLayer(ABC):
@abstractmethod
def get(self, key: str) -> Optional[str]: ...
@abstractmethod
def put(self, key: str, value: str) -> None: ...
@abstractmethod
def invalidate(self, key: str) -> None: ...
# ── Concrete Cache Level ────────────────────────────────────────
@dataclass
class ConcreteCache(CacheLayer):
name: str
capacity: int
strategy: EvictionStrategy
listeners: list[CacheListener] = field(default_factory=list)
_storage: dict[str, str] = field(default_factory=dict, init=False)
_lock: Lock = field(default_factory=Lock, init=False)
def get(self, key: str) -> Optional[str]:
with self._lock:
if key in self._storage:
self.strategy.record_access(key)
for listener in self.listeners:
listener.on_hit(self.name, key)
return self._storage[key]
for listener in self.listeners:
listener.on_miss(self.name, key)
return None
def put(self, key: str, value: str) -> None:
with self._lock:
if key not in self._storage and len(self._storage) >= self.capacity:
victim = self.strategy.evict()
if victim and victim in self._storage:
del self._storage[victim]
for listener in self.listeners:
listener.on_eviction(self.name, victim)
self._storage[key] = value
self.strategy.record_access(key)
def invalidate(self, key: str) -> None:
with self._lock:
if key in self._storage:
del self._storage[key]
self.strategy.remove(key)
# ── Decorator: Layered Cache ────────────────────────────────────
class CacheDecorator(CacheLayer):
"""Checks local layer first, delegates to inner on miss."""
def __init__(self, local: ConcreteCache, inner: CacheLayer) -> None:
self._local = local
self._inner = inner
def get(self, key: str) -> Optional[str]:
value = self._local.get(key)
if value is not None:
return value
# Miss locally : try the next level
value = self._inner.get(key)
if value is not None:
# Promote to this level on hit from a lower level
self._local.put(key, value)
return value
def put(self, key: str, value: str) -> None:
# Write-through: write to all levels
self._local.put(key, value)
self._inner.put(key, value)
def invalidate(self, key: str) -> None:
self._local.invalidate(key)
self._inner.invalidate(key)
# ── Mediator: Cross-Level Invalidation ──────────────────────────
class CacheMediator:
def __init__(self) -> None:
self._layers: list[ConcreteCache] = []
def register(self, layer: ConcreteCache) -> None:
self._layers.append(layer)
def invalidate_all(self, key: str) -> None:
print(f" [MEDIATOR] Invalidating '{key}' across all levels")
for layer in self._layers:
layer.invalidate(key)
# ── Proxy: Client Entry Point ───────────────────────────────────
class CacheProxy(CacheLayer):
def __init__(self, chain: CacheLayer, mediator: CacheMediator) -> None:
self._chain = chain
self._mediator = mediator
def get(self, key: str) -> Optional[str]:
return self._chain.get(key)
def put(self, key: str, value: str) -> None:
self._chain.put(key, value)
def invalidate(self, key: str) -> None:
self._mediator.invalidate_all(key)
# ── Demo ────────────────────────────────────────────────────────
if __name__ == "__main__":
listener = LoggingListener()
# L2: larger capacity, LFU eviction
l2 = ConcreteCache(name="L2", capacity=4, strategy=LFUEviction(), listeners=[listener])
# L1: small capacity, LRU eviction
l1 = ConcreteCache(name="L1", capacity=2, strategy=LRUEviction(), listeners=[listener])
# Chain: L1 -> L2 (decorator pattern)
chain = CacheDecorator(local=l1, inner=l2)
# Mediator for coordinated invalidation
mediator = CacheMediator()
mediator.register(l1)
mediator.register(l2)
# Proxy is the client-facing entry point
cache = CacheProxy(chain=chain, mediator=mediator)
print("=== 1. Put values (write-through to L1 and L2) ===")
cache.put("user:1", "Alice")
cache.put("user:2", "Bob")
print()
print("=== 2. Get from L1 (cache hit) ===")
result = cache.get("user:1")
print(f" Result: {result}\n")
print("=== 3. Put a third key — triggers L1 eviction (capacity=2) ===")
cache.put("user:3", "Charlie")
print()
print("=== 4. Get evicted key — L1 miss, L2 hit, promote back to L1 ===")
result = cache.get("user:1")
print(f" Result: {result}\n")
print("=== 5. Mediator invalidation across all levels ===")
cache.invalidate("user:2")
print()
print("=== 6. Get invalidated key — miss everywhere ===")
result = cache.get("user:2")
print(f" Result: {result}\n")
print("=== 7. Fill L2 to trigger LFU eviction ===")
cache.put("user:4", "Diana")
cache.put("user:5", "Eve")
# Access user:3 multiple times to increase its frequency
cache.get("user:3")
cache.get("user:3")
# Now add one more : LFU should evict the least frequently used
cache.put("user:6", "Frank")
print()
print("=== 8. Verify LFU kept frequently accessed key ===")
result = cache.get("user:3")
print(f" Result for user:3 (frequently accessed): {result}")
print("\nAll operations completed successfully.")Interview Grading by Level
What an interviewer at each level expects to see in your answer. Use this to calibrate, not to perform.
Junior Engineer (L3)
Builds two cache levels with a working get-on-miss-then-delegate path but treats invalidation, eviction, and metrics as afterthoughts.
- Names Decorator for the L1-wrapping-L2 structure.
- Writes the CacheLayer interface with get and put.
- Implements LRU eviction with an OrderedDict.
- Handles miss-then-promote when prompted.
- Recognizes that write-through and write-back are different policies.
- Hardcodes LRU inside ConcreteCache instead of injecting EvictionStrategy.
- Implements invalidation by walking the decorator chain, which breaks the moment L2 is remote.
- Forgets to promote on inner-hit, so L1 stays cold even after hot reads.
- Couples metrics into the cache class with print statements instead of a listener.
- Treats per-level eviction as one global policy.
Mid-Level Engineer (L4)
Drives the design with the decorator chain and mediator split clearly named, picks per-level eviction strategies, and handles promote-on-hit without prompting.
- Writes the CacheLayer interface before any concrete class so both ConcreteCache, CacheDecorator, and CacheProxy implement the same three-method contract.
- Separates CacheMediator from the decorator chain explicitly, with the reasoning that invalidation is a broadcast not a read path.
- Picks LRU on L1 and LFU on L2 unprompted and defends each with the working-set argument.
- Implements promote-on-hit inside CacheDecorator.get so the working set rises over time.
- Implements thread safety with a per-level lock, not one giant lock around the chain.
- Walks through a put-evict-get-promote-invalidate sequence as a self-check before declaring done.
- Does not volunteer cache stampede prevention until asked.
- Treats observer notifications as fire-and-forget without considering a slow listener blocking eviction.
- Misses the timing-window leak between expiry and sweep when TTLs are involved.
Senior Engineer (L5+)
Volunteers stampede prevention, frames mediator versus decorator as a network-boundary decision, and names the per-level policy split as a working-set call rather than a textbook recommendation.
- Volunteers cache stampede prevention (single-flight or probabilistic early refresh) and explains exactly which keys are at risk.
- Frames mediator-over-chained-invalidation around the L2-is-remote case: a chain call blocks on the network, mediator can be swapped for Redis pub-sub without changing layer code.
- Names the immutability invariant of the decorator chain (constructed once at startup, never mutated) and uses it to argue thread safety without a giant lock.
- Picks LRU for L1 and LFU for L2 with a working-set argument, not a textbook one: 'L1 is tiny so recency dominates, L2 is larger so frequency over a longer window dominates.'
- Proposes a distributed L2 design with Redis pub-sub for invalidation broadcast, and explains how the mediator interface stays the same while the implementation swaps.
- Suggests an async listener pipe with a bounded queue so a slow metrics consumer cannot block eviction.
- Closes with a one-sentence summary that names proxy, decorator, mediator, strategy, and observer with the role each plays, in under 20 seconds.
Common Mistakes
- ✗Coupling cache levels directly so L1 calls L2 which calls L3. Adding or removing a level breaks everything. Decorator composition eliminates this rigidity.
- ✗Ignoring cache stampede. When a popular key expires simultaneously across levels, hundreds of threads hit the backing store at once. Use locking or request coalescing on miss.
- ✗Setting TTL only on L1 and forgetting lower levels. Stale data persists in L2/L3 and gets promoted back to L1 on the next miss, serving outdated values indefinitely.
- ✗Hardcoding the eviction policy into the cache layer. You can't tune per-level without forking the class. Strategy pattern keeps policies swappable.
Key Points
- ✓Decorator pattern lets you stack L1 -> L2 -> L3 without any layer knowing about the others. Adding a new level means wrapping one more decorator. Zero changes to existing layers.
- ✓The mediator centralizes cache coherence. When L1 invalidates a key, the mediator propagates that to L2 and L3 instead of each layer talking to every other layer directly.
- ✓Strategy pattern for eviction means each level can use the policy that fits its profile: L1 (small, fast) uses LRU for recency, L2 (larger, slower) uses LFU for frequency.
- ✓Write-through propagates writes to all levels immediately for consistency. Write-back defers lower-level writes for throughput. The choice is a consistency-vs-latency tradeoff.