Cache Eviction Policy

Discards the entry with the oldest access timestamp first, operating on the principle of temporal locality—data accessed recently is most likely to be accessed again.

• Mechanism: Maintains a doubly-linked list; accessed items move to the head, eviction removes from the tail.
• Complexity: O(1) for both access and eviction.
• Weakness: Vulnerable to cache thrashing during sequential scans where a large working set is accessed once and never again, evicting genuinely hot entries.

Evicts the entry with the lowest access frequency counter, prioritizing items with sustained popularity over recent one-hit wonders.

• Mechanism: Each entry maintains a reference count incremented on access; the minimum count is evicted.
• Advantage: Resistant to cache stampede scenarios where a popular item is temporarily eclipsed by a burst of novel requests.
• Drawback: Suffers from cache pollution—old entries with historically high counts persist indefinitely even if they are no longer relevant, requiring decay mechanisms.

A passive policy that invalidates entries based on an absolute expiration timestamp, enforcing data freshness without evaluating access patterns.

• Mechanism: Each entry carries a pre-defined lifespan; a background scavenger or lazy check on access removes expired items.
• Use Case: Critical for sovereign inference caching where regulatory compliance mandates that cached responses reflecting dynamic data must be purged after a fixed window.
• Risk: Mismanaged TTLs cause cache stampede—a flood of concurrent origin requests when a popular entry expires simultaneously.

Evicts entries strictly in the order they were inserted, treating the cache as a circular buffer with no regard for access frequency or recency.

• Mechanism: Implemented via a simple queue; the oldest inserted entry is evicted when capacity is reached.
• Complexity: O(1) with minimal metadata overhead, making it suitable for edge cache deployments on resource-constrained hardware.
• Limitation: Blind to access patterns; a frequently accessed entry inserted early will be evicted before a useless entry inserted later.

A self-tuning policy that dynamically balances between recency and frequency by maintaining two LRU lists (L1 and L2) with ghost entries to track recently evicted items.

• Mechanism: Adjusts the partition size between the recency-focused L1 list and the frequency-focused L2 list based on workload patterns.
• Advantage: Automatically adapts to shifting access patterns without manual parameter tuning, preventing both cache thrashing and cache pollution.
• Overhead: Higher memory footprint due to maintaining ghost lists of evicted keys.

Uses a compact Count-Min Sketch to estimate access frequency with minimal memory, making eviction decisions based on approximate frequency comparisons.

• Mechanism: Maintains a probabilistic frequency estimator; a new entry is admitted only if its estimated frequency exceeds the eviction candidate's.
• Efficiency: Drastically reduces metadata memory overhead compared to exact LFU, ideal for distributed cache layers with millions of keys.
• Trade-off: Accepts a small, controllable false positive rate in frequency estimation, which may occasionally evict a slightly hotter entry.

The most common eviction policy that discards the item with the oldest access timestamp first. LRU operates on the principle of temporal locality—data accessed recently is likely to be accessed again soon. Implementation typically uses a doubly linked list combined with a hash map for O(1) lookups and evictions.

• Head: Most recently accessed entry
• Tail: Least recently accessed, first to be evicted
• Drawback: Vulnerable to cache pollution from sequential scans that fill the cache with one-time-use data
• Variant: LRU-K tracks the timestamp of the K-th most recent access to better capture long-term utility

Evicts the entry with the lowest access frequency counter over its lifetime. Unlike LRU, LFU captures long-term popularity rather than recency, making it resistant to sequential scan pollution. However, it suffers from cache pollution by history—items that were once popular but are now obsolete retain high counters and never get evicted.

• Implementation: Min-heap or frequency-bucketed lists
• Decay mechanisms: Periodic counter reduction prevents stale entries from persisting
• Use case: Content delivery networks where object popularity is stable over time
• Variant: Window-LFU uses only recent access history to avoid historical bias

A time-based eviction policy where entries are automatically invalidated after a pre-configured duration. TTL is essential for enforcing data freshness in sovereign caching layers where stale inference results could violate compliance or produce incorrect outputs. Unlike access-pattern policies, TTL eviction is deterministic and time-driven.

• Absolute TTL: Expires at a fixed wall-clock time
• Sliding TTL: Resets the timer on each access, keeping hot data alive
• Interaction with LRU: TTL takes precedence—expired entries are evicted regardless of recency
• Critical parameter: Must be tuned to balance freshness against cache hit rate

A pathological performance state where the working set exceeds available cache capacity, causing constant eviction and reloading of entries. The system spends more resources on eviction overhead than on serving requests, collapsing hit rates to near zero. Thrashing is the primary failure mode that eviction policies are designed to prevent.

• Symptoms: High CPU usage, low hit rate, elevated backend load
• Causes: Undersized cache, sudden workload shift, or poor eviction policy choice
• Mitigation: Increase cache size, implement admission policies, or use probabilistic eviction
• Detection: Monitor the ratio of evictions to insertions—a ratio approaching 1:1 indicates thrashing

A self-tuning strategy that dynamically switches between eviction policies based on real-time workload analysis. Adaptive caching uses online machine learning or heuristic algorithms to detect access pattern shifts and select the optimal policy without manual intervention.

• Pattern detection: Identifies sequential scans, temporal bursts, or stable popularity distributions
• Policy switching: Transitions between LRU, LFU, and size-based eviction on the fly
• Cost-awareness: Factors in the computational cost of regenerating each cached entry
• Relevance to sovereign AI: Reduces operational overhead in air-gapped environments where manual tuning is impractical

A cascading failure scenario triggered when a highly popular cache entry expires, causing a flood of concurrent requests to simultaneously hit the origin model or database. The sudden spike overwhelms backend resources, potentially causing a complete service outage. Eviction policies interact with stampede prevention through probabilistic early expiration.

• Mechanism: Multiple threads detect the same cache miss and independently regenerate the value
• Prevention: Locking on miss, external recomputation, or probabilistic early recomputation
• XFetch algorithm: Computes optimal early recomputation time based on request rate and regeneration cost
• Sovereign context: Critical in inference caching where model recomputation is extremely expensive