Part 7: Understanding System Design - Caching Eviction Policies

Sponsored by

Hello “👋”

Welcome to another week, another opportunity to become a Great Backend Engineer.

Today’s issue is brought to you by LaunchFast. Launch your web apps in hours with these  Astro, Next.js, and SvelteKit boilerplates.

Before we get down to the business of today. Part 7 of Understanding System Design.

I have a gift for you: You will love this one.

Invest before this company becomes a household name

What if you had the opportunity to invest in the biggest electronics products before they launched into big box retail, would you?

Ring changed doorbells and Nest changed thermostats. Early investors in these companies earned massive returns, but the opportunity to invest was limited to a select, wealthy few. Not anymore. RYSE has just launched in 100+ Best Buy stores, and you're in luck — you can still invest at only $1.50/share before their name becomes known nationwide.

They have patented the only mass market shade automation device, and their exclusive deal with Best Buy resembles that which led Ring and Nest to their billion-dollar buyouts.

Learn how you can become a shareholder.

Now, back to the business of today.

In the previous edition, I discussed one of the system's components: Distributed Caching. I then discussed distributed caching further and introduced you to different caching strategies and how to implement them.

In this episode, I will explore the Distributed Caching component more deeply and explore different caching eviction policies and caching layers.

Overview of Caching Eviction Policies

A cache is a short-lived or transient storage. The small cache limits the amount of data stored.

With this knowledge of cache engines, we need to figure out how to remove, invalidate, and add data to a cache.

Let’s take an example from a real-world scenario.

Solomon manages a trendy website called Masteringbackend, where different backend engineers worldwide come to read, study, and become great backend engineers.

However, Solomon recently noticed a problem: the response for each article is very slow, and users have to wait longer for pages to load before consuming the content.

So Solomon introduced a Caching system and strategy to solve this problem.

It worked.

The website's resources and pages began to load faster, and students enjoyed watching courses and taking practice projects on the website.

Another problem was that there were many pages, resources, courses, etc., and many students’ favorite ones, some of which were others. Solomon cannot cache everything because of the cache engine's memory limit.

Therefore, It becomes difficult for Solomon to determine which content should be cached and for how long.

Because for a cache to be effective, we want to maximize the number of cache hits and reduce the number of cache misses. We want the chance to be as high as possible that a response is in the cache when a request comes in.

This is exactly where Caching Eviction Policies come in.

What are Caching Eviction Policies?

Cache eviction policies are algorithms that determine how to manage data in a cache.

Caches are small because cache memory is more expensive to produce and purchase. The small size of the cache limits the amount of data we can store, so we need to consider what data we keep or remove over time.

When the cache is full, the algorithm must choose which items to discard to accommodate the new ones.

Many algorithms are used to manage the memory of a cache:

• Least Recently Used (LRU)

• Most Recently Used (MRU)

• Least Frequently Used (LFU)

• First In First Out (FIFO)

• Last In First Out (LIFO)

• Time To Live (TTL)

• Random Selection

Let's use Solomon's website as an example to help visualize each policy. Let’s assume Solomon offers four courses on Masteringbackend that students can take.

1. Become a Rust Backend Engineer

2. Become a Node.js Backend Engineer

3. Become a Python Backend Engineer

4. Become a Ruby Backend Engineer

Next, let’s assume that our cache is empty and can only accept 4 data for this illustration. Let’s represent it as shown below:

• Empty

• Empty

• Empty

• Empty

First, at 12:30, a user requested the “Become a Rust Backend Engineer” course. The request checks the cache and found nothing (this is a miss). Therefore, the request accessed the data in the database, returned it to the user, and it was added to the cache with the timestamp for subsequent as shown below:

• [12:30] Become a Rust Backend Engineer

• Empty

• Empty

• Empty

Next, let’s assume that several requests came in and the cache is filed with data based on different timestamps as shown below:

• [12:30] Become a Rust Backend Engineer

• [1:45] Become a Node.js Backend Engineer

• [2:30] Become a Ruby Backend Engineer

• [1:20] Become a Python Backend Engineer

If a hit (an item found in the cache) occurs at any point, the item's timestamp will be updated to become the most recent. Keep this in mind.

Now, our cache is full. If a new course request comes in and that course isn’t already in the cache, a course must leave the cache so the new one can replace it. Choosing which course gets removed is the responsibility of an eviction policy.

Let’s add one more request:

* 2:50 PM: Become a Golang Backend Engineer

A different course will have to go when the “Become a Golang Backend Engineer” request comes in. Let’s explore what will happen using each eviction strategy we listed earlier:

Least Recently Used (LRU)

The Least recently used (LRU) eviction policy replaces the item not requested or used for the longest time. The idea is to keep the most frequently used items in the cache, assuming they will be requested again.

