What memory invariants must survive a distributed cache eviction storm?

**Date of Record:** 2026 October 27 **Scope:** Applies when an agentic session relies on a distributed cache (Redis, Memcached, or a custom L1/L2 tier) and experiences a cache eviction storm (sudden, widespread invalidation), and must preserve state for a successor to resume without overwhelming the backing store. Does not apply to purely stateless compute or caches with infinite capacity.

Core Distinction

The separation between **local eviction** (a single node drops its cache due to memory pressure) and a **cascading eviction storm** (one node's miss triggers queries to the backing store, which slows down other nodes, causing them to miss and query, cascading globally). Relying solely on the cache layer creates the **Eviction Cascade Hazard**: the cache empties, the backing database is overwhelmed by simultaneous misses, and the agent's session either times out or crashes entirely.

What Was Observed

In high-throughput agent architectures, failing to preserve memory invariants during cache evictions produces three primary failure modes:

  1. **Thundering Herd on Database:** 50 agents share a cache. The cache node restarts, all 50 agents miss simultaneously, and all 50 query the backing database at once, exhausting the connection pool.
  2. **Stale Cache Repopulation:** The cache evicts a key, but the backing store still has an old value due to replication lag. The agent repopulates the cache with stale data, cementing the stale state.
  3. **Rate-Limit Exhaustion:** The cache is gone. The agent falls back to external APIs for every lookup, burning through its rate limit in minutes.

Recorded Elements

  1. **`cache_eviction_rate`:** The exact number of evictions per second observed at the time of session pause, indicating the severity of the storm.
  2. **`backing_store_headroom_hash`:** The cryptographic proof of the backing store's current load and capacity, allowing the successor to determine if it can safely repopulate the cache.
  3. **`single-flight_lock_manifest`:** The exact set of keys that must be re-fetched with a "single-flight" lock (only one agent fetches, others wait), preventing a thundering herd.
  4. **`cache_warmup_priority_list`:** The ordered list of keys by criticality, enabling the successor to prioritize cache warmup on the most important data first.

Condition of Validity

* **Applies when:** The cache layer is shared across multiple agents, the backing store cannot handle the full miss rate, and the cache can undergo large-scale evictions. * **Does not apply when:** The cache is strictly local to each agent with no backing store, or the backing store is provisioned to handle maximum possible miss rate without degradation.

Decision Boundary

  1. **Has the cache eviction rate exceeded the safe threshold?** If no, standard cache behavior applies. If yes, proceed.
  2. **Is the `backing_store_headroom_hash` showing sufficient capacity?** If no, the successor must NOT allow full cache repopulation, and must instead throttle or use stale-while-revalidate.
  3. **Are the `single-flight_lock_manifest` keys present?** If no, the successor must implement single-flight locking before any repopulation attempt.
  4. **Conversely, when can an agent skip single-flight locking during a storm?** Only when the eviction rate is low enough that the backing store can handle the miss rate without degradation, and the agent has a documented capacity headroom of at least 3x the expected miss rate.

Operational Effect

  1. **Eviction Cascade Prevention:** Stops the thundering herd by enforcing single-flight locking for critical keys during a cache storm.
  2. **Backing Store Protection:** Prevents cache repopulation from overwhelming the backing store, preserving its availability.
  3. **Deterministic Recovery:** Provides a prioritized warmup list, allowing the successor to restore the cache efficiently after the storm passes.
from dataclasses import dataclass
from enum import Enum, auto
import hashlib
import json

class EvictionVerdict(Enum):
    NOMINAL_EVICTION = auto()
    STORM_DETECTED_THROTTLE = auto()
    STORM_DETECTED_HALT_REPOPULATION = auto()

@dataclass(frozen=True)
class CacheState:
    eviction_rate_per_sec: float
    safe_eviction_threshold: float
    backing_store_headroom_ratio: float

@dataclass(frozen=True)
class EvictionPolicy:
    critical_keys: frozenset[str]
    min_headroom_for_repopulation: float

@dataclass(frozen=True)
class EvictionManifest:
    verdict: EvictionVerdict
    directive: str
    manifest_digest: str

class EvictionStormGuard:
    @staticmethod
    def _hash(data: str) -> str:
        return hashlib.sha256(data.encode("utf-8")).hexdigest()

    @classmethod
    def evaluate_storm(
        cls, state: CacheState, policy: EvictionPolicy
    ) -> EvictionManifest:
        
        # Gate 1: Eviction rate within safe bounds
        if state.eviction_rate_per_sec <= state.safe_eviction_threshold:
            digest = cls._hash(json.dumps({
                "rate": f"{state.eviction_rate_per_sec:.2f}",
                "threshold": f"{state.safe_eviction_threshold:.2f}"
            }, sort_keys=True))
            return EvictionManifest(
                verdict=EvictionVerdict.NOMINAL_EVICTION,
                directive="PROCEED: Eviction rate within normal bounds.",
                manifest_digest=digest
            )

        # Gate 2: Backing store headroom check
        if state.backing_store_headroom_ratio < policy.min_headroom_for_repopulation:
            return EvictionManifest(
                verdict=EvictionVerdict.STORM_DETECTED_HALT_REPOPULATION,
                directive=f"HALT: Eviction storm detected. Headroom {state.backing_store_headroom_ratio:.2f} < {policy.min_headroom_for_repopulation:.2f}. Halt repopulation.",
                manifest_digest=cls._hash(f"HALT:{state.backing_store_headroom_ratio:.2f}")
            )

        # Gate 3: Throttled repopulation
        digest = cls._hash(json.dumps({
            "rate": f"{state.eviction_rate_per_sec:.2f}",
            "headroom": f"{state.backing_store_headroom_ratio:.2f}",
            "critical_keys": tuple(sorted(policy.critical_keys))
        }, sort_keys=True))
        
        return EvictionManifest(
            verdict=EvictionVerdict.STORM_DETECTED_THROTTLE,
            directive=f"THROTTLE: Repopulate only critical keys {sorted(policy.critical_keys)}. Throttle other fetches.",
            manifest_digest=digest
        )