Caching Strategies & Invalidation

By the end of this lesson you will be able to choose a caching strategy, calculate how much load a cache removes from a database, keep cached data fresh enough, and prevent the "cache stampede" that takes down many busy sites.

Why cache at all?

A cache is a small, fast store that keeps copies of data you will probably need again. Reading from memory takes well under a millisecond. Running a database query might take 5 to 50 ms and uses the database's limited CPU and disk.

Think of a chaiwala near a college in Rohtak. Making each cup from scratch takes five minutes. So at 10:55, just before the break, he brews a big pot. Students get tea instantly. The pot is his cache. He accepts one risk: if someone wants it without sugar, the pot does not help, and if the pot sits for an hour, the tea goes cold. Those two problems, misses and staleness, are what this lesson is about.

The basic words, which the LRU Cache lesson in the DSA course also uses:

• Hit: the data is in the cache. Miss: it is not.
• Hit ratio: hits divided by all reads.
• Eviction: removing items when the cache is full, often with LRU (least recently used).
• TTL (time to live): how long an item may stay before it expires.

How much does a cache help?

The database only sees the misses. So the hit ratio decides everything.

reads_per_sec = 20_000
db_ms, cache_ms = 20.0, 0.5

for hit_ratio in [0.0, 0.50, 0.90, 0.95, 0.99]:
    db_reads = reads_per_sec * (1 - hit_ratio)
    avg_ms = hit_ratio * cache_ms + (1 - hit_ratio) * (cache_ms + db_ms)
    print(f"hit ratio {hit_ratio:4.0%}: database gets {db_reads:7,.0f} reads/s, "
          f"average read {avg_ms:5.2f} ms")

hit ratio   0%: database gets  20,000 reads/s, average read 20.50 ms
hit ratio  50%: database gets  10,000 reads/s, average read 10.50 ms
hit ratio  90%: database gets   2,000 reads/s, average read  2.50 ms
hit ratio  95%: database gets   1,000 reads/s, average read  1.50 ms
hit ratio  99%: database gets     200 reads/s, average read  0.70 ms

Look at 95% versus 99%. The hit ratio rose by only four points, but database load fell five times. Small improvements at the top matter a lot. It also means that if the cache suddenly empties (a restart, a deployment), the database gets 100 times its usual load. Keep that in mind; we return to it below.

Four caching strategies

Cache-aside (lazy loading) is the most common. The application checks the cache; on a miss it reads the database and puts the result in the cache.

read:  app -> cache? hit -> return
                     miss -> database -> put in cache -> return
write: app -> database, then delete the cache key

Read-through looks the same to the app, but the cache library itself loads from the database on a miss.

Write-through writes to the cache and the database together, so the cache is always up to date. Writes are slower, and you may cache data nobody reads.

Write-back (write-behind) writes to the cache only and flushes to the database later in batches. Writes are very fast, but data can be lost if the cache dies before flushing. It suits counters such as "views" where losing a few is acceptable, not payments.

Here is cache-aside with a TTL, working on a product catalogue:

class CacheAside:
    def __init__(self, db, ttl):
        self.db, self.ttl = db, ttl
        self.cache = {}                       # key -> (value, expires_at)
        self.hits = self.misses = 0

    def get(self, key, now):
        entry = self.cache.get(key)
        if entry and entry[1] > now:
            self.hits += 1
            return entry[0]
        self.misses += 1
        value = self.db[key]                  # the slow database read
        self.cache[key] = (value, now + self.ttl)
        return value

    def update(self, key, value):
        self.db[key] = value                  # 1. write the database first
        self.cache.pop(key, None)             # 2. then delete (not update) the cache key

db = {"saree:101": 2499, "saree:102": 1899}
c = CacheAside(db, ttl=60)
print(c.get("saree:101", now=0), c.get("saree:101", now=10))
c.update("saree:101", 2199)                   # Diwali discount
print(c.get("saree:101", now=11))
print(c.get("saree:102", now=12), c.get("saree:102", now=80))   # second read is after TTL
print("hits", c.hits, "misses", c.misses)

2499 2499
2199
1899 1899
hits 1 misses 4

Invalidation: keeping data fresh

