Cache Eviction Policy

Least Recently Used (LRU) evicts the item that has not been accessed for the longest time. It operates on the principle of temporal locality, assuming recently used data is likely to be used again.

• Implementation: Typically uses a doubly-linked list and a hash map. On access, the item is moved to the 'most recent' end of the list. The item at the 'least recent' end is evicted.
• Use Case: Excellent for workloads with strong recency patterns, such as web page caches and database buffer pools.
• Weakness: Can be fooled by scans (one-time sequential accesses) that flush the entire cache.

Least Frequently Used (LFU) evicts the item with the lowest count of access requests. It prioritizes frequency of use over recency.

• Implementation: Maintains a frequency count for each item. Requires more metadata (counters) than LRU and must handle aging to prevent stale, high-count items from permanently occupying the cache.
• Use Case: Ideal for workloads with stable, popular reference patterns, like caching popular product data or media assets.
• Weakness: Susceptible to cache pollution from a burst of requests to a new item that is never accessed again, as its high initial count protects it.

First-In, First-Out (FIFO) evicts the item that has been in the cache the longest, regardless of how often or recently it was accessed. It treats the cache as a simple queue.

• Implementation: Low overhead. New entries are added to the tail of a queue; eviction occurs at the head.
• Use Case: Simple, predictable behavior for sequential or streaming data where access patterns are uniform.
• Weakness: Poor performance for most dynamic workloads because it ignores both recency and frequency, often evicting hot data.

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

• Implementation: Very low computational cost. Requires a pseudo-random number generator and a way to index into the cache (e.g., an array).
• Use Case: Useful as a simple baseline or in adversarial scenarios where other policies' predictable access patterns can be exploited to force worst-case performance (cache thrashing).
• Weakness: Unpredictable and generally yields lower hit rates than LRU or LFU for common workloads, but avoids systematic worst-case behavior.

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

• Implementation: Maintains two LRU lists: T1 for recent entries and T2 for frequent entries. A target parameter p adaptively sizes these lists based on workload. It learns and adjusts to the actual access pattern.
• Use Case: High-performance database systems (e.g., IBM DB2, ZFS) and file caches where workloads are mixed or unpredictable.
• Weakness: Higher memory overhead for metadata and more complex implementation than basic LRU/LFU.

Time-To-Live (TTL) is not a capacity-based eviction policy but a time-based expiration mechanism. Each cache entry has an absolute or relative timestamp after which it is considered stale and evicted on next access or by a background cleaner.

• Implementation: Requires storing a timestamp per entry and a periodic or lazy process to purge expired items.
• Use Case: Critical for data with inherent freshness requirements, such as API rate limit counters, session data, news feeds, or any data sourced from a mutable backend.
• Interaction: Often used in conjunction with capacity policies (e.g., LRU). An item may be evicted because it expired (TTL) or because the cache was full (LRU).

Least Recently Used (LRU) is the canonical cache eviction algorithm that removes the item that has not been accessed for the longest period. It operates on the principle of temporal locality, assuming recently used data is likely to be used again.

• Implementation: Often uses a doubly-linked list and a hash map for O(1) access and movement.
• Weakness: Can be exploited by scans (one-time sequential access of many items), which flush the entire cache.
• Variants: LRU-K considers the time of the K-th-to-last access for better resistance to scans.

Least Frequently Used (LFU) is a cache eviction algorithm that removes the item with the lowest count of access requests. It prioritizes popularity over recency.

• Implementation: Requires maintaining and sorting access counts, often with a min-heap or complex data structures.
• Challenge: Cache pollution from items with a high initial count that are never accessed again.
• Modern Use: Common in CDN and web caching where long-term popularity is a strong predictor.

Time-To-Live (TTL) is a time-based expiration mechanism that sets a deadline on cached data, after which the item is considered stale. It is often used in conjunction with, or as a primary driver for, eviction.

• Primary Use: Ensures data freshness and consistency by bounding how long stale data can persist.
• Implementation: Each cache entry stores an expiration timestamp. A background sweeper or lazy evaluation removes expired items.
• Example: DNS records and API response caches heavily rely on TTL for propagation and consistency.

Adaptive Replacement Cache (ARC) is a self-tuning, adaptive policy that dynamically balances between recency (LRU) and frequency (LFU). It uses two LRU lists: one for recent entries (T1) and one for frequent entries (T2), with adaptive sizes.

• Mechanism: Monitors hits in the lists to decide whether to favor recency or frequency, resizing T1 and T2 accordingly.
• Advantage: Resists scans better than pure LRU and adapts to changing access patterns without manual tuning.
• Complexity: Higher overhead than LRU but provides robust performance for mixed workloads.

Cache invalidation is the process of marking cached data as obsolete and removing it to ensure consistency when the underlying source data changes. It is a critical problem in system design.

• Strategies: Write-through (update cache and DB simultaneously), write-behind (update cache, queue DB write), and invalidation protocols (e.g., purge messages).
• Challenge: Scalability in distributed caches; maintaining consistency without excessive coordination.
• Quote: Often cited as one of the two hard things in computer science, alongside naming things and off-by-one errors.

The working set model is a principle in memory management defining the subset of pages or cache entries a process actively needs within a specific time window (Δ). The goal of a cache is to hold the current working set.

• Principle: If the cache can contain the entire working set, hit rate is high. If not, thrashing occurs.
• Application: Informs the sizing of caches and helps analyze the performance of eviction policies.
• Relation to Eviction: Optimal eviction would only remove items not in the working set, which is theoretically impossible without future knowledge.