Stampede: Little's Law as a count of duplicate work

How many duplicate recomputes does an expiring hot entry cause, and what are the three fixes?

Little's Law says that the average number of requests in a system equals the arrival rate times the time each one spends there: L = λ · W. Apply it to an expiring entry. At the instant it expires, requests for that one key arrive at rate λ_k, and each recompute takes time W. The number of duplicate recomputes in progress is

What makes this a disaster and not just waste is feedback. Those 3,000 queries hit the store at once, which makes W longer, which makes L larger, which adds more load. If λ_k · W is above the origin's capacity, W grows without limit and the key never fills again. The trigger (one entry expiring) is gone, but the system stays down. This state is called metastable failure: a failure that keeps itself going after its cause has disappeared. It is also where genuine queueing delay, growing like 1/(1 − ρ) with utilization ρ, enters caching. It enters in the origin's response time, not in the hit-rate formula.

There are three fixes. They are exactly the three things any conflict-resolution scheme can pay with: waiting, wasted work, or weaker guarantees.

Fix 1. Coalescing: pay in waiting

One requester recomputes. All others wait on a shared promise (a placeholder for the future result). L drops to 1, and the waiters' latency becomes W.

inflight = {}                      # key -> Future, one per node

def get(key):
    v = cache.get(key)
    if v is not None:
        return v
    fut = inflight.get(key)
    if fut is None:                # I am the leader for this key
        fut = inflight[key] = Future()
        try:
            v = db.query(key)      # the one expensive call
            cache.put(key, v, ttl=TTL)
            fut.set_result(v)
        finally:
            del inflight[key]
        return v
    return fut.result()            # followers wait for the leader

The cost is a shared structure keyed by the cache key, which is a lock. That is cheap inside one process. Across nodes it needs a distributed lock, and nobody wants to pay for that. So in a 50-node fleet the honest state of practice is 50 recomputes, not one. Coalescing removes the per-node stampede and leaves the fleet-wide stampede in place.

Fix 2. Probabilistic early expiry: pay in extra work, coordinate not at all

Recompute early, with a probability that rises as the expiry time approaches. The probability is scaled by the measured recompute time δ. A request refreshes the entry when

now − δ · β · ln(rand())  ≥  expiry        # rand() is uniform in (0,1); ln(rand()) is negative

(β is a tuning constant, usually 1.) Because −ln(rand()) is positive and usually small, the test fires only rarely when the expiry is far away and more often as it approaches. Expiry becomes a random variable that fires before the deadline. The first requester that draws a large value recomputes while the old entry is still valid, and everyone else keeps getting hits.

There is no lock, no waiting and no staleness beyond the TTL. The cost is slightly more than one recompute per key per period. It beats coalescing on every axis except total work, and it works across a whole fleet with no distributed component. This is the rule that randomness replaces exhaustive bookkeeping, in its cleanest form here. One design detail is worth copying: the probability is scaled by the measured δ, so expensive entries start trying earlier. That is cost-awareness, and Making it fit finds the same idea in eviction.

Fix 3. Serve-stale-while-revalidate: pay in weakened semantics

One requester refreshes in the background. Everyone else immediately receives the expired value. Staleness now exceeds the TTL by up to W. This is the most widely used fix in practice. HTTP standardizes it as the stale-while-revalidate directive. It is the only fix that spends staleness rather than waiting or work.

The larger problem: correlated expiry

A single-key stampede is the small problem. The large one is correlated expiry. A million keys filled at the same time (by a deploy, a warm-up, or a batch load) with the same TTL expire at the same time. The result is a stampede across the whole key space, not just one key.

The fix is to jitter every TTL: use TTL = T · (1 ± j), with j ≈ 0.1 to 0.2.

import random
ttl = base_ttl * random.uniform(0.9, 1.1)    # j = 0.1

This one line applies three ideas at once. Randomness replaces coordination (no node needs to know when the others expire). The variance in expiry time is what you are buying, and correlation is what costs you. And it fixes a common wrong assumption: TTLs are assumed to be independent, but they are perfectly correlated whenever the population was filled together. (The rule here is that independence assumptions are almost never true.) It is the highest-value single line of configuration in this article.

Compression: L = λ_k · W duplicate recomputes, with feedback. Fix by waiting (coalesce), extra work (early probabilistic expiry) or staleness (serve-stale). And jitter every TTL, because a correlated population means correlated expiry.