Cache Eviction Policies

Caches have limited space. When they get full, and new data needs to be stored, some old data must be removed. This process is called cache eviction. Eviction policies are rules that decide which item to remove.

Choosing the right policy is crucial for maintaining a high cache hit rate, which means finding data in the cache more often, improving performance.

The First-In, First-Out (FIFO) policy is the simplest eviction strategy. It removes the item that has been in the cache the longest, regardless of how often it's been accessed. Think of it like a queue: the first item to enter is the first to leave.

• Simple to implement: Easy to understand and manage.
• Not always efficient: Might evict frequently used items if they were added early.

Imagine a cache that can hold 3 items. Let's see how FIFO handles adding A, B, C, then D:

1. Add A: Cache: [A]

2. Add B: Cache: [A, B]

3. Add C: Cache: [A, B, C]

4. Add D: Cache is full. A is the oldest item (First-In). Evict A. New Cache: [B, C, D]

FIFO prioritizes the entry time, not how often an item is accessed.

The Least Recently Used (LRU) policy is one of the most popular strategies. It evicts the item that hasn't been accessed for the longest time. The idea is that items used recently are more likely to be used again soon.

• Commonly used: Often provides good cache hit rates for many applications.
• More complex: Requires tracking the access time or order for each item.

Consider a cache with a capacity of 3. Access sequence: A, B, C, A, D, B:

1. Add A: Cache: [A]

2. Add B: Cache: [A, B]

3. Add C: Cache: [A, B, C] (A is LRU)

4. Access A: A becomes most recent. Cache: [B, C, A] (B is LRU)

5. Add D: Cache full. B is LRU. Evict B. Cache: [C, A, D]

6. Access B: Cache full. C is LRU. Evict C. Cache: [A, D, B]

The Least Frequently Used (LFU) policy evicts the item that has been accessed the fewest number of times. This policy aims to keep the most popular items in the cache, assuming past frequency predicts future frequency.

• Good for stable access patterns: Keeps popular items in the cache.
• Can be slow to adapt: A popular item from the past might stay even if its popularity drops significantly.
• More complex: Requires tracking access counts for each item.

Cache capacity 3. Access sequence: A, B, C, A, B, D:

1. Add A, B, C: Cache: [A(1), B(1), C(1)]

2. Access A: Cache: [A(2), B(1), C(1)]

3. Access B: Cache: [A(2), B(2), C(1)]

4. Add D: Cache full. C has the lowest frequency (1). Evict C. New Cache: [A(2), B(2), D(1)]

LFU keeps items with higher access counts, ensuring frequently used data stays resident.

The Most Recently Used (MRU) policy is the opposite of LRU. It evicts the item that was accessed *most* recently. This policy is less common but can be effective in specific scenarios, such as when data is accessed only once or in cyclical patterns.

• Niche use cases: Not suitable for general-purpose caching.
• Useful for single-pass data: Where older, less recent data is more likely to be reused.

Cache capacity 3. Access sequence: A, B, C, D:

1. Add A: Cache: [A]

2. Add B: Cache: [A, B]

3. Add C: Cache: [A, B, C]

4. Add D: Cache full. C was the Most Recently Used. Evict C. New Cache: [A, B, D]

MRU removes the item that was just accessed, making room for new data, which can be useful if access patterns avoid recently touched items.

There's no single "best" cache eviction policy; the ideal choice depends on your application's specific access patterns and requirements. Factors to consider:

• Data access frequency: How often are items accessed?
• Data access recency: Is recently used data likely to be used again?
• Implementation overhead: How much complexity and resources can you spare for tracking?
• Workload type: Read-heavy, write-heavy, streaming, etc.

Often, LRU is a good default starting point due to its balance of performance and practicality.

Consider a cache with a capacity of 3 items. The access sequence is: A, B, C, A, D.

What will be the final state of the cache if an LRU (Least Recently Used) eviction policy is applied?

We've explored key cache eviction policies that determine which data to remove when a cache is full:

• FIFO (First-In, First-Out): Evicts the oldest item.
• LRU (Least Recently Used): Evicts the item not accessed for the longest time, often a good default.
• LFU (Least Frequently Used): Evicts the item accessed the fewest times, good for stable popularity.
• MRU (Most Recently Used): Evicts the most recently accessed item, for specific use cases.

Understanding these policies helps optimize cache performance and overall application speed by ensuring relevant data remains accessible.