How does a cache work
Say that every time you want to read a book you use often, you go all the way to a distant warehouse to fetch it. Every trip takes ages. Keep a copy of that one book on your desk, though, and from then on you only have to reach out. Keeping a copy of frequently used data close at hand so you can grab it quickly is what a cache does.
A distant warehouse is slow to reach
In the last lesson we looked at changing data safely. This time it is the reading side. A database usually keeps its data on disk or runs on another computer, so getting data out of it means sending a request and waiting for the answer.
That round trip is longer than you might think. Even when you want the same data again, you have to make the same long trip as the first time. Let's make a few trips to the distant warehouse below.
Tap the data to fetch it from the distant warehouse. The road is long, so each round trip takes a while, and tapping again is just as slow.
Once or twice is bearable. But if the same data, such as the details of a popular product, is looked up hundreds of thousands of times a day, each lookup means another long trip. The waiting adds up, and the warehouse is kept busy answering the same question over and over.
What is more, most data is used only rarely, while a small part is used remarkably often. It is also common to use again something you have just used. So why not keep just that frequently used part close by?
Keep a copy close by
The method is simple. Fetch frequently used data from the distant warehouse once, then keep a copy of it somewhere close. This nearby store is called a cache.
A cache is usually much faster than the warehouse, but correspondingly smaller. Memory is faster than disk, and something on the same computer is closer than something on another one. So only the most frequently used things are picked out and kept in the fast, small place.
Tap an item to keep a copy in the nearby cache. The empty cache slots fill up one by one.
A copy now sits in the nearby cache. The next time you look for the same data, there is no need to go all the way to the distant warehouse; you take it from the cache right beside you.
There is no guarantee, though, that what you want will always be in the cache. What happens differs depending on whether it is there or not, so let's look at the two cases separately.
A hit and a miss
If what you want is already in the cache, you take it straight out by the short road. This is called a hit. If it is not in the cache, there is nothing for it but to make the trip to the distant warehouse; this is called a miss.
On a miss, since you have fetched the data anyway, you leave a copy in the cache, so the next time you look for the same thing it is a hit. The share of all requests that are hits is called the hit rate, and it is the number to watch when judging how well a cache is doing its job.
Tap a request. If it is in the cache, it is a hit by the short road; if not, it is a miss by the long road, after which a copy is left in the cache. Tap the same request twice to see the difference.
At first it missed and was slow, but once a copy had been left behind, the same request hit and became fast. The more often something is looked up, the more hits pile up and the shorter the average time becomes.
When the cache is full, something has to go to make room for a new copy. Often the item that has gone unused the longest is the one removed; this rule is called LRU, for least recently used. It comes from the idea that something used a moment ago is likely to be used again soon. One troublesome problem remains, though. If the original in the distant warehouse changes, what happens to the copy in the cache?
When the cache goes stale
A cache is only a copy. Even if the original in the distant warehouse changes, the cache does not know about it and keeps holding the copy it received earlier.
So a hit may still be fast while the value it hands out is out of date. A cache in this state is said to be stale. Speed at the risk of handing out a wrong value: that is the downside of caching.
Tap the original to change its value. The cache keeps holding the old value; refilling or dropping the cache brings it back in line with the original.
Changing the original put the cache out of step. There are two main ways to guard against this. One is to update or delete the cached copy whenever the original changes; the other is to give each copy an expiry time and throw it away once that time has passed.
A slot that has been emptied is filled again with a fresh copy on the next miss. A short expiry time means fewer stale values but more misses; a long one means the reverse. Either way, the task is to find a balance that cuts stale values while keeping the fast hits.
Summary
To sum up: a distant store is slow because the road there and back is long, so a copy of frequently used data is kept close by. That is a cache. If what you want is in the cache, it is a hit and fast; if not, it is a miss, and after the trip to the distant store a copy is left behind.
When the cache fills up, the items unused the longest go first, and when the original changes, the copy is updated or thrown away to keep stale values out. Keeping data close and using it fast while making sure it does not drift from the original: that is caching.
Tap the key points in order to review. (far is slow → a copy close by → hit and miss → stale when the original changes)
Caches are not found only in front of databases. The same idea is at work in the CPU, in your web browser, and in delivery networks that copy content from distant servers to places close to users.
For speed, packing data small matters as much as keeping it close. The next lesson, on compression, covers how to store and move the same content in fewer bytes.