DevPath
Tracks

Caching Strategies

Cache-aside, write-through, and write-back patterns, TTLs, invalidation, and how to stop a cache stampede with request coalescing.

intermediate40 min#caching#ttl#invalidation#stampede#consistency

Prerequisites: Caches and LRU Eviction, Load Balancing and Scaling

Why it matters

Most systems read far more than they write, and the same few items are read again and again. A cache keeps those items in fast memory so the slow, expensive source (usually a database) is hit less often. A good cache can cut latency and let a small database serve a large audience. A bad one serves stale data, hides bugs, and collapses under load at the worst moment.

Intuition

A cache is a sticky note on your monitor. Looking at the note is instant; walking to the filing cabinet is slow. The note is only useful if it is usually right, and it is only safe if you have a rule for when to throw it away. Almost every caching decision is about that rule: how stale can this answer be, and who is responsible for refreshing it?

How it works

Where caches live: in the browser, at a CDN, inside the application process, or in a shared cache service such as Redis or Memcached. A shared cache gives every app server the same view; an in-process cache is faster but different on each server.

Read patterns

  • Cache-aside (lazy loading): the application checks the cache; on a miss it reads the database and writes the result into the cache. Simple and the most common. Only requested data is cached, but the first request after a miss is slow.
  • Read-through: the cache itself loads from the database on a miss. The application only talks to the cache.

Write patterns

  • Write-through: write to the cache and the database together before returning. Reads stay fresh and data is durable, at the cost of slower writes.
  • Write-back (write-behind): write to the cache and flush to the database later in batches. Very fast writes, but data can be lost if the cache dies before the flush.
  • Write-around: write only to the database and let the cache fill on the next read. Avoids filling the cache with data that is never read.
AppCacheDatabasewrite-through: put p1 = v2write p1 = v2okack (after DB confirms)write-back: put p1 = v3ack immediatelyflush p1 = v3 (later, batched)
Write-through (top four messages) acknowledges only after the database has the data. Write-back (bottom three) acknowledges first and flushes later, so if the cache dies before the last arrow, v3 is lost.

Expiry and eviction

  • TTL (time to live): each entry expires after a fixed time. It bounds staleness with no coordination.
  • Eviction policy: when memory is full, remove something. LRU (least recently used) is the common default; LFU (least frequently used) favors popular items.

Invalidation: when the source changes, the cached copy must go. The usual approach is to delete the cache key on write rather than update it, so the next read repopulates it. Updating in place is riskier because two concurrent writers can leave the cache holding the older value. A TTL is your safety net for the invalidations you miss.

The stampede problem. When a popular key expires, thousands of requests miss at once and all hit the database to recompute the same value. This is a cache stampede (or thundering herd). Defenses:

  • Request coalescing (single flight): the first miss loads the value; concurrent misses for the same key wait for that one load.
  • Jittered TTLs: add a random offset so many keys do not expire together.
  • Refresh ahead: refresh hot keys shortly before they expire.
  • Serve stale while revalidating: return the old value while one worker refreshes it.
R1
0
R2
1
R3
2
R4
3
R5
4
DB reads: 0
5
The hot key p1 has just expired and five requests arrive at the same moment.
step 1 / 5

Five requests arrive just after p1 expires. Without coalescing the database does the same work five times; with single flight it does it once. This matches the code's output (5 versus 1).

 request --> cache --hit--> return
               |
              miss --> database --> fill cache --> return

Here are two reads of the same key in cache-aside. The first misses and pays for the database; the second hits.

AppCacheDatabaseget p1missread p1v1set p1 = v1 (with TTL)get p1 (next request)hit: v1
Cache-aside: the app does the work on a miss (four messages, then a fill). The next request needs only two messages and never touches the database.
OperationTimeNotes
Cache hitO(1)In-memory hash lookup plus a network hop
Cache miss (cache-aside)cache + DB + cache writeSlower than having no cache
Write-throughDB write + cache writeFresh reads, slower writes
Write-backcache write only (flush later)Fast, but risks data loss

Code: TTL cache, invalidation, and single flight

We inject a fake clock so expiry is testable and the output is deterministic. The asynchronous loader stands in for a slow database.

import asyncio
 
class Clock:
    def __init__(self):
        self.now = 0
 
class TTLCache:
    def __init__(self, clock):
        self.clock, self.data = clock, {}
    def get(self, key):
        item = self.data.get(key)
        if item is None or item[1] <= self.clock.now:
            self.data.pop(key, None)
            return None
        return item[0]
    def set(self, key, value, ttl):
        self.data[key] = (value, self.clock.now + ttl)
    def delete(self, key):
        self.data.pop(key, None)
 
clock = Clock()
cache = TTLCache(clock)
db = {"p1": "v1"}
db_reads = 0
inflight = {}
 
