We had a pricing endpoint that cached an expensive aggregate for 60 seconds. It was expensive enough, close to a third of a second to compute, that we absolutely did not want to run it on every request, so we cached it and moved on. Then every sixty seconds the cache entry expired, and because every app instance had cached it at roughly the same moment, they all missed at the same moment, and the whole fleet stampeded the database at once. Classic thundering herd.
To make “expensive aggregate” concrete: it was the kind of pricing rollup that blends a few million rows into one number per category. Something along these lines, a couple of joins and an aggregate over the last hour of activity:
SELECT p.category_id,
AVG(c.competitor_price) AS market_price,
SUM(oi.qty) AS demand_last_hour,
percentile_cont(0.5) WITHIN GROUP (ORDER BY c.competitor_price) AS median
FROM products p
JOIN competitor_prices c ON c.product_id = p.id
JOIN order_items oi ON oi.product_id = p.id
AND oi.created_at > now() - interval '1 hour'
WHERE p.region = $1
GROUP BY p.category_id;
Nothing pathological, just enough joins, rows, and a percentile that the planner has to sort, to land around 300 ms. Fine to run occasionally, not fine to run on every request, which is exactly why it was cached.
The fix looked obvious. Put a lock around the recompute so only one request does the work and everyone else waits for it. We shipped SET NX as a recompute lock, watched the database load spike flatten out, and felt good about it. The p99 did not get better. And a couple of weeks later, when a pod got killed mid-recompute during a deploy, the p99 didn’t just stay bad, it went to three and a half seconds.
The problem
A hot cached value expires, every app instance misses at the same instant, and the whole fleet stampedes the database at once. The obvious fix is a lock so only one request recomputes, and it doesn’t work the way you’d hope: the lock leaves the user-facing latency exactly where it was, and the day a lock holder dies mid-recompute it stalls everyone for the lock’s full TTL. This walks through the herd, the failed lock fix, and the thing that actually works, all measured.
I rebuilt the whole thing to understand why the obvious fix was the wrong one. 64 concurrent workers hammering one hot key, a recompute that takes about 300 ms, a 2-second TTL to keep the run short, and four strategies measured back to back.
The herd, to have a baseline
With a plain TTL and no coordination, the key expires, all 64 workers miss at the same instant, and all 64 recompute. Between expiries every read is a cache hit and comes back in well under a millisecond. On the expiry, everyone eats a full recompute. The p99 came out at 302 ms, and it’s a sawtooth: near zero for two seconds, then a spike every time the key turns over. The database, meanwhile, takes 64 recomputes in a single burst each cycle, which is the load spike we actually set out to kill.
The lock, which didn’t do what we thought
So we did the obvious thing. One request wins a lock and recomputes, everyone else waits for it and reads the fresh value:
def get_price(r):
v = r.get(KEY)
if v is not None:
return v
if r.set(KEY + ":lock", "1", nx=True, ex=3): # I won, I recompute
v = recompute()
r.set(KEY, v, px=2000)
r.delete(KEY + ":lock")
return v
while True: # I lost, I wait for the winner
v = r.get(KEY)
if v is not None:
return v
time.sleep(0.01)
The database load did drop, exactly one recompute per cycle instead of 64. But look at what happened to the latency: p99 came out at 286 ms, basically identical to the herd’s 302. Of course it did. Every waiter is still blocked for the length of one recompute, the only thing that changed is they’re waiting on a lock holder instead of on their own query. We didn’t remove the 300 ms wait, we just elected one process to do the work and made everyone else queue behind it. The lock reduced database load and did nothing at all for the thing users actually feel.
p99 over time: the lock (our fix) vs probabilistic refresh
And then there’s the failure we didn’t think about until it happened in production. The lock holder is a single process, and processes die. If the holder gets killed after it takes the lock but before it writes the value, the lock just sits there until its own TTL runs out, and every single waiter blocks that entire time. I modeled it by killing the holder mid-recompute one time in five, and the tail went exactly where you’d expect:
Worst stall in the run (max latency)
3,516 ms. The lock took a load problem and handed us a latency problem and a single point of failure, and left the p99 exactly where it was.
What actually fixed it: refresh before anyone’s waiting
The real problem was never “too many processes recompute at once.” It was “the recompute happens at the exact moment a request needs the value, so somebody always waits for it.” So stop waiting for expiry. Refresh the value a little before it expires, in the background, while the cached copy is still perfectly good to serve.
The trick is deciding who refreshes and when without coordinating. Each reader, on every hit, rolls a random number and refreshes early if it comes up. The closer the value is to expiring, and the more expensive it was to compute last time, the higher the chance any given reader volunteers. So exactly one reader (near enough) tends to refresh ahead of the crowd, and it does it in the background, so its own request doesn’t block either:
def get_price(r):
raw = r.get(KEY)
if raw is None: # genuinely cold, rare under load
return recompute_and_store(r)
d = json.loads(raw) # {value, delta (last compute time), exp (expiry)}
if time.time() - d["delta"] * BETA * math.log(random.random()) >= d["exp"]:
background_refresh(r) # volunteer, but don't wait for it
return d["value"] # serve the still-valid value now
That delta * log(random()) term is the whole idea: it’s a random amount of time, weighted by how long the recompute takes, that pulls the effective refresh moment earlier. A reader that happens to roll a large value refreshes well ahead of expiry; most readers roll small and just serve the cache. The key never actually goes cold under load, because someone always tops it up first.
The p99 came out at 2.3 ms. The sawtooth is gone completely, you can see it flat along the bottom of the chart above. The database still only sees about one recompute per cycle, same as the lock. Nobody blocks, nobody stampedes, and there’s no holder whose death takes everyone down, because the refresh is best-effort and the cache is never actually empty when it happens.
The other half: synchronized expiries manufacture the herd
There’s a second bug hiding underneath all of this, and it’s the reason the herd was so sharp in the first place. Every instance cached the value at about the same time with the same TTL, so every instance’s copy expired at the same time. Synchronized expiry is what turns “a cache miss” into “sixty-four simultaneous cache misses.”
Jitter fixes that. If you spread the TTLs out by a random amount, the expiries desynchronize and the miss, if you get one at all, is spread over time instead of landing all at once. I set 300 keys with the same TTL and then with a TTL jittered by plus or minus fifty percent, and counted how many expired inside the same quarter-second window:
Keys expiring in the same window (herd size)
All 300 at once became at most 47. Probabilistic refresh handles the single hot key; jitter handles the fact that lots of keys were set to die together.
Stuff worth remembering
- A recompute lock does not fix the latency of a stampede. It serializes it. Every waiter still blocks for one recompute, so your p99 stays about where it was; all you actually bought was lower database load. If load was your problem the lock helps, but if latency was your problem it doesn’t, and it’s easy to conflate the two.
- The lock also adds a single point of failure. When the holder dies between taking the lock and writing the value, everyone waits the full lock TTL. In my run that was a 3,516 ms stall out of a workload whose p99 was otherwise 300 ms.
- Probabilistic early recomputation is the fix for the latency. One reader refreshes ahead of expiry in the background, so the value is never cold when a request arrives and nobody blocks. It sits right on top of a normal cache read, a few lines, no coordination.
- Jitter your TTLs. Seeding many instances or many keys with the same absolute expiry is what builds the herd; a little randomness in the TTL stops them from expiring in lockstep.
- These are laptop numbers demonstrating the mechanism, the load generator and the four strategies are in the repo. The milliseconds are from my machine; the shapes hold anywhere.
The takeaway
Reaching for a lock when a herd is trampling your database is a reasonable instinct, it’s just aimed at the wrong thing. It cuts the database load, which is real, but it leaves the latency alone, and the latency is what users actually felt. The recompute you want isn’t the one you carefully let a single process run while everyone else waits, it’s one that already finished in the background before the request even showed up.
Comments