Caching Strategies & Invalidation

Every cache is a bet that reads outnumber writes and that some staleness is tolerable. Getting data into Redis is the trivial part; the engineering is in what happens when the underlying row changes, when ten thousand requests miss the same key in the same millisecond, and when one key absorbs half the traffic. This entry maps the patterns first, then the failure modes.

The pattern map #

Every pattern is an answer to two questions: who fills the cache on a miss, and where does a write go first.

Cache-aside dominates because the cache stays a dumb key-value store: on a read the app tries the cache, on a miss it queries the DB and writes the result back with a TTL; on a write it updates the DB and deletes the key. If the cache dies you degrade to slow-but-correct. Read-through and write-through move the fill logic into the caching layer itself, which simplifies callers but requires a cache that can reach your DB. Write-behind acknowledges before durability. Refresh-ahead burns extra reads to keep tail latency flat.

The topological difference matters more than the names: cache-aside treats the cache as a disposable projection of the DB, so correctness never depends on it; write-through makes the cache a mandatory hop, which is what buys read-after-write coherence on the cached path — and couples your write availability to the cache tier.

The magnitudes that justify each tier #

Bar widths are log-scale: 8 px per factor of 10, anchored at the 0.5 ns L1 reference — every extra 8 px of bar is another 10× in latency, so the 66 px between the L1 and cross-region bars span more than eight orders of magnitude.

Two conclusions fall out. A same-DC Redis hit costs ~5,000× a local memory read — which is why an in-process L1 above Redis is itself a caching strategy, not an optimization footnote. And a cross-region round trip costs ~100× a same-DC one — which is why nobody serves a global audience from one cache cluster; you replicate regionally or push to the edge.

Invalidation #

There are two mechanisms and every real system uses both. TTL is passive: staleness is bounded by the TTL, the cache self-heals, and the only decision is what staleness the product tolerates. Explicit invalidation acts at write time — and here the first decision is delete vs update.

Delete wins in almost all cases. Deletes are idempotent, so replays and races between two invalidations converge; a re-SET from two concurrent writers can land in either order and leave the loser's value cached indefinitely. Deletes also avoid writing values nobody will read again — the next reader refills on demand. Facebook's memcache made this a rule: writers delete, only the read path sets.

Ordering matters too: commit the DB write, then delete the key. Deleting first reopens the window — a concurrent reader misses, reads the still-old row, and re-caches it, leaving stale data until TTL. Deleting after commit shrinks the window to the commit→delete gap. Shrinks, not closes:

This race is why "cache invalidation" earns its place in the two-hard-things joke: each half of the protocol is trivial, but the interleavings are not, and the failure mode is silent. The systematic fix is to move invalidation off the web tier entirely: tail the database's WAL/binlog and issue deletes from the commit stream (Facebook's mcsqueal daemons did exactly this). Invalidations then cannot race ahead of commits, cannot be dropped by a crashing app server, and replay safely because deletes are idempotent.

Stampedes and thundering herds #

When a popular key expires, every in-flight reader misses simultaneously and issues the same query — the DB absorbs a spike proportional to the key's popularity exactly when the cache stops helping. Three families of fixes:

Request coalescing / locking. Let one caller fetch while the rest wait on its result. In-process this is singleflight; cross-fleet it is a short lock (SET lock:k token NX PX 3000) or a memcache lease.

var group singleflight.Group

func Get(ctx context.Context, key string) ([]byte, error) {
	if v, err := rdb.Get(ctx, key).Bytes(); err == nil {
		return v, nil
	}
	// One DB fetch per key per process; concurrent callers share it.
	v, err, _ := group.Do(key, func() (any, error) {
		// Detached from ctx: a canceled winner must not fail every waiter.
		lctx, cancel := context.WithTimeout(context.WithoutCancel(ctx), 3*time.Second)
		defer cancel()
		row, err := loadFromDB(lctx, key)
		if err != nil {
			return nil, err
		}
		ttl := baseTTL + time.Duration(rand.Int64N(int64(baseTTL/10)))
		_ = rdb.Set(lctx, key, row, ttl).Err() // refill is best-effort
		return row, nil
	})
	if err != nil {
		return nil, err
	}
	return v.([]byte), nil
}

Two details in the closure are load-bearing. The fetch runs on a context detached from the winning caller (context.WithoutCancel plus its own timeout): singleflight runs one caller's closure on behalf of everyone, so with a caller-scoped context, that caller canceling mid-flight — a client timeout, exactly what a stampede produces — would fail the load with context.Canceled and fan the error out to every coalesced waiter. And the cache refill is best-effort: the value already came from the DB, so a failed SET must not turn a cache-tier outage into a read outage.

Singleflight collapses the herd per process: 400 pods still mean up to 400 concurrent fetches per key. That is usually reduction enough; for brutal keys, add the distributed lock on top.

Probabilistic early expiration. Each reader independently recomputes slightly early with a probability that rises as expiry approaches: refresh when $t_{now} - \delta\,\beta\,\ln(\mathrm{rand}()) \ge t_{expiry}$, where $\delta$ is the recompute cost and $\beta = 1$. One lucky reader refreshes before expiry, so the herd never forms. This "XFetch" rule is provably near-optimal (VLDB '15) and needs no coordination at all.

Serve-stale. Keep the value past its logical expiry and refresh asynchronously; readers get slightly stale data instead of a miss.

Hot keys and skew #

Real access distributions are Zipfian, and a single celebrity key can exceed what one Redis shard can serve — a single instance executes commands on one thread, on the order of 10⁵ simple ops/s. Consistent hashing does not help: the hot key lands on exactly one shard regardless. The standard moves, covered fully in Hot Keys & Hot Partitions: an in-process L1 above the shared cache (microsecond hits, staleness bounded by a short TTL — or by Redis 6 client-side caching, where the server pushes invalidations over RESP3); key splitting for hot counters (k#0…k#N-1, sum on read); and replicating read-mostly hot values to every shard so any node can answer.

Negative caching #

Cache the absence, not just the presence. On a miss where the DB also returns nothing, store a tombstone with a short TTL (seconds to a minute). Otherwise every lookup of a nonexistent id — misspelled URLs, deleted accounts, or a hostile scanner enumerating ids ("cache penetration") — passes straight through to the DB, and the cache provides exactly zero protection on the one workload that is unbounded. Keep the TTL short so newly created rows become visible, or delete the tombstone in the insert path; for adversarial workloads a Bloom filter of valid ids in front of the cache rejects garbage before it costs a round trip.

What memcache-at-Facebook taught everyone #

The NSDI '13 paper is the canonical description of cache-aside at extreme scale, and most large deployments end up reinventing its pieces. Leases solve the stale-set race and thundering herds in one mechanism (below). Regional pools recognize that not every key deserves per-cluster replication: each frontend cluster keeps its own replicas of hot keys, while the long tail lives once in a pool shared by all clusters in the region — trading intra-region latency for a large drop in memory footprint. Invalidation flows from the DB tier, not the web tier: daemons tail the MySQL commit log and fan deletes out to every cluster, so invalidation survives web-server crashes and works across regions.