Caching

The cache hierarchy

A request to Snip passes through up to five places that can answer it before the database does. Each is a cache, each sits closer to a different audience, and each trades a different amount of freshness for speed. Reading them from the client inward shows where a hit saves the most.

Two things in that table decide how you use it. First, the layers farther out save more and offer less control. A browser hit costs you nothing and you cannot reach into a user's laptop to evict it; a Redis entry you can delete in one command. Second, the in-process cache multiplies copies. Twenty app servers means twenty independent copies of a hot key, which can disagree for as long as their TTLs allow. In-process caches suit data that is small, read constantly and safe to be briefly stale, such as feature flags or configuration. Per-user and per-link data belongs in the shared tier.

The buffer pool is the one you never configure as a cache but should know about. If your working set of index and table pages fits in RAM, the database is already serving most reads from memory, and an application cache in front of it is saving query overhead and connections rather than disk seeks. That is still worth having. A database that serves 100 rps from memory is calm; one that serves 10,000 rps from memory is saturating its CPU and connection pool, the bottleneck the numbers chapter told you to watch for.

Read and write patterns

"Use a cache" hides a decision about who talks to whom and in what order. Four patterns cover nearly every case.

Default to cache-aside. It is the only pattern where a cache outage degrades the system instead of breaking it: the app falls through to the database, slower but correct. It also caches only what is read, so memory goes to keys that earn it, and the cache is a plain key-value store with no knowledge of your schema. Read-through is cache-aside with the loop moved into a library; pick it when a framework gives it to you, not for any change in behavior.

Write-through wins when a read immediately after a write must see the new value and the data is read far more than written, such as a user's profile settings. The write pays double, but there is no stale window and no extra invalidation code. Write-back wins only when writes are the bottleneck and loss is acceptable: counters, view tallies, "last seen" timestamps. If you would apologize to a customer for losing the write, do not use it. Snip's click counts fit the profile, and the next chapters will show why even they should not live in a simple cache.

Invalidation, the hard part

The old joke says there are two hard problems in computer science: cache invalidation and naming things. The reason is mechanical. A cache entry is a copy, and the system has two places that can change independently: the source, when someone writes, and the cache, when an entry expires or is evicted. Nothing connects the two unless you build the connection. Every drift between cache and source is a write that reached one and not the other, or reached them in a different order.

Three tactics cover most of the ground, and they stack.

TTL expiry. Give every entry a time to live and let it die. It needs no coordination: even if you forget a code path, no entry stays wrong longer than its TTL. The cost is a staleness window equal to the TTL, and a miss at every expiry. Choose the TTL by asking how long a wrong answer is tolerable, not how long a right one stays right. Prices and permissions get seconds; a blog post gets hours.

Explicit invalidation. On a write, delete (or overwrite) the affected keys. This shrinks the stale window to roughly the time between the database commit and the delete, usually milliseconds. It requires that every write path know every key that depends on the changed row, and that is where it fails in practice: someone adds a list view that caches a query result containing the row, and nothing evicts it. Delete rather than update on write. Deleting is idempotent and the next read rebuilds a correct value; updating needs you to compute the cached form correctly in two places.

Versioned or immutable keys. Never change an entry; change the key. Put a version or content hash in it (app.3f9a1c.js, or user:42:v17), and bump the version on write. Old entries become unreachable and age out by TTL or eviction, so no invalidation message can arrive late or be lost. This is how static assets work behind a CDN, and it fits any data where a cheap version counter exists. The cost is that readers need the current version, which is itself a small piece of state to keep fresh.

Combine them: a TTL as the backstop, explicit deletes for the paths you control, and versioned keys for anything served from the edge where you cannot reach in and delete reliably. Treat a CDN purge as a request, not a guarantee; propagation takes seconds and can fail.

The stampede

