Cache Replacement Algorithms
💡 Concept Name
Cache Replacement Algorithms decide which cached data to remove when the cache is full and new data needs space.
LRU (Least Recently Used) and LFU (Least Frequently Used) are popular strategies for managing cache eviction effectively.
📘 Quick Intro
Cache replacement algorithms help optimize cache hit rates by identifying and evicting the least valuable data based on access patterns.
🧠 Analogy / Short Story
Think of a backpack with limited capacity:
- LRU: You remove the item you haven't used for the longest time.
- LFU: You remove the item you’ve used the least overall.
🔧 Technical Explanation
- 🎯 Detecting changes in source data isn’t always straightforward.
- 🧠 TTL (Time-To-Live) can help expire cache but doesn’t ensure freshness.
- ⚠️ Concurrent reads/writes may cause race conditions in cache.
- 🔄 Eviction and refresh strategies need careful planning.
- 📡 Distributed caches add synchronization and network complexity.
📘 Common Replacement Policies
Key cache eviction policies include LRU (Least Recently Used), LFU (Least Frequently Used), and FIFO (First-In-First-Out). Each suits different access patterns.
🔧 How They Work
- 🕒 LRU: Tracks access order; evicts the oldest accessed data first.
- 🔢 LFU: Counts accesses; removes data used least frequently.
- 🧠 LRU is simpler to implement with doubly linked list + hashmap.
- 📊 LFU requires frequency counters, often implemented with heaps or trees.
- ⚖️ LRU works well when recent access predicts future use.
🔧 Summary
- 🧠 LRU: Evicts the least recently accessed item.
- 📊 LFU: Removes the least frequently accessed item.
- 📅 FIFO: Evicts the oldest inserted item.
- 🚀 These algorithms balance speed and memory use.
- 🔁 Hybrid policies combine these strategies for adaptive caching.
💻 Code Example
// Basic LRU Cache Implementation using LinkedList and Dictionary
public class LRUCache
{
private readonly int _capacity;
private readonly Dictionary> _cacheMap = new();
private readonly LinkedList<(TKey Key, TValue Value)> _lruList = new();
public LRUCache(int capacity) => _capacity = capacity;
public TValue Get(TKey key)
{
if (!_cacheMap.TryGetValue(key, out var node)) throw new KeyNotFoundException();
_lruList.Remove(node);
_lruList.AddFirst(node);
return node.Value.Value;
}
public void Put(TKey key, TValue value)
{
if (_cacheMap.TryGetValue(key, out var node))
_lruList.Remove(node);
else if (_lruList.Count >= _capacity)
{
var leastUsed = _lruList.Last!;
_cacheMap.Remove(leastUsed.Value.Key);
_lruList.RemoveLast();
}
var newNode = new LinkedListNode<(TKey, TValue)>((key, value));
_lruList.AddFirst(newNode);
_cacheMap[key] = newNode;
}
}
📝 MCQs
Q1. What does LRU stand for?
- Last Random Update
- Least Recently Used
- Least RAM Usage
- Longest Running Usage
Q2. Which algorithm removes the least used item?
- FIFO
- LFU
- LRU
- MRU
Q3. What eviction policy removes the oldest item?
- LRU
- LFU
- FIFO
- TTL
Q4. Which algorithm is best for time-based access?
- LFU
- FIFO
- LRU
- MRU
Q5. What happens when cache is full?
- Resize cache
- Eviction
- App crash
- Flush all data
Q6. Which algorithm tracks frequency of use?
- LRU
- LFU
- FIFO
- TTL
Q7. Which policy uses a queue structure?
- LRU
- LFU
- FIFO
- MRU
Q8. What kind of data suits LRU?
- Random data
- Sequential only
- Recently reused
- Old data
Q9. Can LRU be implemented using LinkedList?
- No
- Yes
- Only arrays
- Only Redis
Q10. Why use cache replacement policies?
- To clear cache completely
- To store errors
- To keep cache relevant and efficient
- To log memory use
💡 Bonus Insight
Choosing the right cache eviction algorithm greatly impacts application speed and memory usage. Analyze your app’s data access patterns before deciding.
📄 PDF Download
Need a handy summary for your notes? Download this topic as a PDF!