261: Caching II: TTL, Eviction, Invalidation, Stampedes, Hot Keys, and Consistency

Learning outcomes

By the end of this lesson, you can:

explain and apply ttl in a realistic implementation;
explain and apply eviction in a realistic implementation;
explain and apply invalidation in a realistic implementation;
explain and apply stampede in a realistic implementation;
explain and apply hot keys in a realistic implementation.

Prerequisites and retrieval

This lesson assumes the earlier 01–06 foundation and the preceding lessons in this module. Before you read, retrieve one concrete example from a previous project where one of these concerns appeared. Perhaps a session expired, a cache filled up, a record changed while an old value was still cached, or many requests suddenly hit the same uncached key. The point is not to memorize a list of cache terms. It is to make a defensible decision inside a large-scale distributed service, where requirements, traffic, failure modes, cost, and operational constraints all need to be explicit.

Terminology

TTL: A time-to-live bounds how long an entry can remain in the cache. It limits staleness and memory retention, but it also creates expiry churn when entries expire in groups.
Eviction: LRU, LFU, random, and size-based policies determine which entries are removed when the cache is under pressure. Eviction is about capacity, not about whether the authoritative data changed.
Invalidation: An invalidation removes or updates a cached value after an authoritative write. A system might do that directly, publish invalidation events, or rely on a bounded TTL when the freshness contract permits it.
Stampede: A cache stampede occurs when many concurrent requests miss for the same key and all go to the source at once, potentially overwhelming it.
Hot keys: A hot key is one extremely popular key. It can overload a single cache shard or network path even when the overall cache hit rate looks excellent.
Negative caching: Caching “not found” responses can protect the database from repeated misses, but the entry needs a short TTL or an invalidation path. Otherwise, data created shortly afterward can remain invisible through the cache.

Mental model

Treat Caching II: TTL, Eviction, Invalidation, Stampedes, Hot Keys, and Consistency as a design problem with observable inputs, outputs, invariants, and failure modes. The lookup itself is usually the easy part. Cache incidents tend to come from the lifecycle around that lookup: synchronized expiry, stale permissions, capacity pressure, hot keys, and races between a write and an invalidation.

A strong implementation makes its assumptions visible. It narrows uncertainty at system boundaries and leaves enough evidence—tests, types, constraints, metrics, or diagrams—to show why the design is safe. For example, “this value may be stale for at most 30 seconds” is a useful contract; “we put it in Redis” is only an implementation detail.

A useful interview and production sequence is:

requirement -> constraints -> model -> implementation -> failure analysis -> verification

Do not jump from a requirement directly to a library call. First state what must remain true. Then choose the mechanism that enforces it. If a cached permission can be stale for only a short window, say what that window is. If a cache miss must not overload the database, state the concurrency or rate limit that protects it. Those statements make the trade-offs testable.

Deep dive

1. TTL

If an entry were kept forever, it could consume memory indefinitely and could remain wrong after the source changed. A TTL, or time-to-live, puts an upper bound on how long the entry is eligible to serve from the cache. That bounds staleness and helps reclaim memory, but expiry is not free: an expired entry becomes a miss and may trigger a source lookup.

Popular keys make synchronized expiry especially dangerous. If thousands of entries receive the same TTL and are written at nearly the same time, they can all expire together and create a burst of misses. Add jitter, such as a small random variation around the base TTL, so expiry is spread over time. Then measure both freshness and the resulting miss rate; a longer TTL reduces churn but may serve older data.

Decision rule: Use ttl deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design. The relevant questions are how stale a value may be, whether a write can invalidate it sooner, and what the source can tolerate when entries expire.

2. Eviction

Even entries with long TTLs cannot all remain in a finite cache. When the cache reaches its capacity, an eviction policy decides what to remove. LRU removes values that have not been used recently; LFU favors retaining values that are used frequently; random eviction is simple and can be acceptable in some workloads; size-based policies account for the fact that one large value may consume as much space as many small ones.

The policy should match the access pattern rather than being chosen by habit. An eviction is normally just a cache miss, not a correctness failure, because the authoritative source still owns the data. It becomes a correctness problem only if the architecture incorrectly treats the cache as durable state or cannot safely rebuild a missing entry. This distinction matters during capacity incidents: increasing the cache can improve hit rate, but it does not repair stale data or replace a persistence guarantee.

Decision rule: Use eviction deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design. Define what happens after an eviction, and check whether the selected policy protects the entries that are expensive or important to recompute.

3. Invalidation

