Caching Strategies Invalidation and Stampede Control

Published by Programming Line in System Design and Distributed Systems. Last updated .

Purpose and Outcome

Caching is the deliberate reuse of previously computed or fetched data so a system can answer common requests without repeating expensive work. In system design, a cache usually sits between request-serving code and a slower origin: a database, search cluster, object store, remote API, or CPU-heavy renderer. The outcome is lower latency, lower origin load, and often lower cost. The hard part is not putting data into a cache. The hard part is deciding when cached data is still acceptable, how to remove or bypass stale entries, and how to avoid a cache stampede when many callers miss at the same time.

This lesson focuses on three mechanisms that are often designed together: caching strategy, invalidation, and stampede control. A caching strategy defines how entries are read and written. Invalidation defines how entries become unusable after the underlying data changes. Stampede control protects the origin when many requests all need the same missing or expired value. These concerns matter in the caching, messaging, and streams section because caches often consume change events, publish invalidation messages, and protect downstream services from bursts.

How Caches Work Internally

A cache entry is normally a key, a value, metadata, and an eviction policy decision. The key identifies the cached result, such as user:42 or search:q=shoes:page=1. The value is the serialized response or object. Metadata commonly includes creation time, expiration time, version, size, and sometimes a refresh-in-progress flag. The eviction policy decides what to remove when memory is limited. Common policies include least recently used, least frequently used, and size-aware variants.

A cache hit happens when the key exists and the entry is acceptable for the caller. A miss happens when the key is absent, expired, evicted, or rejected by a version check. Misses usually trigger a load from origin. The load path is the danger zone: if a popular key expires at noon, thousands of request handlers can all discover the miss and all query the database. That is the classic cache stampede.

Expiration and invalidation are related but not identical. Expiration is time based: an entry with a time-to-live, or TTL, is considered invalid after a deadline. Invalidation is event based: a write, deployment, import job, or change-data-capture event marks an entry obsolete. Expiration is simple and works even when write events are missed, but it permits stale data until TTL expiry. Invalidation reduces staleness, but it needs reliable key derivation and message delivery. Many production designs use both: invalidate on known writes and also set a TTL as a safety net.

There are several common caching strategies. Cache-aside means the application checks the cache, loads from origin on miss, then writes the cache. Read-through hides that pattern behind the cache client or library. Write-through writes origin and cache in the request path. Write-behind writes to cache first and asynchronously flushes to origin, trading durability complexity for write latency. Refresh-ahead reloads entries before they expire, often for known hot keys.

API and Configuration Anatomy

A practical cache design usually specifies the following: key format, value schema, TTL, negative-cache TTL, maximum entry size, invalidation trigger, miss loader, stampede policy, and fallback behavior. Key format must include every input that changes the result. If a product page differs by locale and currency, the key must include locale and currency. Value schema matters because old cached bytes may be read by newer application code during a deployment. TTL expresses freshness tolerance. Negative caching stores controlled misses, such as user:not_found, to avoid repeated expensive lookups for absent objects.

Stampede policy is often configured per key family. A low-value key may simply miss and reload. A hot homepage fragment may use a single-flight lock, stale-while-revalidate, jittered TTLs, or early refresh. Single-flight means only one request loads a missing key while others wait or receive stale data. Jitter means adding random variation to TTLs so many keys do not expire simultaneously. Stale-while-revalidate means expired data can still be served for a bounded grace period while one worker refreshes it.

Example 1: Cache-Aside With TTL

The first example shows the simplest useful pattern. The application owns the miss path. It checks the cache, loads from the database on miss, and stores the result with a TTL. The fake clock makes the output deterministic.

class FakeClock:
    def __init__(self):
        self.now = 0

    def advance(self, seconds):
        self.now += seconds


class TTLCache:
    def __init__(self, clock):
        self.clock = clock
        self.entries = {}

    def get(self, key):
        item = self.entries.get(key)
        if item is None:
            return None
        value, expires_at = item
        if self.clock.now >= expires_at:
            del self.entries[key]
            return None
        return value

    def set(self, key, value, ttl_seconds):
        self.entries[key] = (value, self.clock.now + ttl_seconds)


clock = FakeClock()
cache = TTLCache(clock)
loads = 0


def load_profile(user_id):
    global loads
    loads += 1
    return f"profile-v{loads}-for-{user_id}"


def read_profile(user_id):
    key = f"user:{user_id}:profile"
    cached = cache.get(key)
    if cached is not None:
        return "HIT", cached
    value = load_profile(user_id)
    cache.set(key, value, ttl_seconds=10)
    return "MISS", value


print(read_profile(42))
print(read_profile(42))
clock.advance(10)
print(read_profile(42))
print("origin loads", loads)

