We have hinted at this in the previous sections: sometimes the least recently used entries are the ones less likely to be requested again . . . but that is not necessarily true in all contexts.
It may happen that some data was popular in the past and currently becomes temporarily irrelevant, but then it will likely be accessed again in the near future.
Think about an online retailer that operates worldwide. If a product is particularly popular in one or just a few countries, it will hit high peaks of requests during busy hours for that country, while it will hardly be accessed at all during the low peaks of activity for that same area.
Either way, we might end up purging from the cache data that on average is used frequently over time, because there might be fresher data—entries that have been accessed more recently, but perhaps will never ever (or for a long time, longer than the average life of a cache entry) be accessed again.
If that’s a possibility, an alternative policy could be based on counting how many times an entry has been accessed since it was added to the cache, and always retaining those items that are accessed the most.
This purging strategy is called LFU for Least Frequently Used (sometimes also referred to as MFU, Most Frequently Used) and comes with the advantage that items that are stored in the cache and never accessed again get purged out of the cache fairly quickly.
1. So how do we choose?
Those are not the only possible strategies for cache purging. A web cache, for instance, could also consider the cost of retrieving some information in terms of latency, compute time, and even actual costs when, as in our example, you need to pay an external service to retrieve some information.
And that’s just one of many examples. The key point here is that you need to choose the best strategy for your context and for the characteristics of your application. Partly you can determine it during design, but to validate and fine tune your choice, you will likely have to run some profiling and collect statistics on the usage of your cache (don’t be alarmed, though; there are several tools that can automatically do that for you).
2. What makes LFU different
To describe an LFU, we are not going to start from scratch; that would make no sense, as we already have a good basis to start with—our LRU cache.
We’ve said it over and again: the difference between two cache types is the eviction policy. Well, that’s true for the most part, although not quite the whole story.
As shown in figure 7.10, we could implement our LFU from the code in section 7.4 by just changing the eviction policy and therefore the order of elements in the list.
When we add a new entry, we set its counter to 1, and we could insert it at the tail of the list, while on a cache hit we could increment the node’s counter and move it toward the head of the list until we find another node with a larger counter.
That would certainly work correctly. But how efficient would it be? Would there be a way to improve the performance of our cache?
We can forget about constant-time insertion: that only works for the LRU. We can at least maintain constant-time lookup, and it’s better than nothing.
But adding or updating a new element could take up to linear time in edge cases where most of the elements are used with the same frequency.
Can we do any better? Well, once again, at this point a bell should ring (if it doesn’t, you might want to take a look at chapter 2 and appendix C before moving on).
We are no longer basing our eviction policy on a FIFO (first in, first out) queue. The order of insertion doesn’t matter anymore; instead, we have a priority associated with each node.
Now do you see where I am going? The best way to keep an order on entries based on their dynamically changing priority is, of course, a priority queue. It might be a heap, a Fibonacci heap, or any other implementation, but we will stick with the abstract data structure in the code, leaving to users the task of thinking about which implementation works best for them, depending on the programming language they use and, of course, the context in which they will use the cache. For the performance analysis, though, we will consider a heap because it gives us reasonable-enough performance guarantees on all operations, combined with a clean, simple implementation.
Take a look at figure 7.11 to see how this changes our cache internals. Now we have only two things to change in our implementation to switch from an LRU to an LFU:
- The eviction policy (all the logic about choosing which element to remove)
- The data structure used to store elements
It’s time to look at some more code. We highlighted the differences between the corresponding LRU’s methods to make it easier for the readers to compare them.
The initialization of the cache, shown in listing 7.5, is almost identical to the LRU one; we just create an empty priority queue instead of a linked list.
When it comes to adding an entry, things get a bit trickier. Remember that we mentioned how you need to be careful in order to implement the priority? We want to make sure that among the elements with the minimum number of entries, the oldest is removed first; otherwise, we could end up removing the latest entry over and over again, without giving it a chance to have its counter increased.
The solution is described in listing 7.6, where we use a tuple, <counter, timestamp> as priority, where the timestamp is the time of last access to an entry, and it’s used to break ties on the counter; here, higher frequency and larger timestamps mean higher priority.
Finally, we have the method to evict one of the entries, which is implemented in listing 7.7. Using a priority queue makes its implementation even easier, because all the details of removing the element and updating the queue are encapsulated in the priority queue itself.
3. Performance
Let’s once again update our table with the performance for LFU. As shown in table 7.4, since all writing operations for an LFU involve modifying a heap, we can’t have the constant time guarantee anymore, except for the lookup.
It’s worth noting that with a Fibonacci heap, insertion and update of priority in the heap would run in amortized constant time, but deleting the top element would still require logarithmic time, so we couldn’t improve the asymptotic running time needed for storing an entry (because it uses delete).
4. Problems with LFU
Of course, no policy is always perfect, and even LFU has some cons. Most notably, if the cache runs for long, the turnaround time for older entries that are not popular anymore could be very long.
Let’s consider an example: if you have a cache with at most n entries, and the most frequently used one, X, has been requested m times before, but at some point isn’t being accessed anymore (for example, it goes out of stock), then for a set of n new entries to cause the eviction of X, they will have to be requested n*m times at least.
Plugging in some numbers, if your cache holds a thousand elements and X was requested a thousand times, it will take at least one million accesses to a thousand brand-new entries before X is evicted after it becomes useless. Obviously, if more accesses are made to other entries already in the cache, then this number goes down, but on average it should be in that order of magnitude.
To solve this issue, some possible solutions are
- Limiting the maximum value for the counter of an entry
- Resetting or halving the counter of entries over time (for instance, every few hours)
- Computing the weighted frequency based on the time of last access (this would also solve our issue with ties on the counter, and we could avoid storing tuples as priorities)
LRU and LFU are not the only type of cache available. Starting from an LFU cache, and just (this time for real) changing the eviction policy by choosing a different metric for entries priority, custom types can be created to adapt to specific contexts.
For instance, we could decide that certain companies are more important than others, or we might want to weight the number of accesses with the age of the data, halving it every 30 minutes from the last access.
As complicated as it may sound so far, that’s not all of it. You have choices about how to run a cache, but you also have more choices when it comes to how to use it.
Source: Rocca Marcello La (2021), Advanced Algorithms and Data Structures, Manning Publications (2021)