async def load(key):
    global db_reads
    db_reads += 1
    await asyncio.sleep(0.01)  # pretend the database is slow
    return db[key]
 
async def get_naive(key):
    value = cache.get(key)
    if value is None:
        value = await load(key)
        cache.set(key, value, 60)
    return value
 
async def get_single_flight(key):
    value = cache.get(key)
    if value is not None:
        return value
    task = inflight.get(key)
    if task is None:
        async def fill():
            v = await load(key)
            cache.set(key, v, 60)
            return v
        task = asyncio.ensure_future(fill())
        inflight[key] = task
        task.add_done_callback(lambda _: inflight.pop(key, None))
    return await task
 
def update(key, value):
    db[key] = value
    cache.delete(key)  # invalidate; the next read repopulates
 
async def main():
    global db_reads
    await get_naive("p1"); print("t=0 read, db reads:", db_reads)
    clock.now = 30
    await get_naive("p1"); print("t=30 read, db reads:", db_reads)
    clock.now = 61
    await get_naive("p1"); print("t=61 read (expired), db reads:", db_reads)
 
    cache.delete("p1"); db_reads = 0
    await asyncio.gather(*[get_naive("p1") for _ in range(5)])
    print("burst of 5, naive, db reads:", db_reads)
 
    cache.delete("p1"); db_reads = 0
    await asyncio.gather(*[get_single_flight("p1") for _ in range(5)])
    print("burst of 5, single flight, db reads:", db_reads)
 
    update("p1", "v2")
    print("after update:", await get_single_flight("p1"))
 
asyncio.run(main())

Both versions print:

t=0 read, db reads: 1
t=30 read, db reads: 1
t=61 read (expired), db reads: 2
burst of 5, naive, db reads: 5
burst of 5, single flight, db reads: 1
after update: v2

The naive version sent five identical database queries for one missing key; coalescing sent one. At real scale that is the difference between one query and thousands.

Common pitfalls

  • Caching without a staleness budget. Decide how wrong an answer may be and for how long, then pick the TTL from that.
  • Stampedes on hot keys. A single popular key expiring can take down a database. Coalesce, jitter, or refresh ahead.
  • Caching errors and empty results. Cache a "not found" briefly on purpose (negative caching) but never cache a transient failure for a long time.
  • Unbounded keys. Keys that include user input or timestamps never repeat, so the cache fills and evicts useful data.
  • Treating the cache as the source of truth. It can be wiped at any time. The system must still work, slowly, without it.
  • Write-back without a plan for loss. Unflushed writes vanish if the cache node dies.

Practice

Pick a pattern easy

Hint

Match each workload to a read and write pattern.

Show solution

A product page that is read constantly and edited rarely suits cache-aside with delete-on-write and a modest TTL. A like counter that is incremented thousands of times a second suits write-back or batching, accepting a small loss window, because writing each increment to the database is too slow.

Choose a TTL easy

Hint

Start from how stale users can tolerate the data being.

Show solution

Exchange rates shown for information might tolerate a minute of staleness; a user's own profile after they edit it must update immediately, so you invalidate on write and use the TTL only as a backstop. The TTL is a business decision as much as a technical one.

Add jitter medium

Hint

Randomize so that keys written together do not expire together.

Show solution

Set ttl = base + random offset, for example up to 10 percent of base. If a million keys were loaded at startup with identical TTLs they would all expire at the same instant and stampede the database; the offset spreads those expirations over a window.

Implement LRU eviction medium

Hint

You need O(1) lookup and O(1) reordering. Which two structures combine well?

Show solution

Use a hash map from key to node plus a doubly linked list ordered by recency. On a hit, move the node to the front. On insert when full, drop the tail. Both operations are O(1). Python's OrderedDict and JavaScript's Map (which keeps insertion order) give a shortcut.

Interview questions

  1. Explain cache-aside. The app reads the cache first, loads from the database on a miss, and fills the cache. Writes go to the database and invalidate the key.
  2. Write-through versus write-back? Write-through is consistent and durable but slower; write-back is faster but risks losing unflushed data.
  3. What is a cache stampede and how do you prevent it? Many concurrent misses for an expired hot key overload the source. Coalesce requests, jitter TTLs, refresh ahead, or serve stale while revalidating.
  4. Why is cache invalidation hard? The cache and the source are separate systems with no atomic update across them, so some window of inconsistency always exists. You bound it with TTLs and careful ordering.

Interviewers look for: stating the staleness trade-off explicitly, knowing more than one write pattern, and naming the stampede problem without being prompted.

Quick check

Why do many designs delete the cache key on a write instead of updating it with the new value?

Finished this lesson?

Further resources

Related lessons