Caching Strategies and Invalidation
Cache-aside, read-through, write-through, write-back and TTL invalidation, with a measured stampede (50 calls vs 1), an update-race reproduction and an LRU hit-ratio simulation.
A caching strategy decides how data gets into a cache and how stale entries get out. A common web pattern is cache-aside reads with a TTL and delete-on-write: update the database, then delete the key. Interviewers expect the reason to delete instead of overwrite: concurrent writers can apply cache updates out of order and leave an old value cached.
A cache keeps a fast copy of slow data, and a caching design is mostly a choice of how entries get in (cache-aside, read-through) and how stale ones get out (TTL, delete on write). Most bugs come from invalidation races and stampedes on expired hot keys, both of which are reproduced below.
- In cache-aside (lazy loading), the application checks the cache, loads from the database on a miss and fills the cache, so only requested data gets cached.
- Write-back caching acknowledges a write after updating the cache and flushes to the database later, so writes are fast but can be lost if the cache node dies before a flush.
- A reproduced update race with two writers left db = 2 and cache = 1, which is why deleting the cache key on write is safer than overwriting it.
- In a simulation with 100,000 Zipf-distributed keys and an LRU cache, caching 1 percent of keys gave a 50.4 percent hit ratio and caching 10 percent gave 72.9 percent.
- In a cache stampede test, 50 threads reading one missing key made 50 database calls without a lock and 1 database call with a lock and a second check inside it.
01What a cache buys, and what it costs
A cache keeps a copy of data that is expensive to fetch in a place that is cheap to read, usually memory in front of a database or a remote service. A read that finds the data is a hit. A read that does not is a miss, and pays the full cost plus the cost of filling the cache.
The benefit is lower latency and less load on the backing store. The costs are memory, a second copy that can disagree with the first, and new failure modes such as thundering herds. Every strategy below is a different answer to the same two questions: how does data get into the cache, and how does wrong data get out.
02Read strategies: cache-aside and read-through
Cache-aside (also called lazy loading) is the default in most web applications. The application code does the work:
def get_user(uid):
user = cache.get(f"user:{uid}")
if user is None:
user = db.query_user(uid)
cache.set(f"user:{uid}", user, ttl=300)
return userOnly requested data gets cached, and a cache outage degrades to slower reads instead of an outage. The downside is that the first request for each key is always slow, and the cached copy can be stale until it expires or is invalidated.
Read-through puts the same load-on-miss logic inside the cache library or service, so the application only talks to the cache. Behaviour is the same; the difference is who owns the loader code. The Azure Architecture Center describes cache-aside as the pattern that emulates read-through when the cache does not provide it natively.
03Write strategies: write-through, write-back, write-around
Write-through writes to the cache and the database in the same operation. Reads stay fresh, writes are as slow as the database, and data that is never read again still occupies the cache.
Write-back (write-behind) acknowledges after writing the cache and flushes to the database later, in batches. Writes are fast, but if the cache node dies before a flush, those writes are lost. Use it only when losing a short window of writes is acceptable, or when the cache itself is durable.
Write-around writes straight to the database and leaves the cache untouched, so the next read misses and fills it. It avoids filling the cache with data written once and never read.
A common pairing for web services is cache-aside reads with invalidate-on-write: update the database, then delete the cached key. Plain write-around would leave the old entry in the cache until its TTL expires, so the delete is what keeps reads fresh. Delete is safer than overwrite, as the next section shows.
04Invalidation: TTL, delete-on-write, and a race that bites
A TTL (time to live) gives every entry an expiry. It bounds how stale data can get and cleans up after missed invalidations, so it works as a safety net even when you also invalidate explicitly.
Explicit invalidation deletes the key whenever the underlying row changes. Prefer delete to overwrite. I reproduced the reason with two threads: writer W1 sets the database to 1 but its cache update is slow; writer W2 sets the database to 2 and updates the cache immediately; then W1's late cache write lands. Result: db = 2 cache = 1. The cache now disagrees with the database until the TTL ends. With delete-on-write, the worst case is a missing entry that the next read refills from the database.
Even delete-on-write has a narrow race: a reader loads the old value, a writer updates the database and deletes the key, then the reader stores the old value. It is rare, and the TTL is what bounds the damage. For data where even brief staleness is unacceptable (account balances, stock counts), read from the primary database and do not cache.
05Eviction and hit ratio, measured
A cache has finite memory, so something must be evicted. LRU (least recently used) removes the entry untouched for the longest time and is the usual default. LFU removes the least frequently used, FIFO removes the oldest, and random eviction is cheaper than it sounds.
How much memory is enough? I ran a simulation, not a production measurement: 100,000 keys, 300,000 reads where key popularity follows a Zipf-like distribution (probability proportional to 1/rank), cache-aside with an LRU cache.
- 0.1 percent of keys cached (100 entries): 28.9 percent hits
- 1 percent (1,000): 50.4 percent
- 5 percent (5,000): 66.2 percent
- 10 percent (10,000): 72.9 percent
- 30 percent (30,000): 82.3 percent
The shape matters more than the exact numbers: the first small slice of memory buys most of the benefit, and each further slice buys less. Real traffic can be more or less skewed than this model, so measure your own hit ratio before sizing the cache.
06Cache stampede
A stampede (thundering herd) happens when a popular entry expires and every request that arrives before it is refilled goes to the database. I ran it with 50 threads reading one missing key, with a database call that sleeps 50 ms:
- no lock: 50 database calls
- with a lock and a second check inside the lock: 1 database call
with lock:
if "hot" not in cache: # re-check after getting the lock
cache["hot"] = slow_db()
return cache["hot"]In a multi-server system the lock must be shared (a short-lived key in the cache with an expiry) or each server collapses only its own requests. Other mitigations: add random jitter to TTLs so keys written together do not expire together, refresh hot keys before they expire, or serve the stale value while one worker refreshes it. Wikipedia's article on cache stampedes lists locking and probabilistic early expiration among the standard approaches.
07Common interview questions
Q: Cache-aside versus read-through?
A: Same behaviour; in cache-aside the application loads and fills, in read-through the cache layer does.
Q: Write-through versus write-back?
A: Write-through is consistent and slower; write-back is faster but can lose recent writes if the cache fails before flushing.
Q: Why delete the key on write instead of updating it?
A: Concurrent writers can apply cache updates out of order and leave an old value cached; a delete just forces a fresh read.
Q: What is a cache stampede and how do you stop it?
A: Many requests miss on the same expired key together. Use a per-key lock or single-flight loading, TTL jitter, or early refresh.
Q: How do you implement an LRU cache in O(1)?
A: A hash map from key to node plus a doubly linked list ordered by recency; Python's OrderedDict does both.
Q: When should you not cache?
A: When data must always be exactly current, when it is rarely read twice, or when it is cheap to compute.