Cache Invalidation

What it is

Cache invalidation is the process of removing or updating stale entries in a cache when the underlying data changes. Phil Karlton famously quipped that cache invalidation is one of only two hard problems in computer science. The difficulty stems from the inherent tension between performance (keep data in cache as long as possible) and correctness (ensure cached data reflects reality). Every invalidation strategy involves tradeoffs between staleness, consistency, complexity, and the risk of thundering herds on mass invalidation events.

Three primary strategies exist: TTL-based invalidation (data expires automatically after a fixed duration), event-based invalidation (the write path explicitly deletes or updates cache entries when data changes), and write-through invalidation (every write simultaneously updates the cache). Advanced techniques include tag-based invalidation (grouping related keys under a logical tag so all can be invalidated with a single operation) and probabilistic early expiration (pre-emptively refreshing entries before they expire to avoid stampedes).

Why it exists

Without invalidation, caches would serve stale data indefinitely. A product price updated in the database would continue to appear as the old price to all customers until the cache process is restarted. For many business domains — pricing, inventory, user permissions, account status — this is completely unacceptable. Invalidation is what allows systems to use caching aggressively while maintaining data correctness for data that changes.

The challenge is compounded in distributed systems where multiple application instances write independently to a shared cache. A write on instance A must also invalidate the cache entry visible to instances B and C. In multi-region systems, a write in US-East must eventually invalidate the cached copy in EU-West. These coordination requirements introduce complexity, latency, and potential for race conditions that must be carefully managed.

When to use

• You have a cache with meaningful TTLs and writes happen frequently enough that waiting for TTL expiry would serve significantly stale data.
• Correctness requirements demand that users see updated data promptly after writes (user profile changes, permission updates, pricing changes).
• You are using CDN caching for content that needs to be refreshed on demand (new article published, price changed).
• You have related cache keys that must be invalidated together (a user's profile AND their public summary page, both cached separately).
• You need to implement a "stale-while-revalidate" pattern where background refresh avoids latency spikes on cache miss.

When not to use

• Data is effectively immutable or changes on a known schedule — TTL alone is sufficient and event-driven invalidation adds unnecessary complexity.
• The invalidation overhead (network round trips, distributed lock acquisition) exceeds the benefit for low-traffic keys.
• The data is not in a shared cache but in a process-local cache — invalidation is simpler (just delete the local entry) but multi-instance consistency is not achievable without a distributed signal.
• The consistency window (staleness) is acceptable for the use case — leaderboard rankings stale by 5 minutes cause no harm.

Typical architecture

  Strategy 1: TTL-Based (passive expiry)
  Write to DB → cache naturally expires after TTL
  └─ Pro: simple   └─ Con: data stale until TTL elapses

  Strategy 2: Event-Based Invalidation (active)
  Write to DB
       │
       ├──► DEL cache_key (or publish invalidation event)
       │
       └──► Next read is a miss → re-populate cache

  Strategy 3: Tag-Based Invalidation
  Cache tags:
    product:42:detail  → tags: [product, product:42, category:electronics]
    product:42:summary → tags: [product, product:42]
    category:electronics:list → tags: [product, category:electronics]

  On product 42 update:
    invalidate_tag("product:42")
    → deletes product:42:detail AND product:42:summary in one call

  Strategy 4: Probabilistic Early Expiration (XFetch)
  // Avoid stampede: re-compute before TTL expires
  β = 1.0   // tuning parameter
  δ = time to recompute (seconds)
  t_expires = TTL expiry timestamp

  if current_time - β * δ * log(rand()) >= t_expires:
    recompute and refresh cache

  CDN Invalidation (CloudFront, Fastly):
  HTTP PURGE or API call → invalidation propagated to all PoPs
  └─ Takes 5–30 seconds to propagate globally
          

Pros and cons

Implementation notes

Delete vs. update on invalidation: The safest approach is to delete (DEL) the cache key rather than updating it atomically. Updating the cache from the write path risks cache poisoning: if the write transaction rolls back after the cache update, the cache holds data that was never committed to the database. Delete-on-write is safe: the next read will miss and re-populate from the committed database state. The pattern is: 1) write to DB; 2) on successful commit, DEL the affected cache keys. The brief period between delete and re-population introduces one cache miss but guarantees consistency.

Race condition on invalidation: The classic race: (1) Thread A reads from DB; (2) Thread B writes to DB and invalidates cache; (3) Thread A writes stale data to cache. The cache now holds the old value after the invalidation. This is inherent to cache-aside with concurrent writes and misses. Mitigation options: use a short TTL as a safety net; use optimistic locking (store a version with the cached value, only write-back if version matches current); use CDC (Change Data Capture) to drive invalidations from the database WAL rather than the application write path, ensuring invalidations are ordered correctly relative to writes.

Common failure modes

• Invalidation race condition: A read re-populates a cache key with stale data after the invalidation event was processed. Use short TTL as a fallback safety net alongside event-driven invalidation.
• Mass invalidation stampede: A bulk update invalidates thousands of cache keys simultaneously; all subsequent reads miss and hammer the database concurrently. Use staggered invalidation or background refresh queues.
• Cache poisoning: Malformed or tampered data is written to the cache (via injection or a buggy write path) and served to all users until TTL expires. Validate data before caching; never cache data from untrusted sources without validation.
• Tag index inconsistency: The tag-to-key mapping becomes inconsistent if the tag index update and the cache write are not atomic. Use Redis transactions (MULTI/EXEC) or Lua scripts to ensure atomicity.
• CDN stale content after purge failure: A CDN purge API call fails silently; users continue to see old content until TTL expires. Implement retry logic and monitoring for purge API responses.

Decision checklist

• Acceptable staleness window has been defined per data type and informs whether TTL-only or event-driven invalidation is needed.
• The invalidation strategy (delete vs. update) is chosen; delete-on-write is preferred for correctness.
• Race conditions between concurrent reads and invalidations have been analyzed and mitigated (short TTL, version checks, CDC).
• Mass invalidation events are handled with rate limiting, queuing, or staggered invalidation to prevent stampedes.
• CDN cache purge operations are monitored for failures; retry logic and alerts are in place.
• Cache entries storing sensitive data (user permissions, access tokens) are invalidated immediately on security-relevant events (password change, revocation).

Example use cases

• CMS article publishing: When an editor publishes an updated article, the application sends a CDN purge request for the article URL and deletes the article's Redis cache key. Readers see the new content within 10 seconds (CDN propagation time).
• User permission changes: When an admin revokes a user's access, the application immediately DELs the user's permission cache entry in Redis, ensuring the next API request re-fetches from the database and enforces the new permissions.
• E-commerce pricing engine: Product prices are cached with a 5-minute TTL. When a price change event is published to Kafka, a consumer explicitly invalidates the affected product cache keys, ensuring the new price is visible within seconds rather than waiting for the 5-minute TTL.

Related patterns

• Caching Strategies — the foundational article covering cache-aside, write-through, and other read/write patterns.
• CDN Architecture — CDN cache invalidation (purging) is a specialized form of this problem at global network scale.
• Event Notification — event-driven invalidation relies on publishing change events from the write path to cache consumers.

Further reading

• Redis — Keyspace Notifications (event-driven invalidation)
• Facebook TAO — Cache Invalidation at Scale
• Fastly — Cache Purging and Invalidation Guide