Cache Eviction Policies

Jill manages a trendy news website. Lately, her website has grown in popularity and receives thousands of visits a day. As a result of the increased traffic, she added a cache to help decrease web traffic load on our server and help get content to her visitors faster. However, visitors aren’t always going to the same page. The web traffic is split between pages that host news on topics such as sports, stocks, and fashion. This is where things get tricky — How does she decide which content should go into the cache, and which content should leave?

In this article, we’ll discuss concepts related to managing the data within a cache. Throughout, we will be addressing questions such as:

• What strategies exist to manage cache data?
• When should data enter a cache?
• When should it leave?
• How are updates to data handled?

Before we dive in, let’s briefly review important concepts about caches.

A brief review of caching concepts

Remember the following about caches:

• A cache is a layer of fast and temporary storage of data.
• Retrieving from non-cache memory (e.g., a hard drive) is very slow.
• A cache stores the result of requests to avoid retrieval from non-cache memory.
• A cache hit is when a request comes in that has its response stored in the cache.
• A cache miss occurs when a request is not in the cache and needs retrieval from non-cache memory.

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.

Let’s discuss some strategies that help make sure our cache contains relevant data.

Cache eviction policies

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. We need to consider what data we keep or remove over time. This dilemma is the core purpose behind cache eviction policies — specific algorithms for managing data in a cache.

Some of the most common policies are:

• Least Recently Used (LRU)
• Most Recently Used (MRU)
• Least Frequently Used (LFU)

To help visualize these policies, let’s imagine we run a movie site, and we want to cache movie information. We have a cache that can hold four movies. This number is small so that we can illustrate the policies. We have the following log of recent movie visits:

- 12:30 PM: Trash Pandas: The Musical 

- 12:45 PM: Rats of New York 

- 1:30 PM: Honey I Bought A Moose 

- 1:43 PM: Rats of New York 

- 1:50 PM: Trash Pandas: The Musical 

- 1:59 PM: 12 Angry Birds

Let’s assume the cache was empty when we began. It would look like this:

• EMPTY
• EMPTY
• EMPTY
• EMPTY

First, at 12:30, we get a request for “Trash Pandas: The Musical.” The cache is empty, so we have a cache miss. We retrieve “Trash Pandas: The Musical” from non-cache memory and send it to the user. “Trash Pandas: The Musical” also takes first place in the cache.

• (12:30) Trash Pandas: The Musical
• EMPTY
• EMPTY
• EMPTY

Then at 12:45, a request for “Rats of New York” comes in. Our cache currently contains “Trash Pandas: The Musical,” so we have another cache miss. The system retrieves the movie information from non-cache memory and sends it to the user. “Rats of New York” takes the second cache spot.

• (12:30) Trash Pandas: The Musical
• (12:45) Rats of New York
• EMPTY
• EMPTY

At 1:30, “Honey I Bought A Moose” gets requested, causing another cache miss. The system retrieves the information from non-cache memory and stores it in the third cache spot.

• (12:30) Trash Pandas: The Musical
• (12:45) Rats of New York
• (1:30) Honey I Bought A Moose
• EMPTY

At 1:43, we get a request for “Rats of New York.” We are ready this time. Our cache already contains that movie’s information. Our cache sends information about “Rats of New York” back to the user much faster than a non-cache memory retrieval. Nothing in our cache needs to change, except the time when “Rats of New York” was last accessed (now 1:43).

• (12:30) Trash Pandas: The Musical
• (1:43) Rats of New York
• (1:30) Honey I Bought A Moose
• EMPTY

At 1:50, we receive another request for “Trash Pandas: The Musical.” This movie is already stored in our cache and is quickly retrieved and sent to the user. The cache updates the last access time for “Trash Pandas: The Musical.”

• (1:50) Trash Pandas: The Musical
• (1:43) Rats of New York
• (1:30) Honey I Bought A Moose
• EMPTY

At 1:59, “12 Angry Birds” has a request. Yet another cache miss. The system retrieves the information from non-cache memory and stores it in the final cache spot.

• (1:50) Trash Pandas: The Musical
• (1:43) Rats of New York
• (1:30) Honey I Bought A Moose
• (1:59) 12 Angry Birds

Now our cache is full. If a new movie request comes in, which isn’t already in the cache, something will have to leave to replace it. Choosing which movie gets removed is the responsibility of an eviction policy. Let’s add one more request:

* 2:30 PM: Moles: Dig It

A different movie will have to go when the “Moles: Dig It” request comes in. Let’s explore what will happen using each eviction strategy we listed earlier:

Least recently used