In our course site example, the course removed will have the longest time in the cache listing. When the request comes in for “Become a Golang Backend Engineer” at 2:50, the course accessed least recently, “Become a Rust Backend Engineer,” at 12:30, will get replaced.

Before the removal:

• [12:30] Become a Rust Backend Engineer

• [1:45] Become a Node.js Backend Engineer

• [2:30] Become a Ruby Backend Engineer

• [1:20] Become a Python Backend Engineer

After the removal:

• [1:45] Become a Node.js Backend Engineer

• [2:30] Become a Ruby Backend Engineer

• [1:20] Become a Python Backend Engineer

• [2:50] Become a Golang Backend Engineer

The LRU policy uses Timestamps for the last access, so position in the cache doesn’t matter. This policy requires some extra memory and updating the timestamps in the cache.

The LRU policy can be implemented using a Linked List data structure, where each node represents a cached item, and the head of the list is the most recently used item sorted by timestamp.

Whenever an item is accessed, it is moved to the head of the list (by updating the timestamp to recent), and whenever an item needs to be evicted, it is taken from the tail of the list.

Most Recently Used (MRU)

The MRU is the opposite of LRU, where new ones in the cache replace the most recently used data.

In our course site example, the course removed will have the earliest time in the cache listing. When the request for “Become a PHP Backend Engineer” comes in at 3:00, the course accessed most recently, “Become a Golang Backend Engineer,” at 2:50, will be replaced.

Before the removal:

• [1:45] Become a Node.js Backend Engineer

• [2:30] Become a Ruby Backend Engineer

• [1:20] Become a Python Backend Engineer

• [2:50] Become a Golang Backend Engineer

After the removal:

• [1:45] Become a Node.js Backend Engineer

• [2:30] Become a Ruby Backend Engineer

• [1:20] Become a Python Backend Engineer

• [3:00] Become a PHP Backend Engineer

The MRU needs the same data as the LRU and is similar to the LRU implementation using Linked List, except new data replaces the most recently accessed data in the cache.

Least Frequently Used (LFU)

The LFU policy removes items from the cache that have been used the least since its entry. Unlike LRU and MRU, the LFU policy does not require timestamps. Instead, it stores the number of accesses since entry.

In our course site example, the count will be assigned to all the items in the cache that represent the total number of access for a particular course.

Here’s how the cache will look like using the LFU policy:

• [5] Become a Node.js Backend Engineer

• [2] Become a Ruby Backend Engineer

• [4] Become a Python Backend Engineer

• [3] Become a PHP Backend Engineer

The number represents the number of times a particular course has been accessed.

Next, the course that will be replaced from the cache listing when the request for “Become a Golang Backend Engineer” comes in will be “Become a Ruby Backend Engineer” because it has the least count (2).

Before the removal:

• [5] Become a Node.js Backend Engineer

• [2] Become a Ruby Backend Engineer

• [4] Become a Python Backend Engineer

• [3] Become a PHP Backend Engineer

After the removal:

• [5] Become a Node.js Backend Engineer

• [1] Become a Golang Backend Engineer

• [4] Become a Python Backend Engineer

• [3] Become a PHP Backend Engineer

The count number will be updated anytime there is a hit in the cache. For instance, if a user requests “Become a PHP Backend Engineer,” there will be a hit since it is already in the cache, and the number will be incremented to (4).

You can also implement a policy that reverses or is opposite the LFU policy by removing items with the highest count number.

First In First Out (FIFO)

FIFO is a cache eviction policy that removes the item that was added first to the cache without using timestamps or counts. It replaces items based on the position in the cache.

The FIFO policy is a good example of a queue. For instance, if you’re waiting to order pizza at McDonald's, the waiter or waitress will serve the first person in the queue. That means the first person to come in will be the first person to go out.

Using our course example:

If a new course is requested, “Become a Node.js Backend Engineer” will be replaced from the cache listing when the request for “Become a Rust Backend Engineer” comes in because it has the first position in the cache (0).

Before the removal:

• [0] Become a Node.js Backend Engineer

• [1] Become a Ruby Backend Engineer

• [2] Become a Python Backend Engineer

• [3] Become a PHP Backend Engineer

After the removal:

• [0] Become a Golang Backend Engineer

• [1] Become a Python Backend Engineer

• [2] Become a PHP Backend Engineer

• [3] Become a Rust Backend Engineer

The numbers assigned are not “counts”. However, I used it to show the position of each item in the queue where [0] means the first entry and [3] represents the last entry.

Last In First Out (LIFO)

LIFO cache eviction policy is the opposite of FIFO, which removes the item added last to the cache without using timestamps or counts.

