Implementing Probabilistic Early Recomputation in Python

A single hot key — a rendered homepage, an expensive aggregate, a permissions snapshot — sits behind thousands of concurrent readers. When its TTL fires, every one of those readers misses at the same instant and races to recompute the value against your primary database, and the resulting cache stampede can knock the origin over precisely when traffic is heaviest. Probabilistic early recomputation — the XFetch algorithm from Vattani, Chierichetti, and Lowenstein — removes the wall entirely: instead of every reader waiting for a hard expiry, each read rolls a weighted die that makes it exponentially more likely to volunteer for an early refresh as expiry approaches. In practice one lucky request recomputes the value slightly early, resets the entry, and every other reader keeps hitting a warm cache. This page implements XFetch end to end in redis-py 5.x against Redis 7.x, stores the state it needs in a single hash, and backs the whole scheme with a short jittered TTL so a missed roll still self-heals.

# Prerequisites

• Redis 7.x reachable via redis-cli and from your application host.
• redis-py 5.x on Python 3.10+ (pip install "redis>=5,<6"); examples use the redis.asyncio client.
• A single expensive recompute function — a database aggregate, an API call, a template render — whose cost you can measure.
• A read path that already follows cache-aside: the application, not a proxy, is responsible for repopulating the key on a miss.
• Familiarity with how a jittered TTL bounds staleness — XFetch complements it rather than replacing it.

# Step-by-Step Implementation

# 1. Model the cache entry as a hash

XFetch needs three fields per key — the payload, the measured recompute cost delta, and the absolute expiry timestamp — so store them together in a Redis hash instead of a bare string, which keeps the algorithm's inputs atomic with the value they describe.

import time
import redis.asyncio as redis

client = redis.Redis(host="localhost", port=6379, decode_responses=True)


async def store_entry(key: str, value: str, delta: float, ttl: int) -> None:
    # value + delta (seconds to recompute) + absolute expiry, all in one hash.
    expiry = time.time() + ttl
    await client.hset(key, mapping={"value": value, "delta": delta, "expiry": expiry})

# 2. Measure the recompute cost

The delta field is the wall-clock cost of regenerating the value; measure it on the write path with perf_counter so the algorithm knows how much lead time an early refresh actually needs.

async def recompute_and_time(recompute) -> tuple[str, float]:
    start = time.perf_counter()
    value = await recompute()            # your expensive origin call
    delta = time.perf_counter() - start  # seconds this recompute took
    return value, delta

# 3. Implement the XFetch gate

The core of the algorithm is one line: draw a uniform random number in (0, 1), and recompute early when now - delta * beta * ln(random()) is at or past expiry. Because ln of a fraction is negative, that term is always positive and grows with delta, so a costly key volunteers sooner and a cheap key waits until it is nearly expired.

import math
import random


def should_recompute(delta: float, expiry: float, beta: float = 1.0) -> bool:
    # ln(random()) <= 0, so -delta*beta*ln(random()) >= 0 and pulls "now"
    # forward. Larger delta or beta means the gate fires earlier.
    now = time.time()
    return now - delta * beta * math.log(random.random()) >= expiry

# 4. Wire the read path with redis.asyncio

Fetch the hash, and if the entry exists and the gate does not fire, serve the cached value directly; otherwise the request has either found a cold key or won the early-recompute roll, so it regenerates the value and resets the entry for everyone else.

async def get_or_recompute(key: str, recompute, ttl: int = 300, beta: float = 1.0) -> str:
    entry = await client.hgetall(key)
    if entry and not should_recompute(float(entry["delta"]), float(entry["expiry"]), beta):
        return entry["value"]              # warm hit — the common case

    # Cold key or the probabilistic gate fired: this one request refreshes.
    value, delta = await recompute_and_time(recompute)
    await store_entry(key, value, delta, ttl)
    return value

# 5. Add a jittered TTL as a backstop

XFetch is probabilistic, not guaranteed, so give the hash itself an absolute Redis expiry set a little beyond the logical expiry and jittered so sibling keys never expire in lockstep — if every roll somehow misses, the key still leaves the keyspace within a bounded window instead of lingering forever.

