Fixing the LRU Worst-Case Scenario with Randomization

We’ve encountered many algorithms that perform differently based on best, average, and worst-case scenarios. Sometimes, the worst-case scenarios are pretty bad. But other times, worst-case scenarios can be really bad. The worst-case scenario for an LRU cache is, in fact, a nightmare.

This worst-case scenario can occur when performing a nested loop in which the inner loop iterates over a list of items where the number of items is ever so slightly greater than the number of items that the cache can store. Let me explain what I mean.

Continuing with our product price-searching app example, say that on the app’s homepage, we want to display some great deals from the web. Also, say that we want to show one deal at a time in a carousel widget, cycling through a list of deals.

One way to do this is to have an array of product names and have an infinite loop that iterates over the array again and again. For each product, the app will look up that product’s best price, pause for a few seconds, and then move on to the next product from the list.

Here’s a simplified implementation of what I’m talking about:

Because we’re cycling through the same list of products over and over again, we don’t need or want to perform a web search each time we display a deal. Instead, it would be smarter to look up the price once and cache it. This way, we can pull the price from the cache the next time we display that product again.

There’s nothing wrong with this approach unless we encounter the nightmare scenario. This is when the product list’s length is slightly greater than the size of the cache. Let’s see what happens when we continuously iterate over five items, and our cache can contain only a maximum of four items. To make the diagrams simple, we’re going to call the products A, B, C, D, and E.

After we fetch data for the first four items in the order A, B, C, and D, our cache is full:

If our next step fetches E, which is not in the cache, we insert E and evict the LRU item A:

We’ve completed our first cycle through the products, so our loop restarts and fetches the same items again. This means that next up, we’re going to fetch the A. However, we just evicted the A in the previous step, which is pretty unfortunate. As such, we’ll have to fetch the A from the web again. Oh, and when we do, we’ll also have to evict B, which is the LRU item:

Our next request is the B.

Wait, what? It’s not in the cache? We had the B in the cache a second ago! Okay, whatever.

Next in line is to fetch the C. But … we evicted the C from the cache the moment before we needed it.

This pattern, of course, continues forever, rendering the cache utterly useless. We consistently evict each item from the cache the step before we need it! And so, we never—and I mean never—get to pull data from the cache. It’s not official jargon, but I call this the “LRU trap.”

Of course, our product-searching example is somewhat contrived, but the LRU trap can and does happen to unwitting software developers every day. The question is how we can have efficient caching while also avoiding the LRU trap, which is a cache’s worst nightmare.

LRU + Randomization = Sweet Dreams

Fortunately, there is a solution. If we throw some randomization into the mix, we may be able to achieve the balance of fast caching while also avoiding the LRU trap.

I mentioned earlier that LRU is one of many eviction policies that have been described over the years. Some alternative eviction policies, for example, use randomization as part of the eviction algorithm. One such policy is known as random replacement and is completely different than LRU. Instead of tracking the cache data in any way, we evict data at random.

This approach absolutely avoids the LRU trap since we’re not evicting data according to any pattern, let alone the LRU trap pattern. However, random replacement turns out to be a pretty inefficient eviction policy. The whole point of a clever eviction policy is to predict what data might be requested next, and random replacement doesn’t bother to predict anything whatsoever.

Power of Two Choices Strikes Again

However, we may be able to blend randomization with LRU to create an eviction policy that is predictive and also avoids the LRU trap at the same time.

One such blend utilizes the same power of two choices discussed earlier in . That is, we randomly select two items from the cache and evict whichever item is less recently used. So, we’re not necessarily evicting the cache’s least-recently used item, but we’re evicting the least-recently used item from among two random choices.

Again, let’s refer back to our sample cache:

If our next request is for item E, we randomly choose two cache items. Let’s say our “dice” land on C and B.

Between C and B, B is less recently used, so that’s the one we evict, as shown in the .

Although we’re using some randomization, we still leverage some of LRU’s ability to predict the future. That is, between the choices of C and B, C is more likely to be requested again, so we keep it in the cache.

Next up, we request the A. This time, the A is inside the cache. Cache hit! Phew, we avoided the LRU trap.

Indeed, this eviction policy may not be as good at predicting future requests as full-fledged LRU, but its predictions may be good enough and also avoid the LRU trap.

Evicting a Random Node

The power-of-two-choices approach has another drawback: evicting a random node from a linked list is slower than evicting the tail node, which is what we were doing with the classic LRU cache.

Again, because our linked list is a doubly linked list, we are able to evict the tail in O(1) time since a doubly linked list always has immediate access to the tail in addition to the head. Evicting a random node, though, can take up to O(N) time. Although there’s more than one way to delete a random node, they all require traversal of the list.

In any case, let’s implement this power-of-two-choices LRU cache.

Code Implementation: Power-of-Two-Choices LRU Cache

Here’s the strategy we’ll use to evict a node: we’ll randomly pick two numbers from 0 up to the length of the list and use these numbers to represent the indexes of nodes. We’ll then select whichever of the two numbers is greater since this will represent the node closer to the tail and therefore less recently used. We’ll then traverse the list up to the index we’ve selected and remove that node.

To make this all work, we’ll add the following pop_index method to the DoublyLinkedList class:

This method accepts a given index and pops the corresponding node. For example, if the index is 0, we pop the first node. If the index is 2, we pop the third node.

We then modify the evict method from our cache as follows:

This selects the greater of two random indexes and pops the node at the greater index, just as we said we’d do.