Cache Invalidation, Stampede, and Hot Keys

A cache holds copies. When the source changes, the copies are stale until they are updated or removed. Cache invalidation is the set of mechanisms that limit this staleness. A second class of problems appears under load: when many requests miss the same key or the same set of keys at once, the backing store receives a burst it may not survive. This article covers both.

Invalidation approaches

Practical designs combine a delete-on-write or event-based mechanism with a TTL as a safety net. The TTL bounds the damage when an invalidation message is lost.

The delete-versus-read race

With cache-aside and delete-on-write, this interleaving stores stale data:

sequenceDiagram
    participant R as Reader
    participant W as Writer
    participant C as Cache
    participant D as Database
    R->>C: GET k (miss)
    R->>D: read k (old value)
    W->>D: write k (new value)
    W->>C: DELETE k
    R->>C: SET k (old value)
    Note over C: stale entry until TTL

The window is small but real. Mitigations: a TTL; a delayed second delete a short time after the write; storing a version with the value and rejecting older versions; or a lease (see below).

Leases

A lease is a token the cache hands to the first client that misses a key. Only the lease holder may populate the key. If a delete arrives while a lease is outstanding, the lease is invalidated, and the stale write is rejected. Leases also serialize the reloading of a missing key, which addresses the stampede problem below. This mechanism was described for Memcached at Facebook.

Cache stampede (thundering herd)

A cache stampede occurs when a popular entry expires (or is evicted or deleted) and many concurrent requests miss simultaneously. All of them query the database for the same data and then all write it back. The database load spike can slow it enough to cause timeouts, which cause more misses.

Example: a key is read 1,000 times per second and takes 200 ms to recompute. Between expiry and the first successful write-back, about 1,000 x 0.2 = 200 requests miss and each runs the same query. If the load slows to 2 s under that concurrency, about 2,000 requests pile up.

graph TD
    K["Hot key expires"] --> R1["Request 1: miss"]
    K --> R2["Request 2: miss"]
    K --> R3["Request N: miss"]
    R1 --> DB["Database: N identical queries"]
    R2 --> DB
    R3 --> DB

Request coalescing (single flight)

Allow one request per key to load the value; concurrent requests for the same key wait for that result.

• In process: keep a map from key to an in-flight load. Later requests attach to it instead of starting their own. This limits loads to one per key per process.
• Across processes: acquire a short-lived lock in the cache (for example SET lock:k token NX PX 5000 in Redis). The winner loads and populates; the others wait briefly and re-read the cache, or serve stale data.

Locks need an expiry so a crashed loader does not block the key indefinitely.

Serve stale while revalidating

Store the entry with a logical expiry earlier than its physical expiry. When the logical expiry has passed, one request refreshes the value in the background while all requests keep receiving the stale value. Readers never wait on the database. The trade-off is bounded extra staleness.

Probabilistic early expiration

Each reader may decide to refresh before the expiry, with a probability that rises as expiry approaches. The XFetch algorithm refreshes when:

now - delta * beta * ln(rand()) >= expiry

delta is the time the last recomputation took, beta is a tuning factor (1 by default), and rand() is uniform in (0, 1]; the logarithm is negative or zero, so the left side grows beyond now. Expensive values (large delta) are refreshed earlier. Because each reader draws its own random number, the first refresh most likely happens before the entry expires, and once a reader refreshes, the new expiry stops the others. This makes a synchronized miss unlikely, not impossible.

TTL jitter

Adding a random offset to TTLs spreads the expiry times of entries created together, which prevents synchronized expiry of many keys.

Cache avalanche

A cache avalanche is a mass miss across many keys at once, caused by many keys expiring at the same time (for example after a bulk load with an identical TTL) or by a cache node or cluster failing. Mitigations:

• TTL jitter.
• Replication or multiple cache nodes, and consistent hashing so one node's failure remaps only its share of keys. See consistent hashing.
• Warm the cache before directing traffic to a restarted node.
• Rate-limit or shed load at the database and use circuit breakers, so misses cannot overload it.

Cache penetration

Cache penetration is repeated requests for keys that exist in neither the cache nor the database. Each request misses and reaches the database, and nothing is ever cached. It can be accidental (a bug) or an attack using random ids.

• Negative caching: cache the "not found" result with a short TTL.
• Bloom filter: keep a Bloom filter of all valid keys in front of the cache. A negative answer from the filter is definite, so the request is rejected without touching the cache or database. A false positive only causes a normal miss.
• Input validation: reject malformed ids before any lookup.
• Rate limiting per client.

Hot keys

A hot key receives so much traffic that the single cache node owning it becomes the bottleneck, even if the cluster overall has spare capacity. Adding nodes does not help because a key maps to one node.

Mitigations:

• Local (in-process) cache with a short TTL for the hottest keys, so most reads never leave the application instance.
• Key replication: store the value under N derived keys (k#0 ... k#N-1) placed on different nodes; readers pick one at random. Writes and invalidations must update all copies.
• Read replicas of the cache shard.
• Detection: count per-key request rates at the client or proxy (sampled counters or a Count-Min sketch), and promote keys above a threshold to local caching or replication.
• Splitting large values into parts placed on different nodes, when the load is bandwidth and not request count.

Summary of failure modes

Interview questions

• Why can a delete-on-write invalidation still leave stale data? A reader that missed before the write can read the old value from the database and set it in the cache after the writer's delete. TTLs, versioned values, delayed deletes, or leases bound or prevent this.
• How does probabilistic early expiration prevent a stampede? Readers randomly recompute before the real expiry, with higher probability as expiry nears and for values that are costly to compute. The value is usually refreshed by one reader before it expires, so there is no synchronized miss.
• How do penetration and stampede differ? A stampede concerns a key that exists and is temporarily missing from the cache. Penetration concerns keys that do not exist anywhere, so they can never be cached with a real value.
• Why does adding cache nodes not fix a hot key? The key hashes to one node, which serves all requests for it. The fix is to spread the key: local caches or replicated copies under derived keys.