Eviction Policies

Here’s a bit of cache jargon I’m going to use going forward. The common term for deleting something from the cache is to evict it. (It sounds harsh, I know.) Similarly, an eviction policy is an algorithm that decides what data we should evict from the cache.

Computer scientists have proposed a whole slew of different eviction policies over the years. However, the trick is to find the most efficient eviction policy for our cache. To define what it means for an eviction policy to be efficient, let me first introduce a few more caching terms.

Recall that each time an application makes a request for data, it first checks to see if the data is in the cache. If it is, this is called a cache hit. Cache hits are good since it means that the app can grab the data from the cache rather than fetch the data from an external source. On the other hand, if an app makes a request and the data is not in the cache, this is known as a cache miss. Whenever there is a cache miss, the app has no choice but to look for the data on the Internet or wherever the external data source is.

We can use these terms to help define what it means to have an efficient eviction policy. That is, an efficient eviction policy works to increase cache hits and decrease cache misses. (We’ll soon see that we accomplish this by trying to only store data that we’ll need again in the future.) The more requests that our app can fulfill by getting data from the cache, the less time our app needs to spend searching the web.

In sum, the more efficient our cache is, the faster our software will run.

Farthest-in-Future Eviction Policy

Let’s think about how we might design an efficient eviction policy.

Ideally, we’d evict data that will never be requested ever again. After all, the whole point of caching is to quickly deliver data on the second and third time it’s requested. So, if there will never be another future request for a particular item, we can safely evict its data. This enables us to save room for data that we will request again at some point. (How will we know what data will or won’t be requested again? Good question, but hold onto it for now.)

Now, even if all the products in our sample app will be requested again at some point, we can still make our eviction policy more efficient by evicting data that will be requested farthest into the future. Let’s see an example of what I mean.

Here’s a cache that stores up to four items:

Right now, the cache is empty, which, incidentally, is called a cold cache. (I like calling it a cold hard cache, but no one else calls it that.)

To keep the diagrams nice and small, instead of requesting items such as a “Vroom-Master,” we’ll be requesting integers. So, imagine in your mind’s eye that each integer represents some particular physical product.

Here’s an example sequence of requests we’ll be making, from left to right:

Let’s begin to make our requests. First, we request the 3. There’s plenty of room in the cache, so we cache the 3:

We do the same for the next three requests, filling up the cache:

Next, we request the 6. The 6 is not currently in the cache, so this is a cache miss. The previous requests were also cache misses, but this is the first cache miss we encounter where the cache is full.

Because our cache is full, we need to evict one of the cache’s current items if we’re going to cache the 6. And so, we look to our eviction policy to decide which item we’ll evict.

If we look ahead to our future requests (those to the right of the 6), we’ll see that of all the items currently in our cache, the 1 is the one we’ll be requesting farthest into the future. That is, the 3, 5, and 2 will all be requested sooner than the 1. This is what I mean by the term farthest-in-future eviction policy; we evict whichever item will be requested later than all other items in the cache.

In this case, we’ll evict the 1 and replace it with the 6:

Next up, a 5 is requested. We happen to have a 5 in the cache, so we have our first cache hit!

We saved time from having to request the 5 from the web. Also, we don’t have to evict anything since we’re not inserting any new data into the cache.

Next, a 4 is requested. This is a cache miss, but what item to evict?

The 3, 2, and 6 will all be requested again soon, but there won’t be a request for 5 again in the near future. Perhaps there will be in a future batch of requests, but there aren’t any 5’s in the current list of requests. So let’s evict the 5 and cache the 4:

Next, we request a 3. That’s a cache hit:

We also have cache hits with the next three requests:

The final request in this sequence is a 1. That’s a cache miss. As to which item to evict, it’s hard to say since we’re not yet privy to whatever requests may come next.

In any case, the walk-through shows what it means to evict items that will be requested farthest into the future. But now let me explain why this eviction policy is ideal. To some, this may already be intuitive, but I’ll spell it out anyway.

If we evict items that are about to be requested again soon, we’ll certainly cause cache misses that could have been avoided. Now, one might argue that perhaps there might be a case where it’s worthwhile keeping a farthest-in-future item if that item will be requested many times down the line. However, this is not a valid concern, as the next time that item is requested, it’ll be cached at that point and available for all those subsequent requests. By keeping it around in the meantime, we’re taking away space from items that are being requested sooner and causing cache misses.

Clairvoyance Is the Best Policy

The entire premise of our proposed eviction policy assumes that we can predict what requests will be made in the future. But this raises the question: are we able to see into the future?

Indeed, some computer scientists refer to farthest-in-future policy as the clairvoyant eviction policy. That is, we can only evict farthest-in-future items if the computer can, somehow, see the future and know what requests will occur down the road and when. But again, this isn’t practical in most cases because computers cannot see into the future (yet).

That being said, there are some applications where we can, in fact, realistically implement a farthest-in-future policy. That is, there can be an application where we receive a predetermined set of requests, so we know exactly what requests are coming down the pike.

But when we’re leaving it up to human users to decide on the spot what their requests will be, the computer would have to be clairvoyant to take advantage of the farthest-in-future eviction policy. Therefore, in such cases, the clairvoyant eviction policy is only theoretical rather than something we can practically implement.

So, it seems that we’re back to the drawing board. How can we design an eviction policy that is efficient even without knowing what requests will be made in the future?