The first call misses and loads the origin. The second call hits because the entry is still fresh. After advancing the clock by 10 seconds, the entry expires and the next call reloads. The expected output is:

('MISS', 'profile-v1-for-42')
('HIT', 'profile-v1-for-42')
('MISS', 'profile-v2-for-42')
origin loads 2

Example 2: Versioned Key Invalidation

Deleting exact keys is difficult when one database row feeds many cache entries. Versioned keys avoid some delete races. Instead of removing the old key, the writer increments a version number. Readers use the latest version in the key, so older entries become unreachable and expire later.

db = {"sku-7": {"name": "Keyboard", "price": 50}}
versions = {"sku-7": 1}
cache = {}
origin_loads = 0


def cache_key(sku):
    return f"product:{sku}:v{versions[sku]}"


def read_product(sku):
    global origin_loads
    key = cache_key(sku)
    if key in cache:
        return "HIT", cache[key]
    origin_loads += 1
    cache[key] = dict(db[sku])
    return "MISS", cache[key]


def update_price(sku, price):
    db[sku]["price"] = price
    versions[sku] += 1


print(read_product("sku-7"))
print(read_product("sku-7"))
update_price("sku-7", 55)
print(read_product("sku-7"))
print(sorted(cache.keys()))
print("origin loads", origin_loads)

The important behavior is that the old cached value remains physically present but is no longer selected. This is useful when invalidation messages can arrive before or after a reader is in flight. The expected output is:

('MISS', {'name': 'Keyboard', 'price': 50})
('HIT', {'name': 'Keyboard', 'price': 50})
('MISS', {'name': 'Keyboard', 'price': 55})
['product:sku-7:v1', 'product:sku-7:v2']
origin loads 2

Example 3: Stampede Control With Single Flight

A stampede occurs when concurrent callers all observe the same miss and all load the origin. Single-flight coalesces those callers so only one load happens per key. In real systems this may be a local mutex, a distributed lock, or a cache-native feature. The following deterministic batch simulation shows the effect.

def origin_load(key):
    origin_load.calls += 1
    return f"value-for-{key}"


origin_load.calls = 0


def without_singleflight(key, callers):
    cache = {}
    results = []
    for _ in range(callers):
        if key not in cache:
            value = origin_load(key)
            cache[key] = value
        results.append(cache[key])
    return results


def with_singleflight(key, callers):
    cache = {}
    waiters = list(range(callers))
    if key not in cache:
        cache[key] = origin_load(key)
    return [cache[key] for _ in waiters]


origin_load.calls = 0
print(without_singleflight("home", 5))
print("loads without protection", origin_load.calls)
origin_load.calls = 0
print(with_singleflight("home", 5))
print("loads with singleflight", origin_load.calls)

This simplified code processes sequentially, so it does not fully recreate concurrent timing. It still demonstrates the design goal: for one hot key and one refresh window, many callers should share one origin result. The expected output is:

['value-for-home', 'value-for-home', 'value-for-home', 'value-for-home', 'value-for-home']
loads without protection 1
['value-for-home', 'value-for-home', 'value-for-home', 'value-for-home', 'value-for-home']
loads with singleflight 1

Because the sequential cache fills immediately, both paths show one load. In a real concurrent miss, the unprotected path can issue one load per caller before any caller writes the cache. The single-flight path prevents that race by making the first caller the owner of the refresh and making the others wait or use stale data.

Design Choices and Trade-offs

Cache-aside is flexible and easy to adopt, but every caller must implement miss behavior correctly. Read-through centralizes miss behavior, but it can hide expensive origin calls behind what looks like a cheap cache API. Write-through keeps cache and origin aligned in the write path, but adds write latency and failure combinations. Write-behind can absorb bursts, but a cache loss before flush can lose data unless the design includes a durable queue.

TTL length is a product decision as much as a technical one. Short TTLs reduce staleness but increase origin traffic. Long TTLs improve hit rate but can serve obsolete values. Jittered TTLs reduce synchronized expiry, but make exact freshness less predictable. Versioned keys avoid delete races, but consume memory until old versions expire. Explicit deletes save memory sooner, but missed invalidation events can leave stale data behind.

For stampede control, waiting gives fresher answers but increases tail latency. Serving stale data keeps latency low but may violate freshness requirements. Distributed locks can protect a shared database across many application instances, but lock timeouts and ownership must be carefully handled. Local locks are simpler and fast, but only coalesce requests within one process.

Failure Modes and Troubleshooting

Symptom: database CPU spikes every hour. A likely cause is synchronized TTL expiry for many hot keys, often because a deployment, import, or warmup populated them at the same time. Diagnose by graphing cache misses by key family and comparing miss spikes with origin load. Check whether TTLs are identical. Correct it by adding TTL jitter, staggering warmups, or using refresh-ahead for hot keys.

