Discover more from Devtrovert
Optimize Your Cache with These 4 Cache Eviction Strategies
The perfect eviction policy is like having a way to see into the future, knowing what items users will need or not need later on.
We’ve gone over 6 Caching Strategies before, focusing on the six usual methods for filling a cache from a database. Yet, we haven’t touched on the subject of how cache items expire or get removed.
This is a separate issue that’s all about balancing cache efficiency with a great user experience, and it typically doesn’t have much to do with the database itself.
“Why do we need this?”
Without a cache eviction strategy, we won’t be able to achieve peak performance from our caching mechanism.
An eviction strategy helps in managing the cache size and ensures that the most relevant data is readily available, thereby reducing latency and improving system efficiency.
“What’s the idea cache eviction policy?”
The ideal eviction policy is sort of like having a crystal ball that lets you see which items won’t be needed again anytime soon. Basically, it’s all about guessing which items will be useful in the future.
That said, there are four typical strategies we can consider.
1. Least Recently Used (LRU)
This is probably the most familiar strategy, as many libraries use it for cache eviction, sometimes in a variation called TLRU (the next section).
The idea behind LRU is to remove the items that haven’t been used for the longest time first. This works well when you think that items used recently will probably be needed again soon.
How it works?
Imagine we have a cache that can hold up to three items. It already contains
A, B, C, with A being the most recently accessed. Now, we want to get item B.
Check Cache: We see that item B is already in the cache, right? We return B and, at the same time, set B as the most recently accessed. Now the cache is:
B, A, C.
Application Requests D: Next, the application requests D, which is not currently in the cache.
Check cache full: We verify that the cache is at its capacity, meaning all three slots are filled.
Identify the candidate: Looking at the current items, C was the first one to be added, making it the best candidate for removal.
Remove and insert: We remove C to make room for D.
So now, our cache holds
D, B, Aand it’s worth noting that A becomes the next likely candidate for eviction.
“What happens if A is accessed now? Would A still be the next candidate for eviction?”
If A is accessed, it moves to the front of the line as the most recently used item. So no, A wouldn’t be the next one up for eviction, the new sequence would be
A D B.
This method is quite simple to put into action, especially if you’re using data structures like doubly-linked lists and hash maps.
LRU is highly effective for systems where items are likely to be accessed again shortly. However, if your system mainly involves one-time reads, then this strategy might not be the best fit.
In cases where an item is read only once, it will still remain in the cache, taking up space until it eventually gets removed.
2. Time-aware Least Recently Used (TLRU)
This approach takes LRU to the next level by adding an extra layer of intelligence. In TLRU, items are evicted based on not just their last accessed time but also another variable, known as Time to Use (TTU).
The TTU value acts like a timer, setting a duration for how long each item should be considered ‘fresh’ or valid within the cache.
By including this additional TTU criterion, TLRU ensures that the first items to be evicted are those that are not only old, but also less likely to be accessed anytime soon.
How it works?
Okay, let’s imagine we have a cache that can hold 3 items, and we assign each item a Time to Use (TTU) value.
Our application requests D from a cache that’s already full, containing A with a Time To Use (TTU) of 1 seconds, B with a TTU of 3 seconds, and C with a TTU of 3 seconds and at this point, A is the most recently accessed item.
Current Cache State:
A(2) B(3) C(3).
Identify eviction candidate: All three slots are full, so we opt to remove C to make space, similar to what we would do in a standard LRU scenario.
Cache update: We remove C and add D with a TTU of 3 seconds (it’s up to you). Now, the cache consists of
D (TTU: 3s), A (TTU: 2s), B (TTU: 3s).
Cache check after 2 seconds: A’s time expires, so it is removed, the cache is now
D (TTU: 1s), B (TTU: 1s).
Expiration check after 1 second: One more second passes, and both D and B expire, so they are removed from the cache accordingly.
“When do expired items get evicted?”
There are multiple strategies for evicting expired cache items, and you can even mix and match:
One approach is to scan for expired items when a new item needs to be added.
Another option is to run periodic cleanups, sweeping the cache at regular intervals like every second or millisecond.
Or you could evict an expired item right when someone tries to access it.
3. Least Frequently Used (LFU)
So in this strategy, instead of using a Time to Use (TTU) value, we monitor another factor called frequency (freq). The idea is to keep items in the cache that are accessed more often, assuming these are the ones users will need again soon.
LFU eliminates items with the lowest access frequency first, and we maintain a record of how often each item has been accessed.
How it works?
Let’s say we have a cache that can hold 3 items, and it’s already filled with A (freq: 1), B (freq: 2), and C (freq: 4).
An application requests A from a cache that is already full, increase freq of A, so now:
A (freq: 2), B (freq: 2), C (freq: 4).
The app requests A again, , resulting in
A (freq: 2), B (freq: 2), C (freq: 4).
Client need A again, maybe it’s viral, making the cache:
A (freq: 3), B (freq: 2), C (freq: 4).
The app then requests D, and the cache evicts B, which has the lowest frequency and resulting in:
A (freq: 3), D (freq: 1), C (freq: 4).
“What happens if my post gets cached, goes viral for a day with 1 million hits, but then isn’t needed anymore?”
That’s a valid worry, in an LFU approach, the focus is on frequency, not on the time the item has spent in the cache. This means the post could linger in the cache indefinitely, even if it’s no longer relevant.
To address this issue when using a frequency-based strategy, here are three solutions that come to mind:
We could set an upper limit for the frequency count. Say, if a post reaches 10 accesses, don’t let that number climb any further.
Implement a mechanism that gradually lowers the frequency counters over a set period, making older items more likely to be evicted.
Or a hybrid approach that combines LFU and LRU, this way, you can benefit from both the frequency and the recency of item accesses.
4. Most Recently Used (MRU)
At first glance, MRU may seem like the least useful strategy, especially since it’s the complete opposite of LRU.
MRU operates on the idea that the most recently accessed items are the least likely to be needed soon.
Doesn’t make sense? Let’s look at how it works.
How it works?
Imagine you’re designing a loop playlist for an audio player that has a cache with only 3 slots. User A has a playlist with four songs: A, B, C and D.
Initially, the cache is filled with the first three songs: A, B, and C.
When the loop starts, song D is next in line but the cache is already full.
Determine the candidate: This is where MRU shines, the most recently played song is C, and in a loop playlist, C won’t be played again until A, B, and D have all been played.
Time for eviction: We remove song C from the cache to make room for song D.
Like the other strategies, MRU fits well in particular scenarios. If you’re confident that the items you’re using now won’t be needed again soon, MRU could be the right choice for you.
Each cache eviction strategy is good for specific needs, but if you want something simple and useful in many cases, LRU or TLRU are good picks. But remember, you can use these strategies not just for database cache but also for client-side cache (like mobile apps), CDN,…