Mitigating Cache Miss Storms with Single-Writer Locks and Stale Data Serving

The Cache Miss Storm Problem

In a cache-aside architecture, when a cache entry expires, a sudden surge of concurrent requests for that key can all miss the cache. Each of these requests then proceeds to query the backend database simultaneously to recompute the value. This phenomenon, known as a "cache miss storm" or "thundering herd problem," can drastically increase database load, spike API latency, and potentially lead to service degradation or outages, even with a seemingly efficient caching layer.

The Single-Writer Lock and Graceful Stale Serving Pattern

To mitigate cache miss storms, the article advocates for a pattern that coordinates recomputation using a distributed lock. The core idea is to ensure that when a cache key expires, only one of the contending requests is allowed to recompute the value from the database. Other concurrent requests for the same key will either wait for the recomputation to complete and fetch the fresh value or, crucially, be served a slightly stale version of the data if available. This approach prevents the database from being overwhelmed by duplicate queries.

Architectural Components and Flow

1. Cache-Aside Check: First, attempt to retrieve the data from the primary cache. If found and fresh, return it.
2. Distributed Lock Acquisition: If the primary cache misses (or the data is stale), attempt to acquire a distributed lock for that specific key (e.g., using `SETNX` in Redis or `add` in Memcached). This lock typically has a short Time-To-Live (TTL).
3. Recomputation (Lock Holder): The request that successfully acquires the lock proceeds to recompute the value from the backend database. Once recomputed, it updates the primary cache with the fresh data and then releases the lock (ensuring it only releases locks it owns).
4. Waiting/Stale Serving (Contenders): Requests that failed to acquire the lock will not hit the database. Instead, they can either spin-wait for a short period, periodically checking if the primary cache has been updated, or immediately return a gracefully stale version of the data if one is available (e.g., stored with a longer TTL in a secondary stale-data cache).
5. Fallback: As a last resort, if no fresh or stale data can be served after a grace period (and the lock has potentially expired or the recomputation failed), the request might still hit the database, but this scenario should be rare under normal operation.

Trade-offs and Considerations

While this pattern significantly improves performance, it introduces trade-offs. The primary concern is if the lock-holder fails or takes an excessively long time to recompute, other requests might experience increased latency or serve older stale data. Mitigation strategies include setting short lock TTLs (e.g., 200ms) and ensuring robust fallback mechanisms, such as serving stale data for a longer grace period. This balances consistency and availability, favoring availability and reduced database load for read-heavy workloads.

import time
import uuid

LOCK_TTL = 0.2 # seconds
STALE_GRACE = 10 # seconds we allow stale data after expiry

def get_user_profile(user_id):
    key = f"user:{user_id}"
    profile = cache.get(key)
    if profile is not None:
        return profile

    lock_key = f"lock:{key}"
    token = str(uuid.uuid4())
    acquired = cache.add(lock_key, token, ttx=LOCK_TTL)

    if acquired:
        try:
            profile = db.query("SELECT * FROM users WHERE id = %s", user_id)
            cache.set(key, profile, ttl=60)
        finally:
            if cache.get(lock_key) == token:
                cache.delete(lock_key)
        return profile

    deadline = time.time() + STALE_GRACE
    while time.time() < deadline:
        time.sleep(0.01)
        profile = cache.get(key)
        if profile is not None:
            return profile
        if not cache.get(lock_key):
            break

    stale = cache.get(f"{key}:stale")
    if stale is not None:
        return stale

    profile = db.query("SELECT * FROM users WHERE id = %s", user_id)
    cache.set(key, profile, ttl=60)
    cache.set(f"{key}:stale", profile, ttl=STALE_GRACE * 2)
    return profile