Explain probabilistic early expiration (the XFetch algorithm) as a cache-refresh strategy: what extra data must be stored alongside the cached value, and why does it avoid needing a lock at all?

## The insight Mutexes and stale-serving are reactions to a miss. XFetch — from the paper "Optimal Probabilistic Cache Stampede Prevention" — removes the miss instead. If somebody refreshes the entry *just before* it would expire, no request ever sees an empty cache, so there is nothing to stampede on and nothing to serialise. The trick is deciding *who* refreshes early without any coordination. XFetch does it with a per-reader random draw whose probability rises as expiry nears. ## What you store The cached payload carries three fields (in a Redis hash, or serialized into one string): - `value` — the cached data; - `delta` — how long the most recent recompute took, in the same time unit as everything else; - `expiry` — the **logical** freshness deadline as an absolute timestamp. The Redis key gets a **physical** TTL somewhat longer than `expiry` (say expiry + a grace window), so the entry is still present if the early refresh does not happen. Physical TTL is the backstop; logical expiry is the policy. ## The decision rule On every read: ``` now - delta * beta * log(random()) >= expiry -> recompute ``` with `random()` uniform on (0,1) and `log` the natural logarithm. Why this works: - `log(random())` is always negative, so `-delta*beta*log(random())` is a positive random quantity. The reader behaves as if the current time were pushed forward by that amount. - Its distribution is exponential with mean `delta*beta`. Most draws are small; occasionally one is large. - Therefore, when `now` is far below `expiry`, only an unusually large draw triggers a refresh — refreshes are rare. As `now` climbs toward `expiry`, the required draw shrinks and the trigger probability rises smoothly toward certainty. - `delta` scales the whole thing: an entry that takes 2 seconds to rebuild starts drawing meaningfully earlier than one that takes 20 ms. That is the elegant part — the algorithm automatically gives expensive values more lead time, exactly where a stampede would hurt most. - `beta` tunes eagerness. `beta = 1` is the default; `beta > 1` refreshes earlier (more redundant refreshes, more safety margin); `beta < 1` refreshes later (fewer refreshes, higher risk of an actual miss); `beta = 0` disables early refresh entirely. ## Why no lock is needed Each reader decides alone, using only data it already fetched. There is no shared state to contend on, no round trip to acquire anything, and no waiting. Because the winner refreshes *before* the logical expiry and the key is still physically present, every concurrent reader gets a valid value and returns immediately. The rare case of two readers refreshing simultaneously costs one extra recompute — nothing breaks. Contrast with a mutex, which activates *after* a miss: someone has already found an empty cache, so somebody must wait, serve stale, or degrade. XFetch's window of vulnerability is smaller by construction. ## The real costs and limits - **Metadata and measurement.** You must time the recompute and store `delta` and `expiry` with the value. Retro-fitting this onto an existing cache means changing the serialization format for every cached entry. - **Traffic dependence.** The dice are rolled on reads. A key read once a minute is unlikely to roll a trigger before expiry, so it just expires and takes the ordinary miss path. XFetch protects *hot* entries, which is exactly the population that stampedes — but do not expect it to make cold-key misses disappear. - **Refresh latency lands on a real request.** The reader that triggers pays the recompute time. Under low-latency SLOs, do the refresh **asynchronously**: return the still-valid cached value to the caller immediately and rebuild on a background task or worker. Then the algorithm decides *when* to refresh and the request path never slows down at all. - **Not a defence against a cold cache.** After a flush or restart there is no value, so there is no `delta` and no `expiry` to reason about; you are back to plain misses and need bounded recompute concurrency. - **Duplicate refreshes are possible.** Rare, but real. If duplicates are expensive, wrap the recompute in a cheap `SET lock:<key> <token> NX PX <ttl>` — the combination is common: XFetch decides *when*, the mutex ensures *one*. - **`delta` must be honest.** Store the measured duration of the last successful recompute, not a hard-coded guess. If the source of truth degrades, `delta` rises automatically and refreshes start earlier — a pleasant self-tuning property, but it also means an anomalous slow rebuild makes the entry refresh aggressively for a while. ## When to reach for it Good fit: a bounded set of expensive, frequently-read entries where you control the serialization format and can afford background refresh — dashboards, aggregates, recommendation payloads, rendered fragments. Poor fit: a huge keyspace of cheap entries (the metadata overhead and complexity are not worth it), or systems where the miss path must be safe for cold-cache scenarios anyway (then invest in stale-serving plus admission control first). Many teams reach for stale-while-revalidate instead, which achieves a similar "nobody ever waits" property with simpler bookkeeping. The distinguishing benefit of XFetch is that callers never receive stale data at all — the refresh happens while the value is still fresh.