LRU Cache

Although the computer cannot see into the future and know for certain what a user’s next request will be, there are applications that enable the computer to make an educated guess as to what requests are upcoming. A number of cache eviction policies attempt to predict future requests based on looking at past requests. One such strategy is the least-recently-used eviction policy. In fact, least-recently-used, or LRU for short, is one of the most popular eviction policies in use today.

The term “LRU” describes which item we’ll be evicting. That is, we will evict whichever item was least recently used; in other words, which item was least recently requested. For instance, if we have a cache containing the items [1, 2, 3, 4], and our app keeps receiving additional requests for 1, 2, and 3, but hasn’t received a request for 4 in some time, it’s the 4 that will be evicted from our cache next.

The idea behind LRU is that we’re guesstimating that if we haven’t received a request for item 4 in a while, it’s likely because item 4 is becoming increasingly unpopular. And if item 4 is no longer popular, we’re probably not going to receive a request for it in a long time, if at all.

Note that LRU is based on the farthest-in-future eviction policy in that our goal is to evict the item that will be requested farthest into the future. It’s just that we use the idea of LRU to predict which item that’ll be. In other words, if an item is least recently used, it’s probably not in vogue right now and won’t be requested again soon.

A cache that uses the LRU eviction policy is called an LRU cache. However, note that this name can be a bit misleading. It kind of sounds as if we’ll be caching LRU items, while in fact the opposite is true; it’s a cache with an LRU eviction policy. So LRU describes which items we evict from the cache, not the ones we keep. And indeed, we keep the items that were most recently used.

LRU may not make sense in every application, but it’s reasonable for many of them. This is because there are many contexts in which we can determine a request’s popularity by how recently someone made that request.

LRU in Action

To see LRU in action, let’s walk through an LRU cache example using the same request sequence we did when looking at the clairvoyant eviction policy. To speed things up, we’ll jump to the step where we first filled the cache:

Okay, let’s LRU!

Our next request is a 6. This is a cache miss, so we must evict something from the cache to make space for the 6. With LRU, we look leftward to see which of the past items was least recently “used”—that is, least recently requested.

Of the items in the cache, the 3 was used least recently, so we evict it and replace it with the 6:

Note that I’m no longer displaying the complete list of requests to come, in line with the fact that we’re not clairvoyant.

The next request is for the 5. We have a cache hit, which is gratifying:

We now request a 4, which is a cache miss. Of the items in the cache, the 2 was least recently used, so we replace the 2 with the 4:

Next up, we have a 3. Ugh, we had the 3 in our cache a few steps ago, but we evicted it. Whatever, it’s okay.

With this cache miss, we look at the items in the cache and determine which of them was least recently requested. Looking back at our previous request sequence, note that the 1 was used less recently than any of the other items in the cache. As such, we replace the 1 with the 3:

The next request is 6, and that’s a cache hit. Sweet.

The 2 is up next. It’s been some time since we’ve seen a request for a 2, so unfortunately, it’s not in the cache. With this cache miss, we evict the 5, as it was least recently used:

Next up, we have a 4. Cache hit!

The last request is a 1, which is a cache miss. We evict the 3 since the 6, 2, and 4 were all more recently used:

If we count the cache misses here, including the initial requests used to fill the cache, we have a tally of 9. This isn’t as good as the clairvoyant policy that yielded only 7 cache misses, but because the clairvoyant policy is only theoretical anyway, our more practical policy of LRU isn’t half bad.

Now, the truth is that this example wasn’t the ideal scenario for an LRU policy since LRU is essentially looking for trends, and no particular value was trending. The requests were kind of all over the place.

But the LRU policy is good for scenarios where requests trend and fade with time. In our cheapest-product search app example, we’d hope that if one person is searching for a particular product, this is a signal that the item is becoming popular, and other people will search for that same item.

Another practical example of this is a web browser. When one uses their browser to search the web, we might assume that the same user will revisit some of those same pages again in the near future. For this particular user, those pages are currently interesting and therefore “trendy.”

So, that’s the whole idea of LRU; we’re taking a bet that current requests are trending, and because they’re trending, we’ll probably see those same requests made again soon.

Take the following sequence:

If you examine these numbers carefully, you might notice that items trend a little bit before the next “hot” number becomes popular. This is the ideal scenario that an LRU policy is designed for.

Care to take a guess at how many cache misses occur here if we use an LRU policy and our cache can hold up to 4 items? You could also take a pencil and paper and figure it out.

There are a whopping 63 requests here, but only 8 cache misses, and that includes the 4 cache misses that initially fill the cache. This sequence was practically made for LRU.