Versioned and Generational Keys: Avoiding Delete Storms with Namespace Epochs

The Delete Storm Problem
When updating one popular object requires invalidating hundreds or thousands of derived cache entries, explicit deletion creates an N:1 fan out that overloads invalidation infrastructure and collapses cache hit rates. A viral post appearing in millions of user feeds would require millions of delete operations. Versioned keys solve this by embedding a version into the cache key itself. When data changes, increment the version, causing all readers to naturally shift to new keys while old entries expire via TTL without explicit deletion. This transforms O(N) invalidation into O(1).
Per Object Versioning
Embed a monotonically increasing version into each key: instead of post:12345, cache post:12345:v7. When post 12345 updates, increment to v8 and store that mapping in a fast metadata store (often cached with short TTL). Readers fetch current version, construct the key, and old v7 entry becomes unreachable, expiring naturally. Works well for individual hot objects but requires version lookups on cache miss.
Generation Epochs
Group related keys under a shared generation counter: feed:g5:user:789 where g5 is current generation. When needing to invalidate the entire namespace (user changed privacy settings), bump generation to g6 in O(1) time, instantly invalidating all feed entries without touching individual keys. Coarser than per object: bumping generation causes temporary cache miss spike as all entries rebuild, but avoids overwhelming invalidation infrastructure with thousands of delete operations.
Trade offs and Requirements
Versioned keys add version lookup latency on cache miss unless versions are cached with aggressive TTL. Generation epochs cause temporary hit rate drops and origin load spikes during rebuild. Both patterns still require TTL as backstop to eventually reclaim space from unreachable old keys. Choose per object versions for precise invalidation when version lookups are affordable; use generation epochs for bulk invalidation when temporary miss spikes are acceptable.

💡 Key Takeaways

✓Versioned keys transform O(N) fan out invalidations into O(1) by embedding version in key. Old entries become unreachable and expire via TTL.

✓Per object versioning (post:12345:v7 to v8) provides precise invalidation but requires version metadata lookups on cache miss.

✓Generation epochs (feed:g5 to g6) invalidate entire namespaces atomically in O(1), ideal for bulk invalidations but cause temporary hit rate drops.

✓Both require TTL as backstop to reclaim space from unreachable old generation keys.

📌 Interview Tips

1Explain delete storm: viral post in millions of feeds requires millions of deletes. Versioning makes it one version bump.

2Per object versioning: post:12345:v7 becomes v8, readers fetch current version first, old entry expires naturally via TTL.

3Generation epochs: user privacy change bumps feed:g5 to g6, all feed entries invalidated instantly without per key deletes.

← Back to Cache Invalidation Strategies Overview