Cache Eviction Policy

What is Caching and Why Eviction?

A cache is a smaller, faster memory storage area that stores copies of frequently accessed data from a primary, slower storage (like RAM caching disk data, or a web server caching database results). Accessing data from the cache (a cache hit) is much faster than fetching it from the original source (a cache miss).

Since the cache has limited size, it will eventually become full. When new data needs to be added but the cache is full, an existing item must be removed (evicted) to make space. A cache eviction policy is the algorithm used to decide which item to discard. The goal is to evict the item least likely to be needed soon, maximizing the chance that future requests result in cache hits.

Common Eviction Policies

1. FIFO (First-In, First-Out)

This is the simplest policy. It treats the cache like a queue. The item that has been in the cache the longest is the first one to be evicted, regardless of how often or recently it was accessed.

• How it works: When eviction is needed, remove the item that was added earliest.
• Pros: Very simple and fast to implement.
• Cons: Often inefficient. A frequently accessed item might be evicted simply because it was added early.

2. LRU (Least Recently Used)

This policy assumes that data accessed recently is likely to be accessed again soon. It evicts the item that hasn't been accessed for the longest time.

• How it works: Keep track of when each item was last accessed. When eviction is needed, remove the item with the oldest access timestamp. Accessing an item (a cache hit) updates its timestamp, making it "recently used".
• Pros: Generally performs well, as it keeps frequently and recently used data. It's a common default policy.
• Cons: Requires tracking access times for every item, which adds overhead. Can perform poorly with cyclical access patterns where old items become needed again right after eviction.

3. LFU (Least Frequently Used)

This policy assumes that data accessed most often is more important and should stay in the cache. It evicts the item that has been accessed the fewest number of times.

• How it works: Keep a counter for each item, incrementing it on each access (cache hit). When eviction is needed, remove the item with the lowest frequency count.
• Pros: Keeps popular items even if they haven't been accessed very recently.
• Cons: Requires tracking frequency counts. An item might have been popular initially but isn't needed anymore (cache pollution). Needs a tie-breaking rule (e.g., LRU among least frequent items) if multiple items have the same lowest frequency. Can be more complex to implement efficiently.