Caching helps store frequently accessed data to improve the performance and functionality of web applications. However, managing data in a cache can be challenging. Cache eviction helps manage cached data by removing outdated, unused, or less frequently accessed items to make space for new data.
Cache eviction plays an important role in managing limited cache storage and maintaining application performance. When a cache becomes full, an eviction policy determines which data should be removed to make room for new information. In this article, we’ll explore how cache eviction works, the most common eviction policies, and how to choose the right strategy for your application.
What is Cache Eviction
Cache eviction refers to removing data from a cache when it reaches its storage limit or when certain data is no longer needed. Because caches have limited capacity, they cannot store data indefinitely. Therefore, eviction policies determine which items should be removed to make room for new data.
Why is cache eviction needed?
A cache has limited memory. When it's full and a new item needs to be stored, the system must decide which existing item to remove. This decision is made using a cache eviction policy.
Example Imagine a cache that can store only 3 items.- Cache:
[A, B, C] - You request
D. - Since the cache is full, one item must be evicted.
- If the policy is Least Recently Used (LRU) and A hasn't been accessed recently, the cache becomes
[B, C, D]. Here,Awas evicted.
What Are Cache Eviction Policies?
Cache eviction policies are rules used to decide which data should be removed from a cache when the cache becomes full. Since a cache has limited storage, an eviction strategy helps remove less useful data and make room for new or frequently accessed data.
In simple terms: Cache eviction policies help a system decide “Which data should we remove when there is no more space in the cache?” The right strategy depends on how frequently data is accessed, how long it remains useful, and the requirements of the application.
Where cache eviction is used
- Web browsers: Remove old cached web pages and images.
- Databases: Keep frequently accessed records in memory.
- Operating systems: Manage memory pages.
- CDNs: Replace less useful content with newly requested content.
- Applications: Libraries like Redis, Memcached, and in-memory caches use eviction policies.
Why choosing the right policy matters
-
An effective eviction policy:
- Improves application performance.
- Reduces database or disk access.
- Makes better use of limited memory.
- Increases the cache hit rate (how often requested data is found in the cache).
Common Cache Eviction Policies
- LRU (Least Recently Used) Removes the data that has not been accessed for the longest time. It is one of the most commonly used cache eviction strategies.
- LFU (Least Frequently Used) Removes data that has been accessed the fewest number of times. This strategy is useful when frequently accessed data should remain in the cache.
- FIFO (First In, First Out) Removes the data that was added to the cache first, regardless of how frequently or recently it was accessed.
- TTL (Time-to-Live) Removes cached data after it reaches a predefined expiration time. This is useful when cached information should only remain valid for a specific period.
- MRU (Most Recently Used) Removes the data that was accessed most recently. This can be useful for applications where recently accessed data is less likely to be needed again.
Important: The cache technology determines which eviction policies it natively supports.
Think of it this way| Cache | Where data lives | Eviction policy |
|---|---|---|
IMemoryCache | Application server memory | Supports expiration/priority/compaction; not strict LRU |
| Redis | Separate cache server | Supports several eviction policies, including LRU approximations |
| Custom in-memory cache | Application memory | You can implement strict LRU yourself |
| Custom distributed cache | Redis/etc. | Usually let the distributed cache handle eviction |
Implementing Cache Eviction Policies
LRU (Least Recently Used)
In C#, a clean way to implement an LRU (Least Recently Used) cache eviction policy is with Dictionary for O(1) lookup and LinkedList to maintain usage order.
using System;
using System.Collections.Generic;
public class LruCache<TKey, TValue>
{
private readonly int _capacity;
// Maps key -> node in the linked list
private readonly Dictionary<TKey, LinkedListNode<(TKey Key, TValue Value)>> _cache;
// Most recently used at the front,
// least recently used at the back.
private readonly LinkedList<(TKey Key, TValue Value)> _lruList;
public LruCache(int capacity)
{
if (capacity <= 0)
throw new ArgumentException("Capacity must be greater than 0.");
_capacity = capacity;
_cache = new Dictionary<TKey, LinkedListNode<(TKey, TValue)>>();
_lruList = new LinkedList<(TKey, TValue)>();
}
public bool TryGet(TKey key, out TValue value)
{
if (_cache.TryGetValue(key, out var node))
{
// Mark as recently used
_lruList.Remove(node);
_lruList.AddFirst(node);
value = node.Value.Value;
return true;
}
value = default!;
return false;
}
public void Put(TKey key, TValue value)
{
// Key already exists
if (_cache.TryGetValue(key, out var existingNode))
{
existingNode.Value = (key, value);
// Move to front because it was recently used
_lruList.Remove(existingNode);
_lruList.AddFirst(existingNode);
return;
}
// Add new item
var newNode = new LinkedListNode<(TKey, TValue)>((key, value));
_lruList.AddFirst(newNode);
_cache[key] = newNode;
// Evict least recently used item
if (_cache.Count > _capacity)
{
var lruNode = _lruList.Last!;
_lruList.RemoveLast();
_cache.Remove(lruNode.Value.Key);
}
}
public int Count => _cache.Count;
}
An LRU (Least Recently Used) cache is implemented by combining a Dictionary with a LinkedList. The Dictionary provides fast O(1) average-time lookup by mapping each cache key to its corresponding linked-list node, while the LinkedList maintains the order in which items were recently accessed.
The first node in the list represents the most recently used (MRU) item, and the last node represents the least recently used (LRU) item.
Whenever an item is retrieved using TryGet, its node is removed from its current position and moved to the front of the list, marking it as recently used. Similarly, when a new item is added using Put, it is inserted at the front of the list.
If the cache exceeds its configured capacity, the last node is removed from the linked list and its corresponding key is also removed from the dictionary.
This combination allows lookup, insertion, updating, and LRU eviction to be performed in O(1) average time, making it an efficient approach for implementing a custom in-memory LRU cache.
Usage Example
var cache = new LruCache<int, string>(3);
cache.Put(1, "A");
cache.Put(2, "B");
cache.Put(3, "C");
// Cache order:
// 3 -> 2 -> 1
// MRU LRU
cache.TryGet(1, out var value);
// Accessing 1 makes it most recently used:
// 1 -> 3 -> 2
// MRU LRU
cache.Put(4, "D");
// 2 is the least recently used, so it gets evicted.
// Remaining:
// 4 -> 1 -> 3
Console.WriteLine(cache.TryGet(2, out _)); // False
Console.WriteLine(cache.TryGet(1, out _)); // True
Console.WriteLine(cache.TryGet(3, out _)); // True
Console.WriteLine(cache.TryGet(4, out _)); // True
Best Practices for Cache Eviction Policies
- Choose the policy based on access patterns
- LRU (Least Recently Used): Good default for workloads with temporal locality.
- LFU (Least Frequently Used): Useful when frequently accessed items should remain cached for longer.
- FIFO: Simple and predictable, but doesn't consider how frequently or recently an item is accessed.
- Random: Very simple and sometimes effective for large caches where maintaining eviction metadata is expensive.
- MRU: Useful for workloads where recently accessed items are less likely to be accessed again soon.
- Don't rely on eviction alone
Combine an eviction policy with TTL (Time-to-Live) or expiration. An item can be frequently accessed but still become stale, so popularity alone shouldn't determine how long it remains in the cache.
- Set an appropriate cache size
A cache that is too small causes frequent evictions and low hit rates. A cache that is unnecessarily large increases memory consumption and infrastructure costs. Monitor the workload and tune the capacity accordingly.
- Monitor cache hit and miss rates
Eviction policies should be evaluated using real metrics:- Cache hit ratio
- Cache miss ratio
- Eviction rate
- Memory utilization
- Average item lifetime
- Latency
- Backend/database load
- Consider item cost, not just recency
Computational cost to regenerate the item- Size of the item
- Frequency of access
- Importance of the data
- Backend/database cost
- Avoid caching everything
Some data has little reuse or is cheap to regenerate. Caching it can consume valuable space and cause useful entries to be evicted. Cache data that provides meaningful performance or load reduction.
- Handle stale data explicitly
Eviction and freshness are different problems. Use mechanisms such as:- TTL
- Explicit invalidation
- Versioning
- Write-through/write-back policies
- Cache refresh
- Watch for cache pollution
A large number of one-time or rarely reused objects can push valuable objects out of the cache. This is particularly important with LRU, where recently accessed does not necessarily mean frequently useful.
- Consider workload changes
Cache behavior can change significantly between normal traffic, traffic spikes, batch processing, and unusual workloads. Monitor eviction behavior over time rather than tuning the policy once and assuming it will remain optimal.
- Prefer simplicity unless complexity provides measurable benefits
Start with a well-understood policy such as LRU + TTL. Move to more sophisticated policies such as LFU, TinyLFU, or cost-aware approaches when measurements show that the simpler policy is insufficient.
Summary
Caching is a fundamental technique for improving application performance by storing frequently accessed data closer to where it is needed. However, cache capacity is limited, and when a cache becomes full, it must decide which entries to remove. This process is known as cache eviction.
In this article, we take a deep dive into cache eviction policies and explore how different policies determine which data should be removed from a cache. We examine commonly used approaches such as LRU (Least Recently Used), LFU (Least Frequently Used), FIFO (First In, First Out), MRU (Most Recently Used), and Random eviction, along with their advantages, limitations, and suitable use cases.
The article also discusses important considerations when selecting an eviction policy, including access patterns, cache size, data freshness, memory usage, cache hit ratio, and application workload. Finally, we look at best practices for designing and tuning cache eviction mechanisms to achieve a balance between performance, memory efficiency, and data freshness.
The goal is to provide a practical understanding of cache eviction policies and help engineers choose the right approach for their specific systems and workloads.
Thanks