Request Coalescing and Probabilistic Early Expiration

A cache under steady load is a filter: the source sees a small fraction of the reads. That fraction is not constant. It concentrates at the moments entries die, and if the entry belongs to a key that thousands of requests per second are reading, the filter opens all at once. The source then receives not one read but every read that would have hit, in the space of the time it takes the first one to complete. The effect compounds because the source is now slower under that burst, which lengthens the window during which more requests miss.

The defences work at two different points: collapse concurrent misses into one load, and avoid the simultaneous expiry that creates the burst in the first place.

The shape of the burst

Suppose a key is read at rate R and its entry expires. Every request arriving during the load’s latency L misses and starts its own load. The number of simultaneous source reads is approximately R × L, capped by concurrency limits. If R is 20,000 reads per second and L is 10 milliseconds, the source sees about 200 concurrent reads for one key, and its own increased latency raises L, which raises the count again. The burst is self-reinforcing until the first load completes and populates the entry.

Two variables are available: reduce R × L by shortening L, or multiply it by a factor near zero by ensuring only one load happens. The second is cheaper, because L is a property of the source and the network.

Single flight: one loader per key

The minimal mechanism is a table of in-flight loads keyed by cache key, guarded by a mutex. The first caller for a missing key becomes the loader; later callers wait on the same result. When the loader finishes, it stores the value, closes the entry, and wakes the waiters.

type flight struct {
    done chan struct{}
    val  []byte
    err  error
}

type group struct {
    mu sync.Mutex
    m  map[string]*flight
}

func (g *group) Do(key string, load func() ([]byte, error)) (val []byte, err error) {
    g.mu.Lock()
    if f, ok := g.m[key]; ok {
        g.mu.Unlock()
        <-f.done
        return f.val, f.err
    }
    f := &flight{done: make(chan struct{})}
    g.m[key] = f
    g.mu.Unlock()

    defer func() {
        if r := recover(); r != nil {
            val, err = nil, fmt.Errorf("loader panicked: %v", r)
        }
        f.val, f.err = val, err
        g.mu.Lock()
        delete(g.m, key)
        g.mu.Unlock()
        close(f.done)      // publishes the result to every waiter
    }()
    return load()
}

The subtleties are in the error and cancellation paths. If the loader returns an error, all waiters receive the same error, which is usually correct — retrying individually would restore the burst. A panic in the loader needs the same treatment: without the deferred cleanup, the entry stays in the map and every later caller blocks on a channel that will never close. If the loader’s caller disconnects, its context cancellation must not cancel the shared load for everyone else; the load has to run under a context that outlives the initiating request, with its own deadline. And the load must not be able to block forever: a waiter with a request deadline should give up and return a degraded answer rather than hang on a load that has no timeout.

Go’s golang.org/x/sync/singleflight provides this structure, including a Forget method for the case where a load result should not be shared. The same pattern appears in Java caches as the guarantee that a mapping function is applied at most once per key concurrently.

Single flight is per process. With a hundred application instances, it reduces the burst by a factor of a hundred, not to one. The residual is still a hundred concurrent loads against the source, which is often acceptable and sometimes is not. Reducing it further requires coordination outside the process, and that coordination is where distributed locking enters — with all of its failure modes. A distributed lock held while loading converts a lock timeout into an outage; a lock without a lease expiry converts a crashed holder into a permanently cold key. The practical middle ground is a soft lock: attempt to acquire with a short timeout, and on failure wait briefly and re-check the cache, then load anyway if the entry is still missing. The lock becomes an optimisation that can be ignored rather than a gate that can deadlock.

Early recomputation

The second defence attacks the moment of expiry. If entries for a hot key could be recomputed before they expire, the deadline would never be reached by a live entry, and the burst would never form. Deterministic early refresh — refresh at 90% of the TTL — merely moves the cliff: all instances refresh at the same instant relative to the entry’s creation, and the result is a smaller but equally synchronised burst. A scheduled version of it also refreshes entries that nobody reads, which wastes source capacity on cold keys.

Probabilistic early expiration avoids both problems by making each reader independently decide whether to refresh now. The XFetch algorithm, published as “Optimal Probabilistic Cache Stampede Prevention”, computes a recomputation time by subtracting a random exponential term from the deadline:

refresh if: now - delta * beta * ln(U) >= expiry

Here delta is the measured or estimated time to recompute the value, beta is a tuning constant, U is uniform in (0, 1), and expiry is the absolute deadline. Because ln(U) is negative and unbounded as U approaches zero, the subtraction can push the effective refresh time arbitrarily far before the deadline, with probability decreasing exponentially with distance. More importantly, the decision is per read: a key read a thousand times per second gets a thousand independent draws per second, so the refresh happens early with near-certainty; a key read once a minute almost always waits for its deadline. Popularity, not wall-clock, drives the refresh.

The delta term is what makes the distribution adaptive. A value that takes 200 milliseconds to compute should be refreshed earlier, in absolute terms, than one that takes 2 milliseconds, because the recomputation itself must finish before the deadline. Systems that cannot measure delta use a fixed estimate, which is less accurate but preserves the property that refresh is spread over time rather than concentrated at one instant.

Serving stale while refreshing

A third approach sidesteps the burst by decoupling the response from the refresh: return the expired entry immediately and start a background refresh, marking the entry as stale in progress so that only one refresh starts. HTTP captures this in stale-while-revalidate, defined in RFC 5861, which lets a shared cache serve a stale response for a bounded window while it revalidates. Application caches implement the same idea with a soft TTL and a hard TTL: reads between the two serve the old value and trigger an asynchronous reload; reads after the hard TTL block or fail.

The trade is explicit staleness for latency. It works when the value is expensive to compute, read far more often than it changes, and a slightly old answer is acceptable. It fails when the caller needs read-your-writes, because the background refresh races the writer’s invalidation — the same interleaving described in invalidation by deletion and versioned keys. A refresh that started before a write can complete after the invalidation and repopulate the old value. Version stamps in the entry, or a refresh that re-reads the version after loading, close that window.

Where the burst goes when the key is gone

Coalescing depends on the key being in the cache at all. If the cache is restarted, or a whole shard is lost, every key is a miss simultaneously and single flight operates per key, which is the right granularity for correctness but does nothing for the aggregate load. The same applies to a mass invalidation after a deploy that changes the serialization format: every entry is unreadable, and the source sees a full working set at once.

Two mitigations exist and both are about pacing rather than collapsing. The first is warming: populate the hottest keys before the instance accepts traffic, driven by a recorded key list or by replaying recent queries. The second is admission control at the source boundary — a concurrency limit on loads, with excess requests queued or served stale — so that the source degrades in a controlled way rather than being asked for its entire working set at once. Neither is a cache mechanism strictly, but both determine whether the cache’s failure is survivable, which is the subject of hit ratio arithmetic and working-set sizing.

The residual window

Even with coalescing and early refresh, a narrow window remains: the first load after a cold start has no value to serve and no stale copy to fall back on. For keys where that window must not be visible, the cache is the wrong mechanism for the guarantee, and the answer lives in the source’s read path — a read replica, a materialised view, or a precomputed document that is written ahead of the request. The cache can then be a latency optimisation rather than a correctness dependency.