Cache Eviction Policy

The foundational temporal eviction algorithm that discards the item with the oldest access timestamp first. LRU operates on the principle of temporal locality: data accessed recently is highly likely to be accessed again soon.

• Mechanism: Maintains a doubly-linked list and hash map. Every GET or SET moves the item to the head. Eviction removes from the tail.
• Complexity: O(1) for both access and eviction.
• Best For: General-purpose workloads with strong recency bias, such as user session data or recent document queries.
• Weakness: Vulnerable to cache pollution from a full scan of infrequently accessed data, which flushes out the genuinely hot working set.

A time-bound eviction policy where each cache entry is assigned an absolute or sliding expiration timestamp upon insertion. The entry is automatically invalidated and removed once its lifespan elapses, regardless of access frequency.

• Absolute TTL: Expires at a fixed wall-clock time (e.g., '2025-01-01 00:00:00 UTC'). Ideal for daily financial snapshots.
• Sliding TTL: Resets the timer on every access. Ideal for user sessions where idle timeout is the concern.
• Best For: Data with known staleness windows, such as embedding caches for semi-static documents or API rate-limit counters.
• Weakness: Does not react to memory pressure. A sudden write spike can fill the cache with unexpired entries, causing an out-of-memory error before the timer fires.

An access-count-based policy that evicts the item with the lowest hit frequency. LFU tracks a counter for every key and removes the statistically least popular item when capacity is reached.

• Mechanism: Often implemented with a min-heap or a frequency list. A GET increments the counter and re-orders the item.
• Best For: Stable, long-lived datasets where historical popularity is a strong predictor of future value, such as a semantic cache storing frequently asked enterprise questions.
• Weakness: Cache pollution from historical data. An item that was extremely popular last week but is now irrelevant retains a high count and refuses to be evicted, occupying space that new, relevant data needs. Modern variants like Window-TinyLFU add recency weighting to solve this.

The simplest eviction policy, operating as a standard queue. The first item written into the cache is the first item evicted, regardless of how many times it has been accessed since insertion.

• Mechanism: A simple queue data structure. No re-ordering on access.
• Complexity: O(1) for all operations. Extremely low CPU overhead.
• Best For: Write-heavy, transient data streams where no single item is more valuable than another, such as a KV-Cache for a continuous batching inference server where sequences are processed in strict generation order.
• Weakness: Completely ignores access patterns. A frequently accessed 'hot' item will be evicted simply because it was the first to arrive, drastically reducing hit ratio for read-heavy workloads.

A probabilistic eviction strategy that selects a random candidate for removal when the cache is full. Despite its simplicity, it performs surprisingly well in specific adversarial scenarios.

• Mechanism: A random number generator selects the victim index. No metadata tracking is required.
• Best For: Extremely high-throughput systems where the overhead of tracking access order or frequency is prohibitive, or as a baseline comparison for more complex policies.
• Advantage: Immune to cache stampede pathologies caused by synchronized expiry timers. It naturally distributes eviction pressure.
• Weakness: Non-deterministic performance. It can occasionally evict the single most valuable item in the cache, causing a temporary latency spike for that specific query.

A hybrid policy that splits the cache into a probationary segment and a protected segment. New entries enter probation; if accessed again, they are promoted to the protected segment. Eviction occurs from the probationary end.

• Mechanism: Two LRU lists. A hit in probation promotes the item to the protected segment's head. When the protected segment is full, its tail item is demoted back to probation.
• Best For: Workloads susceptible to cache pollution from sequential scans. A single linear scan of a database table will cycle through the probationary segment without flushing the protected 'hot' set.
• Real-World Use: Forms the basis of many high-performance in-memory databases and OS page replacement algorithms. It provides a strong balance between recency and frequency without the historical baggage of pure LFU.

The primary metric for evaluating an eviction policy's effectiveness. It represents the percentage of requests served from the cache.

• Formula: (Cache Hits / Total Requests) * 100
• A high hit ratio means the eviction policy is correctly predicting future access patterns.
• Example: A 95% hit ratio means only 5% of requests incur the high latency of a primary database lookup.

A caching layer that stores query-answer pairs based on semantic similarity rather than exact string matching.

• Uses vector embeddings to determine if a new query is sufficiently similar to a cached query.
• Benefit: Can serve a cached response for a paraphrased question, dramatically increasing the effective hit ratio for natural language systems.
• Eviction Policy: Often uses a similarity threshold combined with TTL, as traditional recency-based policies don't map cleanly to semantic space.

A catastrophic failure mode that occurs when a highly popular cache entry expires.

• Scenario: A hot item expires. A flood of concurrent requests simultaneously miss the cache and hammer the backend database.
• Mitigation: Use probabilistic early expiration or a locking mechanism so only one request is allowed to regenerate the value.
• This is a critical consideration when setting TTL-based eviction policies for high-traffic keys.

A Time-To-Live policy evicts items after a fixed duration, regardless of access frequency.

• Use Case: Ideal for data with a known staleness window, like session tokens or weather data.
• Contrast with LRU: TTL guarantees data freshness; LRU optimizes for access patterns.
• Implementation: Can be passive (evict on access) or active (a background sweeper process removes expired keys).

A specialized memory mechanism in transformer models that stores the computed Key and Value tensors from previous tokens.

• Function: Prevents redundant computation during autoregressive text generation.
• Eviction Policy: Uses a sliding window or token budgeting. When the context window is full, old KV pairs are evicted, often using a simple FIFO or a more complex priority policy to retain important tokens.