TTL gives a bounded freshness guarantee, but it does not make a changed value disappear immediately. When a write changes authoritative data, an invalidation strategy determines how and when the cache stops serving the old value. The simplest approach is to delete or update the cache after the write. A distributed service may publish an invalidation event for other instances or regions. If the business contract allows bounded staleness, it may rely on a TTL instead.

The ordering and failure behavior need to be explicit. If the cache is updated before the database write and the write fails, the cache may advertise data that was never committed. If the database write succeeds but invalidation fails, readers may see stale data until another mechanism repairs the entry. “There are only two hard things” is not a substitute for a defined strategy: specify the authoritative store, the allowed stale window, the event-delivery behavior, and the recovery path.

Decision rule: Use invalidation deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design. For permission-sensitive data, be especially careful: stale authorization information is not merely a cache-quality issue.

4. Stampede

Suppose an expensive key expires. Without coordination, every request that arrives during the miss window can query the source and then attempt to populate the same key. That burst is a cache stampede, also called a thundering herd. It can overload the database even though the cache is functioning as designed.

Request coalescing or single-flight lets one request perform the lookup while other requests wait for the same result. A distributed lock can coordinate across instances, although it adds lease, timeout, and failure concerns. Stale-while-revalidate serves an existing value while one background request refreshes it. Probabilistic early refresh starts some refreshes before expiry to reduce synchronized misses. Each approach changes the freshness, latency, and coordination contract, so the choice should be measured rather than treated as a universal fix.

Decision rule: Address stampedes deliberately when the miss path could overwhelm the source. Choose a mechanism whose lock, waiting, stale-read, or refresh behavior you can describe and test. A single-flight guard inside one process does not protect a multi-instance service unless the coordination scope matches the failure mode.

5. Hot keys

High cache hit rate does not guarantee even load. If one key accounts for a large share of requests, the shard holding it, the network path to that shard, or the process serving it can become a bottleneck. This is a hot-key problem, not necessarily a cache-capacity problem.

Depending on the workload, replicate the value into local caches, place replicas behind a read path, shard the key by suffix and aggregate the results, or redesign the access pattern. Replication can reduce concentration but makes invalidation and memory usage harder. Suffix sharding can distribute reads but is awkward for writes and requires aggregation. A local cache can be fast, but it introduces another freshness boundary.

Decision rule: Handle hot keys deliberately when one access pattern overloads a shard or network path. Confirm the concentration with per-key or sampled-key metrics before adding complexity. A global hit-rate metric can hide the exact key causing the incident.

6. Negative caching

Repeated requests for an identifier that does not exist can also overload the source. Negative caching stores the “not found” result for a limited period and prevents the same miss from reaching the database repeatedly. This is useful for malformed or frequently probed IDs, but it has a specific correctness risk: if the record is created while the negative entry is present, readers can continue to receive “not found.”

Use a short TTL for negative entries, or invalidate them when the corresponding record is created. The appropriate duration depends on how quickly new data must become visible and how costly repeated misses are. Do not assume that negative caching is harmless simply because it stores no positive data.

Decision rule: Use negative caching deliberately when repeated absence is expensive and a bounded period of invisibility is acceptable. Make its shorter freshness window and creation-time invalidation behavior part of the contract.

Worked example

Consider a large-scale distributed service whose requirements, traffic, failure modes, cost, and operational constraints must be made explicit. Start by writing the requirement in one sentence, list the input and output contracts, and identify which of the concepts above owns each failure mode. The useful design move is separation: parsing and validation belong at the boundary; domain rules belong in the domain or service layer; persistence rules belong in the database or repository; presentation rules belong in the client. Mixing these concerns can make a happy-path demo look shorter, but it makes cache races and edge cases much harder to reason about.

Client
  |
DNS -> CDN / Edge
  |
Load Balancer -> API instances -> Cache
                          |          |
                          +------> Primary datastore
                          |
                          +------> Queue / Stream -> Workers

In this model, ask which layer owns each decision. The CDN or edge may cache a response, the API instance may use a local cache, and the shared cache may sit in front of the primary datastore. Those are separate caches with separate invalidation and freshness behavior. A write that updates the datastore does not automatically update every layer unless the design provides that path.

Walk the example with at least four cases: the normal path, an empty or missing value, a duplicate, retry, or concurrent path where relevant, and a dependency failure. For each case, state which layer detects the problem and what the caller observes. For a missing ID, decide whether the result is a short-lived negative cache entry. For simultaneous misses, decide whether requests coalesce. For a permission-sensitive object, state whether stale data is allowed at all and how a successful write invalidates it. This is the level of explanation expected in a senior code review or technical interview.

Production perspective

