1"""Chapter 12 practice (Caching: the basics). Extends the approved v4 solution:
2- TTLCache with LRU eviction and a hit-rate counter (Level 3, from v4)
3- TTL jitter, write-through / write-back / write-around, LRU vs LFU
4- the invalidation race: delete-then-update vs update-then-delete (Level 4, from v4)
5Standard library only, with a fake clock so everything is deterministic.
6Run: python3 ch12_caching.py"""
7import random
8from collections import Counter, OrderedDict
9
10
11class Clock:
12 def __init__(self):
13 self.t = 0.0
14
15 def __call__(self):
16 return self.t
17
18
19class TTLCache:
20 """A small in-memory cache with a size limit (LRU eviction) and expiry (TTL)."""
21
22 def __init__(self, capacity, ttl_seconds, clock):
23 self.capacity, self.ttl, self.clock = capacity, ttl_seconds, clock
24 self.items = OrderedDict() # key -> (value, expires_at), oldest-used first
25 self.hits = self.misses = 0
26
27 def get(self, key):
28 entry = self.items.get(key)
29 if entry is None or entry[1] <= self.clock():
30 self.items.pop(key, None) # expired counts as a miss
31 self.misses += 1
32 return None
33 self.items.move_to_end(key) # mark as most recently used
34 self.hits += 1
35 return entry[0]
36
37 def set(self, key, value, ttl=None):
38 self.items[key] = (value, self.clock() + (self.ttl if ttl is None else ttl))
39 self.items.move_to_end(key)
40 if len(self.items) > self.capacity:
41 self.items.popitem(last=False) # evict the least recently used
42
43 def delete(self, key):
44 self.items.pop(key, None)
45
46 def hit_rate(self):
47 total = self.hits + self.misses
48 return self.hits / total if total else 0.0
49
50
51class LFUCache:
52 """Evicts the key used the fewest times (ties: the oldest)."""
53
54 def __init__(self, capacity):
55 self.capacity = capacity
56 self.items, self.uses, self.order, self.tick = {}, Counter(), {}, 0
57
58 def get(self, key):
59 if key in self.items:
60 self.uses[key] += 1
61 return self.items[key]
62 return None
63
64 def set(self, key, value):
65 if key not in self.items and len(self.items) >= self.capacity:
66 victim = min(self.items, key=lambda k: (self.uses[k], self.order[k]))
67 del self.items[victim], self.order[victim]
68 self.uses.pop(victim)
69 self.tick += 1
70 self.items[key] = value
71 self.order.setdefault(key, self.tick)
72 self.uses[key] += 1
73
74
75class FakeDB:
76 def __init__(self, data):
77 self.data, self.reads, self.writes = dict(data), 0, 0
78
79 def get(self, k):
80 self.reads += 1
81 return self.data[k]
82
83 def set(self, k, v):
84 self.writes += 1
85 self.data[k] = v
86
87
88# ---- Read strategy: cache-aside --------------------------------------------------------------
89
90def cache_aside_get(cache, db, key):
91 value = cache.get(key)
92 if value is None:
93 value = db.get(key)
94 cache.set(key, value)
95 return value
96
97
98# ---- Write strategies -----------------------------------------------------------------------
99
100def write_through(cache, db, key, value):
101 db.set(key, value) # write the truth...
102 cache.set(key, value) # ...and the copy, together
103
104
105class WriteBack:
106 """Write to the cache now; flush to the database later. Fast, but a crash loses
107 whatever hasn't been flushed."""
108
109 def __init__(self, cache, db):
110 self.cache, self.db, self.dirty = cache, db, set()
111
112 def write(self, key, value):
113 self.cache.set(key, value)
114 self.dirty.add(key)
115
116 def flush(self):
117 for k in sorted(self.dirty):
118 self.db.set(k, self.cache.items[k][0])
119 self.dirty.clear()
120
121 def crash(self):
122 self.cache.items.clear()
123 lost = len(self.dirty)
124 self.dirty.clear()
125 return lost
126
127
128def write_around(cache, db, key, value):
129 db.set(key, value) # write only the truth...
130 cache.delete(key) # ...and drop any old copy; the next read fills it
131
132
133# ---- TTL jitter ----------------------------------------------------------------------------------
134
135def ttl_with_jitter(base, spread, rng):
136 return base + rng.uniform(-spread, spread)
137
138
139def busiest_second(expiry_times):
140 return max(Counter(int(t) for t in expiry_times).values())
141
142
143# ---- The invalidation race (Level 4, from v4) ----------------------------------------------------
144
145def race(order):
146 """Simulates: admin changes milk 52 -> 56 (the DB update takes a while) while a user reads.
147 order = 'delete_first' (buggy) or 'update_first' (fixed). Returns what the cache holds after."""
148 clock = Clock()
149 cache = TTLCache(10, 600, clock)
150 db = FakeDB({"milk": 52})
151 cache.set("milk", 52)
152 if order == "delete_first":
153 cache.delete("milk") # 1. admin deletes the copy
154 user_sees = cache_aside_get(cache, db, "milk") # 2. user misses, reads OLD 52, caches it
155 db.set("milk", 56) # 3. admin's slow update finally lands
156 else:
157 db.set("milk", 56) # 1. admin updates the truth
158 cache.delete("milk") # 2. then deletes the copy
159 user_sees = cache_aside_get(cache, db, "milk") # 3. user misses, reads NEW 56
160 return cache.get("milk"), user_sees
161
162
163def run_checks():
164 clock = Clock()
165 db = FakeDB({"milk": 52, "bread": 40, "eggs": 70})
166 cache = TTLCache(capacity=2, ttl_seconds=60, clock=clock)
167
168 # 1. Repeated reads: only the first goes to the database.
169 for _ in range(5):
170 cache_aside_get(cache, db, "milk")
171 assert db.reads == 1 and cache.hit_rate() == 0.8
172
173 # 2. LRU: capacity 2, so a third key evicts the least recently used.
174 cache_aside_get(cache, db, "bread")
175 cache_aside_get(cache, db, "milk") # milk now most recent
176 cache_aside_get(cache, db, "eggs") # evicts bread
177 assert "bread" not in cache.items and "milk" in cache.items
178
179 # 3. TTL: after expiry, a read is a miss again.
180 before = db.reads
181 clock.t += 61
182 cache_aside_get(cache, db, "milk")
183 assert db.reads == before + 1
184
185 # 4. Write strategies
186 c2, d2 = TTLCache(10, 60, clock), FakeDB({"milk": 52})
187 write_through(c2, d2, "milk", 56)
188 assert d2.data["milk"] == 56 and c2.get("milk") == 56
189
190 c3, d3 = TTLCache(10, 60, clock), FakeDB({"milk": 52, "eggs": 70})
191 wb = WriteBack(c3, d3)
192 wb.write("milk", 56); wb.write("eggs", 72)
193 assert d3.writes == 0 # nothing in the database yet
194 wb.flush()
195 assert d3.data == {"milk": 56, "eggs": 72} and d3.writes == 2
196 wb.write("milk", 58)
197 assert wb.crash() == 1 and d3.data["milk"] == 56 # unflushed write lost
198
199 c4, d4 = TTLCache(10, 60, clock), FakeDB({"milk": 52})
200 c4.set("milk", 52)
201 write_around(c4, d4, "milk", 56)
202 assert c4.get("milk") is None and cache_aside_get(c4, d4, "milk") == 56
203
204 # 5. Jitter: 10,000 keys cached at the same moment with a fixed 300 s TTL all expire in
205 # the same second; with +/- 30 s of jitter they spread across about 60 seconds.
206 rng = random.Random(4)
207 fixed = [300.0] * 10_000
208 jittered = [ttl_with_jitter(300, 30, rng) for _ in range(10_000)]
209 assert busiest_second(fixed) == 10_000
210 assert busiest_second(jittered) < 300
211
212 # 6. LRU vs LFU when a one-off scan passes through.
213 hot = ["milk", "bread"] * 50
214 scan = [f"rare-{i}" for i in range(5)]
215 lru, lfu = TTLCache(3, 10_000, clock), LFUCache(3)
216 for k in hot + scan:
217 if lru.get(k) is None:
218 lru.set(k, 1)
219 if lfu.get(k) is None:
220 lfu.set(k, 1)
221 assert "milk" not in lru.items and "bread" not in lru.items # scan pushed the hot keys out
222 assert "milk" in lfu.items and "bread" in lfu.items # popular keys survive
223
224 # 7. Level 4: the race
225 held_bad, _ = race("delete_first")
226 held_good, user_good = race("update_first")
227 assert held_bad == 52 and held_good == 56 and user_good == 56
228
229 print(f"All checks pass. Busiest second without jitter: {busiest_second(fixed):,} expiries; "
230 f"with jitter: {busiest_second(jittered)}. Race: delete-first leaves {held_bad} cached.")
231
232
233if __name__ == "__main__":
234 run_checks()