Cache-aside has a failure mode that appears only at scale. A hot key expires. In the next few milliseconds, before anyone refills it, every request for that key misses, and each one independently goes to the database to compute the same answer. If the key takes 1,000 requests per second and the query takes 50 ms, about 50 requests are in flight before the first returns, and they all run the same query. The database slows under the extra load, so the refill takes longer, so more requests pile up. This is the cache stampede, or thundering herd. A cache that absorbed 99% of reads becomes a synchronized burst aimed at the one component you built it to protect.

Three mitigations, usually used together.

• One loader per key. On a miss, take a short per-key lock; the winner queries the database and fills the cache, and the others wait briefly or serve a slightly stale value. Inside one process this is request coalescing, called singleflight in Go: concurrent callers for the same key share one in-flight call. Across servers use a lock in the cache itself, with an expiry so a crashed holder cannot block the key forever.
• Recompute early. Refresh a hot key before it expires. The probabilistic version has each reader, as expiry nears, roll a die weighted by how long the recompute takes; one reader volunteers while everyone else still gets a hit. The expiry never arrives as a cliff.
• Jitter the TTLs. If you load 10,000 keys at startup with a 1-hour TTL, they all expire in the same second. Add random spread, say plus or minus 10%, and the expiries smear across six minutes instead of landing together.

def get_url(code):
    val = redis.get(f"u:{code}")
    if val is not None:
        return None if val == MISSING else val          # hit (maybe a cached "not found")

    # miss: only one caller per key rebuilds; the rest briefly wait and retry
    if redis.set(f"lock:{code}", 1, nx=True, px=2000):
        row = db.fetch_url(code)                        # the expensive call
        ttl = BASE_TTL * random.uniform(0.9, 1.1)       # jitter
        redis.set(f"u:{code}", row.url if row else MISSING, ex=int(ttl if row else 60))
        redis.delete(f"lock:{code}")
        return row.url if row else None
    time.sleep(0.02)
    return get_url(code)

The same code shows negative caching. A lookup for a code that does not exist is a miss every time, so a crawler guessing codes sends each guess to the database and never fills the cache. Store the "not found" answer too, with a short TTL (the 60 seconds above), so the database hears each bad code once a minute at most. Keep that TTL short: if the code is created a moment later, readers should not be told it does not exist for long.

Caching Snip

A redirect is the ideal cache workload: the answer for a code is a short string that rarely changes, and a small set of codes takes nearly all the traffic. Snip's design here has three parts.

Size and hit rate. Snip stores 1 billion links at about 500 B per row, roughly 500 GB. You cannot serve that from RAM cheaply, and you do not need to. Traffic on short links is heavily skewed, so assume 1% of links (10 million) account for about 99% of redirects. At 500 B per entry, a generous figure since the cache stores only the code and URL, that hot set is about 5 GB, which fits on one Redis node with room to spare. This is the back-of-envelope sizing the numbers chapter teaches. At a 99% hit rate, the database sees about 12 of the 1,200 average redirects per second, and about 100 of a 10,000 rps peak. Without the cache it sees all of them. That ratio is what makes the cache the first thing you add, ahead of replicas.

Two layers, two TTLs. Cache code to URL in Redis with a TTL of 24 hours plus jitter. The mapping is almost immutable, so the TTL is a backstop for missed invalidations and a way to let cold links fall out, not a freshness control. At the CDN, cache the redirect response for a short time, about 5 minutes. The edge absorbs viral bursts before they reach your servers, and the short TTL bounds how long an edited or deleted link keeps working somewhere you cannot reach. Return a 302, not a 301: browsers cache a 301 indefinitely, so an edit would never reach users who had visited, and Snip would also never see their repeat clicks.

Edits and deletes. When a user edits or deletes a link, write the database first, then delete the Redis key, then purge the CDN path. For a delete, store a short-lived tombstone rather than leaving a gap, so the next read hits "not found" in the cache instead of racing the database. Accept that for up to 5 minutes some edge locations may still redirect to the old URL; for a link taken down for abuse, send the purge and treat the edge TTL as the worst case you quote.

