Cache Consistency, Invalidation, and Stampede Prevention TODO
Concept
A cache starts carrying a consistency problem the moment the source of truth and the copy diverge; policies broadly split into expiration-based (TTL) and invalidation-based (delete or update on write). Updating the cache on the write path can let concurrent writes land out of order and leave a stale value behind, so deleting is usually safer than updating. A cache stampede happens when a popular key expires and many requests hit the origin simultaneously, which can momentarily take the origin down. The countermeasures are single-flight (letting only one request query the origin), adding random jitter to expiration times, proactive early recomputation before expiry, and stale-while-revalidate (serving the stale value briefly while a refresh is in flight). Whichever policy you pick, you first have to define 'how much staleness is acceptable' before a choice is even possible.
A large share of outages don't come from missing a cache — they come from the cache emptying all at once and the backend collapsing under the exposed load.
Code & Formula
# 캐시 일관성·무효화·스탬피드 방지 — TTL 만료 순간 다수 요청이 몰리는 스탬피드를
# single-flight(락)로 한 요청만 원본을 조회하게 막는 것을 시연한다.
import time
import threading
origin_calls = 0
origin_lock = threading.Lock()
def slow_origin_fetch(key):
global origin_calls
with origin_lock:
origin_calls += 1
time.sleep(0.05) # 원본 DB/서비스 호출을 흉내
return f"value-for-{key}"
class SingleFlightCache:
def __init__(self):
self.store = {} # key -> (value, expires_at)
self.inflight = {} # key -> threading.Event (동시 요청 합류용)
self.lock = threading.Lock()
def get(self, key, ttl=1.0):
with self.lock:
entry = self.store.get(key)
if entry and entry[1] > time.time():
return entry[0]
if key in self.inflight:
event = self.inflight[key]
else:
event = threading.Event()
self.inflight[key] = event
event = None # 이 스레드가 원본을 조회할 담당자
if event is not None:
event.wait()
return self.store[key][0]
value = slow_origin_fetch(key)
with self.lock:
self.store[key] = (value, time.time() + ttl)
waiter = self.inflight.pop(key)
waiter.set()
return value
cache = SingleFlightCache()
results = []
def worker():
results.append(cache.get("hot-key"))
threads = [threading.Thread(target=worker) for _ in range(20)]
for t in threads: t.start()
for t in threads: t.join()
print("concurrent requests:", len(threads))
print("origin fetches actually made:", origin_calls) # 1 이어야 stampede 방지 성공
print("all results identical:", len(set(results)) == 1)
docs/code/algorithms/algorithms-79.py
Exercise
Build a load test that hits the same key concurrently, then compare origin query counts and p99 latency between a plain TTL cache and one using single-flight.
Practical Connection
Values like prices, order-book snapshots, or oracle responses — where the origin is expensive and access is concentrated — carry the highest stampede risk, and here 'acceptable staleness' maps directly to the price accuracy users actually see.
If you study this on a given day, add a note link and a ✅ to this line in the source curriculum (docs/knowledge/dev-100-curriculum.md) and this spot will lead straight to the note body. You can also write directly on this page — but regenerating overwrites it, so it's safer to keep anything you want to save as markdown under docs/algorithms/.