XFetch: coordination-free probabilistic early expiration

A lock-based mitigation adds a Redis round-trip to every cache miss — fine for ultra-hot keys, wasteful for the 99% of keys that rarely collide. XFetch achieves the same “only one rebuild per TTL window” guarantee with zero coordination and zero network cost.

The decision rule

Each cache read evaluates:

should_refresh = (-beta * delta * ln(rand())) >= time_to_expire

Where:

• delta — typical rebuild duration in seconds (e.g., 0.4)
• beta — tuning constant, default 1.0
• rand() — uniform random in (0, 1)
• time_to_expire — seconds until the current TTL fires

As time_to_expire approaches 0 (close to expiry), the threshold on the left (-beta * delta * ln(rand())) is increasingly likely to exceed it. Far from expiry the probability is near zero. Near expiry it climbs fast.

Result: the cache key gets refreshed before it expires. The first request to fire the probabilistic threshold runs the rebuild while the existing cached value is still served to everyone else. By the time TTL would have fired, the cache already has a fresh value.

The exact numbers depend on the distribution of reads, but the trend is clear: the probability concentrates in the final few seconds before expiry.

Expected refreshes per TTL window = 1

The key property Vattani et al. prove: integrating the probability over the TTL window gives exactly one expected early refresh, regardless of fleet size or read rate. A fleet of 100 nodes reading the key 1,000 times per second does not produce 100,000 early refreshes — it still produces approximately 1. The exponential distribution has the property that the minimum of N independent draws is also exponential with rate N × lambda. As fleet size grows, the earliest reader fires the threshold sooner, but the total count remains ~1.

When XFetch works and when it does not

XFetch requires reads to be frequent enough that “some reader” hits the probabilistic threshold before TTL. The algorithm is transparent when reads happen, say, every 100 ms over a 60-second TTL — many chances to fire the threshold in the final seconds.

Failure case: cold or sporadic keys. A key read once per 30 seconds with TTL=60 s may have only one or two reads in the entire “early refresh” window (the final ~1 s). With small N, the probability of missing the threshold entirely is significant. The key expires normally and stampedes.

Rule of thumb: use XFetch on keys with ≥ 10 reads per expected-rebuild-duration window before TTL. For colder keys, fall back to a lock or SWR.

Tuning beta

beta controls how early the refresh window opens:

• beta < 1.0: earlier refreshes, wider window, more wasted early rebuilds on cold keys. Use when rebuild cost is very low and staleness must be minimised.
• beta = 1.0 (default): the window opens when time_to_expire ≈ delta. Balanced.
• beta > 1.0: later refreshes, narrower window, higher risk of missing the threshold on cold keys. Use only when rebuild is expensive and early staleness must be avoided.