What remains behind the cache is a database taking tens of reads per second and one million new links a day. That is a light load, but it is a single machine with all of your data, which is the next problem: scaling the database.

✓ Check yourself

Answer from memory before opening each one.

1. A cache-aside service deletes the cache key after every database write, yet a key is sometimes stale for its full TTL. Describe the sequence of events that causes it.

   Show answer

   A reader misses and reads the old row from the database. Before it writes to the cache, a writer commits the new row and deletes the key. The reader then writes its old value into the cache. The delete happened before the stale insert, so it cannot undo it. Only the TTL removes the entry, which is why every cache-aside entry needs one.

2. Why does a stampede make the database slower rather than just busier, and what does that do to the next refill?

   Show answer

   Dozens of identical queries run at once and compete for CPU, locks and connections, so each takes longer than a single query would. The slower refill leaves the key empty for longer, which lets more requests miss and join the pile. The load feeds itself until the key is filled or the database is overwhelmed.

3. You choose write-back for a "likes" counter and the cache node restarts. What exactly did you lose, and what would make you decline write-back for the same data?

   Show answer

   You lose every acknowledged write that had not yet been flushed to the database, bounded by the flush interval. For a likes count that may be tolerable. Decline it if the count drives money or access, or if users can see a number go backward, because then the loss is a visible bug and not noise.

4. Snip sets a 24-hour TTL on Redis entries and 5 minutes at the CDN. Why not use 24 hours at both, and what does a user see when a link is deleted?

   Show answer

   You can delete a Redis key at once, but a CDN purge is slow and can fail, so the edge TTL is the worst-case time a deleted link keeps redirecting. A 24-hour edge TTL would make that a day. With 5 minutes, a deleted link may redirect for up to 5 minutes from some regions, and fails immediately wherever the purge landed.

5. A crawler requests 50,000 random 7-character codes per minute and your database load doubles even though the hit rate on real links is 99%. What is happening and what is the fix?

   Show answer

   Codes that do not exist never get cached, so each probe misses and queries the database. Add negative caching: store a "not found" marker with a short TTL (about a minute) so each bad code costs one query. Rate limiting the crawler by IP also helps.

Takeaway

• A cache is a copy, and any copy can drift from the source. Every caching decision is a decision about how wrong the copy may be and for how long.
• Layers closer to the client save more latency and give you less control; the in-process layer multiplies copies across servers, so keep it for small, stale-tolerant data.
• Default to cache-aside because a cache failure degrades the system rather than breaking it; choose write-through for read-after-write needs and write-back only when losing a short window of writes is acceptable.
• Combine a TTL backstop, explicit deletes on write, and versioned keys at the edge. The TTL is required, because the cache-aside race can restore a stale value after the delete.
• A hot key expiring can send thousands of identical queries at the database. Use per-key locking or coalescing, early recompute, and jittered TTLs, and cache "not found" briefly.
• Snip's redirects need about 5 GB of cache for a 99% hit rate, cutting database reads from roughly 1,200 per second to about 12. Click counting is a write and does not belong in this cache.

The cache takes most reads, but the database still holds every byte and takes every write, and one machine will run out. → Scaling the Database

Further reading

• Designing Data-Intensive Applications — Martin Kleppmann, 2017. The chapters on replication and consistency explain why copies drift, which is the root of every invalidation bug.
• Scaling Memcache at Facebook — Nishtala et al., NSDI 2013. Leases against stampedes and stale sets, at a scale where both were daily problems.
• Optimal Probabilistic Cache Stampede Prevention — Vattani, Chierichetti and Lowenstein, VLDB 2015. The math behind early probabilistic recomputation.
• Redis key eviction — Redis documentation. What happens when the cache fills: eviction policies such as LRU and LFU, and how to choose one.