Caching Strategies

A database keeps everything safely on disk, but a question to it can take many milliseconds, especially a hard question. An in-memory cache, such as Redis or Memcached, keeps copies of popular answers in memory, which is much faster to reach. An answer from a cache often comes back in well under a millisecond.

When the answer is in the cache, that is a cache hit: reach into the backpack, done. When it is not, that is a cache miss: walk to the kitchen, and bring back a copy for next time. The share of requests that are hits is called the hit rate. A high hit rate means the database gets to rest.

The most common way to use a cache is called cache-aside, or lazy loading. The app checks the cache first. On a miss, it reads the database, saves a copy in the cache, and then answers. Only things people actually ask for end up in the cache, and if the cache breaks, the app can still go to the database, just more slowly.

The trade-offs: the first request for anything is always a miss, a copy can grow old when the real data changes, and the cache is one more system to run. A cache is also the wrong place for the only copy of anything, because it can lose what it holds.

Memory is small and costs a lot, so a cache cannot hold everything. When it is full and a new copy needs room, something has to go. Choosing what to throw out is called eviction.

The most common rule is LRU, which stands for least recently used: throw out the thing nobody has asked for in the longest time. If you have not touched the grapes in your backpack all week, they go first, and the snacks you keep reaching for stay. Some caches use LFU, least frequently used, which counts how often something is asked for instead of how recently.

Copies can also carry a timer, called a TTL (time to live). When the timer runs out, the copy is thrown away even if there is plenty of room, so the next request fetches a fresh one. Short timers keep copies fresh but cause more misses. Long timers give more hits but older copies.

If there is only one ice cream factory, far away, everyone waits a long time for a cone. So the factory sends trucks to park in every neighborhood. A CDN does this for files. It is a big network of servers, called edge locations, spread across many cities. They keep copies of pictures, videos, scripts and style files close to the people who use them.

Your request goes to the nearest edge. If the edge has a copy, it answers right away, after a short trip. If not, the edge fetches the file once from the origin, which is your own main server, keeps a copy, and serves everyone nearby from then on. The origin does far less work, and big rushes of visitors are spread across many edges.

CDNs work best for files that are the same for everyone and change rarely. To update a file, the safest trick is to give the new version a new name, like logo.v2.png or a name with a fingerprint of its contents, so edges never mix up old and new. You can also ask the CDN to throw a copy away (a purge), but that takes a little time to reach every edge.

The trade-offs: the first visitor near each edge still waits for the origin, personal or fast-changing pages usually cannot be shared from the edge, and clearing stale copies out of edges all over the world takes care.

A cache holds copies, and copies can go stale. If a price changes in the database but the cache still has the old price, people see the wrong number. Deciding when a copy is no longer good, and getting rid of it, is called invalidation. Programmers joke that it is one of the two hardest problems in computer science, next to naming things.

The trade-off is always freshness against speed. The longer you keep copies, the more hits you get, and the more likely someone sees old data. Decide for each kind of data how old is too old: a few minutes is fine for a video's view count, but not for a bank balance.

There are three common tools, and most systems mix them, for example delete on change for speed, plus a TTL as a safety net in case a delete is ever missed:

• Expire with a timer (TTL): simple and safe, but the copy can be wrong until the timer runs out.
• Delete on change: when the app changes the database, it also deletes the cached copy, so the next read fetches a fresh one. Deleting is safer than rewriting the copy, because two updates racing each other can leave the older value behind.
• Versioned keys: put a version number in the name, like menu:v8. When the menu changes, readers start asking for menu:v9, and the old copy simply ages out.

With write-through, every write goes to the cache and to the database together, and the app only says done once both are saved. It is like updating both your backpack copy and the school records before you say you are finished.

The good part: the cache always has the latest version of anything that was written, so a read right after a write is a hit, and the copies match. The costs: every write waits for two saves, so writes are slower. And the cache fills up with things that were written but may never be read, so write-through is usually paired with a TTL to clear them out.

One more catch: the two saves are not one single step. If one of them fails, the app must notice and fix or delete the cached copy, or the two can still disagree.

With write-around, writes go straight to the database and skip the cache. If the cache had an old copy, the app deletes it. The cache only gets the new data later, the next time someone reads it and misses.

This is good when new data is rarely read right away, like log messages or a big upload, because the cache does not fill up with things nobody asks for. The cost is that the first read after a write is always a miss, so it is a little slower.

A cousin worth knowing is write-back, also called write-behind. The app writes only to the cache and says done right away. The cache saves the changes to the database a little later, often in batches. Writes are very fast, and the database gets fewer, bigger saves. But if the cache crashes before it saves, those changes are lost, so write-back is used only where that risk is acceptable or the cache keeps its own safe copy.

Imagine the most popular snack in the backpack, the one everyone wants, expires. In the same second, a thousand kids find it missing, and all of them run to the kitchen to make it again. The kitchen is swamped, everyone waits, and the kitchen may even fall over. This is a cache stampede, also called the thundering herd or dogpile problem. It often hits a very popular key, or a cache that was just restarted and is empty.

Fix one, a lock (single flight): the first request that misses takes a lock and goes to the database. Everyone else waits for that one answer, or gets the slightly old copy while it is being refreshed. Many requests sharing a single trip like this is called request coalescing. One trip instead of a thousand.

Fix two, refresh before it expires: a background job refreshes hot keys a little before their timer runs out (refresh-ahead). Or each request, as the timer nears its end, rolls dice with a small but growing chance of refreshing early (probabilistic early expiration), so usually just one request does it, a bit ahead of time. Fix three, add jitter: give each timer a little random extra, like 10 minutes plus or minus 1, so keys made at the same moment do not all expire at the same moment.

Fix four, serve stale while revalidating: keep handing out the old copy for a short while after it expires, while one request quietly fetches a fresh one. Big systems usually use several of these fixes together.