Cache Eviction Policy

The Least Recently Used (LRU) policy evicts the item that has not been accessed for the longest time. It operates on the principle of temporal locality, assuming that 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 item at the back of the list is evicted.
• Use Case: Excellent for workloads with strong recency patterns, such as web page caches and database query result caches.
• Drawback: Can be fooled by scans (one-time sequential accesses) that pollute the cache by evicting useful, frequently accessed items.

The Least Frequently Used (LFU) policy evicts the item with the lowest access count. It prioritizes retention based on historical popularity rather than recent access time.

• Implementation: Maintains a frequency count for each item, often with a min-heap or complex data structures to manage increments efficiently.
• Use Case: Ideal for workloads with stable, long-term popularity distributions, like caching popular product listings or media files.
• Drawback: Suffers from cache pollution; an item accessed heavily in the past but now irrelevant can remain in the cache indefinitely, blocking new items. Modern implementations use aging mechanisms to mitigate this.

The First-In, First-Out (FIFO) policy 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: Uses a standard queue data structure. New items are added to the back; the item at the front is evicted.
• Use Case: Simple to implement with low overhead. Sometimes used in operating system page caches.
• Drawback: Ignores access patterns entirely. A very hot item loaded early will still be evicted once it cycles to the front of the queue, leading to poor hit rates for cyclic or popular data.

The Random Replacement (RR) policy selects a candidate item for eviction at random. This non-deterministic approach requires minimal bookkeeping.

• Implementation: On eviction, generate a random index within the cache's capacity and evict the item at that slot.
• Use Case: Useful when access patterns are unpredictable or when the overhead of tracking recency/frequency is prohibitive. Found in some CPU caches.
• Drawback: Performance is unpredictable and often suboptimal compared to adaptive policies, as it may evict critical, hot data purely by chance.

The Most Recently Used (MRU) policy, counter-intuitively, evicts the most recently accessed item. This is based on the observation that in some access patterns, the newest item is least likely to be needed again in the immediate future.

• Implementation: Similar to LRU but evicts from the front of the recency list instead of the back.
• Use Case: Effective for workloads with linear scans (e.g., looping through a database table). In a scan, the just-accessed page is the one you will not return to, making it the ideal candidate for eviction.
• Drawback: Performs very poorly for general-purpose or recency-based workloads, where evicting the newest item destroys cache utility.

Time-To-Live (TTL) Expiration is not a pure eviction policy but a complementary mechanism that removes items based on age. Each cache entry is assigned a timestamp and a maximum lifespan. Entries are evicted when their TTL expires, irrespective of cache capacity or access patterns.

• Implementation: Requires a background process or lazy evaluation to check entry ages. Often combined with LRU or LFU.
• Use Case: Critical for ensuring data freshness and consistency. Used extensively for caching API responses, DNS records, and session data where information has a natural validity period.
• Drawback: Does not directly address capacity-driven eviction. A cache can be full of unexpired but irrelevant items, preventing new entries from being stored.

A cache eviction policy that removes the item that has not been accessed for the longest period. It is based on the principle of temporal locality, assuming that recently used data is likely to be used again.

• Implementation: Often uses a combination of a hash map (for O(1) lookups) and a doubly linked list (to track access order).
• Use Case: Highly effective for workloads with strong recency patterns, such as database query caches and web page caches.
• Challenge: Can be suboptimal for scans or cyclical access patterns that flush the entire cache.

A cache eviction policy that removes the item with the lowest count of accesses. It is based on the principle of frequency, prioritizing items that are used often over time.

• Implementation: Requires maintaining and sorting access counts, which can add overhead. Modern implementations use approximate counts or aging mechanisms to handle changing access patterns.
• Use Case: Ideal for caching stable, popular reference data, like library functions or common user profiles.
• Challenge: Can suffer from "cache pollution" where a once-popular item remains in cache long after it becomes irrelevant.

A simple cache eviction policy that removes the oldest item in the cache, regardless of how often or recently it has been accessed. It treats the cache as a circular buffer.

• Implementation: Typically uses a standard queue data structure.
• Use Case: Useful for sequential streaming data or when access patterns are uniform and unpredictable.
• Limitation: Ignores access frequency and recency, often leading to lower hit rates compared to LRU or LFU for common workloads.

A fundamental data integrity protocol where all modifications are written to a persistent log file before they are applied to the main database or data structure. This is not an eviction policy but a complementary durability mechanism.

• Function: Ensures atomicity and durability (ACID properties). If a system crashes, the log can replay changes to recover a consistent state.
• Interaction with Cache: Dirty pages in a database buffer cache must be flushed according to WAL rules, which can influence when data is evicted from memory to stable storage.

A form of automatic memory management that reclaims memory occupied by objects that are no longer in use by the program. It is a broader system-level concept analogous to cache eviction.

• Mechanism: The garbage collector (GC) identifies unreachable objects (e.g., via mark-and-sweep, generational collection) and frees their memory.
• Comparison to Eviction: While eviction policies manage a fixed-size cache, GC manages a dynamically allocated heap. Both decide what data to remove to free space.
• Performance Impact: GC pauses ("stop-the-world") are a critical performance consideration, similar to cache miss penalties.

A data structure used in storage engines (e.g., RocksDB, Cassandra) that optimizes write throughput. Its compaction process is a form of systematic data eviction and reorganization.

• Process: Writes are batched in memory (MemTable) and later flushed to disk as immutable Sorted String Tables (SSTables). A background compaction process merges and rewrites SSTables, discarding old or deleted data.
• Eviction Analogy: Compaction policies (e.g., Size-Tiered, Leveled) decide which SSTables to merge and which data to discard, directly impacting read performance and storage amplification.