Cache Stampedes, Thundering Herds, Hot Keys, Negative Caching, and Jittered Expiry

1. A cache stampede is correlated miss amplification

AtlasMart's homepage fragment is requested by thousands of clients per second. If one hot key expires and 20 application workers observe the miss together, each can launch the same database query/recomputation. The cache normally reduces origin work; at the expiry boundary it can briefly multiply it.

A cache stampede or thundering herd is this synchronized regeneration pressure. A hot key concentrates traffic on one logical item or shard. The dangerous metric is not only cache hit ratio but the number of origin operations caused by one logical cache miss episode.

2. Request coalescing collapses identical in-flight work

With per-key single-flight, the first caller becomes the loader and later callers wait for the same result instead of performing duplicate source reads. Correct implementations recheck cache state after acquiring leadership, bound waiter time, and release failed in-flight state so recovery can proceed.

3. Desynchronize and precompute carefully

TTL jitter adds controlled randomness so many keys do not expire on the same second. Probabilistic early refresh lets some requests refresh before expiry; Vattani, Chierichetti, and Lowenstein analyze this cache-stampede problem formally. Negative caching stores a short-lived “not found” result so repeated requests for a nonexistent SKU do not repeatedly hit the database. Negative entries must be short-lived or invalidated when the object appears.

Hot-key replication can spread read load across several cache nodes, but version freshness and invalidation must still be defined. Rate limiting protects the source when all cache defenses fail.

4. Refresh locks, stale serving, and fencing

A lock can keep two refreshers from rebuilding the same key, but a lease can expire while a slow worker is still running. If a faster worker obtains a newer lease and publishes generation 8, the stale generation-7 worker must not overwrite it later. Version checks or fencing tokens make downstream state reject the stale publisher. Serving slightly stale data while one worker refreshes can reduce tail latency, but only for data whose staleness policy permits it.

5. AtlasMart lab: collapse the herd and expose the lock risk

import random

clients = 20
print("SYNCHRONIZED EXPIRY")
origin_loads_naive = clients
origin_loads_singleflight = 1
print("clients:", clients, "naive origin loads:", origin_loads_naive)
print("with per-key single-flight:", origin_loads_singleflight)

print("\nTTL JITTER ACROSS 20 KEYS")
rng = random.Random(19)
expiries = [60 + rng.randint(-10, 10) for _ in range(20)]
hist = {t:expiries.count(t) for t in sorted(set(expiries))}
print("expiry histogram:", hist)
print("largest synchronized bucket:", max(hist.values()))

print("\nNEGATIVE CACHE")
requests_for_missing = 10
loads_without_negative = requests_for_missing
loads_with_negative = 1
print("missing sku requests:", requests_for_missing)
print("origin loads without/with negative cache:", loads_without_negative, loads_with_negative)

print("\nHOT-KEY REPLICATION")
requests=100
replicas=4
per_replica=[0]*replicas
for i in range(requests): per_replica[i % replicas]+=1
print("front-cache request distribution:", per_replica, "max:", max(per_replica))

print("\nSTALE REFRESHER + FENCING")
accepted_generation=8
slow_worker_token=7
fast_worker_token=8
print("fast worker publishes generation", fast_worker_token)
print("slow stale publish accepted without fence: True  <- wrong")
print("slow stale publish accepted with fence:", slow_worker_token >= accepted_generation)
print("lesson: collapse duplicate work, desynchronize expiry, and fence stale refreshers")

6. Deliberately wrong approach: synchronize every key to the same TTL boundary

Batch-loading 100,000 keys at deploy time with identical TTLs can schedule the next outage. Add jitter based on workload and freshness constraints, warm critical keys before cutover, cap concurrent origin work, and verify behavior after whole-cache loss—not just one-key expiry.

7. Production judgment and bridge

Measure origin amplification per miss, concurrent regenerations per key, lock waiters, refresh duration, stale-serving age, negative-cache hit rate, hot-key QPS, and backend saturation. Load-test synchronized expiry and total cache loss. Do not negative-cache authorization failures across users, and scope single-flight keys by all response-varying dimensions such as tenant, locale, permissions, and representation.

The final lesson asks the architectural question underneath every mitigation: which AtlasMart facts may disappear, which must survive, and exactly how derived state will be reconstructed?