Cache Eviction

Least Recently Used (LRU) evicts the item that has not been accessed for the longest time. It assumes recently used data is likely to be used again soon.

• Implementation: Typically uses a doubly linked list and a hash map. On access, the item is moved to the front (most recent). The tail item is evicted.
• Use Case: Excellent for workloads with strong temporal locality, such as user session data or browsing history.
• Weakness: Can be fooled by a single, sequential scan of a large dataset (one-time access), which flushes the entire cache.

Least Frequently Used (LFU) evicts the item with the lowest access count. It assumes frequently accessed data is more important.

• Implementation: Maintains a frequency count for each item. Often requires more complex data structures (e.g., a min-heap or layered lists) to manage efficiently.
• Use Case: Ideal for stable, repetitive access patterns, like caching popular API responses or static assets.
• Weakness: Can suffer from 'cache pollution' where an item accessed heavily in the past remains cached indefinitely, even if never used again. New items are highly susceptible to immediate eviction.

First-In, First-Out (FIFO) evicts the oldest item in the cache based on insertion time, regardless of how often or recently it was accessed.

• Implementation: Simple queue structure. New items are added to the back; the front item is evicted.
• Use Case: Useful as a baseline or in scenarios where access patterns are uniform and unpredictable.
• Weakness: Ignores access patterns entirely. A very hot item loaded early will still be evicted once it reaches the front of the queue, leading to poor hit rates for cyclical patterns.

Random Replacement (RR) selects a candidate item for eviction at random.

• Implementation: Low overhead. Can use a random number generator to pick an index from the cache's storage array.
• Use Case: Provides a simple, stateless alternative that avoids the worst-case scenarios of other policies. Used in some CPU caches.
• Weakness: Unpredictable and generally yields a lower hit ratio than LRU or LFU for patterned workloads. Performance is probabilistic.

Time-To-Live (TTL) is a time-based eviction policy where each item is assigned a maximum lifespan. Items are evicted when their TTL expires, irrespective of cache pressure.

• Implementation: Each cache entry has a timestamp. A background sweeper or lazy expiration checks timestamps on access.
• Use Case: Critical for ensuring data freshness. Universal in web caches (HTTP Cache-Control: max-age) and agent-side caching for API responses that become stale.
• Weakness: Does not directly address space management. A cache can fill with soon-to-expire items, requiring a secondary policy (like LRU) for capacity eviction.

Adaptive Replacement Cache (ARC) is a sophisticated, self-tuning algorithm that dynamically balances between recency (LRU) and frequency (LFU).

• Implementation: Maintains two LRU lists: one for recent entries (T1) and one for frequent entries (T2), plus two ghost lists (B1, B2) that track recently evicted items. Adaptively resizes the lists based on workload.
• Use Case: Designed for workloads where access patterns shift over time. It outperforms both LRU and LFU for many real-world, variable database and file system workloads.
• Weakness: Higher memory overhead due to ghost lists and more complex logic. The adaptive tuning has a learning period.

Least Recently Used (LRU) is the most common cache eviction algorithm. It removes the item that has not been accessed for the longest period when the cache reaches capacity. Implementation typically uses a doubly linked list and a hash map for O(1) operations.

• Mechanism: On every access (read or write), the item is moved to the front (most recent) of the list. The item at the tail of the list is evicted first.
• Use Case: Excellent for workloads with strong temporal locality, where recently used items are likely to be used again.
• Limitation: Can perform poorly under scanning patterns (one-time sequential access) as it flushes the entire cache.

Cache invalidation is the process of marking cached data as stale or deleting it to ensure subsequent requests fetch fresh data from the primary source. It is a proactive consistency mechanism, whereas eviction is a reactive capacity mechanism.

• Methods: Explicit deletion (by key), tag-based invalidation (all items with a specific tag), or time-based (TTL expiration).
• Challenge: Known as one of the two hard problems in computer science (along with naming things). Poor invalidation logic leads to stale reads.
• Pattern: Often used with write-through or write-behind caches to maintain consistency after source data updates.

Time-To-Live (TTL) is a time-based cache eviction and invalidation policy. It defines the maximum duration, in seconds or milliseconds, that a cached item is considered valid before it is automatically expired.

• Operation: A timestamp is stored with each cache entry. A background sweeper or on-access check compares the current time against the expiry time.
• Advantage: Simple to implement and effective for data that becomes stale at predictable intervals (e.g., API rate limit counters, non-critical configuration).
• Consideration: Can cause cache stampedes if many items expire simultaneously, leading to a thundering herd of database queries.

The cache hit ratio is the primary performance metric for any cache, calculated as (Cache Hits / Total Requests) * 100. It directly measures the effectiveness of the cache and its eviction policy.

• Interpretation: A high ratio (e.g., >95%) indicates the cache is effectively serving requests and reducing load on the primary data store. A low ratio suggests a poor eviction policy, insufficient cache size, or non-cacheable access patterns.
• Engineering Trade-off: The goal is to maximize the hit ratio within given memory constraints. Advanced policies like ARC or LRU-K self-tune to improve this ratio.
• Monitoring: A sudden drop in hit ratio is a critical alert, often indicating a change in traffic patterns or a bug in invalidation logic.

Adaptive Replacement Cache (ARC) is a sophisticated, self-tuning eviction algorithm that dynamically balances between recency (like LRU) and frequency (like LFU) to optimize the hit ratio under varying access patterns.

• Mechanism: Maintains two LRU lists: T1 for recent entries and T2 for frequent entries. It adaptively adjusts the size of these lists based on observed hits and misses.
• Advantage: Outperforms both LRU and LFU for many real-world, mixed workloads because it learns and adapts. It is immune to cache scans that cripple LRU.
• Complexity: More CPU and memory overhead than LRU (requires maintaining 4 metadata lists), but often worth the cost for high-performance caching tiers.

A cache stampede (or thundering herd) is a performance degradation scenario where the simultaneous expiration or invalidation of many cache items causes a sudden, overwhelming surge of requests to hit the primary data source.

• Cause: Often triggered by a TTL expiry wave, cache server restart, or a mass invalidation event.
• Mitigation Strategies:
  • Staggered Expiration: Add jitter (random variation) to TTLs.
  • Background Refresh: Use the stale-while-revalidate pattern to serve stale data while one process updates the cache.
  • Locking/Mutex: Ensure only one request recomputes the value while others wait.
• Impact: Can lead to database saturation, increased latency, and timeouts, potentially causing a cascading failure.