Symptom: users see old prices after an update. The cause may be incomplete invalidation key coverage. A write invalidated product:sku but not category:page, search:query, or a rendered fragment containing the same price. Diagnose by tracing which read paths include the stale field and listing their cache keys. Correct it by deriving affected keys from a dependency map, using versioned namespaces, or consuming change events to invalidate materialized views.

Symptom: request latency increases during cache refresh. The cause may be a single-flight policy that makes every caller wait behind a slow origin load. Diagnose by measuring lock wait time separately from origin time. Correct it by bounding wait time, serving stale data during refresh, or moving refresh work to a background worker.

Symptom: cache memory grows unexpectedly. Versioned keys or high-cardinality keys may be accumulating. Diagnose by sampling key prefixes, entry sizes, and version counts. Correct it by setting TTLs on old versions, limiting query parameters included in cacheable keys, and rejecting cache entries above a configured size.

Security, Performance, and Reliability Implications

Caches can leak data when keys omit authorization-relevant dimensions. If an account-specific response is cached only by URL, one user may receive another user’s data. Include tenant, user, role, locale, and permission version when they affect output, or do not cache that response. Avoid storing secrets unless the cache is encrypted and access controlled like the origin.

Performance depends on hit rate, object size, network distance, serialization cost, and miss amplification. A remote cache can be slower than local memory for tiny objects, but still valuable when the origin is much slower. Reliability improves when stale serving absorbs origin failures, but only if stale limits are explicit. A cache should degrade intentionally: either fail open with bounded stale data for low-risk content, or fail closed for sensitive and strongly consistent data.

Hands-on Lab: Add Jitter and Stale Serving

Prerequisites: Python 3, a terminal, and no external services. The lab simulates a hot key, TTL jitter, and stale-while-revalidate behavior.

  1. Create a temporary file named cache_lab.py.
  2. Paste the following code into the file.
  3. Run python cache_lab.py.
  4. Verify that requests after soft expiry can receive a stale value while refresh occurs.
  5. Cleanup by deleting cache_lab.py.
class Entry:
    def __init__(self, value, soft_expiry, hard_expiry):
        self.value = value
        self.soft_expiry = soft_expiry
        self.hard_expiry = hard_expiry
        self.refreshing = False


class Cache:
    def __init__(self):
        self.entry = None
        self.loads = 0

    def load_origin(self):
        self.loads += 1
        return f"payload-v{self.loads}"

    def read(self, now):
        if self.entry is None or now >= self.entry.hard_expiry:
            value = self.load_origin()
            self.entry = Entry(value, now + 5, now + 20)
            return "MISS", value
        if now >= self.entry.soft_expiry:
            if not self.entry.refreshing:
                self.entry.refreshing = True
                old = self.entry.value
                value = self.load_origin()
                self.entry = Entry(value, now + 5, now + 20)
                return "STALE_REFRESHED", old
            return "STALE", self.entry.value
        return "HIT", self.entry.value


cache = Cache()
print(cache.read(0))
print(cache.read(3))
print(cache.read(5))
print(cache.read(6))
print("origin loads", cache.loads)

The expected output is:

('MISS', 'payload-v1')
('HIT', 'payload-v1')
('STALE_REFRESHED', 'payload-v1')
('HIT', 'payload-v2')
origin loads 2

The verification point is the third line. At time 5, the value has passed soft expiry but not hard expiry, so the caller receives the old payload while the cache refreshes. At time 6, the refreshed value is available. In a real implementation, the refresh may run asynchronously; this simulation performs it immediately while preserving the externally visible stale response.

Assessment Exercises

  1. A product update changes price, inventory, and eligibility rules. Identify at least four cache keys or key families that may need invalidation, and explain how you would find them.
  2. You operate a homepage cache with a 60-second TTL and observe origin spikes every minute. Propose two changes that reduce the spike without making all content permanently stale.
  3. For a banking balance endpoint, decide whether to use cache-aside, write-through, stale-while-revalidate, or no cache. Justify the choice using freshness and security constraints.
  4. A distributed lock protects refreshes, but some requests wait longer than the user timeout. What metrics would you add, and what policy change would you test first?
  5. Design a cache key for a search result page that varies by query, page, sort order, tenant, and locale. Explain which parameters must be normalized before key construction.

Summary

Effective caching is a controlled compromise between speed, freshness, memory, and origin protection. Cache-aside, read-through, write-through, write-behind, and refresh-ahead place responsibility in different parts of the system. TTLs provide automatic expiry, while invalidation reacts to known changes. Stampede control prevents a popular miss from becoming an outage by coalescing refreshes, adding jitter, serving bounded stale data, or refreshing ahead of demand. The right design starts with the data’s freshness requirement, then chooses key structure, invalidation scope, and miss behavior that keep the origin stable under load.