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.
Code Implementation
1 from abc import ABC, abstractmethod
2 from collections import OrderedDict, defaultdict
3 from dataclasses import dataclass, field
4 from typing import Optional
5 from threading import Lock
6
7
8 # ── Observer: Cache Event Listener ──────────────────────────────
9
10 class CacheListener(ABC):
11 @abstractmethod
12 def on_hit(self, level: str, key: str) -> None: ...
13 @abstractmethod
14 def on_miss(self, level: str, key: str) -> None: ...
15 @abstractmethod
16 def on_eviction(self, level: str, key: str) -> None: ...
17
18
19 class LoggingListener(CacheListener):
20 def on_hit(self, level: str, key: str) -> None:
21 print(f" [HIT] {level} -> key='{key}'")
22
23 def on_miss(self, level: str, key: str) -> None:
24 print(f" [MISS] {level} -> key='{key}'")
25
26 def on_eviction(self, level: str, key: str) -> None:
27 print(f" [EVICTION] {level} -> key='{key}'")
28
29
30 # ── Strategy: Eviction Policies ─────────────────────────────────
31
32 class EvictionStrategy(ABC):
33 @abstractmethod
34 def record_access(self, key: str) -> None: ...
35 @abstractmethod
36 def evict(self) -> Optional[str]: ...
37 @abstractmethod
38 def remove(self, key: str) -> None: ...
39
40
41 class LRUEviction(EvictionStrategy):
42 def __init__(self) -> None:
43 self._order: OrderedDict[str, None] = OrderedDict()
44
45 def record_access(self, key: str) -> None:
46 if key in self._order:
47 self._order.move_to_end(key)
48 else:
49 self._order[key] = None
50
51 def evict(self) -> Optional[str]:
52 if self._order:
53 return self._order.popitem(last=False)[0]
54 return None
55
56 def remove(self, key: str) -> None:
57 self._order.pop(key, None)
58
59
60 class LFUEviction(EvictionStrategy):
61 def __init__(self) -> None:
62 self._freq: dict[str, int] = defaultdict(int)
63
64 def record_access(self, key: str) -> None:
65 self._freq[key] += 1
66
67 def evict(self) -> Optional[str]:
68 if not self._freq:
69 return None
70 victim = min(self._freq, key=self._freq.get) # type: ignore
71 del self._freq[victim]
72 return victim
73
74 def remove(self, key: str) -> None:
75 self._freq.pop(key, None)
76
77
78 # ── Core: CacheLayer Interface ──────────────────────────────────
79
80 class CacheLayer(ABC):
81 @abstractmethod
82 def get(self, key: str) -> Optional[str]: ...
83 @abstractmethod
84 def put(self, key: str, value: str) -> None: ...
85 @abstractmethod
86 def invalidate(self, key: str) -> None: ...
87
88
89 # ── Concrete Cache Level ────────────────────────────────────────
90
91 @dataclass
92 class ConcreteCache(CacheLayer):
93 name: str
94 capacity: int
95 strategy: EvictionStrategy
96 listeners: list[CacheListener] = field(default_factory=list)
97 _storage: dict[str, str] = field(default_factory=dict, init=False)
98 _lock: Lock = field(default_factory=Lock, init=False)
99
100 def get(self, key: str) -> Optional[str]:
101 with self._lock:
102 if key in self._storage:
103 self.strategy.record_access(key)
104 for listener in self.listeners:
105 listener.on_hit(self.name, key)
106 return self._storage[key]
107 for listener in self.listeners:
108 listener.on_miss(self.name, key)
109 return None
110
111 def put(self, key: str, value: str) -> None:
112 with self._lock:
113 if key not in self._storage and len(self._storage) >= self.capacity:
114 victim = self.strategy.evict()
115 if victim and victim in self._storage:
116 del self._storage[victim]
117 for listener in self.listeners:
118 listener.on_eviction(self.name, victim)
119 self._storage[key] = value
120 self.strategy.record_access(key)
121
122 def invalidate(self, key: str) -> None:
123 with self._lock:
124 if key in self._storage:
125 del self._storage[key]
126 self.strategy.remove(key)
127
128
129 # ── Decorator: Layered Cache ────────────────────────────────────
130
131 class CacheDecorator(CacheLayer):
132 """Checks local layer first, delegates to inner on miss."""
133
134 def __init__(self, local: ConcreteCache, inner: CacheLayer) -> None:
135 self._local = local
136 self._inner = inner
137
138 def get(self, key: str) -> Optional[str]:
139 value = self._local.get(key)
140 if value is not None:
141 return value
142 # Miss locally : try the next level
143 value = self._inner.get(key)
144 if value is not None:
145 # Promote to this level on hit from a lower level
146 self._local.put(key, value)
147 return value
148
149 def put(self, key: str, value: str) -> None:
150 # Write-through: write to all levels
151 self._local.put(key, value)
152 self._inner.put(key, value)
153
154 def invalidate(self, key: str) -> None:
155 self._local.invalidate(key)
156 self._inner.invalidate(key)
157
158
159 # ── Mediator: Cross-Level Invalidation ──────────────────────────
160
161 class CacheMediator:
162 def __init__(self) -> None:
163 self._layers: list[ConcreteCache] = []
164
165 def register(self, layer: ConcreteCache) -> None:
166 self._layers.append(layer)
167
168 def invalidate_all(self, key: str) -> None:
169 print(f" [MEDIATOR] Invalidating '{key}' across all levels")
170 for layer in self._layers:
171 layer.invalidate(key)
172
173
174 # ── Proxy: Client Entry Point ───────────────────────────────────
175
176 class CacheProxy(CacheLayer):
177 def __init__(self, chain: CacheLayer, mediator: CacheMediator) -> None:
178 self._chain = chain
179 self._mediator = mediator
180
181 def get(self, key: str) -> Optional[str]:
182 return self._chain.get(key)
183
184 def put(self, key: str, value: str) -> None:
185 self._chain.put(key, value)
186
187 def invalidate(self, key: str) -> None:
188 self._mediator.invalidate_all(key)
189
190
191 # ── Demo ────────────────────────────────────────────────────────
192
193 if __name__ == "__main__":
194 listener = LoggingListener()
195
196 # L2: larger capacity, LFU eviction
197 l2 = ConcreteCache(name="L2", capacity=4, strategy=LFUEviction(), listeners=[listener])
198
199 # L1: small capacity, LRU eviction
200 l1 = ConcreteCache(name="L1", capacity=2, strategy=LRUEviction(), listeners=[listener])
201
202 # Chain: L1 -> L2 (decorator pattern)
203 chain = CacheDecorator(local=l1, inner=l2)
204
205 # Mediator for coordinated invalidation
206 mediator = CacheMediator()
207 mediator.register(l1)
208 mediator.register(l2)
209
210 # Proxy is the client-facing entry point
211 cache = CacheProxy(chain=chain, mediator=mediator)
212
213 print("=== 1. Put values (write-through to L1 and L2) ===")
214 cache.put("user:1", "Alice")
215 cache.put("user:2", "Bob")
216 print()
217
218 print("=== 2. Get from L1 (cache hit) ===")
219 result = cache.get("user:1")
220 print(f" Result: {result}\n")
221
222 print("=== 3. Put a third key — triggers L1 eviction (capacity=2) ===")
223 cache.put("user:3", "Charlie")
224 print()
225
226 print("=== 4. Get evicted key — L1 miss, L2 hit, promote back to L1 ===")
227 result = cache.get("user:1")
228 print(f" Result: {result}\n")
229
230 print("=== 5. Mediator invalidation across all levels ===")
231 cache.invalidate("user:2")
232 print()
233
234 print("=== 6. Get invalidated key — miss everywhere ===")
235 result = cache.get("user:2")
236 print(f" Result: {result}\n")
237
238 print("=== 7. Fill L2 to trigger LFU eviction ===")
239 cache.put("user:4", "Diana")
240 cache.put("user:5", "Eve")
241 # Access user:3 multiple times to increase its frequency
242 cache.get("user:3")
243 cache.get("user:3")
244 # Now add one more : LFU should evict the least frequently used
245 cache.put("user:6", "Frank")
246 print()
247
248 print("=== 8. Verify LFU kept frequently accessed key ===")
249 result = cache.get("user:3")
250 print(f" Result for user:3 (frequently accessed): {result}")
251
252 print("\nAll operations completed successfully.")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.