Caching Eviction and Invalidation Policies

Least Recently Used (LRU)

LRU evicts the item that has not been accessed for the longest time. This policy operates on the principle of temporal locality, assuming that recently accessed data is more likely to be needed again soon.

Characteristics:

• Maintains access order using a doubly-linked list or similar structure
• Moves accessed items to the front of the queue
• Evicts items from the back when space is needed
• Effective for workloads with temporal locality patterns

Use cases:

• Web browsers caching recently visited pages
• Application-level caching with predictable access patterns
• Systems where recency is more important than frequency

Least Frequently Used (LFU)

LFU removes the item with the fewest accesses over time. This policy prioritizes keeping frequently accessed items in the cache, assuming that items with higher access counts are more likely to be requested again.

Characteristics:

• Tracks access frequency for each cached item
• Maintains counters that increment on each access
• Evicts items with the lowest frequency count
• Effective when access patterns are stable over time

Use cases:

• Content delivery networks caching popular assets
• Database query result caching
• Systems with stable, predictable access patterns

First In, First Out (FIFO)

FIFO evicts the item that was added to the cache first, regardless of how often or recently it was accessed. This policy treats the cache like a queue, removing items in the order they were added.

Characteristics:

• Simple queue-based implementation
• No tracking of access patterns or frequency
• Low overhead and easy to implement
• May not always yield optimal performance

Use cases:

• Simple caching scenarios with uniform data importance
• Systems with limited computational resources
• When data freshness is more important than access patterns

Random Replacement

Random Replacement removes an item chosen randomly from the cache. This policy requires minimal overhead and can be effective when access patterns are unpredictable.

Characteristics:

• Minimal computational overhead
• No tracking of access history or patterns
• Unpredictable eviction behavior
• Simple to implement

Use cases:

• Systems with truly random access patterns
• When other policies are too expensive to implement
• Testing and benchmarking scenarios

Time-To-Live (TTL)

TTL evicts items after a fixed duration since being cached. Each cache entry has an expiration timestamp, and items are automatically removed once their TTL expires, regardless of access patterns.

Characteristics:

• Time-based expiration for each cache entry
• Ensures data freshness and prevents stale data
• Can be combined with other eviction policies
• Requires periodic cleanup of expired entries

Use cases:

• API response caching with known update frequencies
• Session data and authentication tokens
• Time-sensitive data that becomes stale quickly

Adaptive Replacement Cache (ARC)

ARC balances between LRU and LFU dynamically based on workload. This policy maintains two lists: one for recently accessed items and another for frequently accessed items, adapting the balance between them based on access patterns.

Characteristics:

• Dynamically adapts to changing access patterns
• Combines benefits of both LRU and LFU
• More complex implementation than simple policies
• Better performance for mixed workloads

Use cases:

• Systems with varying access patterns
• High-performance caching requirements
• When workload characteristics change over time

Least Recently/Frequently Used (LRFU)

LRFU combines aspects of LRU and LFU by assigning weights to recency and frequency. This policy calculates a score for each item based on both when it was last accessed and how frequently it has been accessed, evicting items with the lowest scores.

Characteristics:

• Balances recency and frequency through weighted scoring
• Configurable weights allow tuning for specific workloads
• More sophisticated than pure LRU or LFU
• Requires tracking both access time and frequency

Use cases:

• Systems requiring balanced consideration of recency and frequency
• Workloads with both temporal and frequency-based patterns
• When fine-tuning cache behavior is necessary

Time-Based Invalidation

Cache entries are invalidated after a fixed time period, similar to TTL eviction. This approach ensures data freshness but may invalidate entries that haven't changed.

Event-Based Invalidation

Cache entries are invalidated when specific events occur, such as data updates or deletions. This approach maintains better consistency but requires tracking dependencies between data and cache entries.

Manual Invalidation

Cache entries are explicitly invalidated by application code or administrators. This provides full control but requires careful management to avoid stale data.

Tag-Based Invalidation

Cache entries are tagged with metadata, and invalidation occurs by tag. This allows invalidating multiple related entries simultaneously, useful for hierarchical or related data.