Cache

Cache

Every time a page loads, the web server makes one or more calls to the database to fetch the data that page needs. When the same data is requested over and over, those repeated database calls become the thing that slows the application down. A cache is what you put in front of that work.

A cache is a small, fast, in-memory store that holds the result of an expensive operation or a piece of frequently read data. The first request pays the full cost, computing the result or querying the database, and the result is kept in the cache. Every request after that reads it straight from memory and skips the expensive work.

The cache tier

The cache tier is a temporary data store layer that sits between the web tier and the data tier, and it is much faster than the database because it answers from memory. Giving it its own tier, rather than caching inside each web server's process, buys three things:

• Better performance. Reads that hit the cache are served from memory instead of going to disk-backed database queries.
• Less database load. Every cache hit is a database query that never happens, so the database has spare capacity for the writes and the uncached reads that actually need it.
• Independent scaling. The cache is its own pool of servers, so you can add cache capacity to match your read pattern without touching the database, and vice versa.

Read-through cache

When the web server needs some data, it goes through the cache first:

1. Check the cache for the data.
2. If it is there (a cache hit), return it to the client.
3. If it is not (a cache miss), query the database, write the result into the cache, then return it to the client.

The cache fills itself lazily: a key only lands in the cache the first time something misses on it. This pattern, where the cache sits in the read path and loads from the database on a miss, is called a read-through cache.

Talking to a cache is simple, because most cache servers ship client libraries for the common languages. A typical Memcached call looks like this:

SECONDS = 1
cache.set('myKey', 'hi there', 3600 * SECONDS)
cache.get('myKey')

set stores a value under a key with a time to live, here one hour. get reads it back, or returns nothing if the key has expired or been evicted since.

Other caching strategies

Read-through is one way to run a cache. There are others. They differ on two things: how data gets into the cache, and what happens to the cache when someone writes.

On a read

Both of these serve reads from the cache and go to the database only on a miss. The one difference is who handles the miss: your application, or the cache itself.

• Cache-aside. Your application handles it. The code checks the cache; if the key is not there, it reads the database, writes that value into the cache, and returns it. The cache is a plain store that knows nothing about the database. This is the most common setup, and the simplest. Two downsides: those miss steps have to be written out everywhere the app reads this kind of data, and if a popular key expires, many requests miss at once and hit the database together (a cache stampede, covered in its own post).
• Read-through. The cache handles it. Your application just asks the cache for the key and gets a value back. On a miss, the cache reads the database itself, using a load function you gave it when setting it up, then stores the value and returns it. The application never makes the database call. The upside over cache-aside is that this miss logic sits in one place instead of being copied everywhere. The first read of a key is still slow.

On a write

• Write-through. Write to the cache and the database at the same time, in one step. The cache is never out of date. The cost: every write is slower now, and you cache things that may never be read.
• Write-back. Write to the cache and return right away. The cache saves to the database a bit later. Writes are fast, and many writes to the same key become one database write. The danger: if the cache server dies before it saves, those writes are lost.
• Write-around. Write straight to the database and skip the cache. The key gets cached later, on the first read that misses. Good when data is written but not read again soon. The catch: a read right after a write always misses.

Real systems pick one from each list. A common pair is cache-aside with write-around, for data that is read a lot and can be slightly out of date. Read-through with write-through is for when a read must always show the latest write. The book uses read-through, and that is all you need for the rest of the chapter.

When a cache is the right tool

Cache data that is read often and written rarely. A user's profile, a product description, the list of top posts on a page: read on nearly every request, changed once in a while. That is the ideal shape.

It is a poor fit for data you cannot afford to lose. A cache keeps everything in volatile memory, so if the cache server restarts, everything in it is gone. That is acceptable for a copy of something and unacceptable for the only copy. Anything that has to survive belongs in a persistent store, and the cache only ever holds a duplicate of it.

Expiration policy

It is good practice to give cached entries an expiration time. When an entry expires it is dropped from the cache, so the next read for that key misses and reloads a fresh copy from the database.

The size of that window is a real tradeoff:

• Too short, and keys expire before they get reused, so the cache barely deflects any load and the database is queried almost as often as if there were no cache.
• Too long, and the cache keeps serving a value long after the database copy changed, so users see stale data.

Without any expiration policy, entries live in memory indefinitely, which both wastes space on data nobody reads anymore and maximizes how stale a served value can get.

Consistency

The cache and the database hold two copies of the same data, and keeping them in agreement is its own problem. A write that changes the database and a write that updates or invalidates the cache are two separate operations, not one transaction, so there is always a moment where one has happened and the other has not. A crash or a race in that gap leaves the cache holding a value the database no longer has.

This gets harder as the system spreads across regions, because now there are multiple cache deployments to keep in sync with the database and with each other. Facebook's paper Scaling Memcache at Facebook (Nishtala et al., NSDI 2013) is the standard reference for how far this problem goes at scale.

When the cache fills up: eviction

A cache has a fixed amount of memory. Once it is full, storing a new entry means removing an existing one to make room. That removal is called cache eviction, and the rule for choosing the victim is the eviction policy:

• Least Recently Used (LRU) evicts whatever has gone longest without being read. This is the most common choice, because "not touched in a while" is usually a good proxy for "not needed soon".
• Least Frequently Used (LFU) evicts whatever has been read the fewest times, keeping popular keys even if they have gone briefly quiet.
• First In First Out (FIFO) evicts the oldest entry regardless of how often it is read.

LRU is the default; the others are worth reaching for when your access pattern has a shape LRU handles badly.

When the cache goes offline

A single cache server is a single point of failure: a part of the system that, if it fails, takes the whole system down with it. It is the same problem we hit with one web server and one database. If the cache dies, every read misses and falls through to the database at once, and a database sized for cache-assisted traffic can fall over under the full unfiltered load.

Two mitigations, used together:

• Spread the cache across several servers, in more than one data center, so losing one server or one site takes out a fraction of the cache rather than all of it.
• Overprovision memory by some percentage above what you currently need, so a traffic spike or the loss of one node does not immediately push the remaining cache into constant eviction.

The design so far

The web tier and the data tier are both redundant now, and a cache tier sits between them absorbing the repeated reads:

1. The client's request reaches a web server through the load balancer.
2. The web server checks the cache for the data it needs.
3. On a hit, it responds from the cache. On a miss, it reads from a slave database, writes the result into the cache, and then responds.
4. Writes still go straight to the master database.

Response times for dynamic data are in good shape. What is left is static content, the JavaScript, CSS, image, and video files that every page pulls and that do not need to come from your servers at all. Pushing those onto a content delivery network (CDN) is the next post.