Hi Friends,
Welcome to the 194th issue of the Polymathic Engineer.
Most of the code we (or our agents) write performs simple tasks, so it makes little sense to optimize them. However, some computations are too expensive to repeat if we don’t need to. Accessing a database is one of them. Calling an external service is another.
Let’s go through an example. Consider a price-comparison service. Given a product ID, the service calls the APIs of four online retailers, collects the prices, and returns the best offer. Each call goes outside your network and has its own latency. You can call the four retailers in parallel, but you need all four answers before you can decide, so your latency will be at least as high as the slowest of them.
This is where things get tricky. Suppose you promised your customers a service-level agreement (SLA) where 95% of the monthly calls return within 750 ms. Most of the time, this is not a problem. But during traffic peaks, a couple of retailers take as long as 3 s to answer. To make things worse, the load balancer kills every call that takes longer than 3.5 s. If you need around 250 ms to handle the incoming call and process the data, you risk having a lot of timeouts. And if you are a paid service, violating the SLA means giving money back.
Since the catalog is small (a few hundred products), the most natural thing to do is to compute the best offer once, store it, and look it up the next time somebody asks for the same product. After an initial warm-up period when every call has to actually compute values, most calls will be answered without hitting the retailers at all. This is precisely what a cache does.
We already discussed where to place a cache in a distributed system, which strategies to use for reads and writes, and how to handle stale data. Here, we focus on the cache itself as a data structure: how to build one so that storing, looking up, and evicting entries are all fast, no matter how many entries it holds.
The outline is as follows:
- The contract
- Memory alone is not enough
- Building an LRU cache
- When fresher data isn’t better: the LFU cache
- Code
To learn technical skills, you must work on real projects. CodeCrafters is a great platform for that. You can build your own Redis, Kafka, DNS server, SQLite, HTTP server, or Git from scratch using your chosen programming language.
The contract
As always, let’s start by defining the interface our data structure should offer. A cache stores a certain number of entries, established when the cache is created. It always allows you to add a new entry, and it decides which entries to keep based on its eviction policy. The following snippet shows the API:
class Cache:
init(max_size)
get(key)
set(key, value)
size()When set is called with a key that already exists, the new value overwrites the old one. get returns the value stored for a key, or nothing if the key is not in the cache. size tells you how many entries are stored at the moment.
There is one thing we are sweeping under the rug: cached values can go stale. The best offer computed this morning is no longer true once the retailers update their prices. How to deal with stale data depends heavily on the context. In some cases, an old value can provide a good enough approximation if a certain margin of error is acceptable. Conversely, in a time-critical, safety-critical application, approximations and stale data are not an option (certainly not for more than a few seconds).
How can we quickly tell when data goes stale? Usually, you store a timestamp along with the value when you write it to cache and check it when you read it. If it’s too old to still be relevant, you can recompute and update the cache.
Handling stale data is an orthogonal task that enhances the base mechanism, and we covered time-to-live and invalidation in a previous issue. So, in the rest of the article, we assume that cached values don’t go stale.
Memory alone is not enough
Let’s stop and recap what we discussed so far. We have an expensive computation whose results can be reused, and we need a mechanism to remember those results so that we compute them only once. For our example, this is straightforward. There are at most a few hundred products, and for each, we store only the best offer. A very small amount of memory is enough.
What would happen, however, if we wanted to cache the raw listings retailers return, with descriptions, images, and shipping options? A popular product can have thousands of listings across sellers, and each one takes a few kilobytes. Even with a few hundred products, the cache could reach several gigabytes.
Or consider how a social media app like Facebook works. When you open your feed, an algorithm computes the best posts to show you, based on your mutuals, your preferences, and the users you follow. It’s a resource-consuming algorithm, so you want to cache its results as much as possible: there is no need to recompute the feed if the same user comes back after 5 minutes. Now consider this cache for a billion users. Even if you store just the top 50 posts per feed, and for each post just its ID, you still need hundreds of gigabytes.
These examples show how easily a cache can reach a size that is hard or impossible to keep in memory. You could move to a distributed cache, but even there, the more entries you store, the slower it gets to check the cache. And in any case, we can’t add entries forever. A cache is a finite system, and at some point, it will be full.
So, once the cache is full, adding a new entry means removing an existing one. The question is which one. The ideal answer is to remove entries that won’t be requested anymore, or at least those that will be requested less. Unfortunately, no computer can predict which elements we are going to need the most, so we can only make an educated guess.
One reasonable assumption is that an entry that hasn’t been accessed for a long time is worth less than one accessed recently. If a product hasn’t been requested in hours, it’s likely it won’t be needed soon, or ever again. But looking only at the time of last access throws away useful information. Suppose an entry was accessed hundreds of times, but not in the last few minutes. Every newer entry, even one accessed just once, would be considered more valuable. If you think about it, an entry accessed only once has been computed but never read from the cache, so caching it has brought no advantage yet. A different approach is to value entries based on how often they are accessed.
These assumptions give us two different caches. Let’s build them, starting with the first.
Building an LRU cache
The first cache we build is the LRU (least recently used) cache, which removes the least recently used entry every time it needs to make room. Before choosing the data structures, let’s list the operations we want to be fast: