Optional stampede protection for CacheManager.get_or_set()

[allen0099]

Summary

CacheManager.get_or_set() documents that it "does not provide stampede protection: concurrent misses for the same key may each invoke factory". When the factory is expensive (a slow query, an upstream API with rate limits) and the key is hot, an expiry turns into N simultaneous recomputations.

Proposal

An opt-in lock around the miss path, built on CacheLock (#64):

report = await cache.get_or_set(
    "report:daily",
    build_report,
    ttl=300,
    lock_ttl=30,        # enables protection; upper bound on one factory run
    wait_timeout=10,    # how long other callers wait for the winner
)

1. On a miss, try to acquire a lock for the key (non-blocking).
2. The winner re-checks the cache, runs factory, stores the value, and releases the lock.
3. Everyone else polls the cache until the value appears or wait_timeout elapses.
4. On timeout, fall back to running factory themselves, so a crashed winner degrades to today's behaviour instead of failing requests.

Without lock_ttl the behaviour is unchanged, so this is backward compatible.

Open questions

• Polling interval and whether to back off.
• Whether the @cache decorator's miss path should get the same option later (separate issue; it has to deal with response objects, not plain values).

Depends on: #64

[allen0099]

@ShivanshShukla, following up on your question in #175: this issue could be a good next step for you. It adds optional stampede protection to CacheManager.get_or_set() and builds directly on the CacheLock you wrote in #150. It is opt-in and not tied to a release, so there is room to get the design right.

Before writing code, please post a short design here covering:

• the parameters (lock_ttl, wait_timeout or otherwise) and their defaults;
• how waiters poll: the interval, and whether to back off;
• what happens when the winner crashes or the factory raises.

Once we agree here, I'll assign it to you. #67 (ConcurrencyLimit) is a natural follow-up after that.

[ShivanshShukla]

Hi @allen0099, thanks for tagging me! This is a perfect follow-up to the CacheLock work, and I'd love to take it on.

Here is my proposed design for the stampede protection implementation:

1. Parameters and Defaults

• lock_ttl: Optional[float] = None. This acts as the opt-in flag. If None, we bypass the locking logic entirely to maintain backward compatibility.
• wait_timeout: Optional[float] = 10.0. Only active if lock_ttl is provided. This defines the upper bound a waiter will poll before degrading to executing the factory itself.

2. Polling Strategy (Waiters)

Waiters shouldn't spam the cache backend. I propose an exponential backoff with jitter:

• Initial interval: 50ms (so fast factories don't suffer unnecessary latency).
• Multiplier: 1.5x to 2.0x per attempt.
• Max interval: Capped at 500ms or 1s.
• Jitter: Add a small randomized jitter (e.g., +/- 10%) to prevent multiple waiters from polling at the exact same millisecond and causing micro-spikes on the cache server.

3. Failure Modes

What happens if the winner crashes (e.g., process killed/OOM)?

• The lock_ttl acts as the safety net in the cache backend. Meanwhile, the waiting tasks will eventually hit their wait_timeout.
• Once wait_timeout elapses, the waiters will log a warning and fall back to running the factory themselves (graceful degradation, behaving like the current non-locked path).

What happens if the factory raises an exception?

• The winner's execution will be wrapped in a try...finally block.
• If the factory fails, the winner explicitly calls lock.release() in the finally block before re-raising the exception.
• This immediately frees up the lock. The next waiter in the polling cycle will acquire it and become the new winner to try the factory again (which is preferred over all waiters timing out and stampeding).

Let me know if this aligns with your vision for the feature. If it looks good, I can start scaffolding the implementation!

[allen0099]

Thanks @ShivanshShukla, this is a good starting point. Releasing the lock in finally and polling with backoff and jitter both look right. Some points to settle before you start. The first one also sets up where this is heading.

1. An explicit switch, and a manager-wide default

lock_ttl=None doubles as the on/off switch, which forces users to pick a TTL just to turn the feature on. It also makes get_or_set(key, f, lock_ttl=30) hard to read. Please separate the two:

class CacheManager:
    def __init__(self, ..., lock: bool = False, lock_ttl: int = 60): ...

    async def get_or_set(
        self,
        key,
        factory,
        ttl=None,
        *,
        lock: bool | None = None,  # None = inherit the manager's setting
        lock_ttl: int | None = None,
        wait_timeout: float | None = None,
    ): ...

The per-call lock defaulting to None (inherit) rather than False matters. We plan to turn protection on by default in 0.4.0 (tracked in #280), and with this shape that is a one-line change to the manager default, with no signature change. lock_ttl defaults to 60 like CacheLock.

2. Re-entrancy

If factory calls get_or_set for the same key, it would wait on its own lock until the timeout. Please guard against that, e.g. with a contextvars set of keys held by the current task, and skip locking on re-entry. It is rare while the feature is opt-in, but it has to exist before the default flips.

3. Types

Backend TTLs are whole seconds (validate_ttl rejects floats, and CacheLock.ttl is an int), so lock_ttl is int | None. Please use X | None rather than Optional[X] to match the codebase.

4. What waiters poll

On each tick a waiter should:

1. check the cache, and return on a hit;
2. otherwise try to take the lock.

Whoever takes the lock must re-check the cache before calling factory. Without that re-check, a waiter that takes the lock just after the winner stored the value and released it would compute it again.

5. Timeout fallback

Running factory in every waiter once wait_timeout passes is a stampede in exactly the case this feature exists for: a slow factory. So:

• wait_timeout should default to something derived from lock_ttl, not a fixed 10 s.
• The post-timeout behaviour should be explicit: either documented as "compute it yourself", or selectable to raise TimeoutError instead. What do you think?

6. A lock shorter than the factory

If factory outlives lock_ttl, the lock expires mid-run and a second winner starts. For a first version it is enough to document that lock_ttl should exceed the expected factory time. Renewing the lock via CacheLock.extend() can come later.

7. Ordering

The winner stores the value, then releases the lock, never the other way round.

8. Tests

• Please make the sleep and the clock injectable, so the tests don't wait in real time (see Tests: control time instead of sleeping for TTLs #185).
• The live tests should cover memory, Redis and Memcached. They should include a crashed winner, a raising factory and a wait timeout. 0.4.0: enable get_or_set() stampede protection by default #280 lists these among the gates for the 0.4.0 default.

With those settled, please post an updated signature here and I'll assign the issue to you. I've put this on the 0.3.9 milestone, so there is no rush.