Cache Invalidation

This is an active strategy where the application logic explicitly removes or updates cache entries when the underlying data changes. This is often triggered by write operations (POST, PUT, DELETE) in an application's API.

• Implementation: The application calls the cache's DELETE or SET command after successfully updating the primary database.
• Challenge: Requires precise knowledge of which cache keys correspond to the modified data, which can be complex with denormalized or computed views. In distributed systems, this can lead to race conditions if not carefully sequenced.

These are proactive strategies that tie cache updates directly to database writes.

• Write-Through Cache: The application writes data to the cache and the primary database synchronously. The write is not considered complete until both succeed. This guarantees cache consistency but adds latency to write operations.
• Write-Behind Cache (Write-Back): The application writes only to the cache, which acknowledges immediately. The cache then asynchronously batches writes to the database later. This offers very low write latency but risks data loss if the cache fails before the batch is persisted.

A sophisticated strategy for managing dependencies. Instead of tracking individual keys, related data is associated with one or more tags (e.g., user:123, product:456). When the underlying data for a tag changes, all cache entries marked with that tag are invalidated in a single operation.

• Use Case: Ideal for content management systems or e-commerce platforms where a single product update should invalidate the product page, category listing, and search results.
• Example: A framework like django-cacheops or Laravel's cache system uses tagging to manage complex relationships efficiently.

Leverages a publish-subscribe model or database change data capture (CDC) streams for near-real-time cache coherence. The cache client subscribes to events published by the primary database or an application event bus.

• Mechanism: When a record is updated, the database (e.g., via PostgreSQL's LISTEN/NOTIFY or Debezium) emits an event. A dedicated service or the cache clients listen for these events and invalidate the corresponding cache keys.
• Benefit: Decouples the application logic from invalidation logic and provides very low latency between source update and cache refresh.

A strategy that avoids the thundering herd problem and delete/update races. Instead of invalidating by deletion, a new version of the data is written under a new key.

• Process: The cache key includes a version number or generation ID (e.g., product_456:v2). When data changes, the generation is incremented. Clients always read using the latest known version identifier, which can be stored in a fast, separate lookup.
• Advantage: Old versions remain available until garbage collected, eliminating race conditions where a stale delete might cause a flood of simultaneous database queries. This pattern is fundamental to systems like Facebook's McRouter.

A predetermined algorithm that determines which items to remove from a cache when it reaches its capacity limit. It is the proactive counterpart to invalidation, managing space rather than correctness.

• Purpose: Makes space for new entries by selecting victims based on a heuristic.
• Common Policies: Include LRU (Least Recently Used), LFU (Least Frequently Used), and FIFO (First-In, First-Out).
• Relationship to Invalidation: Eviction policies often handle capacity-driven removal, while invalidation handles correctness-driven removal due to source data changes.

A time-based expiration mechanism that sets a lifespan on cached data. It is a simple, proactive form of invalidation that does not require explicit signals from the source.

• Mechanism: Each cache entry is stamped with an expiration timestamp upon creation or update.
• Operation: The cache system periodically scans for and evicts entries whose TTL has elapsed.
• Use Case: Ideal for data that has a known, natural staleness (e.g., weather data, promotional content) where exact update events are unknown.

A storage optimization where data modifications are written only to the cache initially, deferring the update to the backing store. This creates a critical invalidation dependency.

• Process: Write operations complete at cache speed. Modified ("dirty") data is written to the primary database later, often on eviction.
• Invalidation Complexity: Other caches holding the same data must be invalidated once the write-back occurs to the source, requiring a coordinated invalidation broadcast.
• Risk: Data loss if the cache fails before the write-back completes.

A performance anti-pattern that can be triggered by a cache invalidation event. When a popular cache item expires or is invalidated, a sudden surge of parallel requests attempts to recompute the same value, overwhelming the backend.

• Cause: Simultaneous cache misses for the same key after invalidation.
• Mitigation Strategies:
  • Stale-While-Revalidate: Serve stale data while one request fetches an update.
  • Request Coalescing: Deduplicate concurrent requests for the same key.
  • Probabilistic Early Expiration: Randomize refresh times before the actual TTL.

A database isolation technique that maintains multiple versions of a data item. It provides an elegant solution to the read-write conflict inherent in cache invalidation.

• How it Works: Writers create a new version of a row; readers continue to access the older, consistent version until their transaction completes.
• Impact on Caching: Caches can store specific versions. Invalidation becomes less urgent because readers with stale caches are still served a correct (though older) snapshot.
• Benefit: Eliminates the need to immediately invalidate caches on every write, reducing latency spikes.

A probabilistic, memory-efficient data structure used to test set membership. It optimizes cache invalidation in distributed systems by reducing unnecessary network calls.

• Function: Answers "Is this key possibly in the cache?" or "definitely not in the cache?" with a controlled false-positive rate.
• Invalidation Application: A client can maintain a local Bloom filter representing the remote cache's contents. Before fetching data, it checks the filter. A "definitely not" result avoids a costly cache miss query entirely.
• Efficiency: Uses significantly less memory than storing the full key list, enabling broader invalidation hinting.