Production correctness is broader than “the code works on my machine.” Ask how the design behaves during deploys, retries, partial failure, stale clients, concurrent requests, malformed data, schema changes, and high cardinality. A cache adds another stateful boundary, so observe hit and miss rates, eviction counts, entry age, refresh failures, invalidation lag, waiters on single-flight work, and concentration by key where practical. Prefer explicit contracts, bounded resource usage, structured errors, and measurable behavior. Optimize only after evidence identifies the bottleneck or risk.

When the topic involves an external dependency, define a timeout and cancellation strategy. A request waiting behind a single-flight operation still needs a way to stop waiting. When it involves persistence, define transaction and consistency expectations, including what happens if the write succeeds but invalidation does not. When it involves user-visible state, define loading, empty, error, stale, and success states. When it involves security, assume the client can be modified and the network input is untrusted. Never let a cache hit substitute for server-side authorization.

Guided lab

Simulate a cache stampede on an expensive lookup, then add single-flight and TTL jitter. Define invalidation for a permission-sensitive object and a negative-cache TTL for missing IDs. The lab should show not only that the hit rate improves, but also what happens to source load, request latency, stale responses, and recovery when the source fails.

Complete the lab with this discipline:

Write the requirement and two non-requirements.
List input, output, and error contracts before implementation.
Implement the smallest correct vertical slice.
Add at least one invalid-input test and one edge-case test.
Instrument or inspect the behavior instead of guessing. Look at concurrent source calls, cache age, and the result returned to callers.
Refactor one hidden assumption into an explicit type, constraint, function, or configuration.
Explain one alternative design and why you did not choose it.
Record a short “what would break at 10× scale?” note. Consider hot-key concentration, invalidation traffic, memory, and the load generated by misses.

Edge cases and failure modes

TTL: Test absence, malformed input, duplicates, ordering and concurrency where applicable, and behavior at the smallest and largest credible sizes. Also test synchronized expiry and verify that jitter prevents an avoidable burst.
Eviction: Test absence, malformed input, duplicates, ordering and concurrency where applicable, and behavior at the smallest and largest credible sizes. Confirm that an evicted entry is rebuilt safely and that eviction does not remove a value the system incorrectly treats as durable.
Invalidation: Test absence, malformed input, duplicates, ordering and concurrency where applicable, and behavior at the smallest and largest credible sizes. Exercise a successful write followed by invalidation failure or delayed delivery.
Stampede: Test absence, malformed input, duplicates, ordering and concurrency where applicable, and behavior at the smallest and largest credible sizes. Verify the number of source calls when many requests miss together, including timeout and source-failure behavior.
Hot keys: Test absence, malformed input, duplicates, ordering and concurrency where applicable, and behavior at the smallest and largest credible sizes. Measure whether replication, local caching, or sharding actually moves load away from the bottleneck.

Common mistakes and debugging

Solving the example instead of the requirement: a copied pattern can be syntactically correct but architecturally wrong.
Hiding uncertainty with assertions, broad exception handlers, permissive schemas, or “temporary” any values.
Testing only the happy path and therefore discovering contracts only after integration.
Optimizing before measuring, or selecting a scalable mechanism without a scale requirement.
Letting client-side behavior stand in for server-side authorization, validation, or persistence guarantees.
Treating a high overall hit rate as proof that there are no hot keys or stampedes.
Treating eviction as data loss, or treating TTL as an invalidation guarantee without checking the freshness contract.

For debugging, reproduce the smallest failing case and inspect the actual value, key, age, expiry, and execution plan. Trace the boundary where the invariant first becomes false: source or build, browser or DOM, Network or HTTP, server or route, database or query, or deployment or configuration. A sudden source-load spike with many simultaneous misses suggests a stampede; a high hit rate with one overloaded shard suggests a hot key; old values after a successful write suggest invalidation ordering or delivery trouble. Fix the owning layer rather than adding a downstream patch.

Interview questions

What problem does TTL solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Eviction solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Invalidation solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Stampede solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Hot keys solve, and what trade-off or failure mode would make you choose a different approach?

Checkpoint

Without notes, explain Caching II: TTL, Eviction, Invalidation, Stampedes, Hot Keys, and Consistency to another developer in five minutes. Your explanation must include one invariant, one edge case, one production failure mode, and one alternative design. Then implement a small example without copying the lesson code. Be ready to explain what happens when the entry expires, is evicted, is invalidated late, is requested concurrently, or becomes disproportionately popular.

Mastery checklist

I can define the core terms precisely.
I can choose a design from requirements instead of from habit.
I can implement and test the normal path and edge cases.
I can explain the runtime, storage, or complexity cost.
I can identify which layer owns validation, errors, and recovery.
I can compare at least two reasonable alternatives.
I can explain how the design changes at larger scale or stricter reliability.