The Least recently used (LRU) eviction policy replaces the item not requested for the longest time. In our movie site example, the movie removed will have the earliest time in the cache listing.

When the request comes in for “Moles: Dig It” the movie accessed least recently, “Honey I Bought A Moose” at 1:30, will get replaced.

Before the removal:

• (1:50) Trash Pandas: The Musical
• (1:43) Rats of New York
• (1:30) Honey I Bought A Moose
• (1:59) 12 Angry Birds

After the removal:

• (1:50) Trash Pandas: The Musical
• (1:43) Rats of New York
• (1:59) 12 Angry Birds
• (2:30) Moles: Dig It

The LRU policy is implemented using a timestamp for last access. This policy requires some extra memory and needs to update the timestamps in the cache. Under the LRU replacement policy, if a new movie were to come in, “Rats of New York” would be next to get replaced.

The LRU policy can better consider which items in the cache have been recently useful. These characteristics make LRU perform well when items are used frequently for a while, then usage drops. This is ideal in our scenario and closely mimics real-world movie theaters where movies rise in popularity on initial release and then are replaced by the next most popular release.

Most recently used

Let’s look at a different scenario — a movie club that has favorite movies. The club watches them one after the next, then starts over once they finish. If we were to use an LRU policy, we would be evicting the movies coming up the soonest! This is where the Most recently used (MRU) policy comes into play.

The MRU policy replaces the cache element used most recently. While we could think of MRU as the opposite of LRU, they need the same data and are similar to implement. In our movie example, the movie with the latest time will be the one to be removed. Let’s again set the cache to when it first became full:

• (1:50) Trash Pandas: The Musical
• (1:43) Rats of New York
• (1:30) Honey I Bought A Moose
• (1:59) 12 Angry Birds

Now, at 2:30, the “Moles: Dig It” request will come in. Remember, under LRU, “Honey I Bought A Moose” was replaced. MRU selects “12 Angry Birds” for removal, as this film was most recently requested.

Before the removal:

• (1:50) Trash Pandas: The Musical
• (1:43) Rats of New York
• (1:30) Honey I Bought A Moose
• (1:59) 12 Angry Birds

After the removal:

• (1:50) Trash Pandas: The Musical
• (1:43) Rats of New York
• (1:30) Honey I Bought A Moose
• (2:30) Moles: Dig It

MRU is useful for situations where the longer an item hasn’t been used, the more likely it will come up next. The movie club scenario illustrates this kind of situation.

However, what if items tend to stay frequently accessed over time? Perhaps there are some movie classics that people keep coming back to. The following policy would help deal with that situation.

Least frequently used

The Least frequency used (LFU) policy will remove the item in the cache used the least since its entry. Unlike LRU and MRU, LFU does not require access time storage. Instead, it stores the number of accesses since entry. Let’s revisit the set of initial requests.

- 12:30 PM: Trash Pandas: The Musical 

- 12:45 PM: Rats of New York 

- 1:30 PM: Honey I Bought A Moose 

- 1:43 PM: Rats of New York 

- 1:50 PM: Trash Pandas: The Musical 

- 1:59 PM: 12 Angry Birds

We can see that “Trash Pandas: the Musical” and “Rats of New York” have been accessed twice. Meanwhile, “Honey I Bought A Moose” and “12 Angry Birds” have each been only accessed once. The structure of the cache might look like this:

• (2) Trash Pandas: The Musical
• (2) Rats of New York
• (1) Honey I Bought A Moose
• (1) 12 Angry Birds

When the request for “Moles: Dig It” comes in, “Honey I Bought A Moose” or “12 Angry Birds” will be replaced, depending on the policy implementation. We could resolve this “tie” in various ways, such as items’ order in the cache or their last access time.

This policy is practical when some items are used repeatedly over time. By storing a counter instead of a timestamp, LFU tends to use less memory than MRU or LRU.

LFU can be problematic when an item is used frequently, and then usage drops off. This usage can cause an item to become “stuck” in the cache despite not being used.

Wrap up

We’ve now learned some of the fundamentals of managing data inside of a cache using eviction policies. Let’s take a moment to review what we’ve learned:

• Cache eviction policies are specific algorithms for how to manage data in a cache. These algorithms specifically focus on how our applications decide to remove data.
• Least recently used (LRU) eviction policy removes the item used the least recently.
• Most recently used (MRU) eviction policy removes the item used the most recently.
• Least frequently used (LFU) eviction policy removes the item used the least often.

We have only scratched the surface of the many different eviction policies that exist. To dive deeper into various policies, explore the extensive list here.