The FIFO policy is a good example of a stack. For instance, you could stack three bags of Rice to be used later in your family. When a family member wants to take a bag from the store (stack), the person will start from the top, the last to be stacked.

Now, let’s relate this with our course site example:

If a new course is requested, “Become a PHP Backend Engineer” will be replaced from the cache listing when the request for “Become a Rust Backend Engineer” comes in because it is at the top of the cache (last to enter).

Before the removal:

• [0] Become a Node.js Backend Engineer

• [1] Become a Ruby Backend Engineer

• [2] Become a Python Backend Engineer

• [3] Become a PHP Backend Engineer

After the removal:

• [0] Become a Golang Backend Engineer

• [1] Become a Python Backend Engineer

• [2] Become a PHP Backend Engineer

• [3] Become a Rust Backend Engineer

Time To Live (TTL)

TTL is a cache eviction policy that removes items that have expired their time-to-live. Each item added to the cache has a predefined time-to-expiration in this policy. The idea is to keep the most up-to-date items in the cache, assuming they are more relevant and useful than outdated ones.

TTL is a flexible and adaptive policy that works well for applications that have dynamic and time-sensitive data, such as news, weather, or stock prices.

Let’s try to use our course example:

If a new course is requested, “Become a Node.js Backend Engineer” will be removed from the cache listing when the request for “Become a Rust Backend Engineer” comes in because it expires in 1 hour compared to others that have 2 hours and above.

Before the removal:

• [1h] Become a Node.js Backend Engineer

• [2h] Become a Ruby Backend Engineer

• [4h] Become a Python Backend Engineer

• [3h] Become a PHP Backend Engineer

After the removal:

• [5h] Become a Rust Backend Engineer

• [2h] Become a Ruby Backend Engineer

• [4h] Become a Python Backend Engineer

• [3h] Become a PHP Backend Engineer

The developer assigns the duration. Therefore, any duration can be assigned to any item depending on if the item is accessed more frequently.

Random Selection

In this cache eviction policy, the system randomly selects a data item from the cache to give space when necessary.

This policy is not advisable to be used. However, it has its advantages and disadvantages.

I hope this gives you a complete breakdown of the different caching eviction policies and how to implement them.

Next, let’s look at the Caching layers and the available types of Caching layers.

Caching layers

A caching layer is a component in a software architecture that stores temporary copies of data to serve future requests for that data more quickly.

Its purpose is to improve a system's performance and efficiency by reducing the time and resources required to fetch data from its source, such as a database, API, or external service.

Below are some of the available caching layers:

• DNS Cache

• Client Side Cache

• Content Delivery Network(CDN)

• Application Server Cache

• Database Cache

I have already created a detailed article on my blog that reviews each of these Caching Layers to help you learn more.

That will be all for this week. I like to keep this newsletter short.

Today, I discussed distributed caching further and introduced you to different caching eviction policies, how to implement them, and different Caching Layers.

Next week, I will start exploring databases as one of the components of system design.

Don’t miss it. Share with a friend

Did you learn any new things from this newsletter this week? Please reply to this email and let me know. Feedback like this encourages me to keep going.

See you on Saturday.

Remember to get the LaunchFast Boilerplate. Launch your web apps in hours with these  Astro, Next.js, and SvelteKit boilerplates.

Top 5 Remote Backend Jobs this week

Here are the top 5 Backend Jobs you can apply to now.

👨‍💻 Resistant AI
✍️ Senior Software Engineer
📍Remote, Prague
💰 Click on Apply for salary details
Click here to Apply for this role.

👨‍💻 Homepage
✍️ Backend Developer
📍Remote, Poland
💰 Click on Apply for salary details
Click here to Apply for this role.

👨‍💻 BandLab Technologies
✍️ Senior Backend Engineer, Ads Team
📍Remote, Asia, Africa, Europe
💰 Click on Apply for salary details
Click here to Apply for this role.

👨‍💻 WunderGraph
✍️ Senior Golang Engineer - Remote (EMEA)
📍Remote, Go, Golang
💰 Click on Apply for salary details
Click here to Apply for this role.

Want more Remote Backend Jobs? Visit GetBackendJobs.com

Backend Engineering Resources

1. Backend Engineering Hub

2. All Backend Books

3. Visit our Backend Store

4. Join our Community

LAST WORD 👋 

How am I doing?

I love hearing from readers, and I'm always looking for feedback. How am I doing with The Backend Weekly? Is there anything you'd like to see more or less of? Which aspects of the newsletter do you enjoy the most?

Hit reply and say hello - I'd love to hear from you!

Stay awesome,
Solomon

I moved my newsletter from Substack to Beehiiv, and it's been an amazing journey. Start yours here.