Minus Log Of Random

A hot key is written with a 60 second TTL. Readers arrive throughout its life, and the four nearest expiry are marked.

Every reader runs this, where $\Delta$ is the measured wall time the last recompute took and rand() draws uniformly from $(0, 1]$ :

function XFetch(key, ttl; beta = 1)
    value, delta, expiry <- CacheRead(key)
    if !value or Time() - delta * beta * log(rand()) >= expiry then
        start <- Time()
        value <- RecomputeValue()
        delta <- Time() - start
        CacheWrite(key, (value, delta), ttl)
    end
    return value
end

What does the term $-\Delta\beta\ln(\text{rand}())$ accomplish?

It scales the TTL by $\beta$ , so raising $\beta$ keeps values cached longer and lowers origin load

It pulls each reader's effective expiry earlier by an independent exponential random amount whose scale is the recompute cost, so expensive keys are refreshed further ahead and typically one reader does it

It adds jitter to the TTL when the value is written, spreading expiry times across keys

It makes readers that arrive near expiry sleep a random interval and retry, so only the first one reaches the origin