Caching Strategies and Eviction Policies
The single highest-leverage component in most systems, and the one with the most ways to go subtly wrong. Patterns, eviction, invalidation and the failure modes that cause outages.
Covers: Cache-aside, read-through, write-through, write-back; LRU, LFU, TTL; invalidation; stampedes; hot keys
Caching is usually the largest performance win available: a Redis read is ~0.5 ms against a database read of 5–50 ms, and it removes load from the component that is hardest to scale. It is also where the two hardest problems in computer science live - cache invalidation and naming things - and an interviewer will absolutely push on invalidation.
30-second answer
Cache-aside puts the application in charge: check the cache, on a miss read the database and populate. Read-through hides that behind the cache client. Write-through writes to cache and database together, keeping them consistent at the cost of write latency and caching data nobody reads. Write-back writes only to the cache and flushes later, which is the fastest and the only one that can lose data. Cache-aside is the default for almost every system because it is simple, resilient to cache outages, and only caches what is actually read.
| Pattern | Read path | Write path | Risk |
|---|---|---|---|
| Cache-aside | App checks cache → miss → DB → populate | App writes DB, then invalidates cache | Brief inconsistency window; every miss hits the DB |
| Read-through | Cache library fetches from DB on miss | Usually paired with write-through | Less control; cache becomes a hard dependency |
| Write-through | Always a hit for written keys | Write cache + DB synchronously | Higher write latency; caches unread data |
| Write-back | Always a hit | Write cache; flush to DB asynchronously | Data loss if the cache dies before flushing |
| Refresh-ahead | Hit; refreshed before expiry | Background refresh of hot keys | Wasted refreshes for keys that go cold |
def get_user(user_id):
key = f"user:{user_id}:v3" # version in the key -> schema changes are free
cached = redis.get(key)
if cached is not None:
return deserialize(cached) # note: 'is not None', so we can cache negatives
user = db.get_user(user_id)
# Cache the miss too, briefly - otherwise a hammered nonexistent id is a DB DoS.
ttl = 300 if user else 30
redis.setex(key, ttl + random.randint(0, 60), serialize(user)) # jitter the TTL
return user
def update_user(user_id, data):
db.update_user(user_id, data) # database first, always
redis.delete(f"user:{user_id}:v3") # then invalidate - do NOT write the new valueWhere the cache lives matters as much as the pattern
| Layer | Latency | Scope | Invalidation |
|---|---|---|---|
| Browser / client | 0 ms | One user | Nearly impossible - use short max-age or content hashes |
| CDN edge | 10–50 ms | A region | Purge API; slow and eventually consistent |
| Application in-process | ~100 ns | One instance | Hard - instances drift; keep TTLs seconds, not minutes |
| Distributed (Redis) | ~0.5 ms | All instances | Easy and immediate - a single DELETE |
| Database buffer pool | ~1 ms | One database | Automatic |
Multi-layer caching compounds the wins and compounds the invalidation difficulty. The nearer the user, the faster the hit and the harder the purge.
Say these points
- Cache-aside is the default: simple, survives cache loss, caches only what is read.
- Write to the database first, then delete the cache key - never write the value in.
- Cache negative results briefly to stop lookups for nonexistent keys hammering the DB.
- Version keys so a schema change is a deploy, not a mass purge.
- Each caching layer trades latency against invalidation difficulty.
Avoid these mistakes
- Updating the cache instead of deleting, allowing stale writes to win a race.
- Invalidating before the database write.
- No TTL at all - a missed invalidation then becomes permanent.
- Caching everything indiscriminately, including data written far more often than read.
Expect these follow-ups
- How do you invalidate a cached list when one of its members changes?
- When would write-back actually be the right choice?
- How do you keep an in-process cache coherent across 200 instances?
30-second answer
A stampede happens when a hot key expires and thousands of concurrent requests all miss and hit the database at once - prevent it with a lock so one request recomputes while the others wait or serve stale. Penetration is repeated requests for keys that do not exist, so the cache never helps - prevent it by caching negative results and using a Bloom filter. Avalanche is many keys expiring simultaneously, usually because they were populated together with identical TTLs - prevent it by adding random jitter to every TTL.
1 · Stampede (thundering herd)
The homepage feed is cached with a 60-second TTL and served 10,000 times a second. At the instant it expires, all 10,000 in-flight requests miss simultaneously, and all 10,000 run the same expensive query. The database saturates, queries slow down, the recompute takes longer, and more requests pile in behind. This is a genuine outage mechanism, not a theoretical one.
def get_with_early_recompute(key, recompute, ttl=60, beta=1.0):
"""XFetch: refresh *before* expiry with a probability that rises as
expiry approaches, so exactly one request usually recomputes early."""
packed = redis.get(key)
if packed is None:
return recompute_and_store(key, recompute, ttl)
value, delta, expiry = unpack(packed) # delta = last recompute duration
# The longer a recompute takes, the earlier we start rolling for it.
if time.time() - delta * beta * math.log(random.random()) >= expiry:
return recompute_and_store(key, recompute, ttl)
return value # still fresh enough
def recompute_and_store(key, recompute, ttl):
start = time.time()
value = recompute()
delta = time.time() - start
redis.setex(key, ttl, pack(value, delta, time.time() + ttl))
return value| Mitigation | How | Trade-off |
|---|---|---|
| Lock / single-flight | First miss takes a short lock and recomputes; others wait or serve stale | Adds a lock round trip; a crashed holder must time out |
| Probabilistic early expiry | Recompute slightly before TTL with rising probability | Slightly more recomputes overall; no coordination needed |
| Serve stale while revalidating | Return the expired value immediately and refresh in the background | Users briefly see stale data - usually completely fine |
| Never expire hot keys | Refresh proactively on a schedule | Requires knowing which keys are hot |
2 · Penetration (queries for keys that do not exist)
An attacker - or a buggy client - requests /user/999999999 repeatedly. The cache misses every time because there is nothing to cache, and every request reaches the database. The cache provides zero protection precisely when you need it most.
- Cache the negative. Store a tombstone with a short TTL (30–60 s) so repeated misses are absorbed. Keep the TTL short so a newly created record appears quickly.
- Bloom filter in front. A compact probabilistic set of all existing IDs. 'Definitely not present' short-circuits the lookup entirely; false positives just fall through to the normal path. Perfect fit, since false negatives are impossible.
- Validate the key shape. If IDs are UUIDs, reject anything that is not a UUID before touching any storage.
3 · Avalanche (mass simultaneous expiry)
You warm the cache at deploy time with 100,000 keys, all with a 3,600-second TTL. One hour later, every one of them expires in the same second. The database receives its entire day's read load in a few seconds.
# ❌ Every key populated together expires together.
redis.setex(key, 3600, value)
# ✅ Jitter spreads expiry over a 10-minute window.
redis.setex(key, 3600 + random.randint(0, 600), value)| Problem | Trigger | Fix |
|---|---|---|
| Stampede | One hot key expires under high concurrency | Lock, early recompute, or serve-stale-while-revalidate |
| Penetration | Requests for keys that do not exist | Negative caching plus a Bloom filter |
| Avalanche | Many keys expiring at once | TTL jitter |
| Cache outage | Redis unavailable | Coalescing, circuit breaker, local fallback, capacity headroom |
| Hot key | One key gets a disproportionate share of traffic | Client-side replication of that key, or local caching |
Say these points
- Stampede: one expiring hot key can take down the database - lock or recompute early.
- Penetration: cache negative results and front with a Bloom filter.
- Avalanche: always add random jitter to TTLs.
- Plan capacity for a zero-hit-rate scenario; a cache outage must not cascade.
- Serving stale while revalidating is usually acceptable and removes an entire class of failure.
Avoid these mistakes
- Identical TTLs on bulk-populated keys.
- No negative caching, leaving a trivial database DoS open.
- Assuming the database can absorb full traffic if the cache fails.
- A stampede lock with no timeout, so a crashed holder blocks everyone.
Expect these follow-ups
- Redis is down and the database is melting. What is your immediate action?
- How do you warm a cold cache after a full flush without a thundering herd?
- One key receives 40% of all cache traffic. What do you do?
30-second answer
LRU evicts what was used least recently - cheap, and it adapts fast to changing access patterns, but a single large scan can wipe the whole working set. LFU evicts what is used least often - it protects genuinely hot keys from scans, but adapts slowly and needs frequency decay or yesterday's popular items never leave. TTL is not really eviction, it is a freshness bound, and you almost always want it alongside a size-based policy. Size the cache by measuring the working set: plot hit rate against memory and find the knee, because past that point additional memory buys almost nothing.
| Policy | Evicts | Strength | Weakness |
|---|---|---|---|
| LRU | Least recently used | Adapts quickly; cheap to implement | One big scan evicts the entire working set |
| LFU | Least frequently used | Resists scans; protects genuinely hot keys | Slow to adapt; needs decay to forget old popularity |
| FIFO | Oldest inserted | Trivially simple | Ignores usage entirely - usually worst hit rate |
| Random | Any key | No metadata, no locking | Surprisingly decent, and very cheap |
| TTL | Anything older than N | Bounds staleness | Not a memory-management policy on its own |
| LRU-K / SLRU | Considers the last K accesses | Distinguishes one-hit wonders from real hot keys | More memory and complexity |
Sizing: find the knee of the curve
Cache hit rate against size is a strongly concave curve. Typical shape for a web workload:
| Cache size (% of dataset) | Typical hit rate | Marginal value |
|---|---|---|
| 1% | ~60% | Enormous |
| 5% | ~80% | Large |
| 10% | ~88% | Good - usually the knee |
| 25% | ~94% | Diminishing |
| 50% | ~97% | Poor value per gigabyte |
| 100% | 100% | You have bought a second database |
Access distributions are heavily skewed - a small fraction of keys serves most requests. Measure your own curve; do not assume these numbers.
The right question is not “what hit rate do we want?” but “what does the next gigabyte buy?”. Going from 88% to 94% removes half the remaining database load, which may well be worth it. Going from 97% to 98% almost never is.
What not to cache
- Data written more often than it is read - you pay invalidation cost for no benefit.
- Anything where staleness is unacceptable and TTL would have to be near zero.
- Very large objects that would evict thousands of small hot ones.
- Per-user data with essentially no reuse - a cache with a 2% hit rate is pure overhead.
- Data already fast to fetch: caching a 0.3 ms primary-key lookup behind a 0.5 ms network hop makes it slower.
Say these points
- LRU adapts fast but is scan-vulnerable; LFU resists scans but adapts slowly.
- Use TTL for freshness alongside a size-based eviction policy, not instead of one.
- Size by the knee of the hit-rate curve - usually ~10% of the dataset.
- Track origin load and tail latency, not just hit rate.
- Some data should never be cached; write-heavy and low-reuse data are the clearest cases.
Avoid these mistakes
- Using LRU where a nightly batch job scans the dataset.
- LFU without decay, so last month's hits never age out.
- Optimising hit rate while origin load stays unchanged.
- Caching objects large enough to evict the entire hot set.
Expect these follow-ups
- How does Redis's approximated LRU differ from true LRU, and why?
- How would you detect that your cache is being scan-polluted?
- What eviction policy would you choose for a CDN, and why?
Showing 3 of 3 questions for caching-strategies-and-eviction-policies.
Check your understanding
4 questions · no sign-up, nothing stored
Hands-on challenge
Build it - this is what you talk about in a deep-dive round.
Add caching to a slow endpoint and prove it
Take a real endpoint backed by a database and add a cache layer that survives all three failure modes in this lesson.
Requirements
- Implement cache-aside with versioned keys, jittered TTLs and negative caching.
- Add single-flight or probabilistic early recompute and demonstrate it prevents a stampede under load.
- Measure hit rate, p50/p99 latency and origin QPS before and after.
- Plot hit rate against cache size at four sizes and identify the knee.
- Simulate a total cache outage under load and record what happens to the database.
Stretch goals
- Add a small in-process L1 cache in front of Redis and measure the additional gain.
- Implement a Bloom filter for existence checks and measure its effect on penetration.