async def store_entry(key: str, value: str, delta: float, ttl: int) -> None:
    expiry = time.time() + ttl
    await client.hset(key, mapping={"value": value, "delta": delta, "expiry": expiry})
    # Backstop lives past the logical expiry; jitter avoids synchronized removal.
    jitter = random.randint(0, ttl // 5)
    await client.expire(key, ttl + 60 + jitter)

# 6. Tune beta

beta scales how aggressively the gate fires: the default of 1.0 reproduces the paper's optimal behaviour, values above 1.0 shift recomputes earlier (more headroom, more redundant refreshes), and values below 1.0 push them closer to expiry (fewer refreshes, higher stampede risk). Tune it per key family against the recompute-to-request ratio you observe in production.

# Very hot, very expensive key: buy more lead time by firing earlier.
hot = await get_or_recompute("page:home", render_home, ttl=300, beta=2.0)

# Cheap, rarely read key: let it drift close to expiry before refreshing.
cold = await get_or_recompute("cfg:flags", load_flags, ttl=600, beta=0.5)

# Failure Modes

delta stored as zero, so the gate never fires. If the measurement in Step 2 is skipped or a serialization bug writes delta=0, the term delta * beta * ln(random()) collapses to zero and every read waits for the hard expiry — reintroducing the exact stampede XFetch was meant to prevent. Diagnose by inspecting the hash:

redis-cli HGET page:home delta   # must be a positive float, never 0

Fix by ensuring the write path always times the recompute and rejects a zero cost before calling HSET.

Beta set too high, causing redundant recomputes. An aggressive beta shifts the curve so far left that many readers volunteer well before expiry, hammering the origin with refreshes that throw away still-fresh values. Diagnose by comparing how often you recompute against how often you serve a warm hit:

redis-cli INFO stats | grep -E "keyspace_hits|keyspace_misses"
# A recompute rate climbing toward the request rate means beta is too high.

Fix by lowering beta toward 1.0 and re-measuring; the goal is a recompute count far below the read count.

Backstop TTL shorter than the logical expiry. If the EXPIRE in Step 5 is set below ttl, Redis evicts the hash before its logical expiry, and all three XFetch fields vanish together — turning every subsequent read into a cold-key miss. Diagnose by confirming the physical TTL outlives the stored expiry:

redis-cli TTL page:home            # should exceed the remaining logical window
redis-cli HGET page:home expiry    # absolute expiry the backstop must outlast

# Verification

Confirm a populated key carries all three fields and a live backstop before trusting the scheme under load:

redis-cli HGETALL page:home        # expect value, delta (>0), and expiry
redis-cli TTL page:home            # expect a positive integer beyond the window

Assert that under concurrent load a single request refreshes the key early rather than a herd refreshing at once. Instrument the recompute path so the ratio is observable:

from prometheus_client import Counter

RECOMPUTES = Counter("xfetch_recomputes_total", "Early and cold recomputes")
READS = Counter("xfetch_reads_total", "Total cache reads")

# Increment READS on every get_or_recompute call and RECOMPUTES inside the
# recompute branch; a healthy hot key shows RECOMPUTES far below READS.

Drive the key with many concurrent readers and watch the counters: xfetch_recomputes_total should tick up in ones just before each expiry while xfetch_reads_total climbs freely, proving the herd never forms.

# FAQ

# What does the beta parameter actually control?

beta scales the size of the early-recompute window. It multiplies the delta * ln(random()) term, so a larger beta makes the gate fire further ahead of expiry — more lead time to regenerate the value, at the cost of occasionally recomputing a value that was still fresh. The paper shows beta = 1.0 is optimal for minimizing the combined cost of stampedes and redundant work; treat it as the default and only move it when a specific key's recompute-to-read ratio tells you to.

# Why does the algorithm use a logarithm?

The recompute cost of a Poisson-like arrival process is modelled with an exponential distribution, and -ln(random()) is the standard way to sample from an exponential using a uniform draw. That transform makes the probability of an early refresh rise exponentially as expiry nears rather than linearly, which is what concentrates the single recompute into the narrow window just before the key would otherwise expire. It is not an arbitrary curve — it falls directly out of modelling when the next request will arrive.

# How does this interact with the key's TTL?

They are complementary layers. XFetch is the primary defence: it refreshes the hot key early so the hard expiry is rarely reached. The jittered TTL backstop from Step 5 is the safety net for the rare case where every roll misses or the process handling a refresh crashes mid-recompute, mirroring how a short TTL bounds a lost explicit purge. Set the backstop slightly longer than the logical expiry so it never fires first during normal operation.

# Is probabilistic early recomputation safe across multiple workers?

Yes, but understand what it does and does not guarantee. Each worker's read rolls the die independently, so the expected number of early recomputes is low but not exactly one — occasionally two requests refresh in the same window and both write. That double-write is harmless for idempotent recomputes, and the redundancy is far cheaper than a full stampede. When even a single redundant recompute is unacceptable, wrap the refresh branch in a short single-flight lock as described below.

# Does XFetch help a cold key that was never cached?

No. XFetch depends on a still-valid value being present to serve while one request refreshes; a cold key has nothing to serve, so every concurrent reader misses at once and stampedes the origin regardless of the algorithm. For that case, guard the first population with a single-flight distributed lock so exactly one worker computes the initial value while the rest wait, then let XFetch keep the now-warm key fresh from that point on.

---

Up: Cache Stampede Prevention with Probabilistic Early Expiration

# Related

• Cache Stampede Prevention with Probabilistic Early Expiration
• Distributed Locks for Cache Coordination
• TTL vs Explicit Invalidation: A Production Reliability Boundary
• Cache-Aside vs Read-Through Patterns