There is a well-known joke in computing, usually credited to Phil Karlton, that the two hard things are cache invalidation and naming things. Invalidation means removing or updating cached data when the source changes.

Common approaches:

1. TTL only. Data may be stale for up to the TTL. Simple, and fine for things like a restaurant's rating.
2. Delete on write. After updating the database, delete the cache key. The next read loads fresh data.
3. Versioned keys. Put a version in the key (menu:42:v7). Changing the version makes old entries unreachable; they expire on their own.
4. Change events. The database's change log publishes "row changed" events, and a consumer deletes the matching keys. You will see event streams in Message Queues & Event Streaming.

Why delete rather than update the cache on write? If two writers update the same key at nearly the same time, their cache updates can arrive in the opposite order to their database writes, leaving the old value in the cache for the whole TTL. Deleting is safer, because the next read always loads from the database. Even deleting has a rare race (a slow reader puts an old value back just after the delete), which is why most teams also keep a TTL as a safety net.

Cache stampede

When a very popular key expires, hundreds of requests can miss at the same moment and all hit the database together. This is a cache stampede (also called the thundering herd problem). Picture the moment the chaiwala's pot runs out at break time and fifty students crowd the stove.

Fixes:

• Request coalescing (single flight): only the first miss loads from the database; the others wait for that result.
• Jittered TTLs: add a small random amount to each TTL so keys do not all expire at the same second.
• Early refresh: refresh a hot key in the background shortly before it expires.

import random

def stampede(requests_at_expiry, coalesce):
    db_queries = 0
    loading = False
    for _ in range(requests_at_expiry):
        if coalesce:
            if not loading:
                loading = True
                db_queries += 1                # only the first miss goes to the DB
            # the rest wait for that one result
        else:
            db_queries += 1                    # every miss goes to the DB
    return db_queries

print("Without coalescing:", stampede(500, coalesce=False), "database queries")
print("With coalescing   :", stampede(500, coalesce=True), "database query")

rng = random.Random(3)
base_ttl = 300
plain = [base_ttl for _ in range(5)]
jittered = [base_ttl + rng.randint(0, 60) for _ in range(5)]
print("Plain TTLs   :", plain)
print("Jittered TTLs:", jittered)

Without coalescing: 500 database queries
With coalescing   : 1 database query
Plain TTLs   : [300, 300, 300, 300, 300]
Jittered TTLs: [315, 337, 334, 308, 323]

Where caches live

Caches exist at many levels, and a request may pass through several:

CDNs and distributed caches get their own lesson next: CDNs & Distributed Caches.

Common mistakes

• Caching without a TTL, so a missed invalidation leaves wrong data forever.
• Updating the cache instead of deleting it on writes, causing ordering races.
• Caching personal data under a shared key, so one user sees another user's details.
• Treating the cache as the source of truth for data you cannot lose.
• Ignoring cold starts. After a cache restart the database must survive the full load, or you must warm the cache first.

Key points

• A cache trades a little freshness for a big drop in latency and database load.
• The database sees only misses, so small hit-ratio gains at the top remove a lot of load.
• Cache-aside is the default; write-through keeps the cache fresh; write-back is fast but risky.
• Invalidate by deleting keys on write, keep a TTL as a safety net, or use versioned keys.
• Prevent stampedes with request coalescing, jittered TTLs and early refresh.

class CacheAside:
    def __init__(self, db, ttl):
        self.db, self.ttl, self.cache = db, ttl, {}
        self.hits = self.misses = 0

    def get(self, key, now):
        entry = self.cache.get(key)
        if entry and entry[1] > now:
            self.hits += 1
            return entry[0]
        self.misses += 1
        self.cache[key] = (self.db[key], now + self.ttl)
        return self.db[key]

    def get_many(self, keys, now):
        return {k: self.get(k, now) for k in keys}

c = CacheAside({"saree:101": 2499, "saree:102": 1899}, ttl=60)
print(c.get_many(["saree:101", "saree:102"], now=0))
print(c.get_many(["saree:101", "saree:102"], now=5))
print("hits", c.hits, "misses", c.misses)

{'saree:101': 2499, 'saree:102': 1899}
{'saree:101': 2499, 'saree:102': 1899}
hits 2 misses 2