Optimize Your Cache with These 4 Cache Eviction Strategies: LRU, TLRU, LFU, MRU

The perfect eviction policy is like being able to see into the future and know what items users will need or not

We’ve reviewed six caching strategies before, focusing on the six usual methods for filling a cache from a database. Yet, we haven’t touched on 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 manage 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 like having a crystal ball that lets you see which items won’t be needed again anytime soon. 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 (discussed in 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 items used recently may 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.

1. 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.
2. Application requests D: Next, the application requests D, which is not currently in the cache.
3. Check cache full: We verify it is at capacity, meaning all three slots are filled.
4. Identify the candidate: Looking at the current items, C was the first to be added, making it the best candidate for removal.
5. Remove and insert: We remove C to make room for D.

So now, our cache holds D, B, A, and 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.

Consideration

This method is quite simple, especially if you use data structures like doubly-linked lists and hash maps.

LRU is highly effective for systems where items will likely 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 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 intelligence layer. In TLRU, items are evicted based on their last accessed time and 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 three 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 one second, B with a TTU of three seconds, and C with a TTU of three seconds, and at this point, A is the most recently accessed item.

Current cache state: A(2) B(3) C(3).

1. Identify eviction candidate: All three slots are full, so we remove C to make space, similar to what we would do in a standard LRU scenario.
2. Cache update: We remove C and add D with a three-second TTU (it’s up to you). Now, the cache consists of D (TTU: 3s), A (TTU: 2s), B (TTU: 3s).
3. Cache check after two seconds: A’s time expires, so it is removed. The cache is now D (TTU: 1s), B (TTU: 1s).
4. Expiration check after one 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 regularly, 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, instead of using a Time to Use (TTU) value in this strategy, 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 first eliminates items with the lowest access frequency, and we record how often each item has been accessed.

How it works?

Let’s say we have a cache that can hold three items, and it’s already filled with A (freq: 1), B (freq: 2), and C (freq: 4).

1. An application requests A from a cache that is already full, increasing the frequency of A. So now we have A (freq: 2), B (freq: 2), C (freq: 4).
2. The app requests A again, resulting in A (freq: 2), B (freq: 2), C (freq: 4).
3. Client needs A again. Maybe it’s viral and makes the cache look like A (freq: 3), B (freq: 2), C (freq: 4).
4. The app then requests D, and the cache evicts B, which has the lowest frequency. This results 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 ten accesses, don’t let that number climb 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, you can benefit from both the frequency and recency of item accesses.

4. Most Recently Used (MRU)

At first glance, MRU may seem like the least helpful strategy, especially since it’s the 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 three 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